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

[Jed Brown]

This sounds an awful lot like a homework question.  In any case, it does
not relate directly to PETSc and is thus off-topic for this list.

Zulfi Khan via petsc-users <petsc-users at mcs.anl.gov> writes:

> 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.