Parallelization of Loops with Variable Distance Data
Dependences
Archana Kale

∗

Amitkumar Patil

†

arXiv:1311.2927v1 [] 12 Nov 2013

Supratim Biswas ‡
Department of Computer Science and Engineering
Indian Institute of Technology, Bombay

Abstract

1

The extent of parallelization of a loop is largely
determined by the dependences between its
statements. While dependence free loops are
fully parallelizable, those with loop carried dependences are not. Dependence distance is a
measure of absolute difference between a pair
of dependent iterations. Loops with constant
distance data dependence(CD3 ), because of
uniform distance between the dependent iterations, lead to easy partitioning of the iteration space and hence they have been successfully dealt with.
Parallelization of loops with variable distance
data dependences(V D3 ) is a considerably difficult problem. It is our belief that partitioning
the iteration space in such loops cannot be done
without examining solutions of the corresponding Linear Diophantine Equations(LDEs). Focus of this work is to study V D3 and examine
the relation between dependent iterations. Our
analysis based on parametric solution leads to
a mathematical formulation capturing dependence between iterations. Our approach shows
the existence of reasonable exploitable parallelism in V D3 loops with multiple LDEs.
Category D.3.4 Code Generation,
Compilers, Optimization
General Terms Dependence Distance,
Iteration Space, Partition, Parametric
Solutions, Linear Diophantine Equation,
Parallelism, Algorithms, Schedule

Loops with loop carried CD3 s having cycle free
Data Dependence Graph(DDG) have been successfully dealt with in the literature[2], however few researchers have considered loops having cycles in DDG[4]. Fewer efforts have
considered loops with variable distance data
dependence(V D3 ) and DDGs with or without
cycles[1]. Unlike the case of constant distance,
the solutions of LDEs for V D3 do not seem to
have a regular structure among dependent iterations. This is probably the reason for not
enough research reported in this area.
Our approach builds on a two variable LDE
for which parametric solutions are well known
[3]. We have analyzed the parametric solutions
and have developed a mathematical formulation that captures the structure among dependent iterations. The structure leads to partitioning of the iteration space where each component of the partition represents iterations
which have to be executed sequentially and distinct components are parallelizable. Further,
bounds on the number and size of components
have been obtained. Examining the structure
of a component, we show that all iterations of
the component can be generated from a single
iteration, called its seed. The representation of
the partition is consequently reduced to a set
of seeds. This set is used as a basis to generate the components dynamically in a demand
driven manner which can lead to schedules.
We have extended this approach to partition
the iteration space for multiple LDEs by combining the components of partitions of the indi-

∗

archanak@cse.iitb.ac.in
amitkumar@cse..iitb.ac.in
‡
sb@cse.iitb.ac.in
†

1

Introduction

vidual LDEs. The correctness of the non-trivial
composition of partitions to form the resultant
partition is proved. We have presented algorithms for all important formulations of our
work. The applicability of our approach rests
on its ability to extract exploitable parallelism
from V D3 loops with multiple LDEs. Experimental evaluation of effectiveness of our approach requires existence of V D3 loops with
large number of LDEs. Since we could not
find such loops in the benchmark programs, we
chose to create multiple LDEs with random coefficients for our experimentation. We present
an algorithm to generate iteration schedule.
Results show that loops with V D3 offer reasonable parallelism which reduces as the number of LDEs increase. To increase the parallelism in case of large number of LDEs we have
formed an alternate partition using a heuristic.
This heuristic shows non trivial improvement
in parallelism.

-8

-5

-4

-1

0

3

-7

-3

1

2

7

-6

-2

4

5

6

Figure 1: Partition of [-8,7]

Connected Component(CC), CC = pi , is a
set of dependent iterations which should be
executed sequentially. Different CCs can be
executed parallely without synchronization.
Partitioning the iteration space exposes all
the parallelism naturally present in the loop.
Here |P | = 11 is the maximum number of
parallely executable CCs and the size of largest
CC, max(|pi |) is 3. Among many possible
semantically equivalent schedules a realizable
4-thread parallel schedule for the loop is:
2 Motivation
{{-8,-7,-6,-5},{-3,-2,3,7},{-4,-1,1,4},{0,2,5,6}}.
The approach is motivated by the following ex- This example though simple, brings out the
3
ample. Consider a loop having CD3 over iter- possibility of Parallelizing a V D loop.
ation space R=[-8,7].
for(i = -8 ; i < 8 ; i++)
{ S1: g[i] = .........;
S2: ......... = g[i + 3];}

2.1

Background

Our approach rests on using solutions of LDEs.
Without loss of generality, an LDE of the form
ax + by = c, in this paper is assumed to be
normalized where a > 0 and a ≤ |b|.
Given an Iteration space and a set of LDEs,
we use the term Precise dependence(PD)
to denote the collection of all solutions of all
LDEs in the iteration space. A 2 variable LDE
characterizes V D3 , except for the case a = 1
and b = −1 where it characterizes CD3 . Iterations which do not appear in PD are independent iterations.

The CD3 is ”+3” and leads to a 3 element partitioning of iteration space for parallelization
as follows: { {-8,-5,-2,1,4,7}, {-7,-4,-1,2,5}, {6,-3,0,3,6} }.
Consider the following V D3 loop.
for(i = -8 ; i < 8 ; i++)
{ S1: g[2i + 1] = .........;
S2: ......... = g[3i + 6];}

The dependent iteration pairs of the loop
are modelled by LDE: 2x − 3y = 5. The
solutions of the LDE i.e. dependent iteration
pairs over R=[-8,7] are: { (-8,-7) , (-5,-5) , 3 Precise Dependence for Sin(-2,-3) , (1,-1) , (4,1) , (7,3) }. This leads
gle LDE
to Partition, P = ∪∀i pi , of R as shown in
Figure 1 where iterations are nodes and edges A 2 variable LDE characterizes pair of 1 direpresent dependence between them. Each mensional array access in a single non-nested
2

loop. This section presents structure of P and
efficient generation of PD for it. Consider the The general structure of CCs for and LDE,
where m is not a multiple of a or b is:
loop:
{(α
±
mal ), (α
∓
mal−1 b), (α
±
for(i = LB ; i < UB ; i++)
l−2
2
j
i
ma b ), ....., (α ± (−1) .ma bj ), .....,
{ S1 g[ai] = .........;
(α
±
(−1)l−2 .ma2 bl−2 ), (α
±
S2 ......... = g[c - bi];}
l−1
l−1
(−1) .mab ), (α ± (−1)l .mbl )}
Referring to figure 1 and LDE 2x − 3y = 5,
all solutions of the LDE can be derived using
parametric solution {-5 + 3t , -5 + 2t}, where
−1 ≤ t ≤ 6 is an integer[3]. If (x,y) is a
solution of LDE and x precedes y in iteration
order then x is called as source and y is
called as sink. Using parametric solution it is
possible to compute source of a given sink and
sink of a given source. Consider source = 1,
sink = −1 is obtained for t = 2. Similarly
using sink = 1, source = 4 is obtained. Hence
(1,-1) and (4,1) are solutions of LDE. Since
1(source in one solution and sink in other) is
an iteration common to both solutions {-1,1,4}
is a CC. The as possible extensions {8.5,4} and
{-1,-2.33} are not integer solutions so the size
of CC = 3. Iteration 2 can be neither a sink
nor a source, hence 2 is independent iteration.

Seed is a representative iteration of a
CC which can generate a CC. For a Single
LDE single LOOP case all iterations are Seeds
of corresponding CCs.If α is not an integer
CC and Seeds are computed using particular
solution {β, γ} of LDE as: {(β −mb), (γ +ma)}
The Seeds for CCs can be computed
using the aforementioned structure.

3.2

This sub-section shows bounds on number |P |
and length |CC| of CCs for LDE in a given
range R = [L,U].
Lemma 3.1. Number of CCs of length 2 is
R/|b|.

Observations based on aforementioned parametric solution of LDE ax + by = c are:
An Iteration which is a source as well as
a sink extend a CC.
An Iteration which either source or sink
but not both does not extend a CC.
An Iteration which neither source nor
sink is and independent iteration forming singleton CC.

3.1

Bounds on |P | and |CC|

Proof. Every solution of LDE is a CC of length
2. The number of solutions in the range R is
R/|b|. Hence proved.
Number of Singleton CCs is R − 2R/|b|.
Lemma 3.2. Number of CCs of length l
(including sub-CCs of length < l) = R/(|b|l−1 ).
Proof. Proof by Induction: Number of CCs of
length 2 is R/|b| using lemma 3.1.
Assumption: Number of CCs of length k is
R/(|b|k−1 ).
To Prove That: Number of CCs of length k + 1
is R/(|b|k ).
An end element of a CC of length k has a form
(α ± mak )or(α ± mbk ).
if m = ka is a multiple of a the element
(α ∓ kbk+1 ) adds to the CC.
The maximum number of elements having pattern (α ∓ kbk+1 ) ∈ [LB,UB] is R/(|b|k ). Hence

Formulation of CCs

The objective of this section is to formulate
the structure of a CC and relationship between
its constituent iterations. The solutions to
LDE in parametric form {(α − mb), (α + ma)},
where m is an integer and {α, α} is a particular
solution form CCs of length 2.
Longer CCs are formed if m is a multiple
of a or b. As (α + mab) is a common iteration
the CC is {(α − mbb), (α + mab), (α − maa)}.
3

1st , 2nd , 3rd , ..., nth pair of statements respectively.
Let S1 , S2 , S3 , ..., Sn be the solutions of the
Let pmax be a positive integer such that LDE-1,LDE-2,LDE-3,...,LDE-n respectively.
R/(|b|Pmax+1 ) < 1 ≤ R/(|b|Pmax ) then the upper bound on length of CCs is Lmax = Pmax +1.
S = S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn
(1)
Proved.

The upper bound on Number of non singleton CCs is: Nmax = R/|b| − R/(b2 ) +
3
4
Pmax )
R/(|b|
 ) − R/(b )...R/(|b|

= R |b|Pmax − (−1)Pmax )/(|b|Pmax .(|b| + 1)

Lemma 4.1. All the dependent iterations in
L1 are elements of S. (i.e if iterations i1 and i2
are dependent then (i1 , i2 ) ∈ S or (i2 , i1 ) ∈ S.

In multidimensional arrays, subscripts are separable if indices do not occur in other subscripts. A loop is separable if subscripts of all
arrays in it (excluding arrays which are only
read but not written) are separable. We construct and prove precise dependence theory for
simple loops first and then extend it to all separable loops. Precise dependence information is
obtained by solving LDE’s and obtaining the
dependence graph for the given range of the
loop. A node from each connected component
in undirected dependence graph is selected and
stored for generation of the CC and scheduling
purpose (here onwards referred as ’seed’).
Even though we present a general method for
parallelizing and scheduling any type of separable loop, we demonstrate that some special
cases have interesting properties which can be
exploited for efficiency and effectiveness.

Lemma 4.2. All elements in S represent dependent iterations in L1 . (i.e if (i1 , i2 ) ∈ S or
(i2 , i1 ) ∈ S then iterations i1 and i2 are dependent.

Proof. Proof by contradiction. Assume there is
a pair of iteration x1 and x2 which are depenThis gives a closed-form expression for dent but (x , x ) ∈
/ S. x1 and
1 2 / S and (x2 , x1 ) ∈
the bounds, a useful input for scheduling.
x2 access same memory location of atleast one
array (say array A) and for some statements s1
and s2 . This implies (x1 , x2 ) or (x2 , x1 ) is a so4 Classification of loops for
lution of LDE that represents s1 and s2 . Hence
parallelization
(i1 , i2 ) ∈ S or (i2 , i1 ) ∈ S.

4.1

Proof. Proof by contradiction. Assume there is
an element (x1 , x2 ) ∈ S but x1 and x2 are not
dependent. If (x1 , x2 ) ∈ S then (x1 , x2 ) ∈ Sk
for some k th pair of statements (1 ≤ k ≤ n)
and this implies x1 and x2 are dependent.
Theorem 4.3. Precise dependency information for L1 captures all parallelism present at
iteration level granularity.
Proof. From lemma 4.1 and 4.2.
When dependencies come from two or more
LDE’s, solutions combine to produce DAG’s
which represent the dependence graph of loop.
Seeds can be classified as, common seeds:
seeds that occur in solutions of more than one
LDE and unique seeds: seeds that occur in
solution of exactly one LDE.
Dependence graph can be partitioned into
connected components having atleast one
 node
n
which is common seed for any of the k sets of
k LDE’s each (where 1 ≤ k ≤ n).
Common seeds of k lde’s can be obtained by
intersection of common seeds of k2 disjoint pair
of lde’s.

Single Loop, Multiple LDEs

Consider a loop L1 having n pairs of statements such that each pair has exactly one common array access (if a statement has more than
one common array access, it can be broken into
multiple statements having exactly one common
array access), construct a LDE per pair (construction is shown in previous section). Let the
LDE’s be LDE-1,LDE-2,LDE-3, ...LDE-n for
4

4.2

Formulation of Common Seeds

4.4

Nested loops with multiple lde’s
accessing only one common array

Common Seeds are iterations which are common to solutions of 2 or more LDEs. Consider
solutions of 2 LDEs: (source1 , sink1 ) and
(source2 , sink2 ). Common Seeds are formed
when : source1 = source2 or source1 = sink2
or sink1 = source2 or sink1 = sink2

We consider nested loops having no conditional
statements and the body of loop is located inside the inner most loop. All the array access
expressions are affine and are separable.
Consider a loop L2 having l number of nested
loops, a common array A of n dimension, m be
Common Seeds are intersection of solu- the number of pair of array accesses for each
array such that atleast one of the accesses in
tions of multiple LDEs.
For n LDEs there are n Ck 2k (1 ≤ k ≤ n) ways the pair is write.
Let ∀a ∈ [l], ia be used in access exof forming common Seeds.
pressions of Ca number of subscripts and Da
be a set which contains all the subscripts
whose access expressions involve ia . Da =
4.3 Generating
unique
common {d , d , ..., d }, where ∀i ∈ [C ], d ∈ [n].
a,1 a,2
a
a,i
a,Ca
seeds
[n] subscripts are partitioned such that.
A set of seeds is known as unique common seeds
∀i, j ∈ [l] & i 6= j, Di ∩ Dj = φ
if all seeds in the set are common seeds and no
[
two seeds are from the same connected compoDi = [n]
(2)
nent.
∀i∈[l]
Consider a loop in which dependent iteraLet ∀u ∈ [m] and ∀v ∈ [n], Su,v represent the
tions are captured by n LDE’s, let CS be the
formed from uth pair of
set of common seeds (obtained using method solutions of the LDE
th
described in 4.2), UCS be the set of unique array accesses on v subscript.
Let
common seeds, ∀i ∈ [n] Seedi , U Li represent
(T
th
the seeds and unique seeds of i LDE respec1
∀i∈Da Su,i if Da 6= φ
∀u ∈ [m], ∀a ∈ [l], Su,a =
tively.
R
otherwise
a

(3)
Algorithm 1 Algorithm for generating unique
common seeds and unique seeds
U CS = Ø
for i = 1 to n do
U Li = Seedi
end for
while CS 6= φ do
pick an element e from CS
CS = CS − {e}
U CS = U CS ∪ {e}
P art = schedule(e, parametric soln
of LDE’s) 1
CS = CS − P art
for i = 1 to n do
U Li = U Li − P art
end for
end while

where Ra is the range of

ath

Let ∀u ∈ [m], Tu =

loop.
Y

1
Su,a

(4)

∀a∈[l]

Let T =

m
[

Tu

(5)

u=1

Lemma 4.4. T captures all the dependent pair
of iterations in L2 . If iterations (x1 , x2 , ..., xl )
and (y1 , y2 , ..., yl ) are dependent then

Y 
(xa , ya ) if Di ∈
/φ
∈T
(e1, e2)|e1, e2 ∈ Ri otherwise
∀a∈[l]

 OR
(ya , xa ) if Di ∈
/φ
∈ T (6)
(e1, e2)|e1, e2 ∈ Ri otherwise

Y 
∀a∈[l]

where Ri is the range of ith loop
5

Equation 9 and 4 imply ∀a ∈ [l], (xa , ya ) or
(ya , xa ) satisfy all the lde’s present in Da simultaneously. If Da = φ then ia does not appear in
access expression of any subscript. Hence the
two iterations are accessing atleast one common memory location and are dependent, but
this is a contradiction. Hence the proof.

Proof. Proof by contradiction.
Assume
there are two iterations (x1 , x2 , ..., xl ) and
(y1 , y2 , ..., yl ), which are dependent but don’t
satisfy equation 6.
Since the two iterations are dependent,
atleast one pair of array accesses should access same memory location. If the two iterations are accessing the same memory location,
∀a ∈ [l], (xa , ya ) has to simultaneously satisfy
all the LDE’s where ia is used in access expression.
the two iterations access same memory location iff (xa , ya ) or (ya , xa ) satisfies all the lde’s
of subscripts in Da simultaneously.

Theorem 4.6. Precise dependence information for L2 captures all the parallelism present
at iteration level granularity.
Proof. From lemma 4.4 and 4.5.

5

∃q ∈ [m], ∀a ∈ [l], (Da 6= φ) =⇒
∀k ∈ Da , (xa , ya ) ∈ Sq,k

Nested loops and multiple
multi-dimension arrays

or
Consider a nested loop L3 having l number of
loops and N be the number of common ar∀k ∈ Da , (ya , xa ) ∈ Sq,k
(7) rays having n , n , ..., n dimensions respec1 2
N
tively and let m1 , m2 , ..., mN be the number of
Equation 7 and 3 imply 8.
pairs of statements accessing the common arrays respectively. Let P1 , P2 , ..., PN be the de1
pendency information as computed by equation
∃q ∈ [m], ∀a ∈ [l], (xa , ya ) ∈ Sq,a
5 by considering one array at a time.
(8)
Let P = ∪N
i=1 Pi .
Equation 8, 4 and 5 imply equation 6 is true,
Theorem 5.1. Precise dependence P for L3
but this is a contradiction. Hence the proof.
captures all the parallelism present.
∃q ∈ [m], ∀a ∈ [l], (Da 6= φ) =⇒

Lemma 4.5. Every element of T represents
atleast one
Ql pair of dependent iterations in
L2 . If
i=1 {(xi , yi )} ∈ T , then iterations
(x1 , x2 , ..., xl ) and (y1 , y2 , ..., yl ) are dependent.

Proof. P1 , P2 , ..., PN captures all the iteration
pairs which cause dependence in 1st , 2nd , ..., nth
array respectively(from theorem 4.6). Dependencies in loop arise because of dependencies
in accessing atleast one common array. Hence
Proof. Proof by contradiction.
Ql Assume there P captures all the dependencies present in the
exists an element E =
i=1 {(xi , yi )} and
E ∈ T , but iterations (x1 , x2 , ..., xl ) and loop.
(y1 , y2 , ..., yl ) are not dependent.
Equation 5 implies 9 and equation 9 and 4
6 Generation of the connected
imply 10 .

∃q ∈ [m], E ∈ Tq
(∃q ∈ [m], ∀a ∈ [l], (xa , ya ) ∈

1
Sq,a

or
1
∃q ∈ [m], ∀a ∈ [r], (ya , xa ) ∈ Sq,a
)

component from seed during
run-time

(9)

A seed is a representative iteration of a CC.
This section gives an algorithm for generating
(10) CC from its seed with its proof of correctness.
6

6.1

Algorithm for generating itera- e and ∀x ∈ Dh , x > e & ((x, e) ∈ T or (e, x) ∈
T )).
tion schedule

Since there are no cyclic dependencies, there
Function: Computes a dependency preserving is atleast one node for which |D | = 0.
l
schedule of a connected component.
Input: A seed (belonging to the CC, whose
1. If |Dl | = 0 for e then it can be executed
schedule is being computed) and solutions to
and Dh is added to heap.
the LDE’s in parametric form.
2. If |Dl | =
6 0 for e and e is not marked as
Algorithm:
visited then elements of Dl and Dh are
added to heap along with e marked as visAlgorithm 2 Algorithm for generating iteraited.Hence all the dependencies of e have
tion schedule
been added to heap.
Add seed to min heap (referred to as heap in
this algorithm).
while heap is not empty do
remove minimum element e
if e is not visited then
Discover dependencies of e and add
them to heap
if there are no dependencies for e
then
Add e to schedule
else
Mark e as visited
Add e to heap
end if
else
if e was not added to schedule then
Add e to schedule
end if
end if
end while

6.2

3. If e is marked as visited then it can be
executed. Since e has been visited, nodes
in Dl of e were added to heap previously.
As e is the minimum value node on heap
now, this implies that all elements in Dl of
e have been executed.
Since the above mentioned process is repeated till heap is empty, all the nodes in the
connected component are scheduled/executed
in dependency preserving order.

6.3

Time and space complexity

Since every node is examined atmost twice (i.e
if Dl 6= 0 for some node e then e is examined
for first time when e is minimum value node on
heap and e is NOT marked as visited and examined for second time to when e is the minimum
value node on heap and it marked as visited).
Maximum number of steps taken by the algorithm is atmost 2n, where n is number of nodes
in the connected component. Hence algorithm
runs in O(n) time.
As heap contains the nodes in the connected
component, in the worst case, all but one of the
nodes in the connected component will be on
heap. Maximum space consumed by the algorithm is n − 1 units. Hence algorithm runs in
O(n) space.

Correctness Proof

Dependencies of a node are discovered by substituting the value of node in the solution of the
LDE’s. All nodes on which the given node is
dependent on and all the nodes which depend
on the given node are discovered (by theorem
4.3).
Let e be the minimum value node taken out
of min heap, let Dl be the set of nodes on
which e depends (i.e nodes in Dl should be ex- 7 Iteration schedule for nested
ecuted before e and ∀x ∈ Dl , x < e & ((x, e) ∈
loops
T or (e, x) ∈ T )), (T is constructed in equation
5) and Dh be the set of nodes which depend Consider a nested n loop structure, let V conon e (i.e nodes in Dh should be executed after tain the loops whose induction variables are
7

used in array access expressions and W contain
the loops whose induction variables do not appear in any array access expression, V ∪ W =
[n] and V ∩ W = φ. Let loops be numbered
as l1 , l2 , ..., ln starting from outermost to innermost loop. Let ∀i ∈ V, Seedi be the set containing seeds to generate connected components of Algorithm 3 Algorithm for generating iterathe partition arising out of all the LDEs in- tion schedule for nested loops
volving ith loop induction variable. We present
procedure schedule main
Algorithm 3 for scheduling nested loops. It
for i=1 to n do
uses Algorithm 2 to schedule individual loops.
if li ∈ V then
Sequential nested loops will be executed by a
Create |Seedi | number of threads.
group of synchronization free threads parallely.
Do a one-to-one mapping
of threads to seeds in Seedi .
Each of the created thread runs
8 Experimental Results
Algorithm 2 to generate a
schedule for running ith loop.
The analysis and algorithms developed and
Each thread calls
presented in this paper show how partitioning
SCHEDULE SUB(i+1).
of iteration space can be done in case of
3
exit
V D and multiple loops with multiple LDEs.
else
We have considered 2 variable LDEs with
Keep the ith loop sequential.
separable loops. In the presence of multiple
Schedule consists of iterations in
LDEs and the ensuing interactions between
range of ith loop.
their individual partitions the generation of
end if
the overall partition of the system is difficult.
end
for
While our formulation successfully captures
Execute body of loop. 2
the overall partition, the experimentation
end procedure
explores the extent of existing parallelism.
procedure schedule sub(k)
for i=k to n do
The experiments were parametrized by:
if li ∈ V then
i) Loop range ii) number of LDEs iii) RanCreate |Ri | number of threads. 3
domized coefficients for V D3 and iv) number
Do a one-to-one mapping of
of experiments carried out. The loop range
15
15
threads to values in Ri .
was varied from [ −2 to 2,..., −2 to 2 ],
else
[1..90] LDEs and up to 100 experiments. For
Keep the ith loop sequential.
each experiment the partition was evaluated
Schedule consists of iterations in
in terms of minimum, maximum and averrange of ith loop.
age number of CCs, which are measures of
end if
exploitable parallelism.
end for
Execute body of loop.
• Table 1 shows that the extent of paralend procedure
lelism on the average is atleast 95% across
various ranges. Thus, V D3 for single LDE
has significant exploitable parallelism even
for large loop ranges.
• Table 2 shows average parallelism when
the number of LDEs are increased up to
90. The number of parallel components
8

Range
5
9
17
33
65
129
257
513
1025
2049
4097
8193
16385
32769
65537

Parallels
5
9
16.97
32.93
64.81
128.44
255.27
508.42
1012.16
2016.82
4021.72
8026.04
16036.87
32058.47
64101.76

CCs
0
0
0.03
0.07
0.18
0.54
1.67
4.35
12.32
30.92
72.44
161.06
335.95
685.59
1384.98

Independents
5
9
16.94
32.86
64.63
127.9
253.6
504.07
999.84
1985.9
3949.28
7864.98
15700.92
31372.88
62716.78

Range
5
9
17
33
65
129
257
513
1025
2049
4097
8193
16385
32769
65537

2LDE
4.97
8.92
16.82
32.59
64.15
127.11
252.79
501.27
993.81
1972.04
3920.22
7810.89
15599.41
31176.54
62330.68

5LDEs
4.93
8.89
16.69
32.39
63.28
124.20
244.76
481.27
945.15
1852.66
3646.23
7224.94
14388.60
28714.82
51724.69

30LDEs
4.61
8.16
15.11
28.57
54.06
99.11
176.12
308.30
525.85
897.32
1557.49
2853.74
5488.09
10722.84
21179.73

90LDEs
3.99
6.78
11.74
20.66
34.68
51.44
68.40
87.65
114.74
150.58
211.95
346.77
628.31
1159.05
2199.60

Table 1: Average exploitable parallelism for
Table 2: Average exploitable parallelism for
single LDE
varying No. of LDEs

reduce considerably when the number of
LDEs increase. This is a consequence of
ineraction between the partitions of the individual LDEs. Figure 2 shows the range
of overall exploitable parallelism for 1,30
and 90 LDEs. The table 2 shows average behaviour and graph shows maximum
parallelism. It can be seen that as the as
the number of LDEs increse the maximun
paralleism decreses. There is not enough
differnece in the minimum parallelism is

• Results show that exploitable parallelism
decreases for increasing number of loops.
It was observed that a large number of
dependences cross loop independent iterations (αs) in solutions of LDEs. We computed a representative iteration αr using
heuristic based on set of loop independent
iterations (αs ). The range was split into
[LB,αr] and [αr+1,UB]. The partition for
all the LDEs reported in table 2 have been
recreated using the heuristic. This is reported in table 3 it shows a significant improvement in exploitable parallelism if the
range is split into [LB , αh ] and [αh + 1
, UB]. The improvement ratio increases to
approximately 20:1 as the number of LDEs
and range increase. Figure 3 shows significant improvement in maximum parallelism
for 1,30 and 90 LDEs after splitting the
range into 2 ranges. Comparing Figure 3
and Figure 2 it can be observed that the
effective maximum parallelism shows considerable improvement. To summarize the
heuristic used by us to split the iteration
ranges seems to profitable.

70000
90 LDE min - 90 LDE max
1 LDE max - 30 LDE max
30 LDE max - 90 LDE max
60000

Available parallelism

50000

40000

30000

20000

10000

0
0

10000

20000

30000

40000

50000

60000

70000

Range

Figure 2: Overall Exploitable parallelism

9

30LDEs
splitAvg
5
4.61
4.68
9
8.16
8.49
17
15.11
15.57
33
28.57
29.29
65
54.06
56.10
129
99.11
108.25
257
176.12
217.2
513
308.30
439.07
1025 525.85
880.85
2049 897.32
1754.99
4097 1557.49 3514.13
8193 2853.74 7065.49
16385 5488.09 14264.31
32769 10722.84 28702.30
65537 21179.73 57578.68
Range Avg

90LDEs
splitAvg
3.99
4.15
6.78
6.93
11.74
12.23
20.66
21.44
34.68
37.73
51.44
70.25
68.40
144.19
87.65
318.07
114.74 660.92
150.58 1330.00
211.95 2651.60
346.77 5410.43
628.31 11192.73
1159.05 22849.37
2199.60 46151.75
Avg

space, a set of parallel CCs. We computed
bounds on the number and size of CCs. The
partition is represented in a reduced form by
a set of seeds. Algorithms to use this set for
generation of the components dynamically in
a demand driven manner which can lead to
schedules are presented. As we could not find
loops with large number of LDEs in practice
randomly created multiple LDEs were used for
our experimentation. Results show existence
of reasonable parallelism which reduces as the
number of LDEs increase. To improve results
we have formed an alternate partition using
a heuristic. This heuristic shows non trivial
improvement in parallelism. Further method
to obtain synchronization free parallelism is
presented at iteration level granularity using
efficient algorithms.

While computing precise dependence in
Table 3: Improved Average exploitable paral- the most general case is NP-complete, most
lelism after range splitting
of the array access patterns found in practice
are amenable to our approach. Our handling
of exploitable parallelism in V D3 and multiple
loops expands the domain of applications that
are parallelizable today. Compile time analysis
for precise dependence opens opportunity of
automatic generation of parallel threads suited
for multi-core configuration. Even heavily connected dependence graphs show considerable
parallelism which can be exploited by a well
designed scheduling algorithm.
70000

90 LDE min - 90 LDE max
1 LDE max - 30 LDE max
30 LDE max - 90 LDE max

60000

Available parallelism

50000

40000

30000

20000

10000

Some of the possible future directions are:
characterizing class of loops for which precise
dependence can be computed. Integrating
precise dependence analysis, seed generation
and scheduling for automatic generation of
parallel code.

0
0

10000

20000

30000

40000

50000

60000

70000

Range

Figure 3: Exploitable parallelism after cut

9

Conclusion

Capturing dependence in case of loops with
V D3 is presented in this paper. Our approach
uses a two variable LDE and its parametric
solutions to analyze and mathematically
formulate Precise Dependence, the inherent
dependence in the loops. Theoretical methods
to compute precise dependence are presented.
The result is a partition of the iteration

References

10

[1] Supratim Biswas, Ajay Sethi and
Amitabha Sanyal.
Extensions to cycle shrinking. International Journal of
high Speed Computing, 7(2):265–284,
1995.

[2] Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures.
Morgan Kafumann, 2002.
[3] Utpal Banerjee. Dependence Analysis.
Kulwer Academic Publishers, 1996.
[4] C. D. Polychronopoulos. Compiler Optimizations for Enhancing Parallelism and
Their Impact on Architecture Design.
IEEE Transaction on Computers, August
1988.

11

