For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Scheduling a Task Graph onto a Message Passing Multiprocessor System
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/06/25
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>>
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.