Liang Liu, Hyeong-Ah Choi and Shmuel Rotenstreich
Department of Electrical Engineering and Computer Science
The George Washington University
Washington, DC 20052
A partitionable hypercube may not find a subcube of the requested dimension due to fragmentaion, despite the availability of a sufficient number of free nodes. Compaction can make a subcube of the requested dimension available by migrating some tasks. In all previously proposed migration schemes, tasks are migrated sequentially. In this paper, we propose simultaneous task migration, which migrates several tasks simultaneously, through mutually link-disjoint paths. We show that the problem of minimizing the total migration times is NP-complete. An heuristic algorithm is devised, and simulation results are provided.
Keywords: hypercube, circuit-switching, compaction, migration, allocation, fragmentation, scheduling, NP-complete
Received December 12, 1992; revised April 15, 1993.
Communicated by Chuan-lin Wu.