| RE: [ptp-dev] Need help on the construction of SDM routing tree |
|
Hi Greg, Thanks for your explanation. Here I still have some questions about the sdm debugger. 1. The routing tree is a binomial tree,which is constructed based on the sdm_id, i.e, task rank of MPI program. It seems that the ROOT of this binomial tree is the SDM_MASTER(i.e, sdm_client). Right? 2. How is the routing file (containing the routing table entries) provided? Should it be provided by hand before launching SDM debugger? And the first elemnt of a routing table entry, i.e, node_id, is the node id, not the MPI task id/rank, so the corresponding hostname can be provided. Right? If so, during the sdm_tcp_init(), each process (including sdm server and client) waits for connection from its parent and connects to its children. During this process,entry->nodeID,which should be a physical node id, is compared to rank id (either sdm_get_route_id() or mapp->id), to obtain the listen port or the destionation port. Since the entry->nodeID is known before job launching(in fact, during machine configuration), and rank id can only be known after job launching, how can these two be compared because the job distribution is completely controlled by runtime /resource management system? Jie From: g.watson@xxxxxxxxxxxx To: ptp-dev@xxxxxxxxxxx Subject: Re: [ptp-dev] Need help on the construction of SDM routing tree Date: Mon, 17 Nov 2008 17:03:55 +0000 Jie, This code is used to construct a binomial tree. The tree is "lopsided" in that there are more elements on the left side than the right side of each branch. This ensures that at a particular node in the tree messages sent to each branch in sequence will reach the leaves simultaneously. See http://en.wikipedia.org/wiki/Binomial_heap for a diagram.
The tree is constructed in sdm_route_init, which in turn calls find_descendants. A couple of things to note. First is that the root of the computed tree is always node 0. SInce the actual node id of the root can vary, we first normalize the tree so that the root id is 0. Second, each node actually computes a number of trees:
- "descendants" contains all the nodes in the tree from the current location to the leaves
- "children" contains only the immediate children of the current location
- "child_descendants" is a hash that contains the descendants of every child of the current location
At any given position in the tree, it is easy to compute the children by starting with the current node and setting successively higher bits until the highest numbered node in the tree has been reached. For example, suppose there are 9 nodes in the tree. Node 0 (0000) will have children 1 (0001), 2 (0010), 4 (0100), and 8 (1000). Node 1 (0001) will have children 3 (0011) and 5 (0101). Node 2 (0010) will have child 6 (0110) and node 3 (0011) will have child 7 (0111). Nodes 4, 5, 6, 7, and 8 don't have any children because if you set the next highest bit the result will be greater than the number of nodes. For example setting the next highest bit on node 4 (0100) gives 10 (1100).
The full tree is computed recursively.
Hope this helps,
Greg
On Nov 4, 2008, at 3:56 PM, JiangJie wrote: 八卦娱乐包打听，MSN资讯速递帮你忙！ 了解详细！ |