Iteration Bound

 

回顾几个定义

• Iteration：
     算法执行一次叫做一个Iteration。
• Iteration Period：
     算法执行一次所用的时间。
• Critical Path：
     组合逻辑：输入到输出的最长路径；
     时序逻辑：所有路径中，不存在延时单元的最长路径,即任何两个延时单元之间的路经中最长的路径 
     系统性能受限于Critical Path。
• Latency：输出与相应输入的时间间隔
     组合逻辑：门延时个数
     时序逻辑：时钟周期个数

算法执行顺序的限制

• DFG的每条边都定义了一个顺序限制：
     没有延时单元的边 Intra-Iteration Constraint
     有延时单元的边 Inter-Iteration Constraint
  

  

      例子:
      

            

Loop

Loop Bound
算法中第j个loop的loop bound 定义为：
 例子：

 

Loop Bound 例子

 

Iteration Bound

• Critical Loop： 
     一个DSP算法中，具有最大Loop Bound的Loop
• Iteration Bound:
     算法中的反馈环路导致算法具有Iteration Bound；
     Critical Loop的Loop Bound，即DSP算法最大的Loop Bound；
     对应最小输入间隔（采样周期的下界） 、最大输入速率；
  

  

 

Critical Loop 例子
具有多个Loop的DSP算法：

 

Iteration Bound 例子
   Loop Bound

 

Iteration Bound计算方法

• Longest Path Matrix (LPM)
• Minimum Cycle Mean (MCM)
• Negative Cycle Detection (NCD)

     Longest Path Matrix 算法
      • 算法中有d个延时（D1, D2, ……, Dd），则构造d个矩阵
      
         其中每个元素 表示：
             从Di到Dj具有m-1个延时的最长路径的计算时间；
             如果不存在这样的路径，则为-1 。 
      • Iteration Bound:      

          

          对角元素：具有m个延时的环路中，最长的计算时间

Longest Path Matrix 算法例子

Iteration Bound:

• 算法中的反馈环路导致算法具有Iteration Bound；
• Critical Loop的Loop Bound，即DSP算法最大的Loop Bound；
• 对应于：最小输入间隔（采样周期的下界） 、最大输入速率（采样频率的上界） ；
• 具有多种计算方法计算，可用计算机实现。

 

 下一页   重定时（Retiming）

 

 

 

<<上一节　　下一节>>