[petsc-users] Required Help on Calculation of All-to-All broadcast in a Balanced Binary Tree -Please

[Zulfi Khan]

Calculation of Cost of all-to-broadcast for a Balanced Binary Tree

Hi,

I have a question is:

Given a balanced binary tree as shown in Figure 4.7 (attached),describe a procedure to perform all-to-all broadcast that takes time (ts +twmp/2)logp for m-word messages on p nodes (assuming th is ignored). Assumethat only the leaves of the tree contain nodes, and that an exchange of twom-word messages between any two nodes connected by bidirectional channels takestime ts + twmk if the communication channel (or a part of it) is shared by ksimultaneous messages.

 

Equations:

comm cost = ts + tw* m* k (as given in the question)

I am trying to calculate the cost of balanced binary tree for allto all broadcast. I have created a procedure for this broadcast:

 P0 P1 P2 P3  (left sub tree): P4, P5, P6, P7(right sub tree)

1st Step: broadcast from left subtree to right subtree(for 8 processors four on left subtree and four on right subtree), the cost is:




P0 exchanges with P7 (i.e each P0 & P7 contains 2 messages)

P1 exchanges with P6 (i.e each P1 & P6 contains 2 messages) 

P2 exchanges with P5 (i.e. each P2 & P5 contains 2 messages)

P3 exchanges with P4 (i.e each P3 and P4 contains 2 messages)

2nd Step: Broadcast Across  the Subtrees Within the Left and RightSubtree

P0 exchanges with P3 (i.e each P0 & P3 contains 4 messages)

P1 exchanges with P2 (i.e each P1 & P2 contains 4 messages)

P4 exchanges with P7 (i.e. each P4 & P7 contains 4 messages)

P5 exchanges with P6 (i.e. each P5 & P6 contains 4 messages)  

3rd Step: Broadcast Within the Subtrees of Left and Right Subtree

P0 exchanges with P1 (i.e each P0 & P1 contains 8 messages)

P2 exchanges with P3 (i.e each P2 & P3 contains 8 messages)

P4 exchanges with P5 ((i.e each P4 & P5 contains 8 messages)

P6 exchanges with P7 (i.e. each P6 & P7 contains 8 messages)

Step 1: t_s + t_w m * 2 //Let k =2.Is k correct?

Step 2: t_s + t_w m *  1  //Letk = 1. Is  k correct?

Step3: t_s +t_w m * 1// Let k = 1. Is k  correct?

logp(t_s + 2 * t_w m + 1 * t_w m +1 * t_w m)

 t_comm = logp(t_s+4t_w m)

Now p/2 = 4

There t_comm = logp(t_s + t_w mp/2)

 

My answer is correct as given inthe question but I don’t have any justification for choosing the value of ‘k’?

Can some body please guide me is mysolution correct? What is the justification of choosing the value of k?

 

Stack Exchange link is;
https://cs.stackexchange.com/questions/106631/all-to-all-broadcast-on-a-balanced-binary-tree

Kindly help me, I would be very much thankful to you guys.

Zulfi.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20190410/45e6a2c6/attachment-0001.html>