Unfolding（展开）

• Unfolding：
   • 是一种可以应用于DSP程序的转换技术，它产生一个新的程序来描述原有程序的多次Iteration。
   • 以J为展开因子（Unfolding Factor）展开一个DSP程序，就会产生一个以原程序连续执行J次的新程序。
• Unfolding的应用
   • 高速、低功耗DSP算法实现： 
         展开程序以发现其中的并发性；
         根据程序的并发性，设计并行结构，以便在更小的Iteration Period中完成程序，达到Iteration Bound，从而提高吞吐量，降低功耗；
  例子:
  • 编译理论中：Unfolding＝Loop Unrolling
  • 例子：Loop Unrolling
  
  
  
  
  

 

Unfolding ≡ Parallel Processing
在展开系统中，每个延时是J倍降速的。即如果一个延时单元的输入信号是x(kJ+m)，则该延时单元的输出是x((k-1)J+m)= x(kJ+m-J)。

Unfolding例子

几个符号

一种Unfolding方法

• 对于原始DFG中的每个节点U，画J个节点U0，U1，……，UJ-1；
• 对原始DFG中每一条边U V，如果有W个延时，则画J条边 ，分别具有 个延时。其中
  
  

 

Unfolding性质
　　（1）

• Unfolding算法保持DFG中的延时数目不变；
  
• Unfolding保持DSP程序的运算顺序限制（数据相关性）不变；

　　（2）

• 原始DFG中延时为Wl的loop，对应于J 阶展开后的DFG中的 gcd(Wl , J) 个loop，每个loop包含 Wl / gcd(Wl , J) 个延时和每个节点的 J / gcd(Wl , J) 个拷贝
• 一个Iteration Bound为 的DFG，J 阶展开后所得到的DFG的Iteration Bound为
  gcd：greatest common divisor，最大公约数

　　（3）

• 考虑原始DFG中延时为W的路径，当W<J 时，该路径的J 阶unfolding将得到 (J-W)个无延时路径和W个延时为1的路径；
• 原始DFG中包含J 个或更多延时的任何路径，都能生成J 个路径，其每个路径具有一个或更多延时。因此，原始DFG中包含J 个或更多延时的路径不能生成一条在J 阶展开DFG中的关键路径。

　　（4）

• 任何对J 阶展开后的DFG GJ 所能得到的的可行重定时（Retiming），都可以通过直接对原始DFG G重定时，再J 阶展开后得到。

应用：
　　减小Iteration Period
　　　• Iteration Bound 是指一个带反馈环路的DSP程序的Iteration Period的下界。即使有无穷多个处理器，实现的DSP程序的Iteration Period都不能小于
　　　•在某些情况下，如果不用Unfolding技术，DSP程序不能达到
　　　　　DFG中存在某个节点，其计算时间大于 ；
　　　　　DFG的Iteration Bound 不是整数；
　　　　　DFG中存在计算时间大于 的节点，且Iteration Bound 不是整数。

DFG中存在计算时间大于Iteration Bound的节点
　　（1）

DFG的Iteration Bound不是整数
　　（1）
DFG中存在计算时间大于Iteration Bound的节点， 且Iteration Bound不是整数
　　　　　这种情况下，使得Iteration Period能够等于Iteration Bound的最小展开因子是能够使 成为大于等于最长节点计算时间的整数的J的最小值。
　　　　　例如： ，最长节点计算时间为6， 则使得Iteration Period能够等于Iteration Bound的最小展开因子是6。

　　（2）

　　　

应用：设计并行处理结构

• FIR滤波器，J＝3 Unfolding：
  
  

 

 

　　（2）

 

  

<<上一节　　下一节>>