Dynamic processor allocation in hypercube computers

摘要

Fully recognizing various subcubes in a hypercube computer efficiently is nontrivial due to the specific structure of the hypercube. We propose a method with much less complexity than the multiple-GC strategy in generating the search space, while achieving complete subcube recognition. This method is referred to as a dynamic processor allocation scheme because the search space generated is dependent upon the dimension of the requested subcube dynamically, rather than being predetermined and fixed. The basic idea of this strategy lies in collapsing the binary tree representations of a hypercube successively so that the nodes which form a subcube but are distant would be brought close to each other for recognition. The strategy can be implemented efficiently by using shuffle operations on the leaf node addresses of binary tree representations. Extensive simulation runs are carried out to collect experimental performance measures of interest of different allocation strategies. Itis shown from analytic and experimental results that this strategy compares favorably in many situations to any other known allocation scheme capable of achieving complete subcube recognition.