Computer Organization - University Of Washington

Computer organization Computer design – an application of digital logic design proceduresComputer processing unit memory systemProcessing unit control datapathControl finite state machine inputs machine instruction, datapath conditionsoutputs register transfer control signals, ALU operation codesinstruction interpretation instruction fetch, decode, executeDatapath functional units registers functional units ALU, multipliers, dividers, etc.registers program counter, shifters, storage registersAutumn 20101CSE370 - XIX - Computer OrganizationStructure of a computer Block diagram viewaddressProcessorcentral processingunit (CPU)Controlread/writedatacontrol signalsMemorySystemData Pathdata conditionsinstruction unit– instruction fetch andinterpretation FSMAutumn 2010execution unit– functional unitsand registersCSE370 - XIX - Computer Organization2

Registers Selectively loaded – EN or LD inputOutput enable – OE inputMultiple registers – group 4 or 8 in umn 2010OE asserted causes FF state to beconnected to output pins; otherwise theyare left unconnected (high impedance)LD asserted during a lo-to-hi clocktransition loads new data into FFs3CSE370 - XIX - Computer OrganizationRegister transfer Point-to-point connection MUXMUXMUXMUXR0R1R2R3R0R1R2R3R2R3Common input from multiplexer(input bus) dedicated wiresmuxes on inputs ofeach registerload enablesfor each registercontrol signalsfor multiplexerMUXCommon bus with output enables(input/output bus) output enables and loadenables for each registerAutumn 2010R0CSE370 - XIX - Computer OrganizationR1BUS4

Register files Collections of registers in one package two-dimensional array of FFsaddress used as index to a particular wordcan have separate read and write addresses so can do both at same time4 by 4 register file 16 D-FFsorganized as four words of four bits eachwrite-enable (load)read-enable (output n 2010Q3Q2Q1Q05CSE370 - XIX - Computer OrganizationMemories Larger collections of storage elements implemented not as FFs but as much more efficient latcheshigh-density memories use 1 to 5 switches (transitors) per memory bitStatic RAM – 1024 words each 4 bits wide once written, memory holds as long as there is power applied not true for denser dynamic RAM – lose power, lose memoryaddress lines to select word (10 lines for 1024 words)read enablesame as output enableoften called chip select (CS)permits connection of many chips into larger array(tie multiple chips IO pins together)write enable (same as load)bi-directional data lines Autumn 2010output when reading, input when writingCSE370 - XIX - Computer 6

Instruction sequencing Example – an instruction toadd the contents of two registers (Rx and Ry)and place result in a third register (Rz)Step 1: get ADD instruction from memory into instruction register (IR)Step 2: decode instruction instruction in IR has “operation code” to identify it as an ADD instructionregister indices used to generate output enables for registers Rx and Ryregister index used to generate load signal for register RzStep 3: execute instruction enable Rx and Ry output and direct to ALU (possibly through busses/muxes)set ALU to perform ADD operationdirect result (through busses/muxes) to Rz so that it can be loaded intoregisterAutumn 2010CSE370 - XIX - Computer Organization7Instruction types Data manipulation Data staging add, subtractincrement, decrementmultiplyshift, rotateimmediate operandsload/store data to/from memoryregister-to-register moveControl conditional/unconditional branches in program flowsubroutine call and returnAutumn 2010CSE370 - XIX - Computer Organization8

Elements of the control unit (aka instruction unit) Standard FSM elements Plus additional “control” registers state registernext-state logicoutput logic (data-path/control signaling)Moore or synchronous Mealy machine (to avoid loops unbroken by FF)instruction register (IR)program counter (PC)Inputs/outputs outputs control elements of data pathinputs from data path used to alter flow of program (e.g., test if zero)Autumn 20109CSE370 - XIX - Computer OrganizationInstruction execution Control state diagram (for each diagram) InitInstructions partitioned into three classes resetfetch o-registerDifferent sequence throughdiagram for eachinstruction type (may needmore than one state)Autumn 2010ResetBranchBranchBranchTaken Not TakenCSE370 - XIX - Computer XEQInstr.Registerto-RegisterIncr.PC10

Data path (hierarchy) CinArithmetic circuits constructedin hierarchical and modular fashion each bit in datapathis functionally identical4-bit, 8-bit, 16-bit, 32-bit datapathsmay include carry-lookahead orcarry-select capabilityAinBinSumCoutAinHABinHACinAutumn 2010FACSE370 - XIX - Computer OrganizationSumCout11Data path (ALU) ALU block diagram input: data on which to operate and operation to performoutput: result of operation and status informationAB3232Operation32OverAutumn 2010S ZeroCSE370 - XIX - Computer Organization12

Data path (ALU registers) Accumulator (common register construct) One-address instructions special registerone of the inputs to ALUoutput of ALU always stored back in accumulatoronly need operation and address of one operand32other operand and destinationis accumulator registerREGAC – AC op Mem[addr]32"single address instructions”(AC implicit operand)OPAC32Multiple registers Overpart of instruction usedto choose register operandsAutumn 201032Zero13CSE370 - XIX - Computer OrganizationData path (bit-slice) Bit-slice concept – replicate to build n-bit wide R0R1frommemoryAutumn 2010.frommemoryCSE370 - XIX - Computer OrganizationCIfrommemory14

Instruction path Program counter (PC) Instruction register (IR) keeps track of program executionaddress of next instruction to read from memorymay have “auto-increment” feature or use ALU to “add 1”current instructionincludes ALU operation and address(es) of operand(s)also holds target of jump instruction if branch instructionimmediate operands – value represented explicitly in instructionRelationship to data path PC may be incremented through ALUcontents of IR may also be required as input to ALU – immediate operandsAutumn 2010CSE370 - XIX - Computer Organization15Data path (memory interface) Memory separate data and instruction memory (Harvard architecture) single combined memory (Princeton architecture) single address bus, single data busSeparate memory two address busses, two data bussesALU output - data memory inputinstruction register - data memory addressdata memory output - input to registersprogram counter - instruction memory addressinstruction memory output - instruction registerSingle memory ALU output - memory inputPC or IR - addressmemory output - instruction or data registersAutumn 2010CSE370 - XIX - Computer Organization16

Block diagram of processor (Harvard) Register transfer view of Harvard architecture black arrows represent data-flow between registersblue arrows other are control signals from control FSM(also load control for each register, not shown)2 MARs (PC and IR)32MAR memory address registerREG3 MBRs (AC, REG and IR)32MBR memory buffer registerloadpathAC32storepathOPOverrd wrdataData Memory(32-bit words)addr32ZeroControlFSM32IRPCdata3232Inst Memory(32-bit words)addrOP32Autumn 201017CSE370 - XIX - Computer OrganizationBlock diagram of processor (Princeton) Register transfer view of Princeton architecture black arrows represent data-flow between registersblue arrows other are control signals from control FSM(also load control and output enable for each register, not shown)2 MARs (PC and IR) multiplexed (3-state)loadMAR memory address registerpath323 MBRs (AC, REG and IR)REGACMBR memory buffer register3232OPOverControlFSMstorepathrd wrdataData Memory(32-bit words)addr32ZeroMAR32IRPC3232OP32Autumn 2010CSE370 - XIX - Computer Organization18

A simplified processor data-path and memory Modeled after MIPS R2000 Used in 378 text by Patterson & HennessyPrinceton architecture – shared data/instruction memory32-bit machine32 register filePC incremented through ALUMulti-cycle instructions in our implementation single-cycle for real R2000, you’ll see that in 378Only a subset of the instructions are implementedSynchronous Mealy (Moore) controllerAutumn 201019CSE370 - XIX - Computer OrganizationProcessor instructions Three principal types (32 bits in each instruction)typeR(egister)I(mmediate)J(ump) RIJop666rs55rt55rd5shft516funct626The instructions we will implement (only a small subset)addsubandorsltlwswbeqaddijhaltAutumn rsrttarget 4363742CSE370 - XIX - Computer Organizationrd rs rtrd rs - rtrd rs & rtrd rs rtrd (rs rt)rt mem[rs offset]mem[rs offset] rtpc pc offset, if (rs rt)rt rs offsetpc target addressstop execution until reset20

Our R2000 implementationAutumn 2010CSE370 - XIX - Computer Organization21Memorymodule Memory(address, write, read, data);input [31:0] address;input write, read;inout [31:0] data;reg[31:0] memory[0:255];wiredelayed write;assign #10 delayed write write;always @(posedge delayed write) beginmemory[address[7:0]] data;endassign data read ? memory[address[7:0]] : 32'hzzzzzzzz;endmoduleAutumn 2010CSE370 - XIX - Computer Organization22

Program (compute nth Fibonacci number)Compilerr1 0r2 1r0 mem [ rz 254 ]r0 mem[254];r1 0;r2 1;r3 ( rz r0 )if ( r3 rz ) goto exit2if ( rz rz ) goto entryif (r0 0) goto entry; else goto exit2;loop:loop:r1 r1 r2r0 r0 ( -1 )r1 r1 r2;r0 r0 – 1;entry:entry:ifr2r0if(r0 r2 r0 –(r0 if (r2 r0 if (goto0) goto exit1;r1;1;0) goto exit2; else goto loop;exit1:r2 r1;exit1:mem[255] r2;HALTexit2:r0 rz ) goto exit1r2 r1r0 ( -1 )r0 rz ) goto exit2loopr2 r1 rzexit2:mem [ rz 255 ] r2haltAutumn 201023CSE370 - XIX - Computer OrganizationMemory – initial contents (test terparameterparameterALULWSWBEQADDIJHALT ameterparameterADDSUBANDORSLT functfunctfunctinitial memory[8'h0f] U,{ADDI,{BEQ,{J,{ALU,{SW,{HALT,rz, r1, 16'h0000};rz, r2, 16'h0001};rz, r0, 16'h00fe};rz, r0, r3, shftX,r3, rz, 16'h0009};rz, rz, 16'h0002};r1, r2, r1, shftX,r0, r0, 16'hffff};r0, rz, 16'h0004};r2, r1, r2, shftX,r0, r0, 16'hffff};r0, rz, 16'h0002};26'h0000006};r1, rz, r2, shftX,rz, r2, 16'h00ff};26'hxxxxxxx};memory[8'hfe] 32'h00000004;endAutumn 2010SLT};ADD};ADD};OR}; 0 35 43 4 8 2 63 ry:exit1:exit2:parameter shftX r r0r1r2r3rz5'h00;5'h01;5'h02;5'h03;5'h1f;r1 0r2 1r0 mem [ rz 254 ]r3 ( rz r0 )if ( r3 rz ) goto exit2if ( rz rz ) goto entry /* goto entryr1 r1 r2r0 r0 ( -1 )if ( r0 rz ) goto exit1r2 r2 r1r0 r0 ( -1 )if ( r0 rz ) goto exit2goto loopr2 r1 rz/* r2 r1mem [ rz 255 ] r2halt// this is the input NCSE370 - XIX - Computer Organization24

ALUmodule ALU(RegA, PC, Inst, RegB, op, srcA, srcB, ALUout, zero, ut[31:0] RegA;[31:0] PC;[31:0] Inst;[31:0] RegB;[5:0] op;srcA;[1:0] srcB;[31:0] ALUout;zero, neg;wireregregregreg[31:0] A;[31:0] B;[31:0] result;zero;neg;always @(A or B or op) begincase (op)6'b000001: result A B;6'b000010: result A - B;6'b000100: result A & B;6'b001000: result A B;6'b010000: result A;6'b100000: result B;default:result 32'hxxxxxxxx;endcasezero (result 32'h00000000);neg result[31];endassign A (srcA) ? PC : RegA;assign ALUout result;always @(Inst or RegB or srcB) beginendmodulecase (srcB)2'b00: B RegB;2'b01: B 32'h00000000;2'b10: B {Inst[15], Inst[15], Inst[15], Inst[15], Inst[15], Inst[15],Inst[15], Inst[15], Inst[15], Inst[15], Inst[15], Inst[15],Inst[15], Inst[15], Inst[15], Inst[15], Inst[15:0]};2'b11: B 32'h00000001;endcaseendAutumn 2010CSE370 - XIX - Computer Organization25Registers and 3-state driversmodule Reg32 LD(D, LD, Q, clk);inputinputoutputinput[31:0] D;LD;[31:0] Q;clk;reg[31:0] Q;always @(posedge clk) beginif (LD) Q D;endendmodulemodule Tri32(I, OE, O);input [31:0] I;input OE;output [31:0] O;assign O (OE) ? I : 32'hzzzzzzzz;endmoduleAutumn 2010CSE370 - XIX - Computer Organization26