_site/cache-transitions/index.html - public/gem5-website - Git at Google

 <!DOCTYPE html>
 <html>
 <head>
 	<meta charset="utf-8">
 	<meta http-equiv="x-ua-compatible" content="ie=edge">
 	<meta name="viewport" content="width=device-width, initial-scale=1">

 	<title>gem5</title>

 	<!-- SITE FAVICON -->
 	<link rel="shortcut icon" type="image/gif" href="/assets/img/gem5ColorVert.gif"/>

 	<link rel="canonical" href="http://localhost:4000/cache-transitions/">
 	<link href='https://fonts.googleapis.com/css?family=Open+Sans:400,300,700,800,600' rel='stylesheet' type='text/css'>
 	<link href='https://fonts.googleapis.com/css?family=Muli:400,300' rel='stylesheet' type='text/css'>

 	<!-- FAVICON -->
 	<link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css">

 	<!-- BOOTSTRAP -->
 	<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/css/bootstrap.min.css" integrity="sha384-MCw98/SFnGE8fJT3GXwEOngsV7Zt27NXFoaoApmYm81iuXoPkFOJwJ8ERdknLPMO" crossorigin="anonymous">

 	<!-- CUSTOM CSS -->
 	<link rel="stylesheet" href="/css/main.css">
 </head>


 <body>
 	<nav class="navbar navbar-expand-md navbar-light bg-light">
   <a class="navbar-brand" href="/">
 		<img src="/assets/img/gem5ColorLong.gif" alt="gem5" height=45px>
 	</a>
   <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNavDropdown" aria-controls="navbarNavDropdown" aria-expanded="false" aria-label="Toggle navigation">
     <span class="navbar-toggler-icon"></span>
   </button>
   <div class="collapse navbar-collapse" id="navbarNavDropdown">
     <ul class="navbar-nav ml-auto">
       <li class="nav-item ">
         <a class="nav-link" href="/">Home</a>
       </li>

 			<li class="nav-item dropdown ">
 				<a class="nav-link dropdown-toggle" href="/about" id="navbarDropdownMenuLink" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
 					About
 				</a>
 				<div class="dropdown-menu" aria-labelledby="navbarDropdownMenuLink">
           <a class="dropdown-item" href="/about">About</a>
           <a class="dropdown-item" href="/publications">Publications</a>
           <a class="dropdown-item" href="/governance">Governance</a>
 				</div>
 			</li>

 			<li class="nav-item dropdown active">
 				<a class="nav-link dropdown-toggle" href="#" id="navbarDropdownMenuLink" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
 					Documentation
 				</a>
 				<div class="dropdown-menu" aria-labelledby="navbarDropdownMenuLink">
 					<!-- Pull navigation from _data/documentation.yml -->

             <a class="dropdown-item" href="/introduction">Introduction</a>

             <a class="dropdown-item" href="/building">Getting Started</a>

             <a class="dropdown-item" href="/environment">Modifying/Extending</a>

             <a class="dropdown-item" href="/MSIintro">Modeling Cache Coherence with Ruby</a>

 				</div>
 			</li>

       <li class="nav-item ">
         <a class="nav-link" href="/contributing">Contributing</a>
       </li>

 			<li class="nav-item ">
         <a class="nav-link" href="/search">Search</a>
       </li>
     </ul>
   </div>
 </nav>

 	<main>
 		<div class="sidenav-top">
   <img src="/assets/img/gem5ColorLong.gif" height="80">
   <div class="search">
     <form action="/search" method="get">
       <!-- <label for="search-box"><i class="fa fa-search"></i></label> -->
       <input type="text" name="query">
       <button type="submit" name="submit"><i class="fa fa-search"></i></button>
     </form>
   </div>
 </div>
 <div class="sidenav">
   <!-- Pull navigation from _data/documentation.yml -->

     <a class="item" href="/introduction" role="button" aria-expanded="false" aria-controls="collapseExample">
       Introduction
     </a>
     <div class="collapse " id="introdution">

     </div>

     <a class="item" data-toggle="collapse" href="#pt1" role="button" aria-expanded="false" aria-controls="collapseExample">
       Getting Started
     </a>
     <div class="collapse " id="pt1">

         <a class="subitem " href="/building">Building gem5</a>

         <a class="subitem " href="/simple_config">Creating a simple configuration script</a>

         <a class="subitem " href="/cache_config">Adding cache to configuration script</a>

         <a class="subitem " href="/gem5_stats">Understanding gem5 statistics and output</a>

         <a class="subitem " href="/example_configs">Using the default configuration scripts</a>

     </div>

     <a class="item" data-toggle="collapse" href="#pt2" role="button" aria-expanded="false" aria-controls="collapseExample">
       Modifying/Extending
     </a>
     <div class="collapse " id="pt2">

         <a class="subitem " href="/environment">Setting up your development environment</a>

         <a class="subitem " href="/helloobject">Creating a very simple SimObject</a>

         <a class="subitem " href="/debugging">Debugging gem5</a>

         <a class="subitem " href="/events">Event-driven programming</a>

         <a class="subitem " href="/parameters">Adding parameters to SimObjects and more events</a>

         <a class="subitem " href="/memoryobject">Creating SimObjects in the memory system</a>

         <a class="subitem " href="/simplecache">Creating a simple cache object</a>

     </div>

     <a class="item" data-toggle="collapse" href="#pt3" role="button" aria-expanded="false" aria-controls="collapseExample">
       Modeling Cache Coherence with Ruby
     </a>
     <div class="collapse show" id="pt3">

         <a class="subitem " href="/MSIintro">Introduction to Ruby</a>

         <a class="subitem " href="/cache-intro">MSI example cache protocol</a>

         <a class="subitem " href="/cache-declarations">Declaring a state machine</a>

         <a class="subitem " href="/cache-in-ports">In port code blocks</a>

         <a class="subitem " href="/cache-actions">Action code blocks</a>

         <a class="subitem active" href="/cache-transitions">Transition code blocks</a>

         <a class="subitem " href="/directory">MSI Directory implementation</a>

         <a class="subitem " href="/MSIbuilding">Compiling a SLICC protocol</a>

         <a class="subitem " href="/configuration">Configuring a simple Ruby system</a>

         <a class="subitem " href="/running">Running the simple Ruby system</a>

         <a class="subitem " href="/MSIdebugging">Debugging SLICC Protocols</a>

         <a class="subitem " href="/simple-MI_example">Configuring for a standard protocol</a>

     </div>

 </div>

 <div class="container" id="doc-container">

   <!-- <h1>Transition code blocks</h1> -->
   <dl>
   <dt>authors</dt>
   <dd>Jason Lowe-Power</dd>
 </dl>

 <h1 id="transition-code-blocks">Transition code blocks</h1>

 <p>Finally, we’ve reached the final section of the state machine file! This
 section contains the details for all of the transitions between states
 and what actions to execute during the transition.</p>

 <p>So far in this chapter we have written the state machine top to bottom
 one section at a time. However, in most cache coherence implementations
 you will find that you need to move around between sections. For
 instance, when writing the transitions you will realize you forgot to
 add an action, or you notice that you actually need another transient
 state to implement the protocol. This is the normal way to write
 protocols, but for simplicity this chapter goes through the file top to
 bottom.</p>

 <p>Transition blocks consist of two parts. First, the first line of a
 transition block contains the begin state, event to transition on, and
 end state (the end state may not be required, as we will discuss below).
 Second, the transition block contains all of the actions to execute on
 this transition. For instance, a simple transition in the MSI protocol
 is transitioning out of Invalid on a Load.</p>

 <p>``` {.sourceCode .c++}
 transition(I, Load, IS_D) {
     allocateCacheBlock;
     allocateTBE;
     sendGetS;
     popMandatoryQueue;
 }</p>
 <div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>
 First, you specify the transition as the "parameters" to the
 `transition` statement. In this case, if the initial state is `I` and
 the event is `Load` then transition to `IS_D` (was invalid, going to
 shared, waiting for data). This transition is straight out of Table 8.3
 in Sorin et al.

 Then, inside the `transition` code block, all of the actions that will
 execute are listed in order. For this transition first we allocate the
 cache block. Remember that in the `allocateCacheBlock` action the newly
 allocated entry is set to the entry that will be used in the rest of the
 actions. After allocating the cache block, we also allocate a TBE. This
 could be used if we need to wait for acks from other caches. Next, we
 send a GetS request to the directory, and finally we pop the head entry
 off of the mandatory queue since we have fully handled it.

 ``` {.sourceCode .c++}
 transition(IS_D, {Load, Store, Replacement, Inv}) {
     stall;
 }
 </code></pre></div></div>

 <p>In this transition, we use slightly different syntax. According to Table
 8.3 from Sorin et al., we should stall if the cache is in IS_D on
 loads, stores, replacements, and invalidates. We can specify a single
 transition statement for this by including multiple events in curly
 brackets as above. Additionally, the final state isn’t required. If the
 final state isn’t specified, then the transition is executed and the
 state is not updated (i.e., the block stays in its beginning state). You
 can read the above transition as “If the cache block is in state IS_D
 and there is a load, store, replacement, or invalidate stall the
 protocol and do not transition out of the state.” You can also use curly
 brackets for beginning states, as shown in some of the transitions
 below.</p>

 <p>Below is the rest of the transitions needed to implement the L1 cache
 from the MSI protocol.</p>

 <p>``` {.sourceCode .c++}
 transition(IS_D, {DataDirNoAcks, DataOwner}, S) {
     writeDataToCache;
     deallocateTBE;
     externalLoadHit;
     popResponseQueue;
 }</p>

 <p>transition({IM_AD, IM_A}, {Load, Store, Replacement, FwdGetS, FwdGetM}) {
     stall;
 }</p>

 <p>transition({IM_AD, SM_AD}, {DataDirNoAcks, DataOwner}, M) {
     writeDataToCache;
     deallocateTBE;
     externalStoreHit;
     popResponseQueue;
 }</p>

 <p>transition(IM_AD, DataDirAcks, IM_A) {
     writeDataToCache;
     storeAcks;
     popResponseQueue;
 }</p>

 <p>transition({IM_AD, IM_A, SM_AD, SM_A}, InvAck) {
     decrAcks;
     popResponseQueue;
 }</p>

 <p>transition({IM_A, SM_A}, LastInvAck, M) {
     deallocateTBE;
     externalStoreHit;
     popResponseQueue;
 }</p>

 <p>transition({S, SM_AD, SM_A, M}, Load) {
     loadHit;
     popMandatoryQueue;
 }</p>

 <p>transition(S, Store, SM_AD) {
     allocateTBE;
     sendGetM;
     popMandatoryQueue;
 }</p>

 <p>transition(S, Replacement, SI_A) {
     sendPutS;
     forwardEviction;
 }</p>

 <p>transition(S, Inv, I) {
     sendInvAcktoReq;
     deallocateCacheBlock;
     forwardEviction;
     popForwardQueue;
 }</p>

 <p>transition({SM_AD, SM_A}, {Store, Replacement, FwdGetS, FwdGetM}) {
     stall;
 }</p>

 <p>transition(SM_AD, Inv, IM_AD) {
     sendInvAcktoReq;
     forwardEviction;
     popForwardQueue;
 }</p>

 <p>transition(SM_AD, DataDirAcks, SM_A) {
     writeDataToCache;
     storeAcks;
     popResponseQueue;
 }</p>

 <p>transition(M, Store) {
     storeHit;
     popMandatoryQueue;
 }</p>

 <p>transition(M, Replacement, MI_A) {
     sendPutM;
     forwardEviction;
 }</p>

 <p>transition(M, FwdGetS, S) {
     sendCacheDataToReq;
     sendCacheDataToDir;
     popForwardQueue;
 }</p>

 <p>transition(M, FwdGetM, I) {
     sendCacheDataToReq;
     deallocateCacheBlock;
     popForwardQueue;
 }</p>

 <p>transition({MI_A, SI_A, II_A}, {Load, Store, Replacement}) {
     stall;
 }</p>

 <p>transition(MI_A, FwdGetS, SI_A) {
     sendCacheDataToReq;
     sendCacheDataToDir;
     popForwardQueue;
 }</p>

 <p>transition(MI_A, FwdGetM, II_A) {
     sendCacheDataToReq;
     popForwardQueue;
 }</p>

 <p>transition({MI_A, SI_A, II_A}, PutAck, I) {
     deallocateCacheBlock;
     popForwardQueue;
 }</p>

 <p>transition(SI_A, Inv, II_A) {
     sendInvAcktoReq;
     popForwardQueue;
 }
 ```</p>

 <p>You can download the complete <code class="highlighter-rouge">MSI-cache.sm</code> file
 here &lt;../../_static/scripts/part3/MSI_protocol/MSI-cache.sm&gt;.</p>


 </div>

 	</main>

 	<script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
 	<script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.3/umd/popper.min.js" integrity="sha384-ZMP7rVo3mIykV+2+9J3UJ46jBk0WLaUAdn689aCwoqbBJiSnjAK/l8WvCWPIPm49" crossorigin="anonymous"></script>
 	<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/js/bootstrap.min.js" integrity="sha384-ChfqqxuZUCnJSK3+MXmPNIyE6ZbWh2IMqE241rYiqJxyMiZ6OW/JmZQ5stwEULTy" crossorigin="anonymous"></script>

 	<script>
 	  // When the user scrolls down 20px from the top of the document, show the button
 	  window.onscroll = function() {scrollFunction()};

 	  function scrollFunction() {
 	      if (document.body.scrollTop > 100 || document.documentElement.scrollTop > 20) {
 	          document.getElementById("myBtn").style.display = "block";
 	      } else {
 	          document.getElementById("myBtn").style.display = "none";
 	      }
 	  }

 	  // When the user clicks on the button, scroll to the top of the document
 	  function topFunction() {
 	      document.body.scrollTop = 0;
 	      document.documentElement.scrollTop = 0;
 	  }
 	</script>

 </body>

 <footer class="page-footer">
 	<div class="container">
 		<div class="row">

 			<div class="col-12 col-sm-4">
 				<p><a href="/about">About</a></p>
 				<p><a href="/publications">Publications</a></p>
 				<p><a href="/contributing">Contributing</a></p>
 			</div><br>

 			<div class="col-12 col-sm-4">
 				<p><a href="/gettingstarted">Documentation</a></p>
 				<p><a href="#">Source</a></p>
 			</div><br>

 			<div class="col-12 col-sm-4">
 				<p><a href="/help">Help</a></p>
 				<p><a href="/search">Search</a></p>
 				<p><a href="#">Mailing Lists</a></p>
 			</div>

 		</div>
 	</div>
 </footer>


 </html>
	<!DOCTYPE html>
	<html>
	<head>
	<meta charset="utf-8">
	<meta http-equiv="x-ua-compatible" content="ie=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1">

	<title>gem5</title>

	<!-- SITE FAVICON -->
	<link rel="shortcut icon" type="image/gif" href="/assets/img/gem5ColorVert.gif"/>

	<link rel="canonical" href="http://localhost:4000/cache-transitions/">
	<link href='https://fonts.googleapis.com/css?family=Open+Sans:400,300,700,800,600' rel='stylesheet' type='text/css'>
	<link href='https://fonts.googleapis.com/css?family=Muli:400,300' rel='stylesheet' type='text/css'>

	<!-- FAVICON -->
	<link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css">

	<!-- BOOTSTRAP -->
	<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/css/bootstrap.min.css" integrity="sha384-MCw98/SFnGE8fJT3GXwEOngsV7Zt27NXFoaoApmYm81iuXoPkFOJwJ8ERdknLPMO" crossorigin="anonymous">

	<!-- CUSTOM CSS -->
	<link rel="stylesheet" href="/css/main.css">
	</head>


	<body>
	<nav class="navbar navbar-expand-md navbar-light bg-light">
	<a class="navbar-brand" href="/">
	<img src="/assets/img/gem5ColorLong.gif" alt="gem5" height=45px>
	</a>
	<button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNavDropdown" aria-controls="navbarNavDropdown" aria-expanded="false" aria-label="Toggle navigation">
	<span class="navbar-toggler-icon"></span>
	</button>
	<div class="collapse navbar-collapse" id="navbarNavDropdown">
	<ul class="navbar-nav ml-auto">
	<li class="nav-item ">
	<a class="nav-link" href="/">Home</a>
	</li>

	<li class="nav-item dropdown ">
	<a class="nav-link dropdown-toggle" href="/about" id="navbarDropdownMenuLink" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
	About
	</a>
	<div class="dropdown-menu" aria-labelledby="navbarDropdownMenuLink">
	<a class="dropdown-item" href="/about">About</a>
	<a class="dropdown-item" href="/publications">Publications</a>
	<a class="dropdown-item" href="/governance">Governance</a>
	</div>
	</li>

	<li class="nav-item dropdown active">
	<a class="nav-link dropdown-toggle" href="#" id="navbarDropdownMenuLink" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
	Documentation
	</a>
	<div class="dropdown-menu" aria-labelledby="navbarDropdownMenuLink">
	<!-- Pull navigation from _data/documentation.yml -->

	<a class="dropdown-item" href="/introduction">Introduction</a>

	<a class="dropdown-item" href="/building">Getting Started</a>

	<a class="dropdown-item" href="/environment">Modifying/Extending</a>

	<a class="dropdown-item" href="/MSIintro">Modeling Cache Coherence with Ruby</a>

	</div>
	</li>

	<li class="nav-item ">
	<a class="nav-link" href="/contributing">Contributing</a>
	</li>

	<li class="nav-item ">
	<a class="nav-link" href="/search">Search</a>
	</li>
	</ul>
	</div>
	</nav>

	<main>
	<div class="sidenav-top">
	<img src="/assets/img/gem5ColorLong.gif" height="80">
	<div class="search">
	<form action="/search" method="get">
	<!-- <label for="search-box"><i class="fa fa-search"></i></label> -->
	<input type="text" name="query">
	<button type="submit" name="submit"><i class="fa fa-search"></i></button>
	</form>
	</div>
	</div>
	<div class="sidenav">
	<!-- Pull navigation from _data/documentation.yml -->

	<a class="item" href="/introduction" role="button" aria-expanded="false" aria-controls="collapseExample">
	Introduction
	</a>
	<div class="collapse " id="introdution">

	</div>

	<a class="item" data-toggle="collapse" href="#pt1" role="button" aria-expanded="false" aria-controls="collapseExample">
	Getting Started
	</a>
	<div class="collapse " id="pt1">

	<a class="subitem " href="/building">Building gem5</a>

	<a class="subitem " href="/simple_config">Creating a simple configuration script</a>

	<a class="subitem " href="/cache_config">Adding cache to configuration script</a>

	<a class="subitem " href="/gem5_stats">Understanding gem5 statistics and output</a>

	<a class="subitem " href="/example_configs">Using the default configuration scripts</a>

	</div>

	<a class="item" data-toggle="collapse" href="#pt2" role="button" aria-expanded="false" aria-controls="collapseExample">
	Modifying/Extending
	</a>
	<div class="collapse " id="pt2">

	<a class="subitem " href="/environment">Setting up your development environment</a>

	<a class="subitem " href="/helloobject">Creating a very simple SimObject</a>

	<a class="subitem " href="/debugging">Debugging gem5</a>

	<a class="subitem " href="/events">Event-driven programming</a>

	<a class="subitem " href="/parameters">Adding parameters to SimObjects and more events</a>

	<a class="subitem " href="/memoryobject">Creating SimObjects in the memory system</a>

	<a class="subitem " href="/simplecache">Creating a simple cache object</a>

	</div>

	<a class="item" data-toggle="collapse" href="#pt3" role="button" aria-expanded="false" aria-controls="collapseExample">
	Modeling Cache Coherence with Ruby
	</a>
	<div class="collapse show" id="pt3">

	<a class="subitem " href="/MSIintro">Introduction to Ruby</a>

	<a class="subitem " href="/cache-intro">MSI example cache protocol</a>

	<a class="subitem " href="/cache-declarations">Declaring a state machine</a>

	<a class="subitem " href="/cache-in-ports">In port code blocks</a>

	<a class="subitem " href="/cache-actions">Action code blocks</a>

	<a class="subitem active" href="/cache-transitions">Transition code blocks</a>

	<a class="subitem " href="/directory">MSI Directory implementation</a>

	<a class="subitem " href="/MSIbuilding">Compiling a SLICC protocol</a>

	<a class="subitem " href="/configuration">Configuring a simple Ruby system</a>

	<a class="subitem " href="/running">Running the simple Ruby system</a>

	<a class="subitem " href="/MSIdebugging">Debugging SLICC Protocols</a>

	<a class="subitem " href="/simple-MI_example">Configuring for a standard protocol</a>

	</div>

	</div>

	<div class="container" id="doc-container">

	<!-- <h1>Transition code blocks</h1> -->
	<dl>
	<dt>authors</dt>
	<dd>Jason Lowe-Power</dd>
	</dl>

	<h1 id="transition-code-blocks">Transition code blocks</h1>

	<p>Finally, we’ve reached the final section of the state machine file! This
	section contains the details for all of the transitions between states
	and what actions to execute during the transition.</p>

	<p>So far in this chapter we have written the state machine top to bottom
	one section at a time. However, in most cache coherence implementations
	you will find that you need to move around between sections. For
	instance, when writing the transitions you will realize you forgot to
	add an action, or you notice that you actually need another transient
	state to implement the protocol. This is the normal way to write
	protocols, but for simplicity this chapter goes through the file top to
	bottom.</p>

	<p>Transition blocks consist of two parts. First, the first line of a
	transition block contains the begin state, event to transition on, and
	end state (the end state may not be required, as we will discuss below).
	Second, the transition block contains all of the actions to execute on
	this transition. For instance, a simple transition in the MSI protocol
	is transitioning out of Invalid on a Load.</p>

	<p>``` {.sourceCode .c++}
	transition(I, Load, IS_D) {
	allocateCacheBlock;
	allocateTBE;
	sendGetS;
	popMandatoryQueue;
	}</p>
	<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>
	First, you specify the transition as the "parameters" to the
	`transition` statement. In this case, if the initial state is `I` and
	the event is `Load` then transition to `IS_D` (was invalid, going to
	shared, waiting for data). This transition is straight out of Table 8.3
	in Sorin et al.

	Then, inside the `transition` code block, all of the actions that will
	execute are listed in order. For this transition first we allocate the
	cache block. Remember that in the `allocateCacheBlock` action the newly
	allocated entry is set to the entry that will be used in the rest of the
	actions. After allocating the cache block, we also allocate a TBE. This
	could be used if we need to wait for acks from other caches. Next, we
	send a GetS request to the directory, and finally we pop the head entry
	off of the mandatory queue since we have fully handled it.

	``` {.sourceCode .c++}
	transition(IS_D, {Load, Store, Replacement, Inv}) {
	stall;
	}
	</code></pre></div></div>

	<p>In this transition, we use slightly different syntax. According to Table
	8.3 from Sorin et al., we should stall if the cache is in IS_D on
	loads, stores, replacements, and invalidates. We can specify a single
	transition statement for this by including multiple events in curly
	brackets as above. Additionally, the final state isn’t required. If the
	final state isn’t specified, then the transition is executed and the
	state is not updated (i.e., the block stays in its beginning state). You
	can read the above transition as “If the cache block is in state IS_D
	and there is a load, store, replacement, or invalidate stall the
	protocol and do not transition out of the state.” You can also use curly
	brackets for beginning states, as shown in some of the transitions
	below.</p>

	<p>Below is the rest of the transitions needed to implement the L1 cache
	from the MSI protocol.</p>

	<p>``` {.sourceCode .c++}
	transition(IS_D, {DataDirNoAcks, DataOwner}, S) {
	writeDataToCache;
	deallocateTBE;
	externalLoadHit;
	popResponseQueue;
	}</p>

	<p>transition({IM_AD, IM_A}, {Load, Store, Replacement, FwdGetS, FwdGetM}) {
	stall;
	}</p>

	<p>transition({IM_AD, SM_AD}, {DataDirNoAcks, DataOwner}, M) {
	writeDataToCache;
	deallocateTBE;
	externalStoreHit;
	popResponseQueue;
	}</p>

	<p>transition(IM_AD, DataDirAcks, IM_A) {
	writeDataToCache;
	storeAcks;
	popResponseQueue;
	}</p>

	<p>transition({IM_AD, IM_A, SM_AD, SM_A}, InvAck) {
	decrAcks;
	popResponseQueue;
	}</p>

	<p>transition({IM_A, SM_A}, LastInvAck, M) {
	deallocateTBE;
	externalStoreHit;
	popResponseQueue;
	}</p>

	<p>transition({S, SM_AD, SM_A, M}, Load) {
	loadHit;
	popMandatoryQueue;
	}</p>

	<p>transition(S, Store, SM_AD) {
	allocateTBE;
	sendGetM;
	popMandatoryQueue;
	}</p>

	<p>transition(S, Replacement, SI_A) {
	sendPutS;
	forwardEviction;
	}</p>

	<p>transition(S, Inv, I) {
	sendInvAcktoReq;
	deallocateCacheBlock;
	forwardEviction;
	popForwardQueue;
	}</p>

	<p>transition({SM_AD, SM_A}, {Store, Replacement, FwdGetS, FwdGetM}) {
	stall;
	}</p>

	<p>transition(SM_AD, Inv, IM_AD) {
	sendInvAcktoReq;
	forwardEviction;
	popForwardQueue;
	}</p>

	<p>transition(SM_AD, DataDirAcks, SM_A) {
	writeDataToCache;
	storeAcks;
	popResponseQueue;
	}</p>

	<p>transition(M, Store) {
	storeHit;
	popMandatoryQueue;
	}</p>

	<p>transition(M, Replacement, MI_A) {
	sendPutM;
	forwardEviction;
	}</p>

	<p>transition(M, FwdGetS, S) {
	sendCacheDataToReq;
	sendCacheDataToDir;
	popForwardQueue;
	}</p>

	<p>transition(M, FwdGetM, I) {
	sendCacheDataToReq;
	deallocateCacheBlock;
	popForwardQueue;
	}</p>

	<p>transition({MI_A, SI_A, II_A}, {Load, Store, Replacement}) {
	stall;
	}</p>

	<p>transition(MI_A, FwdGetS, SI_A) {
	sendCacheDataToReq;
	sendCacheDataToDir;
	popForwardQueue;
	}</p>

	<p>transition(MI_A, FwdGetM, II_A) {
	sendCacheDataToReq;
	popForwardQueue;
	}</p>

	<p>transition({MI_A, SI_A, II_A}, PutAck, I) {
	deallocateCacheBlock;
	popForwardQueue;
	}</p>

	<p>transition(SI_A, Inv, II_A) {
	sendInvAcktoReq;
	popForwardQueue;
	}
	```</p>

	<p>You can download the complete <code class="highlighter-rouge">MSI-cache.sm</code> file
	here <../../_static/scripts/part3/MSI_protocol/MSI-cache.sm>.</p>


	</div>

	</main>

	<script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.3/umd/popper.min.js" integrity="sha384-ZMP7rVo3mIykV+2+9J3UJ46jBk0WLaUAdn689aCwoqbBJiSnjAK/l8WvCWPIPm49" crossorigin="anonymous"></script>
	<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.1.3/js/bootstrap.min.js" integrity="sha384-ChfqqxuZUCnJSK3+MXmPNIyE6ZbWh2IMqE241rYiqJxyMiZ6OW/JmZQ5stwEULTy" crossorigin="anonymous"></script>

	<script>
	// When the user scrolls down 20px from the top of the document, show the button
	window.onscroll = function() {scrollFunction()};

	function scrollFunction() {
	if (document.body.scrollTop > 100 \|\| document.documentElement.scrollTop > 20) {
	document.getElementById("myBtn").style.display = "block";
	} else {
	document.getElementById("myBtn").style.display = "none";
	}
	}

	// When the user clicks on the button, scroll to the top of the document
	function topFunction() {
	document.body.scrollTop = 0;
	document.documentElement.scrollTop = 0;
	}
	</script>

	</body>

	<footer class="page-footer">
	<div class="container">
	<div class="row">

	<div class="col-12 col-sm-4">
	<p><a href="/about">About</a></p>
	<p><a href="/publications">Publications</a></p>
	<p><a href="/contributing">Contributing</a></p>
	</div><br>

	<div class="col-12 col-sm-4">
	<p><a href="/gettingstarted">Documentation</a></p>
	<p><a href="#">Source</a></p>
	</div><br>

	<div class="col-12 col-sm-4">
	<p><a href="/help">Help</a></p>
	<p><a href="/search">Search</a></p>
	<p><a href="#">Mailing Lists</a></p>
	</div>

	</div>
	</div>
	</footer>


	</html>