SUBCUBE ALLOCATION STRATEGIES IN EXTENDED HYPERCUBE MULTIPROCESSORS

Abstract

The Extended Hypercube (EH) architecture is suited for hierarchical expansion of multiprocessor systems. The basic module of EH consists of a k-cube and an additional node for handling communication - the Network Controller (NC). The NC in effect allows the Processor Element (PE) of each node to concentrate on computation rather than on communication. A particular advantage of EH is that they can support multiusers, each of which can be assigned an independent subcube of nodes by the operating system. In such an environment, espacially one where requests for cubes of various dimensions arrive very frequently, it is of the prime importance to make judicial allocations of subcubes so that the EH does not become badly fragmented. The -main objective of Subcube -allocation problem is to maximize the utilization of the resources as well as minimize the inherent system fragmentation. This is similar to the conventional memory allocation problem. Full recognition- of various subcubes in the basic module i.e., hypercube is nontrivial due to specific structure of the hypercube. In this dissertation.we address two subcube allocation strategies namely buddy strategy and Gray code strategy for the hypercube and develop schemes to adopt them to EH taking into consideration special properties of EH. Simulation programs are then developed to-evaluate the--r-elative performance of this strategies.