Principles Of Digital Design Chapter Register Transfer Specification And Design Chapter preview Boolean algebra Logic gates and flip-flops Finite-state machine Binary system and data representation Sequential design techniques Combinational components Generalized finite-state machines Logic design techniques Storage components 8 Register-transfer design Processor components Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine Register-transfer design z Each standard or custom IC consists of one or more datapaths and control units z To synthesize such IC we introduce the model of a FSM with a datapath (FSMD) z We demonstrate synthesis algorithms for FSMD model, including component selection, resource sharing, pipelining and scheduling Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine Example 7.1 Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine Design Model Control inputs Control unit Datapath inputs Control signals Status signals Control outputs Nextstate logic D Q D Q Control unit Copyright © 2004-2005 by Daniel D Gajski Datapath inputs Control signals Selector Register RF Mem D Datapath outputs High-level block diagram Control inputs Datapath Bus Bus Q State register Output logic */÷ ALU Bus Status signals Register Datapath Control outputs outputs Register-transfer-level block diagram Datapath Slides by Xi Cheng, University of California, Irvine Ones-counter specification Data Mask Temp Ocount Start = Start = Done=0; Data = Input Done=0; Ocount = Done=0; Mask = Done=0; Temp = Data AND Mask Data = Done=0; Ocount = Ocount + Temp Done=1; Data = Data >> Data = Done=1; Output =Ocount Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine FSDM Definition In Chapter we defined an FSM as a quintuple < S, I, O, f, h > where S is a set of states, I and O are the sets of input and output S , and h : S × I O symbols: f : S × I More precisely, I = A1 × A2 ×…Ak S = Q1 × Q2 ×…Qm O = Y1 × Y2 ×…Yn Where Ai, ≤ i ≤ k , is an input signal, Qi, ≤ i ≤ m is the flip-flop output and Yi, ≤ i ≤ n is an output signal To define a FSMD, we define a set of variables V = V1 × V2 ×…Vq which defines the state of the datapath by defining the values of all variables in each state = = { U U = {( W V ∈ ) ∈ W } } V∈ {≤ p = f ≥} I =I ×I C D where IC = A1 × A2 ×…Ak as before and ID = B1 × B2 ×…Bp, O =O ×O C D Where OC = Y1 × Y2 ×…Yn as before and OD = Z1 × Z2 ×…Zr Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine FSDM Definition With formal definition of expressions and relations over a set of variables we can simplify function f : ( S ×V ) × I S ×V by separating it into two parts: fC and fD The function fC defines the next state of the control unit S fC : S ×IC × STAT while the function fD defines the values of datapath variables in the next state V fD : S ×V × ID fD :={fDi : V × ID V : { Vj =ej | Vj Also, hC : S ×IC × STAT V, ej Expr ( V × ID )}} ∈ ∈ OC and hD : S ×V × ID Copyright © 2004-2005 by Daniel D Gajski OD Slides by Xi Cheng, University of California, Irvine FSMD specification of Ones-counter Next state Control Datapath Present (Start Data=0) Output output State 00 01 10 11 Done Outport Data Datapath Variables Ocount Temp Mask s0 s1 s0 s0 s1 s1 Z X X X X s2 s2 s2 s2 Z Inport X X X s2 s3 s3 s3 s3 s3 Z Data X X s4 s4 s4 s4 Z Data Ocount X Ocount Data AND Mask Mask X Mask s4 s5 s5 s5 s5 Z Data s5 s6 s6 s6 s6 Z Data Ocount+Temp s6 s4 s7 s4 s7 Z Data>>1 Ocount X Mask s7 s0 s0 s0 s0 Ocount Data Ocount X X State and output table Next state Control Datapath Present (Start Data=0) Output output Data Variables State 00 01 10 11 Done Outport Present State s0 Next state condition state Start = s0 [Start = Control and Datapath actions condition actions ] Done = s0 s1 s0 s0 s1 s1 Z s2 s2 s2 s2 Z Data = Inport s1 s2 Data = Inport s2 s3 s3 s3 s3 s3 Z Ocount = s2 s3 Ocount = s4 s4 s4 s4 Z Mask = s3 s4 Mask = s4 s5 s5 s5 s5 Z Temp = Data AND Mask s4 s5 Temp = Data AND Mask s5 s6 Ocount = Ocount + Temp s5 s6 s6 s6 s6 Z Ocount = Ocount + Temp s6 s4 s7 s4 s7 Z Data = Data >> s7 s0 s0 s0 s0 Ocount Data s6 s7 State and output table with variable assignments Copyright © 2004-2005 by Daniel D Gajski [Data = s1 s4 s7 s0 Data = Data >> ] [ Done = Data = Inport ] State-action table Slides by Xi Cheng, University of California, Irvine Algorithmic-State-Machine z Graphic representation of FSMD model z Equivalent to state-action table z Similar to a flowchart used for program description Copyright © 2004-2005 by Daniel D Gajski 10 Slides by Xi Cheng, University of California, Irvine Datapath with pipelined functional unit In In R2 R1 R3 Bus Bus 2-stage AU >>3 >>1 Bus Bus Out (a) Datapath with pipelined AU s0 Read R1 s1 s2 s3 a Read R2 b s4 s5 s6 t1 t1 x t2 t2 t3 s7 s10 s11 s12 t5 t7 t6 t4 AU stage |a| AU stage |b| |a| max |b| shifters - max + - max + max >>3 >>1 Write R1 a Write R2 b t1 x t2 t7 t3 t5 t6 t4 Outport Copyright © 2004-2005 by Daniel D Gajski s9 x Read R3 Write R3 s8 t7 (b) Timing diagram 48 Slides by Xi Cheng, University of California, Irvine Datapath pipelining In In s0 a = In b = In R2 R1 Bus Bus AU 1 s1 t1 = |a| >>3 >>1 Bus Bus s2 t2 = |b| R3 s3 R5 R4 Bus t4 = ( t1 , t2 ) >>1 Bus s4 x = max( t1 , t2 ) t3 = max ( t1 , t2 )>>3 AU s5 Bus t5 = x – t3 Out (b) Pipelined datapath s6 t6 = t4 + t5 s7 t7 = max ( t6 , x ) s8 Done = Out = t7 R1 = [ a, t1 ] R3 = [ t3, t5, t6, t7 ] R2 = [ b, t2 ] R4 = [ x ] AU1 = [ abs/min/max ] R5 = [ t4 ] AU2 = [ +/-/max ] (a) ASM Chart Copyright © 2004-2005 by Daniel D Gajski (c) Register and functional unit assignment 49 Slides by Xi Cheng, University of California, Irvine Datapath pipelining In In R2 R1 Bus Bus nth pair AU >>3 s0 s5 s6 s7 s8 s9 Read R3 t3 t6 t7 Read R4 x >>1 Bus Bus Read R1 s1 a Read R2 R3 R5 R4 b AU stage Bus s2 AU Bus Out (b) Pipelined datapath s3 s4 t1 t1 t2 t2 |a| |b| max Shifters Bus (n+1)th pair >>1 >>3 Write R1 a Write R2 b t1 t2 Read R5 x t4 AU stage Write R3 t3 Write R4 x Write R5 t5 - + max t5 t6 t7 t4 nth pair (d) Timing diagram Copyright © 2004-2005 by Daniel D Gajski 50 Slides by Xi Cheng, University of California, Irvine Timing diagram for datapath pipeline with pipelined units s0 Read R1 Read R2 AU1 stage AU1 stage Shifters Write R1 Write R2 Read R3 Read R4 Read R5 AU2 stage AU2 stage Write R3 Write R4 Write R5 Out Copyright © 2004-2005 by Daniel D Gajski s1 a s2 b s3 t1 t2 |a| |b| s4 t1 t2 s5 s6 s7 s8 s9 s10 s11 s12 s13 max |a| |b| max >>1 >>3 a b t1 t2 t3 x t5 t6 x t7 t4 - t3 x t4 + max - + max t5 t6 t7 t3 x t4 t7 51 Slides by Xi Cheng, University of California, Irvine Pipelined FSMD implementation ∗/÷ (a) Standard FSMD implementation ∗/÷ (b) FSMD implementation with control and datapath pipelining 52 Copyright © 2004-2005 by Daniel D Gajski Slides by Xi Cheng, University of California, Irvine ASM charts for pipelined FSMDs ∗/÷ (b) FSMD implementation with control and datapath pipelining (a) ASM chart Copyright © 2004-2005 by Daniel D Gajski (b) ASM chart for control pipeline with status register (c) ASM chart for control pipeline with status register and (d) ASM chart for control and datapath pipeline 53 control registers Slides by Xi Cheng, University of California, Irvine Scheduling RT description such as ASM chart specifies data operations in each state z Flowcharts or programming languages not have states, but only specify order in which operations are executed z Scheduling transforms flowcharts or programs with RT descriptions z Two types of scheduling z (a) resource constrained (resource given, minimize time) (b) time constrained (time given, minimize resources) Copyright © 2004-2005 by Daniel D Gajski 54 Slides by Xi Cheng, University of California, Irvine Control/dataflow graph for SRA a=In b=In a>b In1 In a b 0 Start a t1=|a| t2=|b| x=max (t1, t2) y=min(t1, t2) t3=x>>3 t4=y>>1 t5=x-t3 t6=t4+t5 t7= max(t6,x) Done=1 Out=t7 b |a| |b| max >>1 >>3 + max Out (b) Control/Data flow graph (a) Flowchart Copyright © 2004-2005 by Daniel D Gajski Done 55 Slides by Xi Cheng, University of California, Irvine Basic schedules (a) ASAP schedule Copyright © 2004-2005 by Daniel D Gajski (a) ALAP schedule 56 Slides by Xi Cheng, University of California, Irvine List scheduling algorithm Copyright © 2004-2005 by Daniel D Gajski 57 Slides by Xi Cheng, University of California, Irvine Resource-constrained scheduling Perfrom ASAP Perfrom ALAP Determine mobilities Create ready list Sort ready list by mobilities Schedule ops from ready list Delete scheduled ops from ready list Add new ops to ready list Increment state index no All ops scheduled? yes Copyright © 2004-2005 by Daniel D Gajski (a) ASAP (b) ALAP 58 (c) Ready list with mobilities (d) RC schedule Slides by Xi Cheng, University of California, Irvine Time-constrained scheduling Perfrom ASAP Perfrom ALAP Determine mobilities ranges Create probability distribution graphs All ops scheduled? no All ops scheduled? yes yes Schedule ops from ready list Schedule ops from ready list Copyright © 2004-2005 by Daniel D Gajski 59 Slides by Xi Cheng, University of California, Irvine TC schedule for SRA algorithm s1 |a| |b| s2 max s3 >>1 >>3 - s4 s5 + s6 max |a| |b| |b| max max |a| >>3 >>1 - >>3 - >>1 + + max s7 max Out s8 Out (a) ASAP Copyright © 2004-2005 by Daniel D Gajski (b) ALAP 60 (c) TC schedule Slides by Xi Cheng, University of California, Irvine Probability distribution graph before, during and after TC scheduling (a) Initial probability distribution graph (c) Distribution graph after max, + and –,>>3 and >>1 were scheduled Copyright © 2004-2005 by Daniel D Gajski (b) Distribution graph after max, + and – were scheduled (c) Distribution graph for final scheduled 61 Slides by Xi Cheng, University of California, Irvine Chapter summary We introduced RT design: z z FSMD model RT specification with ¾Static-action tables ¾ASM charts z z Procedure for synthesis from RT specification Design Optimization through ¾Register sharing ¾Unit chaining ¾Functional unit sharing ¾Multiclocking ¾Bus sharing z Design Pipelining ¾Unit pipelining ¾Control pipelining ¾Datapath pipelining z Scheduling of flowcharts Copyright © 2004-2005 by Daniel D Gajski 62 Slides by Xi Cheng, University of California, Irvine [...]... Square-root approximation Copyright © 2004-2005 by Daniel D Gajski 21 Slides by Xi Cheng, University of California, Irvine Register sharing (Variable merging) z Grouping of variables with nonoverlaping lifetimes z Each group shares one register z Grouping reduces number of registers needed in the design z Two algorithms: Copyright © 2004-2005 by Daniel D Gajski ‹ left-edge ‹ graph-partitioning 22 Slides by Xi... 2004-2005 by Daniel D Gajski Non-shared design 30 Shared design Slides by Xi Cheng, University of California, Irvine Complex library components c1 c0 Operation 0 1 absolute 1 0 minimum 1 1 maximum c1 c0 Unit for computing minimum, maxmum and absolute value 0 0 addition 0 1 minimum 1 0 subtraction 1 1 maximum Unit for computing addition, subtraction, minimum and maximum c1 c0 Operation 1 0 addition... Chart Copyright © 2004-2005 by Daniel D Gajski (b) Design without merged units 34 (c) Design with merged units Slides by Xi Cheng, University of California, Irvine Unit merging for SRA datapath (a) Compatibility graph (c) Compatibility graph after merging of min, + and _ Copyright © 2004-2005 by Daniel D Gajski (b) Compatibility graph after merging of + and _ (d) Final graph partitions 35 ASM Chart Slides... Initial compatibility grah a = In 1 b = In 2 Start (b) Compatibility graph after merging t3, t5 and t6 s1 0 1 t1 = |a| t2 = |b| s2 x = max( t1 , t2 ) y = min ( t1 , t2 ) s3 (c) Compatibility graph after merging t1, x and t7 t3 = x >> 3 t4 = y >>1 s4 t5 = x – t3 s5 (d) Compatibility graph after merging t2 and y t6 = t4 + t5 s6 t7 = max ( t6 , x ) s7 (e) Final compatibility graph Copyright © 2004-2005... = Q1Q’0DataLSB Load = s1 = Q’1Q0 Done = Output enable = s3= Q1Q0 0) Input-based version Copyright © 2004-2005 by Daniel D Gajski 17 Slides by Xi Cheng, University of California, Irvine Register- transfer synthesis z Register sharing Block diagram s0 a = In 1 b = In 2 Start s1 0 z Functional unit sharing 1 t1 = |a| t2 = |b| s2 x = max( t1 , t2 ) y = min ( t1 , t2 ) z Bus sharing s3 t3 = x >> 3 t4 = y... addition, subtraction, and absolute value Copyright © 2004-2005 by Daniel D Gajski Operation c2 c1 c0 Operation 0 0 1 addition 1 0 0 absolute absolute 1 0 1 subtraction subtraction 1 1 0 minimum 1 1 1 maximum 31 Unit for computing addition, subtraction, minimum, maximum and absolute value Slides by Xi Cheng, University of California, Irvine Operator merging for SRA implementation Compunoent AND Invert EX-OR... by Xi Cheng, University of California, Irvine Merging variables with common sources and destination a si x=a+b c b Selector d Selector + sj a,c b,d Selector Selector + y=c+d Partial ASM Chart Copyright © 2004-2005 by Daniel D Gajski Selector Selector x y Datapath without register sharing 25 Selector x,y Datapath with register sharing Slides by Xi Cheng, University of California, Irvine Graph partitioning... graph Copyright © 2004-2005 by Daniel D Gajski 27 Done = 1 Out = t7 ASM Chart Slides by Xi Cheng, University of California, Irvine Register assignment generated by the graph-partitioning algorithm z z z R1 = [ a , t1 , x , t7 ] R2 =[b , t2 , y , t3 , t5 , t6 ] R3= [ t4 ] Register assignments Datapath Copyright © 2004-2005 by Daniel D Gajski 28 Slides by Xi Cheng, University of California, Irvine Functional... Compatibiltity graph |a| 1 1 1 |b| 1 1 1 min 1 1 1 max 1 1 1 + 1 - 1 1 Total 5 6 4 (b) Cost table Unit (c) Merging altermative Compunoent AND Invert EX-OR Adder Selector Logic Logic Logic [| a |/min] 1 [| b |/max/+/-] 1 Total 2 1 1 1 2 1 1 2 1 2 2 (d) Cost table Compunoent AND Invert EX-OR Adder Selector Logic Logic Logic Unit [| a |/min/+] 1 1 1 2 ASM Chart Copyright © 2004-2005 by Daniel D Gajski [| b... algorithm Copyright © 2004-2005 by Daniel D Gajski 23 Slides by Xi Cheng, University of California, Irvine Register sharing by left-edge algorithm s1 s2 s3 s4 s5 s6 s7 a b t1 t2 x y t3 t4 t5 t6 t7 X X R1 = {a, t1, x, t7} R2 = {b, t2, y, t4, t6} X X X X X X X X s0 a = In 1 b = In 2 R3 = {t2, t5 } X Start Register assignments X s1 X X 0 1 t1 = |a| t2 = |b| s2 X x = max( t1 , t2 ) y = min ( t1 , t2 ) Sorted