Datapath Design ITopicsTopics Sequential instruction execution cycle Instruction mapping to hardware Instruction decodingSystems I2OverviewHow do we build aHow do we build a digital computer?digital computer? Hardware building blocks: digital logic primitives Instruction set architecture: what HW must implementPrincipled approachPrincipled approach Hardware designed to implement one instruction at a time Plus connect to next instruction Decompose each instruction into a series of steps Expect that most steps will be common to many instructionsExtend design from thereExtend design from there Overlap execution of multiple instructions (pipelining) Later in this course Parallel execution of many instructions In more advanced computer architecture course3Y86 Instruction SetByte0 1 2 3 4 5pushl rA A 0rA8jXX Dest 7fn Destpopl rA B 0rA8call Dest 8 0Destrrmovl rA, rB 2 0rA rBirmovl V, rB 3 0 8rB Vrmmovl rA, D(rB) 4 0rA rB Dmrmovl D(rB), rA 5 0rA rB DOPl rA, rB 6fn rA rBret 9 0nop 0 0halt 1 0addl 6 0subl 6 1andl 6 2xorl 6 3jmp 7 0jle 7 1jl 7 2je 7 3jne 7 4jge 7 5jg 7 64Building BlocksCombinational LogicCombinational Logic Compute Boolean functions ofinputs Continuously respond to inputchanges Operate on data and implementcontrolStorage ElementsStorage Elements Store bits Addressable memories Non-addressable registers Loaded only as clock risesRegisterfileABWdstWsrcAvalAsrcBvalBvalWClockALUfunABMUX01=Clock5Hardware Control Language Very simple hardware description language Can only express limited aspects of hardware operation Parts we want to explore and modifyData TypesData Types bool: Boolean a, b, c, … int: words A, B, C, … Does not specify word size---bytes, 32-bit words, …StatementsStatements bool a = bool-expr ; int A = int-expr ;6HCL Operations Classify by type of value returnedBoolean ExpressionsBoolean Expressions Logic Operations a && b, a || b, !a Word Comparisons A == B, A != B, A < B, A <= B, A >= B, A > B Set Membership A in { B, C, D }» Same as A == B || A == C || A == DWord ExpressionsWord Expressions Case expressions [ a : A; b : B; c : C ] Evaluate test expressions a, b, c, … in sequence Return word expression A, B, C, … for first successful test7SEQ HardwareStructureStateState Program counter register (PC) Condition code register (CC) Register File Memories Access same memory space Data: for reading/writing programdata Instruction: for readinginstructionsInstruction FlowInstruction Flow Read instruction at addressspecified by PC Process through stages Update program counterInstructionmemoryInstructionmemoryPCincrementPCincrementCCCCALUALUDatamemoryDatamemoryFetchDecodeExecuteMemoryWrite backicode ifunrA , rBvalCRegisterfileRegisterfileA BMERegisterfileRegisterfileA BMEPCvalPsrcA, srcBdstA, dstBvalA, valBaluA, aluBBchvalEAddr, DatavalMPCvalE, valMnewPC8SEQ StagesFetchFetch Read instruction from instructionmemoryDecodeDecode Read program registersExecuteExecute Compute value or addressMemoryMemory Read or write dataWrite BackWrite Back Write program registersPCPC Update program counterInstructionmemoryInstructionmemoryPCincrementPCincrementCCCCALUALUDatamemoryDatamemoryFetchDecodeExecuteMemoryWrite backicode ifunrA , rBvalCRegisterfileRegisterfileA BMERegisterfileRegisterfileA BMEPCvalPsrcA, srcBdstA, dstBvalA, valBaluA, aluBBchvalEAddr, DatavalMPCvalE, valMnewPC9Instruction DecodingInstruction FormatInstruction Format Instruction byte icode:ifun Optional register byte rA:rB Optional constant word valC5 0rA rB DicodeifunrArBvalCOptionalOptional10Executing Arith./Logical OperationFetchFetch Read 2 bytesDecodeDecode Read operand registersExecuteExecute Perform operation Set condition codesMemoryMemory Do nothingWrite backWrite back Update registerPC UpdatePC Update Increment PC by 2 Why?OPl rA, rB 6 fnrA rB11Stage Computation: Arith/Log. Ops Formulate instruction execution as sequence of simplesteps Use same general form for all instructionsOPl rA, rBicode:ifun ← M1[PC]rA:rB ← M1[PC+1]valP ← PC+2FetchRead instruction byteRead register byteCompute next PCvalA ← R[rA]valB ← R[rB]DecodeRead operand ARead operand BvalE ← valB OP valASet CCExecutePerform ALU operationSet condition code registerMemoryR[rB] ← valEWritebackWrite back resultPC ← valPPC updateUpdate PC12Executing rmmovlFetchFetch Read 6 bytesDecodeDecode Read operand registersExecuteExecute Compute effective addressMemoryMemory Write to memoryWrite backWrite back Do nothingPC UpdatePC Update Increment PC by 6rmmovl rA, D(rB)4 0rArB D13Stage Computation: rmmovl Use ALU for address computationrmmovl rA, D(rB)icode:ifun ← M1[PC]rA:rB ← M1[PC+1]valC ← M4[PC+2]valP ← PC+6FetchRead instruction byteRead register byteRead displacement DCompute next PCvalA ← R[rA]valB ← R[rB]DecodeRead operand ARead operand BvalE ← valB + valCExecuteCompute effective address M4[valE] ← valAMemoryWrite value to memoryWritebackPC ← valPPC updateUpdate PC14Executing poplFetchFetch Read 2 bytesDecodeDecode Read stack pointerExecuteExecute Increment stack pointer by 4MemoryMemory Read from old stack pointerWrite backWrite back Update stack pointer Write result to registerPC UpdatePC Update Increment PC by 2popl rA b 0rA815Stage Computation: popl Use ALU to increment stack pointer Must update two registers Popped value New stack pointerpopl rAicode:ifun ← M1[PC]rA:rB ← M1[PC+1]valP ← PC+2FetchRead instruction byteRead register byteCompute next PCvalA ← R[%esp]valB ← R [%esp]DecodeRead stack pointerRead stack pointervalE ← valB + 4ExecuteIncrement stack pointervalM ← M4[valA]MemoryRead from stackR[%esp] ← valER[rA] ← valMWritebackUpdate stack pointerWrite back resultPC ← valPPC updateUpdate PC16SummaryTodayToday Sequential instruction execution cycle Instruction mapping to hardware Instruction decodingNext timeNext time Control flow instructions Hardware for sequential machine