Quick buddy-subcube compaction in hypercubes

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.