- mpiwg-rma - mailman3.cels.anl.gov

Re: [Mpi3-rma] Use cases for RMA
by Torsten Hoefler 03 Mar '10

03 Mar '10

Bill, I do see another use-case which is not simple in MPI-2.2: simple nearest neighbor (stencil) updates. For such operations, it is often beneficial to start computation at the receiver as soon as the data from the first neighbor arrived. So what one would probably like to do is: (1) initiate the communication to all neighbors (nonblocking of course) (2) check some local completion flag (ideally some kind of counter which is mutated after some neighbor placed his data, a single counter because we would not like to poll N memory locations for N neighbors) (3) check which neighbor completed and perform computation on the received data (4) check for completion (leave polling if all neighbors completed) Step (2) seems tricky with MPI-2.2. One could use passive mode target and MPI_Accumulate() but (1) there are no ordering guarantees between puts and accumulates (which is good) so that one would need to open an exclusive access epoch locally for each poll in order to ensure consistency. There might be easier/better ways to do this, but we should add this to our use-cases. All the Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Research Associate Blue Waters Directorate | University of Illinois 1205 W Clark Street | Urbana, IL, 61801 NCSA Building | +01 (217) 244-7736

1 0

Re: [Mpi3-rma] Use cases for RMA
by Torsten Hoefler 03 Mar '10

03 Mar '10

Hello Bill, one more example, which would not work too well in MPI-2.2 is the implementation of parallel graph algorithms. With regards to the efficient parallelization, there are some easy ones (PageRank, Connected Components etc.), but there are also much more demanding algorithms such as SSSP (e.g., \Delta stepping)or Betweenness Centrality. Those algorithms commonly build upon level-wise graph traversals (BFS) which needs remote queue updates. A common strategy to parallelize BFS is to distribute the graph vertices (this has its own load-balancing issues) and have a distributed queue with local pop(), remote push(), and global ifempty() semantics. In this model, computation (the little there is) is pushed towards the owner of the vertex, i.e., into the queue of the owning process. This is commonly implemented with a polling active-message-like layer on top of MPI (see Parallel Boost Graph Library) and pseudo-code can be found in http://www.unixer.de/publications/img/hoefler-dsde-protocols.pdf (Algorithm 3, I have C++ source code if anybody is interested). However, this obviously causes a lot of unnecessary overhead at the receive side (polling and unnecessary queue matching, and we also don't need MPI's ordering semantics). An active message (or remote procedure call, or an MPI_Accumulate with an operation that conditionally pushes on a remote queue) could eliminate those overheads and one could perform the DSDE steps (conditional insert into queue) in Algorithm 5 much more efficient. It would be even better if MPI would offer us some termination-detection mechanism in case we do not need level-wise traversals (some algorithms allow that, e.g., label-correcting SSSPs). One might think that remote locks and updates could be used to protect and access the queue, however, those operations introduce a large amount of lock traffic and effectively multiplies the latency. Many such (sparse) graph algorithms are latency-bound and one would like to update remote queues as rapidly as possible. All the Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Research Associate Blue Waters Directorate | University of Illinois 1205 W Clark Street | Urbana, IL, 61801 NCSA Building | +01 (217) 244-7736

1 0

Re: [Mpi3-rma] Use cases for RMA
by Bronis R. de Supinski 03 Mar '10

03 Mar '10

Tom: My recollection is that you had some difficulty trying to use MPI for the distributed table with caching implementation besides performance. Were you looking at MPI one sided communication? If so, what was the issue again? Bronis On Wed, 3 Mar 2010, William Gropp wrote: > It sounds like this doesn't require anything more than what's already > been requested by Jeff. That is, MPI-2 RMA is fine as long as the > implementation is efficient (a quality of implementation issue, best > addressed with benchmarks at procurement, rather than changing the > standard). Let me know if I'm missing something. > > Bill > > On Mar 3, 2010, at 9:45 AM, Bronis R. de Supinski wrote: > > > > > Bill: > > > > One use case that I am familiar with at LLNL is to > > distribute large read-only (write-once) tables. We > > have libraries with this access pattern; the current > > method is to replicate the tables in all MPI processes. > > We have done a prototype implementation using GAs to > > distribute the table. We also need support for caching > > values locally. I think a good RMA implementation > > would allow us to build a generic implementation of > > the distribute and cache functionality... > > > > Bronis > > > > > > On Wed, 3 Mar 2010, William Gropp wrote: > > > >> I went through the mail that was sent out in response to our request > >> for use cases, and I must say it was underwhelming. I've included a > >> short summary below; based on this, we aren't looking at the correct > >> needs. I don't think that these are representative of *all* of the > >> needs of RMA, but without good use cases, I don't see how we can > >> justify any but the most limited extensions/changes to the current > >> design. Please (a) let me know if I overlooked something and (b) > >> send > >> me (and the list) additional use cases. For example, we haven't > >> included any of the issues needed to implement PGAS languages, nor > >> have we addressed the existing SHMEM codes. Do we simply say that a > >> high-quality implementation will permit interoperation with whatever > >> OpenSHMEM is? And what do we do about the RMI issue that one of the > >> two use cases that we have raises? > >> > >> Basically, I received two detailed notes for the area of Quantum > >> Chemistry. In brief: > >> > >> MPI-2 RMA is already adequate for most parts, as long as the > >> implementation makes progress (as it is required to) on passive > >> updates. Requires get or accumulate; rarely requires put. > >> Dynamic load balancing (a related but separate issue) needs some sort > >> of RMW. (Thanks to Jeff Hammond) > >> > >> More complex algorithms and data structures appear to require remote > >> method invocation (RMI). Sparse tree updates provide one example. > >> (Thanks to Robert Harrison) > >> > >> Bill > >> > >> > >> William Gropp > >> Deputy Director for Research > >> Institute for Advanced Computing Applications and Technologies > >> Paul and Cynthia Saylor Professor of Computer Science > >> University of Illinois Urbana-Champaign > >> > >> > >> > >> > >> _______________________________________________ > >> mpi3-rma mailing list > >> mpi3-rma(a)lists.mpi-forum.org > >> http://**lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma > >> > >> > > _______________________________________________ > > mpi3-rma mailing list > > mpi3-rma(a)lists.mpi-forum.org > > http://*lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma > > William Gropp > Deputy Director for Research > Institute for Advanced Computing Applications and Technologies > Paul and Cynthia Saylor Professor of Computer Science > University of Illinois Urbana-Champaign > > > > > >

1 0

Re: [Mpi3-rma] Use cases for RMA
by William Gropp 03 Mar '10

03 Mar '10

It sounds like this doesn't require anything more than what's already been requested by Jeff. That is, MPI-2 RMA is fine as long as the implementation is efficient (a quality of implementation issue, best addressed with benchmarks at procurement, rather than changing the standard). Let me know if I'm missing something. Bill On Mar 3, 2010, at 9:45 AM, Bronis R. de Supinski wrote: > > Bill: > > One use case that I am familiar with at LLNL is to > distribute large read-only (write-once) tables. We > have libraries with this access pattern; the current > method is to replicate the tables in all MPI processes. > We have done a prototype implementation using GAs to > distribute the table. We also need support for caching > values locally. I think a good RMA implementation > would allow us to build a generic implementation of > the distribute and cache functionality... > > Bronis > > > On Wed, 3 Mar 2010, William Gropp wrote: > >> I went through the mail that was sent out in response to our request >> for use cases, and I must say it was underwhelming. I've included a >> short summary below; based on this, we aren't looking at the correct >> needs. I don't think that these are representative of *all* of the >> needs of RMA, but without good use cases, I don't see how we can >> justify any but the most limited extensions/changes to the current >> design. Please (a) let me know if I overlooked something and (b) >> send >> me (and the list) additional use cases. For example, we haven't >> included any of the issues needed to implement PGAS languages, nor >> have we addressed the existing SHMEM codes. Do we simply say that a >> high-quality implementation will permit interoperation with whatever >> OpenSHMEM is? And what do we do about the RMI issue that one of the >> two use cases that we have raises? >> >> Basically, I received two detailed notes for the area of Quantum >> Chemistry. In brief: >> >> MPI-2 RMA is already adequate for most parts, as long as the >> implementation makes progress (as it is required to) on passive >> updates. Requires get or accumulate; rarely requires put. >> Dynamic load balancing (a related but separate issue) needs some sort >> of RMW. (Thanks to Jeff Hammond) >> >> More complex algorithms and data structures appear to require remote >> method invocation (RMI). Sparse tree updates provide one example. >> (Thanks to Robert Harrison) >> >> Bill >> >> >> William Gropp >> Deputy Director for Research >> Institute for Advanced Computing Applications and Technologies >> Paul and Cynthia Saylor Professor of Computer Science >> University of Illinois Urbana-Champaign >> >> >> >> >> _______________________________________________ >> mpi3-rma mailing list >> mpi3-rma(a)lists.mpi-forum.org >> http://*lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma >> >> > _______________________________________________ > mpi3-rma mailing list > mpi3-rma(a)lists.mpi-forum.org > http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma William Gropp Deputy Director for Research Institute for Advanced Computing Applications and Technologies Paul and Cynthia Saylor Professor of Computer Science University of Illinois Urbana-Champaign

1 0

Re: [Mpi3-rma] Use cases for RMA
by Bronis R. de Supinski 03 Mar '10

03 Mar '10

Bill: One use case that I am familiar with at LLNL is to distribute large read-only (write-once) tables. We have libraries with this access pattern; the current method is to replicate the tables in all MPI processes. We have done a prototype implementation using GAs to distribute the table. We also need support for caching values locally. I think a good RMA implementation would allow us to build a generic implementation of the distribute and cache functionality... Bronis On Wed, 3 Mar 2010, William Gropp wrote: > I went through the mail that was sent out in response to our request > for use cases, and I must say it was underwhelming. I've included a > short summary below; based on this, we aren't looking at the correct > needs. I don't think that these are representative of *all* of the > needs of RMA, but without good use cases, I don't see how we can > justify any but the most limited extensions/changes to the current > design. Please (a) let me know if I overlooked something and (b) send > me (and the list) additional use cases. For example, we haven't > included any of the issues needed to implement PGAS languages, nor > have we addressed the existing SHMEM codes. Do we simply say that a > high-quality implementation will permit interoperation with whatever > OpenSHMEM is? And what do we do about the RMI issue that one of the > two use cases that we have raises? > > Basically, I received two detailed notes for the area of Quantum > Chemistry. In brief: > > MPI-2 RMA is already adequate for most parts, as long as the > implementation makes progress (as it is required to) on passive > updates. Requires get or accumulate; rarely requires put. > Dynamic load balancing (a related but separate issue) needs some sort > of RMW. (Thanks to Jeff Hammond) > > More complex algorithms and data structures appear to require remote > method invocation (RMI). Sparse tree updates provide one example. > (Thanks to Robert Harrison) > > Bill > > > William Gropp > Deputy Director for Research > Institute for Advanced Computing Applications and Technologies > Paul and Cynthia Saylor Professor of Computer Science > University of Illinois Urbana-Champaign > > > > > _______________________________________________ > mpi3-rma mailing list > mpi3-rma(a)lists.mpi-forum.org > http://*lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma > >

1 0

[Mpi3-rma] Use cases for RMA
by William Gropp 03 Mar '10

03 Mar '10

I went through the mail that was sent out in response to our request for use cases, and I must say it was underwhelming. I've included a short summary below; based on this, we aren't looking at the correct needs. I don't think that these are representative of *all* of the needs of RMA, but without good use cases, I don't see how we can justify any but the most limited extensions/changes to the current design. Please (a) let me know if I overlooked something and (b) send me (and the list) additional use cases. For example, we haven't included any of the issues needed to implement PGAS languages, nor have we addressed the existing SHMEM codes. Do we simply say that a high-quality implementation will permit interoperation with whatever OpenSHMEM is? And what do we do about the RMI issue that one of the two use cases that we have raises? Basically, I received two detailed notes for the area of Quantum Chemistry. In brief: MPI-2 RMA is already adequate for most parts, as long as the implementation makes progress (as it is required to) on passive updates. Requires get or accumulate; rarely requires put. Dynamic load balancing (a related but separate issue) needs some sort of RMW. (Thanks to Jeff Hammond) More complex algorithms and data structures appear to require remote method invocation (RMI). Sparse tree updates provide one example. (Thanks to Robert Harrison) Bill William Gropp Deputy Director for Research Institute for Advanced Computing Applications and Technologies Paul and Cynthia Saylor Professor of Computer Science University of Illinois Urbana-Champaign

1 0

[Mpi3-rma] Updated RMA proposal
by Torsten Hoefler 02 Mar '10

02 Mar '10

Hello all, I still believe that small fixes to the existing RMA rather than a complete redesign could lead to a better RMA interface for MPI. I updated my proposal from November with all comments I received so far. The major changes are: - P2P windows are gone now (the problems of establishing them seemed to outweigh the benefits and object-oriented codes can do their own memory management inside an existing window) - the windows have been replaced by a p2p synchronization based on lock/unlock. I think splitting up unlock into flush (which is essentially a wait) and unlock (which is now only unlock) would be beneficial. However, this would break backwards compatibility! (needs further discussion) - collective window allocation (I am getting more and more convinced that we should have this in the standard, just like MPI_Alloc_mem, just collectively and automatically registered as window). An alternative would be to define a collective MPI_Alloc_mem, which I would find confusing because all this seems to be good for would be memory windows. - collective operation registration (in order to use user-defined ops in MPI_[Get_]Accumulate[_get] calls. This is a stub right now but would be similar to MPI_Op_create, just collectively). Remember, if we allow operations, then we enable very mighty programming techniques with accumulate and friends. - MPI_RMA_query is slightly reworded Everything is in http://www.unixer.de/sec/one-side-2.pdf (new text is red, erased text green, and comments blue). All the Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Research Associate Blue Waters Directorate | University of Illinois 1205 W Clark Street | Urbana, IL, 61801 NCSA Building | +01 (217) 244-7736

1 0

[Mpi3-rma] RMA phone call on Wednesday
by Rajeev Thakur 01 Mar '10

01 Mar '10

We are having a phone call this Wednesday at 11am Central to discuss Pavan's proposal before the meeting next week. The time will not work for everyone, but whoever can participate, please do. The current version of the proposal is at www.mcs.anl.gov/~balaji/tmp/rma/rma-1.5.1.pdf . Rajeev Date: 2010-03-03 (Wednesday) Time: 11am Central, 9am Pacific, noon Eastern Passcode: 11797 Domestic dial number: 888 769 8760 International dial number: 212 287 1666

1 0

Re: [Mpi3-rma] RMA proposal
by Pavan Balaji 28 Feb '10

28 Feb '10

I have received a few comments so far, mostly on additional text to clarify a few things. Here's a new draft that adds these explanations (no semantics changes compared to 1.5): http://www.mcs.anl.gov/~balaji/tmp/rma/rma-1.5.1.pdf I urge everyone to please take a look at the document if you are interested in participating in the RMA discussion during the next Forum meeting. Trying to understand the semantics at the meeting would be a waste of time for everyone. Regards, -- Pavan On 02/24/2010 02:16 PM, Pavan Balaji wrote: > Based on some additional internal discussion and comments here, there's > a new version of the draft put up: > http://www.mcs.anl.gov/~balaji/tmp/rma/rma-1.5.pdf > > -- Pavan > > On 02/23/2010 12:51 PM, Pavan Balaji wrote: >> All, >> >> I've created a new RMA proposal >> (http://www.mcs.anl.gov/~balaji/tmp/rma/rma-1.4.pdf) and would like to >> initiate some discussion on it. >> >> The general idea is similar to the lock/unlock primitives in MPI-2.2, >> but the main difference is that it decouples synchronization of requests >> from lock/unlock itself. I've added some discussion items at places >> where there is no clear answer one way or the other. There are some >> examples in the end to give you a feel of how it can be used. >> >> In order to not confuse with the semantics of MPI-2.2, I've forked off a >> new concept called "Portals" which is similar to "Windows". We can >> either keep it as a separate chapter (or sub-chapter within RMA); or we >> can decide to merge it back into the concept of "Windows" as a new >> synchronization primitive. Names and syntax are always open to change. >> >> Look forward to your comments. >> >> Thanks, >> >> -- Pavan >> > -- Pavan Balaji http://www.mcs.anl.gov/~balaji

1 0

Re: [Mpi3-rma] RMA proposal
by Pavan Balaji 24 Feb '10

24 Feb '10

Based on some additional internal discussion and comments here, there's a new version of the draft put up: http://www.mcs.anl.gov/~balaji/tmp/rma/rma-1.5.pdf -- Pavan On 02/23/2010 12:51 PM, Pavan Balaji wrote: > All, > > I've created a new RMA proposal > (http://www.mcs.anl.gov/~balaji/tmp/rma/rma-1.4.pdf) and would like to > initiate some discussion on it. > > The general idea is similar to the lock/unlock primitives in MPI-2.2, > but the main difference is that it decouples synchronization of requests > from lock/unlock itself. I've added some discussion items at places > where there is no clear answer one way or the other. There are some > examples in the end to give you a feel of how it can be used. > > In order to not confuse with the semantics of MPI-2.2, I've forked off a > new concept called "Portals" which is similar to "Windows". We can > either keep it as a separate chapter (or sub-chapter within RMA); or we > can decide to merge it back into the concept of "Windows" as a new > synchronization primitive. Names and syntax are always open to change. > > Look forward to your comments. > > Thanks, > > -- Pavan > -- Pavan Balaji http://www.mcs.anl.gov/~balaji

1 0