CS61C Machine Structures Lecture 21 State Elements Circuits that Remember 3 8 2006 John Wawrzynek www cs berkeley edu johnw www inst eecs berkeley edu cs61c CS 61C L21 State Elements Circuits That Remember 1 Wawrzynek Spring 2006 UCB Review ISA is very important abstraction layer Contract between HW and SW Basic building blocks are logic gates Clocks control pulse of our circuits Voltages are analog quantized to 0 1 Circuit delays are fact of life Two types Stateless Combinational Logic in which output is function of input only State circuits e g registers CS 61C L21 State Elements Circuits That Remember 2 Wawrzynek Spring 2006 UCB Uses for State Elements 1 As a place to store values for some indeterminate amount of time Register files like 1 31 on the MIPS Memory caches and main memory 2 Help control the flow of information between combinational logic blocks State elements are used to hold up the movement of information at the inputs to combinational logic blocks and allow for orderly passage CS 61C L21 State Elements Circuits That Remember 3 Wawrzynek Spring 2006 UCB Accumulator Example Why do we need to control the flow of information S 0 for i 0 i n i S S Xi Assume Want Each X value is applied in succession one per cycle After n cycles the sum is present on S CS 61C L21 State Elements Circuits That Remember 4 Wawrzynek Spring 2006 UCB First try Does this work Feedback Nope Reason 1 What is there to control the next iteration of the for loop Reason 2 How do we say S 0 CS 61C L21 State Elements Circuits That Remember 5 Wawrzynek Spring 2006 UCB Second try How about this Rough timing Register is used to hold up the transfer of data to adder CS 61C L21 State Elements Circuits That Remember 6 Wawrzynek Spring 2006 UCB Register Details What s inside n instances of a Flip Flop Flip flop name because the output flips and flops between and 0 1 D is data Q is output Also called d type Flip Flop CS 61C L21 State Elements Circuits That Remember 7 Wawrzynek Spring 2006 UCB What s the timing of a Flip flop 1 2 Edge triggered d type flip flop This one is positive edge triggered On the rising edge of the clock the input d is sampled and transferred to the output At all other times the input d is ignored Example waveforms CS 61C L21 State Elements Circuits That Remember 8 Wawrzynek Spring 2006 UCB What s the timing of a Flip flop 2 2 Edge triggered d type flip flop This one is positive edge triggered On the rising edge of the clock the input d is sampled and transferred to the output At all other times the input d is ignored CS 61C L21 State Elements Circuits That Remember 9 Wawrzynek Spring 2006 UCB Administrivia CS 61C L21 State Elements Circuits That Remember 10 Wawrzynek Spring 2006 UCB Accumulator Revisited proper timing 1 2 Reset input to register is used to force it to all zeros takes priority over D input Si 1 holds the result of the ith 1 iteration Analyze circuit timing starting at the output of the register CS 61C L21 State Elements Circuits That Remember 11 Wawrzynek Spring 2006 UCB Accumulator Revisited proper timing 2 2 reset signal shown Also in practice X might not arrive to the adder at the same time as Si 1 Si temporarily is wrong but register always captures correct value In good circuits instability never happens around rising edge of clk CS 61C L21 State Elements Circuits That Remember 12 Wawrzynek Spring 2006 UCB Pipelining to improve performance 1 2 Extra Register are often added to help speed up the clock rate Timing Note delay of 1 clock cycle from input to output Clock period limited by propagation delay of adder shifter CS 61C L21 State Elements Circuits That Remember 13 Wawrzynek Spring 2006 UCB Pipelining to improve performance 2 2 Insertion of register allows higher clock frequency More outputs per second CS 61C L21 State Elements Circuits That Remember 14 Timing Wawrzynek Spring 2006 UCB Finite State Machines FSM Introduction You have seen FSMs in other classes Same basic idea The function can be represented with a state transition diagram With combinational logic and registers any FSM can be implemented in hardware CS 61C L21 State Elements Circuits That Remember 15 Wawrzynek Spring 2006 UCB Finite State Machine Example 3 ones FSM to detect the occurrence of 3 consecutive 1 s in the input Draw the FSM Assume state transitions are controlled by the clock on each clock cycle the machine checks the inputs and moves to a new state and produces a new output CS 61C L21 State Elements Circuits That Remember 16 Wawrzynek Spring 2006 UCB Hardware Implementation of FSM Therefore a register is needed to hold the a representation of which state the machine is in Use a unique bit pattern for each state Combinational logic circuit is used to implement a function maps from present state and input to next state and output CS 61C L21 State Elements Circuits That Remember 17 Wawrzynek Spring 2006 UCB Hardware for FSM Combinational Logic Next lecture we will discuss the detailed implementation but for now can look at its functional specification truth table form Truth table PS Input NS Output 00 0 00 0 00 1 01 0 01 0 00 0 01 1 10 0 10 0 00 0 10 1 00 1 CS 61C L21 State Elements Circuits That Remember 18 Wawrzynek Spring 2006 UCB General Model for Synchronous Systems CS 61C L21 State Elements Circuits That Remember 19 Wawrzynek Spring 2006 UCB And In conclusion State elements are used to Build memories Control the flow of information between other state elements and combinational logic D flip flops used to build registers Clocks tell us when D flip flops change Setup and Hold times important We pipeline long delay CL for faster clock Finite State Machines extremely useful You ll see them again 150 152 164 CS 61C L21 State Elements Circuits That Remember 20 Wawrzynek Spring 2006 UCB
View Full Document
Unlocking...