Job migration on a hypercube using the buddy method

An optimal strategy to find multiple shortest parallel free paths between two partitions of the same size, under the buddy method, is given. The buddy method provides a relatively efficient partitioning technique for a hypercube multiprocessor. When a hypercube multiprocessor is partitioned according to the buddy method, the links between partitions are not used. These unused links can be utilized to construct 2^k disjoint paths between two partitions of size k to migrate a job from one partition to another. The authors prove that 2^k disjoint paths using only the unused links always exist between an allocated partition of size k to an unallocated partition of the same size, and the number of such paths is 2^i-1 if the addresses of two partitions differ by i bits. An efficient routing algorithm to construct such path with complexity O(i) is given. Simulation results support the usefulness of such paths