DIRECTORY IO;

CacheSim: CEDAR PROGRAM
IMPORTS IO
= BEGIN
wdsPerBlk:		CARDINAL = 8;
blksPerSLn:		CARDINAL = 4;
sLnsPerBLn:		CARDINAL = 8;
blksPerBLn:		CARDINAL = blksPerSLn*sLnsPerBLn;
sLnsPerSCache:	CARDINAL = 64;
SCPerBC:			CARDINAL = 8;
bLnsPerBC:		CARDINAL = sLnsPerSCache * SCPerBC;

AddrPageIdx:		TYPE = [0..4194304);			-- 22 bits
PageWdIdx:		TYPE = [0..1024);				-- 10 bits
BCLineIdx:		TYPE = [0..bLnsPerBC);
BlkWdIdx:		TYPE = [0..wdsPerBlk);
DeviceID:			TYPE = [0..1024);
DynaBusCmd:	TYPE = {
RBRqst,	RBRply,
WSRqst,	WSRply,
CWSRqst,	CWSRply,
WBRqst,	WBRply,	-- WBRply not used
FBRqst,	FBRply,
IORRqst,	IORRply,
IOWRqst,	IOWRply,
BIORqst,	BIORply, 
MapRqst,	MapRply,
DMRqst,	DMRply};

Word:			TYPE = LONG CARDINAL;
AddressRec:	TYPE = RECORD[page: AddrPageIdx_0, wd: PageWdIdx_0];
Data:			TYPE = REF DataAry;
DataAry:		TYPE = ARRAY WdIndex OF Word _ ALL[0];
BlockAry:	TYPE = RECORD[
victim:		BlkIndex	_ 0,
victimLock:	BOOL		_ FALSE,
blks:			ARRAY BlkIndex OF BlockRec];
BlockRec: 		TYPE = RECORD[
owner:	BOOL			_ FALSE,		-- Owner
shared:	BOOL			_ FALSE,		-- Shared
rpValid:	BOOL			_ FALSE,		-- Real		page valid
vpValid:	BOOL			_ FALSE,		-- Virtual	page valid
rAddr:	AddressRec	_ [ ],			-- Real		address
vAddr:	AddressRec	_ [ ],			-- Virtual	address
data:		Data			_ NIL ];
SnoopRec:	TYPE = RECORD[
enabled:	BOOL			_ FALSE,		-- Enable snooping of the outstanding address
shared:	BOOL			_ FALSE,		-- Shared Accumulator
rplyStale:	BOOL			_ FALSE,		-- RplyStale
addr:		AddressRec	_ [ ] ];		-- Outstanding address
PacketRec:	TYPE = RECORD[
valid:		BOOL			_ FALSE,
head:		HeaderRec	_ [],
data:		Data			_ NIL ];
HeaderRec:	TYPE = RECORD[
id:				DeviceID			_ 0,
cmd:			DynaBusCmd	_ RBRqst,
shared:		BOOL				_ FALSE,
rAddr:		AddressRec		_ [ ] ];
FifoRec:	TYPE = RECORD[	
count:	INT _ 0,
ary:	SEQUENCE size: CARDINAL OF PacketRec ];

CacheRec:	TYPE = RECORD[
id:				DeviceID		_ 0,						-- this caches id
p:				PacketRec	_ [],						-- received packet
snoop:			SnoopRec		_ [],						-- state of the snooper
array:			CacheAry	_ [],						-- main cache arrary
fifoHi5:		REF FifoRec	_ NEW[FifoRec[4]],		-- Hi priority port for 5 cycle requests
fifoLo2:		REF FifoRec	_ NEW[FifoRec[1]],		-- Lo priority port for 2 cycle requests
tipFB:			BOOL			_ FALSE,					-- a flush block request is outstanding
tipNFB:		BOOL			_ FALSE,					-- non flush block request is outstanding
pAddr:		AddressRec	_ [ ],						-- processor side address
pWord:		Word			_ 0,						-- processor side data
];
c: Cache _ NewCache[];
NewCache: PROC RETURNS[c: Cache] _ {
c _ NEW[CacheRec];
c.p.data _ NEW[DataRec];
FOR blk IN BlkIndex DO
IF c.array[blk].data _ NEW[DataRec] ENDLOOP};

VirtualMatch: PROC[c: Cache]
RETURNS[found: BOOL _ FALSE, blk: BlkIndex _ 0] = {
FOR blk IN BlkIndex DO
IF c.array[blk].vAddr = c.pAddr THEN RETURN[TRUE, blk] ENDLOOP};

MatchPacketReal: PROC[c: Cache]
RETURNS[found: BOOL _ FALSE, blk: BlkIndex _ 0] = {
FOR blk IN BlkIndex DO
IF c.array[blk].rAddr = c.p.head.rAddr THEN RETURN[TRUE, blk] ENDLOOP};

ExtractWd: PROC[d: Data, addr: AddressRec] RETURNS[wd: Word] =
{RETURN[data[addr.wd MOD wdsPerBlk]]};

InsertWd: PROC[d: Data, addr: AddressRec, wd: Word] =
{data[addr.wd MOD wdsPerBlk] _ wd};
ReceivePacket: PROC[c: Cache] = {
SELECT c.p.head.cmd FROM
RBRqst	=> {
IF myRequest
THEN {
InitSnooper[snoop, rAddr];
array[array.victim].rpValid _ F;
array[array.victim].vpValid _ F}
ELSE {
[aMatch, blk]	_ MatchPacketReal[c];
sMatch			_ SnoopMatch[snoop, rAddr];
IF aMatch THEN array[blk].shared _ T;
IF sMatch THEN snoop.shared _ T;
busShared _ aMatch OR sMatch;
busOwner _ aMatch AND array[blk].owner;
IF aMatch AND array[blk].owner THEN
EnQOut[fifo: fifoHi5, cmd:RBRply, shared: T, addr: rAddr, data: array[blk].data]}};
RBRply	=> 
IF myRequest THEN {
[aMatch, blk]		_ MatchPacketReal[c];
snoop.enabled		_ F;
tipNonFB				_ F;
array.victimLock	_ F;
IF aMatch	THEN array[blk].vAddr		_ vAddr;
IF ~aMatch	THEN array[array.victim]	_ [
owner:	F,
shared:	snoop.shared OR p.shared,
rpValid:	T,
vpValid:	~snoop.RplyStale,
vAddr:	vAddr,
rAddr:	rAddr,
data:		data ]};

WSRqst, CWSRqst	=> {
IF myRequest
THEN InitSnooper[snoop, rAddr]
ELSE {
[aMatch, blk]	_ MatchPacketReal[c];
sMatch			_ SnoopMatch[snoop, rAddr];
busShared		_ aMatch OR sMatch} };
WSRply, CWSRply	=> {
IF myRequest
THEN	{snoop.enabled _ F;	tipNonFB _ F}
ELSE	{sMatch _ SnoopMatch[snoop, rAddr];	IF sMatch THEN snoop.rplyStale _ T};
[aMatch, blk]	_ MatchPacketReal[c];
IF aMatch THEN {
array[blk].shared	_ p.shared OR myRequest AND snoop.shared;
array[blk].owner	_ myRequest;
word _ ExtractWd[array[blk].data. rAddr];
IF cmd=CWSRply AND word=old THEN word _ new;
array[blk].data _ InsertWd[array[blk].data, rAddr, word]} };

WBRqst	=> {
IF myRequest
THEN InitSnooper[snoop, rAddr]
ELSE {
[aMatch, blk]	_ MatchPacketReal[c];
sMatch			_ SnoopMatch[snoop, rAddr];
IF sMatch THEN	snoop.rplyStale		_ T;
IF aMatch THEN array[blk].data		_ data;
IF aMatch THEN array[blk].owner	_ F} };
WBRply	=> IF myRequest THEN {snoop.enabled _ F;	tipNonFB _ F};
FBRqst	=> IF myRequest	THEN snoop.enabled _ F;
FBRply	=> IF myRequest	THEN 						tipFB _ F;

IORRqst	=> {
[ioMatch, blk]		_ IOMatch[array, ioAddr];
IF ioMatch THEN {
wd: Word _ ExtractWd[array[blk].data, ioAddr];
EnQOut[fifo: fifoHi5, cmd: IORRply, addr: ioAddr, wd: wd]} };
IORRply	=> IF myPacket THEN tipNonFB _ F;
IOWRqst	=> {
[ioMatch, blk]		_ IOMatch[array, ioAddr];
IF ioMatch THEN {
array[blk].data _ InsertWd[array[blk].data, ioAddr, data];
EnQOut[fifo: fifoHi5, cmd: IOWRply, addr: ioAddr, data: data]} };
IOWRply	=> IF myPacket THEN tipNonFB _ F;
BIORqst	=> NoOp[];
BIORply	=> {
blk:		BlkIndex;
ioMatch:	BOOL;
IF myPacket THEN	tipNonFB _ F;
[ioMatch, blk]		_ IOMatch[array, ioAddr];
IF ioMatch THEN
array[blk].data _ InsertWd[array[blk].data, ioAddr, data]};

MapRqst	=> NoOp[];
MapRply	=> {
myPacket: BOOL _ requestorId=myId;
IF myPacket THEN tipNonFB _ F;
IF myPacket THEN array[mapBlk] _ [
shared:	snoop.shared OR p.shared,
owner:	F,
vpValid:	~snoop.RplyStale,
rpValid:	T,
vAddr:	vAddr,
rAddr:	rAddr ]};
DMRqst	=> NoOp[];
DMRply	=> { };	-- Clear vpValid on all matching real pages
ENDCASE;
SELECT cmd FROM
RBRqst	=> {
reply			_ busOwner; -- After Wait[dso]
rplyShared	_ busShared; -- After Wait[dso]
IF ~ownedBelow THEN
EnQOut[fifo: fifoHi5, cmd: RBRply, shared: sharedBelow, addr: rAddr, data: mem[rAddr]]};
RBRply	=> NoOP[];
WBRqst	=> {
MemStore[mem, rAddr, data];
EnQOut[fifo: fifoHi5, cmd: WBRply, shared: F, addr: rAddr]};
WBRply	=> NoOP[];
FBRqst	=> {
MemStore[mem, rAddr, data];
EnQOut[fifo: fifoHi5, cmd: FBRply, shared: F, addr: rAddr]};
FBRply	=> NoOP[];
WSRqst	=> {
p.shared _ busShared; -- After Wait[dso];
EnQOut[fifo: fifoHi5, cmd: WSRply, shared: p.shared, addr: rAddr, data: data]};
WSRply	=> NoOP[];
CWSRqst	=> {
p.shared _ busShared; -- After Wait[dso];
EnQOut[fifo: fifoHi5, cmd: CWSRply, shared: p.shared, addr: rAddr, new: new, old: old]};
CWSRply	=> NoOP[];
IORRqst	=> {
wd:		Word;
ioMatch:	BOOL;
[ioMatch, wd]		_ IOMatch[array, ioAddr];
IF ioMatch THEN {
data _ RdIOReg[ioAddr];
EnQOut[fifo: fifoHi5, cmd: IORRply, addr: ioAddr, data: data]}};
IORRply	=> NoOP[];
IOWRqst	=> {
wd:		Word;
ioMatch:	BOOL;
[ioMatch, wd]		_ IOMatch[array, ioAddr];
IF ioMatch THEN {
WtIOReg[ioAddr, data];
EnQOut[fifo: fifoHi5, cmd: IOWRply, addr: ioAddr, data: data]}};
IOWRply	=> NoOP[];
BIORqst	=> EnQOut[fifo: fifoHi5, cmd: BIOWRply, addr: ioAddr, data: data];
BIORply	=> NoOp[];
MapRqst	=> NoOp[];
MapRply	=> NoOp[];
DMRqst	=> EnQOut[fifo: fifoHi5, cmd: DeMapRply, addr: rAddr];
DMRply	=> NoOp[];
ENDCASE};
PFetch: PROC[c: Cache] = {
aMatch:	BOOL;
blk:		BlkIndex;
[aMatch, blk]	_ VirtualMatch[c];
IF ~aMatch THEN {
HandleMiss[c];
[aMatch, blk]	_ VirtualMatch[c]};
c.pWord _ ExtractWd[ c.array[blk].data[c.pAddr MOD wdsPerBlk] ] };

PStore: PROC[c: Cache] = {
aMatch:	BOOL;
blk:		BlkIndex;
[aMatch, blk]	_ VirtualMatch[c];
IF ~aMatch THEN {
HandleMiss[];
[aMatch, blk]	_ VirtualMatch[c];
IF ~array[blk].shared
THEN {
InsertWd[array[blk].data, vAddr, c.pWord];
array[blk].owner _ T}
ELSE {
EnQOut[fifo: bufLo2, cmd: WSRqst, shared: F, addr: rAddr, wd: c.pWord];
tipNonFB _ T;	WHILE tipNonFB DO NoOp[] ENDLOOP}}};

HandleMiss: PROC[c: Cache] = {
aMatch:	BOOL;
blk:		BlkIndex;
rAddr:	AddressRec;
WHILE tipFB DO NoOp[] ENDLOOP; -- tipFB must be cleared on Reset
[aMatch, blk] _ VirtualPageMatch[c];
IF aMatch
THEN rAddr _ array[blk].rAddr
ELSE {
EnQOut[fifo: bufLo2, cmd: MapRqst, shared: F, addr: vAddr];
tipNonFB _ T;	WHILE tipNonFB DO NoOp[] ENDLOOP};
FreezeVictim[];
victimAddr _ array[array.victim].rAddr;
IF array[array.victim].owner THEN {
InitSnooper[snoop, array[array.victim].raddr]; -- do this before owner can change
EnQOut[fifo: fifoHi5, cmd: FBRqst, addr: rAddr, data: array[array.victim].data];
tipFB _ 1};  -- Snooper must abort FB if stale data (WSRply, CWSRply, WB)
EnQOut[fifo: bufLo2, cmd: RBRqst, shared: F, addr: rAddr, data: victimAddr];
tipNonFB _ T;	WHILE tipNonFB DO NoOp[] ENDLOOP};

END.

jCacheSim.mesa
Don Curry February 11, 1988 11:05:38 am PST
Types and Constants
Utils
Hi slave controller - Read and Write
Hi slave controller - IO
Lo slave controller
Cache processor side
Multiple Matches Possible
Somthing funny to make rAddr from vAddr and rPage
Note that we don't wait for the FBRply. Its checked for before the next processor reference!
สิ˜š
œ
™
Jš
œ+™+—J˜Jšฯk	œ
œ
˜
J˜šฯnœœ
˜Jšœ
˜
Jšœ˜—
head™Jšœœ˜Jšœ
œ˜Jšœ
œ˜Jšœ
œ˜.Jšœœ˜Jšœœ˜Jšœœ˜/J˜Jšœœฯc
˜/JšœœŸ
˜+Jšœœ˜"Jšœœ˜!Jšœœ
˜šœœ˜Jš
œ˜Jš
œ˜Jš
œ˜JšœŸ˜"Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜—J˜Jšœœœ
œ
˜Jšœœœ'˜@Jšœœœ	˜Jš	œ
œœ	œœ˜0šœ
œœ
˜Jš
œ˜Jšœœœ
˜Jšœœ
œ˜$—šœœœ
˜JšœœœŸ˜ JšœœœŸ	˜"Jšœ	œœŸ˜-Jšœ	œœŸ˜/JšœŸ˜+JšœŸ˜-Jšœœ˜—šœ
œœ
˜Jšœ	œœŸ-˜GJšœœœŸ˜.JšœœœŸ˜(JšœŸ˜2—šœœœ
˜Jšœœœ
˜Jš
œ˜Jšœœ˜—šœœœ
˜Jš
œ˜Jš
œ˜Jšœ	œœ
˜Jš
œ˜—šœ	œœ˜Jšœœ˜Jšœœœ
œ
˜,—J˜šœ
œœ
˜JšœŸ˜,JšœŸ˜-JšœŸ˜5JšœŸ˜1Jšœ
œœŸ(˜RJšœ
œœŸ(˜RJšœ	œœŸ'˜DJšœ	œœŸ)˜FJšœŸ˜8JšœŸ˜/J˜—Jš
œ˜—™šžœœ
œ˜$Jšœœ˜Jšœœ
˜šœœ
˜Jšœœ
œ˜-—J˜—šžœœ
˜Jšœœœ˜3šœœ
˜Jš
œœ
œ
œœ˜@—J˜—šžœœ
˜Jšœœœ˜3šœœ
˜Jš
œ%œ
œ
œœ˜G—J˜—šž	œœœ˜>Jšœ
œœ˜&J˜—šžœœ'˜5Jšœœ˜#——™$Jšž
œœ˜!šœ˜š
œ˜
programšœ
˜šœ˜Lš
œ˜Lš
œ ˜ Lš
œ ˜ —šœ˜Lš
œ#˜#Lš
œ$˜$Lšœœ˜%Lšœœ˜ Jšœœ˜Lšœœ˜'šœœ˜#Lš
œS˜S————š
œ
˜
šœœ˜Lš
œ$˜$Lš
œ˜Lš
œ˜Lš
œ˜Lšœœ˜)šœ	œ˜'Lš
œ	˜	Lšœœ
˜!Lš
œ˜Lš
œ˜Lš
œ
˜
Lš
œ
˜
Lš
œ˜———J˜š
œ˜šœ
˜Jšœ˜šœ˜Jš
œ#˜#Jš
œ$˜$Lšœœ˜!———š
œ˜šœ
˜Jšœ"˜&Jšœ%œœ˜M—Jš
œ#˜#šœœ˜Jšœœœ˜;Jš
œ˜Lš
œ)˜)Lšœ
œ
œ˜,Lš
œ<˜<——J˜š
œ˜šœ
˜Lšœ˜šœ˜Lš
œ#˜#Lš
œ$˜$Lšœœ˜$Jšœœ˜'Jšœœ˜'———Jšœ
œœ#˜>Jšœ
œœ˜.Jšœ
œœ˜,——šœ™˜š
œ˜Lš
œ)˜)šœ	œ˜Jš
œ.˜.Jš
œ=˜=——Jšœœ
œ˜)š
œ˜Lš
œ)˜)šœ	œ˜J˜:Jš
œA˜A——Jšœœ
œ˜)Jš
œ˜š
œ˜Lš
œ˜Lšœ	œ
˜Lšœ
œ˜Lš
œ)˜)šœ	˜Jš
œ;˜;——J˜Jš
œ˜š
œ˜Lšœ
œ˜"Lšœ
œ˜šœ
œ˜"Lšœœ
˜!Lš
œ	˜	Lš
œ˜Lš
œ˜Lš
œ
˜
Lš
œ˜——Jš
œ˜JšœŸ+˜:Jšœ
˜——š
œ™šœ˜š
œ˜LšœŸ˜&LšœŸ˜*šœ
˜Lš
œX˜X——Jš
œ˜š
œ˜Lš
œ˜Lš
œ<˜<—Jš
œ˜š
œ˜Lš
œ˜Lš
œ<˜<—Jš
œ˜š
œ˜LšœŸ˜)Lš
œO˜O—Jš
œ˜š
œ˜LšœŸ˜)Lš
œX˜X—Jš
œ˜š
œ˜Lš
œ
˜
Lšœ	œ
˜Lš
œ(˜(šœ	œ˜Jš
œ˜Jš
œ@˜@——Jš
œ˜š
œ˜Lš
œ
˜
Lšœ	œ
˜Lš
œ(˜(šœ	œ˜Jš
œ˜Jš
œ@˜@——Jš
œ˜Jš
œJ˜JJš
œ˜Jš
œ˜Jš
œ˜Jš
œ=˜=Jš
œ˜Jšœ˜	——™šžœœ˜Jšœœ
˜
Jš
œ˜Jš
œ ˜ šœ	œ˜Jš
œ˜Jš
œ!˜!—Jšœ/œ˜BJ˜—šžœœ˜Jšœœ
˜
Jš
œ˜Jš
œ ˜ šœ	œ˜Jš
œ
˜
Jš
œ ˜ —šœ˜šœ˜Jš
œ*˜*Jš
œ˜—šœ˜Jš
œG˜GJšœœ
œœ˜2——J˜—šž
œœ˜Jšœœ
˜
Jš
œ˜Jš
œ˜JšœœœŸ!˜@Jš
œ$˜$Jš
ฯb™šœ˜	Jšœ˜šœ˜Jš
œ;˜;Jšœœ
œœ˜0——Jš
 1™1J˜Jš
œ'˜'šœœ˜#Jšœ/Ÿ"˜QJš
œP˜PJšœ
Ÿ<˜I—Jš
œL˜Lšœœ
œœ˜0Jš
œ\™\———˜Jšœ
˜——…—"า0