src/mem/protocol/MOESI_SMP_token-cache.sm

   1
   2 /*
   3  * Copyright (c) 1999-2005 Mark D. Hill and David A. Wood
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * $Id: MOESI_token-cache.sm 1.10 05/01/19 15:41:25-06:00 beckmann@emperor11.cs.wisc.edu $
  32  *
  33  */
  34
  35 machine(L1Cache, "Token protocol") {
  36
  37   MessageBuffer requestFromCache, network="To", virtual_network="1", ordered="false";
  38   MessageBuffer responseFromCache, network="To", virtual_network="0", ordered="false";
  39   MessageBuffer persistentFromCache, network="To", virtual_network="2", ordered="true";
  40
  41   MessageBuffer requestToCache, network="From", virtual_network="1", ordered="false";
  42   MessageBuffer responseToCache, network="From", virtual_network="0", ordered="false";
  43   MessageBuffer persistentToCache, network="From", virtual_network="2", ordered="true";
  44
  45
  46   // STATES
  47   enumeration(State, desc="Cache states", default="L1Cache_State_I") {
  48     // Base states
  49     NP,   "NP",   desc="Not Present";
  50     I,    "I",    desc="Idle";
  51     S,    "S",    desc="Shared";
  52     O,    "O",    desc="Owned";
  53     M,    "M",    desc="Modified (dirty)";
  54     MM,   "MM",   desc="Modified (dirty and locally modified)";
  55     M_W,  "M^W",  desc="Modified (dirty), waiting";
  56     MM_W, "MM^W", desc="Modified (dirty and locally modified), waiting";
  57
  58     // Transient States
  59     IM, "IM", desc="Issued GetX";
  60     SM, "SM", desc="Issued GetX, we still have an old copy of the line";
  61     OM, "OM", desc="Issued GetX, received data";
  62     IS, "IS", desc="Issued GetS";
  63
  64     // Locked states
  65     I_L,  "I^L",   desc="Invalid, Locked";
  66     S_L,  "S^L",   desc="Shared, Locked";
  67     IM_L, "IM^L",  desc="Invalid, Locked, trying to go to Modified";
  68     SM_L, "SM^L",  desc="Shared, Locked, trying to go to Modified";
  69     IS_L, "IS^L",  desc="Invalid, Locked, trying to go to Shared";
  70   }
  71
  72   // EVENTS
  73   enumeration(Event, desc="Cache events") {
  74     Load,            desc="Load request from the processor";
  75     Ifetch,          desc="I-fetch request from the processor";
  76     Store,           desc="Store request from the processor";
  77     L2_Replacement,  desc="L2 Replacement";
  78     L1_to_L2,        desc="L1 to L2 transfer";
  79     L2_to_L1D,       desc="L2 to L1-Data transfer";
  80     L2_to_L1I,       desc="L2 to L1-Instruction transfer";
  81
  82     // Responses
  83     Data_Shared,             desc="Received a data message, we are now a sharer";
  84     Data_Shared_All_Tokens,  desc="Received a data message, we are now a sharer, we now have all the tokens";
  85     Data_Owner,              desc="Received a data message, we are now the owner";
  86     Data_Owner_All_Tokens,   desc="Received a data message, we are now the owner, we now have all the tokens";
  87     Ack,                     desc="Received an ack message";
  88     Ack_All_Tokens,          desc="Received an ack message, we now have all the tokens";
  89
  90     // Requests
  91     Transient_GETX,  desc="A GetX from another processor";
  92     Transient_GETS,  desc="A GetS from another processor";
  93
  94     // Lock/Unlock
  95     Persistent_GETX,     desc="Another processor has priority to read/write";
  96     Persistent_GETS,     desc="Another processor has priority to read";
  97     Own_Lock_or_Unlock,  desc="This processor now has priority";
  98
  99     // Triggers
 100     Request_Timeout,         desc="Timeout";
 101     Use_Timeout,             desc="Timeout";
 102
 103   }
 104
 105   // TYPES
 106
 107   int getRetryThreshold();
 108
 109   // CacheEntry
 110   structure(Entry, desc="...", interface="AbstractCacheEntry") {
 111     DataBlock DataBlk,       desc="data for the block, required by CacheMemory";
 112     State CacheState,        desc="cache state";
 113     bool Dirty,              desc="Is the data dirty (different than memory)?";
 114     int Tokens,              desc="The number of tokens we're holding for the line";
 115   }
 116
 117   // TBE fields
 118   structure(TBE, desc="...") {
 119     State TBEState,                       desc="Transient state";
 120     int IssueCount,      default="0",     desc="The number of times we've issued a request for this line.";
 121     Address PC,                           desc="Program counter of request";
 122     AccessType AccessType,                desc="Type of request (used for profiling)";
 123     Time IssueTime,                       desc="Time the request was issued";
 124   }
 125
 126   external_type(CacheMemory) {
 127     bool cacheAvail(Address);
 128     Address cacheProbe(Address);
 129     void allocate(Address);
 130     void deallocate(Address);
 131     Entry lookup(Address);
 132     void changePermission(Address, AccessPermission);
 133     bool isTagPresent(Address);
 134   }
 135
 136   external_type(TBETable) {
 137     TBE lookup(Address);
 138     void allocate(Address);
 139     void deallocate(Address);
 140     bool isPresent(Address);
 141   }
 142
 143   external_type(TimerTable, inport="yes") {
 144     bool isReady();
 145     Address readyAddress();
 146     void set(Address, int);
 147     void unset(Address);
 148     bool isSet(Address);
 149   }
 150
 151   MessageBuffer mandatoryQueue, ordered="false", abstract_chip_ptr="true";
 152   Sequencer sequencer, abstract_chip_ptr="true", constructor_hack="i";
 153
 154   TBETable TBEs, template_hack="<L1Cache_TBE>";
 155   CacheMemory L1IcacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L1_CACHE_NUM_SETS_BITS,L1_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L1I"', abstract_chip_ptr="true";
 156   CacheMemory L1DcacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L1_CACHE_NUM_SETS_BITS,L1_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L1D"', abstract_chip_ptr="true";
 157   CacheMemory L2cacheMemory, template_hack="<L1Cache_Entry>", constructor_hack='L2_CACHE_NUM_SETS_BITS,L2_CACHE_ASSOC,MachineType_L1Cache,int_to_string(i)+"_L2"', abstract_chip_ptr="true";
 158   PersistentTable persistentTable, constructor_hack="i";
 159   TimerTable useTimerTable;
 160   TimerTable reissueTimerTable;
 161
 162   int outstandingRequests, default="0";
 163   int outstandingPersistentRequests, default="0";
 164   void profile_outstanding_request(int outstanding);
 165   void profile_outstanding_persistent_request(int outstanding);
 166
 167   int averageLatencyHysteresis, default="(8)"; // Constant that provides hysteresis for calculated the estimated average
 168   int averageLatencyCounter, default="(500 << (*(m_L1Cache_averageLatencyHysteresis_vec[i])))";
 169   // int averageLatencyCounter, default="(250)";
 170
 171   int averageLatencyEstimate() {
 172     return averageLatencyCounter >> averageLatencyHysteresis;
 173   }
 174
 175   void updateAverageLatencyEstimate(int latency) {
 176     assert(latency >= 0);
 177
 178     // By subtracting the current average and then adding the most
 179     // recent sample, we calculate an estimate of the recent average.
 180     // If we simply used a running sum and divided by the total number
 181     // of entries, the estimate of the average would adapt very slowly
 182     // after the execution has run for a long time.
 183     averageLatencyCounter := averageLatencyCounter - averageLatencyEstimate() + latency;
 184   }
 185
 186   Entry getCacheEntry(Address addr), return_by_ref="yes" {
 187     if (L2cacheMemory.isTagPresent(addr)) {
 188       return L2cacheMemory[addr];
 189     } else if (L1DcacheMemory.isTagPresent(addr)) {
 190       return L1DcacheMemory[addr];
 191     } else {
 192       return L1IcacheMemory[addr];
 193     }
 194   }
 195
 196   int getTokens(Address addr) {
 197     if (L2cacheMemory.isTagPresent(addr)) {
 198       return L2cacheMemory[addr].Tokens;
 199     } else if (L1DcacheMemory.isTagPresent(addr)) {
 200       return L1DcacheMemory[addr].Tokens;
 201     } else if (L1IcacheMemory.isTagPresent(addr)) {
 202       return L1IcacheMemory[addr].Tokens;
 203     } else {
 204       return 0;
 205     }
 206   }
 207
 208   void changePermission(Address addr, AccessPermission permission) {
 209     if (L2cacheMemory.isTagPresent(addr)) {
 210       return L2cacheMemory.changePermission(addr, permission);
 211     } else if (L1DcacheMemory.isTagPresent(addr)) {
 212       return L1DcacheMemory.changePermission(addr, permission);
 213     } else {
 214       return L1IcacheMemory.changePermission(addr, permission);
 215     }
 216   }
 217
 218   bool isCacheTagPresent(Address addr) {
 219     return (L2cacheMemory.isTagPresent(addr) || L1DcacheMemory.isTagPresent(addr) || L1IcacheMemory.isTagPresent(addr));
 220   }
 221
 222   State getState(Address addr) {
 223     assert((L1DcacheMemory.isTagPresent(addr) && L1IcacheMemory.isTagPresent(addr)) == false);
 224     assert((L1IcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 225     assert((L1DcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 226
 227     if (TBEs.isPresent(addr)) {
 228       return TBEs[addr].TBEState;
 229     } else if (isCacheTagPresent(addr)) {
 230       return getCacheEntry(addr).CacheState;
 231     } else if ((persistentTable.isLocked(addr) == true) && (persistentTable.findSmallest(addr) != machineID)) {
 232       // Not in cache, in persistent table, but this processor isn't highest priority
 233       return State:I_L;
 234     } else {
 235       return State:NP;
 236     }
 237   }
 238
 239   void setState(Address addr, State state) {
 240     assert((L1DcacheMemory.isTagPresent(addr) && L1IcacheMemory.isTagPresent(addr)) == false);
 241     assert((L1IcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 242     assert((L1DcacheMemory.isTagPresent(addr) && L2cacheMemory.isTagPresent(addr)) == false);
 243
 244     assert(outstandingPersistentRequests >= 0);
 245     assert(outstandingRequests >= 0);
 246
 247     if (useTimerTable.isSet(addr)) {
 248       assert((state == State:M_W) || (state == State:MM_W));
 249     } else {
 250       assert(state != State:M_W);
 251       assert(state != State:MM_W);
 252     }
 253
 254     if (reissueTimerTable.isSet(addr)) {
 255       assert((state == State:IS) ||
 256              (state == State:IM) ||
 257              (state == State:SM) ||
 258              (state == State:OM) ||
 259              (state == State:IS_L) ||
 260              (state == State:IM_L) ||
 261              (state == State:SM_L));
 262     } else if (TBEs.isPresent(addr) && TBEs[addr].IssueCount < getRetryThreshold()) {
 263       // If the timer is not set, you better have issued a persistent request
 264       assert(state != State:IS);
 265       assert(state != State:IM);
 266       assert(state != State:SM);
 267       assert(state != State:OM);
 268       assert(state != State:IS_L);
 269       assert(state != State:IM_L);
 270       assert(state != State:SM_L);
 271     }
 272
 273     if (TBEs.isPresent(addr) && (TBEs[addr].IssueCount > getRetryThreshold())) {
 274       assert(reissueTimerTable.isSet(addr) == false);
 275     }
 276
 277     if (TBEs.isPresent(addr)) {
 278       assert(state != State:I);
 279       assert(state != State:S);
 280       assert(state != State:O);
 281       assert(state != State:MM);
 282       assert(state != State:M);
 283       TBEs[addr].TBEState := state;
 284     }
 285
 286     if (isCacheTagPresent(addr)) {
 287       // Make sure the token count is in range
 288       assert(getCacheEntry(addr).Tokens >= 0);
 289       assert(getCacheEntry(addr).Tokens <= max_tokens());
 290
 291       if ((state == State:I_L) ||
 292           (state == State:IM_L) ||
 293           (state == State:IS_L)) {
 294         // Make sure we have no tokens in the "Invalid, locked" states
 295         if (isCacheTagPresent(addr)) {
 296           assert(getCacheEntry(addr).Tokens == 0);
 297         }
 298
 299         // Make sure the line is locked
 300         assert(persistentTable.isLocked(addr));
 301
 302         // But we shouldn't have highest priority for it
 303         assert(persistentTable.findSmallest(addr) != machineID);
 304
 305       } else if ((state == State:S_L) ||
 306                  (state == State:SM_L)) {
 307         // Make sure we have only one token in the "Shared, locked" states
 308         assert(getCacheEntry(addr).Tokens == 1);
 309
 310         // Make sure the line is locked...
 311         assert(persistentTable.isLocked(addr));
 312
 313         // ...But we shouldn't have highest priority for it...
 314         assert(persistentTable.findSmallest(addr) != machineID);
 315
 316         // ...And it must be a GETS request
 317         assert(persistentTable.typeOfSmallest(addr) == AccessType:Read);
 318
 319       } else {
 320
 321         // If there is an entry in the persistent table of this block,
 322         // this processor needs to have an entry in the table for this
 323         // block, and that entry better be the smallest (highest
 324         // priority).  Otherwise, the state should have been one of
 325         // locked states
 326
 327         if (persistentTable.isLocked(addr)) {
 328           assert(persistentTable.findSmallest(addr) == machineID);
 329         }
 330       }
 331
 332       // in M and E you have all the tokens
 333       if (state == State:MM || state == State:M || state == State:MM_W || state == State:M_W) {
 334         assert(getCacheEntry(addr).Tokens == max_tokens());
 335       }
 336
 337       // in NP you have no tokens
 338       if (state == State:NP) {
 339         assert(getCacheEntry(addr).Tokens == 0);
 340       }
 341
 342       // You have at least one token in S-like states
 343       if (state == State:S || state == State:SM) {
 344         assert(getCacheEntry(addr).Tokens > 0);
 345       }
 346
 347       // You have at least half the token in O-like states
 348       if (state == State:O && state == State:OM) {
 349         assert(getCacheEntry(addr).Tokens >= 1); // Must have at least one token
 350         assert(getCacheEntry(addr).Tokens >= (max_tokens() / 2)); // Only mostly true; this might not always hold
 351       }
 352
 353       getCacheEntry(addr).CacheState := state;
 354
 355       // Set permission
 356       if (state == State:MM ||
 357           state == State:MM_W) {
 358         changePermission(addr, AccessPermission:Read_Write);
 359       } else if ((state == State:S) ||
 360                  (state == State:O) ||
 361                  (state == State:M) ||
 362                  (state == State:M_W) ||
 363                  (state == State:SM) ||
 364                  (state == State:SM_L) ||
 365                  (state == State:OM)) {
 366         changePermission(addr, AccessPermission:Read_Only);
 367       } else {
 368         changePermission(addr, AccessPermission:Invalid);
 369       }
 370     }
 371   }
 372
 373   Event mandatory_request_type_to_event(CacheRequestType type) {
 374     if (type == CacheRequestType:LD) {
 375       return Event:Load;
 376     } else if (type == CacheRequestType:IFETCH) {
 377       return Event:Ifetch;
 378     } else if ((type == CacheRequestType:ST) || (type == CacheRequestType:ATOMIC)) {
 379       return Event:Store;
 380     } else {
 381       error("Invalid CacheRequestType");
 382     }
 383   }
 384
 385   AccessType cache_request_type_to_access_type(CacheRequestType type) {
 386     if ((type == CacheRequestType:LD) || (type == CacheRequestType:IFETCH)) {
 387       return AccessType:Read;
 388     } else if ((type == CacheRequestType:ST) || (type == CacheRequestType:ATOMIC)) {
 389       return AccessType:Write;
 390     } else {
 391       error("Invalid CacheRequestType");
 392     }
 393   }
 394
 395   // ** OUT_PORTS **
 396   out_port(persistentNetwork_out, PersistentMsg, persistentFromCache);
 397   out_port(requestNetwork_out, RequestMsg, requestFromCache);
 398   out_port(responseNetwork_out, ResponseMsg, responseFromCache);
 399
 400   // ** IN_PORTS **
 401
 402   // Use Timer
 403   in_port(useTimerTable_in, Address, useTimerTable) {
 404     if (useTimerTable_in.isReady()) {
 405       trigger(Event:Use_Timeout, useTimerTable.readyAddress());
 406     }
 407   }
 408
 409   // Reissue Timer
 410   in_port(reissueTimerTable_in, Address, reissueTimerTable) {
 411     if (reissueTimerTable_in.isReady()) {
 412       trigger(Event:Request_Timeout, reissueTimerTable.readyAddress());
 413     }
 414   }
 415
 416   // Persistent Network
 417   in_port(persistentNetwork_in, PersistentMsg, persistentToCache) {
 418     if (persistentNetwork_in.isReady()) {
 419       peek(persistentNetwork_in, PersistentMsg) {
 420
 421         // Apply the lockdown or unlockdown message to the table
 422         if (in_msg.Type == PersistentRequestType:GETX_PERSISTENT) {
 423           persistentTable.persistentRequestLock(in_msg.Address, in_msg.Requestor, AccessType:Write);
 424         } else if (in_msg.Type == PersistentRequestType:GETS_PERSISTENT) {
 425           persistentTable.persistentRequestLock(in_msg.Address, in_msg.Requestor, AccessType:Read);
 426         } else if (in_msg.Type == PersistentRequestType:DEACTIVATE_PERSISTENT) {
 427           persistentTable.persistentRequestUnlock(in_msg.Address, in_msg.Requestor);
 428         } else {
 429           error("Unexpected message");
 430         }
 431
 432         // React to the message based on the current state of the table
 433         if (persistentTable.isLocked(in_msg.Address)) {
 434           if (persistentTable.findSmallest(in_msg.Address) == machineID) {
 435             // Our Own Lock - this processor is highest priority
 436             trigger(Event:Own_Lock_or_Unlock, in_msg.Address);
 437           } else {
 438             if (persistentTable.typeOfSmallest(in_msg.Address) == AccessType:Read) {
 439               trigger(Event:Persistent_GETS, in_msg.Address);
 440             } else {
 441               trigger(Event:Persistent_GETX, in_msg.Address);
 442             }
 443           }
 444         } else {
 445           // Unlock case - no entries in the table
 446           trigger(Event:Own_Lock_or_Unlock, in_msg.Address);
 447         }
 448       }
 449     }
 450   }
 451
 452
 453   // Request Network
 454   in_port(requestNetwork_in, RequestMsg, requestToCache) {
 455     if (requestNetwork_in.isReady()) {
 456       peek(requestNetwork_in, RequestMsg) {
 457         if (in_msg.Type == CoherenceRequestType:GETX) {
 458           trigger(Event:Transient_GETX, in_msg.Address);
 459         } else if (in_msg.Type == CoherenceRequestType:GETS) {
 460           trigger(Event:Transient_GETS, in_msg.Address);
 461         } else {
 462           error("Unexpected message");
 463         }
 464       }
 465     }
 466   }
 467
 468   // Response Network
 469   in_port(responseNetwork_in, ResponseMsg, responseToCache) {
 470     if (responseNetwork_in.isReady()) {
 471       peek(responseNetwork_in, ResponseMsg) {
 472
 473         if (getTokens(in_msg.Address) + in_msg.Tokens != max_tokens()) {
 474           if (in_msg.Type == CoherenceResponseType:ACK) {
 475             trigger(Event:Ack, in_msg.Address);
 476           } else if (in_msg.Type == CoherenceResponseType:DATA_OWNER) {
 477             trigger(Event:Data_Owner, in_msg.Address);
 478           } else if (in_msg.Type == CoherenceResponseType:DATA_SHARED) {
 479             trigger(Event:Data_Shared, in_msg.Address);
 480           } else {
 481             error("Unexpected message");
 482           }
 483         } else {
 484           if (in_msg.Type == CoherenceResponseType:ACK) {
 485             trigger(Event:Ack_All_Tokens, in_msg.Address);
 486           } else if (in_msg.Type == CoherenceResponseType:DATA_OWNER) {
 487             trigger(Event:Data_Owner_All_Tokens, in_msg.Address);
 488           } else if (in_msg.Type == CoherenceResponseType:DATA_SHARED) {
 489             trigger(Event:Data_Shared_All_Tokens, in_msg.Address);
 490           } else {
 491             error("Unexpected message");
 492           }
 493         }
 494       }
 495     }
 496   }
 497
 498   // Mandatory Queue
 499   in_port(mandatoryQueue_in, CacheMsg, mandatoryQueue, desc="...") {
 500     if (mandatoryQueue_in.isReady()) {
 501       peek(mandatoryQueue_in, CacheMsg) {
 502         // Check for data access to blocks in I-cache and ifetchs to blocks in D-cache
 503
 504         if (in_msg.Type == CacheRequestType:IFETCH) {
 505           // ** INSTRUCTION ACCESS ***
 506
 507           // Check to see if it is in the OTHER L1
 508           if (L1DcacheMemory.isTagPresent(in_msg.Address)) {
 509             // The block is in the wrong L1, try to write it to the L2
 510             if (L2cacheMemory.cacheAvail(in_msg.Address)) {
 511               trigger(Event:L1_to_L2, in_msg.Address);
 512             } else {
 513               trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(in_msg.Address));
 514             }
 515           }
 516
 517           if (L1IcacheMemory.isTagPresent(in_msg.Address)) {
 518             // The tag matches for the L1, so the L1 fetches the line.  We know it can't be in the L2 due to exclusion
 519             trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 520           } else {
 521             if (L1IcacheMemory.cacheAvail(in_msg.Address)) {
 522               // L1 does't have the line, but we have space for it in the L1
 523               if (L2cacheMemory.isTagPresent(in_msg.Address)) {
 524                 // L2 has it (maybe not with the right permissions)
 525                 trigger(Event:L2_to_L1I, in_msg.Address);
 526               } else {
 527                 // We have room, the L2 doesn't have it, so the L1 fetches the line
 528                 trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 529               }
 530             } else {
 531               // No room in the L1, so we need to make room
 532               if (L2cacheMemory.cacheAvail(L1IcacheMemory.cacheProbe(in_msg.Address))) {
 533                 // The L2 has room, so we move the line from the L1 to the L2
 534                 trigger(Event:L1_to_L2, L1IcacheMemory.cacheProbe(in_msg.Address));
 535               } else {
 536                 // The L2 does not have room, so we replace a line from the L2
 537                 trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(L1IcacheMemory.cacheProbe(in_msg.Address)));
 538               }
 539             }
 540           }
 541         } else {
 542           // *** DATA ACCESS ***
 543
 544             // Check to see if it is in the OTHER L1
 545           if (L1IcacheMemory.isTagPresent(in_msg.Address)) {
 546             // The block is in the wrong L1, try to write it to the L2
 547             if (L2cacheMemory.cacheAvail(in_msg.Address)) {
 548               trigger(Event:L1_to_L2, in_msg.Address);
 549             } else {
 550               trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(in_msg.Address));
 551             }
 552           }
 553
 554           if (L1DcacheMemory.isTagPresent(in_msg.Address)) {
 555             // The tag matches for the L1, so the L1 fetches the line.  We know it can't be in the L2 due to exclusion
 556             trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 557           } else {
 558             if (L1DcacheMemory.cacheAvail(in_msg.Address)) {
 559               // L1 does't have the line, but we have space for it in the L1
 560               if (L2cacheMemory.isTagPresent(in_msg.Address)) {
 561                 // L2 has it (maybe not with the right permissions)
 562                 trigger(Event:L2_to_L1D, in_msg.Address);
 563               } else {
 564                 // We have room, the L2 doesn't have it, so the L1 fetches the line
 565                 trigger(mandatory_request_type_to_event(in_msg.Type), in_msg.Address);
 566               }
 567             } else {
 568               // No room in the L1, so we need to make room
 569               if (L2cacheMemory.cacheAvail(L1DcacheMemory.cacheProbe(in_msg.Address))) {
 570                 // The L2 has room, so we move the line from the L1 to the L2
 571                 trigger(Event:L1_to_L2, L1DcacheMemory.cacheProbe(in_msg.Address));
 572               } else {
 573                 // The L2 does not have room, so we replace a line from the L2
 574                 trigger(Event:L2_Replacement, L2cacheMemory.cacheProbe(L1DcacheMemory.cacheProbe(in_msg.Address)));
 575               }
 576             }
 577           }
 578         }
 579       }
 580     }
 581   }
 582
 583   // ACTIONS
 584
 585   action(a_issueRequest, "a", desc="Issue GETS or GETX request (transient or persistent)") {
 586
 587     if (TBEs[address].IssueCount == 0) {
 588       // Update outstanding requests
 589       profile_outstanding_request(outstandingRequests);
 590       outstandingRequests := outstandingRequests + 1;
 591     }
 592
 593     if (TBEs[address].IssueCount < getRetryThreshold()) {
 594       // Issue a normal request
 595       enqueue(requestNetwork_out, RequestMsg, latency="ISSUE_LATENCY") {
 596         out_msg.Address := address;
 597         out_msg.Requestor := machineID;
 598         out_msg.Destination.broadcast(MachineType:L1Cache);
 599         out_msg.Destination.add(map_Address_to_Directory(address));
 600
 601         if (TBEs[address].AccessType == AccessType:Read) {
 602           out_msg.Type := CoherenceRequestType:GETS;
 603         } else {
 604           out_msg.Type := CoherenceRequestType:GETX;
 605         }
 606
 607         if (TBEs[address].IssueCount == 0) {
 608           out_msg.MessageSize := MessageSizeType:Request_Control;
 609         } else {
 610           out_msg.MessageSize := MessageSizeType:Reissue_Control;
 611         }
 612       }
 613
 614       // Increment IssueCount
 615       TBEs[address].IssueCount := TBEs[address].IssueCount + 1;
 616
 617       // Set a wakeup timer
 618       reissueTimerTable.set(address, 2*averageLatencyEstimate());
 619
 620     } else {
 621       // Try to issue a Persistent Request
 622       if (persistentTable.okToIssueStarving(address)) {
 623         // Issue a persistent request
 624         enqueue(persistentNetwork_out, PersistentMsg, latency="ISSUE_LATENCY") {
 625           out_msg.Address := address;
 626           if (TBEs[address].AccessType == AccessType:Read) {
 627             out_msg.Type := PersistentRequestType:GETS_PERSISTENT;
 628           } else {
 629             out_msg.Type := PersistentRequestType:GETX_PERSISTENT;
 630           }
 631           out_msg.Requestor := machineID;
 632           out_msg.Destination.broadcast(MachineType:L1Cache);
 633           out_msg.Destination.add(map_Address_to_Directory(address));
 634           out_msg.MessageSize := MessageSizeType:Persistent_Control;
 635         }
 636         persistentTable.markEntries(address);
 637
 638         // Update outstanding requests
 639         profile_outstanding_persistent_request(outstandingPersistentRequests);
 640         outstandingPersistentRequests := outstandingPersistentRequests + 1;
 641
 642         // Increment IssueCount
 643         TBEs[address].IssueCount := TBEs[address].IssueCount + 1;
 644
 645         // Do not schedule a wakeup, a persistent requests will always complete
 646
 647       } else {
 648         // We'd like to issue a persistent request, but are not allowed
 649         // to issue a P.R. right now.  This, we do not increment the
 650         // IssueCount.
 651
 652
 653         // Set a wakeup timer
 654         reissueTimerTable.set(address, 10);
 655       }
 656     }
 657   }
 658
 659   action(b_bounceResponse, "b", desc="Bounce tokens and data to memory") {
 660     peek(responseNetwork_in, ResponseMsg) {
 661       // FIXME, should use a 3rd vnet
 662       enqueue(responseNetwork_out, ResponseMsg, latency="NULL_LATENCY") {
 663         out_msg.Address := address;
 664         out_msg.Type := in_msg.Type;
 665         out_msg.Sender := machineID;
 666         out_msg.SenderMachine := MachineType:L1Cache;
 667         out_msg.Destination.add(map_Address_to_Directory(address));
 668         out_msg.DestMachine := MachineType:Directory;
 669         out_msg.Tokens := in_msg.Tokens;
 670         out_msg.MessageSize := in_msg.MessageSize;
 671         out_msg.DataBlk := in_msg.DataBlk;
 672         out_msg.Dirty := in_msg.Dirty;
 673       }
 674     }
 675   }
 676
 677   action(c_cleanReplacement, "c", desc="Issue clean writeback") {
 678     if (getCacheEntry(address).Tokens > 0) {
 679       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 680         out_msg.Address := address;
 681         out_msg.Type := CoherenceResponseType:ACK;
 682         out_msg.Sender := machineID;
 683         out_msg.SenderMachine := MachineType:L1Cache;
 684         out_msg.Destination.add(map_Address_to_Directory(address));
 685         out_msg.DestMachine := MachineType:Directory;
 686         out_msg.Tokens := getCacheEntry(address).Tokens;
 687         out_msg.Dirty := false;
 688         out_msg.MessageSize := MessageSizeType:Writeback_Control;
 689       }
 690       getCacheEntry(address).Tokens := 0;
 691     }
 692   }
 693
 694   action(cc_dirtyReplacement, "\c", desc="Issue dirty writeback") {
 695     enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 696       out_msg.Address := address;
 697       out_msg.Sender := machineID;
 698       out_msg.SenderMachine := MachineType:L1Cache;
 699       out_msg.Destination.add(map_Address_to_Directory(address));
 700       out_msg.DestMachine := MachineType:Directory;
 701       out_msg.Tokens := getCacheEntry(address).Tokens;
 702       out_msg.Dirty := getCacheEntry(address).Dirty;
 703       if (getCacheEntry(address).Dirty) {
 704         out_msg.Type := CoherenceResponseType:DATA_OWNER;
 705         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 706         out_msg.MessageSize := MessageSizeType:Writeback_Data;
 707       } else {
 708         out_msg.Type := CoherenceResponseType:ACK_OWNER;
 709         // NOTE: in a real system this would not send data.  We send
 710         // data here only so we can check it at the memory
 711         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 712         out_msg.MessageSize := MessageSizeType:Writeback_Control;
 713       }
 714     }
 715     getCacheEntry(address).Tokens := 0;
 716   }
 717
 718   action(d_sendDataWithToken, "d", desc="Send data and a token from cache to requestor") {
 719     peek(requestNetwork_in, RequestMsg) {
 720       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 721         out_msg.Address := address;
 722         out_msg.Type := CoherenceResponseType:DATA_SHARED;
 723         out_msg.Sender := machineID;
 724         out_msg.SenderMachine := MachineType:L1Cache;
 725         out_msg.Destination.add(in_msg.Requestor);
 726         out_msg.DestMachine := MachineType:L1Cache;
 727         out_msg.Tokens := 1;
 728         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 729         out_msg.Dirty := getCacheEntry(address).Dirty;
 730         out_msg.MessageSize := MessageSizeType:Response_Data;
 731       }
 732     }
 733     getCacheEntry(address).Tokens := getCacheEntry(address).Tokens - 1;
 734     assert(getCacheEntry(address).Tokens >= 1);
 735   }
 736
 737   action(dd_sendDataWithAllTokens, "\d", desc="Send data and all tokens from cache to requestor") {
 738     peek(requestNetwork_in, RequestMsg) {
 739       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 740         out_msg.Address := address;
 741         out_msg.Type := CoherenceResponseType:DATA_OWNER;
 742         out_msg.Sender := machineID;
 743         out_msg.SenderMachine := MachineType:L1Cache;
 744         out_msg.Destination.add(in_msg.Requestor);
 745         out_msg.DestMachine := MachineType:L1Cache;
 746         assert(getCacheEntry(address).Tokens >= 1);
 747         out_msg.Tokens := getCacheEntry(address).Tokens;
 748         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 749         out_msg.Dirty := getCacheEntry(address).Dirty;
 750         out_msg.MessageSize := MessageSizeType:Response_Data;
 751       }
 752     }
 753     getCacheEntry(address).Tokens := 0;
 754   }
 755
 756   action(e_sendAckWithCollectedTokens, "e", desc="Send ack with the tokens we've collected thus far.") {
 757     assert(persistentTable.findSmallest(address) != machineID); // Make sure we never bounce tokens to ourself
 758     if (getCacheEntry(address).Tokens > 0) {
 759       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 760         out_msg.Address := address;
 761         out_msg.Type := CoherenceResponseType:ACK;
 762         out_msg.Sender := machineID;
 763         out_msg.SenderMachine := MachineType:L1Cache;
 764         out_msg.Destination.add(persistentTable.findSmallest(address));
 765         out_msg.DestMachine := MachineType:L1Cache;
 766         assert(getCacheEntry(address).Tokens >= 1);
 767         out_msg.Tokens := getCacheEntry(address).Tokens;
 768         out_msg.MessageSize := MessageSizeType:Response_Control;
 769       }
 770     }
 771     getCacheEntry(address).Tokens := 0;
 772   }
 773
 774   action(ee_sendDataWithAllTokens, "\e", desc="Send data and all tokens from cache to starver") {
 775     assert(persistentTable.findSmallest(address) != machineID); // Make sure we never bounce tokens to ourself
 776     assert(getCacheEntry(address).Tokens > 0);
 777     enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 778       out_msg.Address := address;
 779       out_msg.Type := CoherenceResponseType:DATA_OWNER;
 780       out_msg.Sender := machineID;
 781       out_msg.SenderMachine := MachineType:L1Cache;
 782       out_msg.Destination.add(persistentTable.findSmallest(address));
 783       out_msg.DestMachine := MachineType:L1Cache;
 784       assert(getCacheEntry(address).Tokens >= 1);
 785       out_msg.Tokens := getCacheEntry(address).Tokens;
 786       out_msg.DataBlk := getCacheEntry(address).DataBlk;
 787       out_msg.Dirty := getCacheEntry(address).Dirty;
 788       out_msg.MessageSize := MessageSizeType:Response_Data;
 789     }
 790     getCacheEntry(address).Tokens := 0;
 791   }
 792
 793   action(f_sendAckWithAllButOneTokens, "f", desc="Send ack with all our tokens but one to starver.") {
 794     assert(persistentTable.findSmallest(address) != machineID); // Make sure we never bounce tokens to ourself
 795     assert(getCacheEntry(address).Tokens > 0);
 796     if (getCacheEntry(address).Tokens > 1) {
 797       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 798         out_msg.Address := address;
 799         out_msg.Type := CoherenceResponseType:ACK;
 800         out_msg.Sender := machineID;
 801         out_msg.SenderMachine := MachineType:L1Cache;
 802         out_msg.Destination.add(persistentTable.findSmallest(address));
 803         out_msg.DestMachine := MachineType:L1Cache;
 804         assert(getCacheEntry(address).Tokens >= 1);
 805         out_msg.Tokens := getCacheEntry(address).Tokens - 1;
 806         out_msg.MessageSize := MessageSizeType:Response_Control;
 807       }
 808     }
 809     getCacheEntry(address).Tokens := 1;
 810   }
 811
 812   action(ff_sendDataWithAllButOneTokens, "\f", desc="Send data and out tokens but one to starver") {
 813     assert(persistentTable.findSmallest(address) != machineID); // Make sure we never bounce tokens to ourself
 814     assert(getCacheEntry(address).Tokens > 0);
 815     if (getCacheEntry(address).Tokens > 1) {
 816       enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 817         out_msg.Address := address;
 818         out_msg.Type := CoherenceResponseType:DATA_OWNER;
 819         out_msg.Sender := machineID;
 820         out_msg.SenderMachine := MachineType:L1Cache;
 821         out_msg.Destination.add(persistentTable.findSmallest(address));
 822         out_msg.DestMachine := MachineType:L1Cache;
 823         assert(getCacheEntry(address).Tokens >= 1);
 824         out_msg.Tokens := getCacheEntry(address).Tokens - 1;
 825         out_msg.DataBlk := getCacheEntry(address).DataBlk;
 826         out_msg.Dirty := getCacheEntry(address).Dirty;
 827         out_msg.MessageSize := MessageSizeType:Response_Data;
 828       }
 829       getCacheEntry(address).Tokens := 1;
 830     }
 831   }
 832
 833   action(g_bounceResponseToStarver, "g", desc="Redirect response to starving processor") {
 834     assert(persistentTable.isLocked(address));
 835     peek(responseNetwork_in, ResponseMsg) {
 836       assert(persistentTable.findSmallest(address) != machineID); // Make sure we never bounce tokens to ourself
 837       // FIXME, should use a 3rd vnet in some cases
 838       enqueue(responseNetwork_out, ResponseMsg, latency="NULL_LATENCY") {
 839         out_msg.Address := address;
 840         out_msg.Type := in_msg.Type;
 841         out_msg.Sender := machineID;
 842         out_msg.SenderMachine := MachineType:L1Cache;
 843         out_msg.Destination.add(persistentTable.findSmallest(address));
 844         out_msg.DestMachine := MachineType:L1Cache;
 845         out_msg.Tokens := in_msg.Tokens;
 846         out_msg.DataBlk := in_msg.DataBlk;
 847         out_msg.Dirty := in_msg.Dirty;
 848         out_msg.MessageSize := in_msg.MessageSize;
 849       }
 850     }
 851   }
 852
 853   action(h_load_hit, "h", desc="Notify sequencer the load completed.") {
 854     DEBUG_EXPR(getCacheEntry(address).DataBlk);
 855     sequencer.readCallback(address, getCacheEntry(address).DataBlk);
 856   }
 857
 858   action(hh_store_hit, "\h", desc="Notify sequencer that store completed.") {
 859     DEBUG_EXPR(getCacheEntry(address).DataBlk);
 860     sequencer.writeCallback(address, getCacheEntry(address).DataBlk);
 861     getCacheEntry(address).Dirty := true;
 862   }
 863
 864   action(i_allocateTBE, "i", desc="Allocate TBE") {
 865     check_allocate(TBEs);
 866     TBEs.allocate(address);
 867     TBEs[address].IssueCount := 0;
 868     peek(mandatoryQueue_in, CacheMsg) {
 869       TBEs[address].PC := in_msg.ProgramCounter;
 870       TBEs[address].AccessType := cache_request_type_to_access_type(in_msg.Type);
 871     }
 872     TBEs[address].IssueTime := get_time();
 873   }
 874
 875   action(j_unsetReissueTimer, "j", desc="Unset reissue timer.") {
 876     if (reissueTimerTable.isSet(address)) {
 877       reissueTimerTable.unset(address);
 878     }
 879   }
 880
 881   action(jj_unsetUseTimer, "\j", desc="Unset use timer.") {
 882     useTimerTable.unset(address);
 883   }
 884
 885   action(k_popMandatoryQueue, "k", desc="Pop mandatory queue.") {
 886     mandatoryQueue_in.dequeue();
 887   }
 888
 889   action(l_popPersistentQueue, "l", desc="Pop persistent queue.") {
 890     persistentNetwork_in.dequeue();
 891   }
 892
 893   action(m_popRequestQueue, "m", desc="Pop request queue.") {
 894     requestNetwork_in.dequeue();
 895   }
 896
 897   action(n_popResponseQueue, "n", desc="Pop response queue") {
 898     responseNetwork_in.dequeue();
 899   }
 900
 901   action(o_scheduleUseTimeout, "o", desc="Schedule a use timeout.") {
 902     useTimerTable.set(address, 15);
 903   }
 904
 905   action(q_updateTokensFromResponse, "q", desc="Update the token count based on the incoming response message") {
 906     peek(responseNetwork_in, ResponseMsg) {
 907       assert(in_msg.Tokens != 0);
 908       getCacheEntry(address).Tokens := getCacheEntry(address).Tokens + in_msg.Tokens;
 909     }
 910   }
 911
 912   action(s_deallocateTBE, "s", desc="Deallocate TBE") {
 913     outstandingRequests := outstandingRequests - 1;
 914     if (TBEs[address].IssueCount > getRetryThreshold()) {
 915       outstandingPersistentRequests := outstandingPersistentRequests - 1;
 916       enqueue(persistentNetwork_out, PersistentMsg, latency="ISSUE_LATENCY") {
 917         out_msg.Address := address;
 918         out_msg.Type := PersistentRequestType:DEACTIVATE_PERSISTENT;
 919         out_msg.Requestor := machineID;
 920         out_msg.Destination.broadcast(MachineType:L1Cache);
 921         out_msg.Destination.add(map_Address_to_Directory(address));
 922         out_msg.MessageSize := MessageSizeType:Persistent_Control;
 923       }
 924     }
 925
 926     // Update average latency
 927     updateAverageLatencyEstimate(time_to_int(get_time()) - time_to_int(TBEs[address].IssueTime));
 928
 929     // Profile
 930     profile_token_retry(address, TBEs[address].AccessType, TBEs[address].IssueCount);
 931     TBEs.deallocate(address);
 932   }
 933
 934   action(t_sendAckWithCollectedTokens, "t", desc="Send ack with the tokens we've collected thus far.") {
 935     if (getCacheEntry(address).Tokens > 0) {
 936       peek(requestNetwork_in, RequestMsg) {
 937         enqueue(responseNetwork_out, ResponseMsg, latency="CACHE_RESPONSE_LATENCY") {
 938           out_msg.Address := address;
 939           out_msg.Type := CoherenceResponseType:ACK;
 940           out_msg.Sender := machineID;
 941           out_msg.SenderMachine := MachineType:L1Cache;
 942           out_msg.Destination.add(in_msg.Requestor);
 943           out_msg.DestMachine := MachineType:L1Cache;
 944           assert(getCacheEntry(address).Tokens >= 1);
 945           out_msg.Tokens := getCacheEntry(address).Tokens;
 946           out_msg.MessageSize := MessageSizeType:Response_Control;
 947         }
 948       }
 949     }
 950     getCacheEntry(address).Tokens := 0;
 951   }
 952
 953   action(u_writeDataToCache, "u", desc="Write data to cache") {
 954     peek(responseNetwork_in, ResponseMsg) {
 955       getCacheEntry(address).DataBlk := in_msg.DataBlk;
 956       getCacheEntry(address).Dirty := in_msg.Dirty;
 957     }
 958   }
 959
 960   action(gg_deallocateL1CacheBlock, "\g", desc="Deallocate cache block.  Sets the cache to invalid, allowing a replacement in parallel with a fetch.") {
 961     if (L1DcacheMemory.isTagPresent(address)) {
 962       L1DcacheMemory.deallocate(address);
 963     } else {
 964       L1IcacheMemory.deallocate(address);
 965     }
 966   }
 967
 968   action(ii_allocateL1DCacheBlock, "\i", desc="Set L1 D-cache tag equal to tag of block B.") {
 969     if (L1DcacheMemory.isTagPresent(address) == false) {
 970       L1DcacheMemory.allocate(address);
 971     }
 972   }
 973
 974   action(pp_allocateL1ICacheBlock, "\p", desc="Set L1 I-cache tag equal to tag of block B.") {
 975     if (L1IcacheMemory.isTagPresent(address) == false) {
 976       L1IcacheMemory.allocate(address);
 977     }
 978   }
 979
 980   action(vv_allocateL2CacheBlock, "\v", desc="Set L2 cache tag equal to tag of block B.") {
 981     L2cacheMemory.allocate(address);
 982   }
 983
 984   action(rr_deallocateL2CacheBlock, "\r", desc="Deallocate L2 cache block.  Sets the cache to not present, allowing a replacement in parallel with a fetch.") {
 985     L2cacheMemory.deallocate(address);
 986   }
 987
 988   action(ss_copyFromL1toL2, "\s", desc="Copy data block from L1 (I or D) to L2") {
 989     if (L1DcacheMemory.isTagPresent(address)) {
 990       L2cacheMemory[address] := L1DcacheMemory[address];
 991     } else {
 992       L2cacheMemory[address] := L1IcacheMemory[address];
 993     }
 994   }
 995
 996   action(tt_copyFromL2toL1, "\t", desc="Copy data block from L2 to L1 (I or D)") {
 997     if (L1DcacheMemory.isTagPresent(address)) {
 998       L1DcacheMemory[address] := L2cacheMemory[address];
 999     } else {
1000       L1IcacheMemory[address] := L2cacheMemory[address];
1001     }
1002   }
1003
1004   action(uu_profileMiss, "\u", desc="Profile the demand miss") {
1005     peek(mandatoryQueue_in, CacheMsg) {
1006       profile_miss(in_msg, id);
1007     }
1008   }
1009
1010   action(w_assertIncomingDataAndCacheDataMatch, "w", desc="Assert that the incoming data and the data in the cache match") {
1011     peek(responseNetwork_in, ResponseMsg) {
1012       assert(getCacheEntry(address).DataBlk == in_msg.DataBlk);
1013     }
1014   }
1015
1016   //  action(z_stall, "z", desc="Stall") {
1017   //  }
1018
1019   action(zz_recycleMandatoryQueue, "\z", desc="Send the head of the mandatory queue to the back of the queue.") {
1020     mandatoryQueue_in.recycle();
1021   }
1022
1023   //*****************************************************
1024   // TRANSITIONS
1025   //*****************************************************
1026
1027   // Transitions for Load/Store/L2_Replacement from transient states
1028   transition({IM, SM, OM, IS, IM_L, IS_L, I_L, S_L, SM_L, M_W, MM_W}, L2_Replacement) {
1029     zz_recycleMandatoryQueue;
1030   }
1031
1032   transition({IM, SM, OM, IS, IM_L, IS_L, SM_L}, Store) {
1033     zz_recycleMandatoryQueue;
1034   }
1035
1036   transition({IM, IS, IM_L, IS_L}, {Load, Ifetch}) {
1037     zz_recycleMandatoryQueue;
1038   }
1039
1040   transition({IM, SM, OM, IS, I_L, IM_L, IS_L, S_L, SM_L}, {L1_to_L2, L2_to_L1D, L2_to_L1I}) {
1041     zz_recycleMandatoryQueue;
1042   }
1043
1044   // Transitions moving data between the L1 and L2 caches
1045   transition({I, S, O, M, MM, M_W, MM_W}, L1_to_L2) {
1046     vv_allocateL2CacheBlock;
1047     ss_copyFromL1toL2;
1048     gg_deallocateL1CacheBlock;
1049   }
1050
1051   transition({I, S, O, M, MM, M_W, MM_W}, L2_to_L1D) {
1052     ii_allocateL1DCacheBlock;
1053     tt_copyFromL2toL1;
1054     rr_deallocateL2CacheBlock;
1055   }
1056
1057   transition({I, S, O, M, MM, M_W, MM_W}, L2_to_L1I) {
1058     pp_allocateL1ICacheBlock;
1059     tt_copyFromL2toL1;
1060     rr_deallocateL2CacheBlock;
1061   }
1062
1063   // Locks
1064   transition({NP, I, S, O, M, MM, M_W, MM_W, IM, SM, OM, IS}, Own_Lock_or_Unlock) {
1065     l_popPersistentQueue;
1066   }
1067
1068   // Transitions from NP
1069   transition(NP, Load, IS) {
1070     ii_allocateL1DCacheBlock;
1071     i_allocateTBE;
1072     a_issueRequest;
1073     uu_profileMiss;
1074     k_popMandatoryQueue;
1075   }
1076
1077   transition(NP, Ifetch, IS) {
1078     pp_allocateL1ICacheBlock;
1079     i_allocateTBE;
1080     a_issueRequest;
1081     uu_profileMiss;
1082     k_popMandatoryQueue;
1083   }
1084
1085   transition(NP, Store, IM) {
1086     ii_allocateL1DCacheBlock;
1087     i_allocateTBE;
1088     a_issueRequest;
1089     uu_profileMiss;
1090     k_popMandatoryQueue;
1091   }
1092
1093   transition(NP, {Ack, Data_Shared, Data_Owner, Data_Owner_All_Tokens}) {
1094     b_bounceResponse;
1095     n_popResponseQueue;
1096   }
1097
1098   transition(NP, {Transient_GETX, Transient_GETS}) {
1099     m_popRequestQueue;
1100   }
1101
1102   transition(NP, {Persistent_GETX, Persistent_GETS}, I_L) {
1103     l_popPersistentQueue;
1104   }
1105
1106   // Transitions from Idle
1107   transition(I, Load, IS) {
1108     i_allocateTBE;
1109     a_issueRequest;
1110     uu_profileMiss;
1111     k_popMandatoryQueue;
1112   }
1113
1114   transition(I, Ifetch, IS) {
1115     i_allocateTBE;
1116     a_issueRequest;
1117     uu_profileMiss;
1118     k_popMandatoryQueue;
1119   }
1120
1121   transition(I, Store, IM) {
1122     i_allocateTBE;
1123     a_issueRequest;
1124     uu_profileMiss;
1125     k_popMandatoryQueue;
1126   }
1127
1128   transition(I, L2_Replacement) {
1129     c_cleanReplacement; // Only needed in some cases
1130     rr_deallocateL2CacheBlock;
1131   }
1132
1133   transition(I, Transient_GETX) {
1134     t_sendAckWithCollectedTokens;
1135     m_popRequestQueue;
1136   }
1137
1138   transition(I, Transient_GETS) {
1139     m_popRequestQueue;
1140   }
1141
1142   transition(I, {Persistent_GETX, Persistent_GETS}, I_L) {
1143     e_sendAckWithCollectedTokens;
1144     l_popPersistentQueue;
1145   }
1146
1147   transition(I_L, {Persistent_GETX, Persistent_GETS}) {
1148     l_popPersistentQueue;
1149   }
1150
1151   transition(I, Ack) {
1152     q_updateTokensFromResponse;
1153     n_popResponseQueue;
1154   }
1155
1156   transition(I, Data_Shared, S) {
1157     u_writeDataToCache;
1158     q_updateTokensFromResponse;
1159     n_popResponseQueue;
1160   }
1161
1162   transition(I, Data_Owner, O) {
1163     u_writeDataToCache;
1164     q_updateTokensFromResponse;
1165     n_popResponseQueue;
1166   }
1167
1168   transition(I, Data_Owner_All_Tokens, M) {
1169     u_writeDataToCache;
1170     q_updateTokensFromResponse;
1171     n_popResponseQueue;
1172   }
1173
1174   // Transitions from Shared
1175   transition({S, SM, S_L, SM_L}, {Load, Ifetch}) {
1176     h_load_hit;
1177     k_popMandatoryQueue;
1178   }
1179
1180   transition(S, Store, SM) {
1181     i_allocateTBE;
1182     a_issueRequest;
1183     uu_profileMiss;
1184     k_popMandatoryQueue;
1185   }
1186
1187   transition(S, L2_Replacement, I) {
1188     c_cleanReplacement;
1189     rr_deallocateL2CacheBlock;
1190   }
1191
1192   transition(S, Transient_GETX, I) {
1193     t_sendAckWithCollectedTokens;
1194     m_popRequestQueue;
1195   }
1196
1197   transition(S, Transient_GETS) {
1198     m_popRequestQueue;
1199   }
1200
1201   transition({S, S_L}, Persistent_GETX, I_L) {
1202     e_sendAckWithCollectedTokens;
1203     l_popPersistentQueue;
1204   }
1205
1206   transition(S, Persistent_GETS, S_L) {
1207     f_sendAckWithAllButOneTokens;
1208     l_popPersistentQueue;
1209   }
1210
1211   transition(S_L, Persistent_GETS) {
1212     l_popPersistentQueue;
1213   }
1214
1215   transition(S, Ack) {
1216     q_updateTokensFromResponse;
1217     n_popResponseQueue;
1218   }
1219
1220   transition(S, Data_Shared) {
1221     w_assertIncomingDataAndCacheDataMatch;
1222     q_updateTokensFromResponse;
1223     n_popResponseQueue;
1224   }
1225
1226   transition(S, Data_Owner, O) {
1227     w_assertIncomingDataAndCacheDataMatch;
1228     q_updateTokensFromResponse;
1229     n_popResponseQueue;
1230   }
1231
1232   transition(S, Data_Owner_All_Tokens, M) {
1233     w_assertIncomingDataAndCacheDataMatch;
1234     q_updateTokensFromResponse;
1235     n_popResponseQueue;
1236   }
1237
1238   // Transitions from Owned
1239   transition({O, OM}, {Load, Ifetch}) {
1240     h_load_hit;
1241     k_popMandatoryQueue;
1242   }
1243
1244   transition(O, Store, OM) {
1245     i_allocateTBE;
1246     a_issueRequest;
1247     uu_profileMiss;
1248     k_popMandatoryQueue;
1249   }
1250
1251   transition(O, L2_Replacement, I) {
1252     cc_dirtyReplacement;
1253     rr_deallocateL2CacheBlock;
1254   }
1255
1256   transition(O, Transient_GETX, I) {
1257     dd_sendDataWithAllTokens;
1258     m_popRequestQueue;
1259   }
1260
1261   transition(O, Persistent_GETX, I_L) {
1262     ee_sendDataWithAllTokens;
1263     l_popPersistentQueue;
1264   }
1265
1266   transition(O, Persistent_GETS, S_L) {
1267     ff_sendDataWithAllButOneTokens;
1268     l_popPersistentQueue;
1269   }
1270
1271   transition(O, Transient_GETS) {
1272     d_sendDataWithToken;
1273     m_popRequestQueue;
1274   }
1275
1276   transition(O, Ack) {
1277     q_updateTokensFromResponse;
1278     n_popResponseQueue;
1279   }
1280
1281   transition(O, Ack_All_Tokens, M) {
1282     q_updateTokensFromResponse;
1283     n_popResponseQueue;
1284   }
1285
1286   transition(O, Data_Shared) {
1287     w_assertIncomingDataAndCacheDataMatch;
1288     q_updateTokensFromResponse;
1289     n_popResponseQueue;
1290   }
1291
1292   transition(O, Data_Shared_All_Tokens, M) {
1293     w_assertIncomingDataAndCacheDataMatch;
1294     q_updateTokensFromResponse;
1295     n_popResponseQueue;
1296   }
1297
1298   // Transitions from Modified
1299   transition({MM, MM_W}, {Load, Ifetch}) {
1300     h_load_hit;
1301     k_popMandatoryQueue;
1302   }
1303
1304   transition({MM, MM_W}, Store) {
1305     hh_store_hit;
1306     k_popMandatoryQueue;
1307   }
1308
1309   transition(MM, L2_Replacement, I) {
1310     cc_dirtyReplacement;
1311     rr_deallocateL2CacheBlock;
1312   }
1313
1314   transition(MM, {Transient_GETX, Transient_GETS}, I) {
1315     dd_sendDataWithAllTokens;
1316     m_popRequestQueue;
1317   }
1318
1319   transition(MM_W, {Transient_GETX, Transient_GETS}) { // Ignore the request
1320     m_popRequestQueue;
1321   }
1322
1323   // Implement the migratory sharing optimization, even for persistent requests
1324   transition(MM, {Persistent_GETX, Persistent_GETS}, I_L) {
1325     ee_sendDataWithAllTokens;
1326     l_popPersistentQueue;
1327   }
1328
1329   // Implement the migratory sharing optimization, even for persistent requests
1330   transition(MM_W, {Persistent_GETX, Persistent_GETS}, I_L) {
1331     s_deallocateTBE;
1332     ee_sendDataWithAllTokens;
1333     jj_unsetUseTimer;
1334     l_popPersistentQueue;
1335   }
1336
1337   transition(MM_W, Use_Timeout, MM) {
1338     s_deallocateTBE;
1339     jj_unsetUseTimer;
1340   }
1341
1342   // Transitions from Dirty Exclusive
1343   transition({M, M_W}, {Load, Ifetch}) {
1344     h_load_hit;
1345     k_popMandatoryQueue;
1346   }
1347
1348   transition(M, Store, MM) {
1349     hh_store_hit;
1350     k_popMandatoryQueue;
1351   }
1352
1353   transition(M_W, Store, MM_W) {
1354     hh_store_hit;
1355     k_popMandatoryQueue;
1356   }
1357
1358   transition(M, L2_Replacement, I) {
1359     cc_dirtyReplacement;
1360     rr_deallocateL2CacheBlock;
1361   }
1362
1363   transition(M, Transient_GETX, I) {
1364     dd_sendDataWithAllTokens;
1365     m_popRequestQueue;
1366   }
1367
1368   transition(M, Transient_GETS, O) {
1369     d_sendDataWithToken;
1370     m_popRequestQueue;
1371   }
1372
1373   transition(M_W,{Transient_GETX, Transient_GETS}) { // Ignore the request
1374     m_popRequestQueue;
1375   }
1376
1377   transition(M, Persistent_GETX, I_L) {
1378     ee_sendDataWithAllTokens;
1379     l_popPersistentQueue;
1380   }
1381
1382   transition(M, Persistent_GETS, S_L) {
1383     ff_sendDataWithAllButOneTokens;
1384     l_popPersistentQueue;
1385   }
1386
1387   transition(M_W, Persistent_GETX, I_L) {
1388     s_deallocateTBE;
1389     ee_sendDataWithAllTokens;
1390     jj_unsetUseTimer;
1391     l_popPersistentQueue;
1392   }
1393
1394   transition(M_W, Persistent_GETS, S_L) {
1395     s_deallocateTBE;
1396     ff_sendDataWithAllButOneTokens;
1397     jj_unsetUseTimer;
1398     l_popPersistentQueue;
1399   }
1400
1401   transition(M_W, Use_Timeout, M) {
1402     s_deallocateTBE;
1403     jj_unsetUseTimer;
1404   }
1405
1406   // Transient_GETX and Transient_GETS in transient states
1407   transition(OM, {Transient_GETX, Transient_GETS}) {
1408     m_popRequestQueue;  // Even if we have the data, we can pretend we don't have it yet.
1409   }
1410
1411   transition(IS, Transient_GETX) {
1412     t_sendAckWithCollectedTokens;
1413     m_popRequestQueue;
1414   }
1415
1416   transition(IS, Transient_GETS) {
1417     m_popRequestQueue;
1418   }
1419
1420   transition(IS, {Persistent_GETX, Persistent_GETS}, IS_L) {
1421     e_sendAckWithCollectedTokens;
1422     l_popPersistentQueue;
1423   }
1424
1425   transition(IS_L, {Persistent_GETX, Persistent_GETS}) {
1426     l_popPersistentQueue;
1427   }
1428
1429   transition(IM, {Persistent_GETX, Persistent_GETS}, IM_L) {
1430     e_sendAckWithCollectedTokens;
1431     l_popPersistentQueue;
1432   }
1433
1434   transition(IM_L, {Persistent_GETX, Persistent_GETS}) {
1435     l_popPersistentQueue;
1436   }
1437
1438   transition({SM, SM_L}, Persistent_GETX, IM_L) {
1439     e_sendAckWithCollectedTokens;
1440     l_popPersistentQueue;
1441   }
1442
1443   transition(SM, Persistent_GETS, SM_L) {
1444     f_sendAckWithAllButOneTokens;
1445     l_popPersistentQueue;
1446   }
1447
1448   transition(SM_L, Persistent_GETS) {
1449     l_popPersistentQueue;
1450   }
1451
1452   transition(OM, Persistent_GETX, IM_L) {
1453     ee_sendDataWithAllTokens;
1454     l_popPersistentQueue;
1455   }
1456
1457   transition(OM, Persistent_GETS, SM_L) {
1458     ff_sendDataWithAllButOneTokens;
1459     l_popPersistentQueue;
1460   }
1461
1462   // Transitions from IM/SM
1463
1464   transition({IM, SM}, Ack) {
1465     q_updateTokensFromResponse;
1466     n_popResponseQueue;
1467   }
1468
1469   transition(IM, Data_Shared, SM) {
1470     u_writeDataToCache;
1471     q_updateTokensFromResponse;
1472     n_popResponseQueue;
1473   }
1474
1475   transition(IM, Data_Owner, OM) {
1476     u_writeDataToCache;
1477     q_updateTokensFromResponse;
1478     n_popResponseQueue;
1479   }
1480
1481   transition(IM, Data_Owner_All_Tokens, MM_W) {
1482     u_writeDataToCache;
1483     q_updateTokensFromResponse;
1484     hh_store_hit;
1485     o_scheduleUseTimeout;
1486     j_unsetReissueTimer;
1487     n_popResponseQueue;
1488   }
1489
1490   transition(SM, Data_Shared) {
1491     w_assertIncomingDataAndCacheDataMatch;
1492     q_updateTokensFromResponse;
1493     n_popResponseQueue;
1494   }
1495
1496   transition(SM, Data_Owner, OM) {
1497     w_assertIncomingDataAndCacheDataMatch;
1498     q_updateTokensFromResponse;
1499     n_popResponseQueue;
1500   }
1501
1502   transition(SM, Data_Owner_All_Tokens, MM_W) {
1503     w_assertIncomingDataAndCacheDataMatch;
1504     q_updateTokensFromResponse;
1505     hh_store_hit;
1506     o_scheduleUseTimeout;
1507     j_unsetReissueTimer;
1508     n_popResponseQueue;
1509   }
1510
1511   transition({IM, SM}, Transient_GETX, IM) {
1512     t_sendAckWithCollectedTokens;
1513     m_popRequestQueue;
1514   }
1515
1516   transition({IM, SM}, Transient_GETS) {
1517     m_popRequestQueue;
1518   }
1519
1520   transition({IM, SM}, Request_Timeout) {
1521     j_unsetReissueTimer;
1522     a_issueRequest;
1523   }
1524
1525   // Transitions from OM
1526
1527   transition(OM, Ack) {
1528     q_updateTokensFromResponse;
1529     n_popResponseQueue;
1530   }
1531
1532   transition(OM, Ack_All_Tokens, MM_W) {
1533     q_updateTokensFromResponse;
1534     hh_store_hit;
1535     o_scheduleUseTimeout;
1536     j_unsetReissueTimer;
1537     n_popResponseQueue;
1538   }
1539
1540   transition(OM, Data_Shared) {
1541     w_assertIncomingDataAndCacheDataMatch;
1542     q_updateTokensFromResponse;
1543     n_popResponseQueue;
1544   }
1545
1546   transition(OM, Data_Shared_All_Tokens, MM_W) {
1547     w_assertIncomingDataAndCacheDataMatch;
1548     q_updateTokensFromResponse;
1549     hh_store_hit;
1550     o_scheduleUseTimeout;
1551     j_unsetReissueTimer;
1552     n_popResponseQueue;
1553   }
1554
1555   transition(OM, Request_Timeout) {
1556     j_unsetReissueTimer;
1557     a_issueRequest;
1558   }
1559
1560   // Transitions from IS
1561
1562   transition(IS, Ack) {
1563     q_updateTokensFromResponse;
1564     n_popResponseQueue;
1565   }
1566
1567   transition(IS, Data_Shared, S) {
1568     u_writeDataToCache;
1569     q_updateTokensFromResponse;
1570     h_load_hit;
1571     s_deallocateTBE;
1572     j_unsetReissueTimer;
1573     n_popResponseQueue;
1574   }
1575
1576   transition(IS, Data_Owner, O) {
1577     u_writeDataToCache;
1578     q_updateTokensFromResponse;
1579     h_load_hit;
1580     s_deallocateTBE;
1581     j_unsetReissueTimer;
1582     n_popResponseQueue;
1583   }
1584
1585   transition(IS, Data_Owner_All_Tokens, M_W) {
1586     u_writeDataToCache;
1587     q_updateTokensFromResponse;
1588     h_load_hit;
1589     o_scheduleUseTimeout;
1590     j_unsetReissueTimer;
1591     n_popResponseQueue;
1592   }
1593
1594   transition(IS, Request_Timeout) {
1595     j_unsetReissueTimer;
1596     a_issueRequest;
1597   }
1598
1599   // Transitions from I_L
1600
1601   transition(I_L, Load, IS_L) {
1602     ii_allocateL1DCacheBlock;
1603     i_allocateTBE;
1604     a_issueRequest;
1605     uu_profileMiss;
1606     k_popMandatoryQueue;
1607   }
1608
1609   transition(I_L, Ifetch, IS_L) {
1610     pp_allocateL1ICacheBlock;
1611     i_allocateTBE;
1612     a_issueRequest;
1613     uu_profileMiss;
1614     k_popMandatoryQueue;
1615   }
1616
1617   transition(I_L, Store, IM_L) {
1618     ii_allocateL1DCacheBlock;
1619     i_allocateTBE;
1620     a_issueRequest;
1621     uu_profileMiss;
1622     k_popMandatoryQueue;
1623   }
1624
1625
1626   // Transitions from S_L
1627
1628   transition(S_L, Store, SM_L) {
1629     i_allocateTBE;
1630     a_issueRequest;
1631     uu_profileMiss;
1632     k_popMandatoryQueue;
1633   }
1634
1635   // Other transitions from *_L states
1636
1637   transition({I_L, IM_L, IS_L, S_L, SM_L}, {Transient_GETS, Transient_GETX}) {
1638     m_popRequestQueue;
1639   }
1640
1641   transition({I_L, IM_L, IS_L, S_L, SM_L}, Ack) {
1642     g_bounceResponseToStarver;
1643     n_popResponseQueue;
1644   }
1645
1646   transition({I_L, IM_L, S_L, SM_L}, {Data_Shared, Data_Owner}) {
1647     g_bounceResponseToStarver;
1648     n_popResponseQueue;
1649   }
1650
1651   transition({I_L, S_L}, Data_Owner_All_Tokens) {
1652     g_bounceResponseToStarver;
1653     n_popResponseQueue;
1654   }
1655
1656   transition(IS_L, Request_Timeout) {
1657     j_unsetReissueTimer;
1658     a_issueRequest;
1659   }
1660
1661   transition({IM_L, SM_L}, Request_Timeout) {
1662     j_unsetReissueTimer;
1663     a_issueRequest;
1664   }
1665
1666   // Opportunisticly Complete the memory operation in the following
1667   // cases.  Note: these transitions could just use
1668   // g_bounceResponseToStarver, but if we have the data and tokens, we
1669   // might as well complete the memory request while we have the
1670   // chance (and then immediately forward on the data)
1671
1672   transition(IM_L, Data_Owner_All_Tokens, I_L) {
1673     u_writeDataToCache;
1674     q_updateTokensFromResponse;
1675     hh_store_hit;
1676     ee_sendDataWithAllTokens;
1677     s_deallocateTBE;
1678     j_unsetReissueTimer;
1679     n_popResponseQueue;
1680   }
1681
1682   transition(SM_L, Data_Owner_All_Tokens, S_L) {
1683     u_writeDataToCache;
1684     q_updateTokensFromResponse;
1685     hh_store_hit;
1686     ff_sendDataWithAllButOneTokens;
1687     s_deallocateTBE;
1688     j_unsetReissueTimer;
1689     n_popResponseQueue;
1690   }
1691
1692   transition(IS_L, Data_Shared, I_L) {
1693     u_writeDataToCache;
1694     q_updateTokensFromResponse;
1695     h_load_hit;
1696     s_deallocateTBE;
1697     e_sendAckWithCollectedTokens;
1698     j_unsetReissueTimer;
1699     j_unsetReissueTimer;
1700     n_popResponseQueue;
1701   }
1702
1703   transition(IS_L, {Data_Owner, Data_Owner_All_Tokens}, I_L) {
1704     u_writeDataToCache;
1705     q_updateTokensFromResponse;
1706     h_load_hit;
1707     ee_sendDataWithAllTokens;
1708     s_deallocateTBE;
1709     j_unsetReissueTimer;
1710     n_popResponseQueue;
1711   }
1712
1713   // Own_Lock_or_Unlock
1714
1715   transition(I_L, Own_Lock_or_Unlock, I) {
1716     l_popPersistentQueue;
1717   }
1718
1719   transition(S_L, Own_Lock_or_Unlock, S) {
1720     l_popPersistentQueue;
1721   }
1722
1723   transition(IM_L, Own_Lock_or_Unlock, IM) {
1724     l_popPersistentQueue;
1725   }
1726
1727   transition(IS_L, Own_Lock_or_Unlock, IS) {
1728     l_popPersistentQueue;
1729   }
1730
1731   transition(SM_L, Own_Lock_or_Unlock, SM) {
1732     l_popPersistentQueue;
1733   }
1734 }