November 2011 - petsc-dev - mailman3.cels.anl.gov

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 12:40, Mark F. Adams <mark.adams(a)columbia.edu>wrote: > OK, that makes sense at least abstractly. I'm skeptical that you are > going to be able to do much with all this one sided stuff; it seems to be > that you would always have the two sided data at some point and then you > might setup one sided maps for repeated operations like for a MatVec that > are efficient. But this is kind of trivial. > Yeah, that's easy. The update for MatMult() just involves each process calling one MPI_Get() for each remote process that it needs data from. What to get is encoded in an MPI_Datatype so there is no user-visible packing on either side. These calls are all non-blocking and you finish the update with MPI_Win_fence(). You can test performance of this approach using -vecscatter_window (although it's slightly different because it does user-visible packing). Of course we can easily build a two-sided representation, but it's not necessary. In the one-sided model above, the owner of a global point does not know how many local parts accessed it (and nowhere inside the MPI implementation or network stack is there storage proportional to the number of accessors, so there isn't a scalability problem with globally coupled dofs). > > I would suggest writing a non-trivail algorithm with your model. I have > two ideas: > > 1) when a coarse AMG (use aggregation MG to me concrete) grid is > constructed and you have a map (bipartite graph) with one edge for each > fine grid point to a coarse grid point (not necessarily on your processor). > I have too few vertices per processor so I want to reduce the number of > processors used in the coarse grid. > Do you assume the availability of a partitioner at this stage, or you just want to do something simple like rank-order aggregation? In my model, the owner of a point would somehow (e.g. by calling a partitioner) determine the new owner of that point. This information is communicated to the ghosters of that point (again without knowing how many there are), any other node/connectivity data is communicated from old owner to new owner (this is a 1-1 relation, thus trivial with these primitives), and finally the ghosters address the new location when they need updates. > I can assume that my fine grid was well partitioned, and to keep the > process local assume the fine grid was partitioned with a space filling > curve, or something, such that when I aggregate processors (eg, (0-3), > (4-7) ... if I reduced the number of active processor by 4) I still have > decent data locality. Eventually I would like a local algorithm to improve > load balance at this point, but that is more than you might want to start > with. > If you have a local graph partitioner that can tell you what to move for better load balance, then I think I can move it efficiently and without redundant storage or specification. > > 2) Any AMR algorithm that you like. Again, you might want to punt on load > balancing. > I think the primitives are fine for this. There is an algorithmic question of how to modify boundary zones with minimal communication, but if you decide how much you want to communicate when (e.g. on the chalk board), I will figure out how to implement it. I think redistribution for load balancing is represented pretty elegantly, but it would be good to work out the details.

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 12:19, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > I answered this in a private discussion and Matt and Jed and totally > demolished his arguments. Folks, it's demolition derby time! Barry scored a direct hit, but landed upside down and is now spinning his wheels. Time for someone to take pity on him and flip him over like you would do for that turtle the neighbor kid left upside down.

1 0

Re: [petsc-dev] Generality of VecScatter
by Mark F. Adams 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 12:31 PM, Barry Smith wrote: > > On Nov 24, 2011, at 9:51 AM, Mark F. Adams wrote: > >> Barry, >> >> I totally disagree. About 5 years ago a lot of lumpenproletariat CS people were crowing that MPI was dead and after a few years of naval gazing w/o being able to compete the sentence "and will be replaced with ..." they quietly resigned themselves to the fact that MPI will be on top for the vast majority of apps for the foreseeable future. I think anyone with their feet on the ground, even the most pro future languages people like Kathy Yelick, sees MPI being in the mix for a long time. Now a days I see lots of "MPI + ?" on slides, or even "MPI + OpenMP + ?" but PGAS languages are still at the fringes. > > You seem to have the tact assumption that the choice is between MPI+X or some PGAS language, this I say is a major straw man! Well of course it is! > (And I totally agree with you PGAS language are junk and will never take off). > > What I am suggesting is there is a third alternative that is compatible with MPI (allowing people to transition from MPI to it without rewriting all current MPI based code) and is COMPLETELY library based (as MPI is). I with you so far, > This new thing would provide a modern API suitable for many core, for GPUs and distributed computing and the API would focus on moving data and scheduling tasks. I don't see how you can do a task based thing with anything that looks remotely like MPI or can be achieved in any kind of an incremental way, but I'd be interested in looking at what you have in mind. Mark > The API will be suitable for C/C++/Fortran 90. Now exact details of the API and the model are not clear to me of course. I will be pushing the MCS CS folks in this direction because I don't see any other reasonable alternative (MPI+X is fundamentally not powerful enough for the new configurations and PGAS are a joke). > > > Barry > > Very crudely this new thing could be thought of as MPI - all point to point stuff + neighbor communication (with all communication including Allreduce asynchronize). > >> >> Mark >> >> On Nov 23, 2011, at 11:22 PM, Barry Smith wrote: >> >>> >>> These guys are making a very big strategic mistake. They cannot expect to get any funding at all if they continue to purse MPI when the acting and presumably next ASCR director believes with every fiber of his being that MPI is dead. They are writing the death sentence to computer science at ANL. >>> >>> Barry >>> >>> >>> On Nov 23, 2011, at 6:28 PM, Jed Brown wrote: >>> >>>> I had a useful conversation with the MPICH guys today about the unstructured communication primitives that Mark, Matt, Barry, and I have been discussing. It's looking like we can do a very thin communication library that has the nice semantics I was looking for, namely that the local-to-global is stored only as indices in the local space. To implement the communication primitives, the owner of a global node never needs to know how many or which processes have that point in their local space. There is an MPI-3 feature that we can use to elegantly avoid two-way knowledge for pointwise gather/scatter. (We can always implement the same interface using vanilla MPI-1, but the MPI-2/3 implementation would have less overhead.) >>>> >>>> If I/we write this layer, VecScatter (with arbitrary data types, etc) could be implemented very easily on top of it. I'm in no rush to do this, but I could imagine getting there eventually. The VecScatter interface allows some things that might not be important. For example, any process can specify an edge in the communication graph, even if it does not own the source or the destination vertex. Also, both source and destination vertices can have degree higher than one. We can even put a link between the same points twice (effectively multiplying that contribution by 2 when using ADD_VALUES). I don't know if this ever makes semantic sense, but the interface allows it. >>>> >>>> I wonder if we can express all useful communication with a more restrictive interface similar to a local-to-global map (but mapping between any vectors) where one side (typically called "local", but doesn't need to actually be a local Vec) has at most one edge. >>>> >>>> What weird things do people use VecScatter for that might break with this more restrictive model? >>> >>> >> > >

1 0

Re: [petsc-dev] Generality of VecScatter
by Mark F. Adams 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 12:45 PM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 11:31, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > You seem to have the tact assumption that the choice is between MPI+X or some PGAS language, this I say is a major straw man! (And I totally agree with you PGAS language are junk and will never take off). > > What I am suggesting is there is a third alternative that is compatible with MPI (allowing people to transition from MPI to it without rewriting all current MPI based code) and is COMPLETELY library based (as MPI is). This new thing would provide a modern API suitable for many core, for GPUs and distributed computing and the API would focus on moving data and scheduling tasks. The API will be suitable for C/C++/Fortran 90. Now exact details of the API and the model are not clear to me of course. I will be pushing the MCS CS folks in this direction because I don't see any other reasonable alternative (MPI+X is fundamentally not powerful enough for the new configurations and PGAS are a joke). > > I just wrote the following in a private discussion with Barry and Matt. Copied here for the rest of you. > > Do you want to abandon MPI as a foundation for distributed memory, or do you just want a reliable way to manage multicore/SMT? I am far from convinced that we can't or shouldn't build our ultimate communication abstraction on top of MPI. In my opinion, the job of MPI is to abstract non-portable network-level details to provide a minimal set of primitives on which to write performant code and to implement libraries. Of course there is some unnecessary cruft, and there are occasional holes where networks can do cool things that are useful to libraries, but have not been exposed through MPI. But cleaning that stuff up is what I think new MPI standards should be targeting. > > I do not believe the goal of MPI is to provide abstractions that are directly usable by applications. That is the scope of domain-specific and general-purpose libraries. If an abstraction can be implemented with portable performance using primitives in MPI, then it should *not* be added to MPI. > I guess Barry "demolished" this argument, but many applications do not have libraries available and many application people are so much better than *some* library developers that they will do it themselves. I don't think it is fruitful to partition the user space into app writers and library writers. Mark > I know that you want these cool high-level persistent communication primitives. I want them too, but I don't want them *inside* of MPI, I want them in their own portable library. For the library to be portable, its network operations should be defined using some portable low-level communication interface. If only one of those existed... > > We can deal with distribution later so it's not a pain for users to get these things installed. > > As a general rule, I would much prefer that these high-level primitives be libraries that use MPI (and are created using communicators), otherwise they will not compose with other libraries and I think will suffer the fate of the PGAS languages, Smalltalk, Lisp, GA, etc.

1 0

Re: [petsc-dev] Generality of VecScatter
by Mark F. Adams 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 11:24 AM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 09:34, Mark F. Adams <mark.adams(a)columbia.edu> wrote: >> The primitives I can readily provide are >> >> broadcast from Y to X >> reduce values on X into Y (min, max, sum, replace, etc) >> >> gather values on X into arrays for each point in Y (in some ordering, rank ordering if you like) > > this is awful. you would at least need to have a way of getting the processors that it came from, the system would have to have this info, right? > > You don't need it for the implementation. If the user wants it, they can get it trivially (gather the ranks over the same communication graph). Sometimes it doesn't matter, and these primitives won't store that by default. Not storing it also makes graph updates lighter weight because you only need to update on one side. > > > also, i think you are getting to general here, i'm not sure why anyone would want to do this but i'm sure someone would and they can just write directly to to MPI-3. > > My point is to have a more user-friendly way to offer this information. The point broadcast ("global to local") and reduce ("local to global with operation") are all you need for many operations. > > My intent is to find an abstraction that is more general than VecScatter, higher level than MPI, and that can be used for all non-synchronizing ("neighbor collective") communication patterns in a library like PETSc. OK, that makes sense at least abstractly. I'm skeptical that you are going to be able to do much with all this one sided stuff; it seems to be that you would always have the two sided data at some point and then you might setup one sided maps for repeated operations like for a MatVec that are efficient. But this is kind of trivial. I would suggest writing a non-trivail algorithm with your model. I have two ideas: 1) when a coarse AMG (use aggregation MG to me concrete) grid is constructed and you have a map (bipartite graph) with one edge for each fine grid point to a coarse grid point (not necessarily on your processor). I have too few vertices per processor so I want to reduce the number of processors used in the coarse grid. I can assume that my fine grid was well partitioned, and to keep the process local assume the fine grid was partitioned with a space filling curve, or something, such that when I aggregate processors (eg, (0-3), (4-7) ... if I reduced the number of active processor by 4) I still have decent data locality. Eventually I would like a local algorithm to improve load balance at this point, but that is more than you might want to start with. 2) Any AMR algorithm that you like. Again, you might want to punt on load balancing. Mark > Having pointwise gather/scatter allows operations involving all copies of a point (instead of only those operations expressed as a reduction with a binary operation). I think you usually don't need it, but we can provide it cheaply and without extra complexity using this abstraction.

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 12:10, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > What's the general flavor of these "high-level persistent communication > primitives"? > I think it's important to define them at least somewhat in order to > understand the rest of the discussion copied here. > I'm trying to evaluate whether my suggestion is sufficient. It can be described succinctly as offering pointwise broadcast, reduce, gather, and scatter over a bipartite graph where one side is identified as having maximum degree one and the other side---with arbitrarily high degree---can perform reductions and get the results of gathers. The specification can be provided as either a single-valued function to {(owner rank, offset), NULL} defined on the side with maximum degree one (this has the lowest overhead and can be used directly for communication) or by having the owner list shared processes (in which case the graph is inverted, but this can be done without O(size) storage and without global synchronization). What I don't want to offer (because I think it is complicated to use and hopefully unnecessary, not because I can't implement it using only moderately heavier data structures) is to have arbitrary degree on both sides.

1 0

Re: [petsc-dev] Generality of VecScatter
by Barry Smith 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 11:45 AM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 11:31, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > You seem to have the tact assumption that the choice is between MPI+X or some PGAS language, this I say is a major straw man! (And I totally agree with you PGAS language are junk and will never take off). > > What I am suggesting is there is a third alternative that is compatible with MPI (allowing people to transition from MPI to it without rewriting all current MPI based code) and is COMPLETELY library based (as MPI is). This new thing would provide a modern API suitable for many core, for GPUs and distributed computing and the API would focus on moving data and scheduling tasks. The API will be suitable for C/C++/Fortran 90. Now exact details of the API and the model are not clear to me of course. I will be pushing the MCS CS folks in this direction because I don't see any other reasonable alternative (MPI+X is fundamentally not powerful enough for the new configurations and PGAS are a joke). > > I just wrote the following in a private discussion with Barry and Matt. Copied here for the rest of you. I answered this in a private discussion and Matt and Jed and totally demolished his arguments. Barry > > Do you want to abandon MPI as a foundation for distributed memory, or do you just want a reliable way to manage multicore/SMT? I am far from convinced that we can't or shouldn't build our ultimate communication abstraction on top of MPI. In my opinion, the job of MPI is to abstract non-portable network-level details to provide a minimal set of primitives on which to write performant code and to implement libraries. Of course there is some unnecessary cruft, and there are occasional holes where networks can do cool things that are useful to libraries, but have not been exposed through MPI. But cleaning that stuff up is what I think new MPI standards should be targeting. > > I do not believe the goal of MPI is to provide abstractions that are directly usable by applications. That is the scope of domain-specific and general-purpose libraries. If an abstraction can be implemented with portable performance using primitives in MPI, then it should *not* be added to MPI. > > I know that you want these cool high-level persistent communication primitives. I want them too, but I don't want them *inside* of MPI, I want them in their own portable library. For the library to be portable, its network operations should be defined using some portable low-level communication interface. If only one of those existed... > > We can deal with distribution later so it's not a pain for users to get these things installed. > > As a general rule, I would much prefer that these high-level primitives be libraries that use MPI (and are created using communicators), otherwise they will not compose with other libraries and I think will suffer the fate of the PGAS languages, Smalltalk, Lisp, GA, etc.

1 0

Re: [petsc-dev] Generality of VecScatter
by Dmitry Karpeev 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 11:45 AM, Jed Brown <jedbrown(a)mcs.anl.gov> wrote: > On Thu, Nov 24, 2011 at 11:31, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > >> You seem to have the tact assumption that the choice is between MPI+X or >> some PGAS language, this I say is a major straw man! (And I totally agree >> with you PGAS language are junk and will never take off). >> >> What I am suggesting is there is a third alternative that is >> compatible with MPI (allowing people to transition from MPI to it without >> rewriting all current MPI based code) and is COMPLETELY library based (as >> MPI is). This new thing would provide a modern API suitable for many core, >> for GPUs and distributed computing and the API would focus on moving data >> and scheduling tasks. The API will be suitable for C/C++/Fortran 90. Now >> exact details of the API and the model are not clear to me of course. I >> will be pushing the MCS CS folks in this direction because I don't see any >> other reasonable alternative (MPI+X is fundamentally not powerful enough >> for the new configurations and PGAS are a joke). >> > > I just wrote the following in a private discussion with Barry and Matt. > Copied here for the rest of you. > > Do you want to abandon MPI as a foundation for distributed memory, or do > you just want a reliable way to manage multicore/SMT? I am far from > convinced that we can't or shouldn't build our ultimate communication > abstraction on top of MPI. In my opinion, the job of MPI is to abstract > non-portable network-level details to provide a minimal set of primitives > on which to write performant code and to implement libraries. Of course > there is some unnecessary cruft, and there are occasional holes where > networks can do cool things that are useful to libraries, but have not been > exposed through MPI. But cleaning that stuff up is what I think new MPI > standards should be targeting. > > I do not believe the goal of MPI is to provide abstractions that are > directly usable by applications. That is the scope of domain-specific and > general-purpose libraries. If an abstraction can be implemented with > portable performance using primitives in MPI, then it should *not* be added > to MPI. > > I know that you want these cool high-level persistent communication > primitives. > What's the general flavor of these "high-level persistent communication primitives"? I think it's important to define them at least somewhat in order to understand the rest of the discussion copied here. > I want them too, but I don't want them *inside* of MPI, I want them in > their own portable library. For the library to be portable, its network > operations should be defined using some portable low-level communication > interface. If only one of those existed... > > We can deal with distribution later so it's not a pain for users to get > these things installed. > > As a general rule, I would much prefer that these high-level primitives be > libraries that use MPI (and are created using communicators), otherwise > they will not compose with other libraries and I think will suffer the fate > of the PGAS languages, Smalltalk, Lisp, GA, etc. >

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 11:31, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > You seem to have the tact assumption that the choice is between MPI+X or > some PGAS language, this I say is a major straw man! (And I totally agree > with you PGAS language are junk and will never take off). > > What I am suggesting is there is a third alternative that is > compatible with MPI (allowing people to transition from MPI to it without > rewriting all current MPI based code) and is COMPLETELY library based (as > MPI is). This new thing would provide a modern API suitable for many core, > for GPUs and distributed computing and the API would focus on moving data > and scheduling tasks. The API will be suitable for C/C++/Fortran 90. Now > exact details of the API and the model are not clear to me of course. I > will be pushing the MCS CS folks in this direction because I don't see any > other reasonable alternative (MPI+X is fundamentally not powerful enough > for the new configurations and PGAS are a joke). > I just wrote the following in a private discussion with Barry and Matt. Copied here for the rest of you. Do you want to abandon MPI as a foundation for distributed memory, or do you just want a reliable way to manage multicore/SMT? I am far from convinced that we can't or shouldn't build our ultimate communication abstraction on top of MPI. In my opinion, the job of MPI is to abstract non-portable network-level details to provide a minimal set of primitives on which to write performant code and to implement libraries. Of course there is some unnecessary cruft, and there are occasional holes where networks can do cool things that are useful to libraries, but have not been exposed through MPI. But cleaning that stuff up is what I think new MPI standards should be targeting. I do not believe the goal of MPI is to provide abstractions that are directly usable by applications. That is the scope of domain-specific and general-purpose libraries. If an abstraction can be implemented with portable performance using primitives in MPI, then it should *not* be added to MPI. I know that you want these cool high-level persistent communication primitives. I want them too, but I don't want them *inside* of MPI, I want them in their own portable library. For the library to be portable, its network operations should be defined using some portable low-level communication interface. If only one of those existed... We can deal with distribution later so it's not a pain for users to get these things installed. As a general rule, I would much prefer that these high-level primitives be libraries that use MPI (and are created using communicators), otherwise they will not compose with other libraries and I think will suffer the fate of the PGAS languages, Smalltalk, Lisp, GA, etc.

1 0

Re: [petsc-dev] Generality of VecScatter
by Barry Smith 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 9:51 AM, Mark F. Adams wrote: > Barry, > > I totally disagree. About 5 years ago a lot of lumpenproletariat CS people were crowing that MPI was dead and after a few years of naval gazing w/o being able to compete the sentence "and will be replaced with ..." they quietly resigned themselves to the fact that MPI will be on top for the vast majority of apps for the foreseeable future. I think anyone with their feet on the ground, even the most pro future languages people like Kathy Yelick, sees MPI being in the mix for a long time. Now a days I see lots of "MPI + ?" on slides, or even "MPI + OpenMP + ?" but PGAS languages are still at the fringes. You seem to have the tact assumption that the choice is between MPI+X or some PGAS language, this I say is a major straw man! (And I totally agree with you PGAS language are junk and will never take off). What I am suggesting is there is a third alternative that is compatible with MPI (allowing people to transition from MPI to it without rewriting all current MPI based code) and is COMPLETELY library based (as MPI is). This new thing would provide a modern API suitable for many core, for GPUs and distributed computing and the API would focus on moving data and scheduling tasks. The API will be suitable for C/C++/Fortran 90. Now exact details of the API and the model are not clear to me of course. I will be pushing the MCS CS folks in this direction because I don't see any other reasonable alternative (MPI+X is fundamentally not powerful enough for the new configurations and PGAS are a joke). Barry Very crudely this new thing could be thought of as MPI - all point to point stuff + neighbor communication (with all communication including Allreduce asynchronize). > > Mark > > On Nov 23, 2011, at 11:22 PM, Barry Smith wrote: > >> >> These guys are making a very big strategic mistake. They cannot expect to get any funding at all if they continue to purse MPI when the acting and presumably next ASCR director believes with every fiber of his being that MPI is dead. They are writing the death sentence to computer science at ANL. >> >> Barry >> >> >> On Nov 23, 2011, at 6:28 PM, Jed Brown wrote: >> >>> I had a useful conversation with the MPICH guys today about the unstructured communication primitives that Mark, Matt, Barry, and I have been discussing. It's looking like we can do a very thin communication library that has the nice semantics I was looking for, namely that the local-to-global is stored only as indices in the local space. To implement the communication primitives, the owner of a global node never needs to know how many or which processes have that point in their local space. There is an MPI-3 feature that we can use to elegantly avoid two-way knowledge for pointwise gather/scatter. (We can always implement the same interface using vanilla MPI-1, but the MPI-2/3 implementation would have less overhead.) >>> >>> If I/we write this layer, VecScatter (with arbitrary data types, etc) could be implemented very easily on top of it. I'm in no rush to do this, but I could imagine getting there eventually. The VecScatter interface allows some things that might not be important. For example, any process can specify an edge in the communication graph, even if it does not own the source or the destination vertex. Also, both source and destination vertices can have degree higher than one. We can even put a link between the same points twice (effectively multiplying that contribution by 2 when using ADD_VALUES). I don't know if this ever makes semantic sense, but the interface allows it. >>> >>> I wonder if we can express all useful communication with a more restrictive interface similar to a local-to-global map (but mapping between any vectors) where one side (typically called "local", but doesn't need to actually be a local Vec) has at most one edge. >>> >>> What weird things do people use VecScatter for that might break with this more restrictive model? >> >> >

1 0