Marilynn Livingston
Dept. of Computer Science, Southern Illinois University at Edwardsville
Quentin F. Stout
EECS Department, University of Michigan
Abstract: Given a type of resource such as disk units, extra memory modules, connections to the host processor, or software modules, we consider the problem of distributing the resource units to processors so that certain performance requirements are met at minimal cost. Typical requirements include insisting that every processor is within a given distance of a resource unit, that every processor is within a given distance of each of several resources, and that every m-dimensional subcube contains a resource unit. The latter is particularly important in a multiuser system in which different users are given their own subcubes.
We also consider the problem of meeting the performance requirements at minimal cost when the subcube allocation system cannot allocate all possible subcubes and the requirements apply only to allocable subcubes. Efficient constructive techniques for distributing a resource are given for several performance requirements, along with upper and lower bounds on the total number of resource units required. These techniques borrow from graph theoretic results concerning domination, and exploit various recursive properties of the hypercube.
Keywords: hypercube computer, parallel computing, subcube fault-tolerance, perfect codes, domination, buddy allocation, resource placement, subcube allocation, parallel architecture
Complete paper: postscript pdf This paper appears in Proceedings 3rd Conference on Hypercube Concurrent Computers and Applications (1988), ACM, pp. 222-231.
Related work:
|
Copyright © 2006-2018 Quentin F. Stout. |