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


Journal of Information Science and Engineering, Vol.19 No.2, pp.205-227 (March 2003)

Quick Buddy-Subcube Compaction in Hypercubes

Hsing-Lung Chen and Shu-Hua Hu*
Department of Electronic Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan
*Department of Electronic Engieering
Jin-Wen Institute of Technology
Hsintien, Taipei, 231 Taiwan

After repeated subcube allocation and deallocation, the hypercube system tends to become fragmented, which can be taken care of by using subcube compaction. Basic buddy-subcube compaction deals with compacting free buddy-subcubes with the same dimension concurrently. All migration paths are pairwise disjoint and contain no links of active subcubes, so that task migration can be performed without suspending the execution of other jobs. This paper considers quick buddy-subcube compaction in that not only can free subcubes with two adjacent dimensions be compacted concurrently, but two disjoint paths can be established between every pair of source-target nodes. Parallel subcube compaction with two concurrent dimensions apparently speeds up subcube compaction by a factor of two. The use of double disjoint paths between each pair of source-target nodes also speeds up subcube compaction by a factor of nearly two. Thus, our approach can speed up subcube compaction by a factor of nearly four.

Keywords: buddy strategy, disjoint paths, fragmentation, hypercubes, subcubes, task migration

Full Text () Retrieve PDF document (200303_02.pdf)

Received April 10, 2001; revised December 25, 2001; accepted March 13, 2002.
Communicated by Gen-Huey Chen.