Skip to content

Instantly share code, notes, and snippets.

@nicklasfrahm

nicklasfrahm/hscod-exercise-cache-design.js

Last active March 30, 2020 10:18
Show Gist options
  • Save nicklasfrahm/6963ebe7455bd85f26830c426d34cc8d to your computer and use it in GitHub Desktop.
Save nicklasfrahm/6963ebe7455bd85f26830c426d34cc8d to your computer and use it in GitHub Desktop.
Download ZIP
HSCOD - Exercise - Cache Design
Raw
hscod-exercise-cache-design.js
const spacer = '--------------------------------------------------';
const decToBin = (dec, paddingCount = 8) =>
dec.toString(2).padStart(paddingCount, '0');
console.log(`${spacer}\nExercise 1\n${spacer}`);
{
const addressSize = 8;
const addressReferences = [3, 180, 43, 2, 191, 88, 190, 2, 88];
const indexes = {};
console.log('REF - BIN - TAG - INDEX - CACHE');
addressReferences.forEach(ref => {
const decStr = ref.toString().padStart(3, ' ');
const refStr = decToBin(ref, addressSize);
const index = decToBin(ref % 16, 4);
const tag = decToBin((ref & ~16) >> 4, 4);
const hit = indexes[index] === tag ? 'HIT' : 'MISS';
indexes[index] = tag;
console.log(`${decStr} - 0b${refStr} - 0b${tag} - 0b${index} - ${hit}`);
});
}
console.log(`${spacer}\nExercise 2\n${spacer}`);
{
const addressSize = 32;
const offsetLength = 5 - 0 + 1;
const indexLenth = 11 - 6 + 1;
const tagLength = 31 - 12 + 1;
const addressReferences = [
0,
4,
16,
132,
232,
160,
1024,
30,
140,
3100,
180,
2180
];
const indexes = {};
let hits = 0;
console.log(`ASSUMPTION: BLOCK OFFSET AND 8 BIT WORD SIZE`);
console.log(`A: CACHE LINE SIZE: ${2 ** offsetLength} WORDS`);
console.log(`B: CACHE BLOCK COUNT: ${2 ** indexLenth} BLOCKS`);
console.log(
'C: REF - BIN - TAG - INDEX - OFFSET - CACHE - START - END'
);
addressReferences.forEach(ref => {
const decStr = ref.toString().padStart(7, ' ');
const refStr = decToBin(ref, addressSize);
const offset = decToBin(ref % 64, offsetLength);
const index = decToBin((ref & (63 << 6)) >> 6, indexLenth);
const tag = decToBin((ref & (~63 << 6)) >> 6, tagLength);
const dataStart = ref & ~63;
const dataEnd = dataStart + 63;
const dataStartStr = dataStart.toString().padStart(5, ' ');
const dataEndStr = dataEnd.toString().padStart(5, ' ');
const hit = indexes[index] && indexes[index].tag === tag ? 'HIT ' : 'MISS';
if (hit.trim() === 'HIT') {
++hits;
}
indexes[index] = {
tag,
offset,
dataStart,
dataEnd
};
console.log(
`${decStr} - 0b${refStr} - 0b${tag} - 0b${index} - 0b${offset} - ${hit} - ${dataStartStr} - ${dataEndStr}`
);
});
console.log(` TOTAL HITS: ${hits}`);
console.log(
` HITRATE: ${Math.round((hits / addressReferences.length) * 100)}%`
);
}
@nicklasfrahm
Copy link
Author

nicklasfrahm commented Mar 23, 2020 •
edited
Loading

The result is:

--------------------------------------------------
Exercise 1
--------------------------------------------------
REF - BIN        - TAG    - INDEX  - CACHE
  3 - 0b00000011 - 0b0000 - 0b0011 - MISS
180 - 0b10110100 - 0b1010 - 0b0100 - MISS
 43 - 0b00101011 - 0b0010 - 0b1011 - MISS
  2 - 0b00000010 - 0b0000 - 0b0010 - MISS
191 - 0b10111111 - 0b1010 - 0b1111 - MISS
 88 - 0b01011000 - 0b0100 - 0b1000 - MISS
190 - 0b10111110 - 0b1010 - 0b1110 - MISS
  2 - 0b00000010 - 0b0000 - 0b0010 - HIT
 88 - 0b01011000 - 0b0100 - 0b1000 - HIT
--------------------------------------------------
Exercise 2
--------------------------------------------------
ASSUMPTION: BLOCK OFFSET AND 8 BIT WORD SIZE
A: CACHE LINE SIZE:   64 WORDS
B: CACHE BLOCK COUNT: 64 BLOCKS
C: REF  - BIN                                - TAG                    - INDEX    - OFFSET   - CACHE - START - END
      0 - 0b00000000000000000000000000000000 - 0b00000000000000000000 - 0b000000 - 0b000000 - MISS  -     0 -    63
      4 - 0b00000000000000000000000000000100 - 0b00000000000000000000 - 0b000000 - 0b000100 - HIT   -     0 -    63
     16 - 0b00000000000000000000000000010000 - 0b00000000000000000000 - 0b000000 - 0b010000 - HIT   -     0 -    63
    132 - 0b00000000000000000000000010000100 - 0b00000000000000000000 - 0b000010 - 0b000100 - MISS  -   128 -   191
    232 - 0b00000000000000000000000011101000 - 0b00000000000000000000 - 0b000011 - 0b101000 - MISS  -   192 -   255
    160 - 0b00000000000000000000000010100000 - 0b00000000000000000000 - 0b000010 - 0b100000 - HIT   -   128 -   191
   1024 - 0b00000000000000000000010000000000 - 0b00000000000000000000 - 0b010000 - 0b000000 - MISS  -  1024 -  1087
     30 - 0b00000000000000000000000000011110 - 0b00000000000000000000 - 0b000000 - 0b011110 - HIT   -     0 -    63
    140 - 0b00000000000000000000000010001100 - 0b00000000000000000000 - 0b000010 - 0b001100 - HIT   -   128 -   191
   3100 - 0b00000000000000000000110000011100 - 0b00000000000000000000 - 0b110000 - 0b011100 - MISS  -  3072 -  3135
    180 - 0b00000000000000000000000010110100 - 0b00000000000000000000 - 0b000010 - 0b110100 - HIT   -   128 -   191
   2180 - 0b00000000000000000000100010000100 - 0b00000000000000000000 - 0b100010 - 0b000100 - MISS  -  2176 -  2239
   TOTAL HITS: 6
   HITRATE:    50%

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment