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

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

03 Mar '10

Thanks. More comments inline. On Mar 3, 2010, at 3:40 PM, Manojkumar Krishnan wrote: > > Bill, > > Please scroll for my comments. > > On Wed, 3 Mar 2010, William Gropp wrote: > >> Thanks. I've added some comments inline. >> >> On Mar 3, 2010, at 1:23 PM, Manojkumar Krishnan wrote: >> >>> >>> Bill, >>> >>> Here are some of the MPI RMA requirements for Global Arrays (GA) and >>> ARMCI. ARMCI is GA's runtime system. GA/ARMCI exploits native >>> network communication interfaces and system resources (such as >>> shared >>> memory) to achieve the best possible performance of the remote >>> memory >>> access/one-sided communication. GA/ARMCI relies *heavily* on >>> optimized >>> contiguous and non-contiguous RMA operations (get/put/acc). >>> >>> For GA/ARMCI and its applications, below are some specfic examples >>> of >>> operations that are hard to achieve in MPI-2 RMA. >>> >>> 1. Memory Allocation: (This might be an implementation issue) The >>> user or >>> library implementors should be able to allocate memory (e.g. shared >>> memory), and register with MPI. This is useful in case of Global >>> Arrays/ARMCI, which use RMA across nodes and shared memory within >>> nodes. >>> ARMCI allocates shared memory segment, and pins/registers with the >>> network. >> >> MPI already provides MPI_Alloc_mem , though this is not necessarily >> shared memory usable by other processes. But the MPI implementation >> could allocate this from a shared memory pool and perform one-sided >> operations using load-store. Do you need something different? >> > > The thing is, this involves additional copy via RMA_Get. Is it > possible for other processes within the same SMP node access the > memory > directly (rather than get/put using load-store). > > For example something like this. In GA, you get *direct* access > (pointer) to memory regions allocated by processes within SMP node. If > proc 0 and 1 are in the same node, proc 1 can access proc 0's region > without explict get/put (i.e. proc 1 gets a pointer to this region). What we may need is a way to provide shared memory (provided by some other service) to an MPI Window, and arrange the access/completion for it. This is something we should look at. > >>> >>> 2. Locks: Should be made optional to keep the RMA programming model >>> simple. If the user doesnot require concurrency, then locks are >>> unnecessary. Enforcing to use locks as default might introduce >>> unnecessary bugs if not carefully programmed (esp. at the level of >>> of >>> extreme scale systems, it is hard to debug). >>> >> >> You need something to provide for local and remote completion. Do >> you >> mean to have blocking RMA operations that (in MPI terms) essentially >> act as lock-RMA_operation-unlock? > > Not really, I meant - performing RMA operations without locks, if > locks > are not needed. Instead of making it default, we can have locks as > optional. I still don't understand what the problem is with "locks" (note that the name is poorly chosen, it isn't really a lock in the usual sense). What lock/unlock does is simple indicate "begin RMA access at target" and "end RMA access at target", with the option of permitting exclusive access to the target window. In the below, I've put what I think are the equivalent MPI RMA calls: > > With respect to completion and synchronization, here is an example > of how > it is done in ARMCI. > > ARMCI_Put: Ensures local completion and source buffer is safe to reuse Lock/Put/Unlock . Permits concurrent non-overlapping destination updates if shared mode is selected. > > ARMCI_NbPut: Non-blocking put. User has to call wait() to reuse source > buffer. Lock/Put . Unlock is like Wait > > ARMCI_Put(dst_proc)+ARMCI_Fence(dst_proc): Ensures local and remote > completion. Also Lock/Put/Unlock > > ARMCI_Allfence. This is collective. Ensures all outstanding RMA > operations are completed on the remote side. Mostly called with > Barrier. Win_fence (active target sync) > > ARMCI_Put_Notify/Wait. This is like light-weight message passing. > After a > (large) put, the sender can send a notify message, and the destination > process can wait on it. This is useful if send/recv is in redevous > mode and send essentially blocks for a slow receiver. In case of > Put/Put_notify, the sender can issue 2 seperate R(D)MA's and no need > to > handshake with the receiver. Thus it is relativly less synchronous. > On the > other hand, if the sender is slow, then the receiver has to wait! > > Please note that, if such a synchronization/completion is required > between source and destination, then user should avoid using RMA > (and use > Send/Recv), as this is truly 2-sided communication. > >> >>> 3. Support for non-overlapping concurrent operations in a window. >> >> MPI RMA already does this, in all of the active target modes, and in >> the passive target mode with the shared lock mode. What do you need >> that isn't supported? > > In the passive target mode, does this require some synchronization > with > the source and destination process if they are accessing non- > overlapping > operations in the same window. If so, then this might not be truly > one-sided operation. Please correct me if I am wrong. The only synchronization is that an exclusive_lock must block subsequent shared locks and must wait for executing shared locks to complete. Is the issue that you never want to check? If so, then this could be added as a Window characteristic. > >> >>> >>> 4. RMW Operation - Useful for implementing dynamic load balancing >>> algorithms (e.g. task queues/work stealing, group/global counters, >>> etc). >>> >> >> Yes, this is a major gap. Is fetch-and-increment enough, or do you >> need compare-and-swap, or a general RMI? > > For ARMCI, we need both: fetch-and-increment and compare-and-swap. A > general RMI is certainly useful, as we have plans to extend the > capability > of ARMCI to perform general RMI. > > -- > Thanks, > -Manoj. > --------------------------------------------------------------- > Manojkumar Krishnan > High Performance Computing Group > Pacific Northwest National Laboratory > Ph: (509) 372-4206 Fax: (509) 372-4720 > http://hpc.pnl.gov/people/manoj > --------------------------------------------------------------- > > >> >> Bill >> >>> The above are feature requirements rather than performance issues, >>> which >>> are implementation specific. >>> >>> If you have any questions, I would be happy to explain the above in >>> detail. >>> >>> Thanks, >>> -Manoj. >>> --------------------------------------------------------------- >>> Manojkumar Krishnan >>> High Performance Computing Group >>> Pacific Northwest National Laboratory >>> Ph: (509) 372-4206 Fax: (509) 372-4720 >>> http://hpc.pnl.gov/people/manoj >>> --------------------------------------------------------------- >>> >>> 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 >> >> >> >> >> _______________________________________________ >> 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 Manojkumar Krishnan 03 Mar '10

03 Mar '10

Bill, Please scroll for my comments. On Wed, 3 Mar 2010, William Gropp wrote: > Thanks. I've added some comments inline. > > On Mar 3, 2010, at 1:23 PM, Manojkumar Krishnan wrote: > > > > > Bill, > > > > Here are some of the MPI RMA requirements for Global Arrays (GA) and > > ARMCI. ARMCI is GA's runtime system. GA/ARMCI exploits native > > network communication interfaces and system resources (such as shared > > memory) to achieve the best possible performance of the remote memory > > access/one-sided communication. GA/ARMCI relies *heavily* on optimized > > contiguous and non-contiguous RMA operations (get/put/acc). > > > > For GA/ARMCI and its applications, below are some specfic examples of > > operations that are hard to achieve in MPI-2 RMA. > > > > 1. Memory Allocation: (This might be an implementation issue) The > > user or > > library implementors should be able to allocate memory (e.g. shared > > memory), and register with MPI. This is useful in case of Global > > Arrays/ARMCI, which use RMA across nodes and shared memory within > > nodes. > > ARMCI allocates shared memory segment, and pins/registers with the > > network. > > MPI already provides MPI_Alloc_mem , though this is not necessarily > shared memory usable by other processes. But the MPI implementation > could allocate this from a shared memory pool and perform one-sided > operations using load-store. Do you need something different? > The thing is, this involves additional copy via RMA_Get. Is it possible for other processes within the same SMP node access the memory directly (rather than get/put using load-store). For example something like this. In GA, you get *direct* access (pointer) to memory regions allocated by processes within SMP node. If proc 0 and 1 are in the same node, proc 1 can access proc 0's region without explict get/put (i.e. proc 1 gets a pointer to this region). > > > > 2. Locks: Should be made optional to keep the RMA programming model > > simple. If the user doesnot require concurrency, then locks are > > unnecessary. Enforcing to use locks as default might introduce > > unnecessary bugs if not carefully programmed (esp. at the level of of > > extreme scale systems, it is hard to debug). > > > > You need something to provide for local and remote completion. Do you > mean to have blocking RMA operations that (in MPI terms) essentially > act as lock-RMA_operation-unlock? Not really, I meant - performing RMA operations without locks, if locks are not needed. Instead of making it default, we can have locks as optional. With respect to completion and synchronization, here is an example of how it is done in ARMCI. ARMCI_Put: Ensures local completion and source buffer is safe to reuse ARMCI_NbPut: Non-blocking put. User has to call wait() to reuse source buffer. ARMCI_Put(dst_proc)+ARMCI_Fence(dst_proc): Ensures local and remote completion. ARMCI_Allfence. This is collective. Ensures all outstanding RMA operations are completed on the remote side. Mostly called with Barrier. ARMCI_Put_Notify/Wait. This is like light-weight message passing. After a (large) put, the sender can send a notify message, and the destination process can wait on it. This is useful if send/recv is in redevous mode and send essentially blocks for a slow receiver. In case of Put/Put_notify, the sender can issue 2 seperate R(D)MA's and no need to handshake with the receiver. Thus it is relativly less synchronous. On the other hand, if the sender is slow, then the receiver has to wait! Please note that, if such a synchronization/completion is required between source and destination, then user should avoid using RMA (and use Send/Recv), as this is truly 2-sided communication. > > > 3. Support for non-overlapping concurrent operations in a window. > > MPI RMA already does this, in all of the active target modes, and in > the passive target mode with the shared lock mode. What do you need > that isn't supported? In the passive target mode, does this require some synchronization with the source and destination process if they are accessing non-overlapping operations in the same window. If so, then this might not be truly one-sided operation. Please correct me if I am wrong. > > > > > 4. RMW Operation - Useful for implementing dynamic load balancing > > algorithms (e.g. task queues/work stealing, group/global counters, > > etc). > > > > Yes, this is a major gap. Is fetch-and-increment enough, or do you > need compare-and-swap, or a general RMI? For ARMCI, we need both: fetch-and-increment and compare-and-swap. A general RMI is certainly useful, as we have plans to extend the capability of ARMCI to perform general RMI. -- Thanks, -Manoj. --------------------------------------------------------------- Manojkumar Krishnan High Performance Computing Group Pacific Northwest National Laboratory Ph: (509) 372-4206 Fax: (509) 372-4720 http://hpc.pnl.gov/people/manoj --------------------------------------------------------------- > > Bill > > > The above are feature requirements rather than performance issues, > > which > > are implementation specific. > > > > If you have any questions, I would be happy to explain the above in > > detail. > > > > Thanks, > > -Manoj. > > --------------------------------------------------------------- > > Manojkumar Krishnan > > High Performance Computing Group > > Pacific Northwest National Laboratory > > Ph: (509) 372-4206 Fax: (509) 372-4720 > > http://hpc.pnl.gov/people/manoj > > --------------------------------------------------------------- > > > > 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 > > > > > _______________________________________________ > mpi3-rma mailing list > mpi3-rma(a)lists.mpi-forum.org > http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-rma >

1 0

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

03 Mar '10

Thanks. I've added some comments inline. On Mar 3, 2010, at 1:23 PM, Manojkumar Krishnan wrote: > > Bill, > > Here are some of the MPI RMA requirements for Global Arrays (GA) and > ARMCI. ARMCI is GA's runtime system. GA/ARMCI exploits native > network communication interfaces and system resources (such as shared > memory) to achieve the best possible performance of the remote memory > access/one-sided communication. GA/ARMCI relies *heavily* on optimized > contiguous and non-contiguous RMA operations (get/put/acc). > > For GA/ARMCI and its applications, below are some specfic examples of > operations that are hard to achieve in MPI-2 RMA. > > 1. Memory Allocation: (This might be an implementation issue) The > user or > library implementors should be able to allocate memory (e.g. shared > memory), and register with MPI. This is useful in case of Global > Arrays/ARMCI, which use RMA across nodes and shared memory within > nodes. > ARMCI allocates shared memory segment, and pins/registers with the > network. MPI already provides MPI_Alloc_mem , though this is not necessarily shared memory usable by other processes. But the MPI implementation could allocate this from a shared memory pool and perform one-sided operations using load-store. Do you need something different? > > 2. Locks: Should be made optional to keep the RMA programming model > simple. If the user doesnot require concurrency, then locks are > unnecessary. Enforcing to use locks as default might introduce > unnecessary bugs if not carefully programmed (esp. at the level of of > extreme scale systems, it is hard to debug). > You need something to provide for local and remote completion. Do you mean to have blocking RMA operations that (in MPI terms) essentially act as lock-RMA_operation-unlock? > 3. Support for non-overlapping concurrent operations in a window. MPI RMA already does this, in all of the active target modes, and in the passive target mode with the shared lock mode. What do you need that isn't supported? > > 4. RMW Operation - Useful for implementing dynamic load balancing > algorithms (e.g. task queues/work stealing, group/global counters, > etc). > Yes, this is a major gap. Is fetch-and-increment enough, or do you need compare-and-swap, or a general RMI? Bill > The above are feature requirements rather than performance issues, > which > are implementation specific. > > If you have any questions, I would be happy to explain the above in > detail. > > Thanks, > -Manoj. > --------------------------------------------------------------- > Manojkumar Krishnan > High Performance Computing Group > Pacific Northwest National Laboratory > Ph: (509) 372-4206 Fax: (509) 372-4720 > http://hpc.pnl.gov/people/manoj > --------------------------------------------------------------- > > 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 Greg Lindahl 03 Mar '10

03 Mar '10

Bronis, I've had good success using a dedicated rank or ranks to hold the table, and 2-sided MPI operations to access it. -- greg On Wed, Mar 03, 2010 at 07:45:41AM -0800, 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

1 0

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

03 Mar '10

Bill, Here are some of the MPI RMA requirements for Global Arrays (GA) and ARMCI. ARMCI is GA's runtime system. GA/ARMCI exploits native network communication interfaces and system resources (such as shared memory) to achieve the best possible performance of the remote memory access/one-sided communication. GA/ARMCI relies *heavily* on optimized contiguous and non-contiguous RMA operations (get/put/acc). For GA/ARMCI and its applications, below are some specfic examples of operations that are hard to achieve in MPI-2 RMA. 1. Memory Allocation: (This might be an implementation issue) The user or library implementors should be able to allocate memory (e.g. shared memory), and register with MPI. This is useful in case of Global Arrays/ARMCI, which use RMA across nodes and shared memory within nodes. ARMCI allocates shared memory segment, and pins/registers with the network. 2. Locks: Should be made optional to keep the RMA programming model simple. If the user doesnot require concurrency, then locks are unnecessary. Enforcing to use locks as default might introduce unnecessary bugs if not carefully programmed (esp. at the level of of extreme scale systems, it is hard to debug). 3. Support for non-overlapping concurrent operations in a window. 4. RMW Operation - Useful for implementing dynamic load balancing algorithms (e.g. task queues/work stealing, group/global counters, etc). The above are feature requirements rather than performance issues, which are implementation specific. If you have any questions, I would be happy to explain the above in detail. Thanks, -Manoj. --------------------------------------------------------------- Manojkumar Krishnan High Performance Computing Group Pacific Northwest National Laboratory Ph: (509) 372-4206 Fax: (509) 372-4720 http://hpc.pnl.gov/people/manoj --------------------------------------------------------------- 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

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