A two-pass approach for optimally assigning linear tasks to multiprocessor systems
Chiun‐Chieh Hsu · International Journal of Systems Science · 1996
The approach presented in this paper is to optimally assign a chain-like task to a multiprocessor system where the optimal assignment is the one with the minimum task turnaround time. Our approach is composed of merge pass and assignment pass. Considering the relationship between execution time and communication time, the merge pass can merge some adjacent modules in the task in order to reduce the maximum completion time among the modules. In some cases, using only the merge pass can obtain an optimal assignment in O(m) time while Sheu and Chiang's method (Sheu and Chiang 1990) requires O(min (m, n)m2) time, where m is the number of modules and n is the number of processors. Even though the merge pass cannot find an optimal solution, the assignment pass can search for an optimal assignment in a small set of possible assignments while Sheu and Chiang's method needs to investigate all possible assignments. A large number of experiments show that the assignment pass only generates a small number of the nodes and edges generated by Sheu and Chaing's method.