[Mpi-22] Ticket #33 (Scalable Graph Topology Interface)

[Supalov, Alexander]

Hi everybody,

Thanks, having a good prototype is definitely a great step forward. I hope that if we happen to have a couple of other MPI-2.2 tickets, the prototypes in which could be improved in a similar manner, their authors may find it possible to do so now.

I wonder whether we may want to consider defining a prototype more strictly, say, by adding a couple of qualifiers like "demonstrating the intended functionality and performance potential" or something. This will definitely increase the quality of the prototypes, and may positively influence the quality of the resulting standard, which is after all what all of us are after here. Given that most of the intended MPI-2.2 tickets already appear to have good prototypes, it should not be a problem to clarify the rules a bit here.

As was mentioned back in April, to facilitate commercial adoption of the MPI-2.2, it might also be good to resolve the ABI and IP matters at the same time, in application to this ticket and all other actual and potential MPI-2.2 entries.

Even though it looks fairly unlikely that an addition of an extra class proposed in #33 will break anything in the C++ ABI, it just might. Hence, we need a determination by the Forum what kind of ABI changes is acceptable for MPI-2.2, possibly individually for each language binding, and what kind of procedure should be used to check the ABI backward compatibility where it is required - like testing, consultation with compiler writers, etc. A reasonable compromise wrt individual language bindings may help to ensure that the scope of the MPI-2.2 standard stays unchanged.

The IP matter is basically a question of a license the prototype is being made available under. To simplify commercial adoption, it would be great to have the prototypes carry a BSD-style or an equally "commercial friendly" open source license. This may require some clarification on part of the authors with their respective institution, but by my records, the matter was in rather satisfactory state back in April. So, it should be no problem to make a slight change to the rules here either.

I guess we should consider returning to these thee topics (prototype, ABI, IP) at the July meeting and making a decision there.

Best regards.

Alexander 

-----Original Message-----
From: mpi-22-bounces_at_[hidden] [mailto:mpi-22-bounces_at_[hidden]] On Behalf Of Jeff Squyres
Sent: Wednesday, June 17, 2009 6:02 PM
To: MPI 2.2
Subject: Re: [Mpi-22] Ticket #33 (Scalable Graph Topology Interface)

Torsten --

Many thanks for your persistence in this ticket.  From your  
description, it sounds like the implementation should be sufficient  
for many of those who abstained or voted against because it now does  
show tangible scalability improvements.

All: please chime in if you feel this is not the case.  #33 was  
perhaps the most "troublesome" ticket, so reaching consensus here  
would be great.  Thanks!

On Jun 17, 2009, at 11:59 AM, Torsten Hoefler wrote:

> Hello,
> everybody who abstained or voted against the proposal, please read
> ticket #33 and discuss any open issue or question either here or  
> with me.
> I would be happy to answer any questions or address any doubts.
>
> A new implementation for all versions of the proposed scalable graph
> interface is attached to ticket #33 (virtual_graph_scal.cpp)
> (https://svn.mpi-forum.org/trac/mpi-forum-web/ticket/33).
>
> This version does not implement the new interface on top of the old
> interface and thus reduces the memory consumption per process from
> O(N*N) to O(N) (assuming a reasonable specification).
>
> The implementation is trivial (took me about 2 hours) and the most
> complex function has 76 lines of code. The whole proposal including an
> example has 199 lines of code (many of this are interface  
> definitions).
>
> As discussed, the communication overhead for the adjacent interface is
> zero and the worst-case communication overhead for the general  
> interface
> is O(N) per process, however, the expected case is O(1) (constant).
>
> The attached implementation now achieves all goals of ticket #33, it
> increases the scalability of the graph interface by reducing the  
> memory
> on the user-side to a lower complexity class and the communication is
> optimized.
>
> Ths significance of improvement is shown in the following table which
> lists the maximum memory consumption in bytes for different  
> communicator
> sizes with the old and the new interface (assuming 8 byte integers).
>
> processes   MPI-2.1 interface   proposed interface
> 512         2 MiB               2 kiB
> 1024        8 MiB               8 kiB
> 4096        134 MiB             32 kiB
> 16384       2.1 GiB             131 kiB
> 65536       34.4 GiB            524 kiB
>
> This is an upper bound, if you are interested in sparse graphs,  
> multiply
> both numbers by 0.01 (1% sparsity). The relative scaling remains the
> same.
>
> All issues related to process remapping are not part of the ticket and
> are not touched (the main intent of this ticket is to enable the use  
> of
> virtual graph topologies at scale at all). However, if you are
> interested in this matter, there is an extensive body of research in
> this area:
>
> "Rank Reordering Strategy for MPI Topology Creation Functions"
>  http://www.springerlink.com/content/f3hqq5u2v14tpu53/
> "Topology mapping for Blue Gene/L supercomputer"
>  http://portal.acm.org/citation.cfm?id=1188576
> "Implementing the MPI process topology mechanism"
>  http://portal.acm.org/citation.cfm?id=762761.762767
> "Scheduling regular and irregular communication patterns on the CM-5"
>  http://portal.acm.org/citation.cfm?id=147877.148034
>
> Thanks & All the Best,
>  Torsten
>
> -- 
> bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ -----
> Torsten Hoefler, Ph.D. | Postdoctoral Fellow
> Open Systems Lab       | Indiana University
> 150 S. Woodlawn Ave.   | Bloomington, IN, 474045, USA
> Lindley Hall Room 135  | +01 (812) 855-3608
> _______________________________________________
> mpi-22 mailing list
> mpi-22_at_[hidden]
> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-22


-- 
Jeff Squyres
Cisco Systems
_______________________________________________
mpi-22 mailing list
mpi-22_at_[hidden]
http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi-22
---------------------------------------------------------------------
Intel GmbH
Dornacher Strasse 1
85622 Feldkirchen/Muenchen Germany
Sitz der Gesellschaft: Feldkirchen bei Muenchen
Geschaeftsfuehrer: Douglas Lusk, Peter Gleissner, Hannes Schwaderer
Registergericht: Muenchen HRB 47456 Ust.-IdNr.
VAT Registration No.: DE129385895
Citibank Frankfurt (BLZ 502 109 00) 600119052
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.