PROCESSOR ALLOCATION STRATEGIES FOR MODIFIED HYPERCUBES

Modified hypercubes (MHs) have been proposed as building blocks for hy percube-based parallel systems that support the application of increme ntal growth techniques. In contrast, systems implementing the standard hypercube network cannot be expanded in practice. However, processor allocation for MHs is a more difficult task due to a slight deviation in their topology from that of the standard hypercube. The paper propo ses two strategies to solve the processor allocation problem for MHs. The proposed strategies are characterised by perfect subcube recogniti on ability and superior performance. Furthermore, two existing process or allocation strategies for standard hypercube networks, namely the b uddy and free-list strategies, are shown to be ineffective for MHs, in the light of their inability to recognise many available subcubes. A comparative analysis that involves the buddy strategy and the new stra tegies is carried out using simulation results.