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