Browse Prior Art Database

Improved Compare And Swap Instruction using Change Bits for Computer Systems with Broadcast

IP.com Disclosure Number: IPCOM000107546D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 3 page(s) / 146K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+3]

Abstract

Compare and Swap is a Read/Modify/Write instruction that is used for synchronizing processors (1). When used to coordinate queue pointers and for other similar functions, a single-operand version of the instruction is subject to a major failure mode. Consequently, practical implementations use a double-operand version of the instruction. Although the double-operand version still has the same failure mode, the probability of failure is so slight that it can be considered to be 0. However, the double-operand version adds to the cost of use of the instruction, as well as to the implementation of the instruction.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Improved Compare And Swap Instruction using Change Bits for Computer Systems with Broadcast

       Compare and Swap is a Read/Modify/Write instruction that
is used for synchronizing processors (1).   When used to coordinate
queue pointers and for other similar functions, a single-operand
version of the instruction is subject to a major failure mode.
Consequently, practical implementations use a double-operand version
of the instruction.  Although the double-operand version still has
the same failure  mode, the probability of failure is so slight that
it can be considered to be 0.  However, the double-operand version
adds to the cost of use of the instruction, as well as to the
implementation of the instruction.

      We describe a means for implementing Compare and Swap correctly
and a slightly lower cost than current "almost correct"
implementations of Compare and Swap.  The new idea is suitable for
systems that use broadcast or other cache-coherence protocol to
assure consistency across several processors.  When this protocol is
present, the additional cost of the implementation of Compare and
Swap is essentially negligible.
Compare and Swap

      Compare and Swap updates a shared variable by computing an
update, then rechecking the shared variable before doing the update
in order to be sure that the shared variable has not changed in the
interim.

      The failure mode of Compare and Swap occurs when a shared
variable is modified a number of times between observations, and the
modifications happen to leave the final state equal to initial state.
The observer cannot distinguish between an unmodified shared variable
and multiple modifications of the shared variable. For the
correctness of Compare and Swap, the shared variable must be
unmodified.  If it has had multiple modifications, the Compare and
Swap could produce inconsistent results.

      The failure mode is eliminated in practice by operating on a
double-operand.  The second operand is a counter that is incremented
each time Compare and Swap is executed.   A Compare and Swap can
update erroneously  only if both the original shared variable and the
counter are the same as their original values obtained when the
update process began.  Since a counter may take many hours to
increment to bring it to its original state, it is extremely unlikely
to find both the counter and the shared variable unchanged when they
have indeed changed.
A Correct Compare and Swap

      The implementation described here works in conjunction with
standard cache-coherence algorithms.  When a shared variable is
fetched at the beginning of an update, it is copied into the cache of
the processor (and a copy is maintained in global memory or the
memory image).  Standard cache-coherence protocols, such as described
by (2), provide a means for invalidating the cache entry if in the
interim any other processor has written to the shared  variable.
Consequently, the Compare...