VerifyCacheModels.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Written by: Pradeep Sindhu, April 16, 1985 4:30:54 pm PST
Last Edited by: Pradeep Sindhu, May 2, 1985 1:09:14 pm PDT
Bertrand Serlet July 28, 1985 10:59:39 pm PDT
VerifyCacheModels:
CEDAR
PROGRAM
IMPORTS AssociativeCache, Convert, DragOpsCrossUtils, IO, Random, ViewerIO = {
vc: CacheModels.Cache;
in, out: IO.STREAM;
readProbes, writeProbes, readMisses, writeMisses, mapMisses, writesToCleanQuads: INT;
maxAddr: INT;
Cache Parameters:
cacheLines, cacheQuadsPerLine: INT;
cacheWordsPerQuad: INT ← 4;
cacheWordsPerPage: INT ← 1024;
probabilityOfRead: REAL = 0.6;
CreateAssociativeCache:
PROC [lines:
INT ← 256, quadsPerLine:
INT ← 2, wordsPerQuad:
INT ← 4, lru:
BOOL]
RETURNS [CacheModels.Cache] = {
cacheLines ← lines; cacheQuadsPerLine ← quadsPerLine; cacheWordsPerQuad ← wordsPerQuad;
vc ← AssociativeCache.NewCache[lines: lines, quadsPerLine: quadsPerLine, wordsPerQuad: wordsPerQuad, lru: lru];
RETURN[vc];
};
Init:
PROC [] = {
[] ← Random.Create[-1, 10173];
[in, out] ← ViewerIO.CreateViewerStreams [name: "VerifyCacheModels", editedStream: FALSE];
readProbes ← writeProbes ← readMisses ← writeMisses ← mapMisses ← writesToCleanQuads ← 0;
};
PrintExpected:
PROC [name: Rope.
ROPE, lines, quadsPerLine:
INT] = {
misses: INT ← readMisses+writeMisses;
probes: INT ← readProbes+writeProbes;
realProbes: REAL ← probes;
realMisses: REAL ← misses;
out.PutF["\nExpected Stats for %g (lines: %g, quads/line: %g)\n",
[rope[name]], [integer[lines]], [integer[quadsPerLine]]];
out.PutF[" probes: %g\n", [integer[probes]]];
out.PutF[
"read probes: %g, write probes: %g\n",
[integer[readProbes]], [integer[writeProbes]]];
out.PutF[
"write misses: %g, writes to clean quads: ??\n",
[integer[writeMisses]]];
out.PutF["misses: %g\n", [integer[misses]]];
IF probes # 0
THEN out.PutF[
"miss rate: %g%%\n",
[rope[Convert.RopeFromReal[(realMisses/realProbes)*100, 3]]]];
out.PutF["map misses: %g\n", [integer[mapMisses]]];
out.PutF["dirty writes: ??\n"]
};
Access:
PROC [addr:
INT, newAddr, forceRead:
BOOL ← FALSE] = {
quadMiss: BOOL ← newAddr AND (addr MOD cacheWordsPerQuad = 0);
mapMiss: BOOL ← quadMiss AND (addr MOD cacheWordsPerPage =0);
rand: INT ← Random.ChooseInt[min: 1, max: 100];
maxAddr ← addr;
IF (rand < probabilityOfRead*100)
OR forceRead
THEN {
-- read reference
vc.fetch[vc, DragOpsCrossUtils.IntToWord[addr]];
readProbes ← readProbes+1;
IF quadMiss THEN readMisses ← readMisses+1;
}
ELSE {
-- write reference
vc.store[vc, DragOpsCrossUtils.IntToWord[addr]];
writeProbes ← writeProbes+1;
IF quadMiss THEN writeMisses ← writeMisses+1;
};
IF mapMiss THEN mapMisses ← mapMisses+1;
};
This procedure generates a non-trivial pattern of references for which the miss statistics are known. Typically, addr points to an address that is guaranteed to get a miss. There is a window of addresses immediately before addr to which references are guaranteed to generate hits. References inside the window are done at random to keep the reference stream nontrivial.
RefPatternKnown:
PROC [n:
INT] = {
addr, tempAddr: INT ← 0;
quads: INT ← cacheLines*cacheQuadsPerLine;
window: INT ← MIN[quads*cacheWordsPerQuad, 64];
pHit: INT = 80;
vc.reset[vc];
Do enough references to fill the cache
THROUGH [1..quads] WHILE n > 0 DO
Access[addr, TRUE];
n ← n-1; addr ← addr+cacheWordsPerQuad;
ENDLOOP;
Now do the remaining references
WHILE n > 0 DO
IF Random.ChooseInt[min: 0, max: 100] < pHit
THEN {
-- cause a hit
tempAddr ← Random.ChooseInt[min: addr-window, max: addr-1];
Access[tempAddr, FALSE]; n ← n-1
}
ELSE {
-- cause a miss, but first reference all the words in the window in order
FOR tempAddr IN [addr-window..addr) DO Access[tempAddr, FALSE]; ENDLOOP;
Access[addr, TRUE];
n ← n-1; addr ← addr+1;
}
ENDLOOP;
};
This procedure generates references to the addresses [0, incr, 2.incr, .. n.incr)
RefPatternSerial:
PROC [n, incr:
INT] = {
addr: INT;
vc.reset[vc];
FOR addr
IN [0..n)
DO
Access[addr*incr, TRUE];
ENDLOOP;
};
This procedure generates a random reference pattern, always starting from the same seed (see Init). It's used to verify that succesive simulations of the same cache on the same data produce the same results.
RefPatternRand:
PROC [n:
INT] = {
addr: INT;
lo: INT ← 0;
hi: INT ← 10000;
vc.reset[vc];
THROUGH [0..n)
DO
addr ← Random.ChooseInt[min: lo, max: hi];
Access[addr, TRUE];
ENDLOOP;
};
PrintStats:
PROC [] = {
vc.print[vc, out, "Virtual Cache"];
PrintExpected["Virtual Cache", cacheLines, cacheQuadsPerLine];
};
}.