IEEE Transactions on Computers · 1991 · 63 citations · 9 references
ComputingComputer EngineeringComputer ScienceOptimizationParallel AlgorithmsParallel ComputingCombinatorial OptimizationHypercube NetworksPerformance OptimizationScalable Algorithm DesignAllocationCoalescingDecision ProblemsHypercube TopologyParallel Algorithms On HypercubesPartitioning AlgorithmsPartitioning Strategies
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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
9
A Microprocessor-based Hypercube Supercomputer
John P. Hayes, Trevor Mudge, Quentin F. Stout et al. · IEEE Micro · 1986 · 155 citations