Just to confirm: this interconnect allows multiple nodes to use the wire at once, correct? Otherwise, it would seem that this configuration has the same problem as the bus, in that there will be contention for the line.
afzhang
Yes, multiple nodes can use the wire at once. However, there could still be some issues with blocking here. Does anyone remember if signals can be sent in both directions around the ring? (That would reduce some of the possible blocking.)
yuel1
@afzhang I believe this is blocking either way. And I believe signals can be sent in both directions as wires don't really care about which way the current flows.
Kapteyn
This slide got me thinking about bisection bandwidth and why it's a relevant metric of system performance.
Bisection bandwidth is relevant under certain situations like when traffic is random. If traffic is random then the probability of a given message needing to travel across the two halves of a network with N nodes is 1/2. If all nodes are sending messages at every single point in time, then we can expect that N/2 messages will need to traverse the two halves. The bisection bandwidth imposes a limit on how much traffic can actually cross the two halves.
But in this case, the bisection bandwidth of 2 data units doesn't seem to fully capture the limitations of the ring interconnect since nodes 0 and 2 cannot communicate at the same time as nodes 1 and 3 no matter which way around the ring you send the packets. If nodes 0 and 3 wished to communicate at the same time as nodes 1 and 2, then they could send their packets simultaneously. So it is not always the case that we can even reach the bisection bandwidth.
Another thing I realized was that we can have packets being sent from nodes 0 to 1, 1 to 2, and 2 to 3 at the same time (assuming nodes can simultaneously send and receive packets). This shows that in situations where data traffic is not random but highly local, the bisection bandwidth is not a good metric of system performance. In this case it under estimates performance.
parallelfifths
@Kapteyn, what you're describing in paragraph 3 is blocking, correct? I do think it's true that bisection bandwidth will never be a useful measure for blocking situations.
Kapteyn
@parallelfifths Yes, my intuition tells me that we can always create a situation where blocking networks will perform worse than their bisection bandwidths. I think that's a concise way to look at it.
Sherry
why the cost here is o(n), which is the same with Mesh? I think "cost" here means if a new node is added, how much work need to be done. For Mesh, if a new node is added, n switch/routers will be deployed, so the cost is o(n). Is my understanding wrong?
parallelfifths
@Sherry, I believe that in both the ring and mesh topologies, if a new node is added, only a single switch/router needs to be added for that node, hence the O(n) cost. Compare this to say, the crossbar topology, in which n switches need to be added per new node. Hence the cost of a crossbar topology is O(n^2).
Sherry
@parallelfifths Now I understand. Thank you for reply. For ring, the cost per node is o(1), but there are n nodes, so the total cost is o(n). For mesh, the cost per node is 4/o(1), then total cost is o(4n)/o(n) for n nodes. For crossbar, the total cost is o(n) per node * n nodes = o(n^2)
Just to confirm: this interconnect allows multiple nodes to use the wire at once, correct? Otherwise, it would seem that this configuration has the same problem as the bus, in that there will be contention for the line.
Yes, multiple nodes can use the wire at once. However, there could still be some issues with blocking here. Does anyone remember if signals can be sent in both directions around the ring? (That would reduce some of the possible blocking.)
@afzhang I believe this is blocking either way. And I believe signals can be sent in both directions as wires don't really care about which way the current flows.
This slide got me thinking about bisection bandwidth and why it's a relevant metric of system performance.
Bisection bandwidth is relevant under certain situations like when traffic is random. If traffic is random then the probability of a given message needing to travel across the two halves of a network with N nodes is 1/2. If all nodes are sending messages at every single point in time, then we can expect that N/2 messages will need to traverse the two halves. The bisection bandwidth imposes a limit on how much traffic can actually cross the two halves.
But in this case, the bisection bandwidth of 2 data units doesn't seem to fully capture the limitations of the ring interconnect since nodes 0 and 2 cannot communicate at the same time as nodes 1 and 3 no matter which way around the ring you send the packets. If nodes 0 and 3 wished to communicate at the same time as nodes 1 and 2, then they could send their packets simultaneously. So it is not always the case that we can even reach the bisection bandwidth.
Another thing I realized was that we can have packets being sent from nodes 0 to 1, 1 to 2, and 2 to 3 at the same time (assuming nodes can simultaneously send and receive packets). This shows that in situations where data traffic is not random but highly local, the bisection bandwidth is not a good metric of system performance. In this case it under estimates performance.
@Kapteyn, what you're describing in paragraph 3 is blocking, correct? I do think it's true that bisection bandwidth will never be a useful measure for blocking situations.
@parallelfifths Yes, my intuition tells me that we can always create a situation where blocking networks will perform worse than their bisection bandwidths. I think that's a concise way to look at it.
why the cost here is o(n), which is the same with Mesh? I think "cost" here means if a new node is added, how much work need to be done. For Mesh, if a new node is added, n switch/routers will be deployed, so the cost is o(n). Is my understanding wrong?
@Sherry, I believe that in both the ring and mesh topologies, if a new node is added, only a single switch/router needs to be added for that node, hence the O(n) cost. Compare this to say, the crossbar topology, in which n switches need to be added per new node. Hence the cost of a crossbar topology is O(n^2).
@parallelfifths Now I understand. Thank you for reply. For ring, the cost per node is o(1), but there are n nodes, so the total cost is o(n). For mesh, the cost per node is 4/o(1), then total cost is o(4n)/o(n) for n nodes. For crossbar, the total cost is o(n) per node * n nodes = o(n^2)