Some notes from lecture:
1. O(N) cost, N here is the number of switches used.
2. If bidirectional, the maximum latency is N/2.
firebb
The major advantage of a ring structure over bus is that each node could communicate with it neighbor through the exclusive link regardless of other communication, which is not possible in bus structure since the bus is shared and broadcasting. This improves parallelism.
pk267
Prof Kayvon said in class: If we want all processors on one side of the ring to communicate with all the processors on the other side of the ring, this is not a good topology to have. Could someone explain what he really means when he says that? He said it in context of bisection bandwidth.
shpeefps
I too have the same question as pk267
eosofsky
Cost is determined by the amount of hardware.
googlebleh
@pk267 @shpeefps So in the given scenario, all processors may want to send messages to any other processor.
Bisection Bandwidth
Here's a visualization of the bisection: http://i.imgur.com/gJVDySL.jpg
When Kayvon says that the "bandwidth remains constant," he means that, even as nodes are added to the network, after you bisect the ring there is still the same amount of bandwidth where the red line cut the network. The same amount of bandwidth is available when sending messages from above the red line to below the red line, regardless of how many nodes are on either side.
The Performance Problem
In this use case, there can be several nodes trying to communicate to other nodes across the bisection trying to communicate. And since the bandwidth remains constant even as the number of nodes trying to communicate increases, at some critical point the bandwidth won't be able to keep up with the load, and these messages going across the bisection could take a very long time.
themj
In this case, the bisection bandwidth would be 2. No matter where you bisect the ring, you will cut through the left side and right side of the ring. This becomes a problem when more nodes are added since you could have thousands of nodes that could be completely bottlenecked if just a wire on the right side and a wire on the left side of the ring are busy.
koala
Is it always desirable to have a higher bisection bandwidth? It seems that it would be best if bisection bandwidth is roughly linear to keep the cost down when we only have a few nodes.
Some notes from lecture: 1. O(N) cost, N here is the number of switches used. 2. If bidirectional, the maximum latency is N/2.
The major advantage of a ring structure over bus is that each node could communicate with it neighbor through the exclusive link regardless of other communication, which is not possible in bus structure since the bus is shared and broadcasting. This improves parallelism.
Prof Kayvon said in class: If we want all processors on one side of the ring to communicate with all the processors on the other side of the ring, this is not a good topology to have. Could someone explain what he really means when he says that? He said it in context of bisection bandwidth.
I too have the same question as pk267
Cost is determined by the amount of hardware.
@pk267 @shpeefps So in the given scenario, all processors may want to send messages to any other processor.
Bisection Bandwidth
Here's a visualization of the bisection: http://i.imgur.com/gJVDySL.jpg When Kayvon says that the "bandwidth remains constant," he means that, even as nodes are added to the network, after you bisect the ring there is still the same amount of bandwidth where the red line cut the network. The same amount of bandwidth is available when sending messages from above the red line to below the red line, regardless of how many nodes are on either side.
The Performance Problem
In this use case, there can be several nodes trying to communicate to other nodes across the bisection trying to communicate. And since the bandwidth remains constant even as the number of nodes trying to communicate increases, at some critical point the bandwidth won't be able to keep up with the load, and these messages going across the bisection could take a very long time.
In this case, the bisection bandwidth would be 2. No matter where you bisect the ring, you will cut through the left side and right side of the ring. This becomes a problem when more nodes are added since you could have thousands of nodes that could be completely bottlenecked if just a wire on the right side and a wire on the left side of the ring are busy.
Is it always desirable to have a higher bisection bandwidth? It seems that it would be best if bisection bandwidth is roughly linear to keep the cost down when we only have a few nodes.