<> <> <> <> <> DIRECTORY Basics USING [BITSHIFT], CacheModels, Convert, DragOpsCross USING [Half, Word, ZerosWord], DragOpsCrossUtils USING [AddDelta, HalfShift, HalfToCard, HalfXor, LowHalf, WordToHalves], IO, Rope; RealCache: CEDAR PROGRAM IMPORTS Basics, Convert, DragOpsCrossUtils, IO, Rope = BEGIN OPEN DragOpsCross, DragOpsCrossUtils; <> Cache: TYPE = CacheModels.Cache; wordsPerQuad: NAT = 4; logWordsPerQuad: NAT = 2; maxQuadsPerLine: NAT = 8; wordsPerPage: CARDINAL = CacheModels.wordsPerPage; QuadIndex: TYPE = [0..maxQuadsPerLine); PageEntry: TYPE = REF PageEntryRep; PageEntryRep: TYPE = RECORD [ next: PageEntry _ NIL, pageAddr: Word _ ZerosWord, useCount: INT _ 0 ]; None: PACKED ARRAY QuadIndex OF BOOL = ALL[FALSE]; HashEntry: TYPE = REF HashEntryRep; HashEntryRep: TYPE = RECORD [ next: HashEntry _ NIL, lineAddr: Word _ ZerosWord, index: NAT _, chunkPresent: PACKED ARRAY QuadIndex OF BOOL _ None, dirty: PACKED ARRAY QuadIndex OF BOOL _ None, referenced: PACKED ARRAY QuadIndex OF BOOL _ 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, lru: BOOL _ FALSE, rover: NAT _ 0, quadsPerLine: NAT _ 2, lineTable: SEQUENCE linesInCache: NAT OF HashEntry ]; CacheStats: TYPE = RECORD [ probes: 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; NewCache: PUBLIC PROC [lines: [0..4096) _ 100, quadsPerLine: [0..32) _ 2, lru: BOOL _ FALSE] RETURNS [cache: CacheModels.Cache] = { <> cache _ NEW[CacheModels.CacheRec _ [ private: NEW[CacheDataRep[lines] _ [quadsPerLine: quadsPerLine, lru: lru, lineTable: NULL]], fetch: Fetch, store: Store, reset: Reset, flush: Flush, print: Print, data: NIL]]; Reset[cache]; }; Reset: CacheModels.CacheResetProc -- [cache: CacheModels.Cache] -- = { <> 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 _ [index: i]]; ENDLOOP; private.stats _ []; -- zero out statistics }; Flush: CacheModels.CacheFlushProc -- [cache: CacheModels.Cache] -- = { <> 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]^ _ [index: i]; ENDLOOP; }; Print: 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 (lines: %g, quads/line: %g)\n probes: %g\n", [rope[IF private.lru THEN Rope.Cat[name, " (pseudo-lru)"] ELSE name]], [integer[private.linesInCache]], [integer[private.quadsPerLine]], [integer[probes]]]; IF probes = 0 THEN RETURN; 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[ " hit rate: %g%%\n", Realn[((probes - misses)/rProbes)*100, 3]]; stream.PutF[ " map misses: %g\n dirty writes: %g\n", [integer[private.stats.mapMisses]], [integer[private.stats.dirtyWrites]]]; }; Fetch: CacheModels.CacheFetchProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word, fromJump: BOOL _ FALSE] -- = { private: CacheData = NARROW[cache.private]; wordsPerLine: NAT = private.quadsPerLine * wordsPerQuad; indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine; chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -logWordsPerQuad]; entry: HashEntry _ Access[cache, AddDelta[addr, -INT[indexInLine]], chunk, fromJump]; entry _ entry; -- to have a place to set a breakpoint }; Store: CacheModels.CacheStoreProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word] -- = { private: CacheData = NARROW[cache.private]; wordsPerLine: NAT = private.quadsPerLine * wordsPerQuad; indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine; chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -logWordsPerQuad]; hashEntry: HashEntry; hashEntry _ Access[cache, AddDelta[addr, -INT[indexInLine]], chunk, FALSE]; hashEntry.dirty[chunk] _ TRUE; }; Method: TYPE = {advanceOnMiss, shiftOnHit}; method: Method _ advanceOnMiss; Access: PROC [cache: Cache, lineAddr: Word, chunk: QuadIndex, fromJump: BOOL] RETURNS [hashEntry: HashEntry] = { data: CacheData = NARROW[cache.private]; oldEntry: BOOL _ TRUE; victim: CARDINAL _ data.victimIndex; hashIndex: CARDINAL; halfHash: Half _ HalfXor[WordToHalves[lineAddr][0], WordToHalves[lineAddr][1]]; halfHash _ HalfXor[halfHash, HalfShift[halfHash, -8]]; hashIndex _ HalfToCard[halfHash] MOD HashLim; hashEntry _ data.hashVector[hashIndex]; data.stats.probes _ data.stats.probes + 1; WHILE hashEntry # NIL DO IF hashEntry.lineAddr = lineAddr THEN { IF data.lru THEN hashEntry.referenced[chunk] _ TRUE; IF hashEntry.index = victim AND method = shiftOnHit THEN { <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; }; IF ~hashEntry.chunkPresent[chunk] THEN { IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1; data.stats.chunkMisses _ data.stats.chunkMisses + 1; hashEntry.chunkPresent[chunk] _ TRUE}; RETURN; }; hashEntry _ hashEntry.next; ENDLOOP; IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1; data.stats.lineMisses _ data.stats.lineMisses + 1; hashEntry _ data.lineTable[victim]; { <> lag: PageEntry _ NIL; oldLineAddr: Word = hashEntry.lineAddr; oldIndexInPage: CARDINAL = HalfToCard[LowHalf[oldLineAddr]] MOD wordsPerPage; oldPageAddr: Word = AddDelta[oldLineAddr, -INT[oldIndexInPage]]; headHashEntry: HashEntry; oldHashIndex: CARDINAL; oldHalfHash: Half _ HalfXor[ WordToHalves[oldLineAddr][0], WordToHalves[oldLineAddr][1]]; oldHalfHash _ HalfXor[oldHalfHash, HalfShift[oldHalfHash, -8]]; oldHashIndex _ HalfToCard[oldHalfHash] MOD HashLim; headHashEntry _ data.hashVector[oldHashIndex]; <> IF headHashEntry = hashEntry THEN data.hashVector[oldHashIndex] _ hashEntry.next ELSE WHILE headHashEntry # NIL DO IF hashEntry = headHashEntry.next THEN { headHashEntry.next _ hashEntry.next; EXIT}; headHashEntry _ headHashEntry.next ENDLOOP; <> FOR pageEntry: PageEntry _ data.pageList, pageEntry.next WHILE pageEntry # NIL DO IF pageEntry.pageAddr = oldPageAddr THEN { <> IF (pageEntry.useCount _ pageEntry.useCount - 1) <= 0 THEN { <> IF lag = NIL THEN data.pageList _ pageEntry.next ELSE lag.next _ pageEntry.next; data.pageEntryCount _ data.pageEntryCount - 1; pageEntry.next _ data.freePageList; data.freePageList _ pageEntry; }; EXIT }; lag _ pageEntry; ENDLOOP; IF hashEntry.dirty # None THEN { FOR i: NAT IN [0..data.quadsPerLine) DO IF hashEntry.dirty[i] THEN data.stats.dirtyWrites _ data.stats.dirtyWrites + 1; ENDLOOP; hashEntry.dirty _ None; }; }; <> { indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage; pageAddr: Word = AddDelta[lineAddr, -INT[indexInPage]]; pageEntry: PageEntry _ data.pageList; <> hashEntry.next _ data.hashVector[hashIndex]; data.hashVector[hashIndex] _ hashEntry; hashEntry.lineAddr _ lineAddr; hashEntry.chunkPresent _ None; hashEntry.chunkPresent[chunk] _ TRUE; WHILE pageEntry # NIL DO IF pageEntry.pageAddr = pageAddr THEN { <> pageEntry.useCount _ pageEntry.useCount + 1; GO TO oldEntry; }; pageEntry _ pageEntry.next; ENDLOOP; <> data.pageEntryCount _ data.pageEntryCount + 1; data.stats.mapMisses _ data.stats.mapMisses + 1; pageEntry _ data.freePageList; IF pageEntry = NIL THEN pageEntry _ NEW[PageEntryRep] ELSE data.freePageList _ pageEntry.next; pageEntry^ _ [next: data.pageList, pageAddr: pageAddr, useCount: 1]; data.pageList _ pageEntry; EXITS oldEntry => NULL; }; <> victim _ victim + 1; data.victimIndex _ IF victim = data.linesInCache THEN 0 ELSE victim; }; END.