Can someone explain how this works for O(1) latency?
It seems that it would be faster for 0 to talk to 0 than for 0 to talk to 7.
funkysenior15
@cube
The picture is a bit misleading, in that the circles in the middle are switches, not routers. So for 0 to talk to 7, it would not need to hop over 8 routers, as it may seem.
In a crossbar, each pair of nodes has a dedicated line, connected by a switch. When the switch is turned on, the line becomes active.
ChandlerBing
@cube In other words, the yellow circles represent connections between the nodes and not routers. Thus for 0 to talk to 7 that particular connection will be switched on and they can communicate in one cycle. This holds true for any pair of nodes and hence the latency is constant.
If you want to be really technical, a longer distance wire would technically take longer for data to traverse (due to physical properties). However, the dimensions here are so small, it doesn't make much of a difference.
rflood
@chandlerbing. That image 403's for me
Does this picture without the duplicated nodes on the left and imply that spatially, at least, a signal would go down into the grid, then come back up to the endpoint?
With concurrent different messages taking different paths through the grid?
msebek
@HLAHat More precisely, the time it takes for a signal to travel across the chip is a limiting criteria that chip designers consider when determining the maximum clock frequency of a chip.
For the sanity of all engineers involved, traversal of the network would take the same number of clock cycles no matter what destination or source is. Both sides must observe the same clock, since that is how the sending side knows when to put the next bit on the bus.
grose
What exactly is the difference between a switch and a router then? Is it that a router doesn't form dedicated connections, and can choose to send packets to one place or another, whereas a switch is kind of like a "railroad" switch, in that it just changes the physical line
ChandlerBing
@grose: Yes, I would think of it as - A switch can be only ON or OFF and implies that there is or isn't a connection between 2 points. Router should have the ability to decide (based on the routing scheme) which of the many possible connections it should send the packet to.
lament
@grose Naively, I would say that a switch connects one fixed link to another and can only be open/close or turned on/off. A router can take requests from across multiple links and channel them along some other appropriate link. Googling this would be a good idea.
grose
But, http://15418.courses.cs.cmu.edu/spring2015/lecture/interconnects/slide_008 seems to 1) treat a switch and router as the same, and 2) say a switch connects a fixed number of inputs to a fixed number of outputs (instead of saying just one)
Kapteyn
@rflood I believe the illustration on the next slide answers your question. The nodes on the left are the actual nodes. There's a wire connecting the "nodes" on the top to the matching nodes on the left. The nodes at the top are just there to indicate the end point of those wires (not shown on this slide) which wrap around to the corresponding node.
rhnil
I found this picture very helpful for me to understand how crossbar works. It explains why crossbar has $O(1)$ latency and how crossbar is different from mesh.
pmassey
I just want to make sure I'm correct -- when discussing blocking vs. non-blocking, we only considering processors pairs that do not overlap, correct?
For example, in this instance, if any two processors wanted to communicate with the same processor (e.g., 1 -> 4 and 2 -> 4) it would seem as though their communication lines would conflict. However, because we don't allow the overlap of processor 4, this example is irrelevant.
caretcaret
@pmassey: Yes, 4 should only be communicating with one processor at a time. The next slide shows more clearly why this is non-blocking: you can connect two nodes "horizontally" and two other nodes "vertically".
Can someone explain how this works for O(1) latency?
It seems that it would be faster for 0 to talk to 0 than for 0 to talk to 7.
@cube The picture is a bit misleading, in that the circles in the middle are switches, not routers. So for 0 to talk to 7, it would not need to hop over 8 routers, as it may seem.
In a crossbar, each pair of nodes has a dedicated line, connected by a switch. When the switch is turned on, the line becomes active.
@cube In other words, the yellow circles represent connections between the nodes and not routers. Thus for 0 to talk to 7 that particular connection will be switched on and they can communicate in one cycle. This holds true for any pair of nodes and hence the latency is constant.
This picture might be a better representation: http://lovingod.host.sk/tanenbaum/8-3.png
If you want to be really technical, a longer distance wire would technically take longer for data to traverse (due to physical properties). However, the dimensions here are so small, it doesn't make much of a difference.
@chandlerbing. That image 403's for me
Does this picture without the duplicated nodes on the left and imply that spatially, at least, a signal would go down into the grid, then come back up to the endpoint?
With concurrent different messages taking different paths through the grid?
@HLAHat More precisely, the time it takes for a signal to travel across the chip is a limiting criteria that chip designers consider when determining the maximum clock frequency of a chip.
For the sanity of all engineers involved, traversal of the network would take the same number of clock cycles no matter what destination or source is. Both sides must observe the same clock, since that is how the sending side knows when to put the next bit on the bus.
What exactly is the difference between a switch and a router then? Is it that a router doesn't form dedicated connections, and can choose to send packets to one place or another, whereas a switch is kind of like a "railroad" switch, in that it just changes the physical line
@grose: Yes, I would think of it as - A switch can be only ON or OFF and implies that there is or isn't a connection between 2 points. Router should have the ability to decide (based on the routing scheme) which of the many possible connections it should send the packet to.
@grose Naively, I would say that a switch connects one fixed link to another and can only be open/close or turned on/off. A router can take requests from across multiple links and channel them along some other appropriate link. Googling this would be a good idea.
But, http://15418.courses.cs.cmu.edu/spring2015/lecture/interconnects/slide_008 seems to 1) treat a switch and router as the same, and 2) say a switch connects a fixed number of inputs to a fixed number of outputs (instead of saying just one)
@rflood I believe the illustration on the next slide answers your question. The nodes on the left are the actual nodes. There's a wire connecting the "nodes" on the top to the matching nodes on the left. The nodes at the top are just there to indicate the end point of those wires (not shown on this slide) which wrap around to the corresponding node.
I found this picture very helpful for me to understand how crossbar works. It explains why crossbar has $O(1)$ latency and how crossbar is different from mesh.
I just want to make sure I'm correct -- when discussing blocking vs. non-blocking, we only considering processors pairs that do not overlap, correct?
For example, in this instance, if any two processors wanted to communicate with the same processor (e.g., 1 -> 4 and 2 -> 4) it would seem as though their communication lines would conflict. However, because we don't allow the overlap of processor 4, this example is irrelevant.
@pmassey: Yes, 4 should only be communicating with one processor at a time. The next slide shows more clearly why this is non-blocking: you can connect two nodes "horizontally" and two other nodes "vertically".