Digital Design Systems Overview and Logic Circuits

Digital Design: A Systems Approach Lecture 17: Overview and Wrapup 1 (c) 2005-2012 W. J. Dally

Restoring logic gives noise margins Input 0 ? 1 Damage Damage Voltage VIL VIH VNML VNMH Output 0 Tran 1 Voltage VOL VOH 2 (c) 2005-2012 W. J. Dally

Represent values with bits Truth values, e.g., door is open Single bit Numbers, temperature (range, precision) Integers, fixed-point, floating-point Sets, e.g., colors Encoded one-hot or binary Compound Includes several of above 3 (c) 2005-2012 W. J. Dally

Combinational Logic We compose gates into combinational logic circuits Output depends only on present value of inputs a out b c d This circuit realizes the function f= _______________ Why don t we realize this function with a single gate? 4 (c) 2005-2012 W. J. Dally

Functions built from decoders and other blocks Example find maximum of 256 small 4-bit numbers Decode each number 4 16 bits (256 times) OR these together w/16 256-bit ORs (each a 4-level tree of 4-input ORs) Use an Arbiter to get highest of 16 Encode the 16 4 Arbiter Decode Encode OR Need to see if this is more efficient than a tournament Can this determine which input has the winning number? 5 (c) 2005-2012 W. J. Dally

Building Blocks xin ain TwoInArray 9 win cout 9 bin win oin ain a TwoInArray 9 Select3 block xout cout b out 9 9 bin c don't lose Empty empty 9 first open square 6 (c) 2005-2012 W. J. Dally

Iterative Circuits in7 in6 in0 in in in remout remout remout rem15:14 rem13:12 rem3:2 rem1:0 out Mul3 Bit Mul3 Bit Mul3 Bit remin remin remin =0 0 2 2 2 2 7 (c) 2005-2012 W. J. Dally

Arithmetic a3 a2 a1 a0 b0 b1 0 FA FA FA FA 0 b2 FA FA FA FA 0 b3 FA FA FA FA 0 p7 p6 p5 p4 p3 p2 p1 p0 8 (c) 2005-2012 W. J. Dally

Sequential Logic Sequential logic circuits have state. Next state and outputs are a function of inputs and present state. state next_state D Q CL s s in out n m clk 9 (c) 2005-2012 W. J. Dally

Sequential circuits work properly if setup and hold time constraints are met c d a Min D Q a b c Max D Q tk clk Suppose tdCQ = ts = th = 100ps, tk = 200ps or 200ps, tmin = 50ps, tmax=2ns. Is hold time met? What is minimum tcy ? 10 (c) 2005-2012 W. J. Dally

Finite-State Machines Finite-state machines are described by a next-state and output function Can be described with a state diagram or state table. carew carew gns yns gew yew 100 001 010 001 001 100 001 010 11 (c) 2005-2012 W. J. Dally

carew carew //------------------------------------------------------ // Traffic_Light // Inputs: // clk - system clock // rst - reset - high true // carew - car east/west - true when car is waiting in east-west direction // Outputs: // lights - (6 bits) {gns, yns, rns, gew, yew, rew} // Waits in state GNS until carew is true, then sequences YNS, GEW, YEW // and back to GNS. //------------------------------------------------------ module Traffic_Light(clk, rst, carew, lights) ; input clk ; input rst ; // reset input carew ; // car present on east-west road output [5:0] lights ; // {gns, yns, rns, gew, yew, rew} wire [`SWIDTH-1:0] state, next ; // current and next state reg [`SWIDTH-1:0] next1 ; // next state w/o reset reg [5:0] lights ; // output - six lights 1=on carew carew gns yns gew gew 100 001 010 001 001 100 001 010 //--------------------------------------------- // FSM Example for Lecture 7 // Bill Dally 1/30/03 //--------------------------------------------- // define state assignment - one hot //--------------------------------------------- `define SWIDTH 4 `define GNS 4'b1000 `define YNS 4'b0100 `define GEW 4'b0010 `define YEW 4'b0001 //--------------------------------------------- // define output codes //--------------------------------------------- `define GNSL 6'b100001 `define YNSL 6'b010001 `define GEWL 6'b001100 `define YEWL 6'b001010 //--------------------------------------------- // define flip-flop //--------------------------------------------- module DFF(clk, in, out) ; parameter n = 1; // width input clk ; input [n-1:0] in ; output [n-1:0] out ; reg [n-1:0] out ; // instantiate state register DFF #(`SWIDTH) state_reg(clk, next, state) ; // next state and output equations - this is combinational logic always @(state or carew) begin case(state) `GNS: {next1, lights} = {(carew ? `YNS : `GNS), `GNSL} ; `YNS: {next1, lights} = {`GEW, `YNSL} ; `GEW: {next1, lights} = {`YEW, `GEWL} ; `YEW: {next1, lights} = {`GNS, `YEWL} ; endcase end // add reset assign next = rst ? `GNS : next1 ; endmodule always @(posedge clk) out = in ; endmodule 12 (c) 2005-2012 W. J. Dally

Data paths are more easily described by realizing the next state function from building blocks 3 n in next count 2 D Q n n n Mux4 1 ^ +/-1 n 0 clk 0 n 4 rst up C L down load 13 (c) 2005-2012 W. J. Dally

module Timer(clk, rst, load, in, done) ; parameter n=4 ; input clk, rst, load ; input [n-1:0] in ; output done ; wire [n-1:0] count, next_count ; wire done ; DFF #(n) cnt(clk, next_count, count) ; always@(rst, load, in, out) begin casex({rst, load, done}) 3'b1xx: next_count = 0 ; // reset 3'b001: next_count = 0 ; // done 3'b01x: next_count = in ; // load default: next_count = count-1 b1; // count down endcase end assign done = (count == 0) ; endmodule 14 (c) 2005-2012 W. J. Dally

Factoring Factor Machines to reduce complexity Divide and conquer car_ew Intersection FSM lights car_lt 9 light time4 done done load on 3 Light FSM Timer time3 tdone tload Timer 15 (c) 2005-2012 W. J. Dally

Most FSMs are a combination of a data path realized from building blocks, and a controller designed from a state diagram. price n Mux3 enough 2 3 a>=b n next amount +/- 5 1 D Q 2 n n n n 0 Mux4 1 10 0 n n sub_addN n 3 25 clk 0 n 4 rst nickel dime Logic quarter dispense (c) 2005-2012 W. J. Dally

Microcode Microcode, realizing a FSM with a memory - a programmable FSM Compress the size of the memory by encoding control and output instructions o o out1 D Q e1 E target/value Mux3 s +1 0 s clk nuPC uPC Memory a d 1 D Q s s s x+s 0 2 s 3 o o outn D Q inputs en Branch Logic E i Output Decode clk x n instruction x Branch Instruction 1 condition branch target 1 3 4 Store Instruction 1 destination value (c) 2005-2012 W. J. Dally 1 3 4

System Design a process Specification Understand what you need to build Divide and conquer Break it down into manageable pieces Define interfaces Clearly specify every signal between pieces Hide implementation Choose representations Timing and sequencing Overall timing use a table Timing of each interface use a simple convention (e.g., valid ready) Add parallelism as needed (pipeline or duplicate units) Timing and sequencing (of parallel structures) Design each module Code Verify Iterate back to the top at any step as needed. 18 (c) 2005-2012 W. J. Dally

DES Example firstKey Key key Generator nextKey DES Decrypt firstBlock Ciphertext Storage Text Checker cipherTextBlock plainTextBlock isPlainText nextBlock startDES DESdone start firstKey nextKey Master FSM DESdone firstBlock nextBlock isPlainText startDES 19 (c) 2005-2012 W. J. Dally

Pipelining Modules are composed in pipelines and parallel configurations Throughput and latency A B C D Master A B C D 20 (c) 2005-2012 W. J. Dally

How does a typical pipeline handshake work? What signals are used between stages? What values must these signals have for data to move from one stage to the next? 21 (c) 2005-2012 W. J. Dally

Flow Control 22 (c) 2005-2012 W. J. Dally

Pipelines Pipelines can stall and idle When do these happen? How can you prevent them A B 10 cycles 5 or 15 cycles A B A S B I A B A S B A S B I 23 (c) 2005-2012 W. J. Dally

Synchronization Failure 24 (c) 2005-2012 W. J. Dally

Failure Probability and Error Rate Each event can potentially fail. Failure rate = event rate x failure probability - t ( ) w = = + P P P t t cy f exp F E S s h t - t ( ) w = = + F f f P t t f cy f exp e F s h e t Clk DVF=1 ts+th tcy DVS tw 25 (c) 2005-2012 W. J. Dally

What is wrong with this picture? counter cnt_w cnt cnt_s D Q D Q 4 4 4 clk1 clk2 26 (c) 2005-2012 W. J. Dally

Asynchronous logic design Continuous state feedback Affected by races and hazards Synthesize/Analyze with flow tables a in Toggle b in a b 27 (c) 2005-2012 W. J. Dally

Congratulations! You are now a logic designer. To become a better one: Practice, practice, practice Study other designs Become a student of the art of digital design Stay on top of the latest technology New parts, processes, tools, techniques Read the trade press Take more courses Go to conferences Build a network (of people) Continue learning What you have now is a license to learn It s a fun field Design lots of neat things chips, boards, systems Play with fun tools, processes, chips, lab equipment Meet fun people (mostly) Make $$ 28 (c) 2005-2012 W. J. Dally