Subcube recognition, allocation/deallocation and relocation in hypercubes
Mee Yee Chan, Shiang-Jen Lee · 2002
The paper investigates four different strategies for subcube recognition, allocation/deallocation and relocation in an n-dimensional hypercube multiprocessor: the buddy strategy which recognizes 2/sup n-k/ k-cubes in O(N) time, N=2/sup n/, has a relocation cost of O(KlogK) process-moves where K=2/sup k/ is the size of subcube requested; the Gray code strategy which recognizes 2/sup n-k+1/ k-cubes in O(N) time is shown to have a relocation cost of O(N) process-moves; the recognizing all strategy can recognize all C/sub k//sup n/2/sup n-k/ k-cubes in O(N/sup 1.58/) time with a relocation cost of O(N) process-moves; and the extended buddy strategy which recognizes 2/sup n-k/+(n-k)2/sup n-k-1/ k-cubes in O(NlogN) time is shown to have a relocation cost of O(KlogK) process-moves.>