|
Let's see how broadcast unfolds in a Divacon
computation/communication graph:
|
Broadcast left-most value to all positions |
|
|
\(PDC(d_{lr},c_{lr},id,(id,other): \# corr, atom?, id)\) |
|
| Input |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
preadjust=id so keep dividing |
| \(d_{lr}\) 3x |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
stopped at atom?=true |
| # corr |
0 |
1.0 |
2 |
3.2 |
4 |
5.4 |
6 |
7.6 |
communicated forward to corresponding element |
| (id,other) |
0 |
0 |
2 |
2 |
4 |
4 |
6 |
6 |
did no-op on left,
picked "other" on right.
then \(c_{lr}\) |
| \(c_{lr}\)(#1) |
0 |
0 |
2 |
2 |
4 |
4 |
6 |
6 |
next is (id,other) : # corr
send fwd to corr |
| # corr |
0 |
0 |
2.0 |
2.0 |
4 |
4 |
6.4 |
6.4 |
sent 0'th forward 0'th, etc.
then (id,other) |
| e.g.: id(4)=4, other(6.4)=4 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
ready for \(c_{lr}\) |
| now \(c_{lr}\#2\) |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
next (id,other):#corr |
| # corr |
0 |
0 |
0 |
0 |
4.0 |
4.0 |
4.0 |
4.0 |
send n'th fwd to n'th
next is (id,other) |
| id(0)=0, other(4.0)=0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
next: \(c_{lr}\#3\) |
| \(c_{lr}\) (#3) output |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
all done |
By this method, broadcast takes \(log(N)\) steps (here, three steps),
each step includes one division, one combination, and a full set of
simultaneous parallel communications (one way only from LHS to RHS)
and local operations (selecting \(other\)).
|
