An enhanced 2D buddy strategy for submesh allocation in mesh networks

Tong Ying Tony Juang, Yu-Chee Tseng, Yuh Shyan Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication1997 3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997
EditorsWanlei Zhou, Andrzej Goscinski, Michael Hobbs
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages345-352
Number of pages8
ISBN (Electronic)0780342291, 9780780342293
DOIs
StatePublished - 1 Jan 1997
Event3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997 - Melbourne, Australia
Duration: 10 Dec 199712 Dec 1997

Publication series

Name1997 3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997

Conference

Conference3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997
CountryAustralia
CityMelbourne
Period10/12/9712/12/97

Fingerprint Dive into the research topics of 'An enhanced 2D buddy strategy for submesh allocation in mesh networks'. Together they form a unique fingerprint.

Cite this