I think trees will seem to be a good choice when there are interactions only between nodes 0 and 1, 2 and 3, ... for most of the times.
ote
I am not really seeing how you alleviate the root bandwidth problem in "fat trees" by placing the higher bandwidth links near the root. What are you accomplishing by placing the higher bandwidth links there?
PID_1
@ote Imagine you pick a pair of processors at random and want to send a message from one to the other. The probability that the message goes through a certain link is proportional to how close it is to the root. (For example, about half a pairs send their message through the top-most link, a quarter through the middle, and an only an eighth through the lower level in the example above.) So if your communication pattern is closer to a random distribution that one that favors local communication, the upper links become a bottleneck, as they need to handle many more messages than the lower ones. Increasing the bandwidth of those links allows them to handle that higher amount of communication that they will need to sustain.
makingthingsfast
In class, we talked about how trees would capture locality for any divide and conquer, which seems to be what others have said in the thread above. It would be bad though if we had to communicate across subtrees because we would get stuck in some channels. We want to increase bisection bandwidth through increasing the number of alternate routes or by using fat trees which has expanded links between subtrees.
Funky9000
I was wondering if we could add a link between "bunch of nodes" in the tree, such as a link among nodes in the level, to reduce the latency?
krillfish
@Funky9000 What do you mean by "bunch of nodes"? The fat links are used to preserve the tree structure of the topology. The specific case for this was, "What if you have to use the tree topology?" If you add different links between different parts of the tree (like between 0+1 and 6+7), you'd get a different topology. Let me know if I misinterpreted what you said.
Funky9000
@krillfish, my apologies, I am saying we could add links among nodes in the same "level" of the tree structure. Eg. a binary tree has 2^k nodes per level and all nodes in that level have a circular link for instance.
mallocanswer
I'm a little confused here. Why do we need higher bandwidth links near the root? @PID_1, I understand "the probability that the message goes through a certain link is proportional to how close it is to the root". But if a link has more messages to transmit, isn't it better to add more links to this route? Because a link can only pass one message at a time.
mallocanswer
@Funky9000, you can choose the topology based on your application or you should write your program according to the topology. In my opinion, if you have circular link between leaf nodes, there is no need to add upper level links.
ArbitorOfTheFountain
Isn't the notion of creating higher bandwidth links essentially the same as creating more links? I guess I'm thinking of the highway analogy presented a previous lecture.
bmperez
@ArbitorOfTheFountain Not necessarily. Bandwidth is the number of packets per unit time, so you can increase it by either increasing the number of packets transmitted at once, or by decreasing the time it takes for a packet to be sent. Thus, one way, as you mentioned, would be to increase the number of links, to allow more packets to be sent in parallel. Alternately, you could increase the speed of the existing link(s), and this would achieve the same effect. There are many ways to change the link's speed, but the typical way of doing so is by changing the physical medium of communication.
In terms of the highway analogy, we could increase the speed limit of the highway (assuming all drivers will naturally go faster in response), and this will increase the highway's overall bandwidth.
stride16
We should note, that in the example of the trees provided in the slide above, it is easy to capture locality for a divide and conquer method. One potential drawback, however is that communication between subtrees can increase latency. Using fat trees, or even increasing the number of possible routes one can take, can increase the bisection bandwidth.
huehue
How do you reason about the bisection bandwidth if the links themselves have different bandwidths? What would be the bisection bandwidth for the fat tree in this slide?
jellybean
@huehue The bisection bandwidth is the minimum bandwidth that cuts the tree in half. In this case, it would be the bandwidth between the two highest nodes, 2 times the bandwidth at the next hierarchical level, or 4 times the bandwidth at the lowest level--whichever is smallest.
I think trees will seem to be a good choice when there are interactions only between nodes 0 and 1, 2 and 3, ... for most of the times.
I am not really seeing how you alleviate the root bandwidth problem in "fat trees" by placing the higher bandwidth links near the root. What are you accomplishing by placing the higher bandwidth links there?
@ote Imagine you pick a pair of processors at random and want to send a message from one to the other. The probability that the message goes through a certain link is proportional to how close it is to the root. (For example, about half a pairs send their message through the top-most link, a quarter through the middle, and an only an eighth through the lower level in the example above.) So if your communication pattern is closer to a random distribution that one that favors local communication, the upper links become a bottleneck, as they need to handle many more messages than the lower ones. Increasing the bandwidth of those links allows them to handle that higher amount of communication that they will need to sustain.
In class, we talked about how trees would capture locality for any divide and conquer, which seems to be what others have said in the thread above. It would be bad though if we had to communicate across subtrees because we would get stuck in some channels. We want to increase bisection bandwidth through increasing the number of alternate routes or by using fat trees which has expanded links between subtrees.
I was wondering if we could add a link between "bunch of nodes" in the tree, such as a link among nodes in the level, to reduce the latency?
@Funky9000 What do you mean by "bunch of nodes"? The fat links are used to preserve the tree structure of the topology. The specific case for this was, "What if you have to use the tree topology?" If you add different links between different parts of the tree (like between 0+1 and 6+7), you'd get a different topology. Let me know if I misinterpreted what you said.
@krillfish, my apologies, I am saying we could add links among nodes in the same "level" of the tree structure. Eg. a binary tree has 2^k nodes per level and all nodes in that level have a circular link for instance.
I'm a little confused here. Why do we need higher bandwidth links near the root? @PID_1, I understand "the probability that the message goes through a certain link is proportional to how close it is to the root". But if a link has more messages to transmit, isn't it better to add more links to this route? Because a link can only pass one message at a time.
@Funky9000, you can choose the topology based on your application or you should write your program according to the topology. In my opinion, if you have circular link between leaf nodes, there is no need to add upper level links.
Isn't the notion of creating higher bandwidth links essentially the same as creating more links? I guess I'm thinking of the highway analogy presented a previous lecture.
@ArbitorOfTheFountain Not necessarily. Bandwidth is the number of packets per unit time, so you can increase it by either increasing the number of packets transmitted at once, or by decreasing the time it takes for a packet to be sent. Thus, one way, as you mentioned, would be to increase the number of links, to allow more packets to be sent in parallel. Alternately, you could increase the speed of the existing link(s), and this would achieve the same effect. There are many ways to change the link's speed, but the typical way of doing so is by changing the physical medium of communication.
In terms of the highway analogy, we could increase the speed limit of the highway (assuming all drivers will naturally go faster in response), and this will increase the highway's overall bandwidth.
We should note, that in the example of the trees provided in the slide above, it is easy to capture locality for a divide and conquer method. One potential drawback, however is that communication between subtrees can increase latency. Using fat trees, or even increasing the number of possible routes one can take, can increase the bisection bandwidth.
How do you reason about the bisection bandwidth if the links themselves have different bandwidths? What would be the bisection bandwidth for the fat tree in this slide?
@huehue The bisection bandwidth is the minimum bandwidth that cuts the tree in half. In this case, it would be the bandwidth between the two highest nodes, 2 times the bandwidth at the next hierarchical level, or 4 times the bandwidth at the lowest level--whichever is smallest.