Browse Prior Art Database

Fetch-And-Op's by Compare-And-Swap

IP.com Disclosure Number: IPCOM000038565D
Original Publication Date: 1987-Feb-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Darema-Rogers, F: AUTHOR [+5]

Abstract

Whenever there are two or more processes (or CPUs) in a multiprocessor (MP) system simultaneously modifying a memory location, correctness of the computation requires that the modification be done by one process at a time, irregardless of the order the location is updated. This indivisibility must be guaranteed at the hardware level. Fetch-and-OP's (F&OP's) [1], such as fetch-and-add (F&A) and fetch-and-max, have been found both syntactically and architecturally useful constructs in parallel computing of guaranteeing the correctness mentioned above. The following method maps the use of all of the F&OP's in an MP system in which they are not supported, such as a 370 MP system, but where the CS [2] (compare-and-swap) is an indivisible operation used for MP synchronization.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 60% of the total text.

Page 1 of 1

Fetch-And-Op's by Compare-And-Swap

Whenever there are two or more processes (or CPUs) in a multiprocessor (MP) system simultaneously modifying a memory location, correctness of the computation requires that the modification be done by one process at a time, irregardless of the order the location is updated. This indivisibility must be guaranteed at the hardware level. Fetch-and-OP's (F&OP's) [1], such as fetch-and-add (F&A) and fetch-and-max, have been found both syntactically and architecturally useful constructs in parallel computing of guaranteeing the correctness mentioned above. The following method maps the use of all of the F&OP's in an MP system in which they are not supported, such as a 370 MP system, but where the CS [2] (compare-and-swap) is an indivisible operation used for MP synchronization. The scheme presents a minimal mapping from the class of F&OP's to CS. Assume that a F&OP is generally indicated as Y=OP(X,A,..), where X is a global variable shared by all of the CPUs and the rest are simply local variables or are not supposed to be accessed by all of the CPUs at a time. For example, if OP=F&A, then Y=X+A. The local A is added to the shared X, and the result is returned to the local Y. Since it is the indivisibility but not the order of how a shared variable is updated by a set of parallel processes, the idea of implementing a F&OP by a CS is to first make a copy of X to a local X, say, MY_X, perform the F&OP locally to get a new X, say, NEW_X,...