CS 61C L21 State Elements: Circuits That Remember (1) Wawrzynek Spring 2006 © UCB3/8/2006John Wawrzynek(www.cs.berkeley.edu/~johnw)www-inst.eecs.berkeley.edu/~cs61c/CS61C – Machine StructuresLecture 21 - State Elements: Circuitsthat RememberCS 61C L21 State Elements: Circuits That Remember (2) Wawrzynek Spring 2006 © UCBReview…°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 (&,|,~), inwhich output is function of input only• State circuits (e.g., registers)CS 61C L21 State Elements: Circuits That Remember (3) Wawrzynek Spring 2006 © UCBUses for State Elements1) As a place to store values for someindeterminate amount of time:• Register files (like $1-$31 on the MIPS)• Memory (caches, and main memory)2) Help control the flow of informationbetween combinational logic blocks.• State elements are used to hold up themovement of information at the inputs tocombinational logic blocks and allow fororderly passage.CS 61C L21 State Elements: Circuits That Remember (4) Wawrzynek Spring 2006 © UCBAccumulator ExampleWant: S=0; for (i=0;i<n;i++) S = S + XiWhy do we need to control the flow of information?Assume:•Each X value is applied in succession, oneper cycle.•After n cycles the sum is present on S.CS 61C L21 State Elements: Circuits That Remember (5) Wawrzynek Spring 2006 © UCBFirst try…Does this work?Nope! Reason #1… What is there to control thenext iteration of the ‘for’ loop?Reason #2… How do we say: ‘S=0’?FeedbackCS 61C L21 State Elements: Circuits That Remember (6) Wawrzynek Spring 2006 © UCBSecond try…How about this?Roughtiming…Register is used to hold up the transfer of data to adder.CS 61C L21 State Elements: Circuits That Remember (7) Wawrzynek Spring 2006 © UCBRegister Details…What’s inside?° n instances of a “Flip-Flop”° Flip-flop name because the output flips andflops between and 0,1° D is “data”, Q is “output”° Also called “d-type Flip-Flop”CS 61C L21 State Elements: Circuits That Remember (8) Wawrzynek Spring 2006 © UCBWhat’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 dis sampled and transferred to the output. Atall other times, the input d is ignored.”° Example waveforms:CS 61C L21 State Elements: Circuits That Remember (9) Wawrzynek Spring 2006 © UCBWhat’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 dis sampled and transferred to the output. Atall other times, the input d is ignored.”CS 61C L21 State Elements: Circuits That Remember (10) Wawrzynek Spring 2006 © UCBAdministrivia -CS 61C L21 State Elements: Circuits That Remember (11) Wawrzynek Spring 2006 © UCBAccumulator Revisited (proper timing 1/2)° Reset input to register isused to force it to allzeros (takes priority overD input).° Si-1 holds the result of theith-1 iteration.° Analyze circuit timingstarting at the output ofthe register.CS 61C L21 State Elements: Circuits That Remember (12) Wawrzynek Spring 2006 © UCBAccumulator Revisited (proper timing 2/2)° reset signal shown.° Also, in practice X mightnot arrive to the adder atthe same time as Si-1° Si temporarily is wrong,but register alwayscaptures correct value.° In good circuits,instability never happensaround rising edge of clk.CS 61C L21 State Elements: Circuits That Remember (13) Wawrzynek Spring 2006 © UCBPipelining to improve performance (1/2)Timing…Extra Register are often added to helpspeed up the clock rate.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 (14) Wawrzynek Spring 2006 © UCBPipelining to improve performance (2/2)Timing…° Insertion of register allows higher clockfrequency.° More outputs per second.CS 61C L21 State Elements: Circuits That Remember (15) Wawrzynek Spring 2006 © UCBFinite State Machines (FSM) Introduction° You have seenFSMs in otherclasses.° Same basic idea.° The function can berepresented with a“state transitiondiagram”.° With combinationallogic and registers,any FSM can beimplemented inhardware.CS 61C L21 State Elements: Circuits That Remember (16) Wawrzynek Spring 2006 © UCBFinite State Machine Example: 3 ones…Draw the FSM…FSM to detect the occurrence of 3 consecutive 1’s in the input.Assume state transitions are controlled by the clock:on each clock cycle the machine checks the inputs and movesto a new state and produces a new output…CS 61C L21 State Elements: Circuits That Remember (17) Wawrzynek Spring 2006 © UCBHardware Implementation of FSM+= ?… Therefore a register is needed to hold the a representation of whichstate the machine is in. Use a unique bit pattern for each state.Combinational logic circuit isused to implement a functionmaps from present state andinput to next state and output.CS 61C L21 State Elements: Circuits That Remember (18) Wawrzynek Spring 2006 © UCBHardware for FSM: Combinational Logic100110000010010101000001001100000000OutputNSInputPSTruth table…Next lecture we will discuss the detailed implementation,but for now can look at its functional specification, truthtable form.CS 61C L21 State Elements: Circuits That Remember (19) Wawrzynek Spring 2006 © UCBGeneral Model for Synchronous SystemsCS 61C L21 State Elements: Circuits That Remember (20) Wawrzynek Spring 2006 © UCB“And In conclusion…”°State elements are used to:• Build memories• Control the flow of information between otherstate 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) &
View Full Document
Unlocking...