Array Replication to Increase Parallelism inApplications Mapped to Configurable
Architectures
Heidi E. Ziegler, Priyadarshini L. Malusare and Pedro C. Diniz
University of Southern California / Information Sciences Institute4676 Admiralty Way, Suite 1001
Marina del Rey, California, 90292{ziegler,priya,pedro}@isi.edu

Abstract. Conﬁgurable architectures, with multiple independent onchip RAM modules, oﬀer the unique opportunity to exploit inherent
parallel memory accesses in a sequential program by not only tailoring
the number and conﬁguration of the modules in the resulting hardware
design but also the accesses to them. In this paper we explore the possibility of array replication for loop computations that is beyond the reachof traditional privatization and parallelization analyses. We present acompiler analysis that identiﬁes portions of array variables that can be
temporarily replicated within the execution of a given loop iteration,
enabling the concurrent execution of statements or even non-perfectly
nested loops. For conﬁgurable architectures where array replication isessentially free in terms of execution time, this replication enables not
only parallel execution but also reduces or even eliminates memory contention. We present preliminary experiments applying the proposed technique to hardware designs for commercially available FPGA devices.

1

Introduction

Emerging computing architectures now have multiple computing cores and multiple memory modules such as discrete and programmable register ﬁles as well
as RAM blocks. For example, ﬁeld-programmable gate arrays (FPGAs) allow
designers to deﬁne an arbitrary set of registers and customize the topology ofinternal RAM blocks [12] to suit the data and computational needs of the computation. Other programmable architectures simply allow for the arrangementof registers and ﬁne-grain functional units to create tailored pipelined architectures [5]. Overall these ﬂexible architectures provide ample opportunities to
exploit data parallelism as well as coarse and ﬁne-grain parallelism.
Unfortunately, mapping sequential applications to these architectures is a difﬁcult task. Programmers must explicitly manage the mapping and organizationof arrays among the rich set of storage resources, conﬁgurable register sets andon and oﬀ-chip memories, if they are to fully exploit the architectural beneﬁts
of conﬁgurable devices. The wide range of design choices faced by the programmer makes it desirable to develop automated analysis and mapping tools that2

can navigate certain characteristics of the design space, in particular, the data
dependences found in common sequential imperative programs.
In this paper we focus on array privatization and array replication techniques
to enable compilers to uncover parallelism opportunities in sequential computations that are traditionally impeded by both anti and output-dependences. We
focus on array privatization not across loop iterations but within the same loop
iteration. It focuses on the analysis of non-perfectly nested loops by determining
anti-dependences between a sequence of nested loops in a control loop.
When two computations, that execute serially, access the same array location,
reading its previous value and then writing a new value into the location, thisgives rise to an anti-dependence between them. Similarly when two computation
use the same location to store consecutive values that are otherwise independent
creates an output-dependence. These dependences can be eliminated by creatinga copy of the array, that each computation freely accesses. Each computation
uses a distinct memory location to write and read a value, and in the absence oftrue-dependences between these loops nest, they can execute concurrently within
the same iteration of the control loop.
This concurrent execution, however, raises the issue of memory contention
when two or more concurrently executing loop nests access the same array region,i.e., the loops exhibit input-dependences. To overcome this memory contention,
we take advantage of the ﬂexibility of memory mapping in conﬁgurable architectures by creating copies of shared array variables. By accessing the array copies,
the parallel loop nests can therefore execute concurrently due to the absenceof anti-dependences but also be contention-free. When the original computation
exhibits loop-carried true-dependences (i.e., values written in a given iterationthat are read in a later iteration of a loop), the transformed code must update
the array copies (not necessarily all of them) when the concurrent execution
terminates to ensure that subsequent computations proceed with the correct
values.
This transformation explores a space-time tradeoﬀ. In order to eliminate
anti-, output- and input-dependences, the implementation requires additional
memory space. In addition, some execution time overhead is incurred in updating the copies to enforce the original program data dependences. The analysis
abstractions, in cooperation with estimates of memory space usage, allow for aneﬀective algorithm to manage this tradeoﬀ and adjust, possibly dynamically, theperformance of the implementation in response to available resources.
In this paper we evaluate the replication and privatization transformations
when mapping a set of computations to a conﬁgurable computing device, aXilinx VirtexTM FPGA. We simulate the transformed code as a concurrently
executing hardware design, thereby revealing the eﬀects on performance and thecorresponding cost of storage.
This paper makes the following speciﬁc contributions:– Describes the application of array replication and array privatization transformations to take advantage of the ﬂexibility of conﬁgurable architectures.

3– Extends existing array data-ﬂow analysis to identify opportunities for concurrent execution of entire loops when arrays are replicated and temporarily
privatized.
– Presents experimental results of our array replication algorithm when applied
to a sample set of image processing computations for speciﬁc mappings to
an FPGA device.
Preliminary results reveal that a modest increase of storage for private andreplicated data leads to hardware designs that exhibit respectable execution time
speedups, making this approach feasible when storage space is not a limiting
factor in the design.
With the increase in VLSI device capacity and the emergence of computing
architectures that have multiple computing units on the same die and a veryrich set of conﬁgurable storage structures, the placement and layout of data
will become increasingly important if applications are to fully exploit the true
potential of internal data bandwidth and computational units.
This paper is structured as follows. Section 2 illustrates a motivating example for array replication. Section 3 describes the compiler analyses and a data
replication algorithm. In section 4 we present preliminary experimental resultsof the application of the proposed analyses to a set of multimedia computations
targeting an FPGA conﬁgurable device. We discuss related work in section 5
and then conclude in section 6.

2

ExampleWe now present an example showing how array replication (or copying) eliminates anti- and output-dependences thereby enabling concurrent execution ofloops. This example also illustrates the elimination of input-dependences (i.e.,
when two loops access arrays that are stored in the same memory module) that
reduces memory contention introduced by concurrency. The computation is illustrated in ﬁgure 1 and consists of an outer i loop with three loop nests, L1, L2and L3 nested within. Each of these three loop nests access a two-dimensional
array variable A using aﬃne subexpressions. The ﬁrst two loop nests L1 and L2
read two consecutive rows of the array whereas the third loop nest L3 writes thearray row read by the ﬁrst loop nest in the same iteration of i and in iteration
i+1 by the second loop nest.
Within loop i, one cannot execute loops L1 and L2 concurrently with loop
L3, since there is an anti-dependence between L3 and the other loops. Iterations of the i loop also cannot be executed concurrently given the loop-carriedtrue-dependence between L3 and L2. As such, privatization of A is therefore notpossible either [11].
A way to enable concurrent execution of all loop nests during the executionof each iteration of the i loop is to create a copy of array A named A 3, which
L3 can update locally while loops L1 and L2 read from the original array A.
We call this transformation where the array is being replicated with respect
to the loop nest that writes it, a partial replication. At the end of concurrent

L1: reads A[i+1][*]L2: reads A[i][*]L3: writes A[i+1][*]L2: reads A[i-1][*] L3: writes A_3[i][*]barrier
update A[i][*] = A_3[i][*]

L1: reads A[i+1][*] L2: reads A[i][*] L3: writes A[i+1][*]barrier
update A[i+1][*] = A_3[i+1][*]

iteration iiteration i

L1: reads A[i][*]iteration i+1/* loop L2 */for(j=0; j < N; j++){for(k=0; k < N; k++){. . . = A[i-1][k];...
}}L1: reads A_1[i+1][*] L2: reads A_2[i][*] L3: writes A[i+1][*]barrier
update A_2[i+1][*] = A_3[i+1][*]

iteration i+1

L1: reads A_1[i][*] L2: reads A_2[i-1][*] L3: writes A_3[i][*]barrier
update A_2[i][*] = A_3[i][*]iteration i(b) Concurrent execution without array replication.

time/* loop L3 */for(j=0; j < N; j++){for(k=0; k < N; k++){A[i][k] = . . .
...
}
}
}

anti
dependency(a) Sequential execution.

time/* loop L1 */for(j=0; j < N; j++){for(k=0; k < N; k++){. . . = A[i][k];...
}}iteration i+1/* control loop */for(i = 0; i < M; i++){

L1: reads A[i][*]L2: reads A[i-1][*]
L3: writes A[i][*]true
dependency

time

4

(c) Concurrent execution replicating array A.

Fig. 1. Example computation and illustrative sequential and concurrent execution.

execution of loops L1 through L3 within one iteration of the i loop, we insert a
synchronization barrier and then update the original array A with the new values
generated by loop L3. This concurrent execution is illustrated in ﬁgure 1(b) andthe corresponding parallel code is depicted in ﬁgure 2(a).
Due to the concurrent execution of the three loop nests, there is now memory
contention on array A by the loops L1 and L2. In an architecture with memory
modules with a limited number of memory ports and in the absence of careful scheduling of read operations the execution of each loop will possibly stallfor data. To alleviate the memory contention, we further replicate array A andassign these new arrays A 1 and A 2 to two memories that can be accessed inparallel by loops L1 and L2. In this extended replication transformation, calledfull replication, we create copies that are local to the loops that both read andwrite the arrays.1 We trade decreased execution time for increased array storage.
In addition, the implementation must update the arrays to ensure data consis1

There are additional degrees of replication with respect to the loops that read agiven array. Furthermore, this need to replicate to reduce memory access contention
interacts with other transformations such as custom data-layout enabled by loop
unrolling as described in [9].

5for(i = 0; i < M; i++){ /* control loop */for(i = 0; i < M; i++){ /* control loop */begin par{for (j=0; j < N; j++){ /* loop L1 */for (k=0; k < N; k++){. . . = A[i][k];. . .;}}}

begin par{for (j=0; j < N; j++){ /* loop L1 */for (k=0; k < N; k++){. . . = A 1[i][k];. . .;
}
}
}

{

{

}

for (j=0; j < N; j++){ /* loop L2 */for (k=0; k < N; k++){. . . = A[i-1][k];. . .;}}}{{for (j=0; j < N; j++){ /* loop L3 */for (k=0; k < N; k++){A 3[j][k] = . . .;. . .;}}for (j=0; j < N; j++){ /* loop L3 */for (k=0; k < N; k++){A 3[j][k] = . . .;. . .;}}}for (j=0; j < N; j++){ /* loop L2 */for (k=0; k < N; k++){. . . = A 2[i-1][k];. . .;}}}
end par/* update original A */for (k=0; k < N; k++){A[i][k] = A 3[i][k];}}}end par/* update A 2 */for (k=0; k < N; k++){A 2[i][k] = A 3[i][k];}(a) Transformed code with(b) Transformed code withpartial replication
full replication
Fig. 2. Transformed example computation

tency. While updating complete arrays is a safe and conservative approach, in
actuality, only array elements that correspond to loop-carried true-dependences
need to be updated. In our example and given that the array section written by
L3 is read only by L2 in the next iteration of the i loop, the implementation only
needs to update the array A 2 associated with L2 and not A 1 associated with
L1. In other words the deﬁnition of the array row written by L3 reaches L2 but
not L1. Figure 2(b) depicts the transformed code after the replication of thesearrays and the corresponding concurrent execution is illustrated in ﬁgure 1(c).
While the inclusion of a copy operation is likely to decrease performance
beneﬁts of such transformations in a classical architecture, in the context of
conﬁgurable architectures, it has little if any impact on overall execution time.
When the implementation of the computation in L3 has to issue a write operation
to a speciﬁc memory module with a conﬁgurable number of read and write ports,
one can specify a multi-port write operation to occur synchronously to many
memory modules without any performance penalty.
This example illustrates the kind of computation the array privatization andreplication analysis described in this paper is designed to handle. First, we focus
on non-perfectly nested loops with intra-iteration anti-dependences and truedependences to recognize computations that can execute concurrently by the6introduction of one copy to the loop nest that modiﬁes sections of an array.
These values must then be copied back into the original array or other copies
at the end of the execution of the parallel code region. Second, we introduce
array copies to eliminate memory contention during the concurrent execution ofmultiple loop nests, thereby eliminating memory contention by exploiting thememory bandwidth available in architectures with conﬁgurable storage units.

3

Compiler Analysis

We now describe the compiler analysis and basic abstractions used to determine
the opportunities for array replication with the goal of executing loop nests concurrently while reducing memory contention caused by accessing shared arrays.
In this section we focus on imperfectly nested loops that manipulate array references. Whereas our analysis can be very precise for arrays that have aﬃne array
access functions, it can also handle, with loss of precision, references that arevery irregular, i.e., array-based indirect accesses.
3.1

Basic Abstractions and Auxiliary Functions

This analysis focuses on imperfectly nested loops where the outermost loops i1
through ik in the nest are perfectly nested. The ik loop in the nest has a loop
body that consists of a sequence of loop nests, each of which is a perfectly nested
loop as well. We name the ik as the control loop and build a control-ﬂow-graph
CFG corresponding to its body where each node corresponds to a loop nest. For
the example in section 2, the CFG is a linear sequence of loop nests L1 throughL3, with loop i as the control loop. The corresponding CFG and dependences
between the nodes are illustrated in ﬁgure 3.
For each loop nest, corresponding to a node nk in the CFG, we deﬁne theupwards-exposed read and write regions for a given array A denoted by ER(A, nk )and WR(A, nk ) respectively. The accessed array region is described by a set of
linear inequalities. Given that each loop nest may be enclosed by a control loop,
the corresponding dimension in the linear inequality will consist of symbolic
information. A simple, yet eﬀective implementation restriction is to limit theanalysis to loops with single-induction variable aﬃne subexpressions making thepresence of index variables of the control loop simple. Figure 3 depicts the CFGof the control loop for the example in section 2, along with the relevant exposedread and write region abstractions for the array A.
Using these abstractions, the compiler can compute data dependences between nodes of the CFG uncovering anti-, input-, output- and true-dependencesby determining if the intersection between ER(A, ni ) and WR(A, nj ) between nodes
ni and nj corresponding to the same array are non-empty. For instance, ananti-dependence exists between loops ni and nj due to array variables A iﬀ
{WR(A, ni) ∩ ER(A, nj) with i > j} = ∅. In some cases the intersection will
yield symbolic variables corresponding to the loops of the nest and the dependence test must conservatively assume dependence. In addition, we also deﬁne

7d ( n 1, n 2) = <0>{

Loop 1anti

ER A= { i < d0 < i , 0 < d1 < N-1}

WR

={}

n1
A
n1

dinp( n 1, n 2) = <1>{

Loop 2ER A= { i-1 < d0 < i-1, 0 < d1 < N-1}
n2
A ={}
WR
n2

d ( n 3, n 2) = <1>
true

Loop 3{

ER A = { }n3WR A = { i < d0 < i , 0 < d1 < N-1}n3

n 3 post dominates { n 1, n 2}

Fig. 3. Control ﬂow graph and dependence information for the example code.

a dependence distance for each dependence type. For the example in section 2,
there is a loop-carried true-dependence on the control loop i with a distance of
1 between the nodes corresponding to the loops L2 and L3 since L3 writes theith row of the array A which is read by L2 on the subsequent iteration of i.
3.2

Algorithm for Detecting Replication

Using the abstractions for data accesses, ER and WR, as well as the δ data dependence distance information, we now describe a compiler algorithm that determines opportunities for parallel execution of the loop nests that make up the
body of the control loop. The algorithm also determines which arrays can be
replicated to mitigate memory contention resulting from concurrent execution.
The algorithm, shown in ﬁgure 4, is structured into 5 main steps. In the ﬁrst
step the algorithm extracts the control loop i and the CFG corresponding to
the enclosed loops. In the second step, for each node nk , the algorithm computes
ER and WR for each array variable A. In step three, the algorithm computes thedependence distances between every pair of nodes. In step four, the algorithm
determines the opportunities for concurrent execution of the nodes within thesame iteration of the i loop. The basic idea of this step is to identify a straightline sequence of nodes such that the last node of the sequence exhibits an antidependence with the other nodes but there are no true- or output-dependences
for that same iteration.2 The set of nodes that meet this data dependence andcontrol dependence criteria are gathered in a parallel region corresponding to
the new node named parallel(nk). The compiler creates an array copy corresponding to this parallel node in order to eliminate anti-dependences and inserts
synchronization code at the beginning and end of the parallel region so thatvalues in the original array are updated with the value generated by nk .
2

Extending this simple algorithm to regions of the CFG with control-ﬂow leads toseveral code generation complications.

8
Step 1. Extract control loops and coarse-grain control flow graphextract control loops i0 , . . . , ik and CFG;
Step 2. Determine exposed read and write information for each loop
for all nodes ni ∈ CFG
for all arrays A ni manipulates
compute ER(A, ni ) and W R(A, ni );Step 3. Compute dependence types and distances
for all pairs of nodes (ni ,nj ) ∈ CFG
compute δtype (ni , nj ) <, =, > x where x is distance
Step 4. Identify parallel regions
for all nodes nk ∈ CFG s.t. W R(A, nk ) = ∅ doif(numPreds(nk ) > 1) thenparallel(nk ) = ∅;continue;
R = {nk };n = preds(nk );while (n = entry OR numSuccs(n) = 1) do
if ((ni ∈ R) AND (ER(A, ni ) = ∅) AND (δtrue (ni , nk ) = 0)) thenR = R + {ni }end if;end while;
parallel(nk ) = R;
insert fork before firstNode(parallel(nk ));insert join barrier after lastNode(parallel(nk ));end for;end for;
Step 5. Reduce contention by replicating arrays
for all parallel regions of CFG do// Partial Replication caseinsert update array variable A for W R(A, nk );if (FullReplication) thenselectNumberCopies(parallel(nk));
for all nj ∈ parallel(nk ) do
update copy of A that has δtrue (nj , nk ) > 0;
for all arrays B replicate array for which δinput (ni , nj ) = 0;
end for all;end if;end for;Fig. 4. Parallelism detection and replication algorithm.

In step ﬁve, the algorithm identiﬁes which array should be replicated foreach parallel region. In this step the algorithm must decide how many copies toinsert for each array variable and which copies need to be updated due to truedependences across iterations of the control loop. In its simplest form, partial
replication, there is a single copy for each parallel region that corresponds toa single node writing to an array variable. In the full replication variation, thealgorithm generates one copy per each node that reads the array variable aswell. Rather then updating all array copies, the algorithm only updates copies
using the reaching deﬁnitions across loop iterations which is captured by loopcarried dependence information [13]. To this eﬀect the algorithm determines
which nodes, and for each array variable, exhibit a loop-carried true dependence,at the control-loop level. The particular value of the dependence distance of thecontrol loop indicates the number of iterations across which the values need to9

be updated in the original array location or copies. For the shortest distance of
1, the values must be updated at the end of the current iteration to be used in
the subsequent iteration. However, if the distance is longer, one can delay the
update and overlap it with the execution of another iteration thereby hiding its
cost.
In this description we have statically determined which nodes of the CFG
and therefore which loop nests operate on copies of the array using an externalfunction, selectCopies(parallel(nk)). We foresee a more sophisticated algorithm, possibly dynamic, in which the need to replicate is selected at run-timedepending on execution conditions.
3.3

Granularity of Replication

The algorithm described above can be augmented to allow the compiler to uncover opportunities for ﬁne-grain replication by observing the order (in terms ofarray dimensions) in which multiple loop nests access the same array variables.
In the example in ﬁgure 1 during parallel execution all loop nests access sharedarrays in the same order, therefore array replication can occur at the ﬁnest granularity of an element.3 Then concurrently executing loop nests only require 1
element of replicated data in the array copy. As soon as a loop nest has ﬁnishedprocessing a given element, another element of the array can be copied. In addition the updates for copies can also proceed at a ﬁner granularity as long as
the iterations of the various concurrent loops execute synchronously. A similar
analysis approach has been developed in the context of choosing the granularityof multiple communicating computations executing in a pipelined fashion [13].
In addition to requiring less storage space, at an increase in synchronization
cost, this strategy also allows for the updates of copies to be executed concurrently with the parallel execution of the loop nests with the proper synchronization. This strategy reduces the execution time overhead of copy updating andsubstantially reduces the storage overhead.
The presence of irregular data access patterns, i.e., non-aﬃne does not posea fundamental problem for the analysis outlined here. Rather then being able
to determine exactly the array sections that need to be replicated in the caseof a ﬁner-grain synchronization, the analysis settles for replication at the nextcomputational level at which the irregular data access pattern has been absorbed
in a speciﬁc array dimension.

4

Experimental Results

We now describe the experimental methodology and results for the manual application of the analysis and program transformations to a set of kernels.
3

The ﬁnest granularity may not be the best choice as additional execution time overhead might not be amortized over the small data size.

10

4.1

Methodology

We applied the analysis algorithm described in section 3 and evaluated the beneﬁts and drawbacks using 3 synthetic kernels hist, bic and lcd.
The hist kernel is composed of 3 nested loops inside a single control loop witha total of 15 lines of C code. Each of the inner loop nests in hist manipulates
3 distinct array variables exhibiting anti-dependences among the last loop nest
and the ﬁrst two nests. There is a true dependence between the ﬁrst and second
loop nests preventing them from being executed concurrently even when antidependences are removed by replication. Nevertheless, the second and third loop
nests can be executed concurrently.
The bic kernel is composed of 4 loop nests inside a single control loop witha total of 50 lines of C code. Each of the inner loop nests manipulates 4 arrayvariables. This kernel exhibits intra-iteration anti-dependences among the four
loop nests and an output dependence between the last two nests. Replicating asingle array variable, however, will enable the concurrent execution of the ﬁrst
three loop nests.
The lcd kernel is composed of 3 loop nests inside a single control loop witha total of 20 lines of C code. Each of the inner loop nests manipulates 2 arrayvariables. This kernel exhibits only intra-iteration anti-dependences among thelast loop nest and the ﬁrst two loop nests allowing the three loop nests to be
executed concurrently via replication of a single array variable.
After we apply the analysis outline in section 3, we manually translate eachof these kernels into behavioral VHDL and simulate the execution of the control
loop using the MonetTM [7] behavioral synthesis tool. From this simulation, we
obtain the execution time of each loop nest, in clock cycles at a given frequency,
assuming each loop nest executes sequentially. Using the number of clock cycles
obtained via the Monet simulation, we then use a simple discrete event simulator
to determine the parallel execution time when one or more of the arrays havebeen replicated, thereby allowing for concurrent execution as well as reduced
memory contention. This simulator allows us to determine the waiting time ofeach loop nest in the control loop as well as the overall percentage of timethe execution spends stalled for memory operations. In our experiments we did
not consider software pipelining execution techniques as they further increase
the memory contention thereby skewing the replication results to be even morefavorable to the application of the technique presented here. In these results weassume that every RAM is dual ported, with a one read and one write portthat can be accessed in parallel and assigned the latency of every read and write
operation to be 3 clock cycles.
4.2

Results

We now describe the results in terms of execution time reduction due to parallelism and the impact on memory space usage for each kernel. The original
version is simply the kernel executing in a sequential fashion without any replication or parallel execution. The partial replication version corresponds to the11introduction of array copies for eliminating anti-dependences. In this version
parallel loops may still access shared data. Finally, the full replication version
includes copies of the array variables to decrease memory contention.
Table 1 summarizes the results in terms of execution time for each kerneland each analysis variation. For the partial and full replication versions, wehave included the cost of performing the update operations after the parallel
regions execute. The table indicates the amount of time each transformed kernel
spends doing computation (comp. columns), updating the copies if any (update
columns), stalling for memory (stall columns) and the overall percentage reduction (red. columns) of the total execution time taking into account the copy
operations which execute sequentially after the parallel region executes.
KernelOriginal CodePartial Replication
Full Replicationcomp. update total stall red. comp. update total stall red. comp. update total stall red.
%
%
%

hist

1.86

0

1.86

0

–

1.29

0.07

1.36

26.9 1.29

0.07

1.36

0

26.9

bic

131.1

0

131.1

0

–

77.8

4.11

81.9 36.9 37.5 65.55

4.11

69.66

0

46.8

lcd

61.44

0

61.44

0

–

49.15

4.10

53.25 24.58 13.3 24.57

4.10

28.68

0

53.3

0

Table 1. Execution time results (cycles in thousands).

As can be seen, there is a sharp decrease in the execution time in the partial
replication code versions due to parallel execution ranging from 13% to 37%.
This reduction simply reﬂects the concurrent execution of loop nests as revealedby comparing the values in the comp. columns for the original and partial replication versions. The results for the partial replication versions also reveal theopportunity to reduce execution time since the stall time values are substantial
in the case of bic and lcd. For hist there is no stall time in the partial replication version given that only two loop nests execute concurrently and one ofthem updates a local copy. By aggressively replicating data in the full replication
versions, the execution time is subsequently reduced leading to overall speedups
between 1.37 and 2.1 over the original code version.
Table 2 depicts the space requirements for each code version. For each kernel and respective code version, we describe the number and size (in terms ofnumber of array elements) the code uses along with the total space in bytes andpercentage increase over the original code version.
Reﬂecting the opportunity for replication, the space requirements increase
monotonically between the partial and full replication code versions. In the caseof the lcd and hist kernels there is a substantial increase in memory usage close
to 100%. While this increase may seem extreme, we note that these ﬁgures arebiased by the fact that we do not take into account other kernel data structures.
This eﬀect is apparent in the bic kernel where due to the fact that this kernel

12KernelOriginal CodeArray
Total Size Incr.
Info(KBytes) (%)

Partial Replication
Array
Total Size Incr.
Info(KBytes) (%)

Full Replication
Array
Total Size Incr.
Info(KBytes) (%)

hist

1 × (64 by 64)
3 × (64)

17.15— 2 × (64 by 64)
3 × (64)

33.56

95.5 2 × (64 by 64)
3 × (64)

33.56

95.5

bic

6 × (64 by 64)

98, 30— 7 × (64 by 64)

114.7

16.7 10 × (64 by 64)

163.8

66.7

lcd

2 × (64 by 64)

32.77— 3 × (64 by 64)

49.15

50.0 4 × (64 by 64)

65.54

100.0

Table 2. Space requirements results.

manipulates a larger number of arrays that are not replicated, the percentage
increase of space requirements is much smaller.
4.3

Discussion

These preliminary results indicate that the execution overhead of updating arraycopies can be negligible, allowing full exploitation of the concurrent execution
performance beneﬁts. The results also reveal that memory contention, even witha small number of concurrent tasks can be substantial. In this scenario, the fully
replicated variation allows for the elimination of memory contention, and further
improve execution performance. Overall fully replicated code versions achieve
speedups between 1.4 and 2.1 with a maximum increase in memory usage by afactor of 2.
Although there are other execution techniques, such as pipelining, theseresults reveal that using replication techniques a compiler can eliminate antidependences enabling substantial increases in execution speed at modest increases in memory space requirements. This experience reveals that replication
can be a valuable technique for parallel performance when memory space is not
at a premium.

5

Related WorkIn this section we discuss related work in the areas of array data-ﬂow analysis,
privatization, storage reuse and replication.
Array Privatization/Renaming and Data-flow Analysis Array privatization determines that a variable assigned within the loop is used only in thesame iteration in which it is assigned [4, 6]. Renaming is designed to allow for
concurrent operations that have output and anti-dependences but where there
is no ﬂow of values between statements of a loop nest. It has been used mainly
for scalar variables as for arrays the additional memory costs make it very unproﬁtable for traditional high-end architectures. Array data-ﬂow analysis [3, 10]focuses on data dependence analysis that is used to determine the privatization
requirements as well as the conditions for parallelization.

13

Replication for Shared Memory Multiprocessor Systems Many compilers targeting shared memory systems replicate data to enable concurrent readaccesses [1] and further [8] investigates adaptive replication in order to reduce
synchronization overheads that may ultimately degrade performance.
Memory Parallelism There have been many approaches to improve memory
parallelism. In particular, for FPGAs, [9] introduces a novel data and code transformation called custom data layout. After applying scalar replacement to reduce
the number of memory accesses, this transformation is applied to partition theremaining array accesses across available memories.
The approach described in this paper diﬀers from these eﬀorts in many respects. First, and unlike traditional privatization analyses, we relax the conditions for privatization allowing anti-dependences both within the same iteration
as well as across iterations of the control loop. Array renaming is the technique used in our ﬁrst transformation to expose concurrency across multiple
loop nests[2]. We augment this transformation with replication (or copying) toincrease the memory bandwidth and hence eliminate contention. Despite thesimilarities our combined renaming and replication transformations allow forvalues to ﬂow across iterations of the control loop whereas simple renaming has
been used within the same loop nest. Second, data layout techniques typicallywork in combination with loop-based transformations such as loop unrolling toexpose more parallel accesses when the unrolled body reveals references withdata access patterns that are disjoint in space. The transformations describedhere are clearly orthogonal to these two approaches. Lastly, the approach described here is geared towards non-perfectly nested loops where an outermost
control loop or loops need to be executed sequentially due to true loop-carried
dependences but each loop nested within can execute concurrently.
The approach described here takes advantage of the fact that conﬁgurable
architectures can mitigate several sources of replication overhead typically notpossible in traditional computing architectures. First, the number and connectivity of memory units can be tailored to the exact number of array copies.
Second, the spatial nature of the execution in conﬁgurable architecture allows
the execution of the copy/update operations without substantially instruction
overhead. Furthermore it is possible to perform a single write operation to multiple memories simultaneously thereby updating more than one array copy.

6

Conclusion

Conﬁgurable architectures oﬀer the potential for customized storage structures.
This ﬂexibility enables the application of low overhead data replication and privatization techniques to mitigate or even eliminate memory contention issues in
concurrent loop execution where shared data are accessed. In this paper we havepresented a simple array data-ﬂow analysis algorithm to uncover the opportunities for array replication and temporary privatization in computations expressed
as non-perfectly nested loops. The experimental results, for a set of kernels targeted to commercially available FPGA devices, reveal that a modest increase in14storage for private and replicated data leads to hardware designs that exhibit
small speedups. These results make this approach feasible when chip capacity
for data storage is available.

References
1. F. Allen, M. Burke, R. Cytron, J. Ferrante, W. Hsieh, and V. Sarkar. A Frameworkfor Determining Useful Parallelism. In Proc. Intl. Conf. Supercomputing, ACM,
pages 207–215, 1988.
2. R. Allen and K. Kennedy. Automatic Translation of Fortran Programs to Vector
Form. 9(4):491–542, 1987.
3. V. Balasundaram and K. Kennedy. A technique for summarizing data access andits use in parallelism enhancing transformations. In Proc. ACM Conf. Programming
Languages Design and Implementation, pages 41–53, 1989.
4. R. Eigenmann, J. Hoeﬂinger, Z. Li, and D. Padua. Experience in the AutomaticParallelization of four Perfect Benchmark Programs. In Proc. 4th Workshop
Languages and Compilers for Parallel Computing, LNCS. Springer-Verlag, 1991.
5. S. Goldstein, H. Schmit, M. Moe, M. Budiu, S. Cadambi, R. Taylor, and R. Laufer.
PipeRench: a coprocessor for streaming multimedia acceleration. In Proc. 26th Intl.
Symp. Comp. Arch., pages 28–39, 1999.
6. Z. Li. Array privatization for parallel execution of loops. In Proc. ACM Intl. Conf.
Supercomputing, 1992.
7. Mentor Graphics Inc. MonetTM , 1999.
8. M. Rinard and P. Diniz. Eliminating Synchronization Bottlenecks in object-based
Programs using Adaptive Replication. In Proc. Intl. Conf. Supercomputing, ACM,
pages 83–92, 1999.
9. B. So, M. Hall, and H. Ziegler. Custom Data Layout for Memory Parallelism. In
Proc. Intl. Symp. Code Gen. Opt., pages 291–302, March 2004.
10. C.-W. Tseng. Compiler optimizations for eliminating barrier synchronization. In
Proc. Fifth Symp. Principles and Practice of Parallel Programming, volume 30(8)of ACM SIGPLAN Notices, pages 144–155, 1995.
11. P. Tu and D. Padua. Automatic Array Privatization. In Proc. 6th Workshop
Languages and Compilers for Parallel Computing, LNCS. Springer-Verlag, 1993.
12. Xilinx Inc. Virtex-II ProTM Platform FPGAs: introduction and overview, DS0831(v2.4.1) edition, March 2003.
13. H. Ziegler, M. Hall, and P. Diniz. Compiler-generated Communication for Pipelined
FPGA applications. In Proc. 40th Design Automation Conference, June 2003.