All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

DSPA Solution Manual Chap 5

Tags

Transcript

Solutions to Assignment #4Chapter 5
5. The critical path lengths of an unfolded DFG only increase when a new arc isgenerated with no delays in the DFG; otherwise the path lengths remain the same. An arcwith D delays in the srcinal DFG produces J-D arcs with no delays in the J-unfolded DFG when J>D.If J>D, then the J unfolded graph will contain an additional arc without delays,and the path length for the J-unfolded DFG increases through those nodes, compared tothe (J-1) unfolded DFG.Therefore, the critical path of the J-unfolded graph is greater than or equal to thatof the (J-1) unfolded graph.7.
The DFG is given as
B A
(15)(5)(2)
DCE
(10)(5)3DD
The computation for the critical path
A B E
→ →
is given as 12 u.t. =
0
crit
T
.Following the algorithm given in Problem 6, we have:
01
25512;1228
crit
T J
= + + =⎡ ⎤= =⎢ ⎥⎢ ⎥
Applying unfolding of degree 2 we get
A0 A1D0C0B0B1 C1 D1
2DDD
E0E1
(2)(2)(5)(5)(10)(10) (15)(15)(5)(5)
112
215178;1738
crit
T J x J
= + = >⎡ ⎤= =⎢ ⎥⎢ ⎥
Applying unfolding of degree 3 we get
22
215178;
crit
T J x
= + = <
So the minimum unfolding factor to achieve iteration period of 8 u.t. is J=3.8.
The srcinal DFD is given as
B A
(20)(10)
D C
(20)3D(10)
The computation for the critical path
B C D A
→ → →
is given as20+20+10+10= 60 u.t.(a)
The 2-unfolded DFG is shown as
A0 A1D0C0B0B1 C1 D1
(10)(10)(20)(20)(20)(20) (10)(10)2DD
The retimed DFG after applying retiming on the the 2-unfolded DFG is given by
A0 A1D0C0B0B1 C1 D1
(10)(10)(20)(20)(20)(20) (10)(10)DDD
This unfolded DFG is retimed such that the computation time on the critical path isequal to 40
u.t
., and hence the sampling period is 20
u.t.
The retiming variable for each node is given as follows:
00001111
'()0'()1'()1'()0'()0'()1'()0'()0
r A r B r C r Dr A r B r C r D
= = − = − == = − = =
(b) The retiming function r for each node in the srcinal DFG can be computed as
01010101
()'()'()0()'()'()2()'()'()1()'()'()0
r A r A r Ar B r B r Br C r C r C r D r D r D
= + == + = −= + = −= + =
With this retiming function, the srcinal DFG can be retimed as follows:
B A
(20)(10)
D C
(20)D(10)DD
Its 2-unfolded version is the following:
A0 A1D0C0B0B1 C1 D1
(10)(10)(20)(20)(20)(20) (10)(10)DDD
01
40..
crit
T B C ut
= → =
The W and D matrices for the retimed version of the srcinal DFG is given as012310304060201260204050(,)(,)120140602030012020406010
W U V D U V
⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦
As can be verified, for all pairs of nodes U, V in the retimed version of the srcinalDFG,If D (U, V)
≥
40, then W (U, V) + r (V)-r (U)
≥
2 holds.11 (a). The retimed DFG is shown as
DDDD2D3D
DD3D D
The computation time for critical path for the retimed graph is 4 u.t. The iteration bound of the srcinal graph is given as61414max,..444
T ut
⎡ ⎤∞ = =⎢ ⎥⎣ ⎦
(b) The minimum unfolding factor J such that the J-unfolded DFG can be retimed toachieve a critical path computation time equal to J X
T
∞
, or a sample period equal to
T
∞
,is J=4. This can be verified by solving the retiming problems for the srcinalDFG:
ã
For all edges
e
U V
⎯⎯→
in the DFG, r(U)-r(V)
≤
w(e);

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks