JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

68

Timing and Code Size Optimization on
Achieving Full Parallelism in Uniform Nested
Loops
Y. Elloumi, M.Akil and M.H. Bedoui
Abstract- Multidimensional Retiming is one of the most important optimization techniques to improve timing parameters of nested
loops. It consists in exploring the iterative and recursive structures of loops to redistribute computation nodes on cycle periods, and thus
to achieve full parallelism. However, this technique introduces a large overhead in a loop generation due to the loop transformation. The
provided solutions are generally characterized by an important cycle number and a gr eat code size. It represents the most limiting
factors while implementing them in embedded systems.
In this paper, we present a new Multidimensional Retiming technique, called “Optimal Multidimensional Retiming” (OMDR). It reveals
the timing and dat a dependency characteristics of nodes, to minimize the overhead. The experimental results show that the average
improvement on t he execution time of the nested loops by our technique is 19.31% compared to the experiments provided by an
existent Multidimensional Retiming Technique. The average code size is reduced by 43.53% compared to previous experiments.
Index Terms— Graph Theory, Multidimensional Applications, Optimization, Parallelism and concurrency.

——————————  ——————————

1 INTRODUCTION

T

he design of real time systems should respect many
constraints such as the execution time and code size,
which require using optimization techniques. The
Retiming presents one of these techniques which can be used
to add and remove registers in order to provide a more
efficient circuit [1].
The increased complexity of such application leads to the
frequent use of a nested iterative and recursive loops. Such
applications can be modeled as “Multidimensional Data
Flow Graph” (MDFG). The standard software pipelining
techniques can only be used to optimize a one-dimensional
loop. When they are applied to optimize nested loops, the
performance improvement is very limited [8].
Other works are proposed to offer an optimization
technique taking advantage of the multiple nested loops,
which is called “Multi-Dimensional Retiming” (MDR). It
aims achieving full parallelism of uniform nested loops. It
consists in scheduling the MDFG with the minimum cycle
period and modifying the execution order of nodes, such as
each one is executed in a separate cycle.
But, Achieving full parallelism requires adding a large
code overhead [2],[3]. It dramatically increases the whole
code size of the provided MDFG. Furthermore, this extra
code requires a significant cycle number to be executed
outside the loop body. Thus, the provided solution does not
allow achieving an application with an adequate execution
time and a code size. It represents a limiting factor to
implement the provided MDFG in a real-time embedded
system.
We propose in this paper a new technique of MDR,
called “Optimal Multidimensional Retiming”. It allows
————————————————

• Y. Elloumi is a P.H.D. student in Paris-Est University, 93162 Noisy le
Grand Cedex, France.
• M. Akil is Professor at computer science department, ESIEE, Paris, 93162
Noisy le Grand Cedex, France.
• M.H. Bedoui is Professor in faculty of medicine of Monastir, University of
Monastir, 5019, Monastir, Tunisia,

redistributing optimally the nodes on cycle periods, while
scheduling the MDFG with the minimal cycle period. This
technique significantly allows optimizing the number of
period cycles (notably the execution time) and the code size,
by exploring the execution time and data dependency
between nodes belonging to the MDFG. Thus, it provides
enhanced solutions, compared to the existent techniques.
The rest of the paper is organized as follow. In section 2,
we give an overview of MDFG formalism. In section 3, we
list the existent MDR techniques and their constraints and
limits. In section 4, we present the theory of the “Optimal
Multidimensional Retiming” technique by describing the
principles and basics concepts, and proposing the
correspondent algorithms. Experimental results are
presented in section 5, followed by concluding remarks in
section 6.

2 MULTIDIMENSIONAL DATA FLOW GRAPH
The Multidimensional Data Flow Graph (MDFG) is an
extension of the classic data flow graph that allows to
represent a nested iterative and recursive structures. It is
modeled by a node-weighted and edge-weighted directed
graph such as 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡), where V is the set of
computation nodes, 𝐸𝐶 𝑉 × 𝑉 is the set of edges, and 𝑑(𝑒𝑖 ) is
a function from E to Z n , representing the multidimensional
delay between two nodes, where n is the number of
dimensions (loops), and 𝑡(𝑣𝑗 ) is a function from V to the
positive integers, representing the computation time of the
node 𝑣𝑗 .
For a MDFG with n dimensions, each edge 𝑒 ∶ 𝑣𝑖 → 𝑣𝑗 is
characterized by a delay where 𝑑(𝑒) = (𝑐1 , 𝑐2 , … , 𝑐𝑛 ). The
value 𝑐𝑘 represents the difference between the execution
iteration of 𝑣𝑗 and the execution iteration of 𝑣𝑖 of the loop 𝑘.
We show in Fig.1.a a two-dimensional Data Flow Graph
(2DFG) corresponding the Wave Digital Filter described in
Algorithm 1, which is composed of two nested loops. The
execution of each node in V exactly represents one iteration,
which is the execution of one instance of the loop body. Each
edge belonging to the 2DFG shown in Fig.1.a is labeled by a

delay 𝑑(𝑒) = (𝑑. 𝑥, 𝑑. 𝑦). Both terms « 𝑑. 𝑥 » and « 𝑑. 𝑦 »

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

represent the difference between the iteration number
executing 𝑣𝑗 and the iteration number executing 𝑣𝑖 , in the
outermost loop as well as in the innermost loop [9].
For an edge 𝑒 : 𝑣𝑖 → 𝑣𝑗 , the delay 𝑑(𝑒) = (0, 𝑥) consists
in the execution of 𝑣𝑖 and 𝑣𝑗 in the same iteration of the
outermost loop. For the innermost loop, if the node vi is
executed in the iteration 𝑘, the node 𝑣𝑗 is executed in the
ALGORITHM 1
WAVE DIGITAL FILTER
0: For i from 0 to m do
1: For j from 0 to n do
2:
D(i,j)= B(i -1 , j+1) × C(i -1 , j-1)
3:
A(i,j)= A(i,j) × 5
4:
B(i,j)= A(i,j) + 1
5:
C(i,j)= A(i,j) + 2
6: End for
7: End for

G illustrates the dependencies between copies of nodes
representing the MDFG G, such as the CDG shown in Fig.2.b
which corresponds to the MDFG G in Fig.1.a. A node in CDG
is a computational cell that represents a complete iteration.
The CDG of a nested loop is bounded by the loop indexes.
A schedule vector s defines a sequence of execution in
the cell dependency graph. The CDG shown in Fig.2.b, can
be executed by a row-wise execution sequence, i.e., the
schedule vector 𝑠 = (1,0). A legal MDFG 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡) is
realizable if there exists a schedule vector s for the cell
dependency graph in respect to G; i.e., 𝑠 × 𝑑(𝑒) ≥ 0, 𝑒 ∈ 𝐸,
and no cycle exists in its corresponding CDG. Note that delay
vectors (0,1) and (0, −1) are both legal in respect to the
schedule vector 𝑠 = (1,0), but they create cycles in cell
dependency graph.

3 MULTIDIMENSIONAL RETIMING

iteration(𝑘 − 𝑥). An edge with zero delay 𝑑(𝑒) = (0,0)
represents a data dependency in the same iteration, such as
the edges 𝐷 → 𝐴, 𝐴 → 𝐵 and 𝐴 → 𝐶 as shown in Fig. 1.a.
𝑒

69

3.1 Principles
The retiming technique consists in redistributing delays in

We use the notation 𝑣𝑖 → 𝑣𝑗 to indicate that 𝑒 is an edge
𝑝

from 𝑣𝑖 node to 𝑣𝑗 node, and 𝑣𝑖 ⇒ 𝑣𝑗 to mean that 𝑝 is a path
from 𝑣𝑖 node to 𝑣𝑗 node. The delay vector of a path 𝑝: 𝑣𝑖
𝑒𝑚

𝑒𝑚+1

𝑒𝑛

�� 𝑣𝑖+1 �⎯⎯� … → 𝑣𝑗 is 𝑑(𝑝) = ∑𝑘=𝑛
and the total
𝑘=𝑚 𝑑(𝑒𝑘 )
𝑘=𝑗
computation time of a path 𝑝 is 𝑡(𝑝) = ∑𝑘=𝑖 𝑡(𝑣𝑘 ). The period
during which all computation nodes in iteration are
executed, according to existing data dependencies and
without resource constraints, is called a cycle period. The
cycle period C(G) of an MDFG is the maximum computation
time among paths that have a zero delay. For example,
assuming that each node is executed in one time unit
𝑡(𝐴) = 𝑡(𝐵) = 𝑡(𝐶) = 𝑡(𝐷) = 1, the MDFG of Fig.1.a
has C(G) = 3. It can be measured through the paths 𝑝: 𝐷 →
𝐴 → 𝐵 or 𝑝: 𝐷 → 𝐴 → 𝐶, as shown in the iteration scheduling
illustrated in Fig.1.b. Each set of nodes belonging to the same
iteration are modeled by a different motif.
The execution pattern of a nested loop can be illustrated
by iteration space as shown in Fig.2.a. Each cell in the
iteration space is a copy of the MDFG. The marked cell,
labeled by (0,0), is the first iteration to be executed. This
…….
B

C

A

e2
(0,0)

B

C

(1,-1)
e4
e5
(1,1)

(a)

D

B

C

A
D
B

(0,0)

e3

D

T
im
e

A

(0,0)
e1

C

A
D

(b)

Fig.1. (a) MDFG of Wave Digital Filter; (b) Iteration scheduling of the
MDFG in Fig.1.a.

graph is transformed on an acyclic graph, called cell
dependency graph (CDG), allowing to show clearly the
execution sequence of a nested loop. The CDG of an MDFG

(a)

(b)

Fig.2. (a) Iteration space of the MDFG in Fig.1; (b) The cell
dependency graph.

the graph. This technique can be applied on a data flow
graph to minimize the cycle period in a polynomial time. The
delays are moved around in the graph in the following way:
a delay unit is drawn from each of the incoming edges of 𝑣,
and then added to each of the outgoing edges of 𝑣, or vice
versa [1]. In the case of MDFG, it consists in redistributing
the execution of nodes on the iterations. The retiming vector
𝑟(𝑢) of a node 𝑢 ∈ 𝐺 represents the offset between the
original iteration containing 𝑢, and the one after retiming.
Note that the retiming technique preserves data
dependencies of the original MDFG. Therefore, we have
𝑑𝑟 (𝑒) = 𝑑(𝑒) + 𝑟(𝑢) − 𝑟(𝑣) for every edge and 𝑑𝑟 (𝑙) = 𝑑(𝑙)
for every cycle 𝑙 ∈ 𝐺. After retiming, the execution of the
node u in the iteration i is moved to the iteration 𝑖 − 𝑟(𝑢).
We show in Fig.3.a the MDFG 𝐺𝑟 = (𝑉, 𝐸, 𝑑𝑟 , 𝑡) of the
wave digital filter after applying the retiming function
𝑟(𝐷) = (0,1). When a delay is pushed through node 𝐷 to its
outgoing edge as shown in Fig.3.a, the actual effect on the
Algorithm 2 of the new MDFG is that the 𝑖 th copy of 𝐷 is
shifted up and is executed with (𝑖 − (0,1)) th copy of nodes 𝐴,
𝐵, and 𝐶. The original zero-delay edge 𝐷 → 𝐴 in Fig.1.a now
has a delay (0,1) after retiming as shown in Fig.3.a. Node 𝐷
in the new loop body has not any data dependency with
other nodes executed in the same cycle. So, node 𝐷 can be
executed in parallel to node 𝐴, as shown in the iteration
scheduling of Fig.3.b. Thus, the cycle period is reduced
from three to two time units.
P

P

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

70

In fact, every retiming operation corresponds to a
software pipelining operation. When 𝑟(𝑢) delay units are
pushed through a node u, every copy of this node is moved
by 𝑟(𝑢) iterations. Hence, a new iteration consists in
redistributing the execution nodes into different iterations.
ALGORITHM 2
WAVE DIGITAL FILTER AFTER RETIMING BY THE FUNCTION
R(D)=(0,1)
0: For i from 0 to m do
1: D(i,0) = B(i-1 , 1) × C(i-1 , -1)
2: For j from 0 to n-1 do
3:
D(i,j+1) = B(i-1 , j+2) × C(i-1 , j)
4:
A(i,j) = D(i,j) × 5
5:
B(i,j) = A(i,j) + 1
6:
C(i,j) = A(i,j) + 2
7: End for
8: A(i,n) = D(i,n) × 5
9: B(i,n) = A(i,n) + 1
10: C(i,n) = A(i,n) + 2
11:End for

(a)

Fig.4. (a) The iteration space the retimed MDFG in Fig.3; (b) The cell
dependency graph.

Hence, the MDR technique aims to transform a realizable
MDFG G on MDFG 𝐺𝑟 in a way that 𝐺𝑟 is still realizable.
Using such concepts, the basic conditions for legal
multidimensional retiming are defined in the following

e2
(0,0)

C

(1,-1)
e4
e5
(1,1)

(0,1)

e3

(a)

D

C

(1,-3)
e4
e5
(1,-1)

D

B

C

A

D

B

C

A

D

B

C

A

D

A

D
D

(0,1)

e3

(a)

Prologue

(b)

Fig.5. (a) Fully parallelized graph of the MDFG in Fig.1; (b) Iteration
scheduling of the MDFG in Fig.5.a

lemma [2].

B

C

A

D

Lemma 1. Let 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡) be a realizable MDFG, r a
multidimensional retiming, and s a schedule vector for the
retimed graph 𝐺 𝑟 = (𝑉, 𝐸, 𝑑𝑟 , 𝑡), then

T
im
e

(0,0)
e1

e2
(0,1)

B

…….

…….
r(D)=(0,1)

A

A

(0,1)
e1

r(D)=(0,2)
r(A)=(0,1)

T
im
e

Some nodes are shifted out of the loop body to provide the
necessary data for the iterative process, which is called
prologue. Correspondingly, some nodes will be executed
after the loop body to complete the process, which is called
epilogue.
Using MD retiming function r, we can trace the pipelined
nodes and also measure the size of the prologue and
epilogue. For node v with retiming 𝑟(𝑣) = (𝑖, 𝑗), there are i
copies of node v appearing in the prologue of outer loop, and
j copies of node v in the prologue of the innermost loop. The

B

(b)

B

C

A

D

B

C

A

D

1.

2.

D

Prologue

(b)

Fig.3. (a) MDFG of algorithm 2; (b) Iteration scheduling of the MDFG in
Fig.3.a

number of copies of a node in the epilogue can also be
derived in a similar way. The iteration space of the retimed
MDFG shown in Fig.4.a with retiming 𝑟(𝐷) = (0,1) clearly
shows that one copy of node D is pushed out of the loop
body on j-dimension, and becomes prologue for the
innermost loop. The corresponding cell dependency graph is
shown in Fig.4.b.
It is known that an MDFG can always be fully
parallelized by applying successively the MD retiming
functions 𝑟(𝐷) = (0,2) and 𝑟(𝐴) = (0,1), which is illustrated
in Fig.5.a. We note that the retimed MDFG has non-zerodelay on each edge. It implies that the nodes belonging to the
same iteration in the original loop body are distributed into
three cycle periods. The MDFG is then scheduled with the
minimal cycle period equal to one time unit, as schematized
the iteration scheduling of Fig.5.b.
To achieve a realizable MDFG after retiming, the legality
condition,𝑠 × 𝑑(𝑒) ≥ 0, has to be satisfying, and there should
not exist any cycle in the cell dependency graph of the
MDFG.

3.
4.

for any path , we have 𝑑𝑟 (𝑝) = 𝑑(𝑝) + 𝑟(𝑢) − 𝑟(𝑣)
for any cycle 𝑙 ∈ 𝐺 we have 𝑑𝑟 (𝑙) = 𝑑(𝑙)
𝑒

for any edge 𝑢 → 𝑣, 𝑑𝑟 (𝑒) × 𝑠 ≥ 0

there is no cycle in the DG equivalent to the MDFG G.

The selection of a legal multidimensional Retiming
function is based on the edge delay of the MDFG. The
approach proposed in [2],[3] consists in defining a
scheduling subspace S for a realizable MDFG 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡).
It represents the space region where there exist schedule
vectors that realize 𝐺; i.e., if schedule 𝑠 ∈ 𝑆 then 𝑠 × 𝑑(𝑒) ≥ 0
for any 𝑒 ∈ 𝐸. In fact, the multidimensional retiming
technique means to decrease zero-delay edges. Thus, a
strictly positive scheduling subspace 𝑠 + is the set al all
vectors 𝑠 ∈ 𝑆 where 𝑠 × 𝑑(𝑒) > 0 for every 𝑑(𝑒) ≠ (0,0, … ,0).
The method of predicting a legal multidimensional retiming
is introduced in the next theorem.
Theorem 1. let 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡) be a realizable MDFG, 𝑠 + a
strictly positive scheduling sub-space of G, s a scheduling vector
in 𝑠 + , and 𝑢 ∈ 𝑉 a node with all incoming edge having nonzero
delay. A legal MD retiming r of u is any vector orthogonal to s.

3.2 Multidimensional Retiming techniques
We describe in this section the existent multidimensional
retiming techniques. They are characterized by achieving full
parallelism by providing the MDFG with no zero-delay edge
[2],[3],[7].
a) Incremental Multidimensional Retiming

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

This technique is based on selecting a set of nodes that
can be retimed by the same multidimensional retiming
function, as described in the following corollary.
Corollary 1. Given a realizable MDFG 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡), 𝑠 + a
strictly positive scheduling sub-space of G, s a scheduling vector
ALGORITHM 5
CHAINED MULTIDIMENSIONAL RETIMING

Input : a realizable MDFG G =(V,E,d,t),
Output : a realizable MDFG Gr =(V,E,dr,t) without d(e)=(0,0,
… ,0)
0: Begin
1: Find a legal MDR function r as describedin steps 2 and 3
in algorithm 3
2: Provide the multi -chain graph and the maximal length
of chain K, as indicated in algorithm 4
3: For each node v with label i do
4:
Apply the MDR function (k-i)× (r)
5: End for
6: End

71

nodes assigned by 𝐴𝑗 . Fig.7 illustrates the full parallelized
MDFG of the IIR filter after applying the Incremental
Multidimensional Retiming.
The steps of algorithm 3 are repeated four times, where
in each one a different MD retiming function is applied. The
fully parallelized MDFG is showed in Fig.7 where all edges
are non-zero delay.

a) Chained Multidimensional Retiming [2],[3]
This technique allows obtaining the full parallelism
solution by defining just one MDR function. It is based on the
following corollary.

in 𝑠 + , and an MD retiming function r orthogonal to s, if a set
𝑋𝐶𝑉has all incoming edges nonzero, then 𝑟(𝑋) is a legal MD
retiming.

Thus, this technique consists in defining a schedule
vector s as described in definition 1, and chooses an MDR
function orthogonal to s. This chosen function is applied to
each node respecting the previous corollary. Those steps are
ALGORITHM 3
INCREMENTAL MULTIDIMENSIONAL RETIMING
Input : a realizable MDFG G =(V,E,d,t)
Output : a realizable MDFG Gr=(V,E,dr ,t) without d(e) =
(0,0, … ,0)
0: Begin
1: While exist zero-delay edge in the graph Do
2: Find a scheduling vector s=(s.x,s.y), that s.x+s.y is
minimum
3: Choose a MDR function
4: Apply the selected MDR function to any nodes that
has all incoming edges with nonzero delays and at
least one outgoing edge with zero delay
5: End while
6: End

repeated incrementally, until all zero-delay edges are
transformed, as described in algorithm 3.
We apply the algorithm above to the 2DFG of Infinite

Fig.6. MDFG of IIR Filter.

Impulse Response filter (IIR) that is illustrated in Fig.6. It is
composed by multiplier nodes assigned by 𝑀𝑖 and adder

Fig.7. IIR Filter MDFG after Incremental MDR.

Corollary 2. [2] Given 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡), 𝑆 + a strict positive
scheduling subspace for G,s a scheduling vector 𝑆 + , a MD
retiming function orthogonal to s, a set 𝑋𝐶𝑉 which all incoming
edges nonzero, and an integer value 𝑘 > 1, then (𝑘 × 𝑟) (𝑋) is
a legal MD retiming.
Thus, it applies the MD retiming to successive nodes in a
path where each node has a retiming function multiple of the
selected retiming value smaller than its predecessor nodes.
ALGORITHM 4
MULTI-CHAIN GRAPH CONSTRUCTION
Input : a realizable MDFG G =(V,E,d,t)
Output : Labeled Multi -chain Graph
0: Begin
1: Remove all non-zero delay edges from the MDFG
2: For each chainCH do
3: Compute the length L of CH
4: For each node starting from the last to the first do
5:
Labeled the node by L
6:
L=L-1
7: End For
8: End For
9: End

This technique starts by transforming the MDFG on
Multi-chain Graph as described in Algorithm 4. Each chain
represents a node succession where all interconnected edges
between them are zero-delay. Each node is labeled by a level
whose the value is greater than its predecessor node and
smaller than its successor ones.
In the case of MDFG of IIR filter, the red integers above each
node of Fig.8 represent the level values that are labeled after
executing algorithm 4. Therefore, the multi-chain maximum
length of 𝐺 is 4.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

So, The technique proceeds to retime all the labeled
nodes by a MD retiming function (𝑘 − 𝑖) × (𝑟), as described
in algorithm 5.
We present in Fig.8 the full parallelized graph of the IIR
filter after applying the chained multidimensional retiming.
The algorithm starts by finding the MDR function which is
equal to (1, −1). We note that all zero delay edges in the
original MDFG are assigned by a delay vector equal to the
MDR function.
Until now, no research works have been interested in
comparing results provided by the techniques described
above. The random choice of the scheduling vector does not
allow defining the technique providing the optimal solution.
However, based on their approaches, Chained MDR is
generally more performing than the Incremental MDR. The
first one consists in defining just one scheduling vector,
which is executed in 𝑂(|𝐸|); while the second requires
defining scheduling vector for each iteration of algorithm 4,
which is executed in 𝑂(|𝑉|).

b) SPINE (Software PIpelining of NEsted loops)
Multidimensional Retiming
This technique tries to provide a more optimal MDFG in
terms of execution time and code size than those described
above. It proceeds to remove all delays such as (0, 𝑘) by
merging them in a delay such as (𝑖, 𝑗). This modification is
applicable only if the MDFG contains at least one edge with a

72

loop. Since this limit is directly associated to the size of the
iteration space, it is called spatial constraint and it is formally
defined as follows.
ALGORITHM 6
SPINE-FULL ALGORITHM
Input : a realizable MDFG G =(V,E,d,t)
Output : a realizable MDFG
Gr =(V,E,dr,t) fully
parallelized with minimum code size
1: Begin
2: If s=(1,0) is legal then
3:
Apply s=(1,0)
4: Else If s=(0,1) is legal and d(e)×(0,1)>=0 then
5:
Apply s=(0,1)
6: Else If s=(1,1) is legal and d(e)×(1,1)>=0 then
7:
Apply s=(1,1)
8: Else
9: Choose a legal scheduling vector s such as d(e)×s>=0,
for any edge and | sx| +| sy| is minimal
10: End

Definition 1. Let a MDFG G contains k-level nested loop N,
controlled by the set of indices 𝐼 = {𝑖0 , 𝑖1 , … , 𝑖𝑘 }, whose values
vary, in unitary increments, in the range 𝐿 = {𝑙0 , 𝑙1 , … , 𝑙𝑘 } to
𝑈 = {𝑢0 , 𝑢1 , … , 𝑢𝑘 } where L is the set of lower boundaries for
the indices and U is the set of maximum values, such as
𝑙𝑗 ≤ 𝑖𝑗 ≤ 𝑢𝑗 , then the spatial constraint Sc of the loop is defined
as:
𝑆𝑐 = [(𝑢0 − 𝑙0 + 1), (𝑢1 − 𝑙1 + 1), … , (𝑢𝑘 − 𝑙𝑘 + 1)]

This definition allows establishing the relation between
the maximum retiming operation and the spatial constraint
according to the following lemma.
Lemma 2. Given a k-level loop N with spatial constraint 𝑆𝑐 =
[𝑠0 , 𝑠1 , … , 𝑠𝑘 ]. The multi-dimensional retiming technique will be
able to achieve full parallelism of the loop body instructions if
the maximum retiming vector r applied to any node u, 𝑟(𝑢) =
(𝑟0 , 𝑟1 , … , 𝑟𝑘 ) satisfies the following condition:
𝑟𝑗 < 𝑠𝑗 𝑠𝑢𝑐ℎ 𝑎𝑠 0 ≤ 𝑗 ≤ 𝑘

Fig.8. IIR Filter MDFG after Chained MDR.

delay equal to (𝑖, 𝑗) such as 𝑖 > 0.
It consists in finding a scheduling vector 𝑠 and a retiming
function 𝑟 orthogonal to 𝑠, as described in algorithm 6, to
provide a minimal overhead.

3.3 Multidimensional Retiming Constraints [5]
We describe in this paragraph the algorithmic constraints
which must be taken into account to achieve full parallelism.
These constraints come from the ratio between loop bounds
and a number of MDR functions to apply.
For example, consider the multi-dimensional data flow
graph in Fig.1; it is easy to verify that if 𝑑(𝑒4) = (0, 𝑘) where
𝑘 < 3, retiming 𝐷 and 𝐴 by some vector (0, 𝑝) will not
satisfy the goal of re-distributing the delays among all edges
in the graph. The same will happen if 𝑑(𝑒5) = (𝑚, 0)
where 𝑚 < 3 for any retiming vectors of the form (𝑞, 0).
Thus, if the loop has only one occurrence, i.e., the loop
boundaries are both 1, then no parallelism can be obtained.
This last constraint is equally applicable to a software or
hardware implementation of the retimed loop.
This study begins by evaluating the constraints imposed
by the limitation on the number of iterations comprising the

3.4 Limitations of existing techniques
We have shown that nested loops can always be fully
parallelized using MD retiming. The presented techniques of
MD retiming are a polynomial time algorithm that fully
parallelizes a given MDFG 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡) by selecting a legal
schedule vector s with 𝑠 × 𝑑(𝑒) > 0, 𝑒 ∈ 𝐸, and a retiming
vector 𝑟 where 𝑟 is orthogonal to 𝑠. Each MD retiming
techniques presented above shows that the selected 𝑠 is a
legal schedule vector for the retimed graph where 𝑑𝑟 (𝑒) ≠
𝑑(𝑒) ± 𝑘. 𝑟.
However, Multidimensional retiming techniques imply a
large overhead of the generated code. It is caused by several
aspects of loop transformation. First, the code size is
increased because of the large code sections of the prologue
and epilogue produced in all the loop dimensions. Second,
the computation of the new loop bounds and loop indexes
need to be recomputed [10].
Moreover, the execution of the prologue and epilogue
section is not fully parallel, which requires a considerable
period cycle number compared to that required by the loop
body. Those disadvantages are aggravated in terms of the
retiming vector value, and the number of the
multidimensional retiming function.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

Each Multidimensional Retiming techniques have a
specific approach to choose the retiming function in order to
decrease the overhead size. Chained and incremental
Multidimensional retiming techniques proceed to chose a
scheduling vector 𝑠 = (𝑠. 𝑥, 𝑠. 𝑦), where 𝑠. 𝑥 + 𝑠. 𝑦 is
minimum. The SPINE technique tries to modify the MDFG
with the intention of applying an MDR function that skews
the minimum column-wise or/and row-wise. Despite
providing an optimal solution, it is reliable only in the
particular case of MDFG. In opposite cases, it applies the
same approach than other techniques.
However, all existent techniques consist in retiming each
node of the MDFG having an out-coming edge with zerodelay: if a path p as 𝑑(𝑝) = (0,0, … ,0) is composed by n
nodes, any technique applies (𝑛 − 1) MDR function to
achieve full parallelism. But, overhead consequences are
sudden after applying each MDR function: the more the
number of MDR function increases, the more the
consequences are dramatic.
As a result, the provided solution becomes very
complicated and not sufficient to be implemented in
embedded systems. Therefore, the existing MD retiming
techniques, although achieving full parallelism, are not
suitable for software nested loops.

4 THEORY OF OPTIMAL MULTIDIMENSIONAL RETIMING
In this section, we present the theoretical foundation of our
proposal MDR technique “Optimal Multidimensional
Retiming”. It aims at minimizing MDR functions by
exploring execution times and data dependency of nodes,
while achieving full parallelism.

3.1 Principle
Multidimensional retiming techniques allow scheduling the
MDFG with a minimal cycle period. For any path p 𝑝: 𝑣𝑖
𝑒𝑚+1

body is executed in 5 cycles. We illustrate in Fig.9 the static
schedule of such an iteration after achieving full parallelism
by the chained multidimensional retiming which is retimed
by the function 𝑟 = (−1,1). The nodes belonging to the same
iteration are modeled by gray circles.
Each gray node has not any data dependency with any
other node executed in the same cycle period. However,
these scheduling shows that provided data by some nodes
are not consumed immediately. For example, nodes 𝐴5 and
𝐴7 are executed in just one time unit and their provided
values are consumed two times units later. We conclude that
cycle periods are not exploited optimally: (more than 66% of
the cycle periods (𝑖 − 2, 𝑗 + 2), (𝑖 − 3, 𝑗 + 3) and (𝑖 − 4, 𝑗 + 4)
are not used). However, they allow executing more than one
node, due to the difference between execution time.
Let us try to execute nodes 𝐴5 and 𝐴7 in the same cycle
period as nodes 𝐴1, 𝐴2 and 𝐴6, as schematized in Fig.10. The
correspond MDFG with new delay values is illustrated in
Fig.11. This transformation results in a legal MDFG that
respects all conditions of lemma 1. Furthermore, it still keeps
a fully parallelized execution, while preserving data
dependency for the whole application. Compared to Fig.8,
this transformation can be considered as decreasing the
number of MDR functions by depriving nodes 𝐴5 and 𝐴7 to
be retimed.
In fact, minimizing the number of MDR functions
implies decreasing the overhead of the generated code. It
consists in reducing the correspondent prologue, epilogue

M5

M6

M7

M8

M1

M2

M3

A3

M5

M6

M7

M8

M1

M2

M3

Theorem 2. Let 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡) a MDFG, the minimal value of
cycle 𝑐𝑚𝑖𝑛 for the G graph is:
𝑐𝑚𝑖𝑛 = 𝑚𝑎𝑥{𝑡(𝑣𝑖 ), 𝑣𝑖 ∈ 𝑉}

We choose to model the MDFG of IIR filter with different
execution time of nodes such as of 𝑡(𝑀𝑖 ) = 3 and 𝑡(𝐴𝑗 ) = 1.
The minimal cycle 𝑐𝑚𝑖𝑛 of this graph is equal to the execution
time of the multiplication node.
Applying any MDR techniques to the IIR filter results in
the fact that each iteration belonging to the original loop

A4

A1

A2

A6

A5

A7

A8

Cycle
(i-3 , j+3)

M4

𝑒𝑛

�� 𝑣𝑖+1 �⎯⎯� … → 𝑣𝑗 of MDFG, they proceed to execute each
node 𝑣𝑘 where 𝑖 ≤ 𝑘 ≤ 𝑗 in a period cycle separately. These
approaches can be generalized into general-time cases [2] [4].
In fact, the computation nodes belonging to a data flow
graph have not generally the same execution times. These
depend on the kind of operation to be done; for example, a
multiplication node needs usually more clock period than an
adder node.
In this case, the minimal cycle period should be fixed
differently. A cycle period represents a time interval leading
to execute computation nodes. The minimal value of a period
cycle can be defined as the smaller time interval that allows
executing any node belonging to the MDFG. Thus, the
minimal cycle period should be equal to the maximal
execution time of node, as described in theorem 2 [1].

Cycle
(i-4 , j+4)

M4

A3

A4

A1

A2

A6

A5

A7

A8

T
im
e

𝑒𝑚

73

M5

M6

M7

M8

M1

M2

M3

Cycle
(i-2 , j+2)

M4
A3

M5

M6

M7

M8

M1

M2

M3

M6

M7

M8

M1

M2

M3

A1

A2

A6

A5

A7

A8

Cycle
(i-1 , j+1)

M4
A3

M5

A4

A4

A1

A2

A6

A5

A7

A8

Cycle
(i , j)

M4
A3

A4

A1

A2

A6

A5

A7

A8

Fig.9. Iteration scheduling after chained MDR.

and the loop bound and index instructions. Moreover, it
results in decreasing the number of cycle periods required to
execute any iteration from 5 to 4, while respecting a fully
parallelized execution. This minimization of cycle periods
implies a similar minimization on the execution time of the
whole application. Thus, this minimization of MDR functions
leads to improve the performance of the provided full
parallel solution.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

Our technique proceeds to share the MDFG on zerodelay paths. It leads to maximize the node number in such a
A8
M5

M6

M7

M8

M1

M2

M3

A3

A4

A2

A1

Cycle
(i-2 , j+2)

A7

A5

M4

A6

A8
M5

M6

M7

M8

M1

M2

M3

Cycle
(i-1 , j+1)

A7

A5

M4

T
im
e

Such modification can be defined as applying the MDR
to path p that can be composed of several nodes where 𝑡(𝑝)
is smaller than 𝑐𝑚𝑖𝑛 . The more the paths contain nodes, the
more the MDR function number decreases. Thus, we propose
a new MDR approach which consists in applying MDR
function to a path of nodes, which can be executed in the
same period cycle, instead of applying the MDR to each node
separately. Our approach is based on selecting the path with
the maximal nodes to achieve full parallelism with a minimal
number of MDR functions. We start by computing the

74

A3

A4

A2

A1

A6

A8

M5

M6

M7

M8

M1

M2

M3

A5

M4
A3

M5

M6

M7

M8

M1

M2

M3

A4

A5

M4
A4

A6

A2

A1

A6

M5

M6

M7

M8

M1

M2

M3

M4

A5

A8

A3

A4

A2

A1

Cycle
(i-1 , j+1)

A7
A6

M6

M7

M8

M1

M2

M3

M4

A5

A8

A3

A4

A1

Cycle
(i , j)

A7
A2

A6

A8

Fig.10. Iteration scheduling after collecting nodes in cycle (i-2, j+2).

Fig.11. MDFG of Fig.10.

minimal period cycle 𝑐𝑚𝑖𝑛 , extracting the paths with maximal
nodes from the MDFG while keeping their execution in 𝑐𝑚𝑖𝑛 ,
and applying the MDR function to the extracted paths.

3.2 Basics concepts
Our technique consists in retiming a path of nodes that can
be executed in the same cycle period. It means that those
nodes are executed in the same iteration of the original loop
body; i.e., all edges belonging to the path have zero-delay.
We call such a kind of path “zero-delay path”, which is
indicated in theorem 3.
𝑒𝑚+1

M1

M2

M3

A4

A1

Cycle
(i , j)

A7

A5

M4

A2

A6

Definition 2. Let 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡), 𝑐𝑚𝑖𝑛 the minimal period cycle
of G. The optimal multidimensional retiming consists in
retiming a set of path p follows :
2.
3.

𝑒𝑛

Theorem 3. Let 𝑝: 𝑣𝑖 �� 𝑣𝑖+1 �⎯⎯� … → 𝑣𝑗 . p is zero-delay 𝑑(𝑝) =
(0, … ,0),if and only if :
∀ 𝑒𝑙 : 𝑣𝑘 → 𝑣𝑘+1 , 𝑑(𝑒𝑙 ) = (0, … ,0); 𝑠𝑢𝑐ℎ 𝑎𝑠 𝑒𝑙 ∈ 𝐸, 𝑣𝑘 ∈ 𝑉, 𝑘
∈ [𝑖, (𝑗 − 1)], 𝑙 ∈ [𝑚, 𝑛]

𝑚𝑎𝑥 (𝑐𝑎𝑟𝑑(𝑝))

𝑑(𝑝) = (0, … ,0)
𝑡(𝑝) ≤ 𝑐𝑚𝑖𝑛
𝑒𝑚

𝑒𝑚+1

𝑒𝑛

Where 𝑝: 𝑣𝑖 �� 𝑣𝑖+1 �⎯⎯� … → 𝑣𝑗 as 𝑣𝑘 ∈ 𝑉 ∀ 𝑘 ∈ [𝑖, 𝑗]
and card(p) is the number of nodes belonging to p such as
𝑐𝑎𝑟𝑑(𝑝) = 𝑗 − 𝑖 + 1.
To preserve data dependency of MDFG, each p path
should not contain any cycle in a way that no cycle between
vp and vm where ∀ 𝑝, 𝑚 ∈ [𝑖, 𝑗] for each selected path
𝑒𝑚

𝑒𝑚

M8

path, while being executed in the minimal cycle period. We
define our idea of optimal multidimensional retiming as
described in definition 2.

1.
M5

M7

Fig.15. Iteration scheduling of MDFG shown in Fig.14.
Cycle
(i-2 , j+2)

A7

M6

A3

A8

T
im
e

A3

Cycle
(i-3 , j+3)

A7
A2

A1

M5

𝑒𝑚+1

𝑒𝑛

Furthermore,
multidimensional
𝑝: 𝑣𝑖 �� 𝑣𝑖+1 �⎯⎯� … → 𝑣𝑗 .
retiming consists in executing several paths in the same cycle
period. Thus, such a path should not have any cycle between
nodes that they belong to.
Our technique is based on retiming a zero-delay path. It
means that all edges belonging to this path preserve the same
delay (zero-delay). Only the delay of in-coming and outcoming edges of the whole path are changed. Thus, it means
retiming the last node that it belongs to.
Referring to [2] and [3], the multidimensional retiming
function is defined from edges having a non-zero delay of
the MDFG. However, there is not constraint that requires
applying the MDR function to nodes with non-zero incoming edges. In the case of zero delay paths, it can be
applied to any node belonging to them, as defined in
theorem 4.
Theorem
4.
Let 𝐺 = (𝑉, 𝐸, 𝑑, 𝑡), and a zero delay path 𝑝: 𝑣𝑖
𝑒(0,…,0)
𝑒(0,..,0)
�⎯⎯⎯� … �⎯⎯� 𝑣𝑗 . If r is a legal MDR function of 𝑣𝑖 ,then r is a
legal MDR function of vk, where 𝑣𝑘 ∈ 𝑃 and 𝑘 ∈ [(𝑖 + 1) , 𝑗].

Proof. a strict positive scheduling sub-space S + contains all
scheduling vectors s where 𝑑(𝑒) × 𝑠 > 0 for each 𝑑(𝑒) ≠
(0,0, … ,0), such as described in definition 2. This implies
that 𝑣𝑖 and vk have the same sub-space 𝑆 + . But, a legal MDR
𝑟 of 𝑣𝑖 is any orthogonal vector to 𝑠, where 𝑠 ∈ 𝑆 +, as
indicated in theorem 1. This means that a legal MDR 𝑟 of 𝑣𝑖
is a legal MDR of 𝑣𝑘 .
So, we provide an MDR function as indicated in theorem
2. This function is applied to the last node of the zero delay
path to retime.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

We conclude in section 3 that it is more sufficient to
select an MDR function to apply it for all nodes to be retimed
to achieve full parallelism, as described in corollary 1. Thus,
we proceed by selecting every last node of a zero-delay path
that will be retimed. Afterwards, we find a legal MDR
function to be applied successively to the selected nodes
while respecting data dependency of the MDFG.
ALGORITHM 8
OPTIMAL MULTIDIMENSIONAL RETIMING
Input : a realizable MDFG G =(V,E,d,t)
Output : a realizable MDFG Gr =(V,E,dr,t)
0: Begin
1: Find a legal MDR function r
2: Provide the LMDFG and the maximal length M , as
described in algorithm 7
3: For i from M down to 1 do
4:
Select nodesv k that are labeled by i
5:
For each v k do
6:
Apply the MDR Retiming (i × r)
7:
End for
8: End for
9: End

3.3 Path Extraction
This step is based on exploring nodes belonging to the
MDFG by testing their data dependency and execution time,
to share them onto paths. We proceed by sweeping
ALGORITHM 7
LABELED MULTIDIMENSIONAL DATA FLOW GRAPH
CONSTRUCTION
Input : a realizable MDFG G =(V,E,d,t)
Output : Labeled Multidimensional Data Flow Graph
(LMDFG), maximal length M
0: Begin
1: Compute cmin
2: Extract all nonzero delay edges from G
3: i =1
4: Add the elements (v j, t(v j)) to R, such as vj is a node
without outcoming edge
5: While R is not empty do
6: For each v j of R do
7:
Collect all predecessor ofv j
8:
For each predecessorv p of v j do
9:
If t(v p)+t(v j) <= cmin and respect data dependency
then
10:
Add (v p, t(v p)+t(v j)) to R
11:
Else
12:
Add (v p, t(v p)) to N E
13:
End If
14:
End for
15: End for
16: Label all nodes of N E by i
17: I= i+1
18: R=N E
19: End while
20: M = i
21: End

75

incrementally the MDFG from the opposite direction of edge.
For each node, we verify that it respects the previous
conditions, to execute it in the suitable cycle.
Our process consists on extracting the last node of each
zero delay path that will be retimed, and labeled by an
increasing order starting from 1. The result is illustrated in a
“Labeled Multidimensional Data Flow Graph” (LMDFG)
taken from the MDFG, as described in algorithm 7.
We proceed by exploring the MDFG in the opposite
direction of data dependency. We start by extracting the nonzero delay edges from the MDFG and collecting all nodes 𝑣𝑘
without outcoming edge in 𝑅 list. For each node belonging to
𝑅, we define all the predecessor nodes 𝑣𝑝 to verify that can be
executed in the same cycle time as nodes in 𝑅. For each 𝑣𝑝 , if
𝑡�𝑣𝑝 � + 𝑡(𝑣𝑘 ) < 𝑐𝑚𝑖𝑛 and if 𝑣𝑝 respects data dependency
conditions described above, we consider 𝑣𝑝 as a node
belonging to the path and we add it to the 𝑅 list. Else, 𝑣𝑘 is
the last node of the previous path that should be retimed,
and then we add then the node 𝑣𝑘 to 𝑁𝐸 list to label it. This
test is repeated for all predecessor nodes of 𝑅 list element.
The next step consists in labeling all the nodes of 𝑁𝐸 list by
1(first value of 𝑖), before replacing 𝑅 elements by 𝑁𝐸
elements. These steps are repeated until testing all nodes of
MDFG.
We show in Fig.12 the LMDFG of IIR filter with 𝑡(𝑀𝑖 ) =
3 and 𝑡(𝐴𝑗 ) = 1. The first iteration of algorithm 7 consists in
labeling the nodes 𝑀1, 𝑀2, 𝑀3, 𝑀4, 𝐴3 and 𝐴4 by 1. The last
iteration assigns nodes 𝑀5, 𝑀6, 𝑀7 and 𝑀8 by 2. Therefore,
the multi-chain maximum length is 2.

3.4 Optimal Multidimensional Algorithm
Our technique starts by finding a legal MDR r of MDFG, as
indicated in theorem 2. After that, it provides the LMDFG
and the maximal label by running algorithm 7. Then, it
selects nodes with maximal label, and applies the MDR
function (𝑖 × 𝑟). These steps are repeated by decreasing the
label of the selected node until achieving retiming all the
labeled nodes, as described in algorithm 8.

Fig.12. Labeled Multidimensional Data Flow Graph (LMDFG) of IIR
filter.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

As an example, we apply this algorithm to the MDFG of
IIR filter. It starts by defining an MDR function 𝑟 = (1, −1),
and providing the LMDFG shown in Fig.12. The first
iteration of the algorithm retimes the nodes that are labeled
by 2, by applying the retiming function 𝑟 = (2, −2) as
illustrated in Fig.13. The second iteration retimes the other
labeled nodes by 𝑟 = (1, −1), to provide the fully
parallelized MDFG of IIR filter as shown in Fig.14. The nodes
interconnected by a zero-delay edge are executed in the same
cycle period. It means that nodes belonging to the same
iteration in the original MDFG are executed in three cycle
periods, as illustrated in the scheduling iteration of the fully
parallelized MDFG in Fig.15.

76

TABLE 4
EVOLUTION OF THE CODE SIZE IN TERMS OF CYCLE PERIOD
MDFG
G1
G2
G3
G4
G5
G6

Optimal MDR
144
144
64
144
60
60

Code size
Chained MDR
400
400
400
400
72
72

Improve
48%
48%
84%
48%
16.66%
16.66%

5 EXPERIMENTAL RESULTS
In this section, we validate our MDR technique by comparing
its provided MDFGs to those generated by the chained MDR.
Four parameters are compared in our experimentation: the
cycle period, the number of MDR functions, the execution
time and the code size. We choose as an application the IIR
filter graph and the wave digital filter after applying the
Fettweis transformation [2], as illustrated in Fig.16. These
two graphs are both composed of addition and
multiplication nodes.
Our experiments consists in modeling each MDFG
frequently in different cases of the execution time 𝑡(𝑣𝑖 ) where
𝑣𝑖 𝜖 𝑉, whose values are indicated in Table.1. We present in
the last column the minimum cycle period whose values are
defined as theorem 2.

Fig.14. Full parallelized IIR filter after applying optimal MDR.

required to achieve full parallelism, for each MDFG, using
both techniques.
After providing the fully parallelized MDFGs, we
generate their respective algorithms, to extract their time and
code size parameters. We present in Table.3 the values of the
period cycle number and the execution time of each MDFG

For each MDFG in Table.1, we apply both chained MDR
and optimal MDR techniques. Each one is characterized by a
number of MDR functions applied to achieve full parallelism.
The chained MDR generates the same fully parallelized
MDFG with the same MDR function number, whatever the

Fig.16. MDFG of wave digital filter

illustrated in Table.1 in terms of MDR techniques. The
column “improve” presents the improvement of the
execution time of result generated by our approach
compared to those generated by the chained MDR, which
accounts for an average improvement of 19.31%.
The code size of each MDFG provided in term of both of
TABLE 1
CYCLE PERIOD IN TERMS OF NODE EXECUTION TIMES
Application
IIR Filter
Fig.13. Retiming labeled nodes by 2.

set of node execution time is.
Contrariwise, optimal MDR provides a specific MDFG
for each MDFG of Table.1, with different MDR function
numbers and retimed nodes. To guaranty a reliable
comparison, we use the same MDR function for both
techniques, which we apply the functions 𝑟 1 = (1, −1) and
𝑟2 = (0,1) respectively to the IIR filter and wave digital
filter. Table.2 illustrates the numbers of MDR functions

WD filter

MDFG
G1
G2
G3
G4
G5
G6

t(A i )
1
1
1
2
1
1

t(M j)
2
3
4
5
2
3

Cmin
2
3
4
5
2
3

the two MDR techniques are shown in Table.4. Each value
presents the instructions number of the loop body and the
overhead caused by an MDR transformation. The code size
values mention that our technique proposes an average
improvement equal to 43.53% of the code size.

JOURNAL OF COMPUTING, VOLUME 3, ISSUE 7, JULY 2011, ISSN 2151-9617
HTTPS://SITES.GOOGLE.COM/SITE/JOURNALOFCOMPUTING/
WWW.JOURNALOFCOMPUTING.ORG

6 CONCLUSION
In this paper, we have proposed a new Multidimensional
Retiming technique to achieve full parallelism of MDFGs. It
allows providing an optimized MDFG compared to those
provided by the existent techniques. It allows minimizing
Multidimensional functions by exploring the execution times
and data dependencies between the nodes.
In the section above, we have applied our technique and
the chained MDR on different cases of MDFG. The results
have shown that our technique generates a more efficient
solution MDFG, than those generated by the chained MDR,
in terms of cycle number, execution time and code size. We
have concluded that our technique provides a more efficient
solution, which allows respecting timing and code
constraints while implementing the nested loop in embedded
TABLE 2
EVOLUTION OF MDR FUNCTION NUMBER IN TERMS OF CYCLE
PERIOD
MDFG
G1
G2
G3
G4
G5
G6

MDR function number
Chained MDR
Optimal MDR
2
4
2
4
1
4
2
4
1
2
1
2

systems.
As an optimization technique, we try in our future works
to study using our MDR technique with other optimization
approaches such as unrolling, loop fusion ... It consists in
defining the applying order and the evolution of the
performance parameter in terms of both approaches.
However, MDR techniques are based on scheduling the
MDFG with a minimum cycle period. This period cycle value
does not mean providing an MDFG with minimum
execution time. We will be interested to extending our MDR
technique to provide the adequate period cycle and a
TABLE 3
EVOLUTION OF CYCLE NUMBER AND EXECUTION TIME IN TERMS
OF CYCLE PERIOD
Execution time
Cycle number
MDFG Optimal Chained Optimal Chained
MDR
MDR
MDR
MDR
G1
258
316
516
632
G2
258
316
774
948
G3
229
316
916
1264
G4
258
316
1290
1580
G5
500
600
1000
1200
G6
500
600
1500
1800

Improve
18.35%
18.35%
27.53%
18.35%
16.66%
16.66%

scheduling approach which allows providing MDFG with
minimum execution time.
Also, in the case of real-time embedded system, the
design consists in respecting the code size constraint, which
should not be exceeded. This principle implies reducing
execution time while achieving a limit value of the code size.
Thus, based on the opposite evolution of the timing
parameters and the code size in terms of MDR functions, we

77

will be interested on proposing an optimization approach
using the MDR technique: it requires finding the set of MDR
functions that provide a retimed MDFG with a best ratio
between the mentioned parameters.

REFERENCES
[1] E. Leiserson & B. Saxe, “retiming synchronous circuitry”,
algorithmica, Springer New York, volume 6, numbers 1-6, juin 1991
[2] N.L. Passos, E.H.M. Sha, “achieving full parallelism using multidimensional retiming”, IEEE Transactions on Parallel and Distributed
Systems , Volume 7 , Issue 11 (November 1996)
[3] N.L. Passos, E.H.M. Sha, ”Full Parallelism In Uniform Nested Loops
Using Multi-Dimensional Retiming”, International Conference on
Parallel Processing, 1994.
[4] Q. Zhuge, C. Xue, M. Qiu, J. Hu and E. H.-M. Sha, "Timing
Optimization via Nest-Loop Pipelining Considering Code Size", Journal
of Microprocessors and Microsystems, Volume 32, Issue 7, October 2008.
[5] by N. L. Passos , D. C. Defoe, R. J. Bailey, R. H. Halverson, and R. P.
Simpson, “Theoretical Constraints on Multi-Dimensional Retiming
Design Techniques", Proceedings of the AeroSense-Aerospace/Defense
Sensing, Simulation and Controls, Orlando, FL, April, 2001.
[6] Qingfeng Zhuge, Chun Jason Xue, Meikang Qiu, Jingtong Hu, Edwin
H.-M. Sha, ”timing optimization via nested loop pipelinig considering
code size”, journal of microprocessors and Microsystems 32, 351-363,
2008.
[7] Qingfeng Zhuge, Zili Shao, Edwin H.-M. Sha, “timing optimization of
nested loops considering code size for DSP applications”, Proceeding of
the 2004 international conference on parallel processing, 2004.
[8]Q. Zhuge, E.H.-M. Sha, C. Chantrapornchai, CRED: code size
reduction technique and implementation for software-pipelined
applications, in Proceedings of the IEEE Workshop of Embedded System
Codesign (ESCODES), September, 2002, pp. 50–56.
[9] T. C. Denk and K. K. Parhi, "Two-Dimensional Retiming," in the IEEE
Transactions on VLSI, Vol. 7, No. 2, June, 1999, pp. 198-211.
[10] N. L. Passos and E. H.-M. Sha, "Scheduling of Uniform MultiDimensional Systems under Resource Constraints," in the IEEE
Transactions on VLSI Systems, December, 1998, Volume 6, Number 4,
pages 719-730.
Yaroub Elloumi is a PHD student since September 2009, registered in
both Paris-Est university (France) and Sfax university (Tunisia). He is a
member of Institut Gaspard-Monge, unité mixte de recherche CNRSUMLPE-ESIEE, UMR 8049. His research interests are High-level design
of real-time system, optimization techniques, and H igh-level parameter
estimation.
Mohamed Akil received his PhD degree from the Montpellier university
(France) in 1981 and hi s doctorat d'état from the Pierre et Marie curie
University (Paris, France) in 1985. He currently teaches and does
research with the position of Professor at computer science department,
ESIEE, Paris. He is a member of Institut Gaspard-Monge, unité mixte de
recherche CNRS-UMLPE-ESIEE, UMR 8049. His research interests are
Architecture for image processing, Image compression, Reconfigurable
architecture and FPGA, High-level Design Methodology for multi-FPGA,
mixed architecture (DSP/FPGA), System on C hip (SoC) and parallel
programming of 2D/3D topological operators. Dr. Akil has more than 80
research papers in the above areas.
Mohamed Hedi Bedoui received his PhD degree from Lille University in
1993. He currently teaches with the position of Professor of biophysics in
the Faculty of Medicine of Monastir (FMM), Tunisia. He is a member of
Medical Technology and i mage processing team (TIM), UR 08-27. His
research interests are real-time and embedded systems, image & signal
processing and har dware/software design in medical field, electronic
applications in biomedical instrumentation. He is the president of the
Tunisian Association of Promotion of Applied Research.

