Array Replication to Increase Parallelism
in Applications Mapped to Configurable
Architectures
Heidi Ziegler, Priyadarshini Malusare, and Pedro Diniz
University of Southern California / Information Sciences Institute4676 Admiralty Way, Suite 1001
Marina del Rey, CA 90292, USA{ziegler,priya,pedro}@isi.edu*This work was partly funded by the National Science Foundation (NSF) under award
number CCR-0209228 and NGS-0204040. Heidi Ziegler is also supported by Intel andthe Boeing Company.

USC

INFORMATIONSCIENCES
INSTITUTE1

Motivation• Emerging architectures have configurable memories– Number, size, interconnect• Opportunities– Large on-chip storage area for data
– Large on-chip read and write bandwidth– Relatively low cost to replicate and copy data

• How we make use of these features?
Configurable memory
S-RAM
D-RAM

CPU

S-RAM
D-RAM

CPU

S-RAM
D-RAM

CPU

S-RAM
D-RAM

CPU

Configurable logic

2

Basic Ideas• Expose concurrency between
loop nests

L1– Replicate arrays to eliminate antiand output-dependences– Add synchronization– Add update logic

L2MemL3• Eliminate memory contention– Replicate arrays– Add synchronization– Add update logic

L1L2L3Mem3

Dependence Definitions
Execution OrderReadWriteL1AL2de anpe tin
W denAR cTimeL3AeA
datadependence

access orderrow-wise

2-Darray4

Example Kernel• Start with all data mapped to the same memoryand sequential execution
MemoryLoop 1read

read

Loop 2

A[i-1][*]
A[ i ][*]

writeAnti
Loop 35

Exploiting Basic Data Independence• L1 and L2 can be parallelized• {L1, L2} and L3 can notMemoryfork
read

Loop 1Loop 2join

readA[i-1][*]
A[ i ][*]

write

Loop 3

6

Using Array Renaming• Create a local copy of array A in order toremove anti-dependence
Memoryforkread

Loop 1Loop 2Loop 3readA[i-1][*]
A[ i ][*]

writecopy

join

Copy

A_1[i-1][*]
A_1[ i ][*]

MemoryContention

7

Using Array Renaming & Replication
forkread

Loop 1Loop 2Loop 3read
write

MemoryMemoryMemoryA_1[i-1][*]
A_1[ i ][*]

A_2[i-1][*]
A_2[ i ][*]

A_3[i-1][*]
A_3[ i ][*]

joinCopy• No memory contention but more memory space• Care in updating copies across iterations of control loop8Mapping to a Configurable Architecture

S-RAM
D-RAM

CPU

A_1

L1

S-RAM
D-RAM

CPU

A_2

L2

S-RAM
D-RAM

CPU

S-RAM
D-RAM

CPU

A_3

L3

• Many on-chip Memories so that Each Array May
be accessed in Parallel• Replication Operation done by Writing toMemories in Tandem using the same Bus
9Array Data Access Descriptor

lb1 < d1 < ub1A
ni{ER, WR} =......

lbx < dx < ubx
Set describes basic data access information
niprogram point / loop nestAarray name
ER, WR exposed read or write array accesslb, ub
lower and upper bound of each dimension d1 … dx
accessed array section, integer linear inequalities
10Compiler Analysis: Data Dependence
Solve for data dependences
WriteReadB
L1

lb1 ! d1 ! ub1=lb 2 ! d 2 ! ub 2

BL2

lb1 ! d1 ! ub1=lb 2 ! d 2 ! u 21

WRL1BDa

De
p.

L2ta

De

pe

ndenceB

ER(data _ dependence ! f WRnBi , ERnBj)
11

Compiler Analysis: Outline• Outline:– Identify Control Loop• CFG with Coarse-grain task information– Extract Data Dependence Information• Exposed Read and Write Information• Array Section for Affine Array Accesses– Extract Parallel Regions• Using Array Renaming to Eliminate Anti-dependences– Identify Array Copies for Reduced Contention• Currently Replicate Write Arrays (partial replication)• Replicate All Write and Read Arrays (full replication)• Status:– Compiler Analysis Implemented in SUIF
– Code Generation and Translation to VHDL Still Manual
12Analysis Example13

Experimental Methodology• Goal– Evaluate Cost/Benefit of Array Renaming and Replication– Configurable logic device - field programmable gate array (FPGA)– Use of Many Memory Blocks for Array Storage• Synthetic Kernels– HIST: 3 loop nests; 3 arrays– BIC: 4 loop nests; 4 arrays (most array data)– LCD: 3 loop nests; 2 arrays• Methodology– Analyze using SUIF and Transform Benchmarks Manually– Loop level execution times and Memory Schedules from MonetTM– Simulate total execution times using loop level inputs– Manual Replication Transformation14

Execution Time Results
Original CodeKernel
Execution Cycles (simulation)- computation- update of replicas- total execution- stall due to memory contention- overall reduction (percentage)

Partial Replication

Full Replication(replication of written arrays)(replication of all arrays)

Fully replicated code
versions achieve speedups
between 1.4 and 2.115

Storage Requirement Results

KernelSpace Requirements- size in KBytes- increment

Fully replicated code
versions require storage
increase by a factor of 216

Discussion• Overhead of Updating Copies can be Negligible– Provided Enough Bandwidth for Updates– Small Number of Replicas• Memory Contention– Even with a Small Number of Arrays can be Substantial– Scheduling could Mitigate this Issue somewhat…

• Preliminary Results Reveal:– Removal of anti-dependences can enable substantial increases inexecution speed the cost of modest increase in storage– Increase in Space can be non-negligible if Initial Footprint is Small17

Related Work• Array Privatization– Eigenmann et al. LCPC 1991; Li ICS 1992; Tu et al. LCPC 1993

• Fine-grain Memory Parallelism– So et. al. CGO 2004

• Pipelining and Communication for FPGAs– Tseng PPoPP 1995; Ziegler et. al. DAC 2003

• This work:– Relaxes constraints on previous analyses• Loop Nests rather than Statements• Coarser-grain & Loop Carried Dependences– Combines the transformations to take advantage of configurable
architecture characteristics• such as many on-chip memories• low cost array replication

18

Conclusion• This paper:– Describes a Simple Loop Nests Analysis for Task-Level Parallelism• Uses Renaming and Replication to Eliminate Dependences• Across loop nests with selected replication strategies• Array Section Analysis to identify replication regions for each Array– Results target configurable architectures with• Many on-chip memories• Programmable Chip Routing– Results• Need to be Expanded to Larger Kernels• Respectable Speedups with Modest Space Increase.

19Thank You20