Title :
Static allocation of a task tree onto a linear array
Author :
Kawaguchi, Tsuyoshi
Author_Institution :
Dept. of Electron. Eng., Miyazaki Univ., Japan
Abstract :
The linear array processor architecture is an important class of interconnection structure that is suitable for VLSI. A heuristic algorithm is presented for mapping a task tree onto a linear array to minimize the total execution time. The algorithm partitions the node set of the task tree into clusters and maps these clusters onto processors. Simulation experiments show that the proposed algorithm is much more efficient than a conventional algorithm
Keywords :
VLSI; integrated circuit interconnections; systolic arrays; trees (mathematics); VLSI; clusters; heuristic algorithm; interconnection structure; linear array; node set; processor architecture; systolic arrays; task graphs; task tree; total execution time; Algorithm design and analysis; Clustering algorithms; Heuristic algorithms; Multiprocessor interconnection networks; Network topology; Parallel machines; Partitioning algorithms; Systolic arrays; Tree graphs; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-1281-3
DOI :
10.1109/ISCAS.1993.394125
