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?
20 yes no, use an invalid line
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
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
40 uint64_t wd_idx
: 2;//Unused
41 uint64_t offset
: 4;//Unused
42 uint64_t index
: 8;//NLINE = 256 = 2^8
55 Cell() : v(false), tag(0) {}
57 bool isHit(uint64_t tag
) {
58 return v
&& (tag
== this->tag
);
61 void fetch(uint32_t* address
) {
64 addr
.fields
.offset
= 0;
65 addr
.fields
.wd_idx
= 0;
66 tag
= addr
.fields
.tag
;
71 ostream
& operator<<(ostream
& out
, const Cell
& cell
) {
72 out
<< " v:" << cell
.v
<< " tag:" << hex
<< cell
.tag
;
79 uint64_t *mask
;//Mask the state to get accurate value for specified 1 bit.
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};
91 mask
= new uint64_t[8]{0b1101000, 0b1101000, 0b1100100, 0b1100100, 0b1010010, 0b1010010, 0b1010001,
93 value
= new uint64_t[8]{0b0000000, 0b0001000, 0b0100000, 0b0100100, 0b1000000, 0b1000010, 0b1010000,
95 next_value
= new uint64_t[8]{0b1101000, 0b1100000, 0b1000100, 0b1000000, 0b0010010, 0b0010000,
96 0b0000001, 0b0000000};
98 //TODO - more NWAY goes here.
100 std::cout
<< "Error definition NWAY = " << NWAY
<< std::endl
;
104 uint32_t *getByTag(uint64_t tag
, uint32_t *pway
) {
105 for (int i
= 0; i
< NWAY
; ++i
) {
106 if (cell
[i
].isHit(tag
)) {
114 void setLRU(uint32_t *address
) {
117 for (int i
= 0; i
< NWAY
; ++i
) {
118 if ((state
& mask
[i
]) == value
[i
]) {
124 cell
[way
].fetch(address
);
125 cout
<< "MISS: way:" << way
<< " address:" << address
<< " state:" << st
<< "->" << state
<< endl
;
128 uint32_t *get(uint32_t *address
, uint32_t *pway
) {
131 uint32_t *d
= getByTag(addr
.fields
.tag
, pway
);
133 return &d
[addr
.fields
.offset
];
138 int set(uint32_t *address
) {
140 uint32_t *p
= get(address
, &way
);
142 printf("HIT: address:%p ref_to way:%d state %X --> ", address
, way
, state
);
144 printf("%X --> ", state
);
145 state
|= next_value
[way
];
146 printf("%X\n", state
);
147 // *p = *address; //skip since address is fake.
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
];
167 Cache() { count
[HIT
] = 0; count
[MISS
] = 0; }
169 void access(uint32_t* address
) {
172 Block
& b
= block
[addr
.fields
.index
];
173 ++count
[b
.set(address
)];
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
;
186 void multiply(uint32_t* m1
, uint32_t* m2
, uint32_t* res
)
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
);
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
;