%You may experience problems if you try to print this file using "lpr"
%command. However, you can print use "enscript -Pp-eeb219 filename" command.

%template for producing IEEE-format articles using LaTeX.
%use at your own risk. 
%make two column with no page numbering, default is 10 point
\documentstyle[twocolumn,epsf]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.75in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.15in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother
\begin{document}
%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf An Incessantly Coherent Cache Scheme for Shared Memory
Multithreaded Systems \thanks{The authors are from Supercomputer Education and
Research Centre, Indian Institute of Science, Bangalore, India. This report describes
research done by the authors at the Laboratory for Computer Science, Massachusetts
Institute of Technology. Funding for the Laboratory is provided in part by the Advanced 
Research Projects Agency of the Department of Defense under the Office of Naval Research contract 
N00014-92-J-1310. Financial support for the first author was provided by Indo-U.S.
Science and Technology Fellowship Program.}}

%for single author (just remove % characters)
\author{S. K. Nandy and Ranjani Narayan \\
  Laboratory for Computer Science\\
  Massachusetts Institute of Technology \\
  Cambridge, Massachusetts, MA 02139\\
  e-mail: nandy@theory.lcs.mit.edu}
 
%for two authors (this is what is printed)
%\author{\begin{tabular}[t]{c@{\extracolsep{5em}}c}
% S. K. Nandy & Ranjani Narayan \\
% \\
%Department of AA & Department of BB \\
%University of CC & University of DD \\
%City, CA 00000-0000	& City, CA 00000-0000 \\
%email-for-author1           & email-for-author2
%\end{tabular}}

\maketitle

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
%IEEE allows italicized abstract
{\em An incessantly coherent cache consistency protocol is proposed in this paper.
The protocol supports limitless sharing and obviates the need to invalidate
shared cache lines by automatically self invalidating cache lines after the expiry of
its {\em lifetime}. The protocol mandates that all writes be performed at the
home locations only. The worst case performance of  this protocol bears the potential
to perform as good as any other directory based protocol. It relieves the network  of
the additional traffic due to invalidations that are in vogue in any of the
existing directory based cache coherence protocols.}
\input{illustrations}
\def\illustrationfileprefix{/abp/nandy/letters/}
\section{Introduction}
Supporting global shared references in  massively parallel architectures
is a major concern. The cost of accessing remote shared memory locations has
a direct impact on the performance of an application on such architectures.
Caching global shared memory reduces the overall latency of global references.
The choice of a shared memory cache coherence protocol is to a large extent 
determined by the messaging protocol and the processor-memory
bus bandwidth which in turn determines the performance of the architecture.

Alewife\cite{anant3} supports shared memory by integrating message passing
and a directory based cache coherence protocol called the LimitLESS
scheme\cite{anant4}. The DASH\cite{dash1} shared memory multiprocessor also 
implements a directory based cache coherence scheme which is an 
invalidation-based ownership protocol. The model of consistency provided in 
DASH is called {\em release consistency}\cite{dash2} and is an extension of
the weak consistency model proposed in\cite{dash3}. The Stanford FLASH
Multiprocessor\cite{flash} is yet another multiprocessor that supports cache 
coherent shared memory using a directory based cache protocol. The protocol 
is based on two components, {\em viz.} a scalable directory data structure 
and a set of handlers.

However, in all the three cited multiprocessor architectures the cost of sending
cache invalidation messages cannot be ignored. We conjecture that a significant
gain in multiprocessor performance can be achieved by totally avoiding
invalidations. We propose such a scheme in this paper. The 
{\em Incessantly Coherent} cache coherence scheme presented here maintains 
incessantly coherent shared memory by automatically invalidating cache lines 
after a specified period called the {\em lifetime}.  The protocol supports 
limitless sharing and permits writes in home locations only.
The worst case performance of the proposed scheme is guaranteed to be at least as
good as any directory based scheme. Additionally the proposed scheme relieves 
the network traffic due to invalidations which is unavoidable in directory 
based schemes.

The rest of the paper is organised as follows. In section 2, we describe the
incessantly coherent cache coherence protocol. This is followed by section 3
that elaborates on the proposed scheme using an walk-through example.
We comment on the performance of the proposed scheme in section 4, and finally
in section 5 conclude with a summary of the contributions.

\section{Incessantly Coherent: A Cache Coherence Protocol}
We propose a cache coherence scheme for a system comprising
multiple processor sites in a network. A site is a set of tightly coupled
processors.  Each processor in this system supports a multi-level
cache and executes multi-threaded code. The programming model assumes a single global
address space. Every global address has an owner site called {\bf home}
Global shared memory support for the system is realized as shared memory 
modules physically distributed amongst the sites. Each site has a shared memory
unit(SMU) and a controller to handle shared references. An example architecture of this 
model is *T-NG~\cite{arvind}.  Other distributed memory multicomputer systems 
are also based on a similar model. Figures~\ref{mymac} and {}~\ref{Cluster}  
give the conceptual model of such a system.

Directory based cache coherence protocols {}~\cite{anant1} and its variants
must invalidate all shared cache lines before a cache line  is written. 
The cost of invalidates in a relatively low bandwidth interconnection network 
can far offset the performance gains obtained by exploiting parallelism. 
Invalidations add to the network traffic that lead to network congestion.
On the other hand, if only a site is allowed to own a cache line then for 
programs that exhibit spatial locality, traffic on the interconnection network
will increase enormously since single ownership of cache lines will lead to 
repeated invalidations followed by {\em wandering} of cache lines. 

We propose an {\em Incessantly Coherent Cache Scheme} that supports limitless 
sharing, alleviates wandering and eliminates invalidations.  All READs are 
performed at the granularity of a cache line. WRITES are permitted at the home
location only.  The problem of wandering is alleviated by enforcing
a finite period of validity time $t_c$ (called lifetime) for each cache line. 
A cache line is automatically invalidated after its lifetime. Limitless sharing
is supported by honoring multiple READ requests simultaneously. Note that the 
cache line could be ``live'' in multiple sites. 

\begin{figure}
\illustrationx{mymac1}{3.2in}
%\begin{center}
%\input{mymac.fig.tex}
\caption{System Model}
\label{mymac}
%\end{center}
\end{figure}
\begin{figure}
\illustrationxy{Cluster2a}{3.3in}{5.5in}
%\begin{center}
%\input{Cluster.fig.tex}
\caption{Details of a Site}
\label{Cluster}
%\end{center}
\end{figure}

A WRITE operation on a cache location is honoured when the lifetime of 
the latest READ has expired.  Multiple WRITES to the same cache line must 
therefore be queued.  It is important to note that a WRITE operation 
is delayed only if it arrives within $t_c$ of the last READ operation.

In systems that implement global memory cache at a lower level in the overall
cache hierarchy, it is possible that cache coherence in higher level caches 
(in processors within a site) is maintained using an entirely different protocol.
It is therefore necessary that on the expiry of lifetime of cache lines in the global 
cache, copies of this cache line in all higher level caches be invalidated.
In such cases, SMU sends appropriate invalidate messages on the site's 
processor-memory interconnection network.

\subsection{Limitless sharing, No wandering, No invalidations}
Read requests for locations
of a particular cache line originating from different sites may result in 
the cache line to ``{\em wander}'' from one site to another.

This problem is alleviated by enforcing
a lifetime for a cache line. A cache line is ``{\em live}'' within a site
for $t_c$, a finite period of time called its lifetime. 
($t_c$ starts immediately after the cache line is loaded.)
A cache line is automatically invalidated after its lifetime.
Multiple READ requests to locations within
the cache line are honoured by sending the entire cache line. In this case, 
note that the cache line could be ``{\em live}'' in multiple sites. 

A WRITE operation on a cache location is honoured when the lifetime of 
the latest READ has expired.  Multiple WRITES to the same cache line must 
therefore be queued.
It is important to note that a WRITE operation 
is delayed only if it arrives within $t_c$ of the last READ operation.

\section{An Example}
Consider the following instruction sequence in a program segment.
\begin{quote}
\tt
global shared variable a\\
.....\\
Instruction $ \ \ $i>    A := A + B\\
Instruction i+1>  P := A + 5\\
.....\\
\end{quote}
A multi-threaded code corresponding to the above program segment
will appear as follows. In addition to the shared variables defined
in the program, additional global  and local counters are defined
in the code generated by the compiler for synchronization.
\begin{quote}
\tt
global shared variable: A\\
global shared counter: syncA=1\\
local synchronization counter: C=3\\
local variable: B\\

Thread T1;generated by instruction i
   \begin{quote}
   \tt
   Store A from global memory into frame\\
   Decrement C\\
   If C=0 then start T4\\
   else stop
   \end{quote}
Thread T2;generated by instruction i
    \begin{quote}
    \tt
   Store syncA from global memory into frame\\
   Decrement C\\
    If C=0 then start T4\\
    else stop
    \end{quote}
Thread T3;generated by instruction i
    \begin{quote}
    \tt
    Store B from local memory into frame\\
   Decrement C\\
    If C=0 then start T4\\
    else stop
    \end{quote}
Thread T4;generated by instruction i
    \begin{quote}
    \tt
     Frame fetch syncA\\
     Frame fetch A\\
     Frame fetch B\\
     A := A + B\\
     Decrement syncA\\
     Perform a guarded write of A and syncA in global shared memory\\
     \end{quote}
Thread T5;generated by instruction i+1
      \begin{quote}
      \tt
      Store {\tt syncA} from global memory into frame\\
      If syncA = 0 then start T6\\
      else retry\\
      \end{quote}
Thread T6;generated by instruction i+1
      \begin{quote}
      \tt
      Store A from global memory into frame\\
      Frame fetch A\\
      Add 5\\
      Store into P in frame\\
      \end{quote}
\end{quote}
Let us assume that threads T1, T2, T3 and T4 are scheduled on
processors in site${}_i$ and threads T5 and T6 are scheduled on processors
in site${}_{i+1}$. Further, we assume that {\tt A} and {\tt syncA} are resident in the
global memory module of site${}_{i+1}$. Clearly the order of execution of threads T1, T2
and T3 are of no consequence. Also thread T4 cannot start before
T1, T2, and T3 have completed. This is ensured by maintaining
a local counter C in the frame. Threads T1,T2,T3 and T4 together share the
same frame in site${}_i$. Threads T5 and T6 together share a
frame in site${}_{i+1}$. Thread T5  cannot start before T4 completes.
This is achieved by maintaining a global counter {\tt syncA} that guarantees
that thread dependencies are not violated.


The Incessantly Coherent cache coherence protocol can now be verified for the
above thread executions. To start with we will impose the following
artificial constraints that will be relaxed later.
\begin{enumerate}
\item Sites i and i+1  maintain clocks that are globally synchronised
\item Communication latency on the site  interconnection network is finite and very
      close to zero. 
\end{enumerate}
The following sequence of actions takes place at global caches. 
\begin{enumerate}
\item Thread T1 executing in site${}_i$ encounters a READ miss on {\tt A}.
      The global memory controller sends out a request for a cache line to
      site${}_{i+1}$. 
\item Site${}_{i+1}$ forwards a cache line containing {\tt A} to the
      global memory controller of site${}_i$.
\item Since communication latency is zero, site${}_i$ receives the cache line
      immediately. This cache line is self invalidated after its lifetime $t_c$ in
      site${}_i$.
\item Thread T2 executing in site${}_i$ encounters a READ hit on the global
      memory cache for a reference to {\tt syncA}. (It is assumed that 
      {\tt syncA} and {\tt A} are in  the same cache line because
       of locality of reference.)
\item Thread T3 executing in site${}_i$ results in no global memory operations.
\item Thread T4 executing in site${}_i$ results in a guarded global WRITE operation. 
      Since all writes are made in the home location, the WRITE operation is delayed 
      until the expiry of the lifetime of the cache line(s) containing {\tt syncA} and 
      {\tt A} in site${}_{i+1}$. 
\item Thread T5 executing in site${}_{i+1}$ results in a READ miss on {\tt syncA}. 
      The global memory controller
      of site${}_{i+1}$ fetches the cache line. If {\tt syncA} is not zero,
      the cache line is brought in again after a retry interval. 
      The number of retries depends on the lifetime $t_c$. Each retry is
      a READ miss.
\item Thread T6 executing in site${}_{i+1}$ encounters a READ hit on the global
      memory cache for {\tt A}. This results in no global memory operation.
\end{enumerate}
Clearly, the above sequence of operations are hazard free.
Now we relax the artificial constraints and review the above set of operations under the
following conditions.
\begin{enumerate}
\item Processors site${}_i$ and sites${}_{i+1}$  maintain independent clocks
\item Communication latency on the site  interconnection network is finite but not
      constant over all transactions 
\end{enumerate}

%It is assumed however that the site interconnection network does not change the
%FIFO order of messages between any two processors.
Figure~\ref{order} (a) gives the sequence of global memory references between
site${}_i$ and site${}_{i+1}$ when the communcation latency is zero. Figure~\ref{order}(b)
shows the same set of operations with finite communication latency. 
It is clear from the figures that with non-zero communication latency
the global memory remains consistent throughout its execution since the same set of
transactions are stretched in time.
There is however an increase in overall latency of program execution. 
Thus the Incessantly Coherent protocol guarantees cache coherence throughout the execution of a program.
\section{Performance}
The performance of any caching depends on the model of multi-threaded computation.
In a data driven model of computation, threads of computations can be viewed as
representing nodes in a dataflow graph. In such a model, thread schedules
are not known {\em a priori}. In contrast, in data parallel model of computation
threads are scheduled statically. In the implicit parallel programming model
synchronization of threads is automatically handled by the compiler. Synchronization is
normally emulated with software counters in memory locations.  In a data driven
model synchronization is absolutely necessary to ensure proper execution order 
of instructions. In the Threaded Abstract Machine (TAM) \cite{culler} such 
synchronization threads are called {\em inlets} and are executed in response to
messages. 

The synchronization operation is essentially an atomic
{\em read-modify-write} to a memory location, followed by a branch on the result.
Usually these memory locations are shared. In \cite{arvind} the expected frequency
of such syncronization events is stated to occur once every 50 or so
instructions.  Further it is reasonable to assume that the same synchronization
counter is not accessed more than once by the same thread. 
This behaviour of synchronization threads clearly swings the pendulum in favor of
the Incessantly Coherent protocol since a cache line is always read without the additional
latency to invalidate previously shared copies in other caches.
Further since the syncronization events are compiler generated, the compiler can
additionally specify the lifetime of such cache lines. Clearly such cache lines
will have shorter lifetimes compared to computation threads. In general, the
compiler can choose to specify different lifetimes for different cache lines.
This feature is particularly valuable if prefetches are used to bring global data into the
cache before they are actually used.

Further, based on the reference pattern, a given site can send messages in advance
to the home site to renew its lifetime. The lifetimes
of cache lines can thus adapt to the reference pattern in multi-threaded program execution.

Based on these observations, it is expected that on the overall, the average latency 
of accessing global shared memory through cache (using the Incessantly Coherent protocol)
is lower than that compared to any directory based caching scheme. 
Since the lifetime of cache lines is very sensitive to the overall system architecture
and the model of multi-threaded computation, it is a good candidate to experiment on the
*T-NG~\cite{arvind} architecture for which coherence protocols can be implemented in
software.
\section{Conclusions}
In this paper we proposed a new shared memory cache coherence protocol. The salient features
of the protocol being that it supports limitless sharing and relieves the network of any traffic
due to invalidation messages. Since cache lines auto-invalidate themselves on the expiry of their
lifetime, and writes are done only at the home location on the expiry of the lifetime, all caches
are always coherent.
\section*{Acknowledgments}
The authors acknowledge the discussions and suggestions received from
Prof. Arvind and thank Dr. Horace Thompson, Prof. John Morris, Prof. Guang R. Gao, Derek Chiou,
Boon Seong Ang, Xiao Wei, James Hoe,and Any Boughton for their helpful comments for a better
understanding of the issues in global cache coherence. 
\begin{thebibliography}{99}
\bibitem{anant3} John Kubiatowicz and Anant Agarwal, ``Anaotomy of a Message in the
Alewife Multiprocessor'', 7th International Conference on Supercomputing.
\bibitem{anant4} David Chaiken, John Kubiatowicz and Anant Agarwal, ``LimitLESS
Directories: A Scalable Cache Coherence Scheme'', Proceedings of the fourth
International Conference on Architectural Support for Programming Languages and
Operating Systems (ASPLOS IV), pp. 224-234, ACM, APril 1991.
\bibitem{dash1} Daniel Lenoski, James Laudon, Kourosh Gharachorloo, Anoop Gupta and John
Hennessy, ``The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor'',
Proceedings of the 17th International Symposium on Computer Architecture, pp. 148-159, Seattle, WA, May 1990.
\bibitem{dash2}  Kourosh Gharachorloo,  Daniel Lenoski, James Laudon, P. Gibbons,
A. Gupta, and J. Hennessy, ``Memory Consistency and Event ordering in Scalable Shared-Memory
Multiprocessor'', Proceedings of the 17th Annual International Symposium on Computer
Architecture, June 1990.
\bibitem{dash3}M. Dubois, C. Scheurich, and F. Briggs, ''Memory Access buffering in 
Multiprocessors'', Proceedings of the 13th Annual International Symposium on Computer 
Architecture, pp. 434-442, June 1986.
\bibitem{flash} Jeffrey Kuskin, {\em et al} ``The Stanfoed FLASH Multiprocessor'',
Proceedings of the 21st Annual International Symposium on Computer
Architecture, 1994 (to appear).
\bibitem{arvind} Boon Seong Ang, Arvind, and Derek Chiou, ``StarT the Next Generation: 
Integrating Global Caches and Dataflow Architecture'', LCS CSG Memo 354, February 25,
1994.
\bibitem{culler} D. E. Culler, S. C. Goldstein, K. E. Schauser, and T. von Eicken,
``TAM -- A Compiler Controlled Threaded Abstract Machine'', Journal of Parallel and 
Distributed Computing, 18(3):347-370, 1993.
\bibitem{anant1} A. Agarwal, R. Simoni, J. Hennessy, and M. Horowitz, ``An evaluation
of directory schemes for cache coherence'', Proceedings of the 15th  Annual  
International Symposium on Computer Architecture, June 1988, pp. 280--289.
\end{thebibliography}

\newpage
\begin{figure}
\illustrationx{ordera}{4.0in}
%\begin{center}
%\input{mymac.fig.tex}
\caption{Global memory accesses}
\label{order}
%\end{center}
\end{figure}

\end{document}

