JISE


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


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


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

  Retrieve PDF document (JISE_200302_02.pdf)