| <!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="/blog">Blog</a> |
| </li> |
| |
| <li class="nav-item "> |
| <a class="nav-link" href="/search">Search</a> |
| </li> |
| </ul> |
| </div> |
| </nav> |
| |
| <main> |
| <div class="sidenav-top"> |
| <a href="/"><img src="/assets/img/gem5ColorLong.gif" height="80"></a> |
| <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="introduction"> |
| |
| </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"> |
| <div class="edit"><a href="https://github.com/gem5/new-website/tree/master/_pages/documentation/part3/cache-transitions.md">Edit this page</a></div> |
| <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> |
| |
| <br> |
| |
| <!-- RETRIVE PREVIOUS PAGE LINK --> |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| <!-- RETRIEVE NEXT PAGE LINK --> |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| <div class="navbuttons"> |
| |
| <a href="/cache-actions"><button type="button" class="btn btn-outline-primary">PREVIOUS</button></a> |
| |
| |
| |
| <a href="/directory"><button type="button" class="btn btn-outline-primary">NEXT</button></a> |
| |
| </div> |
| </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> |
| |
| |
| </html> |