Browse Prior Art Database

Method for Atomically Updating Multiple Non-Contiguous Memory Locations

IP.com Disclosure Number: IPCOM000119858D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 112K

Publishing Venue

IBM

Related People

Bowen, NS: AUTHOR

Abstract

Multiprocessor architectures as well uniprocessors that allow multiprogramming require instructions that can atomically update main memory. These have included well-known instructions such as 1. Test and Set 2. Fetch and Add 3. Increment/Decrement 4. Compare and Swap.

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

Method for Atomically Updating Multiple Non-Contiguous Memory Locations

      Multiprocessor architectures as well uniprocessors that
allow multiprogramming require instructions that can atomically
update main memory.  These have included well-known instructions such
as
1.  Test and Set
2.  Fetch and Add
3.  Increment/Decrement
4.  Compare and Swap.

      All of these instructions require the ability to atomically
read a memory location, update the value, and write the new value
back to memory.  The implementation greatly depends on the cache
coherency policy.  For a write-through cache, reads to the memory
must be blocked during the execution of the instruction.  For a
copy-back cache, these instructions can be implemented by not
allowing a cross invalidate from the time the word is read out of the
line until the time the instruction completes.  The implementation
can either defer cross invalidates for the entire cache or for the
specific line.  One significant problem with this scheme is that the
other processors that are issuing the cross invalidate must wait for
the cross invalidate to be honored.

      These instructions typically work on small units of information
(4 - 8 bytes) that have strong boundary requirements.   There are
many applications which could use a facility to change larger amounts
of contiguous information as well as non-contiguous locations.
Furthermore, the current instructions support the atomic update for a
single instruction.  If the atomic instruction were expanded to
include a greater range (i.e., across multiple instructions) than the
single instruction, the delays suffered for the deferred cross
invalidate could become intolerable.  In addition to the waits that
can effect the cross invalidates, there are potential deadlock
problems if multiple cache lines are required by the atomic
instructions.

      This disclosure describes a new paradigm for performing atomic
updates to memory which allows the data to span an arbitrary space
and time and does not suffer the delays for the cross invalidates.

      The basis for this disclosure is to define a new state for
cache lines in a copy-back cache which is called Abort on Cross
Invalidate (AXI).  We use the classical terms for a copy-back cache:
RO means Read-Only (multiple copies allowed), and RW means Read-Write
(only one copy allowed). An AXI line is considered an exclusive
state, in the sense that there is only one copy in the system, but
has the provision that a cross invalidate for the line results in a
cast of the line with no copy back to main memory (thus the
expression Abort on Cross Invalidate).  Since the cache line may be
cast out once changes have been made, there must be architected
methods for changes to be made to the line.

      The first provision is a technique for beginning the atomic
updat...