A Task Mapping Algorithm for Linear Array Processors

Tsuyoshi KAWAGUCHI; Yoshinori TAMURA; Kouichi UTSUMIYA

A Task Mapping Algorithm for Linear Array Processors

Tsuyoshi KAWAGUCHI, Yoshinori TAMURA, Kouichi UTSUMIYA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.5 pp.546-554

Publication Date: 1994/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Tsuyoshi KAWAGUCHI, Yoshinori TAMURA, Kouichi UTSUMIYA, "A Task Mapping Algorithm for Linear Array Processors" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 5, pp. 546-554, May 1994, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_5_546/_p

Copy

@ARTICLE{e77-d_5_546,
author={Tsuyoshi KAWAGUCHI, Yoshinori TAMURA, Kouichi UTSUMIYA, },
journal={IEICE TRANSACTIONS on Information},
title={A Task Mapping Algorithm for Linear Array Processors},
year={1994},
volume={E77-D},
number={5},
pages={546-554},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A Task Mapping Algorithm for Linear Array Processors
T2 - IEICE TRANSACTIONS on Information
SP - 546
EP - 554
AU - Tsuyoshi KAWAGUCHI
AU - Yoshinori TAMURA
AU - Kouichi UTSUMIYA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1994
AB - 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.
ER -