PROCESSOR ALLOCATION FOR HYPERCUBES

This paper presents an efficient subcube recognition policy for hypercube computers. The policy, which can be executed on both serial and parallel computers, is based on exploiting more subcubes at different levels of the buddy tree. In searching the different levels of the tree, the proposed algorithm checks any subcube at most once. Many unavailable subcubes are not considered as candidates and hence not checked for availability. The number of recognized subcubes, for different subcube sizes, can be adjusted by restricting the search depth down the buddy tree. When only one level is searched, this algorithm performs as the original buddy system. When two levels are searched, it recognizes the same subcubes as the ones in Al-Dhelaan and Bose (Proc. International Phoenix Conference on Computers and Communication. Mar. 1989, pp. 114-118) with a faster speed. When all the levels are searched, a complete subcube recognition is obtained. In a multiprocessing environment, the buddy trees with arbitrary search depths can be distributed among different processors. Each processor can execute the extended buddy tree algorithm on its own tree. The goal is to have different recognized subcubes at each processor to maximize the total number of recognized subcubes. Given a number of processors we introduce the DTM scheme for constructing a set of trees that maximizes the number of recognized subcubes. © 1992.