Subcube allocation in hypercube computers
Shantanu Dutt, John P. Hayes · IEEE Transactions on Computers · 1991
A precise characterization of the subcube allocation problem and a general methodology to solve it are presented. Subcube allocation and coalescing algorithms that have the goal of minimizing fragmentation are developed. The concept of a maximal set of subcubes (MSS), which is useful in making allocations that result in a tightly packed hypercube, is introduced. The problems of allocating subcubes and of forming an MSS are formulated as decision problems and shown to be NP-hard. It is proved analytically that the buddy strategy is optimal under restricted conditions, and it is shown using simulation that its performance is actually poor under more realistic conditions. A heuristic procedure for efficiently coalescing a released cube with the existing free cubes is suggested. This coalescing approach is coupled with a simple best-fit allocation scheme to form the basis of a class of MSS-based strategies that give a substantial performance (hit ratio) improvement over the buddy strategy. Simulation results comparing several different allocation and coalescing strategies, which show that the MSS-based schemes provide a marked performance improvement over previous techniques, are presented.>
Cited by 68 works. doi:10.1109/12.76413
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Art of Computer Programming
- The art of computer programming. Vol.1: Fundamental algorithms
- Logic Design of Digital Systems
- A Microprocessor-based Hypercube Supercomputer
- Processor Allocation in an N-Cube Multiprocessor Using Gray Codes
- Data communication in hypercubes
- A survey of the theory of hypercube graphs
- Logic design of digital systems
- McBOOLE: A New Procedure for Exact Logic Minimization