DIRECTORY DirectMapCache, CacheModels, Convert, DragOpsCrossUtils, IO, Random, Rope, ViewerIO; VerifyDirectMapCache: CEDAR PROGRAM IMPORTS DirectMapCache, Convert, DragOpsCrossUtils, IO, Random, ViewerIO = { cache: CacheModels.Cache; in, out: IO.STREAM; readProbes, writeProbes, readMisses, writeMisses, mapMisses, writesToCleanQuads: INT; maxAddr: INT; cacheLines, cacheQuadsPerLine: INT; cacheWordsPerQuad: INT _ 4; cacheWordsPerPage: INT _ 1024; probabilityOfRead: REAL = 0.6; CreateDirectMapCache: PROC [lines: INT _ 256, quadsPerLine: INT _ 2, wordsPerQuad: INT _ 4] RETURNS [CacheModels.Cache] = { cacheLines _ lines; cacheQuadsPerLine _ quadsPerLine; cacheWordsPerQuad _ wordsPerQuad; cache _ DirectMapCache.NewCache[lines: lines, quadsPerLine: quadsPerLine, wordsPerQuad: wordsPerQuad]; RETURN[cache]; }; Init: PROC [] = { [] _ Random.Create[-1, 10173]; [in, out] _ ViewerIO.CreateViewerStreams [name: "VerifyDirectMapCache", 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 cache.fetch[cache, DragOpsCrossUtils.IntToWord[addr]]; readProbes _ readProbes+1; IF quadMiss THEN readMisses _ readMisses+1; } ELSE { -- write reference cache.store[cache, DragOpsCrossUtils.IntToWord[addr]]; writeProbes _ writeProbes+1; IF quadMiss THEN writeMisses _ writeMisses+1; }; IF mapMiss THEN mapMisses _ mapMisses+1; }; RefPatternKnown: PROC [n: INT] = { addr, tempAddr: INT _ 0; quads: INT _ cacheLines*cacheQuadsPerLine; window: INT _ MIN[quads*cacheWordsPerQuad, 64]; pHit: INT = 80; cache.reset[cache]; THROUGH [1..quads] WHILE n > 0 DO Access[addr, TRUE]; n _ n-1; addr _ addr+cacheWordsPerQuad; ENDLOOP; 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 Access[addr, TRUE]; n _ n-1; addr _ addr+1; } ENDLOOP; }; RefPatternSerial: PROC [n, incr: INT] = { addr: INT; cache.reset[cache]; FOR addr IN [0..n) DO Access[addr*incr, TRUE]; ENDLOOP; }; RefPatternCircular: PROC [n, incr, size: INT] = { addr: INT; cache.reset[cache]; FOR addr IN [0..n) DO Access[(addr*incr) MOD size, TRUE]; ENDLOOP; }; RefPatternRand: PROC [n, lo, hi: INT] = { addr: INT; cache.reset[cache]; THROUGH [0..n) DO addr _ Random.ChooseInt[min: lo, max: hi]; Access[addr, TRUE]; ENDLOOP; }; PrintStats: PROC [] = { cache.print[cache, out, "Virtual Cache"]; PrintExpected["Virtual Cache", cacheLines, cacheQuadsPerLine]; }; }.  VerifyDirectMapCache.mesa Copyright c 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:08:27 pm PDT Bertrand Serlet July 28, 1985 11:02:54 pm PDT Cache Parameters: 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. Do enough references to fill the cache Now do the remaining references FOR tempAddr IN [addr-window..addr) DO Access[tempAddr, FALSE]; ENDLOOP; This procedure generates references to the addresses [0, incr, 2.incr, .. n.incr) This procedure generates references to the addresses [0, incr, 2.incr, .. n.incr) modulo size 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. Κ;˜codešœ™Kšœ Οmœ7™BKšœ9™9Kšœ:™:K™-K™—šΟk ˜ Kšœ9žœ˜T—K˜šΟbœžœž˜#Kšžœ-žœ˜LKšœ˜Kšœ žœžœ˜KšœQžœ˜UKšœ žœ˜ K˜K™Kšœžœ˜#Kšœžœ˜Kšœžœ˜K˜Kšœžœ˜K˜K˜š Οnœžœ žœžœžœžœ˜|KšœW˜WKšœf˜fKšžœ˜Kšœ˜—K˜š œžœ˜Kšœ˜KšœVžœ˜]KšœY˜YK˜Kšœ˜—K˜š  œžœ žœžœ˜CKšœžœ˜%Kšœžœ˜%Kšœ žœ ˜Kšœ žœ ˜K˜˜AK˜9—Kšœ.˜.šœ ˜ Kšœ&˜&Kšœ/˜/—šœ ˜ K˜0Kšœ˜—Kšœ,˜,K˜šžœ žœ ˜K˜Kšœ>˜>—Kšœ3˜3Kšœ˜Kšœ˜—K˜š œžœžœž œ˜>Kšœ žœ žœžœ˜>Kšœ žœ žœžœ˜=Kšœžœ&˜/K˜K•StartOfExpansion[]˜šžœ žœ ˜.šžœΟc˜Kšœ6˜6Kšœ˜Kšžœ žœ˜+K˜—šžœ‘˜Kšœ6˜6Kšœ˜Kšžœ žœ˜-K˜——Kšžœ žœ˜(Kšœ˜—K˜K™τš œžœžœ˜"Kšœžœ˜Kšœžœ ˜*Kšœžœžœ˜/Kšœžœ˜K˜K˜K˜Kšœ&™&Kšžœ žœž˜!Kšœ žœ˜Kšœ'˜'Kšžœ˜K˜K™Kšžœž˜šžœ*˜,šžœ‘˜Kšœ;˜;Kšœžœ ˜ K˜—šžœ‘I˜PKš žœ žœžœžœžœ™HKšœ žœ˜Kšœ˜Kšœ˜——Kšžœ˜K˜Kšœ˜—K˜K™Qš œžœ žœ˜)Kšœžœ˜ K˜K˜K˜šžœžœž˜Kšœžœ˜—Kšžœ˜Kšœ˜—K˜K™]š œžœžœ˜1Kšœžœ˜ K˜K˜K˜šžœžœž˜Kšœžœžœ˜#—Kšžœ˜Kšœ˜—K˜K˜K˜K™Πš œžœ žœ˜)Kšœžœ˜ K˜K˜K˜šžœž˜K˜*Kšœ žœ˜—Kšžœ˜Kšœ˜—K˜K˜š  œžœ˜K˜)Kšœ>˜>Kšœ˜—K˜Kšœ˜—K˜K˜K˜—…—Ži