DIRECTORY DirectMapCache, Basics USING [BITSHIFT], CacheModels, Convert, DragOpsCross USING [Half, Word, ZerosWord], DragOpsCrossUtils USING [AddDelta, HalfToCard, LowHalf, SingleWordShiftRight], IO, Rope; DirectMapCacheImpl: CEDAR PROGRAM IMPORTS Basics, Convert, DragOpsCrossUtils, IO EXPORTS DirectMapCache = BEGIN OPEN DragOpsCross, DragOpsCrossUtils; 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] = { 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] -- = { 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] -- = { 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; 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]; 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. xDirectMapCacheImpl.mesa Copyright c 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 Private types Creates a new cache on the specified shared memory. Resets the given cache to its initial state (all empty). Resets the given cache to its initial state (all empty). Check if the addressed quad is in the cache Write out any dirty entries Κ Š˜codešœ™Kšœ Οmœ1™Kšœžœ%˜GKšœžœ˜3Kšœ ž œ/žœ˜[Kšœ1˜1Kšœ žœ!žœ˜GKšœžœ˜7KšœK˜KK˜Kšœ*˜*Kšžœžœ5žœ3˜yK˜K™+šžœ!žœ˜7šžœ’)˜0Kšžœ žœ3˜CKšœ2˜2Kšžœžœ5˜BK˜.Kšžœžœžœ+˜GK™K™šžœžœ˜ Kšœ˜šžœžœž˜#šžœžœ˜šžœžœž˜KšœY˜Y—Kšœ4˜4K˜—Kšžœ˜—Kšœ˜K˜—K˜Kšœžœ˜Kšœ˜Kšœ?žœ˜DKšžœžœžœ+˜HK˜—šžœ’˜šžœ!žœ˜)Kšžœ žœ3˜CKšœ4˜4Kšžœžœ5˜BK˜Kšœ žœ˜%Kšžœžœžœ+˜HKšœ˜—K˜——K˜Kšœžœ˜#šžœžœ˜Kšžœžœžœ3˜UKšœžœ˜K˜—K˜—Kšžœ˜—K˜—…—,