From: Josh M. <jos...@an...> - 2013-06-07 11:20:07
|
Hi all, with the separation of Rail from the simple x10.array and the fully-featured x10.regionarray classes, the map and reduce methods have been lost from Rail. The map and reduce patterns (and to a lesser extent, scan) are so fundamental that I think this might be an appropriate time to define a standard approach for applying these patterns across X10 data structures. The existing approach seems to be to just implement methods for map/reduce as needed on container classes like Array and DistArray. This may lead to undesirable repetition if it is extended to other types like Rail, ArrayList and other Collections. Would it be appropriate to create a new interface Indexable that defines the indices() method and get and set operators? This could be used to implement a general map operation as follows: public class x10.lang.Map { public @Inline static def map[T](op:(T)=>T, a:Indexable[T]) { finish for (p in a.indices()) async { a(p) = op(a(p)); } } } A related question: should map/reduce be parallel or sequential by default? The current implementations on the simple array classes are all sequential, but there are TODO comments on each suggesting they should be parallel. The new work stealing implementation should substantially reduce the overhead of a parallel loop, which may swing the balance in favour of parallel map/reduce. There are obviously multiple different ways of dividing map/reduce for parallel execution; it seems to me that the best general-purpose implementation would be recursive bisection, possibly with some minimum grain size; but other implementations may work better for particular problems. Do you think it is possible to come up with a standard approach in time for version 2.4? Cheers, Josh -- ------------------------------------------ Josh Milthorpe Postdoctoral Fellow, Research School of Computer Science Australian National University, Building 108 Canberra, ACT 0200 Australia Phone: + 61 (0)2 61254478 Mobile: + 61 (0)407 940743 E-mail: jos...@an... Web: http://cs.anu.edu.au/~Josh.Milthorpe/ |
From: David P G. <gr...@us...> - 2013-06-11 22:27:02
|
Hi Josh, In general, I think the reason to have map/reduce/scan operations in the library (as opposed to defined by the user in their application via the normal iteration methods provided by the library) is to give efficient & parallel implementations of the operations. In terms of semantics, I think that means the operations should be defined to be may parallel (the implementation may implement some operations in parallel, but may also implement some of them sequentially). This gives the implementation the most flexibility to heuristically pick an appropriate task-size to dynamically match the available resources. Doing a good job of dividing the work up into chunks and doing them in parallel takes some amount of clever code, so it is appealing to do it once and share it between multiple data structures. However, the trick is doing that in a way that the abstraction that enables a single map or reduce implementation to work on multiple collection types doesn't introduce so much overhead that the performance gained by clever coding of the parallel work structure gets lost in the sequential overhead of object allocation, indirection, and interface invocation. My intuition is that the general implementation would lose enough performance that we'd end up with specialized ones for many of the data structures, but I could be wrong. It would be interesting to see how much of a performance difference there is and understand how much of the gap is fundamental and how much could be fixed via better optimization of the sequential object-oriented X10 language features. For the specific case of Rail, we should bring back map/reduce functions for Rail before we release 2.4. Since Rail is a @NativeRep class, we will probably do that by putting static functions into x10.util.ArrayUtils (or similar) so that we can write them once in X10. --dave |