Efficient synchronization of multiprocessors with shared memory

Clyde P. Kruskal; Larry Rudolph; Marc Snir

doi:10.1145/48022.48024

Efficient synchronization of multiprocessors with shared memory

Clyde P. Kruskal, Larry Rudolph, Marc Snir

Research output: Contribution to journal › Article › peer-review

Abstract

A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form mem_val := mem_val op val, where op need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.

Original language	English (US)
Pages (from-to)	579-601
Number of pages	23
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Volume	10
Issue number	4
DOIs	https://doi.org/10.1145/48022.48024
State	Published - Oct 1 1988
Externally published	Yes

Keywords

Architecture correctness
fetch-and-add
interconnection network
memory reference combining
parallel prefix
parallel processing
read-modify-write (RMW)

ASJC Scopus subject areas

Software

Online availability

10.1145/48022.48024

Library availability

Discover UIUC Full Text

Cite this

@article{499c64d8ab33484cb7e6d59ac2e5df8b,

title = "Efficient synchronization of multiprocessors with shared memory",

abstract = "A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form mem_val := mem_val op val, where op need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.",

keywords = "Architecture correctness, fetch-and-add, interconnection network, memory reference combining, parallel prefix, parallel processing, read-modify-write (RMW)",

author = "Kruskal, {Clyde P.} and Larry Rudolph and Marc Snir",

year = "1988",

month = oct,

day = "1",

doi = "10.1145/48022.48024",

language = "English (US)",

volume = "10",

pages = "579--601",

journal = "ACM Transactions on Programming Languages and Systems (TOPLAS)",

issn = "0164-0925",

publisher = "Association for Computing Machinery",

number = "4",

}

TY - JOUR

T1 - Efficient synchronization of multiprocessors with shared memory

AU - Kruskal, Clyde P.

AU - Rudolph, Larry

AU - Snir, Marc

PY - 1988/10/1

Y1 - 1988/10/1

N2 - A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form mem_val := mem_val op val, where op need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.

AB - A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form mem_val := mem_val op val, where op need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.

KW - Architecture correctness

KW - fetch-and-add

KW - interconnection network

KW - memory reference combining

KW - parallel prefix

KW - parallel processing

KW - read-modify-write (RMW)

UR - http://www.scopus.com/inward/record.url?scp=0024101778&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024101778&partnerID=8YFLogxK

U2 - 10.1145/48022.48024

DO - 10.1145/48022.48024

M3 - Article

AN - SCOPUS:0024101778

SN - 0164-0925

VL - 10

SP - 579

EP - 601

JO - ACM Transactions on Programming Languages and Systems (TOPLAS)

JF - ACM Transactions on Programming Languages and Systems (TOPLAS)

IS - 4

ER -

Efficient synchronization of multiprocessors with shared memory

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this