进程多线程管道进程间通信网络超详细.ppt

CS152ComputerArchitectureandEngineeringLecture1 Introduction KrsteAsanovicElectricalEngineeringandComputerSciencesUniversityofCaliforniaatBerkeleyhttp www eecs berkeley edu krstehttp inst eecs berkeley edu cs152 WhatisComputerArchitecture 2 Application Physics Initsbroadestdefinition computerarchitectureisthedesignoftheabstractionlayersthatallowustoimplementinformationprocessingapplicationsefficientlyusingavailablemanufacturingtechnologies butthereareexceptions e g magneticcompass 3 AbstractionLayersinModernSystems Algorithm Gates Register TransferLevel RTL Application InstructionSetArchitecture ISA OperatingSystem VirtualMachines Microarchitecture Devices ProgrammingLanguage Circuits Physics Architecturecontinuallychanging 4 Applications Technology Applicationssuggesthowtoimprovetechnology providerevenuetofunddevelopment Improvedtechnologiesmakenewapplicationspossible 5 ComputingDevicesThen EDSAC UniversityofCambridge UK 1949 6 ComputingDevicesNow Robots Supercomputers Automobiles Laptops Set topboxes Smartphones Servers MediaPlayers SensorNets Routers Cameras Games 7 UniprocessorPerformance VAX 25 year1978to1986RISC x86 52 year1986to2002RISC x86 year2002topresent FromHennessyandPatterson ComputerArchitecture AQuantitativeApproach 4thedition October 2006 8 fromKurzweil MajorTechnologyGenerations Bipolar nMOS CMOS pMOS Relays VacuumTubes Electromechanical 9 TheEndoftheUniprocessorEra Singlebiggestchangeinthehistoryofcomputingsystems 10 ThisYear sCS252 CS152focusesoninteractionofsoftwareandhardwaremorearchitectureandlessdigitalengineeringmoreusefulforOSdevelopers compilerwriters performanceprogrammersMuchofthematerialyou lllearnthistermwaspreviouslyinCS252SomeofthecurrentCS61C IfirstsawinCS252over20yearsago Maybeevery10years shiftCS252 CS152 CS61C ClasscontainslabsbasedonvariousdifferentmachinedesignsExperimentwithhowarchitecturalmechanismsworkinpracticeonrealsoftware DesignswritteninChiselhardwaredescriptionlanguageGettosee andmodify alltheworkingpartsofamodernmicroprocessorHopefullyFPGAversionslaterincourse 11 RelatedCourses CS61C CS152 CS150 Basiccomputerorganization firstlookatpipelines caches ComputerArchitecture Firstlookatparallelarchitectures DigitalLogicDesign FPGAs StrongPrerequisite CS250 VLSISystemsDesign CS252 GraduateComputerArchitecture AdvancedTopics 12 CS152ExecutiveSummary 13 CS152Administrivia Instructor Prof KrsteAsanovic krste eecsOffice 579SodaHall insideParLab OfficeHours Mon 5 00 6 00PM emailtoconfirm 579SodaT A YunsupLee yunsup eecsOfficeHours Tuesdays1 2PM 751SodaLectures Tu Th 2 3 30PM 310Soda Possibleroomchange Section F10 30AM 12M 9EvansText ComputerArchitecture AQuantitativeApproach HennesseyandPatterson 5thEdition 2012 Readingsassignedfromthisedition somereadingsavailableinoldereditions seewebpage Webpage http inst eecs berkeley edu cs152LecturesavailableonlinebynoonbeforeclassPiazzza 14 CS152StructureandSyllabus FivemodulesSimplemachinedesign ISAs microprogramming unpipelinedmachines IronLaw simplepipelines Memoryhierarchy DRAM caches optimizations plusvirtualmemorysystems exceptions interruptsComplexpipelining score boarding out of orderissue Explicitlyparallelprocessors vectormachines VLIWmachines multithreadedmachines Multiprocessorarchitectures memorymodels cachecoherence synchronization 15 CS152CourseComponents 15 ProblemSets onepermodule Intendedtohelpyoulearnthematerial Feelfreetodiscusswithotherstudentsandinstructors butmustturninyourownsolutions Gradingbasedmostlyoneffort butquizzesassumethatyouhaveworkedthroughallproblems SolutionsreleasedafterPSshandedin 35 Labs onepermodule Labsuseadvancedfullsystemsimulators newChiselsimulatorsthisyear noSimics Directedplusopen endedsectionstoeachlab50 Quizzes onepermodule In class closed book nocalculators nosmartphones nolaptops Basedonlectures readings problemsets andlabs 16 CS152Labs Eachlabhasdirectedplusopen endedassignmentsDirectedportion 2 7 isintendedtoensurestudentslearnmainconceptsbehindlabEachstudentmustperformownlabandhandintheirownlabreportOpen endedassignment 5 7 istoallowyoutoshowyourcreativityRoughlyaone day mini project E g tryanarchitecturalideaandmeasurepotential negativeresultsOK ifexplainable StudentscanworkindividuallyoringroupsoftwoorthreeGroupopen endedlabreportsmustbehandedinseparatelyStudentscanworkindifferentgroupsfordifferentassignmentsLabreportsmustbereadableEnglishsummaries notdumpsoflogfiles RISC VISA RISC Visanewsimple clean extensibleISAwedevelopedatBerkeleyforeducationandresearchRISC I II firstBerkeleyRISCimplementationsBerkeleyresearchmachinesSOAR SPURconsideredRISC III IVBothofthedominantISAs x86andARM aretoocomplextouseforteachingRISC VISAmanualavailableonwebpageFullGCC basedtoolchainavailable 17 Chiselsimulators ChiselisanewhardwaredescriptionlanguagewedevelopedatBerkeleybasedonScalaConstructingHardwareinaScalaEmbeddedLanguageLabswilluseRISC VprocessorsimulatorsderivedfromChiselprocessordesignsGivesyoumuchmoredetailedinformationthanothersimulatorsCanmaptoFPGAorrealchiplayoutYouneedtolearnsomeminimalChiselinCS152 butwe llmakeChiselRTLsourceavailablesoyoucanseeallthedetailsofourprocessorsCandolabprojectsbasedonmodifyingtheChiselRTLcodeifdesired 18 ChiselDesignFlow 19 ChiselDesignDescription C code FPGAVerilog ASICVerilog C Simulator C Compiler ChiselCompiler FPGAEmulation FPGATools GDSLayout ASICTools 20 ComputerArchitecture ALittleHistory Throughoutthecoursewe lluseahistoricalnarrativetohelpunderstandwhycertainideasaroseWhyworryaboutoldideas Helpstoillustratethedesignprocess andexplainswhycertaindecisionsweretakenBecausefuturetechnologiesmightbeasconstrainedasolderonesThosewhoignorehistoryaredoomedtorepeatitEverymistakemadeinmainframedesignwasalsomadeinminicomputers thenmicrocomputers wherenext 21 CharlesBabbage1791 1871LucasianProfessorofMathematics CambridgeUniversity 1827 1839 22 CharlesBabbage DifferenceEngine1823AnalyticEngine1833Theforerunnerofmoderndigitalcomputer ApplicationMathematicalTables AstronomyNauticalTables NavyBackgroundAnycontinuousfunctioncanbeapproximatedbyapolynomial WeierstrassTechnologymechanical gears Jacquard sloom simplecalculators 23 DifferenceEngineAmachinetocomputemathematicaltables Weierstrass AnycontinuousfunctioncanbeapproximatedbyapolynomialAnypolynomialcanbecomputedfromdifferencetablesAnexamplef n n2 n 41d1 n f n f n 1 2nd2 n d1 n d1 n 1 2f n f n 1 d1 n f n 1 d1 n 1 2 allyouneedisanadder 24 DifferenceEngine 1823Babbage spaperispublished1834ThepaperisreadbyScheutzheisontoAnalyticEngine 1855ScheutzdisplayshismachineattheParisWorldFareCancomputeany6thdegreepolynomialSpeed 33to4432 digitnumbersperminute NowthemachineisattheSmithsonian 25 AnalyticEngine 1833 Babbage spaperwaspublishedconceivedduringahiatusinthedevelopmentofthedifferenceengineInspiration JacquardLoomsloomswerecontrolledbypunchedcardsThesetofcardswithfixedpunchedholesdictatedthepatternofweave programThesamesetofcardscouldbeusedwithdifferentcoloredthreads numbers1871 BabbagediesThemachineremainsunrealized Itisnotcleariftheanalyticenginecouldbebuiltusingthemechanicaltechnologyofthetime 26 AnalyticEngineThefirstconceptionofageneral purposecomputer Thestoreinwhichallvariablestobeoperatedupon aswellasallthosequantitieswhichhavearisenfromtheresultsoftheoperationsareplaced Themillintowhichthequantitiesabouttobeoperateduponarealwaysbrought 27 ThefirstprogrammerAdaByronaka LadyLovelace 1815 52 Ada stutorwasBabbagehimself 28 Babbage sInfluence Babbage sideashadgreatinfluencelaterprimarilybecauseofLuigiMenabrea whopublishednotesofBabbage slecturesinItalyLadyLovelace whotranslatedMenabrea snotesinEnglishandthoroughlyexpandedthem AnalyticEngineweavesalgebraicpatterns Intheearlytwentiethcentury thefocusshiftedtoanalogcomputersbutHarvardMarkIbuiltin1944isverycloseinspirittotheAnalyticEngine 29 HarvardMarkI Builtin1944inIBMEndicottlaboratoriesHowardAiken ProfessorofPhysicsatHarvardEssentiallymechanicalbuthadsomeelectro magneticallycontrolledrelaysandgearsWeighed5tonsandhad750 000componentsAsynchronizingclockthatbeatevery0 015seconds 66Hz Performance 0 3secondsforaddition6secondsformultiplication1minuteforasinecalculationDecimalarithmeticNoConditionalBranch Brokedownonceaweek 30 LinearEquationSolverJohnAtanasoff IowaStateUniversity 1930 s AtanasoffbuilttheLinearEquationSolver Ithad300tubes Special purposebinarydigitalcalculatorDynamicRAM storedvaluesonrefreshedcapacitors Application LinearandIntegraldifferentialequationsBackground VannevarBush sDifferentialAnalyzer ananalogcomputerTechnology TubesandElectromechanicalrelays Atanasoffdecidedthatthecorrectmodeofcomputationwasusingelectronicbinarydigits 31 ElectronicNumericalIntegratorandComputer ENIAC InspiredbyAtanasoffandBerry EckertandMauchlydesignedandbuiltENIAC 1943 45 attheUniversityofPennsylvaniaThefirst completelyelectronic operational general purposeanalyticalcalculator 30tons 72squaremeters 200KWPerformanceReadin120cardsperminuteAdditiontook200ms Division6ms1000timesfasterthanMarkINotveryreliable 32 ElectronicDiscreteVariableAutomaticComputer EDVAC ENIAC sprogrammingsystemwasexternalSequencesofinstructionswereexecutedindependentlyoftheresultsofthecalculationHumaninterventionrequiredtotakeinstructions outoforder Eckert Mauchly JohnvonNeumannandothersdesignedEDVAC 1944 tosolvethisproblemSolutionwasthestoredprogramcomputer programcanbemanipulatedasdata FirstDraftofareportonEDVACwaspublishedin1945 butjusthadvonNeumann ssignature In1973thecourtofMinneapolisattributedthehonorofinventingthecomputertoJohnAtanasoff 33 StoredProgramComputer manualcontrolcalculatorsautomaticcontrolexternal papertape HarvardMarkI 1944Zuse sZ1 WW2internalplugboardENIAC1946read onlymemoryENIAC1948read writememoryEDVAC1947 concept Thesamestoragecanbeusedtostoreprogramanddata Program Asequenceofinstructions Howtocontrolinstructionsequencing EDSAC1950MauriceWilkes 34 TechnologyIssues ENIAC EDVAC18 000tubes4 000tubes2010 digitnumbers2000wordstoragemercurydelaylinesENIAChadmanyasynchronousparallelunitsbutonlyonewasactiveatatime BINAC Twoprocessorsthatcheckedeachotherforreliability Didn tworkwellbecauseprocessorsneveragreed 35 DominantProblem Reliability Meantimebetweenfailures MTBF MIT sWhirlwindwithanMTBFof20min wasperhapsthemostreliablemachine Reasonsforunreliability 1 VacuumTubes2 StoragemediumacousticdelaylinesmercurydelaylinesWilliamstubesSelections ReliabilitysolvedbyinventionofCorememorybyJ Forrester1954atMITforWhirlwindproject 36 CommercialActivity 1948 52 IBM sSSEC followonfromHarvardMarkI SelectiveSequenceElectronicCalculator150wordstore Instructions constraints andtablesofdatawerereadfrompapertapes 66Tapereadingstations Tapescouldbegluedtogethertoformaloop Datacouldbeoutputinonephaseofcomputationandreadinthenextphaseofcomputation 37 AndthentherewasIBM701 IBM701 30machinesweresoldin1953 54usedCRTsasmainmemory 72tubesof32x32beachIBM650 acheaper drumbasedmachine morethan120weresoldin1954andtherewereordersfor750more Usersstoppedbuildingtheirownmachines WhywasIBMlategettingintocomputertechnology IBMwasmakingtoomuchmoney Evenwithoutcomputers IBMrevenuesweredoublingevery4to5yearsin40 sand50 s 38 Computersinmid50 s HardwarewasexpensiveStoresweresmall 1000words Noresidentsystemsoftware Memoryaccesstimewas10to50timesslowerthantheprocessorcycle Instructionexecutiontimewastotallydominatedbythememoryreferencetime TheabilitytodesigncomplexcontrolcircuitstoexecuteaninstructionwasthecentraldesignconcernasopposedtothespeedofdecodingoranALUoperationProgrammer sviewofthemachinewasinseparablefromtheactualhardwareimplementation 39 TheIBM650 1953 4 From650Manual IBM MagneticDrum 1 000or2 00010 digitdecimalwords 20 digitaccumulator Activeinstruction includingnextprogramcounter Digit serialALU 40 Programmer sviewoftheIBM650 Adrummachinewith44instructionsInstruction 6012341009 Loadthecontentsoflocation1234intothedistribution putitalsointotheupperaccumulator setloweraccumulatortozero andthengotolocation1009forthenextinstruction Goodprogrammersoptimizedtheplacementofinstructionsonthedrumtoreducelatency 41 TheEarliestInstructionSets SingleAccumulator Acarry overfromthecalculators LOADxAC M x STORExM x AC ADDxAC AC M x SUBxMULxInvolvedaquotientregisterDIVxSHIFTLEFTAC 2 AC SHIFTRIGHTJUMPxPC xJGExif AC 0thenPC xLOADADRxAC Extractaddressfield M x STOREADRx Typicallylessthan2dozeninstructions 42 Programming SingleAccumulatorMachine LOOPLOADNJGEDONEADDONESTORENF1LOADAF2ADDBF3STORECJUMPLOOPDONEHLT Ci Ai Bi 1 i n HowtomodifytheaddressesA BandC 43 Self ModifyingCode LOOPLOADNJGEDONEADDONESTORENF1LOADAF2ADDBF3STORECJUMPLOOPDONEHLT modifytheprogramforthenextiteration Eachiterationinvolvestotalbook keepinginstructionfetchesoperandfetchesstores Ci Ai Bi 1 i n 17105 1484 44 ModifyexistinginstructionsLOADx IXAC M x IX ADDx IXAC AC M x IX AddnewinstructionstomanipulateindexregistersJZix IXif IX 0thenPC xelseIX IX 1LOADix IXIX M x truncatedtofitIX IndexRegistersTomKilburn ManchesterUniversity mid50 s Oneormorespecializedregisterstosimplifyaddresscalculation Indexregistershaveaccumulator likecharacteristics 45 UsingIndexRegisters LOADi n IXLOOPJZiDONE IXLOADLASTA IXADDLASTB IXSTORELASTC IXJUMPLOOPDONEHALT ProgramdoesnotmodifyitselfEfficiencyhasimproveddramatically ops iter withindexregswithoutindexregsinstructionfetch17 14 operandfetch10 8 store5 4 Costs Instructionsare1to2bitslongerIndexregisterswithALU likecircuitryComplexcontrol Ci Ai Bi 1 i n 5 2 21 46 OperationsonIndexRegisters ToincrementindexregisterbykAC IX newinstructionAC AC kIX AC newinstructionalsotheACmustbesavedandrestored ItmaybebettertoincrementIXdirectlyINCik IXIX IX kMoreinstructionstomanipulateindexregisterSTOREix IXM x IX extendedtofitaword IXbeginstolooklikeanaccumulator severalindexregistersseveralaccumulators GeneralPurposeRegisters 47 EvolutionofAddressingModes 1 Singleaccumulator absoluteaddressLOADx2 Singleaccumulator indexregistersLOADx IX3 IndirectionLOAD x 4 Multipleaccumulators indexregisters indirectionLOADR IX xorLOADR IX x themeaning R M M x IX orR M M x IX 5 IndirectthroughregistersLOADRI RJ 6 TheworksLOADRI RJ RK RJ index RK baseaddr 48 VarietyofInstructionFormats Oneaddressformats AccumulatormachinesAccumulatorisalwaysothersourceanddestinationoperandTwoaddressformats thedestinationissameasoneoftheoperandsources Reg Reg toRegRI RI RJ Reg Mem toRegRI RI M x xcanbespecifieddirectlyorviaaregistereffectiveaddresscalculationforxcouldincludeindexing indirection Threeaddressformats Onedestinationanduptotwooperandsourcesperinstruction RegxReg toRegRI RJ RK RegxMem toRegRI RJ M x 49 ZeroAddressFormats OperandsonastackaddM sp 1 M sp M sp 1 loadM sp M M sp Stackcanbeinregistersorinmemory usuallytopofstackcachedinregisters 50 Burrough sB5000StackArchitecture AnALGOLMachine RobertBarton 1960 Machineimplementationcanbecompletelyhiddeniftheprogrammerisprovidedonlyahigh levellanguageinterface Stackmachineorganizationbecausestacksareconvenientfor expressionevaluation subroutinecalls recursion nestedinterrupts accessingvariablesinblock structuredlanguages B6700 alatermodel hadmanymoreinnovativefeaturestaggeddatavirtualmemorymultipleprocessorsandmemories 51 a b c EvaluationofExpressions a b c a d c e ReversePolishabc adc e 52 a EvaluationofExpressions a b c a d c e ReversePolishabc adc e 53 Hardwareorganizationofthestack Stackispartoftheprocessorstate stackmustbeboundedandsmall numberofRegisters notthesizeofmainmemoryConceptuallystackisunbounded apartofthestackisincludedintheprocessorstate therestiskeptinthemainmemory 54 StackOperationsandImplicitMemoryReferences Supposethetop2elementsofthestackarekeptinregistersandtherestiskeptinthememory Eachpushoperation 1memoryreferencepopoperation 1memoryreferenceNoGood BetterperformancebykeepingthetopNelementsinregisters andmemoryreferencesaremadeonlywhenregisterstackoverflowsorunderflows Issue whentoLoad Unloadregisters 55 StackSizeandMemoryReferences programstack size 2 memoryrefspushaR0apushbR0R1bpushcR0R1R2c ss a R0R1sf a R0pushaR0R1apushdR0R1R2d ss a b c pushcR0R1R2R3c ss a R0R1R2sf a R0R1sf a b c pusheR0R1R2e ss a b c R0R1sf a b c R0 abc adc e 4stores 4fetches implicit 56 StackSizeandExpressionEvaluation programstack size 4 pushaR0pushbR0R1pushcR0R1R2 R0R1 R0pushaR0R1pushdR0R1R2pushcR0R1R2R3 R0R1R2 R0R1pusheR0R1R2 R0R1 R0 abc adc e aandcare loaded twice notthebestuseofregisters 57 RegisterUsageinaGPRMachine MorecontroloverregisterusagesinceregisterscanbenamedexplicitlyLoadRimLoadRi Rj LoadRi Rj Rk eliminatesunnecessaryLoadsandStores fewerRegistersbutinstructionsmaybelonger LoadR0aLoadR1cLoadR2bMulR2R1 a b c a d c e ReuseR2 58 StackMachines Essentialfeatures Inadditiontopush pop etc theinstructionsetmustprovidethecapabilitytorefertoanyelementinthedataareajumptoanyinstructioninthecodeareamoveanyelementinthestackframetothetop machinerytocarryout etc stack 59 StackversusGPROrganizationAmdahl BlaauwandBrooks 1964 1 Theperformanceadvantageofpushdownstackorganizationisderivedfromthepresenceoffastregistersandnotthewaytheyareused 2 Surfacing ofdatainstackwhichare profitable isapproximately50 becauseofconstantsandcommonsubexpressions 3 Advantageofinstructiondensitybecauseofimplicitaddressesisequaledifshortaddressestospecifyregistersareallowed 4 Managementoffinitedepthstackcausescomplexity 5 Recursivesubroutineadvantagecanberealizedonlywiththehelpofanindependentstackforaddressing 6 Fittingvariable lengthfieldsintofixed widthwordisawkward 60 1 Stackprogramsarenotsmallerifshort Register addressesarepermitted 2 Moderncompilerscanmanagefastregisterspacebetterthanthestackdiscipline StackMachines Mostly Diedby1980 GPR sandcachesarebetterthanstackanddisplays Earlylanguage directedarchitecturesoftendidnottakeintoaccounttheroleofcompilers B5000 B6700 HP3000 ICL2900 Symbolics3600 SomewouldclaimthatanechoofthismistakeisvisibleintheSPARCarchitectureregisterwindows morelater 61 Stackspost 1980 InmosTransputers 1985 2000 DesignedtosupportmanyparallelprocessesinOccamlanguageFixed heightstackdesignsimplifiedimplementationStacktrashedoncontextswap fastcontextswitches InmosT800wasworld sfastestmicroprocessorinlate80 sForthmachinesDirectsupportforForthexecutioninsmallembeddedreal timeenvironm