IEICE TRANSACTIONS on Fundamentals
Scheduling a Task Graph onto a Message Passing Multiprocessor System
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.6 pp.670-677
- Publication Date
- 1992/06/25
- Publicized
- Online ISSN
- DOI
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tsuyoshi KAWAGUCHI, "Scheduling a Task Graph onto a Message Passing Multiprocessor System" in IEICE TRANSACTIONS on Fundamentals,
vol. E75-A, no. 6, pp. 670-677, June 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_6_670/_p
Copy
@ARTICLE{e75-a_6_670,
author={Tsuyoshi KAWAGUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Scheduling a Task Graph onto a Message Passing Multiprocessor System},
year={1992},
volume={E75-A},
number={6},
pages={670-677},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Scheduling a Task Graph onto a Message Passing Multiprocessor System
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 670
EP - 677
AU - Tsuyoshi KAWAGUCHI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 1992
AB - 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.
ER -
English
