Heading:qjk40(635) Dragon memory bus protocoly756qjk40 Page Numbers: Yes X: 527 Y: 10.5"qjk40 Inter-Office Memorandumz18592l4445y762\f5b To DragonCore^ Date July 7, 1981z18592l4445d2998e21(0,65535)(1,4445)(5,11684)(6,14146)\f1 2f0t2 1t0 11t6 1f1t0 4f0t7 1t0 From Suzuki Location Palo Altoz18592l4445d2998y716e25\f1 4f0t2 1t0 6t6 1f1t0 8f0t7 1t0 Subject Dragon memory bus protocol Organization CSLz18592l4445d2998e25\f1 7f0t2 1t0 26t6 1f1t0 12f0t7 1t0 XEROX z18592l508y644e14(2116)\f2 5f0 Filed on: FILENAME.memoe30\12bi7BI2bi7BI Issuese30\b Locks in Cache Chip e18\i There are two processes, Processor Interface process and Memory Bus Interface process in the cache chip. Both run asynchronously and share the cache mechanism. Therefore, I assume that there is a locking mechanism to let only one process use cache mechanism at a time.e18j\i1I This introduces the poissiblities of deadlocks between Processor Interface and Memory Bus Interface. Since Memory Bus Interface always holds memory bus when it tries to acquire the lock on the cache, we have to make sure that Processor Interface does not have the cache lock when it tries to acquire memory bus.e18j Memory Bus Protocole30\b Fetch: (3 phases) 1. Arg: ra 2. Data: RealMemory[ra] 3. Data: RealMemory[ra+1] Exceptions: ParityError(Phases 2,3), RpOutOfRange(1)e18j(706)\82i11I Store: (3 phases) 1. Arg: ra 2. Data: Cache[loc].data[0] such that Cache[loc].rp=ra.rp and Cache[loc].b=ra.b 3. Data: Cache[loc].data[1] Exceptions: ParityError(2,3), RpOutOfRange(1) e18j\140i11I SFetch: (3 or 5 phases) 1. Arg: ra 2. Data: RealMemory[ra] 3. Data: RealMemory[ra+1] 4. Data: Cache[loc].data[0] such that Cache[loc].rp=ra.rp and Cache[loc].b=ra.b 5. Data: Cache[loc].data[1] Exceptions: ParityError(2,3,4,5), RpOutOfRange(1)e18j\198i11I WriteMap: (2 phases) 1. Arg: vp 2. Data: (flags, rp) Exceptions: Denied(1)e18j\55i11I ReadMap: (2 phases) 1. Arg: vp 2. Data: (flags, rp) Exceptions: NotReady(1)e18j\54i11I WriteMapFlags: (3 phases) 1. Arg: vp 2. Data: flags 3. Data: (oldFlags, rp) Exceptions: NotReady(1)e18j\79i11I SetMapDirty: (1 phase) 1. Arg: rp Exceptions: Denied(1)e18j\35i11I InvalidateVp: (1 phase) 1. Arg: rpe18j InvalidateRp: (1 phase) 1. Arg: rp. e18j\35G2g MemoryBusType: TYPE = RECORD[ body: SELECT OVERLAID * FROM Instruction => [Op: [0..377B], Arg: [0..77777777B]], Data => [Data: [0..37777777777B]], Exception => [ExceptionCode: [0..37777777777B]]]; IN Fetch, Store, SM, GMF, SMF, MemoryBus: MemoryBusType, Shared OUT MemoryBus, Shared GUARDIAN STATE Cache: ARRAY [0..CacheSize) OF RECORD [ data: ARRAY [0..DataSize) OF Word, vp: VirtualPage, b: PageOffset, rp: RealPage, flags: RECORD[ vaValid, raValid, ceDirty, shared, rpDirty: BOOLEAN]], Master, MemoryBusSuccess: BOOLEAN, Instruction, MemoryBusException, fetchLoc, victimLoc, storeLoc: [0..CacheSize) DATA FLOW CONTROL { victimLoc _ 0; REPEAT { Fetch^ -> FetchProc[] || Store^ -> StoreProc[] || SM^ -> SMProc[] || GMF^ -> GMFProc[] || SMF^ -> SMFProc[]} // {WHEN Init!: REPEAT { Shared _ FALSE; IF Master THEN { Master _ FALSE; MemoryBus.Op _ instruction; MemoryBus.Arg _ arg; NewPhase _ TRUE; NewPhase _ FALSE; SELECT instruction FROM Fetch => BusFetchMaster[]; Store => BusStoreMaster[]; SFetch => BusSFetchMaster[]; SetMapDirty => BusSetMapDirtyMaster[]; InvalidateVp => BusInvalidateVpMaster[]; InvalidateRp => BusInvalidateRpMaster[]; WriteMap => BusWriteMapMaster[]; ReadMap => BusReadMapMaster[]; WriteMapFlags => BusWriteMapFlagsMaster[]; ENDCASE} ELSE { WHEN NewPhase^:; SELECT MemoryBus.Op FROM Fetch => BusFetchSlave[]; Store => BusStoreSlave[]; SFetch => BusSFetchSlave[]; SetMapDirty => BusSetMapDirtySlave[]; InvalidateVp => BusInvalidateVpSlave[]; InvalidateRp => BusInvalidateRpSlave[]; WriteMap => BusWriteMapSlave[]; ReadMap => BusReadMapSlave[]; WriteMapFlags => BusWriteMapFlagsSlave[]; ENDCASE}}} } PROCEDURES -- SIGNALs FetchFinished: SIGNAL = CODE; StoreFinished: SIGNAL = CODE; SFetchFinished: SIGNAL = CODE; SetMapDirtyFinished: SIGNAL = CODE; InvalidateVpFinished: SIGNAL = CODE; InvalidateRpFinished: SIGNAL = CODE; WriteMapFinished: SIGNAL = CODE; ReadMapFinished: SIGNAL = CODE; WriteMapFlagsFinished: SIGNAL = CODE; --1) Bus Slave procedures BusFetchSlave: PROC = { success: BOOLEAN; loc: [0..CacheSize); LockCache[]; [success, loc] _ RpBMatch[MemoryBus.Arg]; UnlockCache[]; IF success THEN { LockCache[]; Shared _ TRUE; WaitNewPhase[]; MemoryBus.Data _ Cache[loc].data[0]; WaitNewPhase[]; MemoryBus.Data _ Cache[loc].data[1]; Cache[loc].flags.shared _ TRUE; Done[]; UnlockCache[] } ELSE {Done[]; DelayPhases[2]}; }; BusStoreSlave: PROC = { success: BOOLEAN; loc: [0..CacheSize); LockCache[]; [success, loc] _ RpBMatch[MemoryBus.Arg]; IF success THEN Cache[loc].flags.ceDirty _ FALSE; SetRpDirty[]; IF success THEN { WaitNewPhase[]; Cache[loc].data[0] _ MemoryBus.Data; WaitNewPhase[]; Cache[loc].data[1] _ MemoryBus.Data; Done[]; UnlockCache[] } ELSE {UnlockCache[]; Done[]; DelayPhases[2]}; }; BusSFetchSlave: PROC = { success: BOOLEAN; loc: [0..CacheSize); LockCache[]; [success, loc] _ RpBMatch[MemoryBus.Arg]; SetRpDirty[]; IF success THEN { Cache[loc].flags.ceDirty _ TRUE; Shared _ TRUE; WaitNewPhase[]; MemoryBus _ Cache[loc].data[0]; WaitNewPhase[]; MemoryBus _ Cache[loc].data[1]; WaitNewPhase[]; Cache[loc].data[0] _ MemoryBus; WaitNewPhase[]; Cache[loc].data[1] _ MemoryBus; Done[]; UnlockCache[] } ELSE { UnlockCache[]; Done[]; DelayPhases[2]; IF Shared THEN DelayPhases[2]}; }; BusSetMapDirtySlave: PROC = { Done[] }; BusInvalidateVpSlave: PROC = { i: [0..CacheSize); LockCache[]; FOR i IN [0..CacheSize) DO IF Cache[i].rp = MemoryBus.Arg THEN Cache[i].flags.vaValid _ FALSE UnlockCache[]; Done[] }; BusInvalidateRpSlave: PROC = { i: [0..CacheSize); LockCache[]; FOR i IN [0..CacheSize) DO IF Cache[i].rp = MemoryBus.Arg THEN Cache[i].flags.raValid _ FALSE UnlockCache[]; Done[] }; BusWriteMapSlave: PROC = { Done[]; IF Exception THEN RETURN; DealyPhases[1]; }; BusReadMapSlave: PROC = { Done[]; IF Exception THEN RETURN; DealyPhases[1]; }; BusWriteMapFlagsSlave: PROC = { Done[]; }; --2) Bus Master procedures BusFetchMaster: PROC = { WHEN EverybodyDone^: ; IF Exception THEN GOTO Failed; LockCache[]; IF Shared THEN Cache[fetchLoc].flags.shared _ TRUE; Cache[fetchLoc].data[0] _ MemoryBus.Data; BeginNewPhase[!ANY => GOTO Failed]; Cache[fetchLoc].data[1] _ MemoryBus.Data; BeginNewPhase[!ANY => GOTO Failed]; UnlockCache[]; MemoryBusSuccess _ TRUE; NOTIFY FetchFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY FetchFinished} }; BusStoreMaster: PROC = { WHEN EverybodyDone^: ; IF Exception THEN GOTO Failed; LockCache[]; Cache[storeLoc].flags.ceDirty _ FALSE; SetDirty[]; MemoryBus.Data _ Cache[storeLoc].data[0]; BeginNewPhase[!ANY => GOTO Failed]; MemoryBus.Data _ Cache[storeLoc].data[1]; BeginNewPhase[!ANY => GOTO Failed]; UnlockCache[]; MemoryBusSuccess _ TRUE; NOTIFY StoreFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY StoreFinished} }; BusSFetchMaster: PROC = { WHEN EverybodyDone^: ; IF Exception THEN GOTO Failed; LockCache[]; IF Shared THEN Cache[fetchLoc].flags.shared _ TRUE; Cache[fetchLoc].data[0] _ MemoryBus.Data; BeginNewPhase[!ANY => GOTO Failed]; Cache[fetchLoc].data[1] _ MemoryBus.Data; BeginNewPhase[!ANY => GOTO Failed]; IF Shared THEN { Cache[fetchLoc].flags.ceDirty _ FALSE; SetDirty[]; MemoryBus.Data _ Cache[fetchLoc].data[0]; BeginNewPhase[!ANY => GOTO Failed]; MemoryBus.Data _ Cache[fetchLoc].data[1]; BeginNewPhase[!ANY => GOTO Failed]; }; UnlockCache[]; MemoryBusSuccess _ TRUE; NOTIFY SFetchFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY SFetchFinished} }; BusSetMapDirtyMaster: PROC = { WHEN EverybodyDone^:; IF Exception THEN GOTO Failed; MemoryBusSuccess _ TRUE; NOTIFY SetMapDirtyFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY SetMapDirtyFinished} }; BusInvalidateVpMaster: PROC = { WHEN EverybodyDone^:; MemoryBusSuccess _ TRUE; NOTIFY InvalidateVpFinished }; BusInvalidateRpMaster: PROC = { WHEN EverybodyDone^:; MemoryBusSuccess _ TRUE; NOTIFY InvalidateRpFinished }; BusWriteMapMaster: PROC = { WHEN EverybodyDone^:; IF Exception THEN GOTO Failed; MasterPhases[1] MemoryBusSuccess _ TRUE; NOTIFY WriteMapFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY WriteMapFinished} }; BusReadMapMaster: PROC = { WHEN EverybodyDone^:; IF Exception THEN GOTO Failed; MasterPhases[1]; MemoryBusSuccess _ TRUE; NOTIFY ReadMapFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY ReadMapFinished} }; BusWriteMapFlagsMaster: PROC = { WHEN EverybodyDone^:; IF Exception THEN GOTO Failed; MasterPhases[2]; MemoryBusSuccess _ TRUE; NOTIFY WriteMapFlagsFinished; EXITS Failed => { MemoryBusExcpetion _ MemoryBus.ExceptionCode; MemoryBusSuccess _ FALSE; NOTIFY WriteMapFlagsFinished} }; --3) Processor Interface procedures FetchProc: PROC = { rp: [0..77777777B]; mapModified, rpDirty, success: BOOLEAN; entryLoc: [0..CacheSize); LockCache[]; DO [success, entryLoc] _ VpBMatch[vp, b]; IF success THEN {out _ Cache[entryLoc].data[w]; UnlockCache[]; RETURN}; [success, rp, rpDirty] _ VpMatch[vp]; SelectVictim[]; IF Cache[victimLoc].flags.ceDirty THEN VictimStore[victimLoc]; IF success THEN { Cache[victimLoc] _ [vp: vp, b: b, rp: rp, flags: [vaValid: TRUE, raValid: TRUE, ceDirty: FALSE, shared: FALSE, rpDirty: rpDirty]} ELSE { [flags, rp] _ ReadMap[vp]; Cache[victimLoc] _ [vp: vp, b: b, rp: rp, flags: [vaValid: TRUE, raValid: FALSE, ceDirty: FALSE, shared: FALSE, rpDirty: flags.dirty]}; mapModified _ MemoryFetch[vp, victimLoc, rp, b]; IF ~mapModified THEN EXIT; ENDLOOP; out _ Cache[victimLoc].data[w]; UnlockCache[]; }; StoreProc: [vp: VirtualPage, b: PageOffset, w: WordOffset, sData: Word] = { savedRp: RealPage; savedRpDirty, success: BOOLEAN; entryLoc: [0..CacheSize); LockCache[]; DO [success, entryLoc] _ VpBMatch[vp, b]; IF ~success THEN { [success, savedRp, savedRpDirty] _ VpMatch[vp]; IF ~success THEN {[flags, savedRp] _ ReadMap[vp]; savedRpDirty _ flags.dirty}; SelectVictim[]; IF Cache[victimLoc].flags.ceDirty THEN VictimStore[victimLoc]; Cache[victimLoc] _ [vp: vp, b: b, rp: savedRp, flags: [vaValid: TRUE, raValid: FALSE, ceDirty: FALSE, shared: FALSE, rpDirty: savedRpDirty]]; IF ~savedRpDirty THEN mapModified _ SetMapDirty[victimLoc, vp, savedRp]; IF mapModified THEN LOOP; mapModified _ SFetch[victimLoc, vp, savedRp] IF mapModified THEN LOOP; UnlockCache[]; RETURN }; Cache[entryLoc].data[w] _ sData; IF ~Cache[entryLoc].flags.rpDirty THEN { mapModified _ SetMapDirty[entryLoc, vp, savedRp]; Cache[entryLoc].flags.reDirty _ TRUE}; IF mapModified THEN LOOP; IF Cache[entryLoc].flags.shared THEN mapModified _ MemoryStore[vp, entryLoc]; IF ~mapModified THEN EXIT; ENDLOOP; UnlockCache[]; }; SM: PROC [mf: MapFlags, rp: RealPageNumber, vp: VirtualPageNumber] = { success: BOOLEAN; InvalidateVp[rp]; DO success _ WriteMap[mf, rp, vp] IF success THEN EXIT; ENDLOOP }; GMF: PROC [vp: VirtualPageNumber] RETURNS [mf: MapFlags, rp: RealPageNumber] = { [mf, rp] _ ReadMap[vp]; }; SMF: PROC [newMf: MapFlags, vp: VirtualPageNumber] RETURNS [mf: MapFlags, rp: RealPageNumber] = { DO [success, mf, rp] _ WriteMapFlags[newMf, vp]; IF success THEN EXIT; ENDLOOP}; --4) Processor Interface to Bus Interface communication VictimStore: PROC[victimLoc: [0..CacheSize)] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; instruction _ Store; arg _ rp; storeLoc _ victimLoc; Master _ TRUE}; WAIT StoreFinished LockCache[]; }; MemoryFetch: PROC[vp: [0..77777777B], victimLoc: [0..CacheSize), rp: [0..77777777B], b: [0..377B]] RETURNS [BOOLEAN] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; LockCache[]; IF ~(Cache[victimLoc].flags.vaValid AND Cache[victimLoc].vp=vp) THEN RETURN[TRUE]; UnlockCache[]; fetchLoc _ victimLoc; instruction _ Fetch; arg _ rp; Master _ TRUE}; WAIT FetchFinished LockCache[]; RETURN[FALSE] }; MemoryStore: PROC[vp: [0..77777777B], entryLoc: [0..CacheSize)] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; LockCache[]; IF ~(Cache[entryLoc].flags.vaValid AND Cache[entryLoc].vp=vp) THEN RETURN[TRUE]; UnlockCache[]; storeLoc _ entryLoc; instruction _ Store; arg _ Cache[entryLoc].rp; Master _ TRUE}; WAIT StoreAndCheckMapFinished LockCache[]; RETURN[FALSE] }; SetMapDirty: PROC[loc: [0..CacheSize), vp, rp: [0..77777777B] RETURN[BOOLEAN] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; LockCache[]; IF ~(Cache[loc].flags.vaValid AND Cache[loc].vp=vp) THEN { RETURN[TRUE]}; UnlockCache[]; instruction _ SetMapDirty; arg _ rp; Master _ TRUE}; WAIT StoreAndCheckMapFinished LockCache[]; RETURN[FALSE] }; InvalidateVp: PROC [rp: [0..77777777B]] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; instruction _ InvalidateVp; arg _ rp; Master _ TRUE}; WAIT StoreAndCheckMapFinished LockCache[]; }; WriteMap: PROC[mf: MapFlags, rp: RealPageNumber, vp: VirtualPageNumber] RETURNS[BOOLEAN] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; instruction _ WriteMap; arg _ rp; Master _ TRUE}; WAIT WriteMapFinished LockCache[]; RETURN[MemoryBusSuccess] }; ReadMap: PROC[vp: VirtualPageNumber] RETURNS [mf: MapFlags, rp: RealPageNumber] = { UnlockCache[]; DO RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; instruction _ ReadMap; arg _ rp; Master _ TRUE}; WAIT ReadMapFinished IF MemoryBusSuccess THEN EXIT; ENDLOOP; LockCache[]; RETURN[MapFlags, MapRp] }; WriteMapFlags: PROC[newMf: MapFlags, vp: VirtualPageNumber] RETURNS [success: BOOLEAN, mf: MapFlags, rp: RealPageNumber] = { UnlockCache[]; RequestArbiter _ TRUE; WHEN GrantArbiter^: { RequestArbiter _ FALSE; instruction _ WriteMapFlags; arg _ rp; Master _ TRUE}; WAIT WriteMapFlagsFinished LockCache[]; RETURN[MemoryBusSuccess, MapFlags, MapRp] }; --5) Cache operations RpBMatch: PROC [ra: [0..77777777B]] RETURNS [BOOLEAN, [0..CacheSize)] = { i: CARDINAL; rp: RealPage _ LOOPHOLE[ra, Ra].rp; b: PageOffset _ LOOPHOLE[ra, Ra].b; FOR i IN [0..CacheSize) DO IF Cache[i].rp=rp AND Cache[i].flags.raValid AND Cache[i].b=b THEN RETURN[TRUE,i]; ENDLOOP; RETURN[FALSE,0] }; VpBMatch: PROC [vp: VirtualPage, b: PageOffset] RETURNS [BOOLEAN, [0..CacheSize)] = { i: CARDINAL; FOR i IN [0..CacheSize) DO IF Cache[i].vp=vp AND Cache[i].flags.vaValid AND Cache[i].b=b THEN RETURN[TRUE,i]; ENDLOOP; RETURN[FALSE,0] }; VpMatch: PROC [vp: VirtualPage] RETURNS [BOOLEAN, RealPage, BOOLEAN -- rpDirty --] = { i: CARDINAL; FOR i IN [0..CacheSize) DO IF Cache[i].vp=vp AND Cache[i].flags.raValid AND Cache[i].flags.vaValid THEN RETURN[TRUE,Cache[i].rp, Cache[i].flags.rpDirty]; ENDLOOP; RETURN[FALSE,0,FALSE] }; SetRpDirty: PROC [rp: RealPage] = { i: [0..CacheSize); FOR i IN [0..CacheSize) DO IF Cache[i].rp=rp THEN Cache[i].flags.rpDirty _ TRUE ENDLOOP; }; SelectVictim: PROC = { victimLoc _ (victimLoc + 1) MOD CacheSize }; --6) Synchronization MasterPhases: PROC[number: CARDINAL] = { THROUGH [0..number) DO WHEN EverybodyDone^:; NewPhase _ TRUE; NewPhase _ FALSE ENDLOOP }; DelayPhases: PROC[number: CARDINAL] = { THROUGH [0..number) DO WHEN NewPhase^: Done[] ENDLOOP }; BeginNewPhase: PROC = { NewPhase _ TRUE; NewPhase _ FALSE; WHEN EverybodyDone^:; IF Exception THEN ERROR }; WaitNewPhase: PROC = { Done[]; WHEN NewPhase^: };e34(564)\f9G