Generation of Maximally Parallel Task Systems

When tasks are executed in parallel, precedence constraints are placed between mutually interfering tasks in order to ensure the consistency of the results. Sometimes these precedence constraints may be over-specified, in which case the number of tasks executed in parallel may not be maximal. Maximum parallelism can be obtained by removing such unnecessary precedence constraints. The purpose of this thesis was to design and develop a software tool to help study the maximal parallelism extraction algorithm. The tool takes a randomly generated task system as input, checks the task system for determinacy, and generates the corresponding maximally parallel task system for randomly generated domains and ranges. The tool was developed on the Computer Science Department's Sequent Symmetry SIS 1 computer system running the DYNIX/ptx operating system. The tool was coded in the C++ programming language using Motif toolkit. The user interface of the tool is based on MotifApp framework. The tool has 37 classes and three major class hierarchies. The results obtained were extensively studied and graphs showing the perfomance of the maximal parallelism extraction algorithm were drawn for the average, best, and worst cases. It was found that the number of tasks did not play a significant part in the increase in parallelism. The increase in parallelism was found to be generally dependent on the ratio of the number of total memory cells to the number of domain/range cells. As the ratio increases, the there is more in parallelism in the maximally parallel task system in comparison to the original determinate task system. And, as the ratio decreases, there is a less increase in the degree of parallelism, the worst case being when there is no increase in parallelism. Significant increase in parallelism in the maximally parallel task system was found when the ratio of the number of memory cells to the number of domain/range cells was greater than ten