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

[Jeff Squyres]

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