Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree?

Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages between any two nodes connected by bidirectional channels takes time ts + twmk if the communication channel (or a part of it) is shared by k simultaneous messages.

Should I use Scatter technique on it, i.e, All-to-Personalized Communication?

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Have you seen: parallelcomp.uw.hu/ch04lev1sec1.html or cs.bilkent.edu.tr/~ozturk/cs426/set5.pdf ? $\endgroup$ – Evil Apr 8 '19 at 6:46
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Apr 8 '19 at 9:33
  • $\begingroup$ Your Q:What have you tried? I want All to All broadcast. I have not seen any example of it for tree. I feel, it would be similar to tree traversal algorithm.Q: Where did you get stuck?a. For all to all broadcast all nodes should have some data. I would I have to distribute data on all nodes? b. For m words how much data should I distribute on each of the p nodes? c. How t_w * m * k would change to t_w *m * p/2? On slide 16 it says that source is the root and in the next line it says source is also the left child. This is confusing. Please provide some description of 1 to All BC for Scatter. $\endgroup$ – user2994783 Apr 8 '19 at 18:45

There are 8 processors: P0..P7, each contains one of the messages M0..M7 so

P0: M0, P1:M1, P2:M2, P3:M3, P4:M4, P5:M5, P6:M6, P7:M7

P0, P1, P2, & P3 are on the left subtree and P4, P5, P6, P7 are on the right subtree.


All the processes make a copy of the message and left subtree processors exchange the copy with the corresponding processors on the right subtree. Result is that each processor now has two messages as shown below:

P0 & P7: M0, M7

P1 & P6: M1, M6

P2 & P5:M2, M5

P3 & P4:M3, M4


Now P3 & P0 would make a copy of their messages and exchange the copy. Pairs of P1, P2 and P4,P7 and P5, P6 would repeat this action. The result is shown below:

P0, P3, P4 & P7: M0, M3, M4, M7

P1, P2, P5 & P6: M1, M2, M5, M6


Now P0 & P1, would make a copy of their messages and exchange the copy. Pairs of P2, P3 and P4, P5 and P6, P7 would repeat this action. The result is the final broadcast:

P0, P1, P2, P3, P4, P5, P6, P7 would all contain the messages:

M0, M1, M2, M3, M4, M5, M6, M7



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.