December 2012 - mpiwg-coll - mailman3.cels.anl.gov

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Torsten Hoefler 19 Dec '12

19 Dec '12

On Tue, Dec 18, 2012 at 02:34:06PM -0700, Jed Brown wrote: > On Tue, Dec 18, 2012 at 1:36 PM, Torsten Hoefler <[1]htor(a)illinois.edu> > wrote: > > On Sun, Dec 16, 2012 at 09:53:55PM -0800, Jed Brown wrote: > > ï¿½ ï¿½On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler > <[1][2]htor(a)illinois.edu> > > ï¿½ ï¿½wrote: > > > > ï¿½ ï¿½ ï¿½> ï¿½ ï¿½Those use cases > > ï¿½ ï¿½ > ï¿½([3][2][3]http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > > ï¿½ ï¿½ ï¿½> ï¿½ ï¿½were all dependent on being able to reduce to > overlapping > > ï¿½ ï¿½ ï¿½targets. > > ï¿½ ï¿½ ï¿½Depends on your definition of target. ï¿½If you mean processes > by > > ï¿½ ï¿½ ï¿½"targets", then the current interface proposal provides this; > if you > > ï¿½ ï¿½ ï¿½mean memory locations at one process by "targets", then this > will not be > > ï¿½ ï¿½ ï¿½possible within current MPI semantics. > > > > ï¿½ ï¿½I mean that the memory overlaps on the processor accumulating the > result > > ï¿½ ï¿½of the reduction. Think of a bunch of subdomains of a regular > grid with > > ï¿½ ï¿½one or two cells of overlap. An example of a "reduction" is to > add up the > > ï¿½ ï¿½contribution from all copies of each given cell. Cells near the > middle of > > ï¿½ ï¿½a "face" are only shared by two processes, but corner cells are > shared by > > ï¿½ ï¿½several processes. > Yes, that would certainly work with the current proposal (not if we want > to support MPI_IN_PLACE, but that wasn't planned anyway). > > I don't see how this works with the current proposal. I see how to send > different-shaped data (though the caller needs to duplicate entries to be > sent to more than one neighbor "corners"), Yes, datatype (*w) support would make this much more efficient. > but not how to receive/reduce > different-shaped data. To do that, we'd either need (a) building an > incoming buffer with replicated "corners" and make recvcounts[] and > recvdispls[], or (b) add a receiving data type for each neighbor. I think I understand, however, to make sure, can you create the smallest possible send/recv/local reduction example that exhibits this problem? > Another doc bug: sendcounts is a single integer in the C interface for > MPI_Neighbor_reducev. > Also, why are those arrays not const int[]? Yes, both bugs. Will be fixed if we agree on the interface. > > ï¿½ ï¿½If you remove the restriction of equal vector sizes, are you > going to add > > ï¿½ ï¿½an MPI_Datatype describing where to put the result? (I'd expect > that to be > > ï¿½ ï¿½a neighbor_reducew.) Note that in general, there would be some > points > > ï¿½ ï¿½shared by neighbors {1,2} and other points shared by neighbors > {1,3} (and > > ï¿½ ï¿½{2,3}, ...) thus we can't just sort such that the reduction is > always > > ï¿½ ï¿½applied to the "first N" elements. > Yes, I understand. We did not plan on a *w interface yet, however, it's > straight-forward and I'd be in favor of it. The current *v interface > would only support contiguous arrangements but I'll carry the request > for th obviously useful w interface to the Forum. > > int MPI_Neighbor_reducew(void *sendbuf,int sendcounts[],int > senddispls[],MPI_Datatype sendtypes[], > ï¿½ ï¿½ void *recvbuf,int recvcounts[],int recvdispls[],MPI_Datatype > recvtypes[],MPI_Op op,MPI_Comm comm); > With the requirement that all entries in recvtypes[] are built from the > same basic type (at least anywhere they may overlap). The counts and > displs arguments are not needed for semantics (they can be absorbed into > the derived types, and I would expect to do this in most applications), > but I leave them in here for consistency with the other *w routines. Yes, sure, the interface is straight-forward. The question is if the Forum likes overlapping entries in datatypes to be reduced. They are somewhat tricky to implement and also forbidden in current datatypes. > > ï¿½ ï¿½ ï¿½One remaining question is if you can always guarantee "packed" > data, > > ï¿½ ï¿½ ï¿½i.e., that the "empty" elements are always at the tail. Well, > I guess > > ï¿½ ï¿½ ï¿½you could always add identity elements in the middle to create > gaps. > > > > ï¿½ ï¿½I could pack, but I thought the point of the W interfaces was to > enable > > ï¿½ ï¿½the user to avoid packing (with possible performance advantages > relative > > ï¿½ ï¿½to fully-portable user code). > Yes, definitely! Unfortunately, DDTs are not always fast :-/. > > That's what JITs are for, right? ;-) Sure, well, the fact is that they're slow in almost all existing implementations. So go and prod your favorite MPI vendor :-). Torsten -- ### qreharg rug ebs fv crryF ------------- http://www.unixer.de/ ----- Torsten Hoefler | Assistant Professor Dept. of Computer Science | ETH Zï¿½rich Universitï¿½tsstrasse 6 | Zurich-8092, Switzerland CAB E 64.1 | Phone: +41 76 309 79 29

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Jed Brown 18 Dec '12

18 Dec '12

On Tue, Dec 18, 2012 at 1:36 PM, Torsten Hoefler <htor(a)illinois.edu> wrote: > On Sun, Dec 16, 2012 at 09:53:55PM -0800, Jed Brown wrote: > > On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler <[1] > htor(a)illinois.edu> > > wrote: > > > > > Those use cases > > ([3][2]http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > > > were all dependent on being able to reduce to overlapping > > targets. > > Depends on your definition of target. If you mean processes by > > "targets", then the current interface proposal provides this; if you > > mean memory locations at one process by "targets", then this will > not be > > possible within current MPI semantics. > > > > I mean that the memory overlaps on the processor accumulating the > result > > of the reduction. Think of a bunch of subdomains of a regular grid > with > > one or two cells of overlap. An example of a "reduction" is to add up > the > > contribution from all copies of each given cell. Cells near the > middle of > > a "face" are only shared by two processes, but corner cells are > shared by > > several processes. > Yes, that would certainly work with the current proposal (not if we want > to support MPI_IN_PLACE, but that wasn't planned anyway). > I don't see how this works with the current proposal. I see how to send different-shaped data (though the caller needs to duplicate entries to be sent to more than one neighbor "corners"), but not how to receive/reduce different-shaped data. To do that, we'd either need (a) building an incoming buffer with replicated "corners" and make recvcounts[] and recvdispls[], or (b) add a receiving data type for each neighbor. Another doc bug: sendcounts is a single integer in the C interface for MPI_Neighbor_reducev. Also, why are those arrays not const int[]? > > If you remove the restriction of equal vector sizes, are you going to > add > > an MPI_Datatype describing where to put the result? (I'd expect that > to be > > a neighbor_reducew.) Note that in general, there would be some points > > shared by neighbors {1,2} and other points shared by neighbors {1,3} > (and > > {2,3}, ...) thus we can't just sort such that the reduction is always > > applied to the "first N" elements. > Yes, I understand. We did not plan on a *w interface yet, however, it's > straight-forward and I'd be in favor of it. The current *v interface > would only support contiguous arrangements but I'll carry the request > for th obviously useful w interface to the Forum. > int MPI_Neighbor_reducew(void *sendbuf,int sendcounts[],int senddispls[],MPI_Datatype sendtypes[], void *recvbuf,int recvcounts[],int recvdispls[],MPI_Datatype recvtypes[],MPI_Op op,MPI_Comm comm); With the requirement that all entries in recvtypes[] are built from the same basic type (at least anywhere they may overlap). The counts and displs arguments are not needed for semantics (they can be absorbed into the derived types, and I would expect to do this in most applications), but I leave them in here for consistency with the other *w routines. > > > One remaining question is if you can always guarantee "packed" data, > > i.e., that the "empty" elements are always at the tail. Well, I > guess > > you could always add identity elements in the middle to create gaps. > > > > I could pack, but I thought the point of the W interfaces was to > enable > > the user to avoid packing (with possible performance advantages > relative > > to fully-portable user code). > Yes, definitely! Unfortunately, DDTs are not always fast :-/. > That's what JITs are for, right? ;-)

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Torsten Hoefler 18 Dec '12

18 Dec '12

On Sun, Dec 16, 2012 at 09:53:55PM -0800, Jed Brown wrote: > On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler <[1]htor(a)illinois.edu> > wrote: > > > ï¿½ ï¿½Those use cases > ([3][2]http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > > ï¿½ ï¿½were all dependent on being able to reduce to overlapping > targets. > Depends on your definition of target. ï¿½If you mean processes by > "targets", then the current interface proposal provides this; if you > mean memory locations at one process by "targets", then this will not be > possible within current MPI semantics. > > I mean that the memory overlaps on the processor accumulating the result > of the reduction. Think of a bunch of subdomains of a regular grid with > one or two cells of overlap. An example of a "reduction" is to add up the > contribution from all copies of each given cell. Cells near the middle of > a "face" are only shared by two processes, but corner cells are shared by > several processes. Yes, that would certainly work with the current proposal (not if we want to support MPI_IN_PLACE, but that wasn't planned anyway). > > ï¿½ ï¿½As for defining "identity", the operation I would like is to > reduce by > > ï¿½ ï¿½combining with a local buffer (usually in-place destination > buffer). That > > ï¿½ ï¿½is, if I have the local buffer > > ï¿½ ï¿½mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] > This can be expressed as a self-edge (we can discuss about in-place > arguments, but then you would need to guarantee that the local buffer is > larger than the largest neighbor buffer). > > Useful application semantics would require the same. Well, so it's no issue. > > ï¿½ ï¿½and vector types for my two neighbors (defined by me) > > ï¿½ ï¿½incoming_type[0] = [0, 3, 4] > > ï¿½ ï¿½incoming_type[1] = [1, 4] > > ï¿½ ï¿½with incoming data (actually getting sent) > > ï¿½ ï¿½incoming_data[0] = [10.2, 20.2, 30.2] > > ï¿½ ï¿½incoming_data[1] = [100.3, 200.3] > > ï¿½ ï¿½the result would be > > ï¿½ ï¿½[op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, > 200.3), > > ï¿½ ï¿½6.1] > > ï¿½ ï¿½This would be a natural expression of the operation I call > "SFReduce" in > > ï¿½ ï¿½[4][3]http://59A2.org/files/StarForest.pdf > I see, this may be doable with the vector interface (if we remove the > restriction of equal vector sizes -- this would remove some optimization > opportunities). Can you confirm that the current proposed > neighbor_reducev() interface can cover this case? > > If you remove the restriction of equal vector sizes, are you going to add > an MPI_Datatype describing where to put the result? (I'd expect that to be > a neighbor_reducew.) Note that in general, there would be some points > shared by neighbors {1,2} and other points shared by neighbors {1,3} (and > {2,3}, ...) thus we can't just sort such that the reduction is always > applied to the "first N" elements. Yes, I understand. We did not plan on a *w interface yet, however, it's straight-forward and I'd be in favor of it. The current *v interface would only support contiguous arrangements but I'll carry the request for th obviously useful w interface to the Forum. > One remaining question is if you can always guarantee "packed" data, > i.e., that the "empty" elements are always at the tail. Well, I guess > you could always add identity elements in the middle to create gaps. > > I could pack, but I thought the point of the W interfaces was to enable > the user to avoid packing (with possible performance advantages relative > to fully-portable user code). Yes, definitely! Unfortunately, DDTs are not always fast :-/. > Also, would the static communication topology work for your use-cases > (neighborhoods don't change for a while). > > Yes, comm topology is typically static, and we wouldn't use the > neighborhood routines if it was changing frequently. Excellent! Thanks, Torsten -- ### qreharg rug ebs fv crryF ------------- http://www.unixer.de/ ----- Torsten Hoefler | Assistant Professor Dept. of Computer Science | ETH Zï¿½rich Universitï¿½tsstrasse 6 | Zurich-8092, Switzerland CAB E 64.1 | Phone: +41 76 309 79 29

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Jed Brown 17 Dec '12

17 Dec '12

On Mon, Dec 17, 2012 at 10:07 AM, Moore, Shirley V <svmoore(a)utep.edu> wrote: > Jed and Torsten, > > Sorry not to have responded until now but I have had a heavy travel > schedule lately. > > I have previously discussed a quantum mechanics application code with > Torsten that might benefit from an efficient implementation of neighborhood > collectives. For this code, we have a distributed array in which processes > store projector data for the ions with which they overlap. Processors that > overlap the same ions store redundant copies of the data but this is a vast > improvement over earlier implementations in which the entire array was > replicated on all the processes. After computing their contribution to the > new projectors, the processes exchange and sum the data with other > processes that overlap the same ions. Currently this is handled with > point-to-point communication. Although better than the earlier > implementations that used MPI_Allreduce, the current implementation still > has substantial communication overhead. The neighborhoods are irregular and > are not entirely static although they change fairly slowly. The question of > whether the vector that is exchanged is the same or not depends on whether > we do one communication phase per ion or all the communication is one call. > Currently we do it in one call - i.e., a process sends the data for all its > ions to all the processes with which it has overlap and processes just > throw away the data they don't need. This sounds like a similar structure to the mesh-based PDE applications I was explaining. If you determine which ions your neighbors have, you could reduce only those that will be used, but then you need the "sparse reduction" that I was suggesting. I don't foresee the approach of sending everything and doing key matching on the receiver being expressible as an MPI reduction, though you could still do a Gather with neighborhood collectives and reduce by key locally. (This would be impractical for PDE applications; I don't know about your case.) > But since they don't have a data location for data they don't store, this > is not a straight reduction but rather they go through the list and pick > out what they need. The problem with doing one communication phase per ion > is that the number of ions with which a process has overlap can be fairly > large -- e.g., on the order of 50. > > Hope this helps. Please let me know any questions or comments. > > Regards, > Shirley Moore > ________________________________________ > From: five9a2(a)gmail.com [five9a2(a)gmail.com] On Behalf Of Jed Brown [ > jedbrown(a)mcs.anl.gov] > Sent: Sunday, December 16, 2012 10:53 PM > To: Torsten Hoefler > Cc: Moore, Shirley V; MPI-3 Collective Subgroup Discussions > Subject: Re: Neighborhood collectives round 2: reductions > > On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler <htor(a)illinois.edu > <mailto:[email protected]>> wrote: > > Those use cases ([3] > http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > > were all dependent on being able to reduce to overlapping targets. > Depends on your definition of target. If you mean processes by > "targets", then the current interface proposal provides this; if you > mean memory locations at one process by "targets", then this will not be > possible within current MPI semantics. > > I mean that the memory overlaps on the processor accumulating the result > of the reduction. Think of a bunch of subdomains of a regular grid with one > or two cells of overlap. An example of a "reduction" is to add up the > contribution from all copies of each given cell. Cells near the middle of a > "face" are only shared by two processes, but corner cells are shared by > several processes. > > > > As for defining "identity", the operation I would like is to reduce by > > combining with a local buffer (usually in-place destination buffer). > That > > is, if I have the local buffer > > mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] > This can be expressed as a self-edge (we can discuss about in-place > arguments, but then you would need to guarantee that the local buffer is > larger than the largest neighbor buffer). > > Useful application semantics would require the same. > > > > and vector types for my two neighbors (defined by me) > > incoming_type[0] = [0, 3, 4] > > incoming_type[1] = [1, 4] > > with incoming data (actually getting sent) > > incoming_data[0] = [10.2, 20.2, 30.2] > > incoming_data[1] = [100.3, 200.3] > > the result would be > > [op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, > 200.3), > > 6.1] > > This would be a natural expression of the operation I call "SFReduce" > in > > [4]http://59A2.org/files/StarForest.pdf > I see, this may be doable with the vector interface (if we remove the > restriction of equal vector sizes -- this would remove some optimization > opportunities). Can you confirm that the current proposed > neighbor_reducev() interface can cover this case? > > If you remove the restriction of equal vector sizes, are you going to add > an MPI_Datatype describing where to put the result? (I'd expect that to be > a neighbor_reducew.) Note that in general, there would be some points > shared by neighbors {1,2} and other points shared by neighbors {1,3} (and > {2,3}, ...) thus we can't just sort such that the reduction is always > applied to the "first N" elements. > > > One remaining question is if you can always guarantee "packed" data, > i.e., that the "empty" elements are always at the tail. Well, I guess > you could always add identity elements in the middle to create gaps. > > I could pack, but I thought the point of the W interfaces was to enable > the user to avoid packing (with possible performance advantages relative to > fully-portable user code). > > > Also, would the static communication topology work for your use-cases > (neighborhoods don't change for a while). > > Yes, comm topology is typically static, and we wouldn't use the > neighborhood routines if it was changing frequently. >

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Moore, Shirley V 17 Dec '12

17 Dec '12

Jed and Torsten, Sorry not to have responded until now but I have had a heavy travel schedule lately. I have previously discussed a quantum mechanics application code with Torsten that might benefit from an efficient implementation of neighborhood collectives. For this code, we have a distributed array in which processes store projector data for the ions with which they overlap. Processors that overlap the same ions store redundant copies of the data but this is a vast improvement over earlier implementations in which the entire array was replicated on all the processes. After computing their contribution to the new projectors, the processes exchange and sum the data with other processes that overlap the same ions. Currently this is handled with point-to-point communication. Although better than the earlier implementations that used MPI_Allreduce, the current implementation still has substantial communication overhead. The neighborhoods are irregular and are not entirely static although they change fairly slowly. The question of whether the vector that is exchanged is the same or not depends on whether we do one communication phase per ion or all the communication is one call. Currently we do it in one call - i.e., a process sends the data for all its ions to all the processes with which it has overlap and processes just throw away the data they don't need. But since they don't have a data location for data they don't store, this is not a straight reduction but rather they go through the list and pick out what they need. The problem with doing one communication phase per ion is that the number of ions with which a process has overlap can be fairly large -- e.g., on the order of 50. Hope this helps. Please let me know any questions or comments. Regards, Shirley Moore ________________________________________ From: five9a2(a)gmail.com [five9a2(a)gmail.com] On Behalf Of Jed Brown [jedbrown(a)mcs.anl.gov] Sent: Sunday, December 16, 2012 10:53 PM To: Torsten Hoefler Cc: Moore, Shirley V; MPI-3 Collective Subgroup Discussions Subject: Re: Neighborhood collectives round 2: reductions On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler <htor(a)illinois.edu<mailto:[email protected]>> wrote: > Those use cases ([3]http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > were all dependent on being able to reduce to overlapping targets. Depends on your definition of target. If you mean processes by "targets", then the current interface proposal provides this; if you mean memory locations at one process by "targets", then this will not be possible within current MPI semantics. I mean that the memory overlaps on the processor accumulating the result of the reduction. Think of a bunch of subdomains of a regular grid with one or two cells of overlap. An example of a "reduction" is to add up the contribution from all copies of each given cell. Cells near the middle of a "face" are only shared by two processes, but corner cells are shared by several processes. > As for defining "identity", the operation I would like is to reduce by > combining with a local buffer (usually in-place destination buffer). That > is, if I have the local buffer > mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] This can be expressed as a self-edge (we can discuss about in-place arguments, but then you would need to guarantee that the local buffer is larger than the largest neighbor buffer). Useful application semantics would require the same. > and vector types for my two neighbors (defined by me) > incoming_type[0] = [0, 3, 4] > incoming_type[1] = [1, 4] > with incoming data (actually getting sent) > incoming_data[0] = [10.2, 20.2, 30.2] > incoming_data[1] = [100.3, 200.3] > the result would be > [op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, 200.3), > 6.1] > This would be a natural expression of the operation I call "SFReduce" in > [4]http://59A2.org/files/StarForest.pdf I see, this may be doable with the vector interface (if we remove the restriction of equal vector sizes -- this would remove some optimization opportunities). Can you confirm that the current proposed neighbor_reducev() interface can cover this case? If you remove the restriction of equal vector sizes, are you going to add an MPI_Datatype describing where to put the result? (I'd expect that to be a neighbor_reducew.) Note that in general, there would be some points shared by neighbors {1,2} and other points shared by neighbors {1,3} (and {2,3}, ...) thus we can't just sort such that the reduction is always applied to the "first N" elements. One remaining question is if you can always guarantee "packed" data, i.e., that the "empty" elements are always at the tail. Well, I guess you could always add identity elements in the middle to create gaps. I could pack, but I thought the point of the W interfaces was to enable the user to avoid packing (with possible performance advantages relative to fully-portable user code). Also, would the static communication topology work for your use-cases (neighborhoods don't change for a while). Yes, comm topology is typically static, and we wouldn't use the neighborhood routines if it was changing frequently.

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Jed Brown 16 Dec '12

16 Dec '12

On Sat, Dec 15, 2012 at 8:08 AM, Torsten Hoefler <htor(a)illinois.edu> wrote: > > Those use cases ([3] > http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > > were all dependent on being able to reduce to overlapping targets. > Depends on your definition of target. If you mean processes by > "targets", then the current interface proposal provides this; if you > mean memory locations at one process by "targets", then this will not be > possible within current MPI semantics. > I mean that the memory overlaps on the processor accumulating the result of the reduction. Think of a bunch of subdomains of a regular grid with one or two cells of overlap. An example of a "reduction" is to add up the contribution from all copies of each given cell. Cells near the middle of a "face" are only shared by two processes, but corner cells are shared by several processes. > > > As for defining "identity", the operation I would like is to reduce by > > combining with a local buffer (usually in-place destination buffer). > That > > is, if I have the local buffer > > mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] > This can be expressed as a self-edge (we can discuss about in-place > arguments, but then you would need to guarantee that the local buffer is > larger than the largest neighbor buffer). > Useful application semantics would require the same. > > > and vector types for my two neighbors (defined by me) > > incoming_type[0] = [0, 3, 4] > > incoming_type[1] = [1, 4] > > with incoming data (actually getting sent) > > incoming_data[0] = [10.2, 20.2, 30.2] > > incoming_data[1] = [100.3, 200.3] > > the result would be > > [op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, > 200.3), > > 6.1] > > This would be a natural expression of the operation I call "SFReduce" > in > > [4]http://59A2.org/files/StarForest.pdf > I see, this may be doable with the vector interface (if we remove the > restriction of equal vector sizes -- this would remove some optimization > opportunities). Can you confirm that the current proposed > neighbor_reducev() interface can cover this case? > If you remove the restriction of equal vector sizes, are you going to add an MPI_Datatype describing where to put the result? (I'd expect that to be a neighbor_reducew.) Note that in general, there would be some points shared by neighbors {1,2} and other points shared by neighbors {1,3} (and {2,3}, ...) thus we can't just sort such that the reduction is always applied to the "first N" elements. > > One remaining question is if you can always guarantee "packed" data, > i.e., that the "empty" elements are always at the tail. Well, I guess > you could always add identity elements in the middle to create gaps. > I could pack, but I thought the point of the W interfaces was to enable the user to avoid packing (with possible performance advantages relative to fully-portable user code). > > Also, would the static communication topology work for your use-cases > (neighborhoods don't change for a while). > Yes, comm topology is typically static, and we wouldn't use the neighborhood routines if it was changing frequently.

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Torsten Hoefler 15 Dec '12

15 Dec '12

On Thu, Dec 13, 2012 at 11:27:16AM -0800, Jed Brown wrote: > On Tue, Dec 11, 2012 at 12:43 AM, Torsten Hoefler <[1]htor(a)illinois.edu> > wrote: > > On Sun, Dec 09, 2012 at 04:55:51PM -0800, Jed Brown wrote: > > ï¿½ ï¿½Understood. May I ask what is the application motivating this > routine? > For the neighbor_reduce, the use-case follows from your earlier emails > (you asked explicitly for this on the collectives mailinglist in > [2]CAM9tzSmY38bq3gmYqwB5TS5jOv8uwTU9e526tANHDTYgX4XOBg(a)mail.gmail.com) > The > neighbor_reducev is a simple generalization and gets closer to what you > were asking for. I think it's non-trivial to provide identity elements > in the interface while it's not too hard to just put the data into the > function (and hopefully not too much overhead). > > Those use cases ([3]http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) > were all dependent on being able to reduce to overlapping targets. Depends on your definition of target. If you mean processes by "targets", then the current interface proposal provides this; if you mean memory locations at one process by "targets", then this will not be possible within current MPI semantics. > As for defining "identity", the operation I would like is to reduce by > combining with a local buffer (usually in-place destination buffer). That > is, if I have the local buffer > mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] This can be expressed as a self-edge (we can discuss about in-place arguments, but then you would need to guarantee that the local buffer is larger than the largest neighbor buffer). > and vector types for my two neighbors (defined by me) > incoming_type[0] = [0, 3, 4] > incoming_type[1] = [1, 4] > with incoming data (actually getting sent) > incoming_data[0] = [10.2, 20.2, 30.2] > incoming_data[1] = [100.3, 200.3] > the result would be > [op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, 200.3), > 6.1] > This would be a natural expression of the operation I call "SFReduce" in > [4]http://59A2.org/files/StarForest.pdf I see, this may be doable with the vector interface (if we remove the restriction of equal vector sizes -- this would remove some optimization opportunities). Can you confirm that the current proposed neighbor_reducev() interface can cover this case? One remaining question is if you can always guarantee "packed" data, i.e., that the "empty" elements are always at the tail. Well, I guess you could always add identity elements in the middle to create gaps. Also, would the static communication topology work for your use-cases (neighborhoods don't change for a while). > If you now think there is no use-case for any of those (or both) > functions then we should discontinue the discussion of them (I have > absolutely no problem with this :-). > > I'm not optimistic about their utility without support for reduction into > different/overlapping targets. Please define "target" (process vs. memory). Thanks & Best, Torsten -- ### qreharg rug ebs fv crryF ------------- http://www.unixer.de/ ----- Torsten Hoefler | Assistant Professor Dept. of Computer Science | ETH Zï¿½rich Universitï¿½tsstrasse 6 | Zurich-8092, Switzerland CAB E 64.1 | Phone: +41 76 309 79 29

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Jed Brown 13 Dec '12

13 Dec '12

On Tue, Dec 11, 2012 at 12:43 AM, Torsten Hoefler <htor(a)illinois.edu> wrote: > On Sun, Dec 09, 2012 at 04:55:51PM -0800, Jed Brown wrote: > > Understood. May I ask what is the application motivating this routine? > For the neighbor_reduce, the use-case follows from your earlier emails > (you asked explicitly for this on the collectives mailinglist in > CAM9tzSmY38bq3gmYqwB5TS5jOv8uwTU9e526tANHDTYgX4XOBg(a)mail.gmail.com) The > neighbor_reducev is a simple generalization and gets closer to what you > were asking for. I think it's non-trivial to provide identity elements > in the interface while it's not too hard to just put the data into the > function (and hopefully not too much overhead). > Those use cases (http://lists.mpi-forum.org/mpi3-coll/2011/11/0239.php) were all dependent on being able to reduce to overlapping targets. As for defining "identity", the operation I would like is to reduce by combining with a local buffer (usually in-place destination buffer). That is, if I have the local buffer mine = [1.1, 2.1, 3.1, 4.1, 5.1, 6.1] and vector types for my two neighbors (defined by me) incoming_type[0] = [0, 3, 4] incoming_type[1] = [1, 4] with incoming data (actually getting sent) incoming_data[0] = [10.2, 20.2, 30.2] incoming_data[1] = [100.3, 200.3] the result would be [op(1.1, 10.2), op(2.1, 100.3), 3.1, op(4.1, 20.2), op(5.1, 30.2, 200.3), 6.1] This would be a natural expression of the operation I call "SFReduce" in http://59A2.org/files/StarForest.pdf > If you now think there is no use-case for any of those (or both) > functions then we should discontinue the discussion of them (I have > absolutely no problem with this :-). I'm not optimistic about their utility without support for reduction into different/overlapping targets.

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Torsten Hoefler 11 Dec '12

11 Dec '12

On Sun, Dec 09, 2012 at 04:55:51PM -0800, Jed Brown wrote: > Understood. May I ask what is the application motivating this routine? For the neighbor_reduce, the use-case follows from your earlier emails (you asked explicitly for this on the collectives mailinglist in CAM9tzSmY38bq3gmYqwB5TS5jOv8uwTU9e526tANHDTYgX4XOBg(a)mail.gmail.com) The neighbor_reducev is a simple generalization and gets closer to what you were asking for. I think it's non-trivial to provide identity elements in the interface while it's not too hard to just put the data into the function (and hopefully not too much overhead). If you now think there is no use-case for any of those (or both) functions then we should discontinue the discussion of them (I have absolutely no problem with this :-). Best, Torsten > > On Dec 9, 2012 1:14 PM, "Torsten Hoefler" <[1]htor(a)illinois.edu> wrote: > > On Sat, Dec 08, 2012 at 12:49:35PM -0800, Jed Brown wrote: > > ï¿½ ï¿½On Sat, Dec 8, 2012 at 11:12 AM, Torsten Hoefler > <[1][2]htor(a)illinois.edu> > > ï¿½ ï¿½wrote: > > > > ï¿½ ï¿½ ï¿½Hi all, > > > > ï¿½ ï¿½ ï¿½We discussed the neighborhood reductions at the last Forum and > the straw > > ï¿½ ï¿½ ï¿½vote if we should include them in the next revision was: > > > > ï¿½ ï¿½ ï¿½ï¿½- yes: 18 > > ï¿½ ï¿½ ï¿½ï¿½- no: 0 > > ï¿½ ï¿½ ï¿½ï¿½- abstain: 3 > > > > ï¿½ ï¿½ ï¿½I addressed all the issues in the draft that were brought up > at the > > ï¿½ ï¿½ ï¿½Forum. The new draft is now at > [2][3]http://www.unixer.de/sec/topol.pdf . > > ï¿½ ï¿½ ï¿½Look > > ï¿½ ï¿½ ï¿½for ticket "XXX". > > > > ï¿½ ï¿½The other interfaces for MPI_Ineighbor_reduce do not contain the > "I" (page > > ï¿½ ï¿½40, line 25 and 30); MPI_Ineighbor_reducevï¿½ > > ï¿½ ï¿½ï¿½does not have the "v" (page 41, line 26 and 31). > Thanks! Those are fixed. [4]http://www.unixer.de/sec/topol.pdf > > > ï¿½ ï¿½ ï¿½One open question remains: would a single send buffer for > > ï¿½ ï¿½ ï¿½neighbor_reduce suffice or do we need one buffer per > destination > > ï¿½ ï¿½ ï¿½process? The second case could always be done with > neighbor_reducev > > ï¿½ ï¿½ ï¿½(with small additional costs). This questions is more to the > potential > > ï¿½ ï¿½ ï¿½users (Jed etc.). > > > > ï¿½ ï¿½My understanding of Neighbor_reducev is that I send different > sizes to > > ï¿½ ï¿½each neighbor, but receive the same size from every neighbor > (reducing > > ï¿½ ï¿½into exactly one buffer). > That is correct. > > > ï¿½ ï¿½That isn't really a useful operation in domain > > ï¿½ ï¿½decomposed methods. The useful operation is that I reduce > different sized > > ï¿½ ï¿½received buffers into different (but sometimes overlapping) parts > of my > > ï¿½ ï¿½local buffer. > Well, the issue is that MPI reduction operations cannot be applied to > vectors of different length because this would require the definition of > an identity element. While this is easy for the predefined ops (e.g., > "MIN_INT" for int max and "0" for sum, etc.), this would require much > more changes for user-defined operations (another call to specify > these). The current interface proposal would require you to fill in > those elements where needed. Or am I misunderstanding or missing > something? > > > ï¿½ ï¿½The single send buffer (with different datatype arguments) > imposes no > > ï¿½ ï¿½restriction and is natural. > Thanks! > > Best, > ï¿½ Torsten > > -- > ### qreharg rug ebs fv crryF ------------- [5]http://www.unixer.de/ > ----- > Torsten Hoefler ï¿½ ï¿½ ï¿½ ï¿½ ï¿½ | Assistant Professor > Dept. of Computer Science | ETH Zï¿½rich > Universitï¿½tsstrasse 6 ï¿½ ï¿½ | Zurich-8092, Switzerland > CAB E 64.1 ï¿½ ï¿½ ï¿½ ï¿½ ï¿½ ï¿½ ï¿½ ï¿½| Phone: [6]+41 76 309 79 29 > > References > > Visible links > 1. mailto:[email protected] > 2. mailto:[email protected] > 3. http://www.unixer.de/sec/topol.pdf > 4. http://www.unixer.de/sec/topol.pdf > 5. http://www.unixer.de/ > 6. file:///home/htor/tmp/mutt/tel:%2B41%2076%20309%2079%2029 -- ### qreharg rug ebs fv crryF ------------- http://www.unixer.de/ ----- Torsten Hoefler | Assistant Professor Dept. of Computer Science | ETH Zï¿½rich Universitï¿½tsstrasse 6 | Zurich-8092, Switzerland CAB E 64.1 | Phone: +41 76 309 79 29

1 0

Re: [mpi3-coll] Neighborhood collectives round 2: reductions
by Jed Brown 09 Dec '12

09 Dec '12

Understood. May I ask what is the application motivating this routine? On Dec 9, 2012 1:14 PM, "Torsten Hoefler" <htor(a)illinois.edu> wrote: > On Sat, Dec 08, 2012 at 12:49:35PM -0800, Jed Brown wrote: > > On Sat, Dec 8, 2012 at 11:12 AM, Torsten Hoefler <[1] > htor(a)illinois.edu> > > wrote: > > > > Hi all, > > > > We discussed the neighborhood reductions at the last Forum and the > straw > > vote if we should include them in the next revision was: > > > > - yes: 18 > > - no: 0 > > - abstain: 3 > > > > I addressed all the issues in the draft that were brought up at the > > Forum. The new draft is now at [2] > http://www.unixer.de/sec/topol.pdf . > > Look > > for ticket "XXX". > > > > The other interfaces for MPI_Ineighbor_reduce do not contain the "I" > (page > > 40, line 25 and 30); MPI_Ineighbor_reducev > > does not have the "v" (page 41, line 26 and 31). > Thanks! Those are fixed. http://www.unixer.de/sec/topol.pdf > > > One open question remains: would a single send buffer for > > neighbor_reduce suffice or do we need one buffer per destination > > process? The second case could always be done with neighbor_reducev > > (with small additional costs). This questions is more to the > potential > > users (Jed etc.). > > > > My understanding of Neighbor_reducev is that I send different sizes to > > each neighbor, but receive the same size from every neighbor (reducing > > into exactly one buffer). > That is correct. > > > That isn't really a useful operation in domain > > decomposed methods. The useful operation is that I reduce different > sized > > received buffers into different (but sometimes overlapping) parts of > my > > local buffer. > Well, the issue is that MPI reduction operations cannot be applied to > vectors of different length because this would require the definition of > an identity element. While this is easy for the predefined ops (e.g., > "MIN_INT" for int max and "0" for sum, etc.), this would require much > more changes for user-defined operations (another call to specify > these). The current interface proposal would require you to fill in > those elements where needed. Or am I misunderstanding or missing something? > > > The single send buffer (with different datatype arguments) imposes no > > restriction and is natural. > Thanks! > > Best, > Torsten > > -- > ### qreharg rug ebs fv crryF ------------- http://www.unixer.de/ ----- > Torsten Hoefler | Assistant Professor > Dept. of Computer Science | ETH Zürich > Universitätsstrasse 6 | Zurich-8092, Switzerland > CAB E 64.1 | Phone: +41 76 309 79 29 >

1 0