
<<SmallCacheAlgorithm.tioga>>
    <<Pradeep Sindhu January 25, 1988 2:35:54 pm PST>>
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[
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[
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[
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
<<This design requires RA to come in the header cycle>>
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[]
<<Wait for any previous transaction to complete (this requires FBTIP to be cleared on Reset)>>
WHILE FBTIP DO NoOp[];

<<Check if we can get mapping from RCam>>
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[];
}

<<Put RAdrs into Snooper and RqstBuffer>>
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;
<<Remember to restore snooper!!>>
};

RqstBuffer.DoRqst; NonFBTIP _ 1;
WHILE NonFBTIP DO NoOp[];
<<>>
<<Note that we don't wait for the FBRply. Its checked for before the next processor reference!>>
RETURN RplyReg;