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

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

25 Nov '11

On Fri, Nov 25, 2011 at 09:45, Mark F. Adams <mark.adams(a)columbia.edu>wrote: > So you want MPI to provide an incremental path to a model that will work > at exa-scale and pthreads are part of that? So you are in the MPI + > pthreads camp? I don't know what Barry wants, but I like the idea of building the library interface that we want on top of MPI+pthreads. I see them merely as portable network- and kernels-level abstractions, not as anything intended to provide a good interface for applications to call directly, or even to use directly when implementing most PETSc functionality. It is a noble goal to offer a unified view of shared/threads and distributed memory. I don't know how possible this is, so it always involve some explicit hierarchy. The distributed-memory primitives might just involve some layout informed by NUMA, followed by threads or CUDA-style kernels run locally. I would really like to see some performance numbers for OpenCL running on CPUs. It would make our life simpler (once OpenCL supports indirect calls) if we could just use that, but I'm not convinced that it will deliver good performance due to the different memory model.

1 0

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

25 Nov '11

On Fri, Nov 25, 2011 at 09:38, Mark F. Adams <mark.adams(a)columbia.edu>wrote: > My point is that at some point the rubber has to hit the road and you need > two side information. You can then set up pointers for some fast one-sided > stuff, and that is fine but you seem to agree that this is trivial. Its > not clear to me that your model is not simply removing some (redundant) > data from the user space, while it is probably in the MPI library. > Whether this information is ever visible inside the MPI stack is dependent on the network. In general, it is never stored at once within the stack and the operations may be done without involving the CPU on the owning process (some network cards can do these operations directly on memory). If the MPI stack wanted to, it could log these operations, but I really meant it when I said it's not needed. Even with some funky implementation that built full two-sided information internally, I think the simpler user-level abstraction would be worthwhile. > > This information is communicated to the ghosters of that point (again > without knowing how many there are), > > > But you knew how many there were, and chose to forget it, and the MPI > layer must know how many there are so it knows when its done communicating. > I'm not sure how you insure correctness with your model. > I never knew. We can ask: what is required to add another level of ghosting? With my model, the owner never needs to be informed that some procs are ghosting another level, nor be aware what those ghosted nodes are. It may place some data in an array for the "pointwise broadcast" of connectivity, but it doesn't need semantic knowledge that that information will used to increase the ghosting. Similarly, any process can stop ghosting a point without informing the owner in any way. Completion comes through MPI_Win_fence() which is collective, but not globally synchronizing (so neighbor communication must have completed, but it's not like an MPI_Barrier or MPI_Allreduce. > 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. > > > How do you load balance with a local partitioner? You said you wanted a local algorithm to improve load balance. I took that to mean that you would redistribute within a subcommunicator and, with simple communication, inform the rest of the processes of the new partition. I think this will work fine. What did you have in mind?

1 0

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

25 Nov '11

Your instance on a library model seems reasonable if language support does not give you much better performance/programmability/etc. And I did not see that you were talking about threads, I was thinking you were looking at an event driven thing like CHARM++. So you want MPI to provide an incremental path to a model that will work at exa-scale and pthreads are part of that? So you are in the MPI + pthreads camp? Mark On Nov 24, 2011, at 2:27 PM, Barry Smith wrote: > > On Nov 24, 2011, at 12:52 PM, Mark F. Adams wrote: > >> >> 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. > > Programming with pthreads is library based programming. There is an API that you call in your language with function calls from your code to do stuff, it is in no way an extension to the language. Now there are some issues with the pthread API and I am not advocating it but just using it as an example of how flexible parallel programming can be done on-node using a purely library based system. > > > Barry > >> >> 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 25 Nov '11

25 Nov '11

On Nov 24, 2011, at 2:12 PM, Jed Brown wrote: > 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, No, lets keep it simple for now. > or you just want to do something simple like rank-order aggregation? Thats fine. > In my model, the owner of a point would somehow (e.g. by calling a partitioner) determine the new owner of that point. My point is that at some point the rubber has to hit the road and you need two side information. You can then set up pointers for some fast one-sided stuff, and that is fine but you seem to agree that this is trivial. Its not clear to me that your model is not simply removing some (redundant) data from the user space, while it is probably in the MPI library. > This information is communicated to the ghosters of that point (again without knowing how many there are), But you knew how many there were, and chose to forget it, and the MPI layer must know how many there are so it knows when its done communicating. I'm not sure how you insure correctness with your model. > 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. How do you load balance with a local partitioner? Mark > > > 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] programming model for PETSc
by Jed Brown 25 Nov '11

25 Nov '11

On Fri, Nov 25, 2011 at 09:02, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > This is a continuation of the thread started by Matt stating he wanted to > use "vectorization" as the low level common kernels and I asked him for > syntax (for example CUDA, OpenCL, ....) You are talking about something > completely different and not relevant for that thread. > Okay, I misunderstood your question, but I think both steps are relevant. The distribution we want between threads isn't computed with the same methodology as a distribution between processes (certainly not in the case of CUDA). I think we will always have some sort of pattern of applying a transformation on the data (which may or may not involve network communication), applying a vectorized operation, and reducing the result. I don't have concrete suggestions for syntax or even primitives for this multi-level case, but I think the communication can probably be described by adding a partition or coloring to the CPU-based communication ideas we were discussing in the other thread.

1 0

Re: [petsc-dev] programming model for PETSc
by Barry Smith 25 Nov '11

25 Nov '11

Jed, This is a continuation of the thread started by Matt stating he wanted to use "vectorization" as the low level common kernels and I asked him for syntax (for example CUDA, OpenCL, ....) You are talking about something completely different and not relevant for that thread. Barry ] On Nov 25, 2011, at 1:43 AM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 21:39, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > I have no idea what you are talking about. What is "local to global" and what are "these primitives"? > > I wrote an earlier email where I outlined some primitives, namely a "pointwise" broadcast, reduce, fetch-and-add, gather, and scatter. Only the first three are truly "primitives", but all five are directly useful to applications. For these, we identify a "local" and "global" space. The ownership of the send and receive buffers need not be local and global, but I'm using these names because they are most familiar to us. The specification of the communication graph _always_ resides in the local space, and the local space has the restriction that each point maps to at most one global point. Is usual, several local points may map to the same global point. > > All communication is initiated by the local side, although the global side may be involved to prepare buffers so that we expose useful collective semantics. > > > Example, how do I write a triangular solve using "local to global" and "these primatives? > > You want parallel sparse triangular solve? Which algorithm do you want to use? > > > How do I write application of a stencil operator using "local to global" and "these primatives? > > How do I write sparse matrix vector product using "local to global" and "these primatives? > > These two look the same, broadcast the values from global to local (natural implementation is that local processes call MPI_Get(), completed when all call MPI_Win_fence()). > > For transpose multiply, we apply the matrix and finish with reduction on the destination global space (naturally implemented with MPI_Accumulate() called by senders, completed when all call MPI_Win_fence()). This is the same communication pattern as symmetric additive Schwarz and Neumann DD methods/storage formats. > > These are the simplest building cases, I think redistributing a mesh after partitioning is a more interesting operation. I explained how that would be done earlier in this thread, but I understand that there is a difference between explaining in an email and showing working code. I'll get busy with the latter in a couple weeks.

1 0

Re: [petsc-dev] programming model for PETSc
by Jed Brown 25 Nov '11

25 Nov '11

On Thu, Nov 24, 2011 at 21:39, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > I have no idea what you are talking about. What is "local to global" and > what are "these primitives"? > I wrote an earlier email where I outlined some primitives, namely a "pointwise" broadcast, reduce, fetch-and-add, gather, and scatter. Only the first three are truly "primitives", but all five are directly useful to applications. For these, we identify a "local" and "global" space. The ownership of the send and receive buffers need not be local and global, but I'm using these names because they are most familiar to us. The specification of the communication graph _always_ resides in the local space, and the local space has the restriction that each point maps to at most one global point. Is usual, several local points may map to the same global point. All communication is initiated by the local side, although the global side may be involved to prepare buffers so that we expose useful collective semantics. > > Example, how do I write a triangular solve using "local to global" > and "these primatives? > You want parallel sparse triangular solve? Which algorithm do you want to use? > > How do I write application of a stencil operator using "local to > global" and "these primatives? > > How do I write sparse matrix vector product using "local to global" > and "these primatives? > These two look the same, broadcast the values from global to local (natural implementation is that local processes call MPI_Get(), completed when all call MPI_Win_fence()). For transpose multiply, we apply the matrix and finish with reduction on the destination global space (naturally implemented with MPI_Accumulate() called by senders, completed when all call MPI_Win_fence()). This is the same communication pattern as symmetric additive Schwarz and Neumann DD methods/storage formats. These are the simplest building cases, I think redistributing a mesh after partitioning is a more interesting operation. I explained how that would be done earlier in this thread, but I understand that there is a difference between explaining in an email and showing working code. I'll get busy with the latter in a couple weeks.

1 0

Re: [petsc-dev] programming model for PETSc
by Barry Smith 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 7:33 PM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 18:56, Matthew Knepley <knepley(a)gmail.com> wrote: > I think the idea of a local point of view is fundamental, not just for parallelism. We use LocalToGlobal mappings in FS so that yu do not have > to know about other fields, just the same as you should not have to know about other processes. > > I agree, local-to-global is the key to scalability. The challenge is making everything run along scalable pipes the way local-to-global does. I think we can do that with these primitives. Jed, I have no idea what you are talking about. What is "local to global" and what are "these primitives"? Example, how do I write a triangular solve using "local to global" and "these primatives? How do I write application of a stencil operator using "local to global" and "these primatives? How do I write sparse matrix vector product using "local to global" and "these primatives? etc etc Barry

1 0

Re: [petsc-dev] programming model for PETSc
by Barry Smith 24 Nov '11

24 Nov '11

On Nov 24, 2011, at 6:41 PM, Jed Brown wrote: > On Thu, Nov 24, 2011 at 18:30, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > In any event, this business of storing explicit ranks/offsets for the ghost indices is sort of antithetical to the current > PetscLayout-based approach of indices having parallel semantics from the outset. A lot of conceptual difficulties > in Sieve and MOAB (and the need for the extra objects such as Overlap and ParallelComm (sic!)) stem from a lack of > a global address space. > > Global addresses and (rank, offset) are equivalent modulo MPI_Scan() which costs essentially the same as MPI_Reduce(). Not free, but not huge when done in setup. I think global indices are usually easier for users to play with (if they need anything that has global semantics, local indices combined with a local-to-global map is even better when sufficient), but they eventually need to be converted to (rank, offset) for communication (MPI does not know about a "global index" and I don't think it should.) Why don't you add PetscGlobalIndexToRankLocalIndex(MPI_Comm,PetscInt n, PetscInt *indices,PetscInt *ranklocalindex); and PetscRankLocalIndexToGlobalIndex() (or better names) to PETSc as utilities if it is so simple and needed everywhere? Barry

1 0

Re: [petsc-dev] programming model for PETSc
by Jed Brown 24 Nov '11

24 Nov '11

On Thu, Nov 24, 2011 at 18:56, Matthew Knepley <knepley(a)gmail.com> wrote: > I think the idea of a local point of view is fundamental, not just for > parallelism. We use LocalToGlobal mappings in FS so that yu do not have > to know about other fields, just the same as you should not have to know > about other processes. > I agree, local-to-global is the key to scalability. The challenge is making everything run along scalable pipes the way local-to-global does. I think we can do that with these primitives.

1 0