Start with a calculator…Calculator LayoutCalculator Bit DesignQuestion: How do we subtract?Question: How do we compute two’s complement?Operations, RevisitedProblem: OverflowOverflow CircuitAdding multiplicationWhat do we need?Multiplying Calculator LayoutControl FSM: Timing is KeySlide 13What do we we haveComputer OrganizationTri-State BuffersTri-States vs. MuxRegister TransferOpen Collector ConceptStructure of a ComputerRegistersSlide 22Register FilesMemoriesInstruction SequencingInstruction TypesElements of the Control Unit (aka Instruction Unit)Instruction ExecutionData Path (Hierarchy)Data Path (ALU)Data Path (ALU + Registers)Data Path (Bit-slice)Instruction PathData Path (Memory Interface)Block Diagram of ProcessorSlide 36A Simplified Processor Data-path and MemoryProcessor ControlProcessor InstructionsTracing an Instruction's ExecutionTracing an Instruction's Execution (cont’d)Slide 42Slide 43Slide 44Register-Transfer-Level DescriptionRegister-Transfer-Level Description (cont’d)Review of FSM TimingFSM Controller for CPU (skeletal Moore FSM)FSM Controller for CPU (reset and instruction fetch)FSM Controller for CPU (decode)FSM Controller for CPU (Instruction Execution)FSM Controller for CPU (Add Instruction)FSM Controller for CPUNext Up: AddersCS 150 – Spring 2008 – Lec #12: Computer Org I - 1Start with a calculator…Integer calculator6 bitsValues 0-63Operations: +, -, Complement, bitwise logical operationsA+B, A-B, A & B, A | B, A = B, ~B (bitwise complement), -B (same as 0-A), A XOR BCS 150 – Spring 2008 – Lec #12: Computer Org I - 2Calculator Layout66A BCOperation6CS 150 – Spring 2008 – Lec #12: Computer Org I - 3Calculator Bit DesignDominated by additionHalf-AdderCS 150 – Spring 2008 – Lec #12: Computer Org I - 4Question: How do we subtract?Tied up in: how do we represent negative numbersOption 1: “Sign-and-Magnitude’’ High-order bit represents signLow-order 5 bits represent magnitude-7 = 10111Key negative: need a separate circuit for subtraction!(How would you do it?)Option 2: “Two’s Complement”Take advantage of fact that 64 = 0 (in 6-bit machine)Therefore: 64-x = -x-7 = 64-7 = 57 = 111001 (Notice 7 = 000111)Key: We can subtract by adding!CS 150 – Spring 2008 – Lec #12: Computer Org I - 5Question: How do we compute two’s complement?Positive numbers: 000001…..011111 (1 - 31)Negative numbers: 111111….100001 (-1 - -31)Notice: 111111 = -1“One’s Complement of A”: Flip each bit of A = ~AOne’s complement of 7 (000111) = 111000Notice: A + ~A = 111111 (-1) XOR of each bit is 1AND of each bit is 0Therefore: -A = ~A + 1CS 150 – Spring 2008 – Lec #12: Computer Org I - 6Operations, RevisitedADD, OR, AND, COMPLEMENT, EQUALITY, XORNegation and Subtraction implemented by manipulating inputs Per-Bit DesignCarry-in to bit 0CS 150 – Spring 2008 – Lec #12: Computer Org I - 7Problem: OverflowConsider 31+31 = 62 = 64-2 = -2!Not what we want!X+Y >= 32 (or X + Y <= -32) yield incorrect resultsNumbers >= 32 or <= -32 can’t be representedKey: detect when it happens and flag itException: “Overflow”How to detect it?Observation I:Can only happen when two positive or two negative numbers added togetherHigh-order bit of operands equalObservation II:Happens only on an AddObservation III:High-Order bit of output != high-order bit of inputsCS 150 – Spring 2008 – Lec #12: Computer Org I - 8Overflow Circuit Also Add: • Test for negative (high-order bit is 1, “N”)• Test for zero (all bits are 0, “Z”)CS 150 – Spring 2008 – Lec #12: Computer Org I - 9Adding multiplicationCombinational circuit is big! (see HW#1)Roughly N^2 elements for NxN multiplicationSo we do it sequentially…just use the algorithm we all learned in schoolPartial result = 0, multiplier = A, multiplicand = BFor I = 1 to Nbits-1 if lsb of multiplier is 1, result = result + multiplicandMultiplicand = multiplicand << 1Multiplier = multiplier >> 1What about sign?Simple algorithm (not optimal!)S = sign(A x B)C = |A|x|B|if (S) result = -C else result = CCS 150 – Spring 2008 – Lec #12: Computer Org I - 10What do we need?Minor:Shifter (too easy to spend class time on!)Test lsb for 1/0 (just run an extra wire from low-order input to ALU)Major:Place to store partial resultsPlace to store sign of resultActions dependent on valuesProgram for multiplication algorithmThese are easy, but change the character of the device!CS 150 – Spring 2008 – Lec #12: Computer Org I - 11Multiplying Calculator Layout66A BCOperation6RegistersControl FSMCS 150 – Spring 2008 – Lec #12: Computer Org I - 12Control FSM: Timing is KeyBasically the same program we saw before, BUTNeed to keep track of timing!•Compute sign of result•Load multiplier with |A|•Load multiplicand with |B|•Load partial result with 0•If lsb of multiplier is 1•Add multiplicand to partial result•Shift multiplier right•Shift multiplicand left•Negate result if neededCS 150 – Spring 2008 – Lec #12: Computer Org I - 13By This time, we’re getting close to something else…CS 150 – Spring 2008 – Lec #12: Computer Org I - 14What do we we haveControl program in FSM that sequences instructionsStorage that are loaded in response to data conditionsActions taken, or not, in response to conditionsThis is better known as a computerAll we have to add is memoryCS 150 – Spring 2008 – Lec #12: Computer Org I - 15Computer OrganizationComputer design as an application of digital logic design proceduresComputer = processing unit + memory systemProcessing unit = control + datapathControl = finite state machineInputs = machine instruction, datapath conditionsOutputs = register transfer control signals, ALU operation codesInstruction interpretation = instruction fetch, decode, executeDatapath = functional units + registersFunctional units = ALU, multipliers, dividers, etc.Registers = program counter, shifters, storage registersCS 150 – Spring 2008 – Lec #12: Computer Org I - 16Tri-State Buffers0, 1, Z (high impedance state)inoutOEif OE then Out = In else “disconnected”+inout+outOEinBasic InverterInverting BufferCS 150 – Spring 2008 – Lec #12: Computer Org I - 17Tri-States vs. MuxSel2:1 Mux0 1A
View Full Document
Unlocking...