Scheduling a Task Graph onto a Message Passing Multiprocessor System

Tsuyoshi KAWAGUCHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.6   pp.670-677
Publication Date: 1992/06/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1991 Joint Technical Conference on Circuits/Systems, Computers and Communications (JTC-CSCC '91))
Category: Combinational/Numerical/Graphic Algorithms
scheduling,  a network, a routing algorithm,  an optimization algorithm,  time complexity,  

Full Text: PDF>>
Buy this Article

In this paper we study the problem of scheduling parallel program modules onto an MPS (message passing multiprocessor system) so as to minimize the total execution time. Each node in the interconnection network of the MPS has buffers at its input ports to store messages waiting for the transmission. An algorithm for finding a route which minimizes the communication delay of a message to be sent between a processor-pair is first given. Next, we present heuristic algorithms for scheduling program modules onto the MPS. These algorithms use the above routing algorithm. The performances of the proposed algorithms are estimated by using simulation experiments.