January 2009 - Mpi-22 - mailman3.cels.anl.gov

Re: [Mpi-22] [MPI Forum] #96: MPI_OP_CREATE and associativity
by unknown＠example.com 12 Jan '09

12 Jan '09

On Mon, Jan 12, 2009 at 05:11:24PM +0100, Jesper Larsson Traeff wrote: > On Mon, Jan 12, 2009 at 10:36:58AM -0500, Torsten Hoefler wrote: > > > > To optimize this, and retain the order of summation, one could employ > > similar strategies as for gather to reduce the messaging complexity > > (e.g. from O(N) to O(log_N)). > Since you cannot do anything on intermediate nodes in your gather tree, > the message complexity is O(Nm), m: size of vector... yes - details actually depend on the model :). Let's use the well-known LogGP with the extension, that the reduction per byte costs x mus as a base for discussions. I talked about a direct vs. tree algorithm (which of course only makes sense for small data!): I assume that all nodes start their participation in the call at the same time and the root is the one who finishes last. I don't model CPU overhead because this doesn't add more information. Direct: t=L + (P-2)g + (s-1)G + P*s*x BinomialTree: t=log_2(P)L+(log_2(P)-1)g + sum_i=1^(log_2(P)) (i*(s-1)G) + P*s*x The direct receive is simple and needs no explanation. The longest path in the bintree has a length of log_2(P), and the rank 0 sends to log_2(P) nodes. The messages grow along the critical path (thus the sum). > You only gain something for small problems by reducing the number of > receives at the root. yes, however, the definition of "small" changes with scale (see above models). Also, the transmission of mid-sized messages can be handled in the same model with double or fractional trees (see Karp's article "Optimal Broadcast and Summation in the LogP Model" from '93). Yes, and I know that this only affects data motion, the reduction has to be done on order on rank 0. However, it is often the case that (especially for larger messages and modern architectures such as GPUs on Chip/Larrabee), the bandwidth of the processor is much higher than the bandwidth of the network. Large messages could use algorithms that control congestion (such in large Gathers), i.e., only a subset of the processes send at the same time. The data could also reduced in order here. All of those optimizations are not trivial and very network-dependent. > In the case where you use some dynamic algorithm where things may arrive in > some unspecified order, you'd again have to buffer the contributions from > the processes before you can do the reduction. As I said, this depends. And you have the same problems with the current MPI reduction rules, i.e., you either have to buffer or to synchronize. Out of order doesn't exist. So in this implementation, you'll either buffer (small messages) or synchronize (large messages) as you do for the current reductions. > > yes, they can still be treated as associative (for all internal types), > > but thet user should have a chance to define non-associative reductions. > > > In the apps you refer to, I guess they often want an MPI_SUM on an MPI_FLOAT > done in some particular order with a particular bracketing. Thus, what > you need is some ability to control each individual MPI_Reduce call? yes, but I guess controlling each call is not necessary. However, controlling the order of operations might be necessary to ensure correctness. But I don't know a particular app, so the whole argument is weak. I just want to discuss the issue and either understand why we don't have this feature or discuss its addition. My point is that there are (limited) optimization possibilities and that we limit ourselves enourmously by enforcing the same reduction order for all float/double operations and all user-defined operations in MPI-2.1. If associativity would be an explicit property of a user-defined operation, then we could apply dynamic optimizations based on arrival time, which we can't right now (side-note: we can do this for associative ops, such as all ops on non-fp types). Thanks & Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Postdoctoral Researcher Open Systems Lab | Indiana University 150 S. Woodlawn Ave. | Bloomington, IN, 474045, USA Lindley Hall Room 135 | +01 (812) 855-3608 *

1 0

chapter authors 5, 6, 8, 10, 13, 15, 16 please review ticket #46
by unknown＠example.com 12 Jan '09

12 Jan '09

Add const Keyword to the C bindings https://svn.mpi-forum.org/trac/mpi-forum-web/ticket/46 Chapter authors, please review this proposal that it identifies the right functions in your chapters. Chapters 3,4,7,9 and 11 already reviewed. Thanks to Rich and Jesper. Still need to review. Chapter 5 Adam Moody, Collective Communication Chapter 6 Richard Treumann, Groups, Contexts, and Communicators Chapter 10 David Solt, Process Creation and Management Chapter 13 Rajeev Thakur, I/O Chapter 15 Rolf Rabenseifner, Deprecated Functions Chapter 16 Jeff Squyres, Language Bindings To make it easier for the chapter authors, the functions are listed in chapter order in the proposal. Thanks, .Erez *

1 0

Re: [Mpi-22] [MPI Forum] #96: MPI_OP_CREATE and associativity
by unknown＠example.com 12 Jan '09

12 Jan '09

On Mon, Jan 12, 2009 at 10:36:58AM -0500, Torsten Hoefler wrote: > > To optimize this, and retain the order of summation, one could employ > similar strategies as for gather to reduce the messaging complexity > (e.g. from O(N) to O(log_N)). Since you cannot do anything on intermediate nodes in your gather tree, the message complexity is O(Nm), m: size of vector... You only gain something for small problems by reducing the number of receives at the root. In the case where you use some dynamic algorithm where things may arrive in some unspecified order, you'd again have to buffer the contributions from the processes before you can do the reduction. > yes, they can still be treated as associative (for all internal types), > but thet user should have a chance to define non-associative reductions. > In the apps you refer to, I guess they often want an MPI_SUM on an MPI_FLOAT done in some particular order with a particular bracketing. Thus, what you need is some ability to control each individual MPI_Reduce call? Jesper

1 0

Re: [Mpi-22] [MPI Forum] #96: MPI_OP_CREATE and associativity
by unknown＠example.com 12 Jan '09

12 Jan '09

On Mon, Jan 12, 2009 at 03:19:12PM +0100, Jesper Larsson Traeff wrote: > > For non-associative operators, in order to get any meaningful result, > all you can do is to perform the operations in some predefined order > (eg. rank-order) with a predefined "bracketing", ((((0+1)+2)+3)+...)+n). > That seems to imply a linear time algorithm? yes, it does but: linear time in computation, not in communication though! I know, this sounds counter-intuitive, but I heard from other scientists that there are fields that need this functionality (i.e., they can't guarantee numerical stability). Examples are mainly financial markets not so much simulations (most simulations are full of approximations anyway). > Thus, I think it is right that the standard requires the operators to > be associative. That's exactly what I would criticize. Don't get me wrong, I am not pushing hard, but the argument that there seems limited optimization potential, and thus we should ignore mathematical properties seems weak. Also, optimization potential is actually not that limited. The two implementations that I've seen just do a loop over all ranks: if(rank == 0) for(i=0;i<comm_size;i++) { MPI_Recv(buf, ...); sum += buf; } else MPI_Send(buf, ..., 0); To optimize this, and retain the order of summation, one could employ similar strategies as for gather to reduce the messaging complexity (e.g. from O(N) to O(log_N)). Now one could argue that the user could just do MPI_Gather and then sum up the buffer, but what if the user doesn't have enough memory to store the entire array. An MPI implementation could use flow control and messaging algorithms in order to receive the data at rank 0 and reduce it piece by piece. Allreductions have even more potential. > Operators on FLOATs are usually treated as if they are associative > (with some/many MPI libraries providing a possibility to switch to an > algorithm with some predefined ordering and bracketing, for the cases > where this is desired). yes, they can still be treated as associative (for all internal types), but thet user should have a chance to define non-associative reductions. > I therefore think this extension requires a lot more thought for it to > be "mathematically well-defined" and also otherwise make sense why? Making it mathematically consistent is as simple as stated. Some optimization possibilities are shown above. What else is required? Don't get me wrong, I'm not pushing and I'm happy to withdraw the ticket if the general consensus is that it's nonsense. It just seems rather inconsistent to me that associativity is just half-assumed. It is stated on page 160:44: "The operation op is always assumed to be associative." but then on page 161:1, we admit that we actually know the mathematical properties of IEEE-754 and say: "This may change the result of the reduction for operations that are not strictly associative and commutative, such as floating point addition.". And the following advice to implementors makes the situation even worse (I think), because it says that there is only one wrong result that is right for MPI. This advice also disables optimizations that could be done based on arrival patterns (as Bronis mentioned before). This would be much clearer if we would make the associativity explicit. But this might as well be an MPI-3 discussion. Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Postdoctoral Researcher Open Systems Lab | Indiana University 150 S. Woodlawn Ave. | Bloomington, IN, 474045, USA Lindley Hall Room 135 | +01 (812) 855-3608 *

1 0

Re: [Mpi-22] [MPI Forum] #96: MPI_OP_CREATE and associativity
by unknown＠example.com 12 Jan '09

12 Jan '09

For non-associative operators, in order to get any meaningful result, all you can do is to perform the operations in some predefined order (eg. rank-order) with a predefined "bracketing", ((((0+1)+2)+3)+...)+n). That seems to imply a linear time algorithm? Thus, I think it is right that the standard requires the operators to be associative. Operators on FLOATs are usually treated as if they are associative (with some/many MPI libraries providing a possibility to switch to an algorithm with some predefined ordering and bracketing, for the cases where this is desired). I therefore think this extension requires a lot more thought for it to be "mathematically well-defined" and also otherwise make sense Jesper On Fri, Jan 02, 2009 at 05:26:48PM -0000, MPI Forum wrote: > #96: MPI_OP_CREATE and associativity > -------------------------------------+-------------------------------------- > Reporter: htor | Owner: htor > Type: Enhancements to standard | Status: new > Priority: Forum feedback requested | Milestone: 2009/02/09 California > Version: MPI 2.2 | Keywords: > -------------------------------------+-------------------------------------- > Information about associativity can not be attached to user-defined > operations. This prevents any dynamic reordering of trees, based on > different arrival patterns (strongly recommended by the Advice to > Implementors in Sec. 5.9.1). Architecture-dependent associativity can be > derived for predefined types (e.g., MPI_INT is associative while MPI_FLOAT > is not on most architectures). No such statements can be made about user- > defined operations. This seems to be mathematically incomplete. > > == History == > This has been the status quo since MPI-1. > > == Proposed Solution == > Add an additional (bool) in-argument to MPI_OP_CREATE that indicates if > the operation is associative or not. > > == Impact on Implementations == > low, nothing needs to be changed and the argument can be ignored. However, > it reveals rather interesting optimization possibilities at large scale. > > == Impact on Applications / Users == > low, an additional argument can be supplied which could just be "false" to > retain the status quo. > > == Alternative Solutions == > none > > == Entry for the Change Log == > added associativity argument to MPI_OP_CREATE > > -- > Ticket URL: <https://svn.mpi-forum.org/trac/mpi-forum-web/ticket/96> > MPI Forum <https://svn.mpi-forum.org/> > MPI Forum

1 0