A New Graph Approach to Minimizing Processor Fragmentation in Hypercube Multiprocessors

We propose a new approach for subcube and noncubic processor allocations for hypercube multiprocessors. The main idea is to represent available processors in the system by means of a prime cube graph (PC-graph). The PC-graph maintains the inter-relationships between free subcubes and hence reduces both internal and external processor fragmentations. Our simulation results show that the PC-graph approach outperforms the existing allocation strategies by 25% to 50% under certain load conditions. © 1993 IEE