<html><head></head><body><div class="yahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><span><p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">Calculation of Cost of all-to-broadcast for a Balanced Binary Tree</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">Hi,</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">I have a question is:</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">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). 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.</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black"> </span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">Equations:</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">comm cost = ts + tw* m* k (as given in the question)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">I am trying to calculate the cost of balanced binary tree for all
to all broadcast. I have created a procedure for this broadcast:</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black"> <span><b style="color: rgb(0, 0, 0); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;"><span style="font-size: 9pt; font-family: Arial, sans-serif;">P0 P1 P2 P3 (left sub tree): P4, P5, P6, P7(right sub tree)</span></b></span></span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 9pt; font-family: Arial, sans-serif; color: black;">1<sup style="">st</sup> Step: broadcast from left subtree to right subtree
<b>(for 8 processors four on left subtree and four on right subtree), the cost is:</b></span></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><br></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P0 exchanges with P7 (i.e each P0 & P7 contains 2 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P1 exchanges with P6 (i.e each P1 & P6 contains 2 messages) </span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P2 exchanges with P5 (i.e. each P2 & P5 contains 2 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P3 exchanges with P4 (i.e each P3 and P4 contains 2 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 9pt; font-family: Arial, sans-serif; color: black;">2<sup style="">nd</sup> Step: Broadcast Across the Subtrees Within the Left and Right
Subtree</span></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P0 exchanges with P3 (i.e each P0 & P3 contains 4 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P1 exchanges with P2 (i.e each P1 & P2 contains 4 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P4 exchanges with P7 (i.e. each P4 & P7 contains 4 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P5 exchanges with P6 (i.e. each P5 & P6 contains 4 messages) </span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 9pt; font-family: Arial, sans-serif; color: black;">3rd Step: Broadcast Within
the Subtrees of Left and Right Subtree</span></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P0 exchanges with P1 (i.e each P0 & P1 contains 8 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P2 exchanges with P3 (i.e each P2 & P3 contains 8 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P4 exchanges with P5 ((i.e each P4 & P5 contains 8 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">P6 exchanges with P7 (i.e. each P6 & P7 contains 8 messages)</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">Step 1: t_s + t_w m * 2 //Let k =2.
Is k correct?</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">Step 2: t_s + t_w m * 1 //Let
k = 1. Is k correct?</span></i></p>
<div style="border-top: none; border-right: none; border-left: none; border-image: initial; border-bottom: 2.25pt double windowtext; padding: 0in 0in 1pt; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;">
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; border: none; padding: 0in;"><i><span style="font-family:"Times New Roman",serif">Step3: t_s +t_w m * 1
// Let k = 1. Is k correct?</span></i></p>
</div>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">logp(t_s + 2 * t_w m + 1 * t_w m +
1 * t_w m)</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif"> t_comm = logp(t_s+4t_w m)</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">Now p/2 = 4</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">There t_comm = logp(t_s + t_w mp/2)</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif"> </span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">My answer is correct as given in
the question but I don’t have any justification for choosing the value of ‘k’?</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">Can some body please guide me is my
solution correct? What is the justification of choosing the value of k?</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif"> </span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><i><span style="font-family:"Times New Roman",serif">Stack Exchange link is;<br>
https://cs.stackexchange.com/questions/106631/all-to-all-broadcast-on-a-balanced-binary-tree</span></i></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">Kindly help me, I would be very much thankful to you guys.</span></b></p>
<p class="ydp3f378e6MsoNormal" style="line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial;"><b><span style="font-size:9.0pt;font-family:"Arial",sans-serif;mso-fareast-font-family:"Times New Roman";color:black">Zulfi.</span></b></p></span><br></div></body></html>