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

Journal of Inforamtion Science and Engineering, Vol.11 No.3, pp.453-463 (September 1995)
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

Received August 24, 1994; revised February 6, 1995.
Communicated by Shing-Tsaan Huang.