Chapter 5: Unfolding
Keshab K. Parhi
• Unfolding ≡ Parallel Processing
2-unfolded
(1)
B
(1)
A
2D
A0àB0=> A2àB2=> A4àB4=>…..
A1àB1=> A3àB3=> A5àB5=>…..
2 nodes & 2 edges
T∞ = (1+1)/2 = 1ut
(1) 0,2,4,….
B0
(1)
A0
T’∞ = 2ut
(1)
A1
T’∞ = 2ut
D
(1) 1,3,5,….
B1
D
4 nodes & 4 edges
T∞ = 2/2 = 1ut
• In a ‘J’ unfolded system each delay is J-slow => if input to a delay element
is the signal x(kJ + m), the output is x((k-1)J + m) = x(kJ + m – J).
Chap. 5
2
• Algorithm for unfolding:
Ø For each node U in the original DFG, draw J node U0 , U1 ,
U2 ,…, UJ-1 .
Ø For each edge U → V with w delays in the original DFG,
draw the J edges Ui → V(i + w)%J with (i+w)/J delays for i
= 0, 1, …, J-1.
U
37D
V
w = 37
⇒(i+w)/4 = 9, i = 0,1,2
=10, i = 3
U0
9D
V0
U1 9D
V1
U2
V2
U3 10D
9D
V3
ØUnfolding of an edge with w delays in the original DFG
produces J-w edges with no delays and w edges with 1delay in
J unfolded DFG for w < J.
ØUnfolding preserves precedence constraints of a DSP
program.
Chap. 5
3
2D
D
V
U
3-unfolded
6D
5D
T
DFG
U0
V0 2D
U1
V1 2D T1
U2 D
D
T0
V2 2D T2
2D
Properties of unfolding :
Ø Unfolding preserves the number of delays in a DFG.
This can be stated as follows:
w/J + (w+1)/J + … + (w + J - 1)/J = w
Ø J-unfolding of a loop l with wl delays in the original DFG
leads to gcd(wl , J) loops in the unfolded DFG, and each
of these gcd(wl , J) loops contains wl/ gcd(wl , J) delays
and J/ gcd(wl , J) copies of each node that appears in l.
Ø Unfolding a DFG with iteration bound T∞ results in a Junfolded DFG with iteration bound JT∞ .
Chap. 5
4
• Applications of Unfolding
Ø Sample Period Reduction
Ø Parallel Processing
• Sample Period Reduction
Ø Case 1 : A node in the DFG having computation
time greater than T∞ .
Ø Case 2 : Iteration bound is not an integer.
Ø Case 3 : Longest node computation is larger
than the iteration bound T∞, and T∞ is not an
integer.
Chap. 5
5
nguon tai.lieu . vn