Optimal Bounds for Finding Maximum on Array of Processors with k Global Buses
- 1 January 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (1) , 62-64
- https://doi.org/10.1109/TC.1986.1676658
Abstract
The problem of finding the maximum of a set of values stored one per processor on a two-dimensional array of processors with a time-shared global bus is considered. The algorithm given by Bokhari is shown to be optimal, within a multiplicative constant, for this network and for other d-dimensional arrays. We generalize this model and demonstrate optimal bounds for finding the maximum of a set of values stored in a d-dimensional array with k time-shared global buses.Keywords
This publication has 7 references indexed in Scilit:
- Finding Maximum on an Array Processor with a Global BusIEEE Transactions on Computers, 1984
- Mesh-Connected Computers with BroadcastingIEEE Transactions on Computers, 1983
- A Combinatorial Limit to the Computing Power of VLSI CircuitsIEEE Transactions on Computers, 1983
- Lookahead networksPublished by Association for Computing Machinery (ACM) ,1982
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Speed of Recognition of Context-Free Languages by Array AutomataSIAM Journal on Computing, 1975