Calculate the time of an all-to-all broadcast for a balanced binary tree (BBT)

[zak100]

Homework Statement

I am trying to calculate the time of all-to-all broadcast for balanced binary tree (BBT) but my equation is not correct. I need some help in correction of my equation

Relevant Equations

1) Required Time Equation = (t_s + t_w*m*p/2)logp

2)Time for an exchange of two m-word messages between any two nodes connected by bidirectional channels is:
t_s + t_w*m*k
if the communication channel (or a part of it) is shared by k simultaneous messages.

Hi,
I have provided a procedure for broadcast for BBT at the following link:

https://cs.stackexchange.com/questions/106631/all-to-all-broadcast-on-a-balanced-binary-tree

But I am not getting the correct time as asked in the question:

Required Timing equation is: $(t_s + t_w * m* p/2)logp$

Where

$t_s$ = start up time

$t_w$ = per word transfer time

m = size of message

P = number of processors

Given equation for calculating time of an exchange of two m-word messages b/w any two nodes connected by bidirectional channels is:

$T = t_s + t_w*m *k$

Step1: k= 1

$T = t_s + t_w * m *1$

$T = t_s + t_w * m * P/8$ //Note number of processors = 8

Step 2 : k =2

$T = t_s + t_w * m * 2$

$T = t_s + t_w * m * P/4$

Step 3: k =4

$T = t_s + t_w * m * 4$

$T = t_s + t_w * m * P/2$

Adding:$logP(t_s + t_w * m (P/8 + P/4 + P/2))$

Which is not equal to:
$logP(t_s + t_w * m * P/2)$

Can somebody please guide me what is my mistake?
Zulfi.

 

[Mark44]

Zulfi, your solution on StackExchange doesn't make sense to me. Here's a drawing of a balanced binary tree with 6 nodes.

If the binary tree is balanced, then every leaf node will be the same distance away from the root. In the solution you linked to, there are 8 nodes, numbered 0 through 7. If you want, you can imagine that the nodes in the figure above are numbered from 0 through 5. The tree in the drawing can have one more node and still be balanced, as the left subnode under 5 in the figure above, but where will the 8th node go? I don't see anywhere it can go and still leave you with a balanced binary tree. Maybe this is why you aren't getting the answer you think you should get.

 

[zak100]

Hi,
Thanks for your reply.

I don't have to create a balanced binary tree. I have provided a balanced binary such that:
P0 (i.e processor zero) contains message zero (i.e. M0), P1 conatins M1, P2 contains M2, P3 contains M3, P4 contains M4, P5 contains M5, P6 contains M6, and P7 contains M7.

However after all to all broadcast I would have such a situation that each processor has all the messages.
i.e P0 has messages M0, M1, M2, M3, M4, M5, M6, M7
P1 also has M0, M1, M3, M3, M4, M5, M6, M7 and so P2, P3, P4,...P7.

Now equation (1) above is used to calculate the timing for this 3 step communication. I would calculate the timing for each step and then sum them to calculate the overall timing. This overall timing should be same as equation (2).

3 steps means log base 2 of 8. There are 8 processors 0---7. So it requires 3 steps. Some how after the sum i.e equation (3), the 2nd term of equation (3), should produce 4 which is same as p/2 as in equation (2).

I have also provided the link of the question.

Zulfi.

 

[Mark44]

I don't have to create a balanced binary tree. I have provided a balanced binary such that:
P0 (i.e processor zero) contains message zero (i.e. M0), P1 conatins M1, P2 contains M2, P3 contains M3, P4 contains M4, P5 contains M5, P6 contains M6, and P7 contains M7.

Yes, I understand all that, but what I'm saying is what does your balanced binary tree with 8 nodes look like? The tree in the drawing I provided has 6 nodes. The 3 leaf nodes are all two links away from the root. I can add one more leaf, and the tree will still be balanced, with all leaf nodes still two links away from the root, and it will have 7 nodes. How can you add one more node and keep the binary tree balanced?

Please draw such a tree for me.

 

[zak100]

Hi,
Thanks for your reply.

I am uploading an image of a balanced binary tree which can be used for both for All-to-All broadcast and one

-to-All broadcast. Note Fat binary tree is not required.

Thanks for your interest in my problem.

God bless you.
Zulfi.

 

[Mark44]

OK, I was under the impression that all nodes had to populated.

Step1: k= 1
$T = t_s + t_w * m *1$

$T = t_s + t_w * m * P/8$ //Note number of processors = 8
<snip - 2 more steps>

What does the value of k = 1 mean as far as the message exchanges are concerned?
Same question for the steps with k = 2 and k = 3.

Adding:$logP(t_s + t_w * m (P/8 + P/4 + P/2))$

What are you adding to get the above?

From the work you showed before, you have:
k = 1
$T_1 = t_s + t_w * m * P/8$
k = 2
$T_2 = t_s + t_w * m * P/4$
k = 3
$T_3 = t_s + t_w * m * P/2$
(I added subscripts to these T values.)
How did you go from these three equations to something involving $\log(P)$?
If you add $T_1, T_2$, and $T_3$, you get $3t_s + t_w (P/8 + P/4 + P/2)$. Where does $\log(P)$ come from?