Browse Prior Art Database

MP Consistency Using Clocks

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+4]

Abstract

The ability to use clocks for individual processor that relate accesses of one processor to accesses on another processor provide the basis for MP consistency and a degree of freedom in choosing which one of several stores to use in honoring a fetch request.

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

MP Consistency Using Clocks

       The ability to use clocks for individual processor that
relate accesses of one processor to accesses on another processor
provide the basis for MP consistency and a degree of freedom in
choosing which one of several stores to use in honoring a fetch
request.

      The consistency requirements in a conventional multiprocessing
system are very peculiar and are different from consistency criteria
in transaction processing systems. They can be summarized by defining
the following PRECEDENCE and FLOW relations.

      Consider the trace of execution of a program on a
multi-processor system.  Here we ignore non-memory access operations
in the trace and consider only the trace of memory accesses.  Thus,
for each processor, A, B, ... we have the sequence of memory accesses
as
A1, A2, A3, ... B1, B2, B3, ...
where each Ai is a FETCH(x) or STORE(x) operation on some memory
address x.

      Define the precedence relation for any two consecutive
operations on the same processor (e.g., Ai -p-> Aj, i < j ), except
when the former (i.e., Ai) is a store operation and the latter (i.e.,
Aj) is a fetch operation.

      Define the flow relation on the same processor as follows. Ai
-f-> Ak, where Ai is a store into some address x, Ai+1 is fetch from
the same address x and for all i<j<k Aj is not a store into x.
Thus, if no other processor stores into x, then Ak must see the value
stored by Ai.

      Define the communication flow relation across processors as
follows.  Ai -c-> Bj when Ai is store operation into some address x
by processor A and Bj is a fetch operation from the same address x by
some other processor B and Bj sees the same data value stored by Ai.
Thus, the two processors communicated via a common memory location.

      It is important to note that while the relations -p-> and -f->
are static properties derived from the program, the relation -c-> is
dynamic and is determined by the relative speeds of the processors
(except for the degenerate case in which the location x is stored
into only once).

      Each processor individually obeys {-f->,-p->} and generates a
sequence of accesses to the memory hierarchy. The access number of
the instructions on each processor is assigned sequentially and is
the clock of that processor. The access number is consistent with
{-f->,-p->} and replaces the relationship.  Thus, within each
processor access requests are ordered by -a->.  The variability of
processor organization can be viewed as the manner in which
{-f->,-p->} give rise to different -a-> that are compatible.

      MP consistency can be stated in terms of cycles that can be
formed between instructions that are related by -a->, by -c->, and an
Existing Communication Relationship (ECR) that was established by a
prior -c->.  A -c-> relationship exists between a FETCH on one
processor and a STORE on another processor if they access the same
memory location. The -c-> relatio...