Xem mẫu

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