Partitionability of k-extra-stage Omega networks and an optimal task migration algorithm

In a large-scale parallel computing system, partitionability is an importan t feature that allows a large system to be partitioned into smaller subsyst ems so that multiple tasks can be run independently on different subsystems . In such a system, a task run on a subsystem may need to be migrated to an other subsystem if the subsystem is faulty, if load balance is needed, or i f subsystem restructuring is desired. This paper studies the partitionabili ty of k-extra-stage Omega networks and presents an optimal task migration a lgorithm for k-extra-stage Omega networks. (C) 2000 Academic Press.