CONTENTION-FREE 2D-MESH CLUSTER ALLOCATION IN HYPERCUBES

Traditionally, each job in a hypercube multiprocessor is allocated wit h a subcube so that communication interference among jobs may be avoid ed. Although the hypercube is a powerful processor topology, the 2D me sh is a more popular application topology. This paper presents a 2D-me sh cluster allocation strategy for hypercubes. The proposed auxiliary free list processor allocation strategy can efficiently allocate 2D-me sh clusters without size constraints, can reduce average job turnaroun d time compared with that based on subcube allocation strategies, and can guarantee no communication interference among allocated clusters w hen the underlying hypercube implements deadlock free E-cube routing. The proposed auxiliary free list strategy can be easily implemented on hypercube multicomputers to increase processor utilization.