Binary Search in a Multiprocessing Environment
Baer, Hung-Chang Du, Lander · IEEE Transactions on Computers · 1983
In this paper we consider variations on the binary search algorithm when placed in the context of a multiprocessing environment. Several organizations are investigated covering the spectrum from total independence (or free competition for access to common resources) to cooperation as in SIMD architectures. It is assumed that the two main sources of overhead are memory interference and interprocessor synchronization. An organization combining interference-free access to memory by implicit synchronization and a small degree of cooperation yields the best results.
Cited by 9 works. doi:10.1109/tc.1983.1676298
Authors
References
- Algorithms and Complexity: New Directions and Recent Results
- A dichromatic framework for balanced trees
- Analysis of Memory Interference in Multiprocessors
- Interference in multiprocessor computer systems with interleaved memory
- The Design of Special-Purpose VLSI Chips
- An analysis of the instruction execution rate in certain computer structures
- Batched searching of sequential and tree structured files
- Interleaved Memory Bandwidth in a Model of a Multiprocessor Computer System
- Optimal searching algorithms for parallel-pipelined computers
- The Intel®8087 numeric data processor