Topics Before Midterm CS61c Final Review Fall 2004 C Malloc Memory Management MIPS Number Representation Floating Point CAL Andy Carle 12 12 2004 Topics Since Midterm Digital Logic Verilog State Machines CPU Design Pipelining Caches Virtual Memory I O and Performance Topics Since Midterm Digital Logic Verilog State Machines CPU Design Pipelining Caches Virtual Memory I O and Performance Today 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 forgotten Digital Logic and such Truth Tables Boolean Algebra Canonical SOP Combinational Logic State Machines Timing Diagrams Tables Programmable Logic Arrays 1 Digital 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 Algebra Digital Logic Boolean Operators B 0 0 1 1 AB A AND OR NAND 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 A B AB NOR 1 0 0 0 A B XOR XNOR NOT 0 1 1 1 0 0 1 0 0 1 A B A B A Digital Logic Boolean Algebra Laws 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 s a ab b a b Digital Logic Boolean Algebra Minimize the following using Boolean Algebra simplification rules s a ab b a b Digital Logic Boolean Algebra Solution Simplifies to s ab ab This is an XOR What does this function do 2 Digital 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 negated Digital Logic Sequential Logic State Digital 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 Timing 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 Diagrams Digital 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 registers Digital Logic Putting It All Together Exercise Come 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 3rd 1 in a row in which case you output 1 and start over counting 1s 3 FSM 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 Behavioral Digital Logic Verilog Behavioral module 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 Verilog Exercise Implement the following circuit in both structural and behavioral Verilog Digital Logic Verilog Structural module 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 4 Topics Since Midterm Digital Logic Programmable Logic Arrays Creating customized hardware is expensive We would like to be able to prefabricate a circuit and then allow it to be programmed by the developer PLAs are the answer Review how to program one on your own Digital Logic Verilog State Machines CPU Design Pipelining Caches Virtual Memory I O and Performance Single Cycle CPU Design Single Cycle CPU Design Overview Picture Two Major Issues Ideal Instruction Instruction Memory Rd Rs Rt 5 5 5 Instruction Datapath Control PC Clk 32 A Rw Ra Rb 32 32 bit 32 Registers B Clk Data 32 Address ALU Next Address Address Control is the hard part but is make easier by the format of MIPS instructions Control Control Signals Conditions Data In Data Ideal Out Data Memory Clk 32 Datapath ng it All Together A Single Cycle Data Instruction 31 0 0 15 11 15 Rs 1 Analyze instruction set architecture ISA datapath requirements 16 20 Inst Memory Adr 21 25 CPU Design Steps to Design Understand a CPU Rt Rd Imm16 RegDst Equal ALUctr MemWr MemtoReg Rd Rt 1 0 Rs Rt RegWr 5 5 5 busA Rw Ra Rb busW 32 32 32 bit 0 32 32 Registers busB 0 32 Clk 32 WrEnAdr 1 1 Data In Data imm16 32 Clk 16 Clk Memory nPC sel 2 Select set of datapath components and establish clocking methodology imm16 Mux ALU Extender Mux PC Adder PC Ext 5 Assemble the control logic Mux Adder 4 Analyze implementation of each instruction to determine setting of control points 00 4 3 Assemble datapath meeting requirements ExtOp ALUSrc 5 CPU Design Control Signals CPU 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 PC 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 reg is specified in bits 15 11 R fmt 0 if output reg is in bits 20 16 I fmt MemtoReg 1 if writing reg from memory 0 if writing reg from ALU PCSrc 1 for branch address 0 for PC 4 What Does An ADD Look Like CPU Design Instruction Implementation Instruction 31 0 0 15 11 15 Rs lw sw beq R format add sub and or slt corresponding I format addi 16 20 Rt Rd Imm16 RegDst Equal ALUctr MemWr MemtoReg Rd Rt 1 0 Rs Rt RegWr 5 5 5 busA busW Rw Ra Rb 32 32 32 bit 0 32 32 Registers busB 0 32 Clk …
View Full Document
Unlocking...