
\graphicspath{{./images/}}
\usetikzlibrary{positioning,shapes,shadows,arrows,snakes}

\msection{Ruby Memory System}{Derek Hower}

\begin{frame}
\frametitle{Outline}

   \bi 
   \item Feature Overview
   \item Rich Configuration
   \item Rapid Prototyping
     \bi 
     \item SLICC
     \item Modular \& Detailed Components
     \ei
   \item Lifetime of a Ruby memory request
   \ei
\end{frame}

\begin{frame}
\frametitle{Feature Overview}

  \bi
  \item \textit{Flexible} Memory System
    \bi
    \item Rich configuration - Just run it
      \bi
        \item Simulate combinations of caches, coherence, interconnect, etc...
      \ei
     \pause \item Rapid prototyping - Just create it
      \bi
        \item Domain-Specific Language (SLICC) for coherence protocols        
        \item Modular components
      \ei
    \ei
  \pause \item Detailed statistics
    \bi
      \item e.g., Request size/type distribution, state transition frequencies, etc...
    \ei
  \pause \item Detailed component simulation
    \bi
      \item Network (fixed/flexible pipeline and simple) 
      \item Caches (Pluggable replacement policies)
      \item Memory (DDR2)
    \ei   
  \ei
\end{frame}

\begin{frame}
\frametitle{Rich Configuration - Just run it}
  \bi
  \item Can build many different memory systems
    \bi
    \item CMPs, SMPs, SCMPs
    \item 1/2/3 level caches
    \item Pt2Pt/Torus/Mesh Topologies
    \item MESI/MOESI coherence
    \ei
  \item Each components is individually configurable
    \bi
      \item Build heterogeneous cache architectures (\alert{new})
      \item Adjust cache sizes, bandwidth, link latencies, etc...
    \ei
  \item \textcolor{green}{Get research started without modifying code!}
  \ei
\end{frame}

\begin{frame}
\frametitle{Configuration Examples}

  \be
  \item 8 core CMP, 2-Level, MESI protocol, 32K L1s, 8MB 8-banked L2s, crossbar interconnect
    \bi
    \item \texttt{\tiny \textbf{scons build/ALPHA\_FS/gem5.opt PROTOCOL=MESI\_CMP\_directory RUBY=True}}
    \item \texttt{\tiny \textbf{./build/ALPHA\_FS/gem5.opt configs/example/ruby\_fs.py -n 8 --l1i\_size=32kB --l1d\_size=32kB --l2\_size=8MB --num-l2caches=8 --topology=Crossbar --timing}}
    \ei 
  \item 64 socket SMP, 2-Level on-chip Caches, MOESI protocol, 32K L1s, 8MB L2 per chip, mesh interconnect
    \bi
    \item \texttt{\tiny \textbf{scons build/ALPHA\_FS/gem5.opt PROTOCOL=MOESI\_CMP\_directory RUBY=True}}
    \item \texttt{\tiny \textbf{./build/ALPHA\_FS/m5.opt configs/example/ruby\_fs.py -n 64 --l1i\_size=32kB --l1d\_size=32kB --l2\_size=512MB --num-l2caches=64 --topology=Mesh --timing}}
    \ei
  \ee

  \bi
  \item Many other configuration options
  \item \alert{Protocols only work with specific architectures (see wiki)}
  \ei

\end{frame}

\begin{frame}
\frametitle{Rapid Prototyping - Just create it}
  \bi
  \item Modular construction
    \bi
    \item Coherence controller (SLICC)
    \item Cache (C++)
      \bi
      \item Replacement Policy (C++)
      \ei
    \item DRAM (C++)
    \item Topology (Python)
    \item Network implementation (C++)
    \ei
  \item Debugging support
  \ei
\end{frame}

\begin{frame}
\frametitle{SLICC: Specification Language for Implementing Cache Coherence}

   \bi
   \item Domain-Specific Language
     \bi
     \item Syntatically similar to C/C++
     \item Like HDLs, constrains operations to be hardware-like (e.g., no loops)
     \ei
   \item Two generation targets
     \bi
     \item C++ for simulation
       \bi
       \item Coherence controller object
       \ei
     \item HTML for documentation
       \bi
       \item Table-driven specification (State x Event -> Actions \& next state)
       \ei
     \ei
   \ei  
\end{frame}

\begin{frame}
\frametitle{SLICC Protocol Structure}
                  
  \begin{columns}[c]
  \column{.5\textwidth}
  \begin{center}
    \includegraphics<1>[width=6cm]{sliccnetwork.jpg}
  \end{center}

  \column{.5\textwidth}
    \bi
    \item Collection of \textit{Machines}, e.g.
      \bi
      \item L1 Controller 
      \item L2 Controller 
      \item DRAM Controller
      \ei
    \item Machines are connected through \textit{network ports} (\textbf{different} than MemPorts)
    \item Network can be an arbitrary topology
  \ei
  \end{columns}
\end{frame}

\begin{frame}
\frametitle{Machine Structure}

  \begin{center}
    \includegraphics<1>[width=12cm]{sliccmachine.jpg}
  \end{center}

  \bi
  \item Machines are (logically) per-block
  \item Consist of:
    \bi
    \item \textbf{Ports} - Interface to the world
    \item \textbf{States} - Both stable and transient
    \item \textbf{Events} - Triggered by incoming messages
    \item \textbf{Transitions} - Old state x Event -> New state
    \item \textbf{Actions} - Occur atomically during transition, e.g., Send/receive messages from network
    \ei
  \ei
\end{frame}

\begin{frame}
\frametitle{MI Example}

  \begin{columns}[c]
  \column{.5\textwidth}
  \begin{tikzpicture}[font=\tiny]
\node (DirAux) [star,star points=7,star point ratio=0.8, fill=gray!40] {...};
\node (Dir1) [rectangle, text centered, fill=blue!40, left=of DirAux] {Directory};
\node (Dir2) [rectangle, text centered, fill=blue!40, right=of DirAux] {Directory};
\node (Interconnect) [rectangle, text centered, fill=red!40, below=0.5cm of DirAux, text width=3cm ] {Pt-to-Pt Interconnect};
\node (L1Aux) [below=0.5cm of Interconnect, star,star points=7,star point ratio=0.8, fill=gray!40] {...};
\node (L11) [rectangle, text centered, fill=blue!40, left=of L1Aux ] {L1 Cache};
\node (L12) [rectangle, text centered, fill=blue!40, right=of L1Aux] {L1 Cache};
\node (CPU1) [rectangle, text centered, fill=green!40, below=.2cm of L11 ] {CPU};
\node (CPU2) [rectangle, text centered, fill=green!40, below=.2cm of L12 ] {CPU};
\draw[-] (Dir1.south) -- ++(0,-0.25) -- ++(1.0,0) -- ([xshift=-1cm] Interconnect.north);
\draw[-] (Dir2.south) -- ++(0,-0.25) -- ++(-1.0,0) -- ([xshift=1cm] Interconnect.north);
\draw[-] (L11.north) -- ++(0,0.25) -- ++(1.0,0) -- ([xshift=-1cm] Interconnect.south);
\draw[-] (L12.north) -- ++(0,0.25) -- ++(-1.0,0) -- ([xshift=1cm] Interconnect.south);
\draw[-] (L11.south) -- (CPU1.north);
\draw[-] (L12.south) -- (CPU2.north);
  \end{tikzpicture}  

  \column{.5\textwidth}
  \begin{center}
    \includegraphics<1>[width=6cm]{mitransitions.jpg}
  \end{center}

  \end{columns}


  \bi
  \item Single-level coherence protocol 
    \bi
    \item 2 controller types -- Cache + Directory
    \ei
  \item Cache Controller
    \bi
    \item 2 stable states: Modified (a.k.a. Valid), Invalid
    \ei
  \item Directory Controller \alert{[Not Shown]}
    \bi
    \item 2 stable states: Modified (Present in cache), Valid
    \ei 
  \item 3 virtual networks (request, response, forward)
  \item See \texttt{src/mem/ruby/protocols/MI\_example.*}
  \ei
\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Machine structure}

  \begin{block}{\small Machine Pseduo-Code}
  \tiny
  \begin{verbatim}
machine(L1Cache, "MI Example L1 Cache'')
  : Sequencer * sequencer,               // parameters to the machine object (set at initialization)
    CacheMemory * cacheMemory,
    int cache_response_latency = 12,
    int issue_latency = 2
{
   <Define machine interface> // 3 virtual channels to/from network + connection to CPU

   <Declare States & Events>  // M,I,<transients> & Load,Store, etc.

   <Map incoming messages to Events> // e.g., RequestMessage::GETX -> Fwd_GETX

   <Define Actions> // e.g., issueRequest

   <Define Transitions> // e.g., I x Store -> M
}  

  \end{verbatim}
  \end{block}

\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\  Defining a machine interface}

   

  \begin{block}{\tiny Interface to the network}
  \tiny
  \texttt{
    \textcolor{green}{\textbf{// MessageBuffers - opaque C++ communication queues}} \\
    MessageBuffer requestFromCache, network=''To'', virtual\_network=''0'', ordered=''true''; \\
    MessageBuffer responseFromCache, network=''To'', virtual\_network=''1'', ordered=''true''; \\
    MessageBuffer forwardToCache, network=''From'', virtual\_network=''2'', ordered=''true''; \\
    MessageBuffer responseToCache, network=''From'', virtual\_network=''1'', ordered=''true''; 
  }

  \vspace{3 mm} \pause
  \texttt{
    \textcolor{green}{\textbf{// out\_port - map request type to outgoing message buffer}} \\
    out\_port(requestNetwork\_out, RequestMsg, requestFromCache); \\
    out\_port(responseNetwork\_out, ResponseMsg, responseFromCache);
  }

  \vspace{3 mm} \pause
  \texttt{
    \textcolor{green}{\textbf{// in\_port - map request type to incomming message buffer}} \\
    \textcolor{green}{\textbf{//}} \hspace{12 mm} \textcolor{green}{\textbf{and produce code to accept incomming messages}} \\
    in\_port(forwardRequestNetwork\_in, RequestMsg, forwardToCache) \{ ... \} \\
    in\_port(responseNetwork\_in, ResponseMsg, responseToCache) \{ ... \}
  }
  \end{block}

  \pause

  \begin{block}{\tiny Interface to a CPU}
  \tiny
  \texttt{  
  \textcolor{green}{\textbf{// The other end of mandatoryQueue attaches to Sequencer }} \\    
  MessageBuffer mandatoryQueue, ordered=''false'';  \\
  in\_port(mandatoryQueue\_in, RubyRequest, mandatoryQueue, desc=''...'') \{ ... \} \\
  \textcolor{green}{\textbf{// There is no corresponing out\_port - handled with hitCallback }} 
  }
  \end{block}

\end{frame}



\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\  Declaring States}

  \begin{block}{\tiny State Declaration}
  \tiny
  \begin{verbatim}
 // STATES
  state_declaration(State, desc="Cache states") {
    // Stable States
    I, AccessPermission:Invalid, desc="Not Present/Invalid";
    M, AccessPermission:Read_Write, desc="Modified";

    // Transient States
    II, AccessPermission:Busy, desc="Not Present/Invalid, issued PUT";
    MI, AccessPermission:Busy, desc="Modified, issued PUT";
    MII, AccessPermission:Busy, desc="Modified, issued PUTX, received nack";
    IS, AccessPermission:Busy, desc="Issued request for LOAD/IFETCH";
    IM, AccessPermission:Busy, desc="Issued request for STORE/ATOMIC";
  }
  \end{verbatim}
  \end{block}

\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Declaring Events}

  \begin{block}{\tiny Event Declaration}
  \tiny
  \begin{verbatim}
// EVENTS
enumeration(Event, desc="Cache events") {
  // from processor
  Load,           desc="Load request from processor";
  Ifetch,         desc="Ifetch request from processor";
  Store,          desc="Store request from processor";

  // From network (directory)
  Data,           desc="Data from network";
  Fwd_GETX,       desc="Forward from network";
  Inv,            desc="Invalidate request from dir";
  Writeback_Ack,  desc="Ack from the directory for a writeback";
  Writeback_Nack, desc="Nack from the directory for a writeback";

  // Internally generated
  Replacement,    desc="Replace a block";
}
  \end{verbatim}
  \end{block}

\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Mapping messages to events}

  \bi
    \item Mapping occurs in \texttt{in\_port} declaration.
    \item \texttt{\small \textbf{peek(in\_port, message\_type)}} 
      \bi \item Sets variable \texttt{in\_msg} to head of in\_port queue. \ei
    \item \texttt{\small \textbf{trigger(Event, address)}}
  \ei

  \begin{block}{\tiny Event mapping}
  \tiny
  \texttt{
   in\_port(forwardRequestNetwork\_in, RequestMsg, forwardToCache) \{ \\
    \hspace{3 mm}  if (forwardRequestNetwork\_in.isReady()) \{ \\
    \hspace{6 mm}    peek(forwardRequestNetwork\_in, RequestMsg) \{ \\
    \hspace{9 mm}      if (in\_msg.Type == CoherenceRequestType:GETX) \{ \\
    \hspace{12 mm}        trigger(Event:Fwd\_GETX, in\_msg.Address); \\
    \hspace{9 mm}      \} \\
    \hspace{9 mm}      ... \\
    \hspace{6 mm}    \} \\
    \hspace{3 mm}  \} \\
  \}
  }   
  \end{block}

\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Defining Transitions}

  \bi
  \item \texttt{\small \textbf{transition(Starting State(s), Event, [Ending State]) [ \{ Actions \} ] }}
  \ei

  \begin{block}{\tiny Transition sequence for new Store request}
  \tiny
  \begin{verbatim}
transition(I, Store, IM) {
  v_allocateTBE;           // allocate TBE (a.k.a. MSHR) on transition to transient state
  i_allocateL1CacheBlock;
  a_issueRequest;
  m_popMandatoryQueue;
}

transition(IM, Data, M) {
  u_writeDataToCache;
  s_store_hit;
  w_deallocateTBE;          // deallocate TBE on transition back to stable state
  n_popResponseQueue;
}
...
  \end{verbatim}
  \end{block}

\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Defining Actions}

  \bi
  \item \texttt{\small action(name, abbrev, [desc]) \{ implementation \}}
  \item Two special functions available in \textit{action}
    \bi
    \item \texttt{\small peek(in\_port, message\_type) \{ use in\_msg \}} 
      \bi \item assigns \texttt{in\_msg} to message at head of port \ei
    \item \texttt{\small enqueue(out\_port, message\_type, [options]) \{ set out\_msg \}} 
      \bi \item enqueues \texttt{out\_msg} on \texttt{out\_port} \ei
    \ei
  \item Special variable \texttt{address} is available inside an action block
    \bi
    \item Set to the address associated with the event that caused the calling transition
    \ei
  \ei

  \begin{block}{\tiny Example Action Definition}
  \tiny
  \begin{verbatim}
action(e_sendData, "e", desc="Send data from cache to requestor") {
  peek(forwardRequestNetwork_in, RequestMsg) {
    enqueue(responseNetwork_out, ResponseMsg, latency=cache_response_latency) {
      out_msg.Address := address;
      out_msg.Type := CoherenceResponseType:DATA;
      out_msg.Sender := machineID;
      out_msg.Destination.add(in_msg.Requestor);      // uses in_msg set by peek
      out_msg.DataBlk := cacheMemory[address].DataBlk;
      out_msg.MessageSize := MessageSizeType:Response_Data;
    }
  }
}
  \end{verbatim}
  \end{block}

\end{frame}

\begin{frame}
\frametitle{MI Example - L1 Cache Controller \footnotesize \\ Transition Table}

  
\end{frame}

\begin{frame}[fragile]
\frametitle{MI Example \footnotesize \\ Connecting SLICC Machines with a Topology}

\begin{columns}[c]


  \column{.3\textwidth}
  \begin{center}
    \includegraphics<1>[height=3cm]{pt2pt.jpg}
  \end{center}

  \column{.7\textwidth}

  \begin{block}{\tiny Creating the Topology -- \alert{Not In SLICC} \texttt{src/mem/ruby/network/topologies/Pt2Pt.py}}
  \tiny
  \begin{verbatim}
# returns a SimObject for for a Pt2Pt Topology
def makeTopology(nodes, options, IntLink, ExtLink, Router):
    # Create an individual router for each controller (node), 
    # and connect them (ext_links)
    routers = [Router(router_id=i) for i in range(len(nodes))]
    ext_links = [ExtLink(link_id=i, ext_node=n, int_node=routers[i])
                 for (i, n) in enumerate(nodes)]
    link_count = len(nodes)

    # Connect routers all-to-all (int_links)
    int_links = []
    for i in xrange(len(nodes)):
        for j in xrange(len(nodes)):
            if (i != j):
                link_count += 1
                int_links.append(IntLink(link_id=link_count,
                                         node_a=routers[i],
                                         node_b=routers[j]))

    # Return Pt2Pt Topology SimObject
    return Pt2Pt(ext_links=ext_links,
                 int_links=int_links,
                 routers=routers)

  \end{verbatim}
  \end{block}

  \end{columns}

\end{frame}

\begin{frame}[fragile]
\frametitle{Using C++ Objects in SLICC}

  \bi
  \item SLICC can be arbitrarily extended with C++ objects
    \bi
    \item e.g., Interface with a new message filter
    \ei
  \item Steps: 
    \bi
    \item Create class in C++
    \item Declare interface in SLICC with \texttt{structure}, external=''yes''
    \item Initialize object in machine
    \item Use!
    \ei
  \ei

  \begin{block}{\tiny Extending SLICC}

  \tiny
  \begin{columns}[c]
  \column{.5\textwidth}
\texttt{
\textcolor{green}{\textbf{// MessageFilter.h}} \\
class MessageFilter \{ \\
public: \\
\hspace{3 mm}MessageFilter(int param1);\\
\vspace{3 mm}
\hspace{3 mm}// returns 1 if message should be filtered \\
\hspace{3 mm}int filter(RequestMsg msg); \\
\}; \\
\vspace{3 mm}
\textcolor{green}{\textbf{// MessageFilter.cc}} \\
int MessageFilter::filter(RequestMsg msg) \\
\{\\
\hspace{3 mm}...\\
\hspace{3 mm}return 0;\\
\}
}
  \pause

  \column{.5\textwidth}
\texttt{
\textcolor{green}{\textbf{// MI\_example-cache.sm}}          \\
structure(MessageFilter, external=''yes'') \{ \\
\hspace{3 mm}int filter(RequestMsg);        \\
\};                              \\
\pause 
\vspace{3 mm}
MessageFilter requestFilter, \\
\hspace{3 mm} constructor\_hack=''param'';   \\
\pause 
\vspace{3 mm}
action(af\_allocateUnlessFiltered, ``af'') \{ \\
\hspace{3 mm}    if (requestFilter.filter(in\_msg) != 1) \{ \\
\hspace{6 mm}      cacheMemory.allocate(address, new Entry); \\
\hspace{3 mm}    \} \\
  \}
}

  \end{columns}
  \end{block}

\end{frame}

\begin{frame}
\frametitle{Detailed Component Simulation: Caches}
   \bi
   \item Set-Associative Caches
   \item Each CacheMemory object represents one \textit{bank} of cache
   \item Configurable bit select for indexing
   \item Modular replacement policy
     \bi
     \item Tree-based pseudo-LRU
     \item LRU
     \ei
   \item See \texttt{src/mem/ruby/system/CacheMemory.hh}
   \ei
\end{frame}

\begin{frame}
\frametitle{Detailed Component Simulation: Memory}
  \begin{center}
    \includegraphics<1>[width=6cm]{mcoverview.jpg}
  \end{center}
  \bi
  \item Memory controller models a \textbf{single channel} DDR2 controller
  \item Implements closed-page policy
  \item Can configure ranks, tCAS, refresh, etc..
  \item See \texttt{src/mem/ruby/system/MemoryController.hh}
  \ei
\end{frame}

\begin{frame}
\frametitle{Detailed Component Simulation: Network}

  \bi
    \item Simple Network
      \bi
      \item Idealized routers - fixed latency, no internal resources
      \item \textbf{Does} model link bandwidth
      \ei
    \item Garnet Network
      \bi
      \item Detailed routers - both fixed and flexible pipeline model
      \item From Princeton, MIT
      \item \includegraphics<1>[width=6cm]{garnetrouter.jpg}
      \ei
    \item See \texttt{src/mem/ruby/network/*}
  \ei

\end{frame}


\begin{frame}
\frametitle{Ruby Debugging Support}

  \bi
  \item Random testing support
    \bi
    \item Stresses protocol by inserting random timing delays
    \ei
  \item Support for coherence transition tracing
  \item Frequent assertions
  \item Deadlock detection
  \ei
\end{frame}

\begin{frame}
\frametitle{Lifetime of a Ruby Memory Request}

  \begin{enumerate}
    \item<1-> Request enters through \texttt{RubyPort::recvTiming}, is converted to RubyRequest, and passed to \textit{Sequencer}.
    \item<2-> Request enters SLICC controllers through \texttt{Sequencer::makeRequest} via \textit{mandatoryQueue}.
    \item<3-> Message on mandatoryQueue triggers an event in L1 Controller. 
    \item<4-> Until request is completed:
    \begin{enumerate}
    \item<1-> (Event, State) is matched to a transition.
    \item<2-> Actions in the matched transition (optionally) send messages to network \& allocate TBE.
    \item<3-> Responses from network trigger more events. 
    \end{enumerate}
    \item<5-> Last event causes action that calls \texttt{Sequencer::hitCallback} \& deallocates TBE.
    \item<6-> RubyRequest is converted back into a Packet \& sent to RubyPort.
  \end{enumerate}

\end{frame}

