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