loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Hal Burch, Carnegie Mellon University
Fikret Ercal, University of Missouri-Rolla
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.