An Effective Task Allocation Algorithm in Two-Dimensional Mesh Interconnection Networks


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 6, pp. 1667-1677, Jun. 1999
10.3745/KIPSTE.1999.6.6.1667,   PDF Download:

Abstract

An effective allocation of requested number of processors to newly incoming tasks in two-dimensional (2D) mesh interconnection networks is very important for achieving the desired high performance and resource utilization. It also needs to guarantee the complete recognition of the free submeshes based on contiguous and available processors with minimum overhead. An efficient task allocation algorithm for 2D meshes is presented in this paper. By employing a new approach for searching the one-dimensional array, the proposed algorithm can find the available submesh without the scanning of the entire 2D array unlike earlier designs. As a result, the new algorithm can significantly reduce the task allocation time. Comprehensive computer simulation shows that the average allocation time and waiting delay are much smaller than earlier designs irrespective of the size of meshes. The hardware overhead is comparable to other algorithms.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
C. H. Seung, P. G. Leen, Y. S. Moo, "An Effective Task Allocation Algorithm in Two-Dimensional Mesh Interconnection Networks," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 6, pp. 1667-1677, 1999. DOI: 10.3745/KIPSTE.1999.6.6.1667.

[ACM Style]
Choo Hyun Seung, Park Gyung Leen, and Yoo Seong Moo. 1999. An Effective Task Allocation Algorithm in Two-Dimensional Mesh Interconnection Networks. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 6, (1999), 1667-1677. DOI: 10.3745/KIPSTE.1999.6.6.1667.