-- File: [Indigo]<Sakura>Dragon>DragonCacheImpl.sak -- Dragon Cache -- 23-Mar-82 13:02:29 DIRECTORY ConvertUnsafe, DragonCache, Inline, SakuraRT, SimIO; DragonCacheImpl: MONITOR IMPORTS ConvertUnsafe, Inline, SakuraRT, SimIO EXPORTS DragonCache = { -- The functionality of Dragon cache chip is described under the following --conventions: there are two main processes, a process to watch the processor bus --commands (PbusFetch), and a process to watch the memory bus commands --(BackDoor, backdoor operations). Furthermore, PbusFetch cooperates with --several other processes to allow overlapping of pipline operations: MProc is a --process that is invoked from PbusFetch and invokes Mbus operations directly. --Operations associated with Pbus commands are all split into two parts so that --they can be piplined. All the front parts of these operations are inside --PbusFetch, so they do not constitute independent processes. The latter parts --are all independent processes. They are FetchTransport, StoreTransport, and --DoMapOpTransport. -- Communications among processes: --Communication between PbusFetch and MProc is done through two global --variables: DoMProc and MProcDone. The communication between PbusFetch --and transport processes, FetchTransport, StoreTransport, and --DoMapOpTransport, is done by global variables, FetchTransportGo, --StoreTransportGo, and DoMapOpTransportGo, and ~Reject for the other --direction. Cell: TYPE = RECORD [ vp: LONG CARDINAL, rp: LONG CARDINAL, bl: [0..37B], D: ARRAY [0..3] OF LONG CARDINAL, VpValid, RpValid, RpDirty, CEDirty, Shared, TIP: BOOLEAN]; MProcType: TYPE = PROC; -- Constants DataArraySize: CARDINAL = 64; ProcessorNum: STRING = "Proc1: "; -- Global variables FetchTransportGo, StoreTransportGo, DoMapOpTransportGo, Holding, DoMProc, MProcDone, PRq, NewRq, MRq, Orph, MCMD: BOOLEAN; Instruction: DragonCache.PbusOp; DataIndex, VictimIndex: CARDINAL; RqBL, PBL, MBL: [0..37B]; PWord, MWord: [0..3]; RqVP, MVP, RqData, PResult, PRP, MRP, MOResult, MRdData, MWData: LONG CARDINAL; Data: ARRAY [0..DataArraySize) OF Cell; MOp: MProcType; MInst: DragonCache.MbusCommand; MapOp: DragonCache.MapOpKind; RpDirtyReg: BOOLEAN; -- This register is set by ReadMap or PartialMatch PageFault: SIGNAL = CODE; WriteViolation: SIGNAL = CODE; CheckVal: PUBLIC ENTRY PROC [vp: LONG CARDINAL, bl: [0..37B], word: [0..3], val: LONG CARDINAL] = { loc: CARDINAL; matched: BOOLEAN; [matched, loc] ← FullVpMatch[vp, bl]; IF ~ matched THEN ERROR; IF Data[loc].D[word]#val THEN ERROR}; Cache: PUBLIC DEVICE = { IN Op: DragonCache.PbusOp, PDataIn: DragonCache.PbusType, MDataIn: DragonCache.MbusType, ClockA, ClockB, CMDIn, RQ, SharedIn, Grant: BOOLEAN OUT Exception, Reject, SharedOut, CMDOut, Rq: BOOLEAN, PDataOut: DragonCache.PbusType, MDataOut: DragonCache.MbusType GUARDIAN {} CONTROL { -- PbusFetch process procedures PbusFetch: DEVICE = { IN OUT GUARDIAN {} CONTROL { success: BOOLEAN; DO WHEN ClockA UP: NULL; --A (Phase A) IF RQ AND ~Reject THEN { Exception ← FALSE; WITH b: PDataIn SELECT FROM Instruction => {RqVP ← b.vp; RqBL ← b.bl; PWord ← b.word}; ENDCASE => ERROR; Instruction ← Op; WHEN ClockB UP: [success, DataIndex] ← FullVpMatch[RqVP, RqBL]; --M (Phase B) { ENABLE { PageFault => {PDataOut ← [Data[-1]]; Exception ← TRUE}; WriteViolation => {PDataOut ← [Data[0]]; Exception ← TRUE}}; SELECT Instruction FROM Fetch => CallFetch[success]; FetchHold => CallFetchHold[success! PageFault => {PDataOut ← [Data[-1]]; Holding ← FALSE; Exception ← TRUE}; WriteViolation => {PDataOut ← [Data[0]]; Exception ← TRUE}]; Store => CallStore[success]; MapOp => CallMapOp[success]; ENDCASE} }; ENDLOOP} }; WaitForTIP: PROC = { Reject ← TRUE; DO SakuraRT.Delay[30]; IF Data[DataIndex].TIP THEN { WHEN ClockB UP: NULL; LOOP } ELSE EXIT; ENDLOOP}; CallFetch: PROC [success: BOOLEAN] = { -- Started at Phase B index: CARDINAL; IF success THEN { --hit WaitForTIP[]; Reject ← FALSE; FetchTransportGo ← TRUE; Holding ← FALSE} ELSE { Reject ← TRUE; Holding ← FALSE; WHEN ClockA UP: Holding ← TRUE; --R (Phase A) SakuraRT.Delay[10]; PRq ← TRUE; --T (Phase B) WaitForGrant[]; WriteBackVictimIfDirty[]; [success, index] ← PartialMatch[RqVP]; PRP ← Data[index].rp; WHEN ClockB UP: IF ~success THEN CallMProc[ReadMap, "ReadMap"]; IF success THEN CallMProc[ReadQuadMatch, "ReadQuad"] ELSE CallMProc[ReadQuad, "ReadQuad"]; PRq ← FALSE; Reject ← FALSE; [success, DataIndex] ← FullVpMatch[RqVP, RqBL]; IF ~success THEN ERROR; -- This is a description error FetchTransportGo ← TRUE} }; CallFetchHold: PROC [success: BOOLEAN] = { -- Started at Phase B IF ~Holding THEN { Reject ← TRUE; WHEN ClockA UP: NULL; SakuraRT.Delay[10]; PRq ← TRUE; WaitForGrant[]; WHEN ClockB UP: Holding ← TRUE}; CallFetch[success]}; CallStore: PROC [success: BOOLEAN] = { Reject ← TRUE; WHEN ClockA UP: WITH b: PDataIn SELECT FROM Data => RqData ← b.data; ENDCASE => ERROR; WaitForTIP[]; IF ~success THEN { SakuraRT.Delay[10]; PRq ← TRUE; WaitForGrant[]; WriteBackVictimIfDirty[]; WHEN ClockB UP: { [success, DataIndex] ← PartialMatch[RqVP]; PRP ← Data[DataIndex].rp; IF ~success THEN CallMProc[ReadMapAndSetRpDirty, "ReadMapAndSetRpDirty"]}; WHEN ClockB UP: IF success THEN CallMProc[ReadQuadMatch, "ReadQuad"] ELSE CallMProc[ReadQuad, "ReadQuad"]}; WHEN ClockB UP: [success, DataIndex] ← FullVpMatch[RqVP, RqBL]; Data[DataIndex].CEDirty ← TRUE; IF ~Data[DataIndex].RpDirty THEN { IF ~PRq THEN {PRq ← TRUE; WaitForGrant[]}; CallMProc[ReadMapAndSetRpDirty, "ReadMapAndSetRpDirty"]}; IF ~Data[DataIndex].Shared THEN StoreTransportGo ← TRUE ELSE { Data[DataIndex].D[PWord] ← RqData; IF ~PRq THEN {PRq ← TRUE; WaitForGrant[]}; CallMProc[WriteSingle, "WriteSingle"]}; Reject ← FALSE; PRq ← FALSE; }; -- CallStore CallMapOp: PROC [success: BOOLEAN] = { -- Started at Phase B Reject ← TRUE; WHEN ClockA UP: NULL; SakuraRT.Delay[10]; PRq ← TRUE; WaitForGrant[]; WHEN ClockA UP: WITH b: PDataIn SELECT FROM Data => RqData ← b.data; ENDCASE => ERROR; CallMProc[DoMapOp, "DoMapOp"]; PRq ← FALSE}; -- CallMapOp CallMProc: PROC [procedure: MProcType, name: REF TEXT] = { -- Starts in Phase B and finishes in Phase B st: LONG STRING ← [25]; ConvertUnsafe.AppendRefText[st, name]; WaitMProcReallyDone[]; SetMProcDone[FALSE]; SetDoMProc[TRUE]; MOp ← procedure; SimIO.WF2[" %sMbus op: %s started*n", ProcessorNum, st]; DO WHEN ClockB UP: IF IsMProcDone[] THEN EXIT; ENDLOOP; SimIO.WF2[" %sMbus op: %s finished*n", ProcessorNum, st]}; -- CallMProc WaitMProcReallyDone: PROC = { -- Starts in Phase B DO SakuraRT.Delay[30]; IF IsMProcReallyDone[] THEN EXIT; WHEN ClockB UP: NULL; ENDLOOP}; SetMProcReallyDone: ENTRY PROC [val: BOOLEAN] = { MProcReallyDone ← val}; IsMProcReallyDone: ENTRY PROC RETURNS [BOOLEAN] = { RETURN[MProcReallyDone]}; MProcReallyDone: BOOLEAN ← TRUE; WriteBackVictimIfDirty: PROC = { -- Starts at Phase A MRP ← Data[VictimIndex].rp; MBL ← Data[VictimIndex].bl; IF Data[VictimIndex].RpValid AND Data[VictimIndex].CEDirty THEN { CallMProc[WriteQuad, "WriteQuad"]; Data[VictimIndex].CEDirty ← FALSE}; }; -- WriteBackVictimIfNotClean WaitForGrant: PROC = { DO WHEN ClockA UP: IF Grant THEN EXIT ENDLOOP}; -- WaitForGrant -- FetchTransport process procedures FetchTransport: DEVICE = { IN OUT GUARDIAN {} CONTROL { -- Starts at Phase B DO WHEN ClockA UP: NULL; --R (Phase A) IF FetchTransportGo THEN { PResult ← Data[DataIndex].D[PWord]; FetchTransportGo ← FALSE; WHEN ClockB UP: PDataOut ← [Data[PResult]]}; ENDLOOP} }; StoreTransport: DEVICE = { IN OUT GUARDIAN {} CONTROL { -- Starts at Phase B index, pword: CARDINAL; success: BOOLEAN; DO WHEN ClockB UP: { pword ← PWord; [success, index] ← FullVpMatch[RqVP, RqBL]}; WHEN ClockA UP: IF StoreTransportGo THEN { IF ~success THEN ERROR; Data[index].D[pword] ← RqData; StoreTransportGo ← FALSE} ENDLOOP} }; -- StoreTransport DoMapOpTransport: DEVICE = { IN OUT GUARDIAN {} CONTROL { DO WHEN ClockB UP: NULL; -- (B) IF DoMapOpTransportGo THEN { NewRq ← TRUE; MOResult ← MRdData; Reject ← FALSE; WHEN ClockA UP: { PResult ← MOResult; NewRq ← FALSE}; WHEN ClockB UP: { IF Inline.BITAND[Inline.HighHalf[PResult],40000B]#0 THEN Exception ← TRUE; PDataOut ← [Data[PResult]]} } ENDLOOP} }; -- DoMapOpTransport -- MProc process procedures MProc: DEVICE = { IN OUT GUARDIAN {} CONTROL { SetMProcDone[FALSE]; DO WHEN ClockA UP: NULL; IF IsDoMProc[] THEN { SetDoMProc[FALSE]; CMDOut ← TRUE; MOp[]}; ENDLOOP} }; SetDoMProc: ENTRY PROC [val: BOOLEAN] = { DoMProc ← val}; IsDoMProc: ENTRY PROC RETURNS [BOOLEAN] = { RETURN[DoMProc]}; SetMProcDone: ENTRY PROC [val: BOOLEAN] = { MProcDone ← val}; IsMProcDone: ENTRY PROC RETURNS [BOOLEAN] = { RETURN[MProcDone]}; WriteQuad: PROC = { i: CARDINAL; WriteOneWord: PROC [pword: [0..3]] = { WHEN ClockB UP: MWData ← Data[VictimIndex].D[pword]; WHEN ClockA UP: MDataOut ← [Data[MWData]]}; -- WriteOneWord MDataOut ← [Instruction[WriteQuad, MRP, MBL, 0]]; WHEN ClockB UP: MWData ← Data[VictimIndex].D[0]; SakuraRT.Delay[20]; CMDOut ← FALSE; WHEN ClockA UP: MDataOut ← [Data[MWData]]; FOR i IN [1..3] DO WriteOneWord[i] ENDLOOP; WHEN ClockB UP: SetMProcDone[TRUE]; SetMProcReallyDone[TRUE]}; -- WriteQuad ReadMap: PROC = { fault: BOOLEAN; MVP ← RqVP; MDataOut ← [MapCommand[ReadMap, , , , MVP]]; WHEN ClockB UP: SakuraRT.Delay[20]; CMDOut ← FALSE; fault ← WaitMapOpDone[]; IF fault THEN SIGNAL PageFault; WITH b: MDataIn SELECT FROM MapCommand => {MRP ← b.vp; RpDirtyReg ← b.rpdirty}; ENDCASE => ERROR; SetMProcDone[TRUE]; SetMProcReallyDone[TRUE]}; ReadMapAndSetRpDirty: PROC = { fault: BOOLEAN; MVP ← RqVP; MDataOut ← [MapCommand[ReadMapAndSetRpDirty, , , , MVP]]; WHEN ClockB UP: SakuraRT.Delay[20]; CMDOut ← FALSE; fault ← WaitMapOpDone[]; IF fault THEN SIGNAL PageFault; WITH b: MDataIn SELECT FROM MapCommand => {MRP ← b.vp; RpDirtyReg ← b.rpdirty}; ENDCASE => ERROR; SetMProcDone[TRUE]; SetMProcReallyDone[TRUE]}; ReadQuadMatch: PROC = { MRP ← PRP; ReadQuad[]}; ReadQuad: PROC = { ReadOneWord: PROC = {IF ~Orph THEN ReadDataFromBus[@Data[index].D[pword]]}; success: BOOLEAN; pword: CARDINAL ← PWord; index: CARDINAL; PBL ← RqBL; MDataOut ← [Instruction[ReadQuad, MRP, PBL, pword]]; WITH b: MDataIn SELECT FROM Instruction => {MRP ← b.rp; MBL ← b.bl; MWord ← b.word}; ENDCASE => ERROR; WHEN ClockB UP: MRq ← TRUE; -- (Phase B, t2) SakuraRT.Delay[20]; CMDOut ← FALSE; WHEN ClockA UP: [success, index] ← FullRpMatch[MRP, MBL];-- (Phase A, t3) WHEN ClockB UP: { -- (Phase B, t4) Orph ← success; IF ~success THEN index ← VictimIndex}; WHEN ClockA UP: IF ~success THEN { -- (Phase A, t5) Data[index].rp ← MRP; Data[index].bl ← MBL; Data[index].RpValid ← TRUE; Data[index].Shared ← FALSE; Data[index].CEDirty ← FALSE; Data[index].RpDirty ← RpDirtyReg}; WHEN ClockB UP: -- (Phase B, t6) -- { Data[index].vp ← RqVP}; Data[index].VpValid ← TRUE; Data[index].Shared ← SharedIn; VictimIndex ← (VictimIndex+1) MOD DataArraySize; WHEN ClockA UP: MCMD ← CMDIn; -- (Phase A, t7) IF MCMD AND MInst=NotReady THEN WaitOneCycle[]; SetMProcDone[TRUE]; WHEN ClockB UP: ReadOneWord[]; -- (Phase B, t8) WHEN ClockA UP: pword ← (pword+1) MOD 4; -- (Phase A, t9) WHEN ClockB UP: -- (Phase B, t10) --{ Data[index].TIP ← TRUE; ReadOneWord[]; MRq ← FALSE; IF ~Holding THEN NewRq ← TRUE}; WHEN ClockA UP: pword ← (pword+1) MOD 4; -- (Phase A, t11) WHEN ClockB UP: { -- (Phase B, t12) ReadOneWord[]; IF ~Holding THEN NewRq ← FALSE}; WHEN ClockA UP: pword ← (pword+1) MOD 4; -- (Phase A, t13) WHEN ClockB UP: -- (Phase B, t14) --{ ReadOneWord[]; Data[index].TIP ← FALSE; SetMProcReallyDone[TRUE]}}; SetRpDirty: PROC = { -- Starts in A fault: BOOLEAN; PBL ← RqBL; MDataOut ← [Instruction[SetRpDirty, MRP, PBL, PWord]]; WITH b: MDataIn SELECT FROM Instruction => { MRP ← b.rp; MBL ← b.bl; MWord ← b.word}; ENDCASE => ERROR; WHEN ClockB UP: fault ← WaitMapOpDone[]; IF fault THEN SIGNAL WriteViolation; SetMProcDone[TRUE]; SetMProcReallyDone[TRUE]}; WriteSingle: PROC = { PBL ← RqBL; PRP ← RqVP; MDataOut ← [Instruction[WriteSingle, PRP, PBL, PWord]]; NewRq ← TRUE; WHEN ClockB UP: MWData ← RqData; SakuraRT.Delay[20]; CMDOut ← FALSE; WHEN ClockA UP: MDataOut ← [Data[MWData]]; WHEN ClockB UP: SetMProcDone[TRUE]; NewRq ← FALSE; SetMProcReallyDone[TRUE]}; DoMapOp: PROC = { fault: BOOLEAN; MVP ← RqVP; MDataOut ← [MapCommand[DoMapOp, MapOp, , , MVP]]; MCMD ← TRUE; WHEN ClockB UP: MWData ← RqData; SakuraRT.Delay[20]; CMDOut ← FALSE; WHEN ClockA UP: MDataOut ← [Data[MWData]]; fault ← WaitMapOpDone[]; IF fault THEN SIGNAL PageFault; SetMProcDone[TRUE]; ReadDataFromBus[@MRdData]; DoMapOpTransportGo ← TRUE; SetMProcReallyDone[TRUE]}; -- DoMapOp WaitMapOpDone: PROC RETURNS [fault: BOOLEAN] = { DO WHEN ClockB UP: SakuraRT.Delay[30]; MCMD ← CMDIn; [MInst, fault] ← DecodeMbusCommand[]; IF MCMD AND MInst=MapOpDone THEN EXIT; ENDLOOP; }; DecodeMbusCommand: PROC RETURNS [MInst: DragonCache.MbusCommand, fault: BOOLEAN] = { WITH b: MDataIn SELECT FROM Instruction => {MInst ← b.command; MRP ← b.rp; MBL ← b.bl; MWord ← b.word; fault ← FALSE}; MapCommand => {MInst ← b.command; fault ← b.fault}; ENDCASE => ERROR}; WaitOneCycle: PROC = { WHEN ClockB UP: NULL; WHEN ClockA UP: NULL; }; ReadDataFromBus: PROC [data: POINTER TO LONG CARDINAL] = { WITH b: MDataIn SELECT FROM Data => data↑ ← b.data; ENDCASE => ERROR}; ArbiterInterface: DEVICE = { IN OUT GUARDIAN {} CONTROL { arbiterHolding: BOOLEAN ← FALSE; DO WHEN ClockA UP: NULL; SakuraRT.Delay[15]; IF (~ arbiterHolding) AND (PRq OR MRq) THEN { arbiterHolding ← TRUE; Rq ← TRUE} ELSE IF arbiterHolding AND ~PRq AND ~MRq THEN { arbiterHolding ← FALSE; Rq ← FALSE}; ENDLOOP} }; -- Back door operations BackDoor: DEVICE = { IN OUT GUARDIAN {} CONTROL { MInst: DragonCache.MbusCommand; DO WHEN ClockB UP: NULL; MCMD ← CMDIn; IF MCMD THEN { [MInst, ] ← DecodeMbusCommand[]; SELECT MInst FROM ReadQuad => BDReadQuad[]; WriteQuad => NULL; WriteSingle => BDWriteSingle[]; ReadMap => NULL; ReadMapAndSetRpDirty => BDReadMapAndSetRpDirty[]; SetRpDirty => BDSetRpDirty[]; DoMapOp => NULL; ENDCASE}; ENDLOOP} }; BDReadQuad: PROC = { -- Starts in B index: CARDINAL; success: BOOLEAN; ReadOneWord: PROC = { WHEN ClockB UP: IF success THEN MWData ← Data[index].D[MWord]; WHEN ClockA UP: { IF success THEN MDataOut ← [Data[MWData]]; MWord ← (MWord+1) MOD 4}; }; WHEN ClockA UP: [success, index] ← FullRpMatch[MRP, MBL]; IF success THEN { Data[index].Shared ← TRUE; SharedOut ← TRUE}; WHEN ClockB UP: NULL; THROUGH [1..4] DO ReadOneWord[] ENDLOOP; WHEN ClockB UP: SharedOut ← FALSE}; -- BDReadQuad BDWriteSingle: PROC = { index: CARDINAL; success: BOOLEAN; WHEN ClockA UP: [success, index] ← FullRpMatch[MRP, MBL]; SakuraRT.Delay[30]; ReadDataFromBus[@MRdData]; -- (A) WHEN ClockB UP: IF success THEN { Data[index].D[MWord] ← MRdData}};-- BDWriteSingle BDReadMapAndSetRpDirty: PROC = { index: CARDINAL; success: BOOLEAN; WHEN ClockA UP: [success, index] ← FullRpMatch[MRP, MBL]; WHEN ClockB UP: IF success THEN Data[index].RpDirty ← TRUE}; -- BDReadMapAndSetRpDirty BDSetRpDirty: PROC = { index: CARDINAL; success: BOOLEAN; WHEN ClockA UP: [success, index] ← FullRpMatch[MRP, MBL]; WHEN ClockB UP: IF success THEN Data[index].RpDirty ← TRUE}; -- BDSetRpDirty Reject ← FALSE; SharedOut ← FALSE; CMDOut ← FALSE; FOR i: CARDINAL IN [0..DataArraySize) DO Data[i].VpValid ← Data[i].RpValid ← FALSE ENDLOOP; WHEN ClockA UP: NULL; CIRCUIT { COMPONENTS pbus: PbusFetch, fetch: FetchTransport, store: StoreTransport, domapop: DoMapOpTransport, mproc: MProc, backdoor: BackDoor, arbinterface: ArbiterInterface NODES REPRESENTATION CONNECTIONS pbus[], fetch[], store[], domapop[], mproc[], backdoor[], arbinterface[]} } }; -- Data array access procedures FullVpMatch: PROC [vp: LONG CARDINAL, bl: CARDINAL] RETURNS [BOOLEAN, CARDINAL] = { FOR i: CARDINAL IN [0..DataArraySize) DO IF Data[i].VpValid AND Data[i].vp=vp AND Data[i].bl=bl THEN RETURN [TRUE, i] ENDLOOP; RETURN[FALSE, 0]}; FullRpMatch: PROC [rp: LONG CARDINAL, bl: CARDINAL] RETURNS [BOOLEAN, CARDINAL] = { FOR i: CARDINAL IN [0..DataArraySize) DO IF Data[i].RpValid AND Data[i].rp=rp AND Data[i].bl=bl THEN RETURN [TRUE, i] ENDLOOP; RETURN[FALSE, 0]}; PartialMatch: ENTRY PROC [vp: LONG CARDINAL] RETURNS [BOOLEAN, CARDINAL] = { FOR i: CARDINAL IN [0..DataArraySize) DO IF Data[i].VpValid AND Data[i].vp=vp THEN { RpDirtyReg ← Data[i].RpDirty; RETURN [TRUE, i] } ENDLOOP; RETURN[FALSE, 0]}; }.