HPJava Home Page
Community Grids
Java Grande Home
PCRC Home Viewing these pages |
## An Example - Choleski Decomposition
Any real, symmetric, positive definite matrix
A can be decomposed into the form
Now write A and L
as follows:
These observations yield the following algorithm for computing
a Choleski decomposition:
An 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 [[*]] m = new float [[N]] ; ... some code to initialize `a' ... for(int k = 0 ; k < N - 1 ; k++) { at(j = x[k]) { float d = Math.sqrt(a[k, j]) ; a[k, j] = d ; for(int i = k + 1 ; i < N ; i++) a[i, j] /= d ; } Adlib.remap(m[[k + 1 : N - 1]], a[[k + 1 : N - 1, k]]) ; overall(j = x for k + 1 : N - 1) for(int i = j` ; i < N ; i++) a[i, j] -= m[i] * m[j`] ; } at(j = x[N - 1]) a[N - 1, j] = Math.sqrt(a[N - 1, j]) ; }A cyclic range is used to distribute elements of each row of the array over the set of processors. Every column is stored in its entirety on a particular processor - this is specified by making the first dimension sequential. In this kind of algorithm the cyclic ("round robin") assignment of columns to processors generally makes for better load balancing than a block-wise assignment would.
The program introduces the third and final special control construct
of HPJava. The at(i = x[n]) { ... }is completely equivalent to overall(i = x for n : n) { ... }The final statement of our program: at(j = x[N - 1]) a[N - 1, j] = Math.sqrt(a[N - 1, j]) ;should be read to say that the assignment in the body is only executed by the process (or, in a more general, multidimensional context, the set of processes) that holds the `N-1` element of
range `x` . In this sense the at may also
be interpretted as a specialized on construct, except that it
has the additional role of scoping a distributed index. In typical
parallel programs the at construct is used less frequently than the
general overall construct or the on construct.
During the computation, the collective communication
function
Note that it would be illegal to use the distributed index |

Bryan Carpenter,

`(dbc@ecs.soton.ac.uk)`

.
Last updated May 2007.