Efficient Address Generation for Affine Subscripts in Data-Parallel Programs.
Address generation for compiling programs, written in HPF, to executable SPMD code is an important and necessary phase in a parallelizing compiler. This paper presents an efficient compilation technique to generate the local memory access sequences for block-cyclically distributed array references with affine subscripts in data-parallel programs. For the memory accesses of an array reference with affine subscript within a two-nested loop, there exist repetitive patterns both at the outer and inner loops. We use tables to record the memory accesses of repetitive patterns. According to these tables, a new start-computation algorithm is proposed to compute the starting elements on a processor for each outer loop iteration. The complexities of the table constructions are O(k+s2), where k is the distribution block size and s2 is the access stride for the inner loop. After tables are constructed, generating each starting element for each outer loop iteration can run in O(1) time. Moreover, we also show that the repetitive iterations for outer loop are Pk/gcd(Pk,s1), where P is the number of processors and s1 is the access stride for the outer loop. Therefore, the total complexity to generate the local memory access sequences for a block-cyclically distributed array with affine subscript in a two-nested loop is O(Pk/gcd(Pk,s1)+k+s2).
Introduction
Generally speaking, data-parallel languages support
three regular data distributions: block, cyclic, and
block-cyclic data distributions. The block distribution
is to distribute contiguous array elements evenly
onto processors. The cyclic distribution is to distribute
each array element onto processors one at a
time and in a round-robin fashion. The distribution
that blocks of size k are distributed onto processors
in a round-robin fashion is the block-cyclic
distribution and is denoted as cyclic(k). The block-cyclic
distribution is known to be the most general
data distribution. The block and cyclic distributions
can be represented by the block-cyclic distribution as
cyclic(d NA
e) and cyclic(1), respectively, where NA is
the number of array elements and P is the number
of processors.
The address generation problems for compiling
array references with block or cyclic distributions have
been studied thoroughly [5, 12, 13, 21]. The more
general problems for compiling array references with
block-cyclic distribution also have been studied extensively
[3, 7, 9, 11, 11, 14, 16, 19, 20, 22]. A finite
state machine (FSM) approach is proposed to traverse
the local memory access sequence of each processor
[3]. The method is a table-based approach.
The table construction needs to solve k linear Diophantine
equations and incurs a sorting operation.
The work improving the FSM approach [3] is proposed
in [10, 11, 20]. Efficient FSM table generation
is proposed. The improved work enumerates the local
memory access sequences by viewing the accessed
elements an integer lattice. The sorting step in [3]
is avoided in the improved work. In [7], the authors
use the virtual processors to generate communication
sets for each processor. From different viewpoint
of a block-cyclic distribution, the virtual processor
approach actually contains two approaches, one is
termed the virtual block approach and the other is
termed the virtual cyclic approach. The virtual block
approach views a block-cyclic distribution as a block
distribution on a set of virtual processors, which are
then cyclically mapped to processors. On the con-
trary, the virtual cyclic approach views a block-cyclic
distribution as a cyclic distribution on a set of virtual
processors, which are then block-wise mapped
to processors. The other approaches are similar to
either FSM approach or virtual processor approach
except some modifications. However, most of them
consider the simple array subscript. That is, the array
subscripts contain only one induction variable.
Recently, several efforts on compiling array references
with affine array subscripts are proposed [1,
10, 11, 15, 17, 22]. Affine array subscript means the
array subscript is a linear combination of multiple
induction variables (MIVs). In [1], the authors use
a linear algebra framework to generate communication
sets for affine array subscripts. Complex loop
bounds and local array subscripts of the generated
code will incur significant overhead. A table-based
approach is proposed in [22]. The authors classify
all blocks into classes and use a class table to record
the memory accesses of the first repetitive pattern.
By using the class table, they derived the communication
sets for each processor. Both [1] and [22] are
addressing the compilation of array references with
affine subscripts within a multi-nested loop. How-
ever, the proposed methods are not efficient enough
for dealing with some special case.
For compiling array references with affine sub-
scripts, some researchers pay their attention on the
array reference enclosed within a two-nested loop
to find a better result [10, 11, 17]. Based on FSM
approach [3], Kennedy et al. proposed another approach
to solving the compilation of array references
with affine subscripts within a two-nested loop [10,
11]. For the memory accesses of an array reference
with affine subscript within a two-nested loop, there
exist repetitive patterns both at the outer and inner
loops. Moreover, to fix each iteration of the
outer loop, the affine subscript is reduced to a simple
subscript. Therefore, for each iteration in the outer
repetitive pattern, they use FSM approach to generate
the local memory access sequences for the inner
loop. To use FSM approach at the inner loop, start-
computations to decide the initial state of FSM for
each iteration of the outer loop are necessary. They
proposed an O(Pk) algorithm for a start-computation,
where P is the number of processors and k is the
distribution block size. For the outer loop, they
found that the repetitive iterations are Pk iterations.
Hence, the total complexity to generate the local
memory access sequence for an array reference with
affine subscript within a two-nested loop is O(P
Ramanujam et al. proposed an improved work to
find the local starting elements on each processor
[17]. They first find a factor of basis vectors to jump
from a global start to a processor's space and then
traverse the lattice until hitting the starting element.
ENDDO
ENDDO
Fig. 1: HPF-like program model considered in the
paper.
Since a traverse step is incurred, the complexity of
their start-computation algorithm is O(k). Thus the
total complexity of Ramanujam's algorithm is turned
out to be O(Pk 2 ).
In this paper, we also propose another new start-
computation algorithm. A preprocessing step is required
before we compute the starting elements. The
complexity of the preprocessing step is O(k
where s 2 is the access stride for the inner loop. After
preprocessing is done, the time complexity to generate
each starting element on a processor is O(1).
In addition, we also discover that the outer loop
repetitive iterations are Pk= gcd(Pk; s 1 ) instead of
Pk, where s 1 is the access stride for the outer loop.
Therefore, the total complexity of our proposed approach
is O(Pk= gcd(Pk; s 1
which is asymptotical
to O(Pk). The proposed approach is not only
correct but also efficient.
The paper is organized as follows. Section 2 formulates
the problem and describes the traditionally
techniques to generate local memory access sequences
for compiling the array references with affine subscripts
within a two-nested loop. An efficient approach
to finding the starting elements from a global
start is proposed in Section 3. The performance
analyses and comparisons with the related work are
demonstrated in Section 4. Section 5 concludes the
paper.
Address Generation for Affine
Subscripts
2.1 Problem Formulation
Specifically, Fig. 1 illustrates the program model considered
in the paper. Array A is distributed onto
processors with cyclic(k) distribution. The array
reference contains two induction variables i 1 and i 2 .
The access strides of the array reference with respect
to i 1 and i 2 are s 1 and s 2 , respectively. The access
offset of the array reference is o. Fig. 2 is an example
of the program model shown in Fig. 1, where
Fig. 2(a) is the
layout of array elements on processors. The colored
elements are the array elements accessed by the array
reference in the two-nested loop. Fig. 2(b) shows
the global addresses of array elements accessed by
every processor. However, data distribution transfers
the global addressing space to processors' local
spaces. Therefore, what we care is to generate the
local addresses on a processor for the accessed ele-
ments. Thus the MIV address generation problem
is to generate the local addresses of array elements
accessed by each processor, just like Fig. 2(c) shows.
2.2

Table

-Based Address Generation
for Affine Subscripts
For the case of the array reference containing single
induction variable (SIV), as well-known, the memory
accesses on processors have a repetitive pattern. In
[3], a finite state machine (FSM) is built to orderly
iterate the local memory access sequence on a pro-
cessor. Similarly, for the array reference containing
multiple induction variables (MIVs), we can extend
the technique used for SIV to orderly enumerate the
local memory access sequences on a processor.
Consider the program model shown in Fig. 1.
For each outer iteration, the MIV address generation
problem can be reduced to an SIV problem. Thus we
can utilize the FSM approach to generate the local
memory access sequence for an SIV problem. Generating
the local memory access sequence for an MIV
problem can, therefore, be easily solved by enumerating
the sequence for each outer loop iteration until
reaching the outer loop bound. For example, consider
the example illustrated in Fig. 2. Suppose the
outer loop iteration i 1
0. The two-nested loop is
reduced to a single nested loop and the array reference
turns out to be A(2i 2
). Thus a finite state
machine (FSM) can be built to enumerate the local
memory access sequences for the SIV problem. Fig. 3
illustrates the FSM to generate the local memory access
sequences when the array reference contains a
single induction variable and the access stride is 2.
Fig. 3(a) shows the FSM table, where Next records
the next transition state and \DeltaM records the local
memory gaps of successive array elements from current
state transmitting to the next state. Fig. 3(b)
is the transition diagram of the FSM.
The initial state of the FSM depends on the position
of the starting array element in a block on the
processor. For instance, when the starting
element on processor p 0 is 0 and its position in a
(a)
(b)
(c)
Fig. 2: An MIV address generation example, where
Layout of array elements on processors. (b). Global
addresses of array elements accessed by every proces-
sor. (c). Local addresses of array elements accessed
by every processor.
State Next \DeltaM
(a)
(b)
Fig. 3: A finite state machine (FSM) to generate the
local memory access sequences for an SIV problem
with access stride 2.
block is 0, thus the initial state of the FSM for the
case when i 1
0 is at state 0. In addition to the
initial state of the FSM, we also need to know the
local address of the starting element since FSM only
records the local memory gaps between successive array
elements allocated on the processor. FSM has no
enough information to show where to start in terms
of local address. In other words, although we have
the FSM and its initial state, we still do not know
the starting local address in this case. For exam-
ple, besides the initial state of the FSM being state
0 that we should know, we have to figure out the local
address of the starting element. Obviously, when
the local address of the starting element 0 on
processor p 0 is 0. Therefore, when the local
memory access sequence for processor p 0 is 0; 2; 4;
and so on.
Likewise, if the two-nested loop is reduced
to a single nested loop and the array reference is
simplified to 37). The finite state machine
built for the case of i 1
can still be reused since
the memory access stride is still the same (2, for this
example). When i 1
1, the starting element on
processor
is 49 and its position in a block is 1.
Thus the initial state of the FSM for the case of i 1
1 is at state 1. However, where to start in terms
of local address is the key point now. When i 1
1, the starting element on processor p 0
is
its local address on processor p 0
is 13. Therefore,
the local memory access sequence for processor p 0
is 13; 15; and so on. Similarly, it is done likewise
when the outer loop iteration
Accordingly, we can obtain the local memory access
sequences on processors as Fig. 2(c) shows.
Actually, there is no need to iterate all of the
outer loop iterations from 0 to n 1 . We have found out
that iterating the outer loop iterations Pk= gcd(Pk; s 1
times is enough because there is a repetitive pattern
in the outer loop. Having this discovery can save a
lot of time due to the avoidance of recomputation for
repetitive patterns. The following theorem demonstrates
that the repetitive period of the outer loop
is Pk= gcd(Pk; s 1
iterations. Since the space is lim-
ited, the proof of the theorem is omitted in the paper.
One can refer to [18] for more details.
Theorem 1 For the program model shown in Fig. 1,
the memory accesses of the array reference have a
repetitive pattern and the repetitive period in respect
of the outer loop iteration is Pk= gcd(Pk; s 1
tions. 2
According to the above description, evidently, determining
the local address of the starting element
for each outer loop iteration is the primary step to
solve the MIV address generation problem. The problem
to find the local address of starting element for
each outer loop iteration will be described in the next
section. A new approach to generating the local addresses
of the starting elements will be presented in
the next section as well.
Generating Starting Elements
The findings of the starting elements for outer loop
iterations are important for solving the MIV address
generation problem. It is obvious that for a given
outer loop iteration the memory accesses just depend
on the inner loop access stride s 2 . Therefore, in this
section, we use s to indicate the inner loop access
stride s 2 except otherwise notified. The method to
find the starting elements in case of s - k can be
found in [10, 17]. Both of them are O(1) in com-
plexity. However, their methods to find the starting
elements in case of s ? k are O(Pk) and O(k), re-
spectively. We propose a new approach to find the
starting elements in case of s ? k and the time complexity
of the algorithm is O(1). The problem and
its solution are described as follows.
3.1 Problem Description
We have given an overall description of the MIV address
generation problem in Section 2.2. Finding the
starting element on a processor from a given outer
loop iteration plays an important role in dealing with
the MIV address generation problem. The following
we formally describe the induced problem. Let the
accessed element for some fixed outer loop iteration
(a) (b)
Fig. 4: Starting elements on every processor for the
example shown in Fig. 2. (a). Global addresses of
starting elements on every processor. (b). Local addresses
of starting elements on every processor.
be a global start and G be the local address of the
global start. Specifically, given a global start G, the
processor p on which G is allocated and the processor
q which we would like to find its starting element,
the problem is to figure out S q , the local address of
the starting element, for processor q. For example,
consider the example shown in Fig. 2(a). The gray
colored elements are the elements accessed by the
array reference, in which the deep-colored shaded elements
are the global starts corresponding to every
outer loop iterations and the light-colored shaded elements
on each processor are the starting elements
corresponding to every global starts. Suppose a given
global start is 37, which local address is 9 on processor
. The starting elements on processors p 0 ,
and p 3 are 49, 41, and 45, respectively, in terms of
global addresses. The problem is to figure out the
local addresses of these starting elements. That is,
13, 9, and 9, respectively. The starting elements for
every outer loop iteration are shown in Fig. 4. The
global and local addresses of the starting elements
on every processor are listed in Figs. 4(a) and 4(b),
respectively. The goal of the induced problem is to
obtain a table containing the local addresses of the
starting elements on some required processor for every
global start, as Fig. 4(b) shows for that required
processor.
3.2 Preprocessing
Given a global start G, we propose a new approach
to find the local address of the starting element S q
for processor q in case of s ? k. The proposed approach
is a table-based approach. In our approach,
it is necessary to pre-compute a few tables in order
to evaluate the starting elements for a given global
start. In this section, we only describe the character-
Fig. 5: An one-level mapping example to illustrate
the ideas of the tables used in the paper, where it
assumes that array elements are distributed over 4
processors with cyclic(4) distribution and the access
stride is 5.
istics of these tables and how it works in the proposed
approach. The complexities in time and space will
be analyzed in Section 4. For the sake of space limi-
tation, the constructions of the tables are omitted in
the paper. For further details, please refer to [18].
3.2.1 C2P, P2C, and Offset Tables
As well-known, the accessed elements on blocks have
a repetitive pattern. By [22], all blocks can be classified
into s
classes according to the positions of
the accessed elements on a block. Note that blocks
of the same class have the same format. All blocks
can be numbered in terms of class according to the
rule: b mod s
, where b is the block number
of that block. A repetitive pattern contains blocks
from class 0 to class s
1 and which is termed
a class cycle in [22]. In addition, since s ? k, there is
at most one accessed element on a block. Therefore,
we can use a table to record the position of the only
accessed element for every class. Different from [22],
we assume that the accessed element on the block of
class 0 is at the first position, that is, at position 0.
The blocks with no accessed element are recorded by
"-". With the table we can easily and efficiently get
the position of an accessed element on a block if the
class number of the block is given. Therefore, we can
easily deduce S q from G since all blocks have been
classified into classes. We denote the table recording
the position of the accessed element on every class
as C2P table.
As an example, let us suppose that array elements
are distributed over 4 processors with cyclic(4) distribution
and the access stride is 5. The layout of array
elements on processors is illustrated in Fig. 5. In
this figure, the accessed elements are those elements
with a white text on a black background. Obviously,
all blocks are classified into 5 classes. Each class is
colored by the gradations of gray color. The class
number of a block is labeled at the bottom of the
block. The blocks bounded by a dashed line indicate
a repetitive pattern. The accessed elements on class
are at positions 0, 1, 2, and 3, respec-
tively. Therefore, the values of C2P(0), (1), (2), and
(3) are 0, 1, 2, and 3, respectively. Moreover, there
is no accessed element in class 4. So, C2P(4)="-
". Thus we can obtain the C2P table. Fig. 7(a)
illustrates the C2P table for the example shown in
Fig. 5.
We can get the position of an accessed element
on a block according to the class number of a block
by using C2P table. In contrast to C2P table, a
P2C table is to record the class number according
to the position of accessed element on a block. Thus
we can obtain the class number of a block according
to the position of the accessed element on the block.
Generally speaking, we can obtain the class number
of a block according to the position of the accesses
element on the block by using C2P table. However,
it requires a search operation and, in some cases, we
can not recognize the class number of a block according
to the C2P table. For instance, when the number
of classes is smaller than the block size, it is possible
that, for some position, there is no class that its
accessed element is at that position. It would cause
confusion to recognize the class number by that posi-
tion. Therefore, P2C table is necessary. P2C table
can be constructed by C2P table. For example, considering
C2P table shown in Fig. 7(a), one can scan
the table to obtain P2C table. P2C table is illustrated
in Fig. 7(b). Note that, for the above case
that the number of classes is smaller than the block
size, for the position that has no class number to
correspond to, we assume the class number of that
position to be the class number of the previous po-
sition. For example, suppose that the distribution
block size is 4 and the access stride is 6. All blocks
can be classified into 3 classes. The accessed elements
on class 0, 1, and 2 are at the positions of
0, 2, and -, respectively. As a result, positions at 0
and 2 are corresponding to the classes 0 and 1, re-
spectively. We have P2C=(0, -, 1, -). Obviously,
positions at 1 and 3 have no suitable class numbers
to correspond to. With the above assumption, the
class number corresponded by position 1 is 0, the
same as that of the previous position. Similarly, the
class number corresponded by position 3 is 1. Thus,
we have P2C=(0, 0, 1, 1). Basically, C2P and P2C
tables are in some sense like a hash table.
The reason to make the above assumption for
P2C table construction is to solve the offset prob-
lem. The offset problem can be solved by the assumption
in conjunction with another table Offset.
Generally speaking, a global start G can be at any
position in a block. However, as constructing C2P
table, we have assumed that the accessed element on
the block of class 0 should be at position 0, Further-
more, as we construct P2C table, for the position
that has no class number to correspond to, we assign
the class number of the previous value to the current
value. Nevertheless, according to C2P table,
the class number has its real position to correspond
to. Consequently, there is a difference between the
real position and the assumed position if we make
such an assumption. In order to make use of C2P
table in every case, we use another table to record
the difference in order to make up the shortcomings
of C2P table. The table is denoted asOffset table
in the paper.
It has been discussed that when the number of
classes is larger than the block size, each position has
its suitable class number to correspond to. In such a
case, Offset table is of no use. Fig. 5 is an example
under such a condition and the Offset table is
shown in Fig. 7(c). On the other hand, if the number
of classes is smaller than the block size, Follow
the example used in the explanation of P2C table, in
which it assumes that the distribution block size is 4
and the access stride is 6. The C2P and P2C tables
are (0, 2, -) and (0, 0, 1, 1), respectively. Since position
1 has no suitable class number to correspond to,
we assign the class number corresponded by position
0 to position 1. Although, position 1 correspond to
class 0, the real position of accessed element on the
block of class 0 is at position 0 according to C2P ta-
ble. Thus there is a 1 difference between the assumed
value and the real value. As a result, Offset(1)=1.
Similarly, Offset(3)=1. There is no problem on
positions 0 and 2 since they have their suitable class
numbers to correspond to. Consequently, Offset
table is (0, 1, 0, 1).
3.2.2 NextActive and Jump Tables
As previously described, a block contains at most
one accessed element when the access stride is larger
than the block size. Of course, a block may contain
no accessed element at all in such a case. Thus, we
name a block that has elements to be accessed as an
active block; otherwise, it is termed an empty block.
The tables NextAct and Jump that we would like
to introduced are used for jumping over the empty
(a) (b)
Fig. (a) A one group ordered sequence. (b) A
multiple groups ordered sequence.
blocks to an active block. One important observation
here is that, from processor's viewpoint, blocks
on processors have a repetitive pattern in terms of
classes. To explain concretely, let us take a look at
the example shown in Fig. 5. The blocks on processor
are in classes 0, 4, 3, 2, 1, and then repeat
again from class 0. Similar situation also happens
on processors . The sequence of class
numbers on p 1
is 1, 0, 4, 3, 2, and that for p 2
is 2, 1,
0, 4, 3, and that for p 3
is 3, 2, 1, 0, 4. It is interesting
that the sequence of class numbers on each processor
is the same except the initial class number on each
processor. That is, the sequence of class numbers on
each processor can be viewed as the sequence 0, 4,
and the initial class numbers for p 0
and p 3
are 0, 1, 2, and 3, respectively. We use the
notation (0; 4; 3; 2; 1) to denote the ordered sequence.
Clearly, all class numbers have appeared in the ordered
sequence. Thus, we say that there is only one
group in the ordered sequence. Fig. 6(a) illustrates
the one group ordered sequence for this example.
It should be addressed that it is possible that
the sequence of class numbers on each processor may
be different and there may be more than one group
in an ordered sequence. However, groups are mutually
disjoint and a processor can belong to one and
only one group. We give an example to illustrate
the phenomenon. Suppose that array elements are
distributed over 2 processors with cyclic(3) distribution
and the access stride is 12. There are 4 classes
for this example. The sequence of class numbers on
2. and that on p 1 is 1, 3. The ordered sequence
can be represented as (0; 2)(1; 3). Obviously,
the ordered sequence contains two groups. One is
(0; 2) and another is (1; 3). (0; 2) and (1; are mutually
disjoint. Processor p 0
belongs to the group
(0;
belongs to the group (1; 3). Fig. 6(b)
illustrates the multiple groups ordered sequence for
(a)
(c) Offset
(d) NextAct
Fig. 7: Tables used for starting elements findings.
this example.
It is important to have such a discovery since we
can obtain the class number of the next block on a
processor from current block if the class number of
the current block is known. Based on the discovery,
we use one table to record the class number of the
next active block from current block on a processor
and another to record how many empty blocks we
need to skip over. They are named NextAct and
Jump, respectively. The constructions of the two
tables are based on the ordered sequence and C2P
table. If current block is not an empty block, we need
not to jump any block. Thus, the value in NextAct
table for that block is recorded by its class number
and that in Jump table is recorded by 0. Otherwise,
we can traverse the ordered sequence to find an active
block. Then the value in NextAct table for
that block is recorded by the class number of the active
block and that in Jump table is recorded by the
number of blocks that we have traversed. If we can
not find an active block, both the values in Nex-
tAct and Jump tables are recorded by "-". Such
as the example where array elements are distributed
over 4 processors with cyclic(4) distribution and the
access stride is 8, the NextAct and Jump tables are
(0, -) and (0, -), respectively. Although a processor
can belong to one and only one group, NextAct
table is suitable for all processors since the construction
of the table is based on the class number, not
on group. The NextAct and Jump tables for the
example shown in Fig. 5 are illustrated in Fig. 7(d)
and (e), respectively.
3.3 The Algorithm
With these tables we can evaluate the starting element
from a given global start in O(1) time complex-
ity. Fig. 8 illustrates the algorithm to evaluate the
starting element from a given global start. We term
the algorithm Start Computation algorithm. The
basic concept of the Start Computation algorithm
Algorithm: Start Computation algorithm for the
case of s ? k.
Input: G, a global start,
p, the processor where the global start is
allocated,
q, the processor that we would like to find
its starting element, where q 6= p
k, the distribution block size,
P , the number of processors,
s, the access stride,
C, the number of classes, where
C2P, P2C, Offset, NextAct, and
Jump tables.
Output: S q , the starting element on processor q.
Steps:
1. pos
2. dist
3.
4. pos
5. if pos
7. return no starting element on q
8. else pos
Jump(c)\Lambdak
9. endif
10. endif
12. if q ! p then
13.
14. endif
16. return S q
Fig. 8: Start Computation algorithm for the case of
is that, from the viewpoint of the global start, we
try to figure out the distance between the starting
element and the global start. With the distance we
can, therefore, get the local address of the starting
element by adding the distance to the local address
of the global start. The details of the algorithm is
described as follows.
Given G, the local address of a global start, and
where G is allocated, Step 1 is to calculate the
position on a block for the global start. The obtained
value is stored in pos g . Step 2 is to measure the
distance between processors p and q, which is then
stored in dist. In Step 3, P2C(pos g ) can obtain the
class number of the block which the global start is
on. Thus, Step 3 can get the class number of the
block on processor q, which may contain the starting
element. The class number obtained in Step 3 is
represented by c. According to C2P table, C2P(c)
can get the position of the accessed element on the
block of class c, if ever. Therefore, Step 4 can obtain
the position on a block for the starting element on
processor q. The obtained position is represented by
pos s . If pos s does not equal "-", it means that there
is an accessed element on the block. Of course, the
accessed element is the starting element. We can go
direct to Step 11 to evaluate the distance between
the starting element and the global start. If q ! p,
we still need to add a size of a block to the distance
since the starting element must be at one more course
than the global start. That is what Steps 12-14 has
done. As a result, the local address of the starting
element can be obtained, just as Step 15 shows.
On the other hand, if pos means that
there has no accessed element on the block. We can
use NextAct table to obtain the class number of the
next active block. If NextAct(c) = "-", it implies
that there exists no active block on the processor.
Certainly, there is no starting element on the pro-
cessor. Otherwise, which means that we can find an
active block on the processor, we can get the number
of blocks required to jump from the current block
to the next active block and the position of the accessed
element on the active block from Jump and
NextAct tables, respectively. Since pos s in Step
4 represents the position of the starting element on
the block with the same course as the global start,
hence, the distance caused by the number of blocks
required to jump to an active block should be added
to pos s in such a case. Thus, we have Step 8. Steps
after 11 are the same as explained in the previous
paragraph.
Let us take Fig. 9 as an example, where it assumes
that
Given an global start 37, whose local address is 9 on
processor we first to find the starting element for
processor . The input of the Start Computation
algorithm is
. The
tables used for the example are the same as shown
in Fig. 7. Following the Steps from 1 to 4 in the
algorithm we can obtain that pos
2. Since pos s does not equal "-",
we go direct to Step 11 and we obtain that offset =
1. Due to the invalidation of the condition in Step
12, we go direct to Step 15 and we have S 2
which corresponds to the array element 42 in terms
of global address.
On the same input except we take the
finding of the starting element on processor p 0
as
Fig. 9: Layout of array elements on processors for the
case of s 2 ? k, another MIV example, where
another example. After executing the Step 4, we
have pos 4, and pos
Since pos s equals "-", which means that the block
contains no accessed element, we go to Step 6. According
to NextAct and Jump tables, there is an
active block at one block after the empty block on
processor p 0 . By Step 8, we have pos 7. After
Step 11, we have offset = 6. As
needs to add 4, the size of a block. It turns out that
which corresponds to
the array element 67 in terms of global address.
Evidently, the time complexity of Start Computation
algorithm is O(1). The complexity analyses
of the tables used in the algorithm and the performance
comparisons against the existing methods will
be discussed in Section 4.
Performance Analyses and
Comparisons
Performance analyses of the tables used in Start Computation
algorithm are shown in Table 1. Performance
comparisons of our method against the existing
methods are shown in Table 2. For the sake of
space limitation, please refer to [18] for more details.
Conclusions
In this paper, we have presented an efficient approach
to the evaluation of the starting element for some
processor from a given global start, which is a key
step to solve the MIV address generation problem

Table

1: Performance Analyses.

Table

Complexity
Time Space
Offset
NextAct O(C) C

Table

2: Performance Comparisons.
[10]'s [17]'s Ours
start comp. O(1) O(1) O(1)
preprocess O(1) O(1) O(s 2
start comp. O(Pk) O(k) O(1)
outer loop
repetitive Pk Pk Pk
iterations
Total
in data-parallel programs, assuming array is block-
cyclically distributed and its subscript is affine. The
approach is a table-based approach. The constructions
of these tables require O(s
plexity, where s 2 is the access stride of the inner loop.
With these tables, the Start Computation algorithm
can run in O(1) time. In addition, we have discovered
that there exists a repetitive pattern for every
iterations. Therefore, the
MIV address generation problem can be solved in
is the
access stride of the outer loop.
In the future, we would like to apply the address
generation approach to evaluate communication sets.
Furthermore, the address generation and communication
sets evaluation for general affine subscripts are
also under investigation.



--R

A linear algebra framework for static HPF code distribution.
Programming in Vienna Fortran.
Generating local addresses and communication sets for data parallel programs.

Automatic Parallelization for Distributed-Memory Multiprocessing Systems
Concrete Mathematics.
On compiling array expressions for efficient execution on distributed-memory machines
High Performance Fortran Forum.

Efficient address generation for block-cyclic distri- butions
A linear-time algorithm for computing the memory access sequence in data-parallel programs

Compiling global name-space parallel loops for distributed execu- tion
Local iteration set computation for block-cyclic distributions
Computing the local iteration set of a block-cyclically distributed reference with affine subscripts
Optimizing the representation of local iteration sets and access sequences for block-cyclic distributions
Code generation for complex subscripts in data-parallel programs

Generating communication for array state- ments: Design
Efficient computation of address sequences in data parallel programs using closed forms for basis vectors.
An Optimizing Fortran D Compiler for MIMD Distributed-Memory Machines
Compiling array references with affine functions for data-parallel programs
--TR
Concrete mathematics: a foundation for computer science
Compile-time generation of regular communications patterns
Vienna FortranMYAMPERSANDmdash;a Fortran language extension for distributed memory multiprocessors
The high performance Fortran handbook
Generating communication for array statements
Compilation techniques for block-cyclic distributions
An optimizing Fortran D compiler for MIMD distributed-memory machines
Generating local addresses and communication sets for data-parallel programs
A linear-time algorithm for computing the memory access sequence in data-parallel programs
Efficient address generation for block-cyclic distributions
Compiling array expressions for efficient execution on distributed-memory machines
Efficient computation of address sequences in data parallel programs using closed forms for basis vectors
An Empirical Study of Fortran Programs for Parallelizing Compilers
Compiling Global Name-Space Parallel Loops for Distributed Execution
Code Generation for Complex Subscripts in Data-Parallel Programs
affine subscripts;data-parallel languages;data distribution;address generation;multiple induction variables MIVs;distributed-memory multicomputers;single program multiple data SPMD