30-Structural aspects of the System 360 Model 85, Part II The cache.pdf

Thecache,ahigh-speedbufferestablishingastoragehierarchyintheModel85,isdiscussedindepthinthispart,sinceitrepresentsthebasicorganizationaldeparturefromotherSYSTEM/BOcomputers.Discussedareorganizationandoperationofthecache,includingthemechanismsusedtolocateandretrievedataneededbytheprocessor.Theinternalperformancestudiesthatledtouseofthecachearede-scribed,andsimulatedperformanceofthechosenconfigurationiscomparedwiththatofatheoreticalsystemhavinganentire80-nano-secondmainstorage.Finally,theeffectsofvaryingcacheparametersarediscussedandtabulated.StructuralaspectsoftheSystem/360Model8511ThecachebyJ.S.LiptayAmongtheobjectivesoftheModel85isthatofprovidingaSYSTEM/compatibleprocessorwithbothhighperformanceandhighthroughput.Oneoftheimportantingredientsofhighthrough-putisalargemainstoragecapacity(seetheaccompanyingarticleinPartI).However,itisnotfeasibletoprovidealargemainstor-agewithanaccesstimecommensuratewiththe80-nanosecondprocessorcycleoftheModel85.Alongeraccesstimecanbepar-tiallycompensatedforbyanincreaseinoverlap,greaterbuffering,deeperstorageinterleaving,moresophisticationinthehandlingofbranches,andotherimprovementsintheprocessor.Allofthesefactorsonlypartiallycompensatefortheslowerstorage,and,there-fore,wedecidedtouseastoragehierarchyinstead.Thestoragehierarchyconsistsofa1.04-microsecondmainstor-ageandasmall,faststorecalledacache,lwhichisintegratedintotheCPU.Thecacheisnotaddressablebyaprogram,butratherisusedtoholdthecontentsofthoseportionsofmainstoragethatarecurrentlybeingused.Mostprocessorfetchescanthenbehandledbyreferringtothecache,sothatmostofthetimetheprocessorhasashortaccesstime.Whentheprogramstartsoperat-ingondatainadifferentportionofmainstorage,thedatainthatportionmustbeloadedintothecacheandthedatafromsomeotherportionremoved.Thisactivitymusttakeplacewithoutprogramassistance,sincetheModel85mustbecompatiblewiththerestofThispaperdiscussesorganizationofthecacheandthestudiesthatledtoitsuseintheModel85andtoselectingofvaluesforitsparameters.theSYSTEM/360line.ZBMSYSTEMSJOURNALVOL.7NO.1196815Figure1AssignmentofcachesectorstomainstoragesectorsMAINSTORAGECacheorganizationThemainstorageunitsthatcanbeusedontheModel85aretheIBM2365-5andthe2385.Theyhavea1.04-microsecondcycletimeandmakeavailablecapacitiesfrom512Kbytesto4096Kbytes(K=1024).Thecacheisa16K-byteintegratedstorage,whichiscapableofoperatingeveryprocessorcycle.Optionally,itcanbeexpandedto24Kbytesor32Kbytes.Boththecacheandmainstoragearelogicallydividedintosec-tors,eachconsistingof1Kcontiguousbytesstartingon1K-byteboundaries.Duringoperation,acorrespondenceissetupbetweencachesectorsandmainstoragesectorsinwhicheachcachesectorisassignedtoasingledifferentmainstoragesector.However,be-causeofthelimitednumberofcachesectors,mostmainstoragesectorsdonothaveanycachesectorsassignedtothem(seeFigure1).Eachofthecachesectorshasa14-bitsectoraddressregister,whichholdstheaddressofthemainstoragesectortowhichitisassigned.Theassignmentofcachesectorsisdynamicallyadjustedduringassigningoperation,sothattheyareassignedtothemainstoragesectorsthatcachearecurrentlybeingusedbytheprogram.Iftheprogramcausesasectorsfetchfromamainstoragesectorthatdoesnothaveacachesectorassignedtoit,oneofthecachesectorsisthenreassignedtothatmainstoragesector.Tomakeagoodselectionofacachesectortoreassign,enoughinformationismaintainedtoorderthecachesec-torsintoanactivitylist.Thesectoratthetopofthelististheonethatwasmostrecentlyreferredto,thesecondoneisthenextmostrecentlyreferredto,andsoforth.Whenacachesectorisreferredto,itismovedtothetopofthelist,andtheinterveningonesaremoveddownoneposition.Thisisnotmeanttoimplyanactualmovementofsectorswithinthecache,butratherreferstoalogical16J.8.LIPTAYorderingofthesectors.Whenitisnecessarytoreassignasector,theoneselectedistheoneatthebottomoftheactivitylist.Thiscachesectoristheonethathasgonethelongestwithoutbeingreferredto.Whenacachesectorisassignedtoadifferentmainstoragesec-tor,thecontentsofallofthe1Kbyteslocatedinthatmainstoragesectorarenotloadedintothecacheatonce.Rather,eachsectorisdividedinto16blocksof64bytes,andtheblocksareloadedonademandbasis.Whenacachesectorisreassigned,theonlyblockthatisloadedistheonethatwasreferredto.Iftheyarerequired,theremainingblocksareloadedlater,oneatatime.Eachblockinthecachehasabitassociatedwithittorecordwhetherithasbeenloaded.This“validitybit”isturnedonwhentheblockisloadedandoffwhenthesectorisreassigned.Storeoperationsalwayscausemainstoragetobeupdated.Ifthemainstoragesectorbeingchangedhasacachesectorassignedtoit,thecacheisalsoupdated；otherwise,noactivityrelatedtothecachetakesplace.Therefore,storeoperationscannotcauseacachesectortobereassigned,ablocktobeloaded,ortheactivitylisttoberevised.Sinceallofthedatainthecacheisalsoinmainstorage,itisnotnecessaryonacachesectorreassignmenttomoveanydatafromthecachetomainstorage.Allthatisrequiredistochangethesectoraddressregister,resetthevaliditybits,andinitiateIoadingofablock.Theprocessoriscapableofbufferingoneinstructionrequestingthestoringofinformationinmainstorage,sothatitcanproceedwithsubsequentinstructionsevenifexecutionofthestoreinstructioncannotbeinitiatedimmediately.Twoprocessorcyclesarerequiredtofetchdatathatisinthecache.Thefirstcycleisusedtoexaminethesectoraddressregistersandthevaliditybitstodetermineifthedataisinthecache.Thesecondcycleisthenusedtoreadthedataoutofthecache.How-ever,requestscannormallybeoverlapped,sothatonerequestcanbeprocessedeverycycle.Ifthedataisnotpresentinthecache,additionalcyclesarerequiredwhiletheblockisloadedintothecachefrommainstorage.ThestoragewordsizeonwhichtheModel85operatesinternallyis16bytes.Thisisthewidthofthedatapathstoandfromthestorageunits,andistheamounttheprocessorcanstoreorfetchwithasinglerequest.Becauseasingle2365-5storageunitoperatesonan8-byte-wideinterface,twounitsarepairedtogetherandoperatedsimultaneously.Exceptforthe512Kconfiguration,mainstorageisinterleavedfourways.Sinceablockis64bytes,fourfetchestomainstoragearerequiredtoloadoneblockintothecache.Withfour-wayinterleaving,thismeansonerequesttoeachbasicstoragemodule.Toimproveperformance,thefirstbasicstoragemodulereferredtoduringeachblockloadistheonecon-tainingthe16byteswantedbytheprocessor.Inadditiontobeingloadedintothecache,thedataissentdirectlytotheprocessor,sothatexecutioncanproceedassoonaspossible(seeFigure2).OntheModel85,channelsstoreandfetchdatabywayoftheMODEL85CACHEFigure2TimingforablockloadMAINSTORAGENttUtUBSMZACCESSTIMEIBSMPIBSMOACCESSTIMEwBSM-BASICSTORAGEMODULEprocessor.Channelfetchesareprocessedby-gettingtherequireddatafrommainstoragewithoutreferringtothecache.Channelstoresarehandledthesamewayasprocessorstores.Inthisway,ifachannelchangesdatathatisinthecache,thecacheisupdatedbutthechannelsdonothaveanypartofthecachedevotedtothem.PerformancestudiesAmongthequestionsthathadtobeansweredtodeterminewhetherthecacheapproachshouldbetakenwere:(1)howeffectiveisit,and(2)doesitseffectivenessvarysubstantiallyfromoneprogramtoanother?TheprincipaltoolsusedtoanswerthesequestionsarethetracingandtimingtechniquesreferredtoinPartI.Thetracingtechniqueproducesaninstruction-by-instructiontraceofapro-gramoperatingundertheSYSTEM/OOperatingSystem.Theoutputisasequenceof(tracetapes,”whichcontaineveryinstructionexecuted,whetherintheproblemprogramortheoperatingsystem,andthenecessaryinformationtodeterminehowlongittakestobeexecuted.Thesetracetapescontainabout250,000instructionseachandareusedasinputtoatimingprogram,whichdetermines,cycle-by-cycle,howtheModel85wouldexecutethatsequenceofinstruc-tions.Thesetechniquesareintendedtodetermineinternalper-formanceanddonotprovideanyinformationconcerningthrough-put.Anintensiveinvestigationprecededselectionoftheprogramsusedinthisstudy.Inordertomeasuretheeffectivenessofthecache,wepostulatedcacheasystemidenticaltotheModel85exceptthatthestoragehierarchyeffectivenessisreplacedbyasingle-levelstorageoperatingatcachespeed.TheperformanceofsuchasystemisthatwhichwouldbeachievedbytheModel85ifitalwaysfoundthedataitwantedinthecacheandifitneverencounteredinterferenceinmainstorageduetostores.Therefore,itrepresentsanupperlimitontheperformanceoftheModel85；howclosetheModel85approachesthisidealcanserveasameasureofhoweffectivethecacheis.NineteentracetapesI18J.s.LIPTAYFigure3Model85performancerelativetosingle-levelstorageoperatingatcachespeedMEAN=81%75.7980-8490.94PERCENTAGEOFIDEALPERFORMANCEFlgure4ProbabilityoffindingfetcheddataincachePROBABILITYweretimedforboththeModel85andthepostulatedsystem,andtheperformanceoftheModel85wasexpressedasapercentageoftheperformanceoftheidealsystem.Figure3showsthedistribu-tionofperformancedataobtained,Theaveragewas81percentoftheperformanceoftheidealsystem,witharangebetween66and94percent.Animportantstatisticrelatedtocacheoperationistheprob-abilityoffindingthedatawantedforafetchinthecache.Figure4showsthedistributionofthisprobabilityforthesame19tracetapesusedforFigure3.Theaverageprobabilitywas0.968.Itisworthnotingthat,iftheaddressesgeneratedbyaprogramwererandom,theprobabilityoffindingthedatawantedinthecachewouldbemuchlessthan0.01.Therefore,itcanbesaidthatwhatmakesthecacheworkisthefactthatrealprogramsarenotrandomintheiraddressingpatterns.MODEL85CACHETable2Averageperformancerelativetoanidealsystemwithcachesizeandnum-berofbytesperblockvaried-Numberofsectors=16NumberofNumberofbytesperblockcachebytes64128266,8K0.74416K0.8250.8100.78132K0.8910.8850.870Table3Comparativeperformanceusingdifferentcachesectorreplacementalgorithmsalgorithmperformance1partition*1.0002partitions0.9904partitions0.9878partitions0.97916partitions0.933usagebits0.931*ReplacementalgorithmchosenfortheModel85Table3summarizestheresultsobtained.Thechoiceoftheactivitylistwas