Title :
An enhanced 2D buddy strategy for submesh allocation in mesh networks
Author :
Juang, Tong-Ying Tony ; Tseng, Yu-Chee ; Chen, Yuh-Shyan
Author_Institution :
Dept. of Comput. Sci., Chung-Hua Univ., Taiwan
Abstract :
The efficient allocation problem plays an important role in partitionable multiprocessor system. It is critical to the performance of parallel computers, especially for large-scale parallel computers. In this paper, we propose a new enhanced two-dimensional buddy system (E2DBS) strategy which overcomes the drawbacks of previous two-dimensional buddy system (2DBS) strategy, such as four non-buddy submeshes can be allocated, the requesting tasks and the system needs not be square. In E2DBS, we propose an adaptive data structure, called free sub-mesh matrix (FSM), to maintain the free submeshes, which can allocate and deallocate processors easily. Simulation results indicate that our strategy outperforms the previous ones, i.e. 2DBS strategy and best fit strategy, in terms of system processor utilization and average waiting time under various system loads for rectangle requesting tasks with side lengths are powers of 2
Keywords :
data structures; multiprocessor interconnection networks; performance evaluation; adaptive data structure; best fit strategy; enhanced 2D buddy strategy; free sub-mesh matrix; mesh networks; partitionable multiprocessor system; performance; rectangle requesting tasks; simulation results; submesh allocation; Computer science; Concurrent computing; Data structures; Electronic mail; Intelligent networks; Large-scale systems; Mesh networks; Modular construction; Multiprocessing systems; Scalability;
Conference_Titel :
Algorithms and Architectures for Parallel Processing, 1997. ICAPP 97., 1997 3rd International Conference on
Conference_Location :
Melbourne, Vic.
Print_ISBN :
0-7803-4229-1
DOI :
10.1109/ICAPP.1997.651503