Cache Consistency Algorithm 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[]; -- NB: This requires FBTIP to be cleared on Reset PVMatch[VP]; IF ArrayVirtualMatch THEN { Using VMatch Do RdRCam -- putting RP|Offset into RCamRdLatch; } ELSE { RqstBuffer.Header _ MapRqst|myId|VCamRdLatch; RqstBuffer.DoRqst; NonFBTIP _ 1; WHILE NonFBTIP DO NoOp[]; } Snooper.Adrs _ RCamRdLatch; Snooper.RplyStale _ 0; Snooper.Shared _ 0; RqstBuffer.Header _ RbRqst|myId|RCamRdLatch; FreezeVictim[]; Using Victim Do RdRCam; RqstBuffer.Data _ RCamRdLatch; Using Victim Do RdRam; -- NB: RdRam must be initiated only after RdRCam can't be aborted 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; -- NB: We don't wait for the FBRply. Its checked for before the next processor reference! zSCAlgorithm.tioga Pradeep Sindhu March 16, 1987 2:14:15 pm PST This design requires RA to come in the header cycle Κ ˜šœ™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šœžœ‘*˜