37-A sequencing-based taxonomy of I0 systems and review of Historical Machines.pdf

ASequencing-BasedTaxonomyofI/OSystemsandReviewofHistoricalMachinesMarkSrnothermanDept.ofComputerScienceClemsonUniversity,Clemson,SC29634-1906INTERNET:AbstractAnewtaxonomyforI/Osystemsisproposedthatisbasedontheprogramsequencingneces-saryforthecontrolofI/Odevices.AreviewofhistoricalmachinesdemonstratestheneedforamorecomprehensivecategorizationthanpreviouslypublishedandrevealsthehistoricalfirstsofI/OinterruptsintheNBSDYSEAC,DMAintheIBMSAGE(AN/FSQ-7),theinterruptvectorconceptintheLincolnLabsTX-2,andfullysymmetricI/OintheBurroughsD-825multiprocessor.IntroductionTextbookpresentationsofI/Osystemstypicallyidentifyonlyfourcategories(i.e.themethodsofdatatransfer):1)program-controlledI/O(i.e.polling),2)interrupt-drivenI/O,3)DMA,and4)channelI/O.BlaauwandBrookspresentabroadercategorizationintheirmanuscript,ComputerArchitecture10.TheyidentifyessentiallysevendistincttypesofI/Osystems:I.DependentI/OA.directB.singleinstructionoverlap1.privatebufferperdevice2.sharedbuffera.dedicatedtoI/Ousageb.generalbufferinmainmemoryII.AutonomousI/OA.channel(specializedcontroller/processor)B.peripheralprocessor(generalizedprocessor)1.homogeneousmulfiprocessorstructure2.heterogeneousmultiprocessorstructureHowever,afterreviewingthehistoricaldevelopmentofI/Osystems,Iamledtobelievethatthereisamuchricherdesignspaceandmoredifferencesbetweenmachinesthansuggestedbyeitherofthecategorizationsabove.Foruniprocessors,Ibelievethatthemajorissueisthemethodoftransferinitiation；thus,majorcategoriesaresynchronousI/OversustheseveraldifferentwaysinwhichoverlappedI/Ooperationscanbeini-tiated.Foreachoftheoverlappedoperations,Ibelievetheyshouldbesubdividedaccordingtotheirmethodofcompletionreporting.Furthermore,themajormultiprocessorissueofsymmetryinI/Oshouldbehandledseparately.ThemethodoftransferisanindicationoftheleveloffunctionalityoftheI/Osubsystem,thatis,howoftenandhowmuchtheCPUisinvolvedintheactualtransfer.ThisrangesfromtheCPUdoingalltosophisticatedperi-5pheralprocessingunits,anditappliestoallinitiation/completionreportingcategories.Withinthisrange,IdrawadistinctionbetweenacontrollerthatcantransferonlyoneblockbeforerequiringCPUinterventionandacon-trollerthatcantransfermultipleblocksinascatter/gathertypeofoperation(inwhichtheblocksareidentifiedtothecontrollerbyachainofdescriptors).SomedesignersandauthorscallacontrollerwiththelattercapabilityanI/Ochannel.Indeed,BellandNewellcategorizecontrollerswithscatter/gathercapabilityasPios,sincetheyconsiderthechainofblockdescriptorstobeaseriesofjumpinstructions8.However,inthistaxonomyIreservethetermI/OchannelforaspecializedI/Oprocessorthatfetchesinstructionswithidentifiableopcodefields.Moreover,IalsousethedistinctionmadebyBlaauwandBrooksbetweenI/OchannelsandI/Oproces-sors,whichisthegeneralabilitytocount.Thatis,anI/Oprocessorshouldhavetheabilitytomaintainalooporeventcountthatisunrelatedtothetransferofagivennumberofwordsorcharactersperblock.Formultiprocessors,themethodofinitiationisnotasimportantasthesymmetryoftheinitiation；therefore,thissymmetryorlackofitbecomesthebasisofthemajorcategories.Themethodofcompletionreportingisthebasisofsubcategories,andsymmetryininterruptionisexplicitlyidentified.AclassificationofhistoricalmachinesservestodemonstratetheusefulnessoftheproposedtaxonomyandalsoservesasaguidedtourofthehistoryofI/Osystems.ForoldermachineswithmultipleI/Ooptions,Ihavechosentoclassifythemaccordingtotheirestablisheduse(e.g.theIBMS/360hassynchronousI/Ocapability,butitisrarelyused).Somemulfiprocessorsappearinthefirstsection；thisisbecausetheyrepresentthefirstuseofagiventransferinitiationmethod.Notallcategoriesarepopulatedwithmachines.Thismaybetheresultofomissionsonmypart,orthecategorymayindeedbeunfruitful.Iwouldliketocharacterizethereasonsforthelatteroccurrence.ASequencing-BasedTaxonomyI.CPU-I/OINTERACTIONA.SynchronoustransferB.Aerlockedinstructiontostarttransfera.synchronizationbyinterlockb.synchronizationbypollingi.separateinstructionstopollandtransferdataii.controllertransferswordsofblock(i.e.DMA)iii.controllerwithscatter/gathercapability(oftencalledanI/Ochannel)iv.I/Ochannel(withspecializedI/Oinstructionset)v.I/Oprocessorc.synchronizationbyinterrupti.separateinstructiontotransferdataii.controllertransferswordsofblock(i.e.DMA)iii.controllerwithscatter/gathercapability(oftencalledanI/Ochannel)iv.I/Ochannel(withspecializedI/Oinstructionset)v.I/Oprocessor2.conditionalinstructiontostarttransfera.synchronizationbypollingb.synchronizationbyinterrupt3.mailboxdeposittostarttransfer(i.e.singleentry)a.synchronizationbypollingb.synchronizationbyinterrupt4.queueinserttostarttransfer(i.e.multipleentries)a.synchronizationbypollingb.synchronizationbyqueueingc.synchronizationbyinterrupt65.asynchronousinstructiontostarttransfera.synchronizationbypollingb.synchronizationbyinterruptH.MULTIPROCESSORI/OA.Asymmetricinitiation1.synchronizationbypolling2.synchronizationbyasymmetricinterrupt3.synchronizationbysymmetricinterruptB.Symmetricinitiation1.synchronizationbypolling2.synchronizationbyqueueing3.synchronizationbyasymmetricinterrupt4.synchronizationbysymmetricinterruptAReviewofHistoricalMachinesI.CPU-I/OINTERACTIONA.SynchronoustransferERA1103(1953)-word-at-a-timeinterlockedI/O8.BellandNewellandBlaauwandBrookscreditaUNIVACl103Aasthefirstcomputertousetheinterruptconcept8,10,inwhichabatchmachinewaspreemptedtostartdatacollectionfromaNASAwindtunnel44；however,seealsotheUNIVACIandNBSDYSEAC.IBM702(1953)-blockinterlockedI/O5,6.TheCPUstallswhileablockofcharactersistransferredfromanI/Odevicebuffer.The702introducedthecontrolunitconcept.IBM1401(1959)5,6.Thismachinewasoriginallydesignedasaprintercontrollerbutfoundwidespreaduseasasmallbusinesscomputer.ItusesoneopcodeperI/Odevice,andtheseincludereadingacardintomemorylocations0to79,punchingacardfromotherlocations,andprintingfromathirdsetoflocations.TheCPUstallswhilethecharactersaretransferred.Anexampleofitseaseofuseisthatacardduplicat-ingprogramcanbewritteninabout20charactersandpunchedontoonecard.B.Aerlockedinstructiontostarttransfera.synchronizationbyinterlockUNIVACI(1951)-bufferedI/O8,23,56.Thereisone60-wordtapebufferforinputandoneforoutput.AninitialinputinstructionstartsthetransfertothebufferandthenreleasestheCPUforover-lappedinstructionexecution；asubsequentinputinstructiondumpsthebuffertomemory,startsthenexttransfer,andthenreleasestheCPU.IfasubsequentinputinstructionisissuedtooearlythenaninterlockstallstheCPU.I/OerrorshalttheCPU,andtheoperatormustdiagnosetheproblem.CoddcreditstheUNIVACIasoneoftheearliestmachinestobeequippedwithprograminterruptionsincehestatesthatanarithmeticoverflowwouldcausetheprogramtostop17；Eckertalsomentionsseveralchecksthatcanstopthemachine23.However,interruptswereapparentlyneverusedforI/Ocompletion.IBM701(1952)-copylogic5,6,10,14,50,Afteraninitialpreparetoread(orwrite)instruction,7theprogrammustissueacopyinstructionforeachwordinthetransfer.Aloopiscodedtoupdatethememoryaddressesandissuethecopies,andtheloopmayalsoperformsuperficialprocessingsuchascharactercodeconversion.ThecopyinstructionisinterlockedsothatanearlyissueisstalleduntiltheI/Odevicecanprovide/acceptthenextword.Atendoffilethecopyinstructioncausesaone-instructionskip,andattheendofblockitcausesatwo-instructionskip.b.synchronizationbypollingi.separateinstructionstopollandtransferdataPDP-1(1959)7.ThismachineprovidedconditionalskipsonI/Obufferregistercontents,whichareapparentlyusedtopollfortransfercompletion.PDP-8(1965)7,8.Conditionalskipsoncontrolunitstatusregistersareusedforpolling.ii.controllertransferswordsofblock(i.e.DMA)(WhirlwindI,1951-Everettstates,Ingeneralthecomputercontinuestorunduringterminalequip-mentwaittimes,butexplainsnofurther29.)IBMSAGE(orAN/FSQ-7,started1952,operational1955)-DMAoperation3.I/Ooperationsstartblocktransfersofdatato/fromdrumbuffersthatproceedinparallelwithfurtherCPUopera-tions.Acontrollergeneratesthesequentialmemoryaddressesfortheblockanddecrementsacounter,whiletheCPUhasaconditionalbranchtotestcompletionofthetransfer.Transfersarein-terlockedsothattheCPUissmiledifasecondtransferisattemptedbeforethepreviousoneends.Jacobsstatestheinput/output(I/O)break,ormemorycyclestealing,wasintroducedinSAGE37,andSerrell,etal.,identifycomputationinparallelwithI/OasasignificantnewfeatureofSAGE48.(seealsoUNIVAC1107)iii.controllerwithscatter/gathercapability(oftencalledanI/Ochannel)Honeywell800(1963)-hardware-assistedmultiprogramming34,35,42,43.Thismachineimple-mentseightvirtualprocessors,eachhaving2programcountersandanindividualinterruptvectorbaseregister.Oneachmemorycyclethehardwarescansonaprioritybasisforactivityoneightin-putcontrollers,theneightoutputcontrollers,andthentheCPU.WithintheCPUthehardwarescansthevirtualprocessorsinacyclicmanner(withvariousexceptionsformultiplememorycycleopera-tions).(PapersareunclearaboutprogramI/Osynchronization.)iv.I/Ochannel(withspecializedI/Oinstructionset)(seeIBM709)v.I/Oprocessor(exampleunknown)c.synchronizationbyinterrupti.separateinstructiontotransferdataNBSDYSEAC(1954)-introducedI/Ointerrupt38,39.Thismachinehastwoprogramcounters；anI/OsignalcausestheCPUtoswitchPCs.Abitineachinstructioncanforceaswitchback8betweenPCs.Coddstates,intheNBSDYSEACtheverysignificantstepwasmadeofextendinginterruptiontoinput-outputoperations17.LincolnTX-2(1957paper)-multiplesequence30.Thismachinecontains33programcounters；eachI/OdevicehasadedicatedPCandoperatesatafixedpriority(i.e.forerunnerofintetruptvec-tor).Eachinstructionhasbreakanddismissbits:breakisusedtoindicatepointsatwhichahigher-prioritysequencecantakeover,whiledismissisusedtoallowlower-prioritysequencestoresume.BlaauwandBrooksclassifythismachineashavingPPUs10,butIseetheexplicitinstructionbitsasarecognitionofthesharingofasingleCPU.Thus,IconsiderthismachineclosertointerruptvectoringthantovirtualPPUs.PDP-1(1959)7.Bell,etal.,creditthe16-channelsequencebreaksystemtoTX-2influence(ac-tualoperationnotdescribed)7.ii.controllertransferswordsofblock(i.e.DMA)UNIVAC1107(1962)11,12.ControllerusesasingleI/Ocontrolword,whichcontainsamemoryaddress,addressincrement/decrementflag,andawordcount.InterruptoccursonzerocountwhenspecifiedbyLoadChannelcommands.iii.controllerwithscatter/gathercapability(oftencalledanI/Ochannel)IBM7070(1958)-priorityprocessing(I/Ointerrupt)51.AnI/OcompletioncausestheCPUtoswitchtoanuninterruptiblepriorityroutine,andthereturnaddressisstoredinaregister.Themachineprovidesscatter/gathercapabilityusingachainofrecorddefinitionwords.IBMSTRETCH(started1954,delivered1961)10,15,22.TheI/Oexchangeactsasabytemulti-plexor.I/Ocompletionispartofacomprehensiveinterruptvectorfacility,inwhicheachvectorcontainsasingleinstructiontobeexecutedoutsidethenormalinstructioncycle.Theseinstructionscanbesingle-instructionfixupsorsubroutinecalls.Ingeneral,interruptnestingisallowed；howev-er,I/Oistreatedasasinglecause.iv.I/Ochannel(withspecializedI/Oinstructionset)IBM709(1957)-introductionofchannelI/O5,6,32.TheCPUmustexecutetwoinstructionsinsequencetostartI/O.Areadselectorwriteselectinstructionisfirstusedtoselectagivendevice,andthenachannel-specificinstructionisusedtoresetandstartanyofthemaximumofsixchannels(766s).Theaddressfieldoftheresetandstartinstructionisusedtocarrythechannelprogramad-dress.SomedeviceselectinstructionsareinterlockedsothattheCPUisstalledifasecondselectisissuedbeforeapreviousoneends.Theresetandselectinstructions,however,immediatelyactuponthechannels,whichweremuchmoresophisticatedthanthelaterIBMS/360channels.PollingcanbeusedforI/Ocompletion,whileinterruption(data-channeltrap)isavailableasanextracostfeature.Apparently,allinstallationschosetousetheinterruptfeatureM.Rubinstein,personalcom-munication.IBM7090(1958)8,10.Theoptionaldata-channeltrapfeatureofthe709architectureisinclud-edasstandardequipment.Aninterruptvectorwithapairofsaved-PCandnew-PClocationsforeachchannelisusedtoresolveI/Ocompletiontraps.Thelaterversionchannels(7909)canthem-selvesbeinterruptedbyexternaleventsandarecapableofdealingwithI/OretrieswithoutCPUin-tervention.v.I/OprocessorUNIVACLARC(started1954,delivered1960)20,24,25.High-levelrequestpackets(e.g.record9numberorkey)aresenttoanI/Oprocessor,whichalsoperformsservicessuchasdevicequeueing.Therequestingprocessorisinterruptedwhenitsrequestiscomplete.2.conditionalinstructiontostarttransfera.synchronizationbypolling(exampleunknown)b.synchronizationbyinterruptIBMS/360(1964)1,8-10.TheStartI/Oinstructionsetstheconditioncodeaccordingtosuccessofinitiation(pathmaybebusyandCPUmustperformqueueing,orerrormayexist).ChannelI/Oisthemethodoftransfer,butalesscomplexchannelinstructionsetisprovidedthanthatfor7090channels.3.mailboxdeposittostarttransfera.synchronizationbypollingCDC6600(1965)-virtualPPUs8,28,47,54,55,57.InthetypicalOSstructure,PPUsareassignedtodevicesandpollreservedmainmemorylocations(inputmailboxes)todetermineI/Orequestsforthatdevice.Afterstartingadevice,aPPUwillpollthedeviceuntilcompletionandwillthenplaceacom-pletionnoticeinitsoutputmailbox.ProgramsrunningontheCPUcanpolltheoutputmailbox；other-wise,theycanbesuspendeduntilthePPUrunningtheOSseesthecompletionnoticeandresumestheprogrambyanexchangejump.BeforeanoutputtransferthePPUmustmovethedatafromthesharedmainmemorytoitslocalmemory,likewiseafteraninputtransferthePPUmustmovethedatafromitslocalmemorytothesharedmainmemory.TheexecutionoftenvirtualPPUsisaccomplishedbytime-sharingasingleexecutionunit.b.synchronizationbyinterrupt(exampleunknown)4.queueinserttostarttransfera.synchronizationbypollingBurroughsB7700(1972)20,28,47.ReservedlocationsexistinmainmemorythatdefineheadandtailpointerstoI/OdevicerequestqueuesandI/Ocompletionblockqueues.QueuemanipulationsbytheCPUandI/Omodulesareatomicactions.AnyIOMcanhandleanydevice,butastartI/Oinstruc-tionissuedbytheCPUbeginsIOMprocessingonaspecifieddevicequeue.IOMprocessingcontinuesuntilanerror,interrupt,oremptyqueue.TheCPUpollsthecompletionblockqueue,or,optionally,interruptscanbegeneratedoncompletionofeachrequest.(seealsoIBMS/370XAwherepathbusyqueueingishandledbythechannelsubsystem)b.synchronizationbyqueueingHoneywellSeries60Level64(1974)4.MicrocodedsemaphoreoperationsareusedinI/Oprocess-ing.OnI/Ocompletion,thecontrollerinsertsacompletionmessageintoaqueueandsignalsthecorrespondinggeneralsemaphore.10ELXSISystem6400(1987)45.ThismachineusesmessagepassingasasynchronizationmechanismbetweenbothOSprocessesandI/Ocontrollers.AnI/Oprocessornotifiesthecontrollerthatamessageispending,butitistheresponsibilityofthecontrollertohandlequeues,includingout-of-orderpro-cessinganderrorhandling.c.synchronizationbyinterrupt(seealsoIBMS/370XAwherepathbusyqueueingishandledbythechannelsubsystem)5.asynchronousinstructiontostarttransfera.synchronizationbypolling(exampleunknown)b.synchronizationbyinterruptIBMS370(1970)16,47.SIOF(startI/Ofastrelease)isusedtoreleasetheCPUafterachannelhasfetcheditsCAWbutbeforethechannelhasdeterminediftheI/Ooperationcanbesuccessfullyinitiat-ed.Aninterruptoccursifthedeviceorpathisbusy.Thedesignersassumedtheseconditionswouldbeinfrequent,butonlatersystemstheinterruptoverheadcanceledoutanyperformancegainfromthefastreleaseofCPU.H.MULTIPROCESSORI/OA.Asymmetricinitiation1.synchronizationbypolling(exampleunknown)2.synchronizationbyasymmetricinterruptBurroughsB5500(1964)8,10,28.ThismachineprovidesuptotwoCPUs,butonlythemasterCPUcaninitiateI/O.AnITIinstructiontotestforpendinginterruptatendofinterrupthandlingpreventsun-necessarycontextswitching.TheI/OchannelsandCPUsarecrossbarredwithmemorymodules；alsotheI/Ochannelsarecrossbarredwithalltheperipherals.IBMS/370MP(1974)16,28,47.ChannelsanddevicesarededicatedtoaparticularCPU.3.synchronizationbysymmetricinterruptUNIVAC1100Model80(1976)11,12,47.ThismachineprovidesuptofourCPUs,butI/OmustbeinitiatedbyeitherofthetwoCPUsthatconnecttothestorageinterfaceunitthatcontrolsmemoryaccessfortheI/Odevice.I/OisdirectedtothecacheintheSIUratherthandirectlytomainmemory.I/Oin-terruptsaremadeavailabletothetwoCPUsinalternationandforalimitedamountoftimeeach；ifoneCPUdoesntrespondtotheinterruptwithintheavailableperiod,theinterruptispassedontothenextCPUinsequence.B.Symmetricinitiation111.synchronizationbypollingPlesseySystem250(1972)-memory-mappedI/Owithcapabilityprotection19,26,27,33,40.AdesignphilosophyofreliabilityandsecurityledthedesignerstorejectI/OchannelsinfavorofadditionalCPUsandtorejectinterprocessoranddevice-processorinterrupts.Theadvantagesofthisapproachlieinthesimplifiedproblemofcomponentsparing,thepreventionofdisruptionsfromunplannedexternalevents,andtheeaseofhardwareisolationinthecaseofcomponentfailure.DevicedriversobtainI/Orequestsfrommemoryqueuesandpolldeviceregistersuntiltransfersarecomplete.Aninterrupt-likesystemisalsoavailableinwhicheachprocessorperiodically(100microsec.)examinesacommonstatuswordforinterrupt-likerequests；however,variouspapersdifferonitsuseinI/O.(seealsoB-7700)(seealsoIBMS/370XAoptionofmaskingoffsubclassesandusingTestSubchannel)2.synchronizationbyqueueingIntel432(1981)-alayered,intelligentperipheralsubsystemandobject-orienteddesign36.GDPs(i.e.CPUs)canrequestanI/Ooperationbysendingamessageobjecttoadevicerequestportobject.AnI/Oprocessonaninterfaceprocessor(IP)ownsthisportandrespondsbysendingamessagetoanattachedprocessor(AP)(i.e.placingthenecessaryinformationinthelocalmemoryoftheAPandinterruptingtheAP).TheIPhasresponsibilitytoprotectthe432coresystemlogicallyusingcapabilitiesandphysicallyusingseparatebusses,whiletheAPisamoreconventionalmicroprocessor(e.g.8086)andmayusepol-ling,byte-at-a-timeinterrupts,orDMAcontrollersfortheactualI/Otransfer.ThedevicedriverontheAPformatsareplymessagefromtheI/ObuffersinitslocalmemoryandsendsittotheI/OprocessontheIP,whichthensendsamessageobjecttothecorrespondingdevicereplyportobject.(seealsoELXSISystem6400)3.synchronizationbyasymmetricinterruptRamo-WooldridgeRW-400(1960)8,20,28,46.Multiplecomputers(CPUswithlocalmemories)canconnectoveracrossbarexchangetospecializedprocessorscalledbuffermemoriesandfromtheretoanyoneofmultipleI/Ocontrollers.Interruptsareavailable,butthepapersareunclearastowhetherthecon-necfionbetweenabuffermemoryandI/Ocontrollermustbemaintainedforaninterrupttobesent.Cur-tinstatesthatconnectionrequestscanonlybemadebythecomputersorbuffermemoriesbutthatacomputercanrequestthatabuffermemorystartIOoperationsandthenlatertransferdatafromthebuffermemoryintoitslocalmemory20.Enslowindicatesthatacompletesystemwasneverbuilt28.Univacll08-MP(1967)28,47,49.AnyCPUcaninitiateI/Ooperations,butinterruptsaredirectedtoasingleprespecifiedprocessor.GE-655(1969,laterrenamedHoneywell6000)28,47.AnyCPUcaninitiateI/Ooperations,butinter-ruptsaredirectedtoasinglecontrolprocessor(whichisdeterminedbymanuallysetswitches).4.synchronizationbysymmetricinterruptBurroughsD-825(1960)2,8,28,53.Allinterruptsaretransmittedtoeachprocessor；anOS-controlledmaskregisterineachprocessordeterminesifitwillrespondtoagiveninterrupt.IBMS/360Model67(1966)31.I/OhandlingonthisdualprocessorsystemissimilartoD-825.IBMS/370XA(1983)-subchannelperdevice18,21.AnyCPUcanstartI/Oonanydevice,andanyCPUcanacceptaninterrupt.Optionally,interruptrequestsfromsubchannelscanbeassignedtooneof12eightmaskableinterruptionsubclasses,andpriorityschemescanbeprogrammedsothatcertainhighpriorityprogramscanbeinterruptedbyonlyasmallnumberofsubclasses.IfallCPUsmaskoffacer-tainsubclass,theinterruptionstatusisheldpendinginthechannelsystemandcanbeacceptedlaterbyuseofthetestsubchannelinstruction.AtestpendinginterruptioninstructionisalsoavailableandisusedtoavoidanimmediatecontextswitchafteraLPSWisexecutedbytheinterrupthandler.Pathbusyqueueingishandledbythechannelsubsystem.DataGeneralMV/20000(1985).AnyprocessorcanstartI/Oonanychannel.Channelseithersendin-terruptstoaprocessoridentifiedbyanOS-setregisterinthechanneloraccordingtodevicedirectedin-terruptmode,whichusesanOS-controlledtableinmainmemorytomapdevicenumberstoprocessornumbers.SequentBalance(1986)-intelligentinterruptbus52.TheSLICbusinterruptstheprocessorcurrentlyrunningtheprogramwithleastpriority.ConcludingRemarksIwouldliketogatherresponsesandcorrectionstothisnewtaxonomyan