Binary Search in a Multiprocessing Environment

1 July 1983

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-32 (7) , 667-677
https://doi.org/10.1109/tc.1983.1676298

Abstract

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.

Keywords

This publication has 8 references indexed in Scilit:

The Intel®8087 numeric data processor
Published by Association for Computing Machinery (ACM) ,1980
The Design of Special-Purpose VLSI Chips
Computer, 1980
Interleaved Memory Bandwidth in a Model of a Multiprocessor Computer System
IEEE Transactions on Computers, 1979
A dichromatic framework for balanced trees
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1978
Batched searching of sequential and tree structured files
ACM Transactions on Database Systems, 1976
Interference in multiprocessor computer systems with interleaved memory
Communications of the ACM, 1976
Analysis of Memory Interference in Multiprocessors
IEEE Transactions on Computers, 1975
Optimal searching algorithms for parallel-pipelined computers
Published by Springer Nature ,1975