Cache Consistency Algorithm (A0)
1. Bus Side Specification
The specification is broken up into several parts, one for each packet type on the DynaBus. Note that in the current algorithm, data is not maintained consistent all the time. In particular, when a cache does an RBRqst and gets a non-orphan reply that is stale, it puts the block into the cache anyway with RPValid=1 and VPValid=0. Now clearly, the data in the block is out of date, but it cannot be accessed by anyone: on the processor side VPValid is 0; on the bus side, OwBit is 0 so no one can see this data. The reason we set RPValid is to stay consistent with the fact that in the RBRqst we said we were going to cache the block. This way, the big cache can maintain the exists below bits exactly.
The transaction WB will be used by a high speed device to inject data into the memory system as follows:  When it wants to inject a block, it simply puts a WBRqst on the bus. Caches will check if the WBRqst matches and will overwrite their contents and clear owner if it does. This scheme has a hole in that an FBRqst immediately following the WBRqst will cause stale data to appear in memory. This, combined with the fact that no one is owner (because of the WBRqst, means we have a problem). 
At this time the only thing we know needs to be done to make the algorithm work for the big cache is to add a transaction called KillBlockRqst (KBRqst). The request would be issued by the big cache after it had made sure that it had current data by doing an RBRqst. A small cache seeing KBRqst would simply clear the valid bits (real and virtual) for that block.
RBRqst[RequestorId, RA, VRA]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN Snooper.Valid _ 1;
ELSE IF Snooper.Match THEN {Snooper.ShBit _ 1; BShared _ 1};
RMatch[RA];
IF idMatch THEN Using Victim DO {ClrRPValid; ClrVPValid};
IF ArrayRealMatch THEN {
Using RMatch Do {RdRam; IF ~idMatch THEN Array.ShBit _ 1};
IF ~idMatch THEN BShared _ 1;
IF Array.OwBit THEN {BOwner _ 1; FIFO _ [Cmd: RBRply, RplyShared: 1, RA, Data]}
};
Memory Controller Slave
InitiateFetch[RA];
Wait[dso];
abort _ BOwner; RplyShared _ BShared;
IF ~abort THEN FIFO _ [Cmd: RBRply, RplyShared: RplyShared, RA, Data];
RBRply[RequestorId, RplyShared, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN {Snooper.Valid _ 0; NonFBTIP _ 0}
ELSE quit;
Snooper.Valid _ 0;
RMatch[RA];
IF ArrayRealMatch
THEN Using RMatch Do {WtVCam; WtRCam; WtRam}
ELSE Using Victim Do {
VPValid _ ~Snooper.RplyStale; RPValid _ 1;
WtVCam; WtRCam;
WtRam; Array.ShBit _ Snooper.ShBit OR RplyShared; Clr[Array.OwBit]
};
UnFreezeVictim[];
Memory controller
NoOP[];
WBRqst[RequestorId, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN {Snooper.Valid _ 1}
ELSE {IF Snooper.Match THEN Snooper.RplyStale _ 1}
RMatch[RA];
IF ArrayRealMatch THEN {
Using RMatch Do {WtRam; Clr[Array.OwBit]};
}
Memory Controller Slave
Store[RA, Data];
FIFO _ [Cmd: FBRply, RplyShared: 0, RA];
WBRply[RequestorId, RplyShared, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN {Snooper.Valid _ 0; NonFBTIP _ 0};

Memory controller
NoOP[];
FBRqst[RequestorId, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN Snooper.Valid _ 0;
Memory Controller Slave
Store[RA, Data];
FIFO _ [Cmd: FBRply, RplyShared: 0, RA];
FBRply[RequestorId, RplyShared, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN FBTIP _ 0;
Memory controller
NoOP[];
WSRqst[RequestorId, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN Snooper.Valid _ 1
ELSE IF Snooper.Match THEN BShared _ 1;
RMatch[RA];
IF ArrayRealMatch THEN {
IF ~idMatch THEN BShared _ 1;
};
Memory Controller Slave
Wait[dso];
RplyShared _ BShared;
FIFO _ [Cmd: WSRply, RplyShared: RplyShared, RA, Data];
WSRply[RequestorId, RplyShared, RA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN {Snooper.Valid _ 0; NonFBTIP _ 0}
ELSE IF Snooper.Match THEN Snooper.RplyStale _ 1;
RMatch[RA];
IF ArrayRealMatch THEN {
IF idMatch
THEN Using RMatch Do {WtRam; Array.ShBit _ RplyShared OR Snooper.ShBit; Set[Array.OwBit]}
ELSE Using RMatch Do {WtRam; Clr[Array.OwBit]}
};
Memory controller
NoOP[];
CWSRqst[RequestorId, RA, New, Old]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN LdSnooper[RA]
ELSE IF Snooper.Match THEN BShared _ 1;
RMatch[RA];
IF ArrayRealMatch THEN {
IF ~idMatch THEN BShared _ 1;
};
Memory Controller Slave
Wait[dso];
RplyShared _ BShared;
FIFO _ [Cmd: WSRply, RplyShared: RplyShared, RA, New, Old];
CWSRply[RequestorId, RA, New, Old]
Slave Caches
Note: Old value is in the MSW.
idMatch: BOOL _ myId=RequestorId;
IF idMatch
THEN NonFBTIP _ 0
ELSE IF Snooper.Match THEN Snooper.RplyStale _ 1;
RMatch[RA];
IF ArrayRealMatch THEN {
Using RMatch Do RdRam;
IF Old=ValueRead THEN Using RMatch Do WtRam[New];
IF idMatch
THEN Using RMatch Do {Set[Array.OwBit]; Array.ShBit _ RplyShared OR Snooper.ShBit}
ELSE Using RMatch Do Clr[Array.OwBit];
}
Memory controller
NoOP[];
IORRqst[RequestorId, IOA]
Slave Caches
RMatch[IOA];
IF ArrayRealMatch THEN {
Using RMatch Do RdRam;
FIFO _ [Cmd: IORRply, IOA, RamData]
}
Memory Controller Slave
Match[IOA];
IF match THEN {
FIFO _ [Cmd: IORRply, IOA, RdIOReg[IOA]]
}
IORRply[RequestorId, IOA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN NonFBTIP _ 0;
Memory controller
NoOP[];
IOWRqst[RequestorId, IOA, Data]
Slave Caches
RMatch[IOA];
IF ArrayRealMatch THEN {
Using RMatch Do IOAction[];
FIFO _ [Cmd: IOWRply, IOA, Data]
}
Memory Controller Slave
Match[IOA];
IF match THEN {
WtIOReg[IOA, Data];
FIFO _ [Cmd: IORRply, IOA, Data]
}
IOWRply[RequestorId, IOA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN NonFBTIP _ 0;
Memory controller
NoOP[];
BIOWRqst[RequestorId, IOA, Data]
Slave Caches
NoOp[];
Memory Controller Slave
FIFO _ [Cmd: BIOWRply, IOA, Data];
BIOWRply[RequestorId, IOA, Data]
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN NonFBTIP _ 0;
RMatch[IOA];
IF ArrayRealMatch THEN {
Using RMatch Do IOAction[];
}
Memory controller
NoOp[];
MapRqst[RequestorId, VA]
Slave Caches
NoOp[];
Memory Controller Slave
NoOp[];
MapRply[RequestorId, RA, Undefined]  -- note the order: RA comes in header word
Slave Caches
idMatch: BOOL _ myId=RequestorId;
IF idMatch THEN {
{NonFBTIP _ 0; RMatch[RA]} -- putting RA onto the bit lines
RCamRdLatch _ RA; -- We use the RdLatch as a temp reg for RA
LdFlags into VCamWtReg;
};
Memory controller
NoOp[];
DeMapRqst[RequestorId, RA]
Slave Caches
NoOp[];
Memory Controller Slave
FIFO _ [Cmd: DeMapRply, RA];
DeMapRply[RequestorId, RA]
Slave Caches
PRMatch[RP];
IF ArrayRealMatch THEN {
Using RMatch Do Clr[VPValid];
};
Memory controller
NoOP[];
2. Processor Side Specification
Two actions comprise the processor side microcode: PFetch and PStore.
The PSide microcode uses the following variables to communicate with the BSide microcode:
NonFBTIP		a transaction other than FB is in progress
FBTIP		an FB transaction is in progress
PFetch[VA]
VMatch[VA];
IF ArrayVirtualMatch
THEN { -- PFetchHit
Using VMatch Do RdRam
}
ELSE RETURN [HandleMiss[]];
PStore[VA, Data]
VMatch[VA];
IF ArrayVirtualMatch
THEN { -- PStoreHit
Using VMatch Do WtRam; Set[Array.OwBit];
IF ~Array.ShBit
THEN {Using VMatch Do WtRam; Set[Array.OwBit]}
ELSE {
Using VMatch Do RdRCam -- putting RA into RCamRdLatch;
Snooper.Adrs _ RCamRdLatch; Snooper.RplyStale _ 0; Snooper.Shared _ 0;
RqstBuffer.Data _ PData;
RqstBuffer.Header _ WSRqst|myId|RCamRdLatch;
RqstBuffer.DoRqst;
WHILE NonFBTIP DO NoOp[];
RETURN RplyReg;
}
}
ELSE {HandleMiss[]; Goto PStore}
HandleMiss[]
WHILE FBTIP DO NoOp[];

PVMatch[VP];
IF ArrayVirtualMatch
THEN { -- Read RP from RCam
Using VMatch Do RdRCam -- putting RP into RCamRdLatch;
}
ELSE { -- Issue MapRqst
RqstBuffer.Header _ MapRqst|myId|VCamRdLatch; RqstBuffer.DoRqst; NonFBTIP _ 1;
WHILE NonFBTIP DO NoOp[];
}

Snooper.Adrs _ CamRdLatch; Snooper.RplyStale _ 0; Snooper.Shared _ 0;
RqstBuffer.Header _ RBRqst|myId|CamRdLatch;

FreezeVictim[];
Using Victim Do RdRCam; RqstBuffer.Data _ RCamRdLatch;

Note that RdRam must be initiated only after RdRCam can't be aborted
Using Victim Do RdRam;
IF Array.OwBit THEN {
Snooper.Adrs _ RCamRdLatch; Snooper.RplyStale _ 0; Snooper.Shared _ 0;
Snooper.Valid _ 1;
FIFO _ [Cmd: FBRqst, RCamRdLatch, RamBlkRdLatch]; FBTIP _ 1;
};

RqstBuffer.DoRqst; NonFBTIP _ 1;
WHILE NonFBTIP DO NoOp[];
RETURN RplyReg;

žSCAlgorithm.tioga
Pradeep Sindhu October 26, 1987 4:36:25 pm PST
This design requires RA to come in the header cycle
Wait for any previous transaction to complete (this requires FBTIP to be cleared on Reset)
Check if we can get mapping from RCam
Put RAdrs into Snooper and RqstBuffer
Remember to restore snooper!!

Note that we don't wait for the FBRply. Its checked for before the next processor reference!
Κ	G˜š
œ™Icode™.—Ititle˜ 
headš
Οb˜Ibody˜ΏN˜ξN˜κ˜˜Iprogramšœ	Οkœ˜!šžœ˜
Ošžœ˜Ošžœ
žœžœ"˜<—Ošœžœ˜Ošžœ	žœžœ˜9šžœžœ˜Ošœžœ
žœ˜:Ošžœ
žœ
˜Ošžœ
žœžœ žœ˜OO˜——˜Ošœžœ˜JšœΟg
Οdœ˜
O˜%Ošžœžœ
žœ)žœ˜F——˜)š
œ˜Ošœ	žœ˜!šžœ˜
Ošžœ"˜&Ošžœ˜
—Oš
œ˜Ošœžœ˜šžœ˜Ošžœ(˜,šžœ˜Oš
œ*˜*Oš
œ˜Ošœž
œžœ˜BO˜——O˜—˜Oš
œ˜——˜š
œ˜Ošœ	žœ˜!šžœ˜
Ošžœ˜Ošžœžœžœ˜2—Ošœžœ˜šžœžœ˜J˜*O˜
——˜Ošœžœ˜Ošžœ žœ˜(——˜)š
œ˜Ošœ	žœ˜!Jšžœ	žœ#˜2O˜—˜Oš
œ˜——˜š
œ˜Ošœ	žœ˜!šžœ˜
Jšžœ˜——˜Ošœžœ˜Ošžœ žœ˜(——˜)š
œ˜Ošœ	žœ˜!Ošžœ	žœ˜—˜Oš
œ˜——˜š
œ˜Ošœ	žœ˜!šžœ˜
Jšžœ˜Jšžœ
žœžœ
˜'—Jšœžœ˜šžœžœ˜Ošžœ
žœ
˜O˜——˜OšœŸ
 œ˜
O˜Ošžœ)žœ˜7——˜)š
œ˜Ošœ	žœ˜!šžœ˜
Ošžœ"˜&Ošžœ
žœžœ˜1—Ošœžœ˜šžœžœ˜šžœ˜
Ošžœ2žœ!˜YOšžœ*˜.—O˜——˜Oš
œ˜——˜"š
œ˜Ošœ	žœ˜!šžœ˜
Jšžœžœ
˜Jšžœžœ
˜'—Ošœžœ˜šžœžœ˜Ošžœ
žœ
˜O˜——˜OšœŸ
 œ˜
O˜Ošžœ)žœ˜;——˜"Mš
œ˜˜Ošœ	žœ˜!šžœ˜
Ošžœ
˜Ošžœ
žœžœ˜1—Ošœžœ˜šžœžœ˜O˜Ošžœžœ˜1šžœ˜
Ošžœ=žœ˜ROšžœ"˜&—O˜
——˜Oš
œ˜——˜š
œ˜Ošœžœ˜šžœžœ˜J˜Jšžœžœ
˜#J˜
——˜Ošœžœ˜šžœžœ˜Jšžœžœ
žœ˜(J˜
———˜š
œ˜Ošœ	žœ˜!Ošžœ	žœ˜—˜Oš
œ˜——˜š
œ˜Ošœžœ˜šžœžœ˜J˜Jšžœžœ˜ J˜
——˜Ošœžœ˜šžœžœ˜Jšœžœ˜Jšžœžœ˜ J˜
———˜š
œ˜Ošœ	žœ˜!Ošžœ	žœ˜—˜Oš
œ˜——˜ š
œ˜J˜—˜Ošžœžœ˜"——˜ š
œ˜Ošœ	žœ˜!Ošžœ	žœ˜Ošœžœ˜šžœžœ˜J˜J˜
——˜Oš
œ˜——˜š
œ˜J˜—˜J˜——˜Oš
œ˜O™3Ošœ	žœ˜!šžœ	žœ˜OšœžœΟc ˜;Ošœžœ‘*˜<O˜O˜——˜Oš
œ˜——˜š
œ˜J˜—˜Ošžœžœ˜——˜š
œ˜Ošœžœ˜šžœžœ˜O˜O˜——˜Oš
œ˜———š
˜N˜E˜YItable3˜\—˜
Ošœžœ˜šžœ˜šžœ‘˜Oš
œ˜Oš
œ
˜
—Ošžœ
žœ˜——˜Ošœžœ˜šžœ˜šžœ‘˜Oš
œ(˜(šžœ
˜Ošžœ*˜.šžœ˜Ošœ‘˜6Oš
œF˜FOš
œ˜Oš
œ,˜,Oš
œ˜Ošžœ
žœ˜Ošžœ	˜O˜
——Oš
œ
˜
—Ošžœ˜ ——˜Ošœ/‘œ‘™ZOšžœžœ˜O˜O™%Ošœžœ˜šžœ˜šžœ‘˜Ošœ‘˜6O˜
—šžœ‘˜Oš
œN˜NOšžœ
žœ˜O˜
——O˜O™%Oš
œE˜EOš
œ+˜+O˜O˜Oš
œ6˜6O˜Oš
‘D˜DOš
œ˜šžœ
žœ˜Oš
œF˜FOš
œ˜Ošžœ8˜<O™Oš
œ˜—O˜Oš
œ ˜ Ošžœ
žœ˜O™Oš
œ\™\Ošžœ	˜———…— φ+Ϋ