Parallel algorithms for hypercube allocation
Yeimkuan Chang, Laxmi Narayan Bhuyan · International Parallel Processing Symposium · 2002
Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.>
Cited by 4 works. doi:10.1109/ipps.1993.262864
Authors
References
- The Art of Computer Programming
- The Art of Computer Programming
- Generalized Hypercube and Hyperbus Structures for a Computer Network
- Processor Allocation in an N-Cube Multiprocessor Using Gray Codes
- The Performance of Multicomputer Interconnection Networks
- Concurrent processing: A new direction in scientific computing
- A top-down processor allocation scheme for hypercube computers
- Subcube allocation in hypercube computers
- A new strategy for processors allocation in an N-cube multiprocessor
- A novel approach for subcube allocation in hypercube multiprocessors