here the height of the mesh and the width of the mesh is sqrt(N). Hence to get from one end of the mesh to the other in the worst case we would have to travel sqrt(n) to reach that nodes row and then another sqrt(n) to reach that nodes column. Hence a total latency of 2*sqrt(n) => O(sqrt(N)).
This comment was marked helpful 2 times.
analysiser
Question:
If the O(sqrt(N)) latency means the travel cost for one node to another, what does the O(N) cost mean?
This comment was marked helpful 0 times.
mofarrel
The $O(N)$ is the cost of the network. It is the number of nodes in the network. Here there is $1$ node for each processor connected to the interconnect. This gives us $O(N^2)$ nodes.
This comment was marked helpful 0 times.
kayvonf
For a network with N nodes, there are O(N) wires, so cost is O(N). Worse cast latency is 2 * sqrt(N).
here the height of the mesh and the width of the mesh is sqrt(N). Hence to get from one end of the mesh to the other in the worst case we would have to travel sqrt(n) to reach that nodes row and then another sqrt(n) to reach that nodes column. Hence a total latency of 2*sqrt(n) => O(sqrt(N)).
This comment was marked helpful 2 times.
Question:
If the O(sqrt(N)) latency means the travel cost for one node to another, what does the O(N) cost mean?
This comment was marked helpful 0 times.
The $O(N)$ is the cost of the network. It is the number of nodes in the network. Here there is $1$ node for each processor connected to the interconnect. This gives us $O(N^2)$ nodes.
This comment was marked helpful 0 times.
For a network with
Nnodes, there are O(N) wires, so cost is O(N). Worse cast latency is 2 * sqrt(N).This comment was marked helpful 0 times.