Previous | Next --- Slide 22 of 49
Back to Lecture Thumbnails
bochet

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.