Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors

Allan Gottlieb, Boris D. Lubachevsky

Research output: Contribution to journalArticle

Abstract

In this paper we implement several basic operating system primitives by using a “replace-add” operation, which can supersede the standard “test and set” and which appears to be a universal primitive for efficiently coordinating large numbers of independently acting sequential processors. We also present a hardware implementation of replace-add that permits multiple replace-adds to be processed nearly as efficiently as loads and stores. Moreover, the crucial special case of concurrent replace-adds updating the same variable is handled particularly well: If every processing element simultaneously addresses a replace-add at the same variable, all these requests are satisfied in the time required to process just one request.

Original languageEnglish (US)
Pages (from-to)164-189
Number of pages26
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Volume5
Issue number2
DOIs
StatePublished - Jan 4 1983

Keywords

  • Parallel processing
  • network
  • replace-add
  • synchronization
  • ultracomputer

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors'. Together they form a unique fingerprint.

  • Cite this