DocumentCode :
1052178
Title :
A systematic approach for mapping application tasks in hypercubes
Author :
Kavianpour, A. ; Bagherzadeh, N.
Author_Institution :
Dept. of Electr. & Comput. Eng., California Univ., Irvine, CA, USA
Volume :
42
Issue :
6
fYear :
1993
fDate :
6/1/1993 12:00:00 AM
Firstpage :
742
Lastpage :
746
Abstract :
A systematic approach for mapping application tasks to hypercubes is proposed. This method is based on a partitioning algorithm in which the final mapping is rendered as a task-node tuple assignment for an n-cube system. For this method, a single-tasking environment in which each task is assigned to a unique processor is assumed. Dilation-bound and expansion-ratio parameters are used to evaluate the efficacy of this mapping algorithm. An algorithm that minimizes the expansion-ratio parameter is introduced. In addition, an algorithm that reduces the dilaton bound is proposed. Because of the structured formation of the algorithms, they can be applied to any given task structure. As an illustration of the effectiveness of this method, the proposed algorithms are applied to mapping complete binary and d-ary tree task structures to hypercubes
Keywords :
hypercube networks; resource allocation; dilaton bound; expansion-ratio; hypercubes; mapping application tasks; n-cube system; partitioning algorithm; tree task structures; Application software; Approximation algorithms; Costs; Hypercubes; Iterative algorithms; Partitioning algorithms;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.277294
Filename :
277294
Link To Document :
بازگشت