Digital Logic Design - Lecture 32: Datapath Analysis

Lecture 32Datapath AnalysisOverviewDatapaths must deal with input and output data valuesImplement with tri-state buffersNecessary to control external interfacesPerform repetitive operationsSome datapaths require decision makingControl outputs implemented in ROMMoving towards softwareControl implemented as a series of instructionsUnderstanding the data and control path Datapath I/OA wire can be driven by only one tri-state at a timeIf InPass is active, AluPass must be inactiveIf AluPass is active, InPass must be inactiveFunctionXYLoadYLoadXALUInPassOutPassAluPassDatapath I/OTwo values enter from the left (A and B)Need to perform (A+B)+AIn -> X (Load A) In -> Y (Load B)A+B -> Y(A+B)+A -> OutFunctionXYLoadYLoadXALUInPassOutPassAluPassInOutFour steps and then repeatImplementing the Control ROMTwo values enter from the left (A and B)Need to perform (A+B)+AIn -> X (Load A) - State 00In -> Y (Load B) - State 01A+B -> Y - State 10(A+B)+A -> Out - State 11PS NS Function LoadX LoadY InPass AluPass OutPass00 01 000 1 0 1 0 001 10 000 0 1 1 0 0 11 011 0 1 0 1 0 00 011 0 0 0 1 1PSNS010001010010000011001101101010000110ROMControl outputs000110001111AddrMore Complicated ExampleCan we compute (A+B) . (A-B)?Currently, no place for intermediate storageSolution: Add RAM to datapath.FunctionXYLoadYLoadXALUInPassOutPassAluPassMore Complicated ExampleCan we compute (A+B) . (A-B)?Need to add intermediate storage.Typical sizes (1MB – 2GB)FunctionXYLoadYLoadXALUInPassOutPassAluPassRAMAddrReadWriteAdd RAM to the DatapathImplementing the Control ROMTwo values enter from the left (A and B)Need to perform (A+B) . (A-B)In -> X (Load A) - State 000In -> Y (Load B) - State 001A+B -> RAM[4] - State 010A-B -> X - State 011RAM[4] ->Y - State 100(A+B) . (A-B) ->Out - State 101PS NS Function LoadX LoadY InPass AluPass OutPass Addr Read Write000 001 000 1 0 1 0 0 000 0 0001 010 000 0 1 1 0 0 000 0 0010 011 011 0 0 0 1 0 100 0 1 011 100 010 1 0 0 1 0 000 0 0 100 101 000 0 1 0 0 0 100 1 0 101 000 110 0 0 0 1 1 000 0 0Does the Value of the Data Matter?Problem: Add A to itself until overflow occursAmount of steps depends on AFunctionXYLoadYLoadXALUInPassOutPassAluPassRAMAddrReadWriteHow can we determine if overflow occurred?OFImplementing the Control ROM using ConditionsOne value enters from the leftAdd A to itself until overflow occursIn -> X, Y (Load A, B) - State 0 - Next state 1X+Y -> Out, X - State 1 - Next state (1 if no overflow, 0 if overflow)Include overflow (OF) bit as a ROM inputNote that it doubles the size of the ROMPS OF NS Function LoadX LoadY InPass AluPass OutPass Addr Read Write0 0 1 000 1 1 1 0 0 000 0 00 1 1 000 1 1 1 0 0 000 0 01 0 1 011 1 0 0 1 1 000 0 01 1 0 011 1 0 0 1 1 000 0 0Bits in the ROMEach row indicates a ROM wordImplementing the Control ROM with ConditionalsControl path may have many inputsOverflow, carry out, zeroUsed to perform conditional operationsIf statements and loops in programming languagesAddrNS100011100000001000111000000010111001100000000110ROMControl outputs0011010110000011OF2PS OF NS Function LoadX LoadY InPass AluPass OutPass Addr Read Write0 0 1 000 1 1 1 0 0 000 0 00 1 1 000 1 1 1 0 0 000 0 01 0 1 011 1 0 0 1 1 000 0 01 1 0 011 1 0 0 1 1 000 0 0One More ExampleRead two values from RAM (locations 0 and 1) and store to location 2.Very common operation for microprocessorFunctionXYLoadYLoadXALUInPassOutPassAluPassRAMAddrReadWriteImplementing the Control ROMPerform memory reads and writesRAM[0] -> X - State 00RAM[1] -> Y - State 01X+Y -> RAM[2] - State 10PS NS Function LoadX LoadY InPass AluPass OutPass Addr Read Write00 01 000 1 0 0 0 0 000 1 001 10 000 0 1 0 0 0 001 1 0 00 011 0 0 0 1 0 010 0 1No interaction with outside interfaces (In, Out) is requiredVery similar to microprocessor operationsProcessor Construction Kit Subproblem 1: DATA PATHSSubproblem 2: CONTROLProcessor Compilation Software engineer writes C programCompiler software converts C to assembly codeAssembler converts assembly code to binary formatmain () {int A, B, C;C = A + B;}C programCompileLD R1, A ; load A to Reg R1LD R2, B ; load B to Reg R2ADD R3, R1, R2 ; Add R1, R2 -> R3ST R3, C ; Store result in CAssembly programA, B, and C are storage locations inmain memory (DRAM)SummaryDatapaths are important components of computer systemsInteraction between control and data path determines execution timeEach sequence of operations can be represented with a ROM programEach row in the state table corresponds to a word in the ROMMultiple rows for each state if the ROM has a control input (e.g. ALU overflow)Recap after Combinational LogicSequential Logic (Why) ?Sequential circuit has additional dimension which is timeCombinational logic only depends on current inputSequential circuit output depends on previous input other than current inputMore powerful than combinational logicAble to model condition that can’t be accommodated by combinational logicSequential Circuits: LatchesCircuits require memory to store intermediate dataSequential circuits use a periodic signal to determine when to store values.A clock signal can determine storage timesClock signals are periodicSingle bit storage element is a flip flopA basic type of flip flop is a latchLatches are made from logic gatesNAND, NOR, AND, OR, InverterSequential Circuits: LatchesLatches are based on combinational gates (e.g. NAND, NOR)Latches store data even after data input has been removedS-R latches operate like cross-coupled inverters with control inputs (S = set, R = reset)With additional gates, an S-R latch can be converted to a D latch (D stands for data)D latch is simple to understand conceptuallyWhen C = 1, data input D stored in latch and output as QWhen C = 0, data input D ignored and previous latch value output at QSequential Circuits: Flip flopsThe most fundamental sequential components are the latch and flip-flopThey store one bit of data and make it available to other componentsThe main difference between a latch and a flip-flop is that the first are level triggered and the latter are edge triggeredFlip-flops and latches have a clock inputSequential Circuits: Flip flopsFlip flops are powerful storage elementsThey can be constructed from gates and latches!D flip flop is simplest and most widely usedAsynchronous inputs allow for clearing and presetting the flip flop outputMultiple flops allow for data storageThe basis of computer memory!Combine storage and logic to make a computation circuitCombinational vs. SequentialCombinational Logic CircuitOutput is a function only of the present inputs.Does not have state information.Does not require memory.Sequential Logic Circuit (Finite State Machine)Output is a function of the present state and at times present state and input.Has state informationRequires memory.Uses Flip-Flops to implement memory.Synchronous vs. AsynchronousSynchronous Sequential Logic CircuitClockedAll Flip-Flops use the same clock and change state on the same triggering edge.Asynchronous Sequential Logic CircuitNo clockCan change state at any instance in time.Faster but more complex than synchronous sequential circuits.Shift RegistersMultiple flip flops can be combined to form a data register Shift registers allow data to be transported one bit at a timeRegisters also allow for parallel transfer Many bits transferred at the same timeShift registers can be used with adders to build arithmetic unitsRemember: most digital hardware can be built from combinational logic (and, or, invert) and flip flopsBasic components of most computersShift RegistersShift registers can be combined together to allow for data transferSerial transfer used in modems and computer peripherals (e.g. mouse)D flip flops allow for a simple designData clocked in during clock transition (rising or falling edge)Serial addition takes less chip area but is slowUniversal shift register allows for many operationsThe register is programmable.It allows for different operations at different timesCountersCounters are important components in computersThe increment or decrement by one in response to input Two main types of countersRipple (asynchronous) countersSynchronous countersRipple counters Flip flop output serves as a source for triggering other flip flopsSynchronous countersAll flip flops triggered by a clock signalSynchronous counters are more widely used in industry.CountersCounter: A register that goes through a prescribed series of statesBinary counterCounter that follows a binary sequenceN bit binary counter counts in binary from n to 2n-1Ripple counters triggered by initial Count signalApplications:WatchesClocksAlarmsWeb browser refreshTiming AnalysisCircuits do not respond instantaneously to input changesPredictable delay in transferring inputs to outputsPropagation delay Sequential circuits require a periodic clockGoal: analyze clock circuit to determine maximum clock frequencyRequires analysis of paths from flip-flop outputs to flip-flop inputsEven after inputs change, output signal of circuit maintains original output for short timeTiming AnalysisMaximum clock frequency is a fundamental parameter in sequential computer systemsPossible to determined clock frequency from propagation delays and setup timeThe longest path determines the clock frequenctAll flip-flop to flip-flop paths must be checkedHold time are satisfied by examining contamination delaysThe shortest contamination delay path determines if hold times are metCheck handout for more details and examples.RAMMemory is a collection of storage cells with associated input and output circuitryPossible to read and write cellsRandom access memory (RAM) contains words of informationData accessed using a sequence of signalsLeads to timing waveformsDecoders are an important part of memoriesSelects specific data in the RAMStatic RAM loses values when circuit power is removed.Read-Only Memory (ROM)Read-only memory can normally only be readInternal organization similar to SRAMROMs are effective at implementing truth tablesAny logic function can be implemented using ROMsMultiple single-bit functions embedded in a single ROMAlso used in computer systems for initializationROM doesn’t lose storage value when power is removedVery useful for implementing FSMsRead-Only Memory (ROM)An array of semiconductor devicesdiodestransistors field effect transistors2N words by M bitsData can be read but not changed(normal operating conditions)Data is written to the ROM once, and read from the ROM many times.A read-only memory (ROM) consists of an array of semiconductor devices that are interconnected to store a set of binary data.Once binary data is stored in the ROM, it can be read out whenever desired, but the data that is stored cannot be changed under normal operating conditions.ROMROMs are actually combinational devices, not sequential ones!You can’t store arbitrary data into a ROM, so the same address will always contain the same data.You can think of a ROM as a combinational circuit that takes an address as input, and produces some data as the output.A ROM table is basically just a truth table.The table shows what data is stored at each ROM address.You can generate that data combinationally, using the address as the input.Programmable Logic ArrayA ROM is potentially inefficient because it uses a decoder, which generates all possible minterms. No circuit minimization is done.Using a ROM to implement an n-input function requires:An n-to-2n decoder, with n inverters and 2n n-input AND gates.An OR gate with up to 2n inputs.The number of gates roughly doubles for each additional ROM input.A programmable logic array, or PLA, makes the decoder part of the ROM “programmable” too. Instead of generating all minterms, you can choose which products (not necessarily minterms) to generate.ALUMain computation unit in most computer systemsALUs perform a variety of different functionsAdd, subtract, OR, ANDExample: ALU chip (74LS382)Has data and control inputsIndividual chips can be chained together to make larger ALUsALUs are important parts of datapathsROMs often are used in the control pathBuild a data and control pathCircuit Maker SimulatorCircuit Implementation using ComputerCircuit AnalysisRich LibraryCan Add your own component but need professional version Student Version have certain limitations