''Processor Allocation in Hypercube Multiprocessors''
Suresh Rai
Jerry L. Trahan
Thomas Smailus
IEEE Trans. Par. and Distr. Systems,
vol. 6, no. 6, pp. 606-616, 1995
Abstract:
The processor allocation problem requires recognizing and
locating a free subcube that can accommodate a request for a
subcube of a specified size for an incoming task. Methods reported
in the literature fall into two strategies: bottom-up or
bit mapped technique (BMT) and top-down or
available cube technique (ACT). Our algorithm that solves the
allocation problem in faulty hypercubes falls into the category of
ACTs which offer the advantage over BMTs of quickly recognizing
whether or not a requested subcube is available in the list of
fault-free subcubes. We introduce new algebraic functions and the
concept of separation factor to select a subcube for allocation.
The notion of overlap-syndrome, defined in the text, quantifies the
overlap among free subcubes. Our technique has full subcube recognition
ability and thus recognizes more subcubes as compared to
bit mapped techniques: buddy, Gray code and its variants.
The advantages of our approach over some of the existing ACTs
in terms of fragmentation and overall completion time are
described in the text and in simulation results.