CS Fakk Computer Organization - 1 Computer Organization zComputer design as an application of digital logic design procedures zComputer = processing unit + memory system zProcessing unit = control + datapath zControl = finite state machine yInputs = machine instruction, datapath conditions yOutputs = register transfer control signals, ALU operation codes yInstruction interpretation = instruction fetch, decode, execute zDatapath = functional units + registers yFunctional units = ALU, multipliers, dividers, etc. yRegisters = program counter, shifters, storage registers

CS Fakk Computer Organization - 2 central processing unit (CPU) instruction unit – instruction fetch and interpretation FSM execution unit – functional units and registers address read/write data Processor Memory System Structure of a Computer zBlock diagram view control signals data conditions Data PathControl

CS Fakk Computer Organization - 3 LD asserted during a lo-to-hi clock transition loads new data into FFs OE asserted causes FF state to be connected to output pins; otherwise they are left unconnected (high impedance) OE Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0 LD D7 D6 D5 D4 D3 D2 D1 D0 CLK Registers zSelectively loaded – EN or LD input zOutput enable – OE input zMultiple registers – group 4 or 8 in parallel

CS Fakk Computer Organization - 4 Register Transfer zPoint-to-point connection yDedicated wires yMuxes on inputs of each register zCommon input from multiplexer yLoad enables for each register yControl signals for multiplexer zCommon bus with output enables yOutput enables and load enables for each register rt MUX rs MUX rd MUX R4 MUX rs MUX rtrdR4 BUS rsrtrdR4

CS Fakk Computer Organization - 5 RE RB RA WE WB WA D3 D2 D1 D0 Q3 Q2 Q1 Q0 Register Files zCollections of registers in one package yTwo-dimensional array of FFs yAddress used as index to a particular word ySeparate read and write addresses so can do both at same time z4 by 4 register file y16 D-FFs yOrganized as four words of four bits each yWrite-enable (load) yRead-enable (output enable)

CS Fakk Computer Organization - 6 RD WR A9 A8 A7 A6 A5 A4 A3 A2 A1 A0 IO3 IO2 IO1 IO0 Memories zLarger Collections of Storage Elements yImplemented not as FFs but as much more efficient latches yHigh-density memories use 1-5 switches (transitors) per bit zStatic RAM – 1024 words each 4 bits wide yOnce written, memory holds forever (not true for denser dynamic RAM) yAddress lines to select word (10 lines for 1024 words) yRead enable xSame as output enable xOften called chip select xPermits connection of many chips into larger array yWrite enable (same as load enable) yBi-directional data lines xoutput when reading, input when writing

CS Fakk Computer Organization - 7 Instruction Sequencing zExample – an instruction to add the contents of two registers (Rx and Ry) and place result in a third register (Rz) zStep 1: Get the ADD instruction from memory into an instruction register zStep 2: Decode instruction yInstruction in IR has the code of an ADD instruction yRegister indices used to generate output enables for registers Rx and Ry yRegister index used to generate load signal for register Rz zStep 3: execute instruction yEnable Rx and Ry output and direct to ALU ySetup ALU to perform ADD operation yDirect result to Rz so that it can be loaded into register

CS Fakk Computer Organization - 8 Instruction Types zData Manipulation yAdd, subtract yIncrement, decrement yMultiply yShift, rotate yImmediate operands zData Staging yLoad/store data to/from memory yRegister-to-register move zControl yConditional/unconditional branches in program flow ySubroutine call and return

CS Fakk Computer Organization - 9 Elements of the Control Unit (aka Instruction Unit) zStandard FSM Elements yState register yNext-state logic yOutput logic (datapath/control signalling) yMoore or synchronous Mealy machine to avoid loops unbroken by FF zPlus Additional Control" Registers yInstruction register (IR) yProgram counter (PC) zInputs/Outputs yOutputs control elements of data path yInputs from data path used to alter flow of program (test if zero)

CS Fakk Computer Organization - 10 Reset Initialize Machine Register- to-Register Branch Not Taken Branch Taken Instruction Execution zControl State Diagram (for each diagram) yReset yFetch instruction yDecode yExecute zInstructions partitioned into three classes yBranch yLoad/store yRegister-to-register zDifferent sequence through diagram for each instruction type Init Fetch Instr. XEQ Instr. Load/ Store Branch Incr. PC

CS Fakk Computer Organization - 11 Cin Ain Bin Sum Cout FA HA Ain Bin Sum Cin Cout HA Data Path (Hierarchy) zArithmetic circuits constructed in hierarchical and iterative fashion yeach bit in datapath is functionally identical y4-bit, 8-bit, 16-bit, 32-bit datapaths

CS Fakk Computer Organization AB SZN Operation 16 Data Path (ALU) zALU Block Diagram yInput: data and operation to perform yOutput: result of operation and status information

CS Fakk Computer Organization Z N OP 16 ACREG 16 Data Path (ALU + Registers) zAccumulator ySpecial register yOne of the inputs to ALU yOutput of ALU stored back in accumulator zOne-address instructions yOperation and address of one operand yOther operand and destination is accumulator register yAC <– AC op Mem[addr] ySingle address instructions (AC implicit operand) zMultiple registers yPart of instruction used to choose register operands

CS Fakk Computer Organization bits wide 1 bit wide Data Path (Bit-slice) zBit-slice concept: iterate to build n-bit wide datapaths CO CIALU AC R0 from memory rs rt rd CO ALU AC R0 from memory rs rt rd CIALU AC R0 from memory rs rt rd

CS Fakk Computer Organization - 15 Instruction Path zProgram Counter yKeeps track of program execution yAddress of next instruction to read from memory yMay have auto-increment feature or use ALU zInstruction Register yCurrent instruction yIncludes ALU operation and address of operand yAlso holds target of jump instruction yImmediate operands zRelationship to Data Path yPC may be incremented through ALU yContents of IR may also be required as input to ALU

CS Fakk Computer Organization - 16 Data Path (Memory Interface) zMemory ySeparate data and instruction memory (Harvard architecture) xTwo address busses, two data busses ySingle combined memory (Princeton architecture) xSingle address bus, single data bus zSeparate memory yALU output goes to data memory input yRegister input from data memory output yData memory address from instruction register yInstruction register from instruction memory output yInstruction memory address from program counter zSingle memory yAddress from PC or IR yMemory output to instruction and data registers yMemory input from ALU output

CS Fakk Computer Organization Z N OP 8 ACREG 16 load path store path Data Memory (16-bit words) 16 OP 16 PCIR 16 data addr rd wr MARControl FSM Block Diagram of Processor zRegister Transfer View of Princeton Architecture yWhich register outputs are connected to which register inputs yArrows represent data-flow, other are control signals from control FSM yMAR may be a simple multiplexer rather than separate register yMBR is split in two (REG and IR) yLoad control for each register

CS Fakk Computer Organization - 18 Control FSM 16 Z N OP 16 ACREG 16 load path store path Data Memory (16-bit words) 16 OP 16 PCIR 16 data addr rd wr Inst Memory (8-bit words) data addr Block Diagram of Processor zRegister transfer view of Harvard architecture yWhich register outputs are connected to which register inputs yArrows represent data-flow, other are control signals from control FSM yTwo MARs (PC and IR) yTwo MBRs (REG and IR) yLoad control for each register

CS Fakk Computer Organization - 19 A simplified Processor Data-path and Memory zPrinceton architecture zRegister file zInstruction register zPC incremented through ALU zModeled after MIPS rt000 (used in 378 textbook by Patterson & Hennessy) yReally a 32 bit machine yWell do a 16 bit version memory has only 255 words with a display on the last one

CS Fakk Computer Organization - 20 Processor Control zSynchronous Mealy machine zMultiple cycles per instruction

CS Fakk Computer Organization - 21 Processor Instructions zThree principal types (16 bits in each instruction) typeoprsrtrdfunct R (egister) I (mmediate) 3337 J (ump) 313 zSome of the instructions add0rsrtrd0rd = rs + rt sub0rsrtrd1rd = rs - rt and0rsrtrd2rd = rs & rt or0rsrtrd3rd = rs | rt slt0rsrtrd4rd = (rs < rt) lw1rsrtoffsetrt = mem[rs + offset] sw2rsrtoffset mem[rs + offset] = rt beq3rsrtoffset pc = pc + offset, if (rs == rt) addi4rsrtoffsetrt = rs + offset j5target addresspc = target address halt7- stop execution until reset R I J

CS Fakk Computer Organization - 22 Tracing an Instruction's Execution zInstruction: r3 = r1 + r2 R0rs=r1rt=r2rd=r3funct=0 z1. Instruction fetch yMove instruction address from PC to memory address bus yAssert memory read yMove data from memory data bus into IR yConfigure ALU to add 1 to PC yConfigure PC to store new value from ALUout z2. Instruction decode yOp-code bits of IR are input to control FSM yRest of IR bits encode the operand addresses (rs and rt) xThese go to register file

CS Fakk Computer Organization - 23 Tracing an Instruction's Execution (contd) zInstruction: r3 = r1 + r2 R0rs=r1rt=r2rd=r3funct=0 z3. Instruction execute ySet up ALU inputs yConfigure ALU to perform ADD operation yConfigure register file to store ALU result (rd)

CS Fakk Computer Organization - 24 Tracing an Instruction's Execution (contd) zStep 1

CS Fakk Computer Organization - 25 Tracing an Instruction's Execution (contd) zStep 2 to controller

CS Fakk Computer Organization - 26 Tracing an Instruction's Execution (contd) zStep 3

CS Fakk Computer Organization - 27 Register-Transfer-Level Description zControl yTransfer data btwn registers by asserting appropriate control signals zRegister transfer notation: work from register to register yInstruction fetch: mabus PC;– move PC to memory address bus (PCmaEN, ALUmaEN) memory read;– assert memory read signal (mr, RegBmdEN) IR memory;– load IR from memory data bus (IRld) op add– send PC into A input, 1 into B input, add (srcA, srcB0, scrB1, op) PC ALUout– load result of incrementing in ALU into PC (PCld, PCsel) yInstruction decode: IR to controller values of A and B read from register file (rs, rt) yInstruction execution: op add– send regA into A input, regB into B input, add (srcA, srcB0, scrB1, op) rd ALUout– store result of add into destination register (regWrite, wrDataSel, wrRegSel)

CS Fakk Computer Organization - 28 Register-Transfer-Level Description (contd) zHow many states are needed to accomplish these transfers? yData dependencies (where do values that are needed come from?) yResource conflicts (ALU, busses, etc.) zIn our case, it takes three cycles yOne for each step yAll operation within a cycle occur between rising edges of the clock zHow do we set all of the control signals to be output by the state machine? yDepends on the type of machine (Mealy, Moore, synchronous Mealy)

CS Fakk Computer Organization - 29 Review of FSM Timing step 1step 2step 3 fetch decodeexecute IR mem[PC]; PC PC + 1; rd A + BA rs B rt to configure the data-path to do this here, when do we set the control signals?

CS Fakk Computer Organization - 30 instruction execution instruction decode LW SW ADD J reset FSM Controller for CPU (skeletal Moore FSM) zFirst pass at deriving the state diagram (Moore machine) yThese will be further refined into sub-states instruction fetch

CS Fakk Computer Organization - 31 FSM Controller for CPU (reset and inst. fetch) zAssume Moore machine yOutputs associated with states rather than arcs zReset state and instruction fetch sequence zOn reset (go to Fetch state) yStart fetching instructions yPC will set itself to zero mabus PC; memory read; IR memory data bus; PC PC + 1; reset instruction fetch Fetch

CS Fakk Computer Organization - 32 FSM Controller for CPU (decode) zOperation Decode State yNext state branch based on operation code in instruction yRead two operands out of register file xWhat if the instruction doesnt have two operands? instruction decode Decode branch based on value of Inst[15:13] and Inst[3:0] add

CS Fakk Computer Organization - 33 FSM Controller for CPU (Instruction Execution) zFor add instruction yConfigure ALU and store result in register rd A + B yOther instructions may require multiple cycles instruction execution add

CS Fakk Computer Organization - 34 FSM Controller for CPU (Add Instruction) zPutting it all together and closing the loop ythe famous instruction fetch decode execute cycle reset instruction fetch Fetchinstruction decode Decode add instruction execution add

CS Fakk Computer Organization - 35 FSM Controller for CPU zNow we need to repeat this for all the instructions of our processor yFetch and decode states stay the same yDifferent execution states for each instruction xSome may require multiple states if available register transfer paths require sequencing of steps