Nassimi D, Sahni S (1979) Bitonic sort on a mesh-connected parallel computer. In: Proceedings of the american federation of information processing societies spring joint computer conference, vol 32. In: Proceedings of the symposium for parallel algorithms and architectures, pp 148–157, San Diego, June 1992īatcher KE (1968) Sorting networks and their applications. Stricker T (1992) Supporting the hypercube programming model on meshes (a fast parallel sorter for iwarp). Morgan Kaufmann Publishers, San Francisco 837p, ISBN:1-55860-117-1 With this information, it should be possible toĭetermine if a resend is needed.Leighton FT (1991) Introduction to parallel algorithms and architectures: array, trees, hypercubes. Several nodes, and this is due to difficulties for each individual node to determine what an unfiltered approach result in resends to If a node in the higher segment initialize the call, all lower segment nodes are sure to get the call.Ĭonclusion: with roof(log(n)) + 1 steps, n nodes can be informed.įrom testing it is clear that any number of nodes can be reached within the upper limitĪbove by calling c0 in the call chain. This is only required by nodes in the lower segment. Since c0 transfers between these two groups, and all nodes in the lower segment has been called, the final call ensures that all nodes in the higher segment are informed. Proof: All nodes > 2^(b-1) have a corresponding node in < 2^(b-1). This ignore behaviour should be complemented with an extension of the call chain for non-initializing nodes so that c0 is called after cn. It can be be proven that all nodes can ignore nodes in the call chain with higher index than the number of present nodes, as the call chains may require visits in the "higher" indices before returning to the lower, but it should work as the higher dimension is determined by the index of the node itself. Assuming the current node has index i, the x'th position in the call chain is constructed as follows:Ĭ = i XOR (1 1011b -> 1001b -> 1000b, and none of these nodes are present. The last node in the chain should always receive 0. If the node receives a broadcast, the counter decides where in the call chain to start the broadcast. In the case of 8 nodes, 2 is sent to c0, 1 is sent to c1, and 0 is The counter starts at log(n) and decrease before each transmission.It then proceeds down the chain, and sends to c1, c2 and so on all the way through the chain. if the node starts the broadcast, it starts by sending the information to c0.Each node is assigned a number ranging from 0 to n-1.Įach node has at most log(n) other nodes to relay any information to.The goal is to reach all nodes within log(n) time, and reduce the maximum of sent messages for each node to log(n). We then proceed to show an adaptation for the general case. Much less network heavy for the broadcasting node, but the information propagation time is still linear.įirst we handle the case where the number of nodes n is a even power of 2. Another approach is to number each node, and send the information in a circle. This is time consuming and network heavy for the broadcasting node. A naïve approach is to let the initializing node act as a central node and send the information to one node at a time. As we don't have a central node, we need a scheme where all nodes can initialize a broadcast to all other nodes, and reach all nodes with that information in as short time as possible. If a set of nodes are sharing a session, updates must propagate to all nodes. I've found this on my own, but if anyone else has had similar thoughts, I can not claim to be the first. HYPERCUBE SCHEME HOW TOLater posts will cover how to maintain the mesh and alter the size.ĭISCLAIMER: There may be faulty assumptions or results, and if anyone has seen anything like this before, please leave a comment. HYPERCUBE SCHEME SERIESThis is the first in a series of posts about my findings, and it covers the basic structure of a stable mesh. For this purpose I've devised an scheme to maintain a mesh of arbitrary size with logarithmic propagation time and node load. For a few years, I've been thinking about P2P chat mesh networks, and one particularly tricky part is keeping it really decentralized.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |