MapProcessor.tiogaWrittenby:Sindhu,November23,19842:18:11pmPSTLastEditedby:Sindhu,June22,19855:24:24pmPDTTHEDRAGONMAPPROCESSORTheDragonMapProcessorDesignDocumentReleaseas[Indigo]Documentation>MapProcessor.tioga,.presscCopyright1984XeroxCorporation.Allrightsreserved.Abstract:ThismemodescribestheDragonMapProcessor,thedevicethatmapsvirtualaddressestorealandprovidesper-pagememoryprotectioninDragon.TheMapProcessor'smainfeaturesarefastresponsetomappingrequests;theuseofasmall,fixedfractionofmainmemoryformapping;thesupportofmultipleaddressspaceswithsharing;andanorganizationinwhichbothfunctionandperformancecanbeenhancedrelativelyeasilyafterinitialimplementation.XEROXXeroxCorporationPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,California94304ForInternalXeroxUseOnlyp_: g] gm)!f$)+[ g!W #(+ qYp gr NYpYp5qYprrYpYpeqYpprYpYpqYprYpYpksN gg"tI g uD gvD'17lw? gu?V !P# &Xx< gv<*Y"f$*-R 47+;>B: g d# )/ 7Z9q@lC91 g k ")7*07<9?RCv7 gfv%'t,.s39h>YAe5 g[}  #u)@,4 479@ 4; gy gv,A0 5,A/29L,A/47r,A/3 9t I g~$T TVm$dTHEDRAGONMAPPROCESSOR2Contents1.Introduction 2.TheAddressingArchitecture3.SystemOrganization4.SystemFunctions5.TheMapCache6.TheMapCacheController7.TheMapTable8.MiscellaneousIssuesAppendixA.SizeofBypassAreaAppendixB.LayoutofIOAddressSpaceAppendixC.FormatofMapEntriesAppendixD.NotationDRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'Ez^ g{[) XX) } U )} Q)}Nl)K) G)D) A1)0 M=)0^$:)0 7E)0 rG$l%(/;36^@TVm$THEDRAGONMAPPROCESSOR3 1.IntroductionTheDragonMapProcessorisasinglelogicaldevicethatimplementsthemappingfromvirtualaddressestorealandprovidesper-pagememoryprotection.Itsmainfeaturesare:fastresponsetomappingrequestsontheaverage(300ns);theuseofamaptablethatconsumesasmall(<1%),fixedfractionofrealmemory;thesupportofmultiplevirtualaddressspacesthatarepermittedtosharememory;andanorganizationinwhichbothfunctionandperformancecanbeenhancedrelativelyeasilyafterhardwareimplementation.Inspiteofthesefeaturesthedesignissimple.ThisdocumentbeginswiththeaddressingarchitecturesupportedbytheMapProcessor.ItthendescribestheMapProcessor'sorganizationintermsofitsthreecomponents:theMapCache,whichisacustomVLSIchip;theMapCacheController,whosefunctionalityisimplementedbyordinaryDragonprocessors;andthemainmemoryMapTable,whichstoresthevirtualtophysicalmappinginformation.ThefollowingsectionprovidesthefunctionalspecificationsfortheMapProcessor;italsoindicateshoweachfunctionisinvokedandwhereitisimplemented.Thenextthreesectionsdescribeeachofthecomponentsingreaterdetail,whilethelastsectionaddressesdesignissuesthatdonotfitelsewhere.ImportantinformationiscollectedtogetherintheAppendices. 2.TheAddressingArchitectureTheMapProcessor'saddressingarchitecturesupportsmultipleaddressspaces,withfixedsizepagesbeingtheunitofmappingandprotection.ThevirtualaddressesissuedbyeachDragonprocessoraremappedaccordingtooneofanumberofindependentaddressingcontexts,oraddressspaces.Foragivenvirtualaddressthemappingtoarealaddresscanbethoughtofasatwostepprocess,thefirststepbeingtodeterminetheaddressspaceinwhichthevirtualaddressmustbeinterpreted,andthesecondbeingtoperformtheactualtranslation.Beforewedescribeeachofthesestepsitisconvenienttodefinebasictermsandintroducesomeshorthandnotation.Apageisacontiguouschunkofmemory2s32-bitwordslong,alignedona2swordboundary;sisfixedat10.Inourdescriptionvirtualaddresseswillbedenotedbyva,realaddressesbyra,virtualpagesbyvp,realpagesbyrp,andoffsetsintopagesbyoffset.Bothvaandraare32-bitquantities,bothvpandrpare(32s)-bitquantities,andoffsetisans-bitquantity.Ifvpandoffsetarethevirtualpageandoffsetcorrespondingtova,wewillwriteva=vp|offset;similarly,wewillwritera=rp|offsetforrealaddresses.Fourflagsbitsarekeptforeachpage;thesewillbedenotedbyflags.Faultsassociatedwithaddressmappingwillbecommunicatedviaathree-bitorderfield.Thesizesofthesequantitiesareconstrainedinthearchitecturebytherelation||rp||+||flags||+||order||=32,where||x||isshorthandforilog2xj,thenumberofbitsneededtorepresentx.Addressspaceswillbedenotedbytheiraddressspaceid,aid,aquantityconstrainedby||aid||+||vp||=32.Processorswillbeidentifiedbytheirprocessornumber,pn.Figure1illustratesaddressmappingforprocesorpn.Recallthatthefirststepinvolvesdeterminingwhataddressspacetousefortranslatingagivenva.Forthisstepthe32-bitaddressspaceofeachprocessorisdividedupintotwonon-overlappingregions:a228wordsharedregionatthelowendoftheaddressspace,anda232-228wordswitchedregioncomprisingtherest.Ifvaliesinthesharedregiontheaddressspaceusedformappingisspace0,otherwiseitistheonecurrentlyloadedontheprocessor.Atmostoneaddressspacecanbeloadedonagivenprocessoratatime,butthesamespacemaybepresentsimultaneouslyondifferentprocessors.Theoveralleffectofthefirststepthereforeistomap(pn,va<31:28>)ontoaid.ThesecondstepDRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'Ez^ gC q[)%I "#',a03 ;I=CY gN#)/3 68<_AD~XW g!#l(u+.X03?5649X<?EV g aA"'*W/k1,6;@DFU g5 #}% -r/73]6 "d )$ 079 ;i> EM gx #' +4-13 58 A7CK gR#E"^&L),1N 8=? EJI g ! (+./17R:? C3H g! ),3O8(=@ F g ) #$'-039l:@6BES g X "n'-"0k2;4 <BC g,. $`(R+1-H/1 8? B g  z;f gC  q8)%  " *2p/88049q='88=@Dip6p gq6p(l]" # +2.2~8<>B4 g.!"%').s0\ 8{ ?oEP3! gUr!O"f'S)/v1)2V59<>CEf1z g w .#h$+f-2}67;=B*/ g *A"&(L-04 -W)3j (#'$() 026:\>,@+ gMrp++q+! "c#z *X.u05v|,=6&q+7:>B@* gh|*=q*&pR*q*V!4"%~'H) 050;>=?Ep(a gq (a(ahp(a(aq(a(a )$p&(a(a&q'](a(a(K+.p0(a(a1q21(a(a35:H=2ApC(a(aCqF8(a& gp&&pq&p&&q&J #mp&&&'Vq&(p+e&&+q&-// 6u =*p?&&@q&CE#p% gq %% e}p<%%q%p%%iq%V!#(T+.I2 ;p<%%=Eq=%%>@Cp#k gq #kp#kq^#kp#kq#k#k jp"#k#k#bq$#kp#k%sq&#kp#k'q#k*,/u 6O9<?~AD! gj"p$K!!$q'!!(-6 37,aC_& gpI&&q && D p &&!|q"&&"p%Q&&%q&&&&+& 14*5 <=A gpqZ)$ z &w(p./Jq0 16%9;>A\ g  Z3!u#& ,-p1l\\2q2\\369!;>CB* g )! # %(k278r;9q;'p>?"qB ge "%&r'wq(r)q+]p./mq4R8 ?BEpX gqXL Y%X)#,u.469;AC3D g.'[ %'+-269U;a?BC` g&Zl!\%()*$/ 8e:u@% b g5q uC!&(\*-p- b b.:q. b bp/ b b0eq1 b b16p9 b b:{q; b b<?D0rG$l%(/;36^ TVm$JTHEDRAGONMAPPROCESSOR4translatesvainthecontextoftheaidgivenbythefirststep.Thistranslationproducesra=rp|offset,whererpisobtainedbylookinguptheentrycorrespondingtoaid|vpintheMapTable.Thearchitecturealsoprovidesamechanismtobypasstheabovemapping.BypassingisneededtoprovideawayforprocessorstoaccesstheMapTableandmap-faulthandlingcodewithoutgettingmapfaultsintheprocess;itisalsousefulinturningoffmappingaltogether.Bypassinggetsactivatedwheneveraprocessormakesareferencetoaportionofvirtualaddressspacecalledthemapbypassarea.Thisareaappearsatthesamelocationsinalladdressspaces,andisdefinedbythree(32s)-bitquantitiesBypassMask,BypassPattern,andBypassBase.Themaskandpatterndeterminethebypassarea'slocationandsizeinvirtualmemoryasfollows:avaisdefinedtobeinthebypassareaifthebitsofvaunderBypassMaskmatchthecorrespondingbitsofBypassPattern.BypassBasedeterminesthestartinglocationoftheareainrealmemory.Therealaddressproducedbybypassmappingisra=rp|offset,whererp=(BypassBase.BypassMask)V(vp.~BypassMask).Themask,patternandbasecanallbemodified.Thisarchitectureisdesignedtofacilitatesharingbetweenaddressspaces.Thesharedareaprovidesarestrictedformofsharingwhereallofthevp'ssharingaparticularrpmustbeidentical;thissharingisalsoall-or-nothinginthatapageissharedbyallspacesifitissharedbyany.Itisexpectedthatallbutafewcasesofsharingwillbecoveredbythisrestrictedmechanism.Thearchitecturealsopermitsmoregeneralsharinginwhichthevp'ssharingaparticularrpareunrestrictedandwhereeachpagemaybesharedbyanysubsetofthespaces.3.SystemOrganizationTheMapProcessorconsistsofthreecomponents(Figure2):acustomVLSIMapCache,aMapCacheController,andaMapTablekeptinmainmemory.TheMapCacheissimplyaperformanceacceleratorthatsitsbetweenprocessorcachesandtheMapTable.Itcontainsaround1200mappingentriesandallowsmappingrequeststhathittobeservicedinthreecycles,or300ns.Processorcachesthemselveskeepalimitednumberofentries(~50),sotheMapCacheisreallyasecondlevelcache.Whenamapmissoccursinaprocessorcache,thecachefiresoffamappingrequesttotheMapCache.TheMapCachereturnstheentryifitispresent,andsignalsamapfaultifitisnot.Thisfaultisthenhandledbytheprocessorattatchedtothecachethatgotthemapmiss.AsmalltableintheMapCacheisusedtodeterminetheaddressspaceinwhichthereferencesforeachprocesssorshouldbemapped(thefirststepofthemappingprocessdescribedinthelastsection).TheMapCachealsoimplementsanumberofotheroperations,includingonestoflushentries,tomanipulatethecontrolbitsforentriesinprocessorcaches,toswitchaddressspaces,andtocontrolthelocationandsizeofthemapbypassarea.AllcommunicationwiththeMapCacheoccursovertheM-Bus.TheMapCacheControllerisafictitiousdevicewhosefunctionalityisimplementedbyordinaryDragonprocessors.Asexplainedabove,whenevertheMapCachemisses,theprocessorwhosecachegotthemissfieldsthemapfault.ThisprocessorplaystheroleoftheCacheControllerinfetchingthemissingentryfromtheMapTableandshippingittotheMapCache.Inadditiontoservicingmisses,theControlleralsoimplementsacompletesetofoperationsformanipulatingtheMapTable.Thecodefortheseoperationsisavailabletoallprocessorsandcanbeexecutedbyanyoneofthem.ThissplitinfunctionalitybetweenMapCacheandControllerforcesustofreezeinhardwareonlythatportionofthedesignwhichisnecessaryforspeed,leavingtheremaindertobeimplementedbyordinaryDragoncode.Asaresult,enhancementsinbothfunctionandperformancecanbemaderelativelyeasily.Forexample,thestructureoftheMapTablecanbeleftcompletelyopensincethehardwarehasnoknowledgeofit.DRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'Eq_/ g p_/_/^q_/ p#~_/_/$/q_/&*!,o/"2M6: A6p] gq ]p]q1]p]q]]p]]:q]|!#(*-K0 9p;]]<\q=p]p]=q]?A`C[ gYe) q6!"*+02m6grD@CEV g<$H qV*g039?ATo g!&4+3.3p5|ToTo68<q?cToTo@DR gkU &"&+|.,/46~: @ pQ! g qQ!Q!pQ!Q!| qQ!Q!p ZQ!Q!!Mq'Q!Q!(e+0.1a6<>C>Oy g}=n"$)p+9OyOy+qOy-.35s7x9:;@2C?DM gZpeMMqMpMMqM $x') 0r3ep5pMM6c q=MMp?MM@qL+ g -G "%'(P*/-369>EJ gYpJJ,qJpJ=qrJpJqJJp#JJ$&q$JJ&p'JJ( q-JpJ.4 q5JJ}6gJqJ8%p8JJ99q:BJpJ;J qBJJCD<H gRn^!OFa)K J!" (^-:27<?DD g5 z$(+- p/DD0Dq0DD1L279 p?DD@qDA|E#C g |) Y '(+,05168&:">h?A6BAk ga{ #B$'c+,146<">IA ? g  "'+f0g5i7E;p>??>q?Z???@E> g p>>!q>V 5 %(6+|.0q469s=?[Az7 gC q40)Kk m"(% -a2M4v5:b>AaE2 g "v&k)+[.5]8I;?AfE0 g  !['-L147Y:@A/: gN\!%$*02468l=?JB- gM5 %)-*y/N46x; ?eALC+ g#'),9/\35b6<@CH*D gi[#!$Q)C,/H3j8:c=??@A( g l-"}%(*=-c247 =CD& g4b b$'i)+x.24[79G?B*%N g ) I#] ).70 5<7:=z?AX# gn?%J(U+0030 :<)ACu" g do;!&d( /(16(8:?\A X g)EH #%*Y,2#479<?9C g m!-%\),/6)7 "# ).M2 :< E g  &8*}026:0>A gZ:!##'+.58;f>f@RB@ g R!B$(3*-14_9;G<?LB g=h)"2 (+ 34P:>" D g O"%(0+ 249;= D]J g,WN^D!7&)e,. 6D g !# ,.4:7?ApB T g m5 " +-/3 9>~AC gZJ|H!#% ,0@35;>>@/  g rG$l%(/;36^ pTVm$THEDRAGONMAPPROCESSOR5ThefinalcomponentistheMapTable.Itservesastherepositoryformappinginformationforalladdressspaces,mapping(aid,vp)torp.Foreachrealpagethetablealsomaintainsfourflagbitsusedforpagingandmemoryprotection;inhightolowordertheseare:shared,wtEnable,dirty,andspare.NotethatthisorderiscompatiblewithED'sorderwhichis:spare,wtEnable,dirty,andreferenced.TheMapTablestoresinformationonlyaboutpagescurrentlyinmainmemory,andisstructuredasahashtableindexedby(aid,vp).Thisallowsthetabletofitinasmall,fixedfractionofmainmemory(<1%),incontrastwithdirectmapschemes.Theseschemesconsumetablespaceproportionaltoallofvirtualmemoryortothefractionbeingusedfrequently,dependingonhowtheyareimplemented.Assumingthatthehashfunctionspreadsthingsproperly,theaveragetimetoaccessthetablewillbequitegood.Theworstcasetime,however,dependsonhowcollisionsareresolved.Initially,linearchainingwith"movetofrontonaccess"willbeused;ifthisturnsouttobeaperformanceproblemtheschemewillbemodifiedtouseatreestructure.DragonprocessorsaccesstheMapTabledirectlyviathemapbypassarea.4.SystemFunctionsThissectiondescribesthefunctionsimplementedbytheMapProcessor.MapCachefunctionsaretakenupfirst,followedbyCacheControllerfunctions.Thedescriptionforeachfunctionincludesitsspecification,themethodusedforinvokingit,andmiscellaneousinformationrelevantlargelyonlytotheimplementor.4.1MapCacheFunctionsTwooftheMapCachefunctionsareinvokedviathededicatedM-BustransactionsReadMapSetRefandReadMapSetRefSetDirty,whiletheremainderareinvokedbyIOReadFlowandIOWriteFlow.Fortheformertwotheaddressportionofthetransactionisrestrictedtobeintherange[0..225).Forthelattertwoitisrestrictedtobeintherange[0..3*225).ReadMapSetRef(pn:ProcessorNumber,vp:VirtualPage)Returns(rp:RealPage,order:Order,flags:Flags)ReadMapSetRefreturnstherealpagerpandflagscorrespondingtoagivenvirtualpagevp;themappingisperformedinthecontextoftheaddressspacecurrentlyloadedonprocessorpn,sayaid.Ifthereisnoentryfor(aid,vp)intheMapCacheamapfaultissignalledbysettingtheorderbitstoindicatepagefault.ReadMapSetRefisusedbyprocessorcacheswhentheygetamapmisswhileservicingaprocessorread,soitsspeedisimportantforgoodsystemperformance.Invocation:ReadMapSetRef(MAdrs).MAdrs[0..6]=0;MAdrs[7..28]=vp;andMAdrs[29..31]=xxx;pnisderivedfromthenumberofthecurrentM-Busmaster.Results:returnedviaDone(MAdrs,MData).MAdrs[0..21]=rp;MAdrs[22..24]=xxx;MAdrs[25:27]=order;MAdrs[28:31]=flags;MData[0..21]=rp;MData[22..24]=xxx;MData[25:27]=undefined;MData[28:31]=flags;Ifvpliesinthemapbypassareathevaluesforflagsare:shared=FALSE,wtEnable=TRUE,dirty=TRUE,andspare=FALSE.ImplementationNotes:NotethatMAdrs[29..31]forReadMapSetRefisnotinterpretedbutisturnedaroundasMAdrs[22..24]andMData[22..24]forDone.ReadMapSetRefSetDirty(pn:ProcessorNumber,vp:VirtualPage)Returns(rp:RealPage,order:Order,flags:Flags)DRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'Eq_/)9#+')@-B.1: 79? ] g| p A]] q"]]p"]]#{q$,]]%(p&]]'Zq( ]])i,/D15?7;=D[ g# )+.02659pZ9Z9?_|AZ9Z9ArFJZ9qX g-b1 !x$(P, 13q6<?6@ V g0tNp0VVqVVp VV!q"6VV"$E'z+.=135s7<8<@*E[UC gC #'*04:I?C_S g xI\8$F&-'*/37 >&EQ gQF w#&p(+166:?BPM g0 $F(+/26X?@ KW gg  k!%*,p/%KWKW0;2 6cq8KWKWzD gCqAi)w V& /=1407 ?SB? gr#%) 0 7:z AC> g #(+#-@24^6 ? 2 g y&"$'%,025 <=t CtE#0 gu?r1kq0Q"E$&G' -/_1P25^9(r1k<q0>~- g p:--$A& . 5<4@6+Z gq( ) ) }#(p&c( ( &q( (p*( ( ++q( - 68z9=AApD( ( EfqF( &c gc %'R).2S81<>pD&c&cEyqF7&c$ gp$$q$$ -U p!$$!q"$$p#$$$^q%$$&'*<-126"9j:@B# gd" -Q.139>AD!m g gWFaa#J&(,)-.5 7:g> ))ss$$zzocst) 36u pAqB\D]J g pJJpqJ"%z'-.15:n)e )1e1e[e["ec"eoex &, 69T D' g p'GqK'' p'&q)''+t 58 D g   p'q*+p-&-q/13L58=k@uB gp0qmr8qpq$r%q)p)*q,r.eq12mp5$5q8)r9q=))]*]]c]]*]]uu]<o<]]PoP]c]""]].#.]PP] o ]zz]  ]]]!## ,/' 9;={ D g D !$P -:/w~f gpOff5)V+ 3 :AI 1 g_rG$l%(/;36^ TVm$GTHEDRAGONMAPPROCESSOR6ReadMapSetRefSetDirtycheckswhetherwritesarepermittedforvirtualpagevpintheaddressspacecurrentlyloadedonprocessorpnandreturnsthe(rp,flags)iftheyare.ThisfunctionisinvokedbyacachewhenitsprocessortriestowriteintoanentrywhosewtEnablebitisnotset.IfboththedirtyandthewtEnablebitsforthisentryaresetintheMapCache,theinvokingcacheispermittedtodothewrite,otherwiseawriteprotectfaultissignaled.Iftheentryisnotpresentinthefirstplace,amapfaultissignalled.Invocation:ReadMapSetRefSetDirty(MAdrs).MAdrs[0..6]=0;MAdrs[7..28]=vp;andMAdrs[29..31]=xxx;pnisderivedfromthenumberofthecurrentM-Busmaster.Results:returnedviaDone(MAdrs,MData).MAdrs[0..21]=rp;MAdrs[22..24]=xxx;MAdrs[25:27]=order;MAdrs[28:31]=flags;MData[0..21]=rp;MData[22..24]=xxx;MData[25:27]=undefined;MData[28:31]=flags;Ifvpliesinthemapbypassareathevaluesforflagsare:shared=FALSE,wtEnable=TRUE,dirty=TRUE,andspare=FALSE.ImplementationNotes:NotethatMAdrs[29..31]forReadMapSetRefisnotinterpretedbutisturnedaroundasMAdrs[22..24]andMData[22..24]forDone.ReadEntry(pn:ProcessorNumber,vp:VirtualPage)Returns(rp:RealPage,order:Order,flags:Flags)Letaidbetheaddressspacecurrentlyloadedonprocessorpn.ReadEntryreturnstherpandflagscorrespondingto(aid,vp)intheMapCache;iftheentryisnotinthecacheamapfaultissignaled.ThisoperationmaybeusedtoverifythecontentsoftheMapCache.Invocation:IOReadFlow(MAdrs).MAdrs[0..6]=0;MAdrs[7..28]=vp;andMAdrs[29..31]=xxx;pnisderivedfromthenumberofthecurrentM-Busmaster.Results:returnedviaDone(MAdrs,MData):MAdrs[0..24]=undefined;MAdrs[25..27]=noop;MAdrs[28..31]=undefined;MData[0..21]=rp;MData[22..24]=xxx;MData[25:27]=noopifentryisincache,otherwisepagefault;MData[28:31]=flags.Ifvpliesinthemapbypassareathevaluesforflagsare:shared=FALSE,wtEnable=TRUE,dirty=TRUE,andspare=FALSE.ImplementationNotes:WriteEntry(pn:ProcessorNumber,vp:VirtualPage,rp:RealPage,flags:Flags)Letaidbetheaddressspacecurrentlyloadedonprocessorpn.WriteEntryputstheentry(aid,vp)_(rp,flags)intotheMapCache.ThisoperationisusedbytheCacheControllertoreturnanentrytotheMapCacheafteramiss.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=0;MAdrs[7..28]=vp;MAdrs[29..31]=xxx;MData[0..21]=rp;MData[22..24]=xxx;MData[25:27]=don'tcare;MData[28:31]=flags.ImplementationNotes:FlushEntry(aid:AddressSpaceId,vp:VirtualPage)FlushEntrycausestheentrycorrespondingto(aid,vp)toberemovedfromtheMapCache.Iftheentrywasnottheretobeginwith,theoperationhasnoeffect.Notethatthisoperationdoesnotdisturbany(aid,vp)entriesinprocessorcaches;anexplicitChangeFlagsmustbedonetoflushtheseout.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=1;MAdrs[7..28]=vp;MAdrs[29..31]=don'tcare;MData[0..21]=don'tcare;andMData[22..31]=aid.DRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'Eq_/)#f(-)/6:8=Dp@_/_/A_q_/BD] gcn "Mp(]])?q]*-2w5p5~]]6q6]]p7]]8,q:u]];=0@nC[ gv#%+.04K779<<pA([[BqZ9 g *spZ9Z9qZ9 "p%LZ9Z9&4qZ9+E-0<268;<?:BX g _""$<&*025:e=?6EV gZ;!%' *%-a. )T)ToTTosTsTo$T$ToTTozTzToToToTcToTToTToToTos- 8` pAuToToBqBToToD]R g pRRpqR"%z'-.15:n)O )PL1O1PLOPL[O[PL"Oc"PLOoPLOPLPLPLx &, 69T DN g pNGqKNN pN&q)NN+t 58 DL g L  pL'q*LL+p-&LL-qL/13L58=k@uBKV gpKVKV0qmKVrKV8qKVKVpKVKVq$KVrKV%q)KVKVp)KVKV*q,KVrKV.eq1KVKV2mp5$KVKV5q8)KVrKV9q=KVKV)Hr)HHr*HHrHHrcHHrHHr*HHrHuHruHa)p>a>anq>a!\'N+-p4!>a>a4q5>a>a7>BpE[>a>aEq< gp1<<q< Jp<<sq<

BC; gB\ #%z(*e.P067:7=~)8.)88.8s8.s8$8.$88.8z8.z88.o88.c88.88.888sp$ . p7888gq988:< 6 gpv66&q6i1"$u&+0%)4  )4u14 14u4 4u[4 [4u"4 c"4u4 o4u4 4u4u4uxy %+ 5 < 2 g G " ,}/ 9< p1& gq1&1&|!$( p21&1&2q41&1&6p71&1&8q1&9D;=H?B/ g`+fp2//q!/r/#Tq&//p'//(q-7/r/.q1//p2//3Pq5M/r/6q9//:p=m//=q@q/r/AqEp//),)-,*-,-,c-,-,*-,-u,u-<,o<-,-P,oP-,c-","-,-,(,#(-K,K-,o-u,u-,---~) g p))!'#p +U-37q&e)p&e&efq&e  vm!0'+-p3&e&e4q5F&e&e6 >AC$ gp $$ q$$p$$%q$$}$q$pv$$q$$p$$qG$$N/"(+(1[268:> Ee# g(n!$&) 2)  2 s 2s $ 2$  2 z 2z  2o  2c  2  2 sd%p*{ q- / 7:? pD EfqF  g  $|'& 15A ?CM g p|MMq3MM)h)h*hhchh*huhu<ho<hPhoPhc"h"hh(h#(KhKhouhuh~ g px: [" q3) T m )]+p+~33,/q-B33p.33.q/c330Z239<?NB g b="f%(R.1 37;a><@ gDpnqpWq#$*/x1a6. >WAC= g) Y)  Y s Ys $ Y$  Y z Yz  Yo  Yc  Y  Y sd%- 7:? pD EfqF  g E 'G*.B0 p;D  ;q=  rG$l%(/;36^ wTVm$ 6THEDRAGONMAPPROCESSOR7ImplementationNotes:FlushSpace(aid:AddressSpaceId)FlushSpacecausesentriesforspaceaidberemovedfromtheMapCache.Iftherearenoentriesforthisspacetheoperationhasnoeffect.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=2;MAdrs[7..9]=0;MAdrs[10..31]=don'tcare;MData[0..21]=don'tcare;andMData[22..31]=aid.ImplementationNotes:FlushCache()FlushCachecausesallentriestoberemovedfromtheMapCache.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=2;MAdrs[7..9]=1;MAdrs[10..31]=don'tcare;andMData[0..31]=don'tcare.ImplementationNotes:ChangeFlags(rp:RealPage,order:Order,flags:Flags)ChangeFlagsprodstheMapCacheintoexecutingaDoneM-Buscommandwiththespecifiedparameters.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=2;MAdrs[7..9]=2;MAdrs[10..31]=don'tcare;MData[0..21]=rp;MData[22..24]=xxx;MData[25:27]=order;MData[28:31]=flags.ImplementationNotes:NotethatChangeFlagsshouldnotbeusedtosetwtEnableinprocessorcachesaslongaswepermitdifferentaddressspacesbecausewtEnablemayhavedifferentvaluesforthesamepage(thisishighlydesirable,eg.foradebugger).AlsonotethatitisnotnecessarytokeepboththewtEnableanddirtybitsintheMapCache;asinglebit,wEd,whichtracksthelogicvaluewtEnable&dirtyissufficient.However,bothbitswillbekeptsotheycanbereturnedforIOReadsfromprocessors.WriteSpaceRegister(pn:ProcessorNumber,aid:AddressSpaceId)WriteSpaceRegisterwritesaidintothespaceregisterforprocessorpn.Notethatthisoperationdoesnotinvalidatethemapentriesinpn'scaches;thisshouldbedoneinsoftwareviaDeMap.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=2;MAdrs[7..9]=3;MAdrs[10..31]=don'tcare;MData[0..21]=don'tcare;MData[22..31]=aid;pnisderivedfromthecurrentM-Busmaster.ImplementationNotes:ReadSpaceRegister(pn:ProcessorNumber)Returns(aid:AddressSpaceId)ReadSpaceRegisterreturnsthecontentsofthespaceregisterforprocessorpn.Invocation:IOReadFlow(MAdrs).MAdrs[0..6]=2;MAdrs[7..9]=3;andMAdrs[10..31]=don'tcare;pnisderivedfromthecurrentM-Busmaster.ImplementationNotes:DRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'E)^q)_/^*_/^_/^c_/^_/^*_/^_/u^u_/<^o<_/^_/P^oP_/^c_/"^"_/^_/^(^#(_/K^K_/^o_/u^u_/^_/^y_/_/_/~[ g p5[[pqX) C!p%HXX%qX')/M25&8v=?BEV gk!$i&p)T)ToTTosTsTo$T$ToTTozTzToToToTcToTToTToToTos:'0% ;[ EfR g E 'G*.B0 p;DRR;q=RR)O)PLO*PLOPLOcPLOPLO*PLOPLuOuPL1c3p:B##:q;##=A]Dr! g ` #(2p)!!*q+F!!+,1`38m:V=?fD U g)p)psps$p$pzpzpopcpps&1. 8;[ Ef3 g G 'J*.H p8339Dq:X33p;V33<q3=J>C g))*c*uu<o<PoPc""(#(KKouuyp~  p`F& .Pqr)"-')U+/i4H6p<rr=Iq>rr))ss$$zzocsy$ -/e 8U: < P gpc P Pq PV!}&G*) k)  k*  k  kc  k  k*  k u ku < ko<  k P koP  kc " k"  k  k( k#( K kK  ko u ku  k  ky rG$l%(/;36^TVm$ THEDRAGONMAPPROCESSOR8WriteBypassRegister(reg:[BypassMask,BypassPattern,BypassBase],value:(32s)BitQuantity)WriteBypassRegisterwritesvalueintothebypassregisterreg.Recallthatthecontentsofthebypassregistersdefinethelocationandsizeofthemapbypassareabothinvirtualaddressspaceandinrealmemory.OnpoweruptheBypassMaskregisterissetto0whichcausestheMapCachetoimplementtheidentityfunction.Invocation:IOWriteFlow(MAdrs,MData).MAdrs[0..6]=2;MAdrs[7..9]=4;MAdrs[10..29]=don'tcare;MAdrs[30..31]=reg;MData[0..21]=value;MData[22..31]=don'tcare.ImplementationNotes:ReadBypassRegister(reg:[BypassMask,BypassPattern,BypassBase])Returns(value:(32s)BitQuantity)ReadBypassRegisterreturnsthecontentsofbypassregisterreg.Invocation:IOWriteFlow(MAdrs).MAdrs[0..6]=2;MAdrs[7..9]=4;MAdrs[10..29]=don'tcare;MAdrs[30..31]=reg.ImplementationNotes:4.2CacheControllerFunctionsTheMapCacheControllerprovidestwointerfaces:onetoservicerequestsfromtheMapCacheandtheothertoservicerequestsfromDragonsoftwaretomanipulatetheMapTable.Functionsinthetwointerfaceshavedifferentspeedrequirements,andarealsoinvokeddifferently.TheMapCacheinterfacefunctionsmustberelativelyefficientsincetheyareinvokedfrequently,whiletheMapTablefunctionsarenotascritical.TheformerareinvokedviatrapsinitiatedbytheMapCache,whilethelatterareinvokedviaprocedurecalls.ThefirsttwofunctionsbelowbelongtotheMapCacheinterface.TheremainderbelongtotheMapTableinterface.HandleMapFault(aid:AddressSpaceId,vp:VirtualPage)HandleMapFaultiscalledwhenthereisamissintheMapCache.Itfirstchecksiftheentryfor(aid,vp)isintheMapTable.IftheentryisthereitissenttotheMapCacheviaTakeEntry,otherwiseapagefaultissignaled.Invocation:viamapfault.ImplementationNotes:HandleWPFault(aid:AddressSpaceId,vp:VirtualPage)HandleWPFaultiscalledbytheMapCachewhenitisservicingaMapForWriterequestandfindsdirty&wtEnableFALSE.Itfirstchecksifthewriteprotectfaultisrealorsimplyaresultofthisbeingthefirstwritetotheentry'spage.Ifitisreal,awriteprotectfaultissignaled,otherwisethedirtybitfortheentryissetintheMapTableandtheupdatedentrysenttotheMapCacheviaTakeEntry.DRAGONPROJECTFORINTERNALXEROXUSEONLYqg'or Vg'g'!<qg'"zr#g'g'$mqg'(xr)g'g'*qg'+r,g'g'-rvg'E~_* gp_*_*H $ - 59q[)p *[[ q[#&)9-p2[[3@q4[[6:q=Y?E[Z4 gGY$'W* +.21U58<=B*X g8V)ypVVqV!&')+,0475:n>@/Tj g)Q)QQQsQsQ$Q$QQQzQzQQoQQcQQQQQQQs&1. 8;[ EfPG g PGz p(`PGPG(q*0PGPG+H p4PGPG5q8PGPG9 CN g)K)L%K*L%KL%KcL%KL%K*L%KL%uKuL%A. g ~#B)#,n.B 49S<?A, g cx &(+h-2o5G9<,AnC+W g&l!$')/11n7()!&(F*.2R 8;B'4 gu ~# g p###&@ q ) #'(()-1.1{4:&;>C6D gkpqp9qL!%&'*(-/Z24l58:=/@DG g !Y")b)bsbs$b$bzbzbobcbbsq))Q*QQcQQ*QQuuQ<o<QQPoPQcQ""QQ(#(QKKQoQuuQQyQQQ~ g p"]#~% q) ~!7#'+f/902789W B? g@p  } p r q   "+#&+E,/H27;<?sAYEd gS W "!$n(,.5/x0348M<@ Ad gc>"$S&{(4*-147 VBAE[ g gY"L%O(*D.01v~W gpWW6 "a *g 18 ;qTo)](p *ToTo q!ToTop"ToTo#+q#ToTo$ -`/w15R9>@BaR gpCRRqRwNpRR:qR "$R^$R%R^%R&TR^&TR'R^c'R'~R^c'~R'R^'R(|R^c(|R(R^o(RRR).2pR4qR7 ;:>@C_Q gD # ,.Rp.Q Q /{q0Q Q p1kQ Q 2q2Q Q 347;`>@)N;)NN;NsN;sN$N;$NN;NzN;zNN;oNN;cNN;NN;NNNsq1)K)L*K*L*KL*KcL*KL*K*L*KL*uKuL*B@C gApCCkq~CCp[CCqCCf #)0*Z-H02G)A)AiAAisAsAi$A$AiAAizAzAiAoAiAcAiAAiAAiAiAisq1)>)>>*>>>>c>>>>*>>>u>u><>o<>>>P>oP>>c>">">>>>(>#(>K>K>>o>u>u>>>>y>>>~; g p;;SP #q8P) B"&q),t/339;^? 6 g 4$(L,.f04)7*9>"@C5 g|7%}' 015:;?|BD3Z gx1 :#N)p,-143(58 @| 1 g).)/8./8s.s/8$.$/8./8z.z/8.o/8.c/8./8./8/8/8sq1),S),,S*,,S,,Sc,,S,,S*,,S,u,Su,<,So<,,S,P,SoP,,Sc,",S",,S,,S(,S#(,K,SK,,So,u,Su,,S,,Sy,,,~)n g p)n)n #> +D5Lq&)J{{# ,p-&&.{q/&p&/q&15-7:?B$w gPp%$w$wq$wp$wAq$w!$*-102369=? " gay! p#J""#q% "p"%fq"'5* ,m)) U Uss U$$ U Uzz Uo Uc U U U U Usq1)p)p*ppcpp*pupu<po<pPpoPpc"p"pp(p#(KpKpoupuppyz< gCq)) $',/,5:>AF gt D!%$&j(-1369=@BIEe g!f#&(*#-b.0 9:<@,D gT!%&r(+ 0l3D6S9>@fB P g h )g ${&*036N;> EerG$l%(/;36^TVm$ THEDRAGONMAPPROCESSOR10simpleimplementationandgoodperformance.Thefirstisthatthecacheispure:anentryisnevermodifiedwithinthecacheonceithasbeenreadin;ifmodificationsneedtobemade,theentryisflushedfromthecache,modifiedintheMapTable,andreadinagain.Themostimportantconsequenceofthisisthatthecachecanholdmanymoreentriesbymakinguseofdynamiccells.Thesecellsaresmallerthanstaticones,butalsomuchmorepronetoalphaparticlehits.However,sincethecachenevercontainsirreplaceabledata,wedon'tneedtoworryaboutcorrectingerrorswecangetawaybysimplydetectingthemandflushingerroneousentries.Anotherconsequenceisthatentriesneverneedtobewrittenthroughorwrittenback,makingthecontrolportionsofthechipsimpler.Thesecondaspectofthedesignisthatthecachefunctionsasaslavetootherdevices.ThusitneverhastoarbitratefortheM-Bus,andallofitsinteractionswiththebusaresimple.ThisminimizesthecontrollogicneededforinterfacingtotheM-Bus.5.1M-BusInterfaceDuringnormaloperationtheMapCachecommunicateswiththeoutsideworldexclusivelyovertheM-Bus.TheonlyM-BustransactionsrecognizedareIOReadsandIOWritesdirectedtotheappropriateportionofIOaddressspace.Asnotedabove,theMapCachealwaysoperatesasaslavetosomeotherdeviceontheM-Bus(usuallyaprocessorcache),soitneverhastoarbitrateforthebus.TheonlyM-Bussignalsitusesareshowninthetablebelow.SignalDirectionUseMCmdAB[0..4)M<>CrecognizeIOReadandIOWrite,executeIODoneandChangeFlagsMDataAB[0..32)M<>Creadfunctionnameandparameters,returnresultsMaster[0..6)M>CreadM-BusmasterMGntM>Ctellwhenmastershipisgranted5.2StructureTheMapCachechipconsistsofthefollowingparts:M-Businterfacelogic,controlregisters,anaidarray,acachearray,victimselectlogic,refreshlogic,andD-Businterfacelogic.5.2.1M-BusInterfaceLogicThisinterfacelogiccontains:paddriversandreceivers;circuitrytodoaddressmatching;latchestoholdMCmd,IOAddress,IOData,andIODoneresponse;arraybypasslogicthatimplementsidentitymapmodeaswellasmapbypassareaaddressing,andacontrolunitthatsteersthevariousoperations.5.2.2ControlRegistersThecontrolregistersstoreglobalmappinginformation,whichincludesidentitymapmodeandMapBypassBase.5.2.3AidRegistersThisisasetof2||pn||registersof||aid||bitseachthatgivethemappingbetweenprocessorsDRAGONPROJECTFORINTERNALXEROXUSEONLYqg' rg'g' qg'"r#6g'g'$ qg'(r)jg'g'*>qg'+jr,;g'g'-vg'Eq_/ g !- *:-(014}6:p_/_/?AE] g*= [#$'X*-/1; 9=>@D[ g,q!V'd)C+/K369;@CZ9 g b #&(*,/37V;=BE[X g"c H%;(,A/259=XAzCTV gA& v$2'-? 5J8:>2ACUC g -c!+#'i).M4r87;*@S g: G #( +/B027<>CuQ gk3 "%+.3J79^;@DADPM gDTN"7'+,03W5:<?mD\N gs ["%9*.(47vBEe? g)$s(*9-2/357;J: g:!:+ir8R g 8R!"%,8R+h0M4y66+h/`35 4/ g 4/!"%,4/+h-2F5E7r 2+h.0 g 0 !"$0 +h-1- g-!"$-+h-N0E 56{*B gq&)*IK!<"%7+:/ 39<AY %L gWb!%P(-1?38F=p! g3q)_ !$Y)+ 279t;@ g5) #),18);@DF` g . !$&).I1U 8;N<AODF g2Y pi gq) 5#) 1|5;@C>s g p$ gBq )Jr T| T Tr8 T Tq Q!#}p$- $q% &I'-)-/25B;@| rG$l%(/;36^TVm$THEDRAGONMAPPROCESSOR11andtheaddressspacescurrentlyloadedonthem.Duringnormaloperation,theseregistersareaccessedusingpn,andtheaidreadoutisusedalongwithvptolookup(rp,flags).5.2.4CacheArrayThisarrayholdsthemappingbetween(aid,vp)and(rp,flags).Itconsistsofanumberoflines,whereeachlineismadeupofcorrespondingrowsfromfourseparatearrays:an||aid||-bitassociativememoryarrayAIDArray;a(||vp||2)-bitassociativememoryarrayVPArray;a1-bitmemoryarrayMParwhichstorestheparityforthetwoassociativearrays;anda4*(||rp||+||flags||+1)-bitmemoryarrayRPFArraythatcontainsfour(rp,flags)pairsforeachline(theremainingbitinthisarrayisrpfPar).Thetop(||vp||2)bitsoftheincomingvpandtheaidbitsfromAidReg[pn]areusedtodoanassociativelookuptoselectaline,whilethebottom2bitsofvpareusedtoselectbetweenthefour(rp,flags)pairspotentiallystoredwithinthatline.Inaddition,eachlinehasanumberofcontrolbits:refissetwheneveritslineisusedinmapping,lValidindicatesifthe(aid,vp)pairinthislineisvalid;lBrokenisusedtoturnoffbadlinescompletely,andrpf0Valid..rpf3Validindicatewhethereachofthefour(rp,flags)pairsinthislineisvalid.AllpartsoftheCacheArrayexceptforthesecontrolbitsareimplementedusingdynamiccells.Thefinalsectionistheaddressdecoderwhichpermitsindividuallinesinthecachetobeselectedforvictimizationaswellasforreadingandwritingduringtesting.5.2.5VictimSelectLogicWhenamissoccursintheMapCache,thelineselectedasvictimistheonepointedtobythevictimpointervPtr.ForeachcycleduringwhichavictimisnotneededtherefbitforthelinepointedtobyvPtrclearedandvPtrisincrementedifrefwasset.ThusvPtrmovesfromonelinetothenexttillitlandsonalinethathasrefclear.ItfollowsthatvPtrwilltendtobeonlinesthathaverefclearwhenthereisarequesttofindavictim.Therefbitissetwheneveritslineisusedinmapping.Thusthelinesusedmostfrequentlyinmappingwillbetheleastlikelytobepickedasvictims,andsothisprocedureapproximatesleastfrequentlyusedvictimselection.Atthemomentthereisnologictohandlebrokenlines.Acleverwaytoimplementthisinthefuturewouldbeasfollows.WhenlBrokenisset,itslinedoesnotparticipateinmatchesanddoesnotpermititsrefbittobecleared(whenthevictimpointerpassesoverit).Thebrokenlinewillappearasthoughitisinuse,soontheaverageitwillnotbepickedasthevictim.However,whenitdoesgetpickedtheeffectswillnotbeharmful.Theentrywillgetwrittenintotheboguslinebutthislinewillnevermatchsoitwillappearasthoughthewriteentrywasneverdone.Thenextreferencetothisentrywillmiss,andtheentrywillgetwrittentothecacheonemoretime.Howeverbythistimethevictimpointerwillinalllikelihoodhavemovedontoalegitimatelinesotheentrywillbewrittencorrectly!!Isn'tcachingwonderful?5.2.6RefreshLogicTherefreshlogicisresponsibleformaintaininginformationindynamiccells.ItisactivatedperiodicallywhenevertheMapCacheisnotbusyprocessingnormalrequests.ForeachactivationitreadsallthedynamiccellsbelongingtothelinethathasrSelsetandthenwritesthemback.ItthenclearsrSelforthislineandsetsitforthenextline.AtanytimeatmostonelineispermittedtohaverSelset.DRAGONPROJECTFORINTERNALXEROXUSEONLYqg' rg'g' qg'"r#6g'g'$ qg'(r)jg'g'*>qg'+jr,;g'g'-vg'Eq_/ g&~ %&'4+0x5< ;?VD] gp]];q]]p]]q]5"O$&1)m-,p0G]]0q]238lp8]]9iq:]]p:]];eq=]]>'pZ9 gqV)K!'>p'VV(hq)|VVp*aVV*q+VV,/sp/VV0qq1!VVp2VV2uq4VV5768)=1>@&E[pUB gq UBUB1T!'" +/25:?hAYpB UBUBBqCUBUBD%S g $!#5$cp%SS&(q&SS'0, 3j8&CC>q@CCAEfB> g!vW""&j*n.1-49 @ g>)W"(A,b1k 8;N=?CaE#ZChE4/ gp4/4/mqI4/4/i!%)-.346;p>34/4/>q4/@LBpD2 g0Np22q2*p"22#_q2%'P /Fp0221=q2258p@- gTh!$j'+.v 5,6<?yA|C+ g?`"T$1&- p6++6u9R ?q+B*C g ')wa#$):-13v7r:D;BEf& gcl3 p%.& & %q& *v+.0{3J69! ?A$y g $ X"3&*-?1X6 :=?Bb" g> V Y"(%&)"+029579>?@B!* g6"$(+.M0U69==@Ba g8<Q "&i*,D-0746_; =d@Dh gR !*"%)p,</25'8;>BD4 g&J1 !$').25h7 8 ?TB gmE Ru" $&+X 2u5: p gqt)* "P$ , 35+:>?AL g 9#I$&* 05?;6=@ % g f[Th$&(+.up0%%1sq%358;?Cu ~ g :p+ ~ ~q ~)= "%')f+/ 247:<@BE gap ,q rG$l%(/;36^ TVm$tTHEDRAGONMAPPROCESSOR125.2.7D-BusInterfaceLogic--tobewritten5.3Operation--tobewritten5.4D-BusInterface--tobewritten5.5MiscellaneousInformationMaintainenceofdirtybit:whenaprocessorwritesintoapagethefirsttimeafterithasbeenbroughtintomainmemory,itsdirtybitmustbeset.SincetheMapCachehasacopyofthisbit,thiscopymustgetsetalso.ThisisdonebyflushingtheentryfromtheMapCacheandsignallingawriteprotectfaultinresponsetoaMapForWritefromaprocessorcache.Thisoperationisissuedbyacachewhenittriestodoawrite,butfindswtEnabledclear.ItisthenuptotheMapCacheControllersoftwaretofigureoutwhetherthewriteprotectfaultisrealornotandtoupdatethedirtybitintheMapTableandsendtheupdatedentrytotheMapCacheifitisnot.6.TheMapCacheControllerAsstatedearlier,theMapCacheControllerisimplementedbysoftwarerunningonDragonprocessors.Thissoftwareprovidestwointerfaces,onetoservicerequestsfromtheMapCacheandtheothertoperformmoregeneralmanipulationsontheMapTable.DragonprocesorsaccesstheMapTablethroughthespecialmapbypassareaprovidedinlowvirtualmemory.Thisareaisalsomeanttocontainanyothersystemcode(suchassomeofthefaulthandlers)thatcannottoleratemapfaultsduringitsexecution.7.TheMapTableTheMapTableisstoredinmainmemory,andmapspairs(aid,vp)topairs(rp,flags).Itisimplementedasahashtable,wherethehashindexisderivedbyfoldingandXORingthe32bitsof(aid,vp).Eachrowofthetableis4wordslongandisquadwordaligned.Arowcontainstwomappingentriesandtwopointersusedincollisionresolution.Initially,themethodforresolvingcollisionswillbelinearchaining.Ifthiscausesperformanceproblemsthemethodwillbechangedtotreechaining.ThischangewillbestraightforwardsincetheaccessalgorithmsareinDragoncode.Sincetheremaybemorethanonemappingentryperphysicalpage,itispossiblefortheMapTabletooverflow.Thenumberofentriesinthetablewillbe1.5timesthenumberofrealpagesinmainmemory,makingoverflowextremelyunlikely.However,overflowisstillpossible,anditisaproblembecauseamissintheMapTabledoesnotnecessarilymeanpagefaultitcouldalsomeanthattherewasnotenoughspaceinthetable.Tofixthisproblem,theMapDRAGONPROJECTFORINTERNALXEROXUSEONLYqg' rg'g' qg'"r#6g'g'$ qg'(r)jg'g'*>qg'+jr,;g'g'-vg'Ep_, gq[)N?{X gqU>)N?{Q gqN)N?{KP g  qH) +#%+9/]2V37 9<?C'DFZ g[!##&T(t+-046:2>c@BE[D g eN#&(n+. 3p59=?BC g Dl!#v)*+ 489D?UCAd g('T""$3';(*,"/25<ABC? gw$ & '+.+3w59P=A1BEP> g,[q!#q&*-:0n28;=M?Bcp>{{?`q@{{p@{{AfqC{{D(E g 8#i 3$T&*-/M4L6Q;r=>q@]@BE/, gp,,q,,p,,Bq,,k b $%a&*-0-17=?A g?#'+(.G  ) w#S )+-c1718;? b g]=#y%'. 158C:"C g "?)?"v%2*.1&6:3;=BgD gx]#~%+)+3-035j7;:=BD] g$5%j+17=>Az I g- D@"h$%&)-13 :>PA gI, G"'+-c/4I68;eAXCrG$l%(/;36^TVm$LTHEDRAGONMAPPROCESSOR13Tablewillbemaintainedusingtheall-or-nothingrule,whichstatesthateitherallofthevp'sforagivenrpareinthetableornoneare.Withthisrule,tablemissonceagainmeanspagefault,freeingthesoftwarefromhavingtodiscriminatebetweenpagefaultsandtablemisses.8.MiscellaneousIssues--Variablepagesize--MultipleMapCaches--MultipleM-Bussystems--Inrestrictedsharingallvp'smusthaveidenticalprotectioninfoAppendixA.SizeofBypassAreaThemapbypassareamustbelargeenoughtofittheMapTableaswellascodeforhandlingtraps.SincetheMapTablewilllargerbyfar,weneedonlyconsideritssizetocalculatehowlargetomakethebypassarea.MapTablesizeinturndependsdirectlyontheamountofrealmemory.Assumingthat4MbitchipswillbeavailablewithinthelifetimeofDragon,thatwecansurfacemount1024memorychipsperboard,andthatwewillputatmost8memoryboardsonthelargestDragons,themaximumamountofrealmemorycomesoutto1GWord.ThesizeoftheMapTableis1.5*(#pagesinrealmemory)*4words.Roundingupthe1.5upto2,theMapTableoccupies223words.Notethatinroundingup1.5to2we'veleftplentyofspaceforcodeandanyotherdatathatneedstobekeptinthebypassarea.AppendixB.LayoutofIOAddressSpaceAppendixC.FormatofMapEntriesAppendixD.Notation||x||ilog2xj,orthenumberofbitsneededtorepresentxa|ba*2||b||+bvpvirtualpagerprealpagespagesizeaidaddressspaceidpnprocessornumberDRAGONPROJECTFORINTERNALXEROXUSEONLYqg' rg'g' qg'"r#6g'g'$ qg'(r)jg'g'*>qg'+jr,;g'g'-vg'Eq_, gE p"_,_," q_,*-15z8E<.>?pB._,_,BqCy_,_,CD] g pF]]q]Sa"%1(+Q.158K;@9C[ gmM "w *9/269f<zU@ gC qQ)#jOv)EL)EJ)o mA1" %q(.G 4zC gmq q@)E&w!P$)r+,/2767:m<?3AX> gXI!%' )+/@2j79<>YD=F gD! #P'7)+.49;&=BD]; g=] $'=)</3Y5:<BD9 g x#&e*-P02)47:8<=9B8P gm'b#(*-_269o;>virtual addresses invirtual addresses in>>>>>>220228DRAGONPROJECTFORINTERNALXEROXUSEONLYqg' rg'g' qg'"r#6g'g'$ qg'(r)jg'g'*>qg'+jr,;g'g'-vg'E= S#$S) w+,E+, 6o)) g=]g?LNsEQM v$#?AKH#i91O$@L$i#$3$!};$w- MG!}.G#Gw.F#GwQ GwNs #wNs )#wM #w; $w;( $wJt GKvBJ %YA9&,B/.+Q G,Pv+O<<$'2W #'2 #.+O $'F #TVm$p&s/+-J.+M #.+Ns #.+Jt G'%?G#G2%?G#G'A G'$ MF.+HFTVm$Bv("Z4;+,91.F#G2-G91Q5#91NsN#91Q5#!}Ns #22 ;#2F#2Hc#D7- MGO=.G#GD7.G#GD7Q GD7L #D7K% #AuHc$CF#(TVm$spC1`CICGl@[D@[C?2#WD75 #D74 #C9<<#?5i##$2i#@LO#?AK%#D7< #D7qg'+jr,;g'g'-vg'E6Dh$2:|$ _2:Y#2:|$ _2C#2Ci#2:|$ _2:Y#6:|$ _5:|# _79G 0_:|# _1y:|# _-:Y#-:|$ _-Ci#,C#-:|$ _,:Y#,:|# _,DE #,Dh#,E y#1yFG5+iHFC.B3$OB3#Ov6}.6}CI>=@# cE#OE#O c?#W?#4=r$" =#4=$4?O#8;sr#;#i8;$i8?O#.E_#" B3#O.B#8B#8B3$O8E_#9> *$#$9b$ :9b# :Fy #(Xv'Z %Y F%LF :0LG :%Lf MG%W #+FV FH0G+9 G+9G >'I"+w%rG$l%(/;36^TVm$GATES HELVETICA  TIMESROMAN MATH TIMESROMAN TIMESROMAN TIMESROMANY LOGO HELVETICAMATH HELVETICA HELVETICA HELVETICA HELVETICA TIMESROMAN TIMESROMAN TIMESROMANB6! 6.>bL XAf o} @6j/lM*[]<>Users>sindhu.pa>map>MapProcessor.tioga#Tuesday, April 15, 1986 5:38 pm PST