[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 2, pp. 301-311 (March 2000)

Allocation-Time-Based Processor Allocation Scheme for
2D Mesh Architecture*

Xiaomei Zhu and Wei-Ming Lin
Department of Computer Science
Personal System Group
Dell Computer Corp.
Austin, TX 78758-4055, U.S.A.
E-mail: Xiaomei_Zhu@Dell.Com
+Division of Engineering
The University of Texas at San Antonio
San Antonio, TX 78249, U.S.A.
E-mail: wlin@voyager1.utsa.edu

Mesh is a widely used architecture in parallel computing systems. Research on efficient allocation of processors to incoming tasks on mesh architecture is very important in achieving the desired high performance. The processor allocation strategy proposed in this paper is based on a well-known boundary search approach and considers allocation time as a primary allocation decision-making factor. In this proposed technique, an additional novel heuristic is employed to consider, whenever feasible, having adjoining submeshes allocated to tasks with similar allocation times. The external fragmentation problem is expected to be alleviated, leading to improvement in utilization and shorter task waiting time. Another novel add-on feature is also employed to provide extra improvement. Our simulation results demonstrate substantial improvement in performance.

Keywords: parallel processing, processor allocation, mesh architecture, processor utilization, task waiting delay

Full Text () Retrieve PDF document (200003_08.pdf : 3,563,874 bytes)

Received March 26, 1999; revised July 5, 1999; accepted September 8, 1999.
Communicated by Chyi-Nan Chen.
This research was supported in part by the Office of Naval Research under grants N00014-95-1-0514 and N00014-96-1-0897, and in part by the Department of Defense/Air Force Office of Scientific Research under grant F49620-96-1-0472