{"action":"created","issue":{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/33","repository_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic","labels_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/33/labels{/name}","comments_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/33/comments","events_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/33/events","html_url":"https://github.com/mpiforumbot/mpi-forum-historic/issues/33","id":167211305,"number":33,"title":"Fix Scalability Issues in Graph Topology Interface","user":{"login":"mpiforumbot","id":20617676,"avatar_url":"https://avatars.githubusercontent.com/u/20617676?v=3","gravatar_id":"","url":"https://api.github.com/users/mpiforumbot","html_url":"https://github.com/mpiforumbot","followers_url":"https://api.github.com/users/mpiforumbot/followers","following_url":"https://api.github.com/users/mpiforumbot/following{/other_user}","gists_url":"https://api.github.com/users/mpiforumbot/gists{/gist_id}","starred_url":"https://api.github.com/users/mpiforumbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mpiforumbot/subscriptions","organizations_url":"https://api.github.com/users/mpiforumbot/orgs","repos_url":"https://api.github.com/users/mpiforumbot/repos","events_url":"https://api.github.com/users/mpiforumbot/events{/privacy}","received_events_url":"https://api.github.com/users/mpiforumbot/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/labels/MPI%202%5C.2","name":"MPI 2\\.2","color":"ededed"},{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/labels/New%20routine%5C(s%5C)","name":"New routine\\(s\\)","color":"ededed"},{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/labels/Passed","name":"Passed","color":"b60205"},{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/labels/Text%20committed","name":"Text committed","color":"d93f0b"}],"state":"open","locked":false,"assignee":{"login":"mpiforumbot","id":20617676,"avatar_url":"https://avatars.githubusercontent.com/u/20617676?v=3","gravatar_id":"","url":"https://api.github.com/users/mpiforumbot","html_url":"https://github.com/mpiforumbot","followers_url":"https://api.github.com/users/mpiforumbot/followers","following_url":"https://api.github.com/users/mpiforumbot/following{/other_user}","gists_url":"https://api.github.com/users/mpiforumbot/gists{/gist_id}","starred_url":"https://api.github.com/users/mpiforumbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mpiforumbot/subscriptions","organizations_url":"https://api.github.com/users/mpiforumbot/orgs","repos_url":"https://api.github.com/users/mpiforumbot/repos","events_url":"https://api.github.com/users/mpiforumbot/events{/privacy}","received_events_url":"https://api.github.com/users/mpiforumbot/received_events","type":"User","site_admin":false},"assignees":[{"login":"mpiforumbot","id":20617676,"avatar_url":"https://avatars.githubusercontent.com/u/20617676?v=3","gravatar_id":"","url":"https://api.github.com/users/mpiforumbot","html_url":"https://github.com/mpiforumbot","followers_url":"https://api.github.com/users/mpiforumbot/followers","following_url":"https://api.github.com/users/mpiforumbot/following{/other_user}","gists_url":"https://api.github.com/users/mpiforumbot/gists{/gist_id}","starred_url":"https://api.github.com/users/mpiforumbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mpiforumbot/subscriptions","organizations_url":"https://api.github.com/users/mpiforumbot/orgs","repos_url":"https://api.github.com/users/mpiforumbot/repos","events_url":"https://api.github.com/users/mpiforumbot/events{/privacy}","received_events_url":"https://api.github.com/users/mpiforumbot/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/milestones/8","html_url":"https://github.com/mpiforumbot/mpi-forum-historic/milestones/2009/07/27%20Chicago","labels_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/milestones/8/labels","id":1900469,"number":8,"title":"2009/07/27 Chicago","description":"","creator":{"login":"mpiforumbot","id":20617676,"avatar_url":"https://avatars.githubusercontent.com/u/20617676?v=3","gravatar_id":"","url":"https://api.github.com/users/mpiforumbot","html_url":"https://github.com/mpiforumbot","followers_url":"https://api.github.com/users/mpiforumbot/followers","following_url":"https://api.github.com/users/mpiforumbot/following{/other_user}","gists_url":"https://api.github.com/users/mpiforumbot/gists{/gist_id}","starred_url":"https://api.github.com/users/mpiforumbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mpiforumbot/subscriptions","organizations_url":"https://api.github.com/users/mpiforumbot/orgs","repos_url":"https://api.github.com/users/mpiforumbot/repos","events_url":"https://api.github.com/users/mpiforumbot/events{/privacy}","received_events_url":"https://api.github.com/users/mpiforumbot/received_events","type":"User","site_admin":false},"open_issues":1,"closed_issues":10,"state":"closed","created_at":"2016-07-23T22:09:07Z","updated_at":"2016-07-24T01:52:09Z","due_on":"2009-07-29T04:00:00Z","closed_at":"2016-07-23T22:09:07Z"},"comments":115,"created_at":"2016-07-24T01:04:36Z","updated_at":"2016-07-24T01:52:26Z","closed_at":null,"body":"**Originally by _traff_ on 2008-10-10 08:27:53 -0500**\n\n___\n# Fix Scalability Issues in Graph Topology InterfaceAuthor: Torsten Hoefler, Jesper Larsson Traeff with comments from Rolf\nRabenseifner, Hubert Ritzdorf, and Rajeev Thakur\n\n## Status\n Sep 8 2008 Straw votes\n\n For a scalable description\n\n|| Yes || Maybe || No for 2.2 || Abstain ||\n|| 7 || 20 ||0 || 3 ||\n\n For adding info to weight of edges\n\n|| Yes || Maybe || No for 2.2 || Abstain ||\n|| 4 || 22 || 1 || 6 ||\n\nOctober 2008 Straw Vote\n\n|| Yes || Maybe || No for 2.2 || Abstain ||\n|| 23 || 0 || 0 || 5 ||\n\nApril 09 Straw Votes\n\nFully flexible version vs. only adjacent version.\n\n|| only flexible || only adjacent || both ||\n|| 9             || 2             || 8    ||\n\nUsing MPI_Info arguments for any assertions (that change the semantics)\nis not in the spirit of MPI, thus, we can't use Info for neither\nasserting that each process specifies the whole graph or all processes\nspecified reorder or not.\n\nReorder collective or not?\n\n|| collective || not collective ||\n|| 5          || 6              ||\n\nIt's close, but not collective is also more consistent with the current\nstandard. We can change this in MPI-3 easily (while keeping downward\ncompatibility).\n\n\n\n## Description\nThe graph interface in MPI-1 has some serious (and unnecessary) scalability\nissues that prohibit efficient usage on large-scale machines.\n\nThe new scalable interface is essentially a single function, that\nis complemented by two inquiry functions. The concrete proposal introduces\ntwo new constants, and entails a few other changes related to the\ntopology functionality.\n\nSee additional proposal/discussion in Ticket #147.\n\n## History\n\nThis interface was introduced in MPI-1 designed based on some older parallel\nlibrary (Alexander Supalov can provide details). However, the interface was\nnever changed. Right now, each process has to know the whole topology during\ngraph creation and every process can query the neighbors of every other process\nin the communicator with a local operation. This makes it necessary to store\nthe whole topology at every process locally which might be a prohibitive waste\nof memory resources.\n\nThe proposal is to introduce new functionality for specifying topologies by\ndistributed graphs, and deprecate the current MPI 2.1 graph topology\nfunctionality.\n\n## Proposed Solution\n\nPage 15, line 5, add:\n\n`MPI_UNWEIGHTED`\n\nPage 195, line 27, add:\n\n`MPI::Distgraphcomm MPI::Distgraphcomm::Dup() const`\n\nPage 195, line 35, add:\n\n`MPI::Distgraphcomm MPI::Distgraphcomm::Clone() const`\n\nPage 242:15-22 - remove sentence\n\n\"Edges in the communication graph are not weighted, so that processes are either simply connected or not connected at\nall.\"\n\nand (outdated) rationale.\n\nPage 243, line 3: Replace\n\n\"The functions `MPI_GRAPH_CREATE` and `MPI_CART_CREATE` are used\"\n\nby\n\n\"The functions `MPI_GRAPH_CREATE`, `MPI_DIST_GRAPH_CREATE_ADJACENT`, `MPI_DIST_GRAPH_CREATE` and `MPI_CART_CREATE` are used\"\n\nPage 243, line 8, replace:\n\n\"All input arguments must have identical values on all processes of the group of comm_old. A new communicator ...\"\n\nby:\n\n\"For `MPI_GRAPH_CREATE` and `MPI_CART_CREATE`, all input arguments must have\nidentical values on all processes of the group of comm_old.  For\n`MPI_DIST_GRAPH_CREATE_ADJACENT` and `MPI_DIST_GRAPH_CREATE` the input\ncommunication graph is distributed across the calling processes. Therefore the\nprocesses provide different values for the arguments specifying the graph.\nHowever, all processes must give the same value for reorder and the info\nargument. In all cases, a new communicator ...\"\n\nPage 243, line 33 (before last sentence), add:\n\nFor distributed graphs, the functions `MPI_DIST_NEIGHBORS_COUNT` and `MPI_DIST_NEIGHBORS` can be used to extract the neighbors of the calling node.\n\nPage 247, after line 48, add new section:\n\n7.5.4 Distributed (Graph) Constructor\n\nThe general graph constructor assumes that each process passes the full (global) communication graph to the call. This limits the scalability of this\nconstructor. With the distributed graph interface, the communication graph is\nspecified in a fully distributed fashion. Each process specifies\nonly the part of the communication graph of which it is aware. Typically, this could be the set of processes from which the process will eventually receive or get data, or the set of processes to which the process will send or put data, or some combination of such edges. \nTwo different interfaces can be used to create a\ndistributed graph topology. `MPI_DIST_GRAPH_CREATE_ADJACENT` creates a\ndistributed graph communicator with each process specifying all of its incoming and\noutgoing (adjacent) edges in the logical communication graph and thus requires\nminimal communication during creation. `MPI_DIST_GRAPH_CREATE` provides\nfull flexibility, and processes can indicate that communication will occur\nbetween other pairs of processes.  \n\nTo provide better possibilities for\noptimization by the MPI library, the distributed graph constructors\npermit weighted communication edges and take an info argument that\ncan further influence process reordering or other optimizations performed by the\nMPI library. For example, hints can be provided on how edge weights are to be\ninterpreted, the quality of the reordering, and/or the time permitted\nfor the MPI library to process the graph.\n\n```\n#!c\nMPI_DIST_GRAPH_CREATE_ADJACENT(comm_old, indegree, sources, sourceweights, \noutdegree, destinations, destweights, info, reorder, comm_dist_graph)\n IN      comm_old        input communicator (handle)\n IN      indegree        size of sources and sourceweights arrays \n                         (non-negative integer)\n IN      sources         ranks of processes for which the calling \n                         process is a destination \n                         (array of non-negative integers)\n IN      sourceweights   weights of the edges into the calling \n                         process (array of non-negative integers)\n IN      outdegree       size of destinations and destweights arrays \n                         (non-negative integer)\n IN      destinations    ranks of processes for which the calling \n                         process is a source\n                         (array of non-negative integers)\n IN      destweights     weights of the edges out of the calling \n                         process (array of non-negative integers)\n IN      info            hints on optimization and interpretation of \n                         weights (handle)\n IN      reorder         the ranks may be reordered (true) or \n                         not (false) (logical)\n OUT     comm_dist_graph communicator with distributed graph \n                        topology (handle)\n\nint MPI_Dist_graph_create_adjacent(MPI_Comm comm_old, \n          int indegree, int sources[], int sourceweights[],\n          int outdegree, int destinations[], int destweights[],\n          MPI_Info info, int reorder, MPI_Comm *comm_dist_graph)\n\nMPI_DIST_GRAPH_CREATE_ADJACENT(COMM_OLD, INDEGREE, SOURCES, SOURCEWEIGHTS, \nOUTDEGREE, DESTINATIONS, DESTWEIGHTS, INFO, REORDER, COMM_DIST_GRAPH, \nIERROR)\n    INTEGER COMM_OLD, INDEGREE, SOURCES(*), SOURCEWEIGHTS(*), \n    OUTDEGREE, DESTINATIONS(*), DESTWEIGHTS(*), INFO, \n    COMM_DIST_GRAPH, IERROR\n    LOGICAL REORDER\n\nMPI::Distgraphcomm MPI::Intracomm::Dist_graph_create_adjacent(int indegree, \n                   const int sources[], const int sourceweights[],\n                   int outdegree, const int destinations[],\n                   const int destweights[],\n                   const MPI::Info& info, bool reorder) const\n\nMPI::Distgraphcomm MPI::Intracomm::Dist_graph_create_adjacent(int indegree, \n                   const int sources[], int outdegree, \n                   const int destinations[], const MPI::Info& info, \n                   bool reorder) const\n```\n\n`MPI_DIST_GRAPH_CREATE_ADJACENT` returns a handle to a new communicator to which the\ndistributed graph topology information is attached.  \nEach process passes all information about the edges to its neighbors\nin the virtual distributed graph topology.\nThe calling processes must ensure that each edge of the graph is described in the source and in the destination process with the same weights. If there are multiple edges for a given (source,dest) pair, then the sequence of the weights of these edges does not matter. The complete communication topology is the combination of all edges shown in the `sources` arrays of all processes in `comm_old`, which must be identical to the combination of all edges shown in the `destinations` arrays.\nSource and destination ranks must be process\nranks of `comm_old`. This allows a fully distributed specification of the communication graph.\nIsolated processes (i.e., processes with no outgoing or incoming edges, that\nis, processes that have specified `indegree` and `outdegree` as zero and that thus do not occur as source or destination rank in the graph\nspecification) are allowed. \n\nThe call creates a new communicator `comm_dist_graph` of distributed graph\ntopology type to which topology information has been attached. The number of processes in `comm_dist_graph` is identical to the number of processes in `comm_old`. The call to\n`MPI_DIST_GRAPH_CREATE_ADJACENT` is collective.\n\nWeights are specified as non-negative integers and can be used to\ninfluence the process remapping strategy and other internal MPI\noptimizations. For instance, approximate count arguments of later\ncommunication calls along specific edges could be used as their edge\nweights. Multiplicity of edges can likewise indicate more intense\ncommunication between pairs of processes. However, the exact meaning of\nedge weights is not specified by the MPI standard and is left to the\nimplementation. In C or Fortran, an application can supply the special value `MPI_UNWEIGHTED` for both weight arrays to\nindicate that all edges have the same (effectively no) weight. In C++, this constant does not exist and the weight arguments may be omitted from the argument list. It is erroneous\nto supply `MPI_UNWEIGHTED`, or in C++ omit the weight arrays, for some but not all \nprocesses' `sourceweights` and `destweights` arrays in\n`comm_old`. Note that `MPI_UNWEIGHTED` is not a special weight value;\nrather it is a special value for the total array argument. In C, one would\nexpect it to be a `NULL`. In Fortran, `MPI_UNWEIGHTED` is an object\nlike `MPI_BOTTOM` (not usable for initialization or assignment). See\nSection 2.5.4.\n\nThe meaning of the `info` and `reorder` arguments is defined\nin the description of the following routine. \n\n```\n#!c\nMPI_DIST_GRAPH_CREATE(comm_old, n, sources, degrees, \ndestinations, weights, info, reorder, comm_dist_graph)\n IN  comm_old        input communicator (handle)\n IN  n               number of source nodes for which this process\n                     specifies edges (non-negative integer)\n IN  sources         array containing the n source nodes for which\n                     this process specifies edges \n                     (array of non-negative integers)\n IN  degrees         array specifying the number of destinations for\n                     each source node in the source node array \n                     (array of non-negative integers)\n IN  destinations    destination nodes for the source nodes in the \n                     source node array (array of non-negative \n                     integers)\n IN  weights         weights for source to destination edges \n                     (array of non-negative integers)\n IN  info            hints on optimization and interpretation of \n                     weights (handle)\n IN  reorder         the process may be reordered (true) or \n                     not (false) (logical)\n OUT comm_dist_graph communicator with distributed graph topology \n                   added (handle)\n\nint MPI_Dist_graph_create(MPI_Comm comm_old, int n, \n          int sources[], int degrees[], int destinations[],\n          int weights[], MPI_Info info, int reorder, \n          MPI_Comm *comm_dist_graph)\n\n\nMPI_DIST_GRAPH_CREATE(COMM_OLD, N, SOURCES, DEGREES, \nDESTINATIONS, WEIGHTS, INFO, REORDER, COMM_DIST_GRAPH, IERROR)\n    INTEGER COMM_OLD, N, SOURCES(*), DEGREES(*), DESTINATIONS(*), \n    WEIGHTS(*), INFO, COMM_DIST_GRAPH, IERROR\n    LOGICAL REORDER\n\nMPI::Distgraphcomm MPI::Intracomm::Dist_graph_create(int n, \n                   const int sources[], const int degrees[],\n                   const int destinations[], const int weights[], \n                   const MPI::Info& info, bool reorder) const\n\nMPI::Distgraphcomm MPI::Intracomm::Dist_graph_create(int n, \n                   const int sources[], const int degrees[],\n                   const int destinations[], const MPI::Info& info, \n                   bool reorder) const\n```\n\n`MPI_DIST_GRAPH_CREATE` returns a handle to a new communicator to which the\ndistributed graph topology information is attached. Concretely, each process\ncalls the constructor with a set of directed `(source,destination)`\ncommunication edges as described below. Every process passes an array of\n`n` source nodes in the `sources` array.  For each source node, a\nnon-negative number of destination nodes is specified in the `degrees`\narray. The destination nodes are stored in the corresponding consecutive\nsegment of the `destinations` array. More precisely if the `i`-th node\nin `sources` is `s`, this specifies `degrees[i]` edges `(s,d)`\nwith `d` of the `j`-th such edge stored in\n`destinations[degrees[0]+...+degrees[i-1]+j]`. The weight of this edge is\nstored in `weights[degrees[0]+...+degrees[i-1]+j]`.  Both the `sources`\nand the `destinations` arrays may contain the same node more than once, and\nthe order in which nodes are listed as destinations or sources is not\nsignificant. Similarly, different processes may specify edges with the same\nsource and destination nodes.  Source and destination nodes must be process\nranks of `comm_old`. Different processes may specify different numbers of\nsource and destination nodes, as well as different source to destination edges.\nThis allows a fully distributed specification of the communication graph.\nIsolated processes (i.e., processes with no outgoing or incoming edges, that\nis, processes that do not occur as source or destination node in the graph\nspecification) are allowed. \n\nThe call creates a new communicator `comm_dist_graph` of distributed graph\ntopology type to which topology information has been attached. The number of processes in `comm_dist_graph` is identical to the number of processes in `comm_old`. The call to\n`MPI_Dist_graph_create` is collective.\n\nIf `reorder` = `false`, all processes will have the same rank in\n`comm_dist_graph` as in `comm_old`. If `reorder` = `true` then the\nMPI library is free to remap to other processes (of `comm_old`) in order to\nimprove communication on the edges of the communication graph. The weight\nassociated with each edge is a hint to the MPI library about the amount or\nintensity of communication on that edge, and may be used to compute a \"best\"\nreordering.\n\nWeights are specified as non-negative integers and can be used to\ninfluence the process remapping strategy and other internal MPI\noptimizations. For instance, approximate count arguments of later\ncommunication calls along specific edges could be used as their edge\nweights. Multiplicity of edges can likewise indicate more intense\ncommunication between pairs of processes. However, the exact meaning of\nedge weights is not specified by the MPI standard and is left to the\nimplementation. In C or Fortran, an application can supply the special value `MPI_UNWEIGHTED` for the weight array to\nindicate that all edges have the same (effectively no) weight. In C++, this constant does not exist and the weights argument may be omitted from the argument list. It is erroneous\nto supply `MPI_UNWEIGHTED`, or in C++ omit the weight arrays, for some but not all processes of\n`comm_old`. Note that `MPI_UNWEIGHTED` is not a special weight value;\nrather it is a special value for the total array argument. In C, one would\nexpect it to be a `NULL`. In Fortran, `MPI_UNWEIGHTED` is an object\nlike `MPI_BOTTOM` (not usable for initialization or assignment). See\nSection 2.5.4.\n\nThe meaning of the `weights` argument can be influenced by the\n`info` argument. Info arguments can be used to guide the mapping; \npossible options include minimizing the maximum number of edges between processes on different SMP nodes, or minimizing the sum of all such edges.  An MPI\nimplementation is not obliged to follow specific hints, and it is \nlegal for an MPI implementation not to do any reordering.  An MPI\nimplementation may specify more `info` key-value pairs. All processes must specify the same set of key-value `info` pairs. \n\n-Advice to implementors.*\nMPI implementations must document any additionally supported\nkey-value `info` pairs. `MPI_INFO_NULL` is always valid,\nand may indicate the default creation of the distributed graph topology to the MPI library.\n\nAn implementation does not explicitly need to construct the topology from its distributed parts. However, all processes can construct the full topology from the distributed specification and use this in a call to `MPI_GRAPH_CREATE` to create the topology.\nThis may serve as a reference implementation of the\nfunctionality, and may be acceptable for small communicators. However, a\nscalable high-quality implementation would save the topology graph in a\ndistributed way.\n(*End of advice to implementors.*)\n\nExample 7.3  \nAs for Example 7.2., assume there are four processes 0, 1,\n2, 3 with the following adjacency matrix and unit edge weights:\n\n|| process || neighbors ||\n|| 0       || 1, 3      ||\n|| 1       || 0         ||\n|| 2       || 3         ||\n|| 3       || 0, 2      ||\n\nWith `MPI_DIST_GRAPH_CREATE`, this graph could be constructed in many different\nways. One way would be that each process specifies its outgoing edges. The\narguments per process would be:\n\n|| process ||  n  || sources || degrees || destinations || weights ||\n|| 0       ||  1  || 0       || 2       || 1,3          || 1,1     ||\n|| 1       ||  1  || 1       || 1       || 0            || 1       ||\n|| 2       ||  1  || 2       || 1       || 3            || 1       ||\n|| 3       ||  1  || 3       || 2       || 0,2          || 1,1     ||\n\nAnother way would be to pass the whole graph on process 0, which could be\ndone with the following arguments per process:\n|| process ||  n  || sources || degrees || destinations || weights     ||\n|| 0       ||  4  || 0,1,2,3 || 2,1,1,2 || 1,3,0,3,0,2  || 1,1,1,1,1,1 ||\n|| 1       ||  0  || -       || -       || -            || -           ||\n|| 2       ||  0  || -       || -       || -            || -           ||\n|| 3       ||  0  || -       || -       || -            ||           ||\n\nIn both cases above, the application could supply `MPI_UNWEIGHTED` instead of explicitly providing identical weights.\n\n`MPI_DIST_GRAPH_CREATE_ADJACENT` could be used to specify this graph using the following arguments:\n|| process ||  indegree  || sources || sourceweights || outdegree   || destinations || destweights    ||\n|| 0       ||  2         || 1,3     || 1,1           || 2           || 1,3          || 1,1            ||\n|| 1       ||  1         || 0       || 1             || 1           || 0            || 1              ||\n|| 2       ||  1         || 3       || 1             || 1           || 3            || 1              ||\n|| 3       ||  2         || 0,2     || 1,1           || 2           || 0,2          || 1,1            ||\n\n\nExample 7.4  \nA two-dimensional PxQ torus where all processes communicate\nalong the dimensions and along the diagonal edges. This cannot be modelled with Cartesian topologies, but can easily be captured with `MPI_DIST_GRAPH_CREATE` as shown in the following\ncode. In this example, the communication along the dimensions is twice as heavy as the\ncommunication along the diagonals:\n\n```\n#!c\n/*\nInput:     dimensions P, Q\nCondition: number of processes equal to P*Q; otherwise only \n           ranks smaller than P*Q participate\n*/\nint rank, x, y;\nint sources[1], degrees[1];\nint destinations[8], weights[8];\n\nMPI_Comm_rank(MPI_COMM_WORLD, &rank);\n\n/* get x and y dimension */\ny=rank/P; x=rank%P;\n\n/* get my communication partners along x dimension */\ndestinations[0] # P*y+(x+1)%P; weights[0]2;\ndestinations[1] # P*y+(P+x-1)%P; weights[1]2;\n\n/* get my communication partners along y dimension */\ndestinations[2] # P*((y+1)%Q)+x; weights[3]2;\ndestinations[3] # P*((Q+y-1)%Q)+x; weights[4]2;\n\n/* get my communication partners along diagonals */\ndestinations[4] # P*((y+1)%Q)+(x+1)%P; weights[5]1;\ndestinations[5] # P*((Q+y-1)%Q)+(x+1)%P; weights[6]1;\ndestinations[6] # P*((y+1)%Q)+(P+x-1)%P; weights[7]1;\ndestinations[7] # P*((Q+y-1)%Q)+(P+x-1)%P; weights[8]1;\n\nsources[0] = rank;\ndegrees[0] = 8;\nMPI_Dist_graph_create(MPI_COMM_WORLD, 1, sources, degrees, destinations,\n  weights, MPI_INFO_NULL, 1, comm_dist_graph)\n```\n\n\nPage 248, line 21, add (i.e., after MPI_GRAPH): \n\n`MPI_DIST_GRAPH`   distributed graph topology\n\n\nPage 252, line 6, add:\n\nMPI_DIST_GRAPH_NEIGHBORS_COUNT and MPI_DIST_GRAPH_NEIGHBORS provide adjacency\ninformation for a distributed graph topology.\n\n```\n#!c\nMPI_DIST_GRAPH_NEIGHBORS_COUNT(comm, indegree, outdegree, weighted)\n IN      comm          communicator with distributed graph topology (handle)\n OUT     indegree      number of edges into this process (non-negative \n                       integer)\n OUT     outdegree     number of edges out of this process (non-negative \n                       integer)\n OUT     weighted      false if MPI_UNWEIGHTED was supplied during creation, \n                       true otherwise (logical)\n\nint MPI_Dist_graph_neighbors_count(MPI_Comm comm, int *indegree, \n    int *outdegree, int *weighted)\n\nMPI_DIST_GRAPH_NEIGHBORS_COUNT(COMM, INDEGREE, OUTDEGREE, WEIGHTED, IERROR)\n  INTEGER COMM, INDEGREE, OUTDEGREE, IERROR\n  LOGICAL WEIGHTED\n\nvoid MPI::Distgraphcomm::Get_dist_neighbors_count(int rank, int indegree[], \n    int outdegree[], bool& weighted) const\n\n```\n\n```\n#!c\nMPI_DIST_GRAPH_NEIGHBORS(comm, maxindegree, sources, sourceweights, \n                         maxoutdegree, destinations, destweights)\n IN      comm           communicator with distributed graph topology (handle)\n IN      maxindegree    size of sources and sourceweights arrays \n                        (non-negative integer)\n OUT     sources        processes for which the calling process is a \n                        destination (array of non-negative integers)\n OUT     sourceweights  weights of the edges into the calling process \n                        (array of non-negative integers)\n IN      maxoutdegree   size of destinations and destweights arrays \n                        (non-negative integer)\n OUT     destinations   processes for which the calling process is a source\n                        (array of non-negative integers)\n OUT     destweights    weights of the edges out of the calling process \n                        (array of non-negative integers)\n\nint MPI_Dist_graph_neighbors(MPI_Comm comm, int maxindegree, int sources[], \n                             int sourceweights[], int maxoutdegree, \n                             int destinations[], int destweights[])\n\nMPI_DIST_GRAPH_NEIGHBORS(COMM, MAXINDEGREE, SOURCES, SOURCEWEIGHTS, \n                         MAXOUTDEGREE, DESTINATIONS, DESTWEIGHTS, IERROR)\n  INTEGER COMM, MAXINDEGREE, SOURCES(*), SOURCEWEIGHTS(*), MAXOUTDEGREE, \n                         OUTDEGREE, DESTINATIONS(*), DESTWEIGHTS(*), IERROR\n\nvoid MPI::Distgraphcomm::Get_dist_neighbors(int maxindegree, int sources[],\n                                        int sourceweights[], \n                                        int maxoutdegree, \n                                        int destinations[],\n                                        int destweights[])\n```\n\nThese calls are local. The number of edges into and out of the process returned by `MPI_DIST_GRAPH_NEIGHBORS_COUNT` are the total\nnumber of such edges given in the call to `MPI_DIST_GRAPH_CREATE_ADJACENT` or `MPI_DIST_GRAPH_CREATE` (potentially by processes other than the calling process in the case of `MPI_DIST_GRAPH_CREATE`). Multiply defined edges are all counted and returned by `MPI_DIST_GRAPH_NEIGHBORS` in some order. If `MPI_UNWEIGHTED` is supplied for `sourceweights` or\n`destweights` or both, or if `MPI_UNWEIGHTED` was supplied during the\nconstruction of the graph then no weight information is returned in that array\nor those arrays. The only requirement on the order of values in\n`sources` and `destinations` is that two calls to the routine with same input\nargument `comm` will return the same sequence of edges. If `maxindegree`\nor `maxoutdegree` is smaller than the numbers returned by\nMPI_DIST_GRAPH_NEIGHBOR_COUNT, then only the first part of the full list is\nreturned. Note, that the order of returned edges does need not to be identical to the order that was provided in the creation of comm for the case that `MPI_DIST_GRAPH_CREATE_ADJACENT` was used. \n\n-Advice to implementors:* \nSince the query calls are defined to be local,\neach process needs to store the list of its neighbors with incoming and\noutgoing edges. Communication is required at the collective `MPI_DIST_GRAPH_CREATE` call in order to compute the neighbor lists for each process from the distributed graph specification.\n(*End of advice to implementors.*)\n\nPage 450, line 13, add:\n\n`class Distgraphcomm : public Intracomm  {...};`\n\nPage 456, line 1:\n\nreplace: \"five\" with \"six\"\n\nPage 456, line 5:\n\nreplace \"MPI::Cartcomm and MPI::Graphcomm are derived from MPI::Intracomm.\"\n\nwith\n\nMPI::Cartcomm, MPI::Graphcomm, and MPI::Distgraphcomm are derived from MPI::Intracomm.\n\nPage 457, line 11, add:\n\n`Distgraphcomm& Distgraphcomm::Clone() const`\n\nPage 457, line 34, replace:\n\n`// Cartcomm and Graphcomm are similarly defined`\n\nwith:\n\n`// Cartcomm, Graphcomm, and Distgraphcomm are similarly defined`\n\nPage 462, line 36, replace:\n\"MPI_STATUS_IGNORE, MPI_STATUSES_IGNORE, MPI_ERRCODES_IGNORE,\"\n\nwith\n\n\"MPI_STATUS_IGNORE, MPI_STATUSES_IGNORE, MPI_ERRCODES_IGNORE, MPI_UNWEIGHTED,\"\n\nPage 465, line 14, 15: addressed in #104\n\nby:\n\n`// Cartcomm, Graphcomm and Distgraphcomm are similarly defined`\n\nPage 497 (Appendix A), line 9, add:\n\n`MPI_DIST_GRAPH MPI::DIST_GRAPH`\n\nPage 499, after line 12:\n\nadd \"`MPI_UNWEIGHTED Not defined in C++`\"\n\nPage 500, line 6, add:\n\n`MPI::Distgraphcomm`\n\nPage 550, line 27, add:\n\nDistgraphcomm& Distgraphcomm::Clone() const\n\nPage 551, line 13, add:\n\nDistgraphcomm& Distgraphcomm::Dup() const\n\n## Functions to Deprecate (not included in this ticket but kept for reference!)\n\nThe following functions may be deprecated by this proposal (for\nMPI 2.2 or MPI 3.0). The proposal is not dependent on whether this\nhappens or not, and the discussion on this should be kept separate.\n\n```\n#!c\nMPI_GRAPH_CREATE(comm_old, nnodes, index, edges, reorder, comm_dist_graph)\n IN  comm_old        input communicator (handle)\n IN  nnodes          number of nodes in graph (integer)\n IN  index           array of integers describing node degrees (see below)\n IN  edges           array of integers describing graph edges (see below)\n IN  reorder         ranking may be reordered (true) or not (false) (logical)\n OUT comm_dist_graph communicator with graph topology added (handle)\n```\n```\n#!c\nMPI_GRAPH_MAP(comm, nnodes, index, edges, newrank)\n IN      comm                      input communicator (handle)\n IN      nnodes                    number of graph nodes (integer)\n IN      index                     integer array specifying the graph structure, see MPI_GRAPH_CREATE\n IN      edges                     integer array specifying the graph structure\n OUT     newrank                   reordered rank of the calling process;\n                                   MPI_UNDEFINED if the calling process does not belong to graph (integer)\n```\n\n```\n#!c\nMPI_GRAPH_NEIGHBORS(comm, rank, maxneighbors, neighbors)\n IN      comm                    communicator with graph topology (handle)\n IN      rank                    rank of process in group of comm (integer)\n IN      maxneighbors            size of array neighbors (integer)\n OUT     neighbors               ranks of processes that are neighbors to specified process (array of integer)\n```\n\n```\n#!c\nMPI_GRAPH_NEIGHBORS_COUNT(comm, rank, nneighbors)\n IN      comm                 communicator with graph topology (handle)\n IN      rank                 rank of process in group of comm (integer)\n OUT     nneighbors           number of neighbors of specified process (integer)\n```\n\n```\n#!c\nMPI_GRAPH_GET(comm, maxindex, maxedges, index, edges)\n IN      comm                     communicator with graph structure (handle)\n IN      maxindex                 length of vector index in the calling program\n                                  (integer)\n IN      maxedges                 length of vector edges in the calling program\n                                  (integer)\n OUT     index                    array of integers containing the graph structure (for\n                                  details see the definition of MPI_GRAPH_CREATE)\n OUT     edges                    array of integers containing the graph structure\n```\n\n\n```\n#!c\nMPI_GRAPHDIMS_GET(comm, nnodes, nedges)\n IN      comm                    communicator for group with graph structure (handle)\n OUT     nnodes                  number of nodes in graph (integer) (same as number\n                                 of processes in the group)\n OUT     nedges                  number of edges in graph (integer)\n```\n\nSince MPI_DIST_GRAPH_CREATE is collective, it would be a small matter to compute the total number of edges. Thus, MPI_GRAPHDIMS_GET could be kept. Note that nnodes is equal to the number of processes in comm.\n\n### Possible additional functionality (not included in this ticket but kept for future reference)\n\nTo be discussed:\n\n```\n#!c\nMPI_DIST_EDGE_COUNT(comm, edges)\n IN comm              communicator with distributed graph topology (handle)\n OUT edges (integer)  total number of edges in distributed graph\n```\n\n\n## Impact on Implementations\n\nImplementations have to add the new functions, which can easily be\nimplemented on top of the existing, general graph interface. This\ntrivial implementation requires little work.\n\n\n## Impact on Applications / Users\n\nUsers who want to use the new functionality will have to change calls to\ngraph creation and neighbor query functions. They have to introduce\nexplicit communication of neighbor lists if they query other processes\nneighbors (this is unlikely).\n\n## Alternative Solutions\n\nFor more discussion/connection to topological collectives, see [wiki:TopoColl]\n\nKeep for later (maybe introduction in MPI-3):\n*Advice to users.*\nSpecifying `reorder` # `false` on only some processes can support heterogeneous application to hardware mapping. For example, suppose an application does visualization or heavy I/O on rank 0, and that only this processor has the corresponding visualization or I/O capabilities. If this rank should be part of a distributed graph topology, it is useful to specify that this rank will not be remapped. Allowing remapping of other ranks can then exploit features of the interconnection network topology. Another scenario is an application where some ranks have large state information that would be (too) expensive to migrate. Setting `reorder``false` for these ranks guarantees that migration will not be necessary since these processes will preserve their rank in the distributed graph communicator.\n(*End of advice to users.*)\n\n-Advice to implementors.*\nThe reordering optimization problem must account for the constraint that processes with `reorder` = `false` must remain fixed. This could be done by eliminating the fixed nodes and all their edges, and solving the optimization problem on the reduced graph. However, better results may be possible by considering the entire graph.\n(*End of advice to implementors.*)\n\n\n## Entry for the Change Log\n\nSection 7.5.3 on page 247.\nNew functions for a scalable distributed graph topology interface has been added. In this section, the functions MPI_DIST_GRAPH_CREATE_ADJACENT and MPI_DIST_GRAPH_CREATE, the constants MPI_UNWEIGHTED, and the derived C++ class Distgraphcomm were added. \n\nSection 7.5.4, page 252.\nFor the scalable distributed graph topology interface, the functions MPI_DIST_NEIGHBORS_COUNT and MPI_DIST_NEIGHBORS and the constant MPI_DIST_GRAPH were added.  "},"comment":{"url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/comments/234751798","html_url":"https://github.com/mpiforumbot/mpi-forum-historic/issues/33#issuecomment-234751798","issue_url":"https://api.github.com/repos/mpiforumbot/mpi-forum-historic/issues/33","id":234751798,"user":{"login":"mpiforumbot","id":20617676,"avatar_url":"https://avatars.githubusercontent.com/u/20617676?v=3","gravatar_id":"","url":"https://api.github.com/users/mpiforumbot","html_url":"https://github.com/mpiforumbot","followers_url":"https://api.github.com/users/mpiforumbot/followers","following_url":"https://api.github.com/users/mpiforumbot/following{/other_user}","gists_url":"https://api.github.com/users/mpiforumbot/gists{/gist_id}","starred_url":"https://api.github.com/users/mpiforumbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mpiforumbot/subscriptions","organizations_url":"https://api.github.com/users/mpiforumbot/orgs","repos_url":"https://api.github.com/users/mpiforumbot/repos","events_url":"https://api.github.com/users/mpiforumbot/events{/privacy}","received_events_url":"https://api.github.com/users/mpiforumbot/received_events","type":"User","site_admin":false},"created_at":"2016-07-24T01:52:25Z","updated_at":"2016-07-24T01:52:25Z","body":"**Originally by _asupalov_ on 2009-08-17 09:06:11 -0500**\n\n___\n**Attachment added:** [`Annex-ticket-33-5.pdf`](https://github.com/mpiforumbot/mpi-forum-historic/raw/master/attachments/33/Annex-ticket-33-5.pdf) (74.2 KiB)\n"}}
{"actor":{"display_login":"mpiforumbot"}}