6.4.2 状态机与数据路径.ppt

6 4 2状态机与数据路径 数据通道结构 FSMD系统结构 S S0 S1 S2 Sl 表示状态集合 I i0 i1 i2 im 表示输入集合 O o0 o1 o2 on 表示输出集合 V v0 v1 v2 vn 表示变量集合 F S I V S表示映射某种集合到某一状态的瞬态函数 H S O V表示当前状态映射到输出或变量的激活函数 S0是初始状态 研究目标 1 资源约束 硬件功能单元如 算数单元 abs max min 移位器2 时间约束 时序约束如 有限状态机状态数量 流水线结构 时间调度与分配 数据流结构X a axb cxd d数据流向图把计算表达式转化为计算路径的方法同步结构 任何时刻只能保存一个数值 异步结构 每条线对应数据队列 数据进出队列与节点的数据处理是异步操作 数据流 X a axb cxd d 调度算法 1 7 调度算法 2 7 ASAP assoonaspossible 假设每一操作要在一个时钟内精确执行 在每一个状态内 功能单元和资源是可变的 执行的操作都是可变的 ALAP aslateaspossible 如果计算路径保持到最终的计算步骤 则操作在最后可能的状态内执行 ASAP ALAP timeconstraintis4 调度算法 3 7 mobility Scheduling 资源约束Onemultiplierandtwoadders 调度算法 4 7 功能单元分配 Multi adder 1 adder 2 S 1op1op5S 2op7op2S 3op3S 4op6op4S 5op8 资源分配 调度算法 5 7 寄存器分配 lifetimeofeachoperand 需要7registers 调度算法 6 7 LeftedgealgorithmR1 a t3 t4R2 b t2 t7R3 c t6R4 dR5 eR6 t1R7 t5 调度算法 7 7 Datapath优化 1 Resourceoptimization a 存储共享 b 功能单元共享 c 总线共享 d 寄存器合并2 Timeoptimization a 连接或多循环 b 功能单元pipelining c 数据路径pipelining d 控制路径pipelining 连接与多循环操作 连接允许在同一状态中执行两个以上操作的串行执行 连接减少状态数并增加功能 多循环操作允许一个操作在两个以上时钟周期执行操作 多循环操作减小功能单元的尺寸 连接与多循环操作常常被用在非关键路径以提高资源利用率和功能 交通信号控制器 1 7 ControlUnit Datapath Counter Comparator Red Green Yellow NextStateLogic OutputLogic StateRegisters Seq Comb Comb Recount counter R Y G 1 100 1 010 1 001 0 100 0 010 0 001 Recount Counter16 RedGreenYellow Input Output RtGtYt Current times Recount counter 420 R time 4 1 5cyclesG time 2 1 3cyclesY time 0 1 1cycles TrafficLightController 2 7 moduletraffic Clock Reset Red Green Yellow inputClock Reset outputRed Green Yellow wireRecount conter wire 3 0 Counter Number Traffic Control Clock Clock Reset Reset Recount Counter16 Recount conter Red Red Green Green Yellow Yellow Datapath Clock Clock Reset Reset RGY Red Green Yellow Recount Recount conter endmodule moduleDatapath Clock Reset RGY Recount inputClock Reset input 2 0 RGY outputRecount wire 3 0 Counter Number CompareA1 current times Counter Number RGY RGY Recount conter16 Recount Counter16A2 Clock Clock Reset Reset Recount Counter16 Recount Count Out Counter Number endmodule TrafficLightController 3 7 moduleCounter16 Clock Reset Recount Counter16 Count Out inputClock Reset Recount Counter16 output 3 0 Count Out reg 3 0 Count Out always posedgeClock beginif Reset Count Out 0 elsebeginif Recount Counter16 Count Out 0 elseCount Out Count Out 1 endendendmodule TrafficLightController 4 7 modulecompare current times RGY Recount conter16 input 2 0 RGY input 3 0 current times outputRecount conter16 regRecount conter16 parameterR times 4 G times 2 Y times 0 always RGY begincase RGY 3 b100 beginif current times R times Recount conter16 1 elseRecount conter16 0 end 3 b001 beginif current times Y times Recount conter16 1 elseRecount conter16 0 end3 b010 beginif current times G times Recount conter16 1 elseRecount conter16 0 enddefault Recount conter16 1 endcaseendendmodule TrafficLightController 5 7 StateRegister Seq C NextStateLogic Comb C moduleTraffic Control Clock Reset Recount Counter16 Red Green Yellow inputClock Reset Recount Counter16 outputRed Green Yellow regRed Green Yellow reg 1 0 currentstate nextstate parameter 1 0 Red Light 0 Green Light 1 Yellow Light 2 always posedgeClock beginif Reset currentstate Red Light elsecurrentstate nextstate end always currentstate begincase currentstate Red Light beginif Recount Counter16 nextstate Green Light elsenextstate Red Light endGreen Light beginif Recount Counter16 nextstate Yellow Light elsenextstate Green Light endYellow Light beginif Recount Counter16 nextstate Red Light elsenextstate Yellow Light enddefault nextstate Red Light endcaseend TrafficLightController 6 7 OutputLogic Comb C always currentstate begincase currentstate Red Light beginRed 1 b1 Green 1 b0 Yellow 1 b0 endGreen Light beginRed 1 b0 Green 1 b1 Yellow 1 b0 endYellow Light beginRed 1 b0 Green 1 b0 Yellow 1 b1 end default beginRed 1 b0 Green 1 b0 Yellow 1 b0 endendcaseendendmodule TrafficLightCon