Binary Search in a Multiprocessing Environment

Jean Loup Baer, Hung Chang Du, Richard E. Ladner

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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. Copyright

Original languageEnglish (US)
Pages (from-to)667-677
Number of pages11
JournalIEEE Transactions on Computers
Issue number7
StatePublished - Jul 1983


  • Binary search
  • SIMD architectures
  • memory interference
  • multiprocessor systems


Dive into the research topics of 'Binary Search in a Multiprocessing Environment'. Together they form a unique fingerprint.

Cite this