A Task Mapping Algorithm for Linear Array Processors

Tsuyoshi KAWAGUCHI  Yoshinori TAMURA  Kouichi UTSUMIYA  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.5   pp.546-554
Publication Date: 1994/05/25
Online ISSN: 
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)>>
Buy this Article

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.