1CS61c – Final ReviewFall 2004Andy Carle12/12/2004Topics Before Midterm• C & Malloc• Memory Management•MIPS• Number Representation• Floating Point•CALTopics Since Midterm• Digital Logic– Verilog– State Machines•CPU Design• Pipelining•Caches• Virtual Memory• I/O and PerformanceToday’s Focus• Focus on material from after the midterm. Don’t forget to go back and look over the old review session and your midterm• More emphasis on material that we covered just after the midterm, less on stuff from the past few weeks.– Lots of stuff on digital logic– Like one slide on performance• My intent is to help you “page in” (no replacement policy, please) material from the second half of the course that you may have long since forgottenTopics Since Midterm• Digital Logic– Verilog– State Machines•CPU Design• Pipelining•Caches• Virtual Memory• I/O and PerformanceDigital Logic (and such)•Truth Tables• Boolean Algebra• Canonical SOP• Combinational Logic• State Machines• Timing Diagrams & Tables• Programmable Logic Arrays2Digital Logic – Truth Tables• A table describing the output of a function for every possible input• Usually done bitwise when dealing with digital logic•2n entries (each input can have two possible states)Digital Logic – Boolean OperatorsB A AND OR NAND NOR XOR XNOR NOT0 0 0 0 1 1 0 1 10 1 0 1 1 0 1 0 01 0 1 1 0 0 1 0 1 1 1 1 0 0 0 1 AB A+B (AB)’ (A+B)’ A⊕B A≡B A’Digital Logic – Boolean Algebra• An algebraic expression using Boolean operators– e.g. AB + A’B + A(B+C’)• Similar laws to normal algebra– Distributive: AB + A’B + AB + AC’– Idempotent: AB + A’B + AC’– Complementarity: B + AC’Digital Logic – Boolean Algebra LawsDigital Logic – Boolean AlgebraMinimize the following using Boolean Algebra simplification rules:What does this function do?(( ) ) ( )saab b ab=++++(( ) ) ( )saab b ab=++++(( ) ) ( )saab b ab=++++Digital Logic – Boolean Algebra SolutionSimplifies to:sab ab=+This is an XOR3Digital Logic – Canonical SOP Form• Standardized form to describe a truth table uniquely• For every 1 in the output column of the Truth Table have a term in the SOP• Put every input variable in every term, with the ones that were 0 for that entry in the TT negatedDigital Logic – Combinational Logic• Built from Boolean Algebra operators turned in to gates• Output is purely a function of current input• Therefore, can not have memory or remember state• However, this is perfect for describing a truth table as we have seen it so far!Digital Logic – Sequential Logic & State• To implement many practical circuits we need some form of “memory”.• Registers (created from Flip Flops) are our statefull circuit elements.• Adding state to a circuit introduces a notion of time centered around a clock– Complicates Truth Table– Necessitates Timing DiagramsDigital Logic – TimingDigital Logic – Finite State Machines• An abstraction of any system with a finite number of states and logical transitions between them• Useful when trying to come up with the truth table for a problem• States in a FSM are represented by data stored in registersDigital Logic – Putting It All TogetherExerciseCome up with the FSM, Truth Table (NS/Output), Canonical SOP form, Simplified Boolean Equation, and circuit diagram for this function over a continuous bit stream:Output 1 if the input was a 0. Output 0 if the input was a 1. Unless it was the 3rd1 in a row, in which case you output 1 (and start over counting 1s.4FSM Solution – Created At Review Solution• MSB(NS) = S1’ * S0 * n• LSB(NS) = S1’ * S0’ * n• OUT = S1’ * n’ + S1 * S0’Digital Logic – Verilog• Hardware Description Language• Verilog description is a collection of interconnected modules• All modules work in parallel• Structural vs. BehavioralDigital Logic – VerilogExerciseImplement the following circuit in both structural and behavioral Verilog:Digital Logic – VerilogBehavioralmodule pri_enc(in0, in1, in2, e0, e1);input in0, in1, in2;output e0, e1;assign e0 = (~in1 & in0) | in2;assign e1 = in1 | in2;endmodule;Digital Logic – VerilogStructuralmodule pri_enc(in0, in1, in2, e0, e1);input in0, in1, in2;output e0, e1;wire notIn1, and01;not(in1, notIn1);and(notIn1, in0, and01);or(and01, in2, e0);or(in1, in2, e1);endmodule;5Digital Logic – Programmable Logic Arrays• Creating customized hardware is expensive• We would like to be able to pre-fabricate a circuit and then allow it to be programmed by the developer• PLAs are the answer!• Review how to program one on your ownTopics Since Midterm• Digital Logic– Verilog– State Machines•CPU Design• Pipelining•Caches• Virtual Memory• I/O and PerformanceSingle Cycle CPU Design• Overview Picture• Two Major Issues– Datapath–Control• Control is the hard part, but is make easier by the format of MIPS instructionsSingle-Cycle CPU DesignDataOutClk5Rw Ra Rb32 32-bitRegistersRdALUClkData InDataAddressIdealDataMemoryInstructionInstructionAddressIdealInstructionMemoryClkPC5Rs5Rt32323232ABNext AddressControlDatapathControl SignalsConditionsCPU Design – Steps to Design/Understand a CPU• 1. Analyze instruction set architecture (ISA) => datapath requirements• 2. Select set of datapath components and establish clocking methodology• 3. Assemble datapath meeting requirements• 4. Analyze implementation of each instruction to determine setting of control points.• 5. Assemble the control logicng it All Together:A Single Cycle Dataimm1632ALUctrClkbusWRegWr3232busA32busB55 5Rw Ra Rb32 32-bitRegistersRsRtRtRdRegDstExtenderMux3216imm16ALUSrcExtOpMuxMemtoRegClkData InWrEn32AdrDataMemoryMemWrALUEqualInstruction<31:0>010101<21:25><16:20><11:15><0:15>Imm16RdRtRs=AdderAdderPCClk00Mux4nPC_selPC ExtAdrInstMemory6CPU Design – Components of the Datapath• Memory (MEM)– instructions & data• Registers (R: 32 x 32)– read RS– read RT– Write RT or RD•PC• Extender (sign extend)• ALU (Add and Sub register or extended immediate)• Add 4 or extended immediate to PCCPU Design – Control Signals• Branch: 1 for branch, 0 for other• ALU control• MemWrite, MemRead(=MemtoReg): 1 if writing to/reading from memory, 0 if not• ALUSrc: choice of ALU input; 1 for immed, 0 for reg• RegWrite: 1 if writing a reg, 0 if not• RegDst: 1 if output
View Full Document
Unlocking...