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

[Torsten Hoefler]

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