JISE


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


Journal of Information Science and Engineering, Vol. 11 No. 3, pp. 453-463


Fast Subcube Compaction in Hypercubes with the Buddy Allocation Strategy


Hsing-Lung Chen
Department of Electronic Engineering 
National Taiwan Institute of Technology 
43,Keelung Road, Section 4 
Taipei, Taiwan, R.O.C.


    Repeated subcube allocation and deallocation tend to make a system fragmented, which can be taken care of by migrating tasks so as to compact free paction strategy for a hypercube system using the buddy allocation strategy, which takes at most dmigration steps to free up a d-subcube. In each migration step, data for several source-target subcubes are moved simultaneously. However, it dealt with the establishment of a single path from eavh participating node for transmitting migrated information. Since task migration often needs to transmit a large amount of information, the time required for migration with single paths could be long. This paper considers fast task migration in that two disjoint parts are established between every pair of source-target nodes for transmisssion of information simultaneously, thus reducing the size of a message over a path. All selected 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 approach could lead to a considerable saving in migration time for hypercubes which support circuit switching or wormhole routing.


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

  Retrieve PDF document (JISE_199503_07.pdf)