This topology is of high performance because everyone can talk to each one in the graph, with essentially 0 latency.
williamx
What are the yellow circles that connect the intersecting links? It seems like they have to determine which direction to send incoming information. How can the information be sent through two nodes to achieve O(1) latency, when it has to pass through multiple yellow circles?
BestBunny
@williamx In the above diagram, the yellow circles are switches and they do indeed determine which direction to send incoming information. However, information sent between nodes achieving O(1) latency is based on a crossbar interconnect with nodes being connected by one long wire (without intermediate switches) as I remember from lecture.
axiao
Another way to maybe interpret the O(1) latency is that there is only 1 switch doing anything for any message.
For example, if we want to send a message from 5 to 7, then we only need to toggle the switch 7 on row 5 (0-indexed) to route the message correctly. The message starts from node 5, travels horizontally until it hits this switch, then heads up to the destination. All other switches along the message path simply just forward the message along the same wire. Check out this link for a more in detailed description of what I just said.
This also means that the multi-stage logarithmic network has latency O(log N), since at most log N switches need to make a decision on how to route the message (examine each bit of the destination node's number's bit representation).
pk267
@BestBunny: they are not necessarily buses, as Professor Kayvon pointed out in class. They could be gates that decide whether a message goes left or right or up or down.
lfragago
This network architecture has the following characteristics:
Latency is O(1): Since every node is directly connected to every other node in the graph, the latency is O(1) (i.e. a given message from node X to node Y goes directly from X to Y without needing to pass through another node).
Number of switches is O(N^2): Since every node is connected to every other node, to connect the first node with the rest of the nodes we require N-1 switches, for the second node N-2: In total (N-1) + (N-2) + (N-3) +...1 = O(N^2)
This topology is of high performance because everyone can talk to each one in the graph, with essentially 0 latency.
What are the yellow circles that connect the intersecting links? It seems like they have to determine which direction to send incoming information. How can the information be sent through two nodes to achieve O(1) latency, when it has to pass through multiple yellow circles?
@williamx In the above diagram, the yellow circles are switches and they do indeed determine which direction to send incoming information. However, information sent between nodes achieving O(1) latency is based on a crossbar interconnect with nodes being connected by one long wire (without intermediate switches) as I remember from lecture.
Another way to maybe interpret the O(1) latency is that there is only 1 switch doing anything for any message.
For example, if we want to send a message from 5 to 7, then we only need to toggle the switch 7 on row 5 (0-indexed) to route the message correctly. The message starts from node 5, travels horizontally until it hits this switch, then heads up to the destination. All other switches along the message path simply just forward the message along the same wire. Check out this link for a more in detailed description of what I just said.
This also means that the multi-stage logarithmic network has latency O(log N), since at most log N switches need to make a decision on how to route the message (examine each bit of the destination node's number's bit representation).
@BestBunny: they are not necessarily buses, as Professor Kayvon pointed out in class. They could be gates that decide whether a message goes left or right or up or down.
This network architecture has the following characteristics:
Latency is O(1): Since every node is directly connected to every other node in the graph, the latency is O(1) (i.e. a given message from node X to node Y goes directly from X to Y without needing to pass through another node).
Number of switches is O(N^2): Since every node is connected to every other node, to connect the first node with the rest of the nodes we require N-1 switches, for the second node N-2: In total (N-1) + (N-2) + (N-3) +...1 = O(N^2)