1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97) A Fast Algorithm for Complete Subcube Recognition Taipei, Taiwan December 18-December 20 ISBN: 0-8186-8259-0
The complete subcube recognition problem is defined as, given a collection of available processors on an n-dimensional hypercube, locate a subcube of dimension k that consists entirely of available processors, if one exists. Despite many algorithms proposed so far on this subject, improving the time complexity of this problem remains a challenge. Efficiency limits that can be reached have not been exhausted yet. This paper proposes a novel algorithm to recognize all the overlapping subcubes available on an n-dimensional hypercube whose processors are partially allocated. Given P=2^n, as the total number of processors in the hypercube, the new algorithm runs in O(3^n), or O(P^(log 3) log P) time which is an improvement over previously proposed strategies, such as multiple-graycode, missing combination, maximal set of subcubes, and tree collapsing.
Index Terms:
processor allocation, hypercube topology, complete subcube recognition, parallel algorithms, order of complexity.
Citation:
Hal Burch, Fikret Ercal, "A Fast Algorithm for Complete Subcube Recognition," ispan, pp.85, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||