unused_please_ignore_completely/TLB/ariane/TreePLRU.cpp

   1 #include <cstdint>
   2 #include <iostream>
   3 #include <cmath>
   4
   5
   6 #define NWAY 4
   7 #define NLINE 256
   8 #define HIT 0
   9 #define MISS 1
  10 #define MS 1000
  11 /*
  12 Detailed TreePLRU inference see here: https://docs.google.com/spreadsheets/d/14zQpPYPwDAbCCjBT_a3KLaE5FEk-RNhI8Z7Qm_biW8g/edit?usp=sharing
  13 Ref: https://people.cs.clemson.edu/~mark/464/p_lru.txt
  14 four-way set associative - three bits
  15    each bit represents one branch point in a binary decision tree; let 1
  16    represent that the left side has been referenced more recently than the
  17    right side, and 0 vice-versa
  18               are all 4 lines valid?
  19                    /       \
  20                  yes        no, use an invalid line
  21                   |
  22                   |
  23                   |
  24              bit_0 == 0?            state | replace      ref to | next state
  25               /       \             ------+--------      -------+-----------
  26              y         n             00x  |  line_0      line_0 |    11_
  27             /           \            01x  |  line_1      line_1 |    10_
  28      bit_1 == 0?    bit_2 == 0?      1x0  |  line_2      line_2 |    0_1
  29        /    \          /    \        1x1  |  line_3      line_3 |    0_0
  30       y      n        y      n
  31      /        \      /        \        ('x' means       ('_' means unchanged)
  32    line_0  line_1  line_2  line_3      don't care)
  33  8-way set associative - 7  = 1+2+4 bits
  34 16-way set associative - 15 = 1+2+4+8 bits
  35 32-way set associative - 31 = 1+2+4+8+16 bits
  36 64-way set associative - 63 = 1+2+4+8+16+32 bits
  37 */
  38 using namespace std;
  39 struct AddressField {
  40     uint64_t wd_idx : 2;//Unused
  41     uint64_t offset : 4;//Unused
  42     uint64_t index  : 8;//NLINE = 256 = 2^8
  43     uint64_t tag    : 50;
  44 };
  45
  46 union Address {
  47     uint32_t* p;
  48     AddressField fields;
  49 };
  50
  51 struct Cell {
  52     bool v;
  53     uint64_t tag;
  54
  55     Cell() : v(false), tag(0) {}
  56
  57     bool isHit(uint64_t tag) {
  58         return v && (tag == this->tag);
  59     }
  60
  61     void fetch(uint32_t* address) {
  62         Address addr;
  63         addr.p = address;
  64         addr.fields.offset = 0;
  65         addr.fields.wd_idx = 0;
  66         tag = addr.fields.tag;
  67         v = true;
  68     }
  69 };
  70
  71 ostream& operator<<(ostream & out, const Cell& cell) {
  72     out << " v:" << cell.v << " tag:" << hex << cell.tag;
  73     return out;
  74 }
  75
  76 struct Block {
  77     Cell cell[NWAY];
  78     uint32_t state;
  79     uint64_t *mask;//Mask the state to get accurate value for specified 1 bit.
  80     uint64_t *value;
  81     uint64_t *next_value;
  82
  83     Block() : state(0) {
  84         switch (NWAY) {
  85             case 4:
  86                 mask = new uint64_t[4]{0b110, 0b110, 0b101, 0b101};
  87                 value = new uint64_t[4]{0b000, 0b010, 0b100, 0b101};
  88                 next_value = new uint64_t[4]{0b110, 0b100, 0b001, 0b000};
  89                 break;
  90             case 8:
  91                 mask = new uint64_t[8]{0b1101000, 0b1101000, 0b1100100, 0b1100100, 0b1010010, 0b1010010, 0b1010001,
  92                                        0b1010001};
  93                 value = new uint64_t[8]{0b0000000, 0b0001000, 0b0100000, 0b0100100, 0b1000000, 0b1000010, 0b1010000,
  94                                         0b1010001};
  95                 next_value = new uint64_t[8]{0b1101000, 0b1100000, 0b1000100, 0b1000000, 0b0010010, 0b0010000,
  96                                              0b0000001, 0b0000000};
  97                 break;
  98                 //TODO - more NWAY goes here.
  99             default:
 100                 std::cout << "Error definition NWAY = " << NWAY << std::endl;
 101         }
 102     }
 103
 104     uint32_t *getByTag(uint64_t tag, uint32_t *pway) {
 105         for (int i = 0; i < NWAY; ++i) {
 106             if (cell[i].isHit(tag)) {
 107                 *pway = i;
 108                 return pway;
 109             }
 110         }
 111         return NULL;
 112     }
 113
 114     void setLRU(uint32_t *address) {
 115         int way = 0;
 116         uint32_t st = state;
 117         for (int i = 0; i < NWAY; ++i) {
 118             if ((state & mask[i]) == value[i]) {
 119                 state ^= mask[i];
 120                 way = i;
 121                 break;
 122             }
 123         }
 124         cell[way].fetch(address);
 125         cout << "MISS: way:" << way << " address:" << address << " state:" << st << "->" << state << endl;
 126     }
 127
 128     uint32_t *get(uint32_t *address, uint32_t *pway) {
 129         Address addr;
 130         addr.p = address;
 131         uint32_t *d = getByTag(addr.fields.tag, pway);
 132         if (d != NULL) {
 133             return &d[addr.fields.offset];
 134         }
 135         return d;
 136     }
 137
 138     int set(uint32_t *address) {
 139         uint32_t way = 0;
 140         uint32_t *p = get(address, &way);
 141         if (p != NULL) {
 142             printf("HIT: address:%p ref_to way:%d state %X --> ", address, way, state);
 143             state &= ~mask[way];
 144             printf("%X --> ", state);
 145             state |= next_value[way];
 146             printf("%X\n", state);
 147             // *p = *address; //skip since address is fake.
 148             return HIT;
 149         } else {
 150             setLRU(address);
 151             return MISS;
 152         }
 153     }
 154 };
 155
 156 ostream& operator<<(ostream & out, const Block& block) {
 157     out << "state:" << block.state << " ";
 158     for (int i = 0; i<NWAY; i++) {
 159         out << block.cell[i];
 160     }
 161     return out;
 162 }
 163
 164 struct Cache {
 165     Block block[NLINE];
 166     uint32_t count[2];
 167     Cache() { count[HIT] = 0; count[MISS] = 0; }
 168
 169     void access(uint32_t* address) {
 170         Address addr;
 171         addr.p = address;
 172         Block& b = block[addr.fields.index];
 173         ++count[b.set(address)];
 174     }
 175
 176 };
 177 ostream& operator<<(ostream & out, const Cache& cache) {
 178     out << "\n==Summary==\n\tHit: " << cache.count[HIT] <<  " Miss: " << cache.count[MISS] << std::endl;
 179     for (int i = 0; i < NLINE; i++) {
 180         out << cache.block[i] << endl;
 181     }
 182     return out;
 183 }
 184
 185 Cache cache;
 186 void multiply(uint32_t* m1, uint32_t* m2, uint32_t* res)
 187 {
 188     int x, i, j;
 189     for (i = 0; i < MS; i++) {
 190         for (j = 0; j < MS; j++) {
 191             cache.access(res + i*MS +j);
 192             for (x = 0; x < MS; x++) {
 193                 cache.access(m1 + i*MS + x);
 194                 cache.access(m2 + x*MS + j);
 195                 cache.access(res + i*MS +j);
 196                 // res[i][j] += m1[i][x] * m2[x][j];
 197                 cache.access(res + i*MS +j);
 198             }
 199         }
 200     }
 201 }
 202
 203 int main()
 204 {
 205     uint32_t* m1 = (uint32_t*) 0xFACE00A000000000LL;  // fake virtual address; don’t access it
 206     uint32_t* m2 = (uint32_t*) 0xFACE00B000000000LL;  // fake virtual address; don’t access it
 207     uint32_t* res =  (uint32_t*) 0xFACE00C000000000LL; // fake virtual address; don’t access it
 208     multiply(m1, m2, res);
 209     cout << cache << endl;
 210     return 0;
 211 }