HPJava Home Page
PCRC Home Page
NPAC Home Page
Java Grande Home
|
Subarrays
A subarray is a section of a array, typically selected by some
combination of scalar and triplet subscripts.
A subarray is an object in its own right - its type is that of a suitable
multi-dimensional array. It describes some subset of the elements of
a parent array. The syntax for creating a subarray is modelled on the
Fortran syntax for creating regular sections, but the subscripts are
enclosed in double brackets. This distinguishes subarray construction
clearly from the simple subscripting operation introduced earlier. In
int [[]] e = a [[2, 2 : ]] ;
foo(b [[ : , 0, 1 : 10 : 2]]) ;
assume a is a two-dimensional array and b is a
three-dimensional array. e becomes an alias for the 3rd row
of elements of a. The method foo expects a
two-dimensional array as argument. It can read or write to the set of
elements of b selected by the section. Note that the
subscripts of e, like any other array, start at 0, although
the first element is identified with a[2, 2].
Subarray construction is a relatively complex operation. Besides
scalar integers and triplets, allowed subscripts include locations and
ranges. A location subscript must be a location in the range
associated with the relevant dimension of the array, and a range
subscript must be a subrange of the appropriate range of the array. By
definition, integer subscript n in dimension r of
array a is equivalent to location subscript
a.rng(r)[n], and triplet subscript l:u:s is
equivalent to range subscript a.rng(r)[l:u:s].
The mapping (distribution group and ranges) of a subarray
is determined as follows. Suppose all integer and triplet subscripts
are replaced by their equivalent location or range subscripts. If the
location subscripts are i, j, ... the distribution group of
the subarray is
a.grp() / i / j / ...
where a is the parent array. The s'th range of the
subarray is equal to the s'th range-valued subscript.
We can use subranges and subarrays to give a parallel implementation
Cholesky decomposition. In pseudocode the algorithm is
for k=1 to n-1
lkk = akk1/2
for s=k+1 to n
lsk=ask/lkk
for j=k+1 to n
for i=j to n
aij = aij - lik ljk
lnn = ann1/2
The HPJava parallel version is
Procs1 p = new Procs1(P) ;
on(p) {
Range x = new CyclicRange(N, p.dim(0));
float [[*,]] a = new float [[N, x]] ;
float [[*]] b = new float [[N]] ;
... some code to initialise `a' ...
for(int k = 0 ; k < N - 1 ; k++) {
at(l = x[k]) {
float d = Math.sqrt(a[k, l]) ;
a[k, l] = d ;
for(int s = k + 1 ; s < N ; s++)
a[s, l] /= d ;
}
Adlib.remap(b[[k + 1 : ]], a[[k + 1 :, k]]) ;
overall(j = x[k + 1 : ])
for(int i = x.idx(j) ; i < N ; i++)
a[i, j] -= b[i] * b[x.idx(j)] ;
}
at(l = x [N - 1])
a[N - 1, l] = Math.sqrt(a[N - 1, l]) ;
}
A cyclic range is used to allocate the original array on
multiprocessors. The result lower triangular matrix overwrites part of
its storage. During the computation, the collective communication
function remap is used for broadcasting updated columns.
The example also illustrates the use of the member
int idx(Location)
of Range, which recovers a global subscript from a location.
|