A staged allocation scheme for assigning acyclic task graphs to multiprocessors
Nitindra N. Athavale, Rammohan K. Ragade · 1995
The goal of multiprocessor allocation is to optimally assign a task graph onto a given processor architecture, and thereby minimize the completion times of parallel algorithms. The assignment problem is an NP hard problem. This dissertation presents a graph-based partitioning scheme and an allocation technique called GPGA technique for the allocation problem. Two main algorithms described later are the basis of this dissertation. Implemented in an algorithm called GRAPH PARTITIONER, the partitioning scheme stems from refinement of task graph granularity. Another algorithm called GRAPH ALLOCATOR implements the second phase of the assignment technique. These algorithms work on acyclic directed task graphs to exploit parallelism while maintaining precedence constraints. Task graph partitioning in GPGA technique is different from the data partitioning that designers do. The GRAPH PARTITIONER relies on data partitions created in task graphs. The Stages algorithm dominates the time complexity of the GP algorithm, $O(N\sp2$). The time complexity of the GAlloc algorithm is $O(N\sp2+P\sp2$) The GPGA technique's complexity is the sum of the two complexities $O(N\sp2) + O(N\sp2 + P\sp2$). The designs of these algorithms use efficient data structures in the ANSI C language. These algorithms are implemented on an IBM-PC compatible computer. The GPGA technique produces near-optimal results for various numbers of processors and task graphs in satisfactory time. This dissertation compares GPGA technique's effectiveness with that of a previously developed scheme by Selvakumar et al. The algorithm does not assume a single start node and a single end node. The algorithm works with a smaller set of independent task nodes than the Selvakumar et al. heuristics and uses a full set of processor nodes. Consequently, the GPGA technique heuristics have more degrees of freedom over those in the Selvakumar et al. heuristics. The interstage communication reduction strategy restricts the search space. GPGA technique has less time complexity than the Selvakumar et al. heuristics which is$O(N\sp3P{\mid}E{\mid}$log$\sp2P$). The GPGA technique outperforms the Selvakumar et al. heuristic in all test cases. The results are based on random graphs. This technique produces allocations with the speedup of at least unity. This is the result of optimal selection of processors.