Details
-
Type:
Improvement
-
Status:
Open
-
Priority:
Minor
-
Resolution: Unresolved
-
Affects Version/s: X10 2.1.2
-
Fix Version/s: X10 2.4
-
Component/s: XRX Runtime
-
Labels:None
-
Number of attachments :
Description
The current implementation of collecting finish, while correct and general, is inefficient for large result objects and SPMD-style programs.
Suppose I have something like the following code. Each place computes a partial contribution to a large matrix; these are then summed to form the complete matrix. (This example is taken from the Hartree-Fock code in ANUChem.)
A = new Array[T](/*large*/); val partialA = new DistArray[Array[T]](Dist.makeUnique(), ...); for (i in 1..iterations) { finish for (place in Place.places()) async { val placeContribution = at (place) { // calculate partial contribution to A return partialA(place); }; // gather and reduce my contribution val sum = (a:Double, b:Double) => (a+b); atomic { A.map[Double,Double](A, placeContribution, sum); } } // now compute on A }
This could be expressed more succinctly with collecting finish:
static struct ArraySumReducer(region:Region) implements Reducible[Array[Double]] {...} ... val A = finish (ArraySumReducer(A.region)) ateach (place in Place.places()) { ... return partialA(place); } }; ...
However, with the current implementation of collecting finish, this is neither speed nor memory efficient. Collecting finish will create a number Place.MAX_PLACES of arrays in which to store the results from each place, as well as other temporary arrays to hold the partially reduced results. If A is very large, this could be a significant cost.
There may be several possibilities for improvement, depending on the specific case:
- allow for pre-allocation of the results rail (one element per place) at place 0. The allocation could then be hoisted above the outer loop.
- support stack allocation of intermediate results e.g. for small arrays.
- where there is only one offer per place ("SPMD collecting finish"?), each place need not hold a rail of results for each thread - the offer can be sent immediately to the root place. Additionally, there is no need to allocate an initial zero result for each place in the results rail at place 0.