FAST COMPACTION IN HYPERCUBES

Compaction relocates active subcubes in a fragmented hypercube so as t o produce a contiguous free region and eliminate the adverse impact of fragmentation on performance. The overhead of compaction is often con tributed primarily by task migration, which makes use of disjoint path s for transmitting migrated data. Since task migration usually involve s transmitting a large amount of data, the time required for migration with single paths is long, making compaction an undesirably lengthy p rocess. This paper considers fast compaction through the use of all di sjoint paths in existence for migration simultaneously from a source s ubcube to its target subcube, effectively reducing the size of data tr ansmitted over a path and shortening the migration time. This approach leads to considerable savings in the compaction time for hypercubes w hich support circuit switching or wormhole routing, when compared with that using single migration paths.