DirectMapCacheImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Bertrand Serlet, October 17, 1985 4:22:04 pm PDT, stolen from CacheModelImpl.mesa
Last Edited by: Serlet, April 12, 1985 2:39:09 pm PST
Last Edited by: Barth, April 16, 1985 3:58:10 pm PST
Last Edited by: Sindhu, May 1, 1985 7:45:54 pm PDT
Pradeep Sindhu October 18, 1985 0:19:49 am PDT
DirectMapCacheImpl:
CEDAR
PROGRAM
IMPORTS Basics, Convert, DragOpsCrossUtils, IO
EXPORTS DirectMapCache
= BEGIN OPEN DragOpsCross, DragOpsCrossUtils;
Private types
Cache: TYPE = CacheModels.Cache;
wordsPerQuad: NAT = 4;
maxQuadsPerLine: NAT = 64;
maxLines: NAT = 16*1024;
wordsPerPage: CARDINAL = CacheModels.wordsPerPage;
QuadIndex: TYPE = [0..maxQuadsPerLine);
PageEntry: TYPE = REF PageEntryRep;
PageEntryRep:
TYPE =
RECORD [
next: PageEntry ← NIL,
pageAddr: Word ← ZerosWord,
useCount: INT ← 0
];
QuadBitVector:
TYPE =
PACKED
ARRAY QuadIndex
OF
BOOL;
None: QuadBitVector =
ALL[
FALSE];
HashEntry: TYPE = REF HashEntryRep;
HashEntryRep:
TYPE =
RECORD [
next: HashEntry ← NIL,
lineAddr: Word ← ZerosWord,
valid: BOOL ← FALSE,
chunkPresent: QuadBitVector ← None,
dirty: QuadBitVector ← None,
referenced: QuadBitVector ← None
];
CacheData: TYPE = REF CacheDataRep;
CacheDataRep:
TYPE =
RECORD [
stats: CacheStats ← [],
hashVector: HashVector ← NIL,
pageEntryCount: INT ← 0,
pageList: PageEntry ← NIL,
freePageList: PageEntry ← NIL,
victimIndex: CARDINAL ← 0,
rover: NAT ← 0,
quadsPerLine: NAT ← 1,
wordsPerQuad: NAT ← 4,
logWordsPerQuad: NAT,
realCache: CacheModels.Cache ← NIL,
mapCache: CacheModels.Cache ← NIL,
lineTable: SEQUENCE linesInCache: NAT OF HashEntry
];
CacheStats:
TYPE =
RECORD [
probes: INT ← 0,
readProbes: INT ← 0,
writeProbes: INT ← 0,
writeMisses: INT ← 0,
writeClean: INT ← 0,
chunkMisses: INT ← 0,
lineMisses: INT ← 0,
jumpMisses: INT ← 0,
mapMisses: INT ← 0,
dirtyWrites: INT ← 0
];
HashLim: CARDINAL = 512;
HashVector: TYPE = REF HashVectorRep;
HashVectorRep: TYPE = ARRAY [0..HashLim) OF HashEntry;
LogBaseTwo:
PROC [n:
NAT]
RETURNS [
NAT] = {
IF n = 1 THEN RETURN[0] ELSE RETURN[1+LogBaseTwo[n/2]];
};
NewCache:
PUBLIC
PROC [lines:
NAT ← 512, quadsPerLine:
NAT ← 1, wordsPerQuad:
NAT ← 4, realCache, mapCache: CacheModels.Cache ←
NIL]
RETURNS [cache: CacheModels.Cache] = {
Creates a new cache on the specified shared memory.
IF quadsPerLine > maxQuadsPerLine THEN quadsPerLine ← maxQuadsPerLine;
IF lines > maxLines THEN lines ← maxLines;
cache ←
NEW[CacheModels.CacheRec ← [
private: NEW[CacheDataRep[lines] ← [quadsPerLine: quadsPerLine, wordsPerQuad: wordsPerQuad, logWordsPerQuad: LogBaseTwo[wordsPerQuad], realCache: realCache, mapCache: mapCache, lineTable: NULL]],
fetch: Fetch, store: Store, reset: Reset, flush: Flush, print: Print,
data: NIL]];
Reset[cache];
};
Reset:
PUBLIC CacheModels
.CacheResetProc
-- [cache: CacheModels.Cache] -- = {
Resets the given cache to its initial state (all empty).
private: CacheData = NARROW[cache.private];
private.pageList ← NIL;
private.hashVector ← NEW[HashVectorRep ← ALL[NIL]];
private.victimIndex ← 0;
private.pageEntryCount ← 0;
FOR i:
NAT
IN [0..private.linesInCache)
DO
private[i] ← NEW[HashEntryRep];
ENDLOOP;
private.stats ← []; -- zero out statistics
IF private.realCache # NIL THEN private.realCache.reset[private.realCache];
IF private.mapCache # NIL THEN private.mapCache.reset[private.mapCache];
};
Flush:
PUBLIC CacheModels
.CacheFlushProc
-- [cache: CacheModels.Cache] -- = {
Resets the given cache to its initial state (all empty).
private: CacheData = NARROW[cache.private];
private.pageList ← NIL;
private.hashVector^ ← ALL[NIL];
private.victimIndex ← 0;
private.pageEntryCount ← 0;
FOR i:
NAT
IN [0..private.linesInCache)
DO
private[i]^ ← [valid: FALSE];
ENDLOOP;
IF private.realCache # NIL THEN private.realCache.flush[private.realCache];
IF private.mapCache # NIL THEN private.mapCache.flush[private.mapCache];
};
Print:
PUBLIC CacheModels.CachePrintProc
-- [cache: CacheModels.Cache, stream: STREAM, name: ROPE, resetStatistics: BOOL ← TRUE] -- = {
Realn:
PROC [r:
REAL, n:
NAT]
RETURNS [
IO.Value] = {
RETURN [[rope[Convert.RopeFromReal[r, n]]]]};
private: CacheData = NARROW[cache.private];
quadMisses: INT ← private.stats.chunkMisses;
misses: INT ← quadMisses + private.stats.lineMisses;
probes: INT ← private.stats.probes;
rProbes: REAL ← probes;
rMisses: REAL ← misses;
stream.PutF[
"\nStats for %g (directMap, lines: %g, quads/line: %g, words/quad: %g)\n probes: %g",
[rope[name]],
[integer[private.linesInCache]], [integer[private.quadsPerLine]], [integer[private.wordsPerQuad]], [integer[probes]]];
IF probes = 0 THEN RETURN;
stream.PutF[
" (read: %g, write: %g)\n",
[integer[private.stats.readProbes]], [integer[private.stats.writeProbes]]];
stream.PutF[
" write misses: %g, writes to clean quads: %g\n",
[integer[private.stats.writeMisses]], [integer[private.stats.writeClean]]];
stream.PutF[
" misses: %g (%g (%g%%) existing line)\n",
[integer[misses]], [integer[private.stats.chunkMisses]],
IF misses = 0 THEN [rope["-"]] ELSE Realn[(quadMisses/rMisses)*100, 3]];
IF private.stats.jumpMisses # 0
THEN stream.PutF[
" misses caused by jumps: %g (%g%% of probes)\n",
[integer[private.stats.jumpMisses]], Realn[(private.stats.jumpMisses/rProbes)*100, 3]];
IF probes # 0
THEN stream.PutF[
" miss rate: %g%%\n",
Realn[(misses/rProbes)*100, 3]];
stream.PutF[
" map misses: %g (%g%%)\n dirty writes: %g\n",
[integer[private.stats.mapMisses]], Realn[(private.stats.mapMisses/rProbes)*100, 3], [integer[private.stats.dirtyWrites]]];
};
Fetch:
PUBLIC CacheModels.CacheFetchProc
-- [cache: CacheModels.Cache, addr: DragOpsCross.Word, fromJump: BOOL ← FALSE] -- = {
Access[cache, addr, fromJump, FALSE];
};
Store:
PUBLIC CacheModels.CacheStoreProc
-- [cache: CacheModels.Cache, addr: DragOpsCross.Word] -- = {
Access[cache, addr, FALSE, TRUE];
};
Method: TYPE = {advanceOnMiss, shiftOnHit};
method: Method ← advanceOnMiss;
Access:
PROC [cache: Cache, addr: Word, fromJump, write:
BOOL] = {
data: CacheData = NARROW[cache.private];
wordsPerLine: NAT = data.quadsPerLine * data.wordsPerQuad;
indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine;
chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -data.logWordsPerQuad];
lineAddr: Word = AddDelta[-INT[indexInLine], addr];
hashIndex: CARDINAL ← (HalfToCard[LowHalf[lineAddr]] / wordsPerLine) MOD data.linesInCache;
hashEntry: HashEntry ← data.lineTable[hashIndex];
indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage;
pageAddr: Word = AddDelta[-INT[indexInPage], lineAddr];
pageId: Word ← SingleWordShiftRight[pageAddr, CacheModels.logWordsPerPage];
data.stats.probes ← data.stats.probes + 1;
IF write THEN data.stats.writeProbes ← data.stats.writeProbes + 1 ELSE data.stats.readProbes ← data.stats.readProbes + 1;
Check if the addressed quad is in the cache
IF (hashEntry.lineAddr # lineAddr)
OR ~ hashEntry.valid
THEN {
-- the quad's line itself is not in cache
IF fromJump THEN data.stats.jumpMisses ← data.stats.jumpMisses + 1;
data.stats.lineMisses ← data.stats.lineMisses + 1;
IF write THEN data.stats.writeMisses ← data.stats.writeMisses + 1;
data.stats.mapMisses ← data.stats.mapMisses+1;
IF data.mapCache # NIL THEN data.mapCache.fetch[data.mapCache, pageId];
Write out any dirty entries
IF hashEntry.dirty # None
THEN {
qi: QuadIndex;
FOR qi
IN [0..data.quadsPerLine)
DO
IF hashEntry.dirty[qi]
THEN {
IF data.realCache #
NIL
THEN
data.realCache.store[data.realCache, AddDelta[qi*data.wordsPerQuad, hashEntry.lineAddr]];
data.stats.dirtyWrites ← data.stats.dirtyWrites + 1;
};
ENDLOOP;
hashEntry.dirty ← None;
};
hashEntry.valid ← TRUE;
hashEntry.lineAddr ← lineAddr;
hashEntry.chunkPresent ← None; hashEntry.chunkPresent[chunk] ← TRUE;
IF data.realCache # NIL THEN data.realCache.fetch[data.realCache, addr];
}
ELSE {
-- check if quad is in
IF ~ hashEntry.chunkPresent[chunk]
THEN {
IF fromJump THEN data.stats.jumpMisses ← data.stats.jumpMisses + 1;
data.stats.chunkMisses ← data.stats.chunkMisses + 1;
IF write THEN data.stats.writeMisses ← data.stats.writeMisses + 1;
hashEntry.chunkPresent[chunk] ← TRUE;
IF data.realCache # NIL THEN data.realCache.fetch[data.realCache, addr];
}
};
hashEntry.referenced[chunk] ← TRUE;
IF write
THEN {
IF NOT hashEntry.dirty[chunk] THEN data.stats.writeClean ← data.stats.writeClean + 1;
hashEntry.dirty[chunk] ← TRUE;
};
};
END.