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）
