The search functionality is under construction.
The search functionality is under construction.

Scheduling Trees onto Hypercubes and Grids

Satoshi TAYU

  • Full Text Views

    0

  • Cite this

Summary :

In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1011-1019
Publication Date
2002/05/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword