Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.55 KB | None | 0 0
  1. #ifndef CACHE_H
  2. #define CACHE_H
  3.  
  4. #include <iostream>  // std::cout ...
  5. #include <cstdlib>   // rand()
  6.  
  7. /*****************************************************************************/
  8. /* Policy about L2 inclusion of L1's content                                 */
  9. /*****************************************************************************/
  10. #ifndef L2_INCLUSIVE
  11. #  define L2_INCLUSIVE 1
  12. #endif
  13. /*****************************************************************************/
  14.  
  15.  
  16. /*****************************************************************************/
  17. /* Cache allocation strategy on stores                                       */
  18. /*****************************************************************************/
  19. enum {
  20.     STORE_ALLOCATE = 0,
  21.     STORE_NO_ALLOCATE
  22. };
  23. #ifndef STORE_ALLOCATION
  24. #  define STORE_ALLOCATION STORE_ALLOCATE
  25. #endif
  26. /*****************************************************************************/
  27.  
  28. typedef UINT64 CACHE_STATS; // type of cache hit/miss counters
  29.  
  30.  
  31. /**
  32.  * `CACHE_TAG` class represents an address tag stored in a cache.
  33.  * `INVALID_TAG` is used as an error on functions with CACHE_TAG return type.
  34.  **/
  35. class CACHE_TAG
  36. {
  37.   private:
  38.     ADDRINT _tag;
  39.  
  40.   public:
  41.     CACHE_TAG(ADDRINT tag = 0) { _tag = tag; }
  42.     bool operator==(const CACHE_TAG &right) const { return _tag == right._tag; }
  43.     operator ADDRINT() const { return _tag; }
  44. };
  45. CACHE_TAG INVALID_TAG(-1);
  46.  
  47.  
  48. /**
  49.  * Everything related to cache sets
  50.  **/
  51. namespace CACHE_SET
  52. {
  53.  
  54. class LRU
  55. {
  56.   protected:
  57.     std::vector<CACHE_TAG> _tags;
  58.     UINT32 _associativity;
  59.  
  60.  public:
  61.     LRU(UINT32 associativity = 8)
  62.     {
  63.         _associativity = associativity;
  64.         _tags.clear();
  65.     }
  66.  
  67.     VOID SetAssociativity(UINT32 associativity)
  68.     {
  69.         _associativity = associativity;
  70.         _tags.clear();
  71.     }
  72.     UINT32 GetAssociativity() { return _associativity; }
  73.  
  74.     string Name() { return "LRU"; }
  75.    
  76.     UINT32 Find(CACHE_TAG tag)
  77.     {
  78.         for (std::vector<CACHE_TAG>::iterator it = _tags.begin();
  79.              it != _tags.end(); ++it)
  80.         {
  81.             if (*it == tag) { // Tag found, lets make it MRU
  82.                 _tags.erase(it);
  83.                 _tags.push_back(tag);
  84.                 return true;
  85.             }
  86.         }
  87.  
  88.         return false;
  89.     }
  90.  
  91.     CACHE_TAG Replace(CACHE_TAG tag)
  92.     {
  93.         CACHE_TAG ret = INVALID_TAG;
  94.         _tags.push_back(tag);
  95.         if (_tags.size() > _associativity) {
  96.             ret = *_tags.begin();
  97.             _tags.erase(_tags.begin());
  98.         }
  99.         return ret;
  100.     }
  101.    
  102.     VOID DeleteIfPresent(CACHE_TAG tag)
  103.     {
  104.         for (std::vector<CACHE_TAG>::iterator it = _tags.begin();
  105.              it != _tags.end(); ++it)
  106.         {
  107.             if (*it == tag) { // Tag found
  108.                 _tags.erase(it);
  109.                 break;
  110.             }
  111.         }
  112.     }
  113. };
  114.  
  115. } // namespace CACHE_SET
  116.  
  117. template <class SET>
  118. class TWO_LEVEL_CACHE
  119. {
  120.   public:
  121.     typedef enum
  122.     {
  123.         ACCESS_TYPE_LOAD,
  124.         ACCESS_TYPE_STORE,
  125.         ACCESS_TYPE_NUM
  126.     } ACCESS_TYPE;
  127.  
  128.   private:
  129.     enum {
  130.         HIT_L1 = 0,
  131.         HIT_L2,
  132.         MISS_L2,
  133.         ACCESS_RESULT_NUM
  134.     };
  135.  
  136.     static const UINT32 HIT_MISS_NUM = 2;
  137.     CACHE_STATS _l1_access[ACCESS_TYPE_NUM][HIT_MISS_NUM];
  138.     CACHE_STATS _l2_access[ACCESS_TYPE_NUM][HIT_MISS_NUM];
  139.  
  140.     UINT32 _latencies[ACCESS_RESULT_NUM];
  141.  
  142.     SET *_l1_sets;
  143.     SET *_l2_sets;
  144.  
  145.     const std::string _name;
  146.     const UINT32 _l1_cacheSize;
  147.     const UINT32 _l2_cacheSize;
  148.     const UINT32 _l1_blockSize;
  149.     const UINT32 _l2_blockSize;
  150.     const UINT32 _l1_associativity;
  151.     const UINT32 _l2_associativity;
  152.  
  153.     // computed params
  154.     const UINT32 _l1_lineShift; // i.e., no of block offset bits
  155.     const UINT32 _l2_lineShift;
  156.     const UINT32 _l1_setIndexMask; // mask applied to get the set index
  157.     const UINT32 _l2_setIndexMask;
  158.  
  159.     // how many lines ahead to prefetch in L2 (0 disables prefetching)
  160.     const UINT32 _l2_prefetch_lines;
  161.  
  162.     CACHE_STATS L1SumAccess(bool hit) const
  163.     {
  164.         CACHE_STATS sum = 0;
  165.         for (UINT32 accessType = 0; accessType < ACCESS_TYPE_NUM; accessType++)
  166.             sum += _l1_access[accessType][hit];
  167.         return sum;
  168.     }
  169.     CACHE_STATS L2SumAccess(bool hit) const
  170.     {
  171.         CACHE_STATS sum = 0;
  172.         for (UINT32 accessType = 0; accessType < ACCESS_TYPE_NUM; accessType++)
  173.             sum += _l2_access[accessType][hit];
  174.         return sum;
  175.     }
  176.  
  177.     UINT32 L1NumSets() const { return _l1_setIndexMask + 1; }
  178.     UINT32 L2NumSets() const { return _l2_setIndexMask + 1; }
  179.  
  180.     // accessors
  181.     UINT32 L1CacheSize() const { return _l1_cacheSize; }
  182.     UINT32 L2CacheSize() const { return _l2_cacheSize; }
  183.     UINT32 L1BlockSize() const { return _l1_blockSize; }
  184.     UINT32 L2BlockSize() const { return _l2_blockSize; }
  185.     UINT32 L1Associativity() const { return _l1_associativity; }
  186.     UINT32 L2Associativity() const { return _l2_associativity; }
  187.     UINT32 L1LineShift() const { return _l1_lineShift; }
  188.     UINT32 L2LineShift() const { return _l2_lineShift; }
  189.     UINT32 L1SetIndexMask() const { return _l1_setIndexMask; }
  190.     UINT32 L2SetIndexMask() const { return _l2_setIndexMask; }
  191.  
  192.     VOID SplitAddress(const ADDRINT addr, UINT32 lineShift, UINT32 setIndexMask,
  193.                       CACHE_TAG & tag, UINT32 & setIndex) const
  194.     {
  195.         tag = addr >> lineShift;
  196.         setIndex = tag & setIndexMask;
  197.         tag = tag >> FloorLog2(setIndexMask + 1);
  198.     }
  199.  
  200.  
  201.   public:
  202.     // constructors/destructors
  203.     TWO_LEVEL_CACHE(std::string name,
  204.                 UINT32 l1CacheSize, UINT32 l1BlockSize, UINT32 l1Associativity,
  205.                 UINT32 l2CacheSize, UINT32 l2BlockSize, UINT32 l2Associativity,
  206.                 UINT32 l2PrefetchLines,
  207.                 UINT32 l1HitLatency = 1, UINT32 l2HitLatency = 10,
  208.                 UINT32 l2MissLatency = 150);
  209.  
  210.     // Stats
  211.     CACHE_STATS L1Hits(ACCESS_TYPE accessType) const { return _l1_access[accessType][true];}
  212.     CACHE_STATS L2Hits(ACCESS_TYPE accessType) const { return _l2_access[accessType][true];}
  213.     CACHE_STATS L1Misses(ACCESS_TYPE accessType) const { return _l1_access[accessType][false];}
  214.     CACHE_STATS L2Misses(ACCESS_TYPE accessType) const { return _l2_access[accessType][false];}
  215.     CACHE_STATS L1Accesses(ACCESS_TYPE accessType) const { return L1Hits(accessType) + L1Misses(accessType);}
  216.     CACHE_STATS L2Accesses(ACCESS_TYPE accessType) const { return L2Hits(accessType) + L2Misses(accessType);}
  217.     CACHE_STATS L1Hits() const { return L1SumAccess(true);}
  218.     CACHE_STATS L2Hits() const { return L2SumAccess(true);}
  219.     CACHE_STATS L1Misses() const { return L1SumAccess(false);}
  220.     CACHE_STATS L2Misses() const { return L2SumAccess(false);}
  221.     CACHE_STATS L1Accesses() const { return L1Hits() + L1Misses();}
  222.     CACHE_STATS L2Accesses() const { return L2Hits() + L2Misses();}
  223.  
  224.     string StatsLong(string prefix = "") const;
  225.     string PrintCache(string prefix = "") const;
  226.  
  227.     UINT32 Access(ADDRINT addr, ACCESS_TYPE accessType);
  228. };
  229.  
  230. template <class SET>
  231. TWO_LEVEL_CACHE<SET>::TWO_LEVEL_CACHE(
  232.                 std::string name,
  233.                 UINT32 l1CacheSize, UINT32 l1BlockSize, UINT32 l1Associativity,
  234.                 UINT32 l2CacheSize, UINT32 l2BlockSize, UINT32 l2Associativity,
  235.                 UINT32 l2PrefetchLines,
  236.                 UINT32 l1HitLatency, UINT32 l2HitLatency, UINT32 l2MissLatency)
  237.   : _name(name),
  238.     _l1_cacheSize(l1CacheSize),
  239.     _l2_cacheSize(l2CacheSize),
  240.     _l1_blockSize(l1BlockSize),
  241.     _l2_blockSize(l2BlockSize),
  242.     _l1_associativity(l1Associativity),
  243.     _l2_associativity(l2Associativity),
  244.     _l1_lineShift(FloorLog2(l1BlockSize)),
  245.     _l2_lineShift(FloorLog2(l2BlockSize)),
  246.     _l1_setIndexMask((l1CacheSize / (l1Associativity * l1BlockSize)) - 1),
  247.     _l2_setIndexMask((l2CacheSize / (l2Associativity * l2BlockSize)) - 1),
  248.     _l2_prefetch_lines(l2PrefetchLines)
  249. {
  250.  
  251.     // They all need to be power of 2
  252.     ASSERTX(IsPowerOf2(_l1_blockSize));
  253.     ASSERTX(IsPowerOf2(_l2_blockSize));
  254.     ASSERTX(IsPowerOf2(_l1_setIndexMask + 1));
  255.     ASSERTX(IsPowerOf2(_l2_setIndexMask + 1));
  256.  
  257.     // Some more sanity checks
  258.     ASSERTX(_l1_cacheSize <= _l2_cacheSize);
  259.     ASSERTX(_l1_blockSize <= _l2_blockSize);
  260.  
  261.     // Allocate space for L1 and L2 sets
  262.     _l1_sets = new SET[L1NumSets()];
  263.     _l2_sets = new SET[L2NumSets()];
  264.  
  265.     _latencies[HIT_L1] = l1HitLatency;
  266.     _latencies[HIT_L2] = l2HitLatency;
  267.     _latencies[MISS_L2] = l2MissLatency;
  268.  
  269.     for (UINT32 i = 0; i < L1NumSets(); i++)
  270.         _l1_sets[i].SetAssociativity(_l1_associativity);
  271.     for (UINT32 i = 0; i < L2NumSets(); i++)
  272.         _l2_sets[i].SetAssociativity(_l2_associativity);
  273.  
  274.     for (UINT32 accessType = 0; accessType < ACCESS_TYPE_NUM; accessType++)
  275.     {
  276.         _l1_access[accessType][false] = 0;
  277.         _l1_access[accessType][true] = 0;
  278.         _l2_access[accessType][false] = 0;
  279.         _l2_access[accessType][true] = 0;
  280.     }
  281. }
  282.  
  283. template <class SET>
  284. string TWO_LEVEL_CACHE<SET>::StatsLong(string prefix) const
  285. {
  286.     const UINT32 headerWidth = 19;
  287.     const UINT32 numberWidth = 12;
  288.  
  289.     string out;
  290.    
  291.     // L1 stats first
  292.     out += prefix + "L1 Cache Stats:" + "\n";
  293.  
  294.     for (UINT32 i = 0; i < ACCESS_TYPE_NUM; i++)
  295.     {
  296.         const ACCESS_TYPE accessType = ACCESS_TYPE(i);
  297.  
  298.         std::string type(accessType == ACCESS_TYPE_LOAD ? "L1-Load" : "L1-Store");
  299.  
  300.         out += prefix + ljstr(type + "-Hits:      ", headerWidth)
  301.                + dec2str(L1Hits(accessType), numberWidth)  +
  302.                "  " +fltstr(100.0 * L1Hits(accessType) / L1Accesses(accessType), 2, 6) + "%\n";
  303.  
  304.         out += prefix + ljstr(type + "-Misses:    ", headerWidth)
  305.                + dec2str(L1Misses(accessType), numberWidth) +
  306.                "  " +fltstr(100.0 * L1Misses(accessType) / L1Accesses(accessType), 2, 6) + "%\n";
  307.      
  308.         out += prefix + ljstr(type + "-Accesses:  ", headerWidth)
  309.                + dec2str(L1Accesses(accessType), numberWidth) +
  310.                "  " +fltstr(100.0 * L1Accesses(accessType) / L1Accesses(accessType), 2, 6) + "%\n";
  311.      
  312.         out += prefix + "\n";
  313.     }
  314.  
  315.     out += prefix + ljstr("L1-Total-Hits:      ", headerWidth)
  316.            + dec2str(L1Hits(), numberWidth) +
  317.            "  " +fltstr(100.0 * L1Hits() / L1Accesses(), 2, 6) + "%\n";
  318.  
  319.     out += prefix + ljstr("L1-Total-Misses:    ", headerWidth)
  320.            + dec2str(L1Misses(), numberWidth) +
  321.            "  " +fltstr(100.0 * L1Misses() / L1Accesses(), 2, 6) + "%\n";
  322.  
  323.     out += prefix + ljstr("L1-Total-Accesses:  ", headerWidth)
  324.            + dec2str(L1Accesses(), numberWidth) +
  325.            "  " +fltstr(100.0 * L1Accesses() / L1Accesses(), 2, 6) + "%\n";
  326.     out += "\n";
  327.  
  328.  
  329.     // L2 Stats now.
  330.     out += prefix + "L2 Cache Stats:" + "\n";
  331.  
  332.     for (UINT32 i = 0; i < ACCESS_TYPE_NUM; i++)
  333.     {
  334.         const ACCESS_TYPE accessType = ACCESS_TYPE(i);
  335.  
  336.         std::string type(accessType == ACCESS_TYPE_LOAD ? "L2-Load" : "L2-Store");
  337.  
  338.         out += prefix + ljstr(type + "-Hits:      ", headerWidth)
  339.                + dec2str(L2Hits(accessType), numberWidth)  +
  340.                "  " +fltstr(100.0 * L2Hits(accessType) / L2Accesses(accessType), 2, 6) + "%\n";
  341.  
  342.         out += prefix + ljstr(type + "-Misses:    ", headerWidth)
  343.                + dec2str(L2Misses(accessType), numberWidth) +
  344.                "  " +fltstr(100.0 * L2Misses(accessType) / L2Accesses(accessType), 2, 6) + "%\n";
  345.      
  346.         out += prefix + ljstr(type + "-Accesses:  ", headerWidth)
  347.                + dec2str(L2Accesses(accessType), numberWidth) +
  348.                "  " +fltstr(100.0 * L2Accesses(accessType) / L2Accesses(accessType), 2, 6) + "%\n";
  349.      
  350.         out += prefix + "\n";
  351.     }
  352.  
  353.     out += prefix + ljstr("L2-Total-Hits:      ", headerWidth)
  354.            + dec2str(L2Hits(), numberWidth) +
  355.            "  " +fltstr(100.0 * L2Hits() / L2Accesses(), 2, 6) + "%\n";
  356.  
  357.     out += prefix + ljstr("L2-Total-Misses:    ", headerWidth)
  358.            + dec2str(L2Misses(), numberWidth) +
  359.            "  " +fltstr(100.0 * L2Misses() / L2Accesses(), 2, 6) + "%\n";
  360.  
  361.     out += prefix + ljstr("L2-Total-Accesses:  ", headerWidth)
  362.            + dec2str(L2Accesses(), numberWidth) +
  363.            "  " +fltstr(100.0 * L2Accesses() / L2Accesses(), 2, 6) + "%\n";
  364.     out += prefix + "\n";
  365.  
  366.     return out;
  367. }
  368.  
  369. template <class SET>
  370. string TWO_LEVEL_CACHE<SET>::PrintCache(string prefix) const
  371. {
  372.     string out;
  373.  
  374.     out += prefix + "--------\n";
  375.     out += prefix + _name + "\n";
  376.     out += prefix + "--------\n";
  377.     out += prefix + "  L1-Data Cache:\n";
  378.     out += prefix + "    Size(KB):       " + dec2str(this->L1CacheSize()/KILO, 5) + "\n";
  379.     out += prefix + "    Block Size(B):  " + dec2str(this->L1BlockSize(), 5) + "\n";
  380.     out += prefix + "    Associativity:  " + dec2str(this->L1Associativity(), 5) + "\n";
  381.     out += prefix + "\n";
  382.     out += prefix + "  L2-Data Cache:\n";
  383.     out += prefix + "    Size(KB):       " + dec2str(this->L2CacheSize()/KILO, 5) + "\n";
  384.     out += prefix + "    Block Size(B):  " + dec2str(this->L2BlockSize(), 5) + "\n";
  385.     out += prefix + "    Associativity:  " + dec2str(this->L2Associativity(), 5) + "\n";
  386.     out += prefix + "\n";
  387.  
  388.     out += prefix + "Latencies: " + dec2str(_latencies[HIT_L1], 4) + " "
  389.                                   + dec2str(_latencies[HIT_L2], 4) + " "
  390.                                   + dec2str(_latencies[MISS_L2], 4) + "\n";
  391.     //out += prefix + "L1-Sets: " + this->_l1_sets[0].Name() + " assoc: " +
  392.     out += prefix + "L1-Sets: " + dec2str(this->L1NumSets(), 4) + " - " + this->_l1_sets[0].Name() + " - assoc: " +
  393.                           dec2str(this->_l1_sets[0].GetAssociativity(), 3) + "\n";
  394.     //out += prefix + "L2-Sets: " + this->_l2_sets[0].Name() + " assoc: " +
  395.     out += prefix + "L2-Sets: " + dec2str(this->L2NumSets(), 4) + " - " + this->_l2_sets[0].Name() + " - assoc: " +
  396.                           dec2str(this->_l2_sets[0].GetAssociativity(), 3) + "\n";
  397.     out += prefix + "Store_allocation: " + (STORE_ALLOCATION == STORE_ALLOCATE ? "Yes" : "No") + "\n";
  398.     out += prefix + "L2_inclusive: " + (L2_INCLUSIVE == 1 ? "Yes" : "No") + "\n";
  399.     out += prefix + "L2_prefetching: " + (_l2_prefetch_lines <= 0 ? "No" : "Yes (" + dec2str(_l2_prefetch_lines, 3) + ")") + "\n";
  400.     out += "\n";
  401.  
  402.     return out;
  403. }
  404.  
  405. // Returns the cycles to serve the request.
  406. template <class SET>
  407. UINT32 TWO_LEVEL_CACHE<SET>::Access(ADDRINT addr, ACCESS_TYPE accessType)
  408. {
  409.     CACHE_TAG l1Tag, l2Tag;
  410.     UINT32 l1SetIndex, l2SetIndex;
  411.     bool l1Hit = 0, l2Hit = 0;
  412.     UINT32 cycles = 0;
  413.  
  414.     // Let's check L1 first
  415.     SplitAddress(addr, L1LineShift(), L1SetIndexMask(), l1Tag, l1SetIndex);
  416.     SET & l1Set = _l1_sets[l1SetIndex];
  417.     l1Hit = l1Set.Find(l1Tag);
  418.     _l1_access[accessType][l1Hit]++;
  419.     cycles = _latencies[HIT_L1];
  420.  
  421.     if (!l1Hit) {
  422.         // On miss, loads always allocate, stores optionally
  423.         if (accessType == ACCESS_TYPE_LOAD ||
  424.             STORE_ALLOCATION == STORE_ALLOCATE)
  425.             l1Set.Replace(l1Tag);
  426.  
  427.         // Let's check L2 now
  428.         SplitAddress(addr, L2LineShift(), L2SetIndexMask(), l2Tag, l2SetIndex);
  429.         SET & l2Set = _l2_sets[l2SetIndex];
  430.         l2Hit = l2Set.Find(l2Tag);
  431.         _l2_access[accessType][l2Hit]++;
  432.         cycles += _latencies[HIT_L2];
  433.  
  434.         // L2 always allocates loads and stores
  435.         if (!l2Hit) {
  436.             CACHE_TAG l2_replaced = l2Set.Replace(l2Tag);
  437.             cycles += _latencies[MISS_L2];
  438.  
  439.             // If L2 is inclusive and a TAG has been replaced we need to remove
  440.             // all evicted blocks from L1.
  441.             if ((L2_INCLUSIVE == 1) && !(l2_replaced == INVALID_TAG)) {
  442.                 ADDRINT replacedAddr = ADDRINT(l2_replaced) << FloorLog2(L2NumSets());
  443.                 replacedAddr = replacedAddr | l2SetIndex;
  444.                 replacedAddr = replacedAddr << L2LineShift();
  445.                 for (UINT32 i=0; i < L2BlockSize(); i+=L1BlockSize()) {
  446.                     ADDRINT newAddr = replacedAddr | i;
  447.                     SplitAddress(newAddr, L1LineShift(), L1SetIndexMask(), l1Tag, l1SetIndex);
  448.                     l1Set = _l1_sets[l1SetIndex];
  449.                     l1Set.DeleteIfPresent(l1Tag);
  450.                 }
  451.             }
  452.             // PREFETCHING
  453.             ADDRINT prefetch_addr = addr;
  454.             for (UINT32 i=0; i < _l2_prefetch_lines; i++) {
  455.                 prefetch_addr += L2BlockSize();
  456.                 /* .......................... */
  457.                 /* Add here prefetching code. */
  458.                 /* .......................... */
  459.                  // Let's check L2 now
  460.                 SplitAddress(prefetch_addr, L2LineShift(), L2SetIndexMask(), l2Tag, l2SetIndex);
  461.                 SET & l2Set = _l2_sets[l2SetIndex];
  462.                 l2Hit = l2Set.Find(l2Tag);
  463.                 //_l2_access[accessType][l2Hit]++;//??????????????????????????
  464.                 if (!l2Hit){
  465.                     CACHE_TAG l2_replaced = l2Set.Replace(l2Tag);
  466.                    
  467.                     // If L2 is inclusive and a TAG has been replaced we need to remove
  468.                     // all evicted blocks from L1.
  469.                     if ((L2_INCLUSIVE == 1) && !(l2_replaced == INVALID_TAG)) {
  470.                         ADDRINT replacedAddr = ADDRINT(l2_replaced) << FloorLog2(L2NumSets());
  471.                         replacedAddr = replacedAddr | l2SetIndex;
  472.                         replacedAddr = replacedAddr << L2LineShift();
  473.                         for (UINT32 i=0; i < L2BlockSize(); i += L1BlockSize()) {
  474.                             ADDRINT newAddr = replacedAddr | i;
  475.                             SplitAddress(newAddr, L1LineShift(), L1SetIndexMask(), l1Tag, l1SetIndex);
  476.                             l1Set = _l1_sets[l1SetIndex];
  477.                             l1Set.DeleteIfPresent(l1Tag);
  478.                         }
  479.                     }
  480.                 }
  481.             }
  482.         }
  483.  
  484.     }
  485.  
  486.     return cycles;
  487. }
  488.  
  489. #endif // CACHE_H
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement