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.
A Task Mapping Algorithm for Linear Array Processors
Tsuyoshi KAWAGUCHI Yoshinori TAMURA Kouichi UTSUMIYA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/05/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
linear arrays, task graphs, a mapping algorithm, optimization,
Full Text: PDF(707.2KB)>>
The linear array processor architecture is an important class of interconnection structures that are suitable for VLSI. In this paper we study the problem of mapping a task tree onto a linear array to minimize the total execution time. First, an optimization algorithm is presented for a message scheduling probrem which occurs in the task tree mapping problem. Next, we give a heuristic algorithm for the task tree mapping problem. The algorithm partitions the node set of a task tree into clusters and maps these clusters onto processors. Simulation experiments showed that the proposed algorithm is much more efficient than a conventional algorithm.