\section{\label{caching}Implementation and Caching}

Here we discuss an implementation of the distributed memory system
that includes a caching capability. The goal of the design is
to ensure that a large fraction of memory references are satisfied in
the cache memory associated with the processor making the reference.
There are two gains from caching:
\begin{enumerate}

\item
Less demand for high bandwidth between processors and main memory

\item
Lower average latency of memory accesses seen by processors

\end{enumerate}
With caching, many read requests will be answered quickly from
the local cache of a processor. However, multithreaded architecture
of the processor is needed to avoid wasting processor
resources and risking deadlock on attempts to read from undefined
locations. Here we describe the organization of the memory system,
discuss options for implementing deferred read
requests, and give a detailed protocol for a scheme that
appears attractive.

As shown in Figure~\ref{mem-system}, the memory system is
built with a Memory Management Unit (MMU) and fast Cache Memory (C) associated
with each processor. The Memory Network interconnects the
MMUs with Memory Units (MU) that implement memory locations
in disjoint portions of the global address space.
We assume that the network is reliable,
but that messages are subject to arbitrary but finite delays, and
the network does not guarantee preservation of message order.

\begin{figure}[tb]\small\
\begin{center}

\illustrationx{memory-org}{4in}

\end{center}
\caption{\label{mem-system}An implementation of the memory system
  with caching.}
\end{figure}

An important implementation question is where and how
a record is kept of pending read requests that must be answered
when a location becomes defined.
Possible approaches to storing this {\em defer queue} include:

\begin{enumerate}

\item
Store all continuations for pending reads of a location
in a continuation queue at the corresponding Memory Unit.

\item
Store the continuation for each pending read only at
the processor originating the request. When the location
becomes defined, the home processor of the location
broadcasts the value to all processors.

\item
Store at the memory unit a list (the {\em waiting set}) of identifiers of
those processor nodes that have one or more pending reads
for a memory location. Each of these processors holds
the set of continuations for read requests it originated.

\item
The MMU associated with the requesting processor tries
repeatedly to access the location
(at gradually less frequent intervals) until the location
becomes defined.

\end{enumerate}
We have chosen (3) as the most promising approach,
and outline the corresponding protocol in detail
below. Each location has a {\em home node}, the
processor/memory module that has the location in its portion of
the main memory address space.


\subsection{Assumptions}

The specification presented below contains several assumptions
for the sake of simplicity. One is that the cache is fully
associative. A benefit is that a new cache line may be stored in any free
slot of the cache memory. For simplicity, we assume that no cache
line that contains a defer queue is ever replaced until after the
entry becomes defined; that is, we assume there is more
than enough cache memory to hold placeholders for all pending
read requests. If a set-associative or direct mapped cache
organization were used, a more sophisticated mechanism
would be needed to avoid blocked reads due to occupancy of
all possible slots by defer queue entries. A feature to help
avoid potential deadlock would be a buffer for unexecutable
read commands at the processor interface with each MMU. Since
write commands are never blocked by program delays,
they should be allowed to bypass read commands held in the buffer.
Discussion of these alternatives is beyond the scope of the present
paper.

Another assumption is that all memory units are
in the same relationship to each and every processor---we are
not modeling a NUMA architecture. In the case of NUMA
architecture it should be possible to respond somewhat quicker to
a remote read request if the location is represented in the
cache of the home processor, but we do not discuss these details
here.


\subsection{Overview of Memory System Operation}

A {\tt READ} command causes the local cache entry to be
examined. If it is {\tt DEFINED}, the value is returned.
If it is a defer queue, the new continuation is
appended. Otherwise, a new cache entry must be created. This
is possibile only if there is a cache slot with state
{\tt EMPTY} or {\tt DEFINED}. If all cache slots are filled
with {\tt QUEUE} entries, processing of the {\tt READ} command
must be postponed. When a slot
containing a {\tt DEFINED} entry is chosen for replacement, the
existing entry may simply be deleted because there will be
a duplicate at its home memory unit. When a new cache entry is
created for a {\tt READ} request, a
read message is also forwarded to the home memory unit for the specified
address. If the location is {\tt DEFINED} at the home MU, a reply
message is generated. Otherwise the identifier of the requesting processor
is added to the waiting set of the location,

In the case of a {\tt WRITE} command, the local cache line is examined
and the queue of continuations is replaced by the value.
If there is no matching cache line, one is created if a slot
can be made free. In any case, a write message is sent to the home memory unit.
The value is also passed to activate any continuations held
by the local MMU. At the home memory unit, the entry for the
location of interest is changed to {\tt DEFINED} and each processor
in the set of waiting processors for the addressed
location is sent a reply message notifying it of the written value.


\subsection{Formal Model}

In this section we use the Haskell language
to give a specification of the implementation of our memory model.
We use Haskell lists to represent sets of various objects. In doing
this we, of course, do not wish to imply that a hardware
implementation would utilize list operations!

The specification consists of functions that specify the actions
performed by the Memory Managemnent Units (MMUs) and the Memory Units
(MUs). The states of an MMU and of an MU are modelled by elements of
the data types {\tt Cache} and {\tt MemMap}, respectively. For an MMU
the specification is a pair of functions: one that specifies its
action in reponse to commands presented by the associated processor.
The {\tt ProcessCommand} function acts on {\tt READ} and {\tt WRITE}
commands to produce an updated state of the local cache, a set
(possibly empty) containing at most one message directed to the home
MU of the addressed location, and a set of responses to completed {\tt
READ} commands.
\begin{verbatim}
  ProcessCommand :: Request -> Cache ->
          ([Response], [Message], Cache)
\end{verbatim}
The {\tt ProcessMessage} function specifies the MMU's action in
response to {\tt REPLY} messages from the MUs.
\begin{verbatim}
  ProcessMessage :: Message -> Cache ->
          ([Response], [Message], Cache)
\end{verbatim}
The MUs are specified by a function that describes the action
performed in response to messages received from the MMUs.
\begin{verbatim}
  ExecuteCommand :: Message -> MemMap ->
          ([Message], MemMap)
\end{verbatim}

These functions may be viewed as an operational semantics for the
memory system as follows: The overall state of the memory system
consists of the states of all MMUs (elements of {\tt Cache}), the
states of the MUs (elements of {\tt MemMap}), the set of messages in
transit through the memory network, and, for each processor, the set
of commands presented but not yet acted upon, and the set of responses
generated by the MMUs but not yet acted upon by the processors. The
overall state is advanced by selecting arbitrarily a message or command
and using the appropriate semantic function to determine
the new overall system state.

The states of the MMUs and MUs are modelled as follows:

{\em State of the Memory Units:} This is simply the memory map
function that maps locations to entries.

\begin{verbatim}
  data MemMap = Location -> Entry

  data Entry = (UNDEF) | (DEFINED Value) | (QUEUE Set)

  data Set = [Node]
\end{verbatim}

An element of the data type {\tt Set} is a set containing identifiers
of the processors in the waiting set for the location.
This set would most likely be implemented as a fixed-length
bit vector, as in simple directory protocols of cache coherence schemes.


{\em State of the Memory Management Units:} Each cache
entry contains an address key and the contents of the line
that includes a state tag and either a value or the defer queue. 

\begin{verbatim}
  data CacheState = [CacheLine]

  data CacheLine =
    (EMPTY) |
    (DEFINED Address Value) |
    (QUEUE Address Defer)

  data Defer = [Continuation]
\end{verbatim}
As memtioned earlier, the {\tt Continuation} type contains a
data frame pointer and an instruction address.
The defer queue would probably be implemented as a list structure.
A single-element queue would be held in the cache slot; otherwise
the slot would contain a pointer to an overflow area in separate
memory within the MMU.

The formats of commands and responses, and of the messages
passed in the Memory Network are as follows:

{\em Commands and Reponses:} The two command types
presented to the MMUs by processors, and
one type of response have been specified in Section~\ref{memory}.

{\em Messages held in the Memory Network:} There are two
command types sent from the MMUs to the MUs and a
single reply message type.
\begin{verbatim}
  data Message = (MESSAGE Node Content)
  data Content =
    (READ Location Node)   |
    (WRITE Value Location) |
    (REPLY Address Value)
\end{verbatim}
In these messages {\tt Location} is the set of local
addresses for any MU, and {\tt Node} is the set of processor
identifiers.


\subsection{The Memory Management Unit}

The actions performed by the MMUs in response to {\tt READ}
and {\tt WRITE} commands are specified by the 
{\tt ProcessCommand} function given in Figures~\ref{mmu-read}
and~\ref{mmu-write}. An MMU's processing of reply messages from
MUs is specified by the {\tt ProcessMessage} function given in
Figure~\ref{mmu-reply}. In these routines, special functions
are used to invoke operations on the cache memory
\begin{itemize}

\item
{\tt CacheHit cache address}: Return {\tt True} if the
cache contains an entry for address {\tt address}.

\item
{\tt CacheAvailable cache}: Return {\tt True} if the
cache contains any entry in state {\tt UNDEFINED} or
{\tt DEFINED}.

\item
{\tt CacheFetch cache address}: The line held by the
cache for address {\tt address} is returned. If no
entry exists, an error occurs.

\item
{\tt CacheUpdate cache address line}: If the cache
contains a line for {\tt address}, it is replaced with
the given line. Otherwise an error occurs.

\item
{\tt CacheReplace cache address line}: If the cache
contains a line for {\tt address}, it is replaced with
the given line. Otherwise, the line replaces any one
line that is {\tt UNDEFINED}. If there is no such
cache line, a line that is {\tt DEFINED} is replaced.
If none exist, an error occurs.

\end{itemize}

Three functions are used to disect global addresses into
node identifiers and locations, and to construct global
addresses from their components:

\begin{itemize}

\item
\begin{verbatim}
  AddressNode :: Address -> Node
\end{verbatim}

\item
\begin{verbatim}
  AddressLocation :: Address -> Location
\end{verbatim}

\item
\begin{verbatim}
  MakeAddress :: Node -> Location -> Address
\end{verbatim}

\end{itemize}


\begin{figure}[tb]\small
\begin{verbatim}

  ProcessCommand (READ address continuation) cache =

    if not (CacheHit cache address) then               --- cache miss

      if (CacheAvailable cache) then let
          list = [continuation]                        --- make new
          line' = (QUEUE list')                        --- cache
          cache' = CacheReplace cache address line'    --- entry

          node = AddressNode address                   --- forward
          location = AddressLocation address           --- read
          content = (READ location MyNode)             --- request
          msg = (MESSAGE node content)                 --- to the MU
        in ([],[msg], cache')

      else Error "no space for read request"

    else let                                           --- cache hit

        line = CacheFetch cache address
      in case line of
        (DEFINED value) -> let
            response = (RESPONSE value continuation)   --- return
          in ([response],[],cache)                     --- value

        (QUEUE list) -> let
            list' = [continuation:list]                --- append
            line' = (QUEUE list')                      --- continuation
            cache' = CacheUpdate cache address line'   --- to the queue
          in ([],[],cache')
\end{verbatim}
\caption{\label{mmu-read}Actions by an MMU for a {\tt READ} command.}
\end{figure}


\begin{figure}[tb]\small
\begin{verbatim}
  ProcessCommand (WRITE address value) cache =

    if not (CacheHit cache address) then               --- cache miss

      if (CacheAvailable address) then let
          line' = (DEFINED value)                      --- make new
          cache' = CacheReplace cache address line'    --- entry

          node = AddressNode address                   --- forward
          location = AddressLocation address           --- write
          content = (WRITE location MyNode value)      --- request
          msg = (MESSAGE node content)                 --- to the MU
        in ([],[msg], cache')

      else let
          node = AddressNode address                   --- forward
          location = AddressLocation address           --- write
          content = (WRITE location MyNode value)      --- request
          msg = (MESSAGE node content)                 --- to the MU
        in ([],[msg], cache')          

    else let                                           --- cache hit

        line = CacheFetch cache address
      in case line of
        (DEFINED value) -> Error "multiple write"

        (QUEUE queue) -> let
            responses = MakeResponses queue value      --- respond to
            line' = (DEFINED value)                    --- deferred
            cache' = CacheUpdate cache address line'   --- reads
          in (responses, [], cache')
\end{verbatim}
\caption{\label{mmu-write}Actions by an MMU for a {\tt WRITE} command.}
\end{figure}

\begin{figure}[tb]\small
\begin{verbatim}
  ProcessMessage (REPLY address value) cache =
    if (CacheHit cache address) then let
        line = CacheFetch cache address
      in case line of
        (DEFINED _) -> Error "address already defined"

        (QUEUE list) -> let
            responses = MakeResponses list value       --- update
            line' = (DEFINED value)                    --- cache and
            cache' = CacheUpdate cache address line'   --- respond
          in (responses, [], cache')

    else Error "no pending reads"
\end{verbatim}
\caption{\label{mmu-reply}Actions by an MMU for a {\tt REPLY} message.}
\end{figure}


\subsection{The Memory Unit}

The Memory Unit reponds to write commands by storing the
given value and sending {\tt REPLY} messages to each
node, if any, in the waiting set. For read commands, a
{\tt REPLY} message is sent if the location is {\tt DEFINED}; otherwise,
the number of the originating node is added to the waiting set.
These actions are specified by the function
{\tt ExecuteCommand} defined in Figures~\ref{mu-read}
and~\ref{mu-write}.
\begin{figure}[tb]\small
\begin{verbatim}
  ExecuteCommand (READ location node) map = let
      entry = map location
    in case entry of
      (UNDEF) -> let
          set' = [node]
          entry' = (QUEUE set')
          map' = MapUpdate map location entry'
        in ([], map')

      (DEFINED value) -> let
          address = MakeAddress MyNode location
          content = (REPLY address value)
          msg = (MESSAGE node content)
        in ([msg], map)

      (QUEUE set) -> let
          set' = SetUnion set [node]
          entry' = (QUEUE set')
          map' = MapUpdate map location entry'
        in ([], map')
\end{verbatim}
\caption{\label{mu-read}Actions by an MU for a {\tt READ} message.}
\end{figure}
\begin{figure}[tb]\small
\begin{verbatim}
  ExecuteCommand (WRITE location value) map = let
      entry = map location
    in case entry of
      (UNDEF) -> let
          entry' = (DEFINED value)
          map' = MemUpdate map location value
        in ([], map')

      (DEFINED value) -> Error "multiple write"

      (QUEUE set) -> let
          address = MakeAddress MyNode location
          msgs = MakeReplies set address value
          entry' = (DEFINED value)
          map' = MemUpdate map location entry'
        in (msgs, map')

  MakeReplies :: Set -> Address -> Value -> [Message]

  MakeReplies set address value =
    case set of
      [] -> []
      [node:set'] -> let
          content = (REPLY address value)
          msg = (MESSAGE node content)
        in [msg:(MakeReplies set' address value)
\end{verbatim}
\caption{\label{mu-write}Actions by an MU for a {\tt WRITE} message.}
\end{figure}
The {\tt MakeReplies} function returns a set (list) of reply
messages, one for each node in the waiting processor set.
