JISE


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


Journal of Information Science and Engineering, Vol. 9 No. 1, pp. 27-44


Simultaneous Task Migration Problem on Partitionable Circuit-Switched Hypercubes


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

  Retrieve PDF document (JISE_199301_02.pdf)