Cost of communication is non-uniform. If two tasks need to communicate often, assign them to nearby processors(nodes).
holard
The slide indicates that the average latency is in O(sqrt(N)). Is it also the case that the worst-case latency is also O(sqrt(N))?
Metalbird
So from what I can tell, the worst case would be if you have to move from, for example, the top left corner to the bottom right corner. In that case the latency would be O(2N). So in that case that would make the latency much worse than the average latency of O(sqrt(N)). However, if we only have to move from top left to the one to the right of it, the latency is O(1). Out of all possible moves the average latency is O(sqrt(N)), but as nemo mentioned above, the cost is non-uniform and can vary significantly.
sushi
In my opinion, in both of the worst case and the average case, the latency is O(sqrt(N)). The reason is that the length of the side of the mesh is sqrt(N) given N nodes. Therefore, even if the top-left nodes wants to communicate with the down-right node, it only takes O(2sqrt(N)).
sampathchanda
I agree with sushi, since the path length would at max be 2*sqrt(N) only for communication between any of the nodes.
Cost of communication is non-uniform. If two tasks need to communicate often, assign them to nearby processors(nodes).
The slide indicates that the average latency is in O(sqrt(N)). Is it also the case that the worst-case latency is also O(sqrt(N))?
So from what I can tell, the worst case would be if you have to move from, for example, the top left corner to the bottom right corner. In that case the latency would be O(2N). So in that case that would make the latency much worse than the average latency of O(sqrt(N)). However, if we only have to move from top left to the one to the right of it, the latency is O(1). Out of all possible moves the average latency is O(sqrt(N)), but as nemo mentioned above, the cost is non-uniform and can vary significantly.
In my opinion, in both of the worst case and the average case, the latency is O(sqrt(N)). The reason is that the length of the side of the mesh is sqrt(N) given N nodes. Therefore, even if the top-left nodes wants to communicate with the down-right node, it only takes O(2sqrt(N)).
I agree with sushi, since the path length would at max be 2*sqrt(N) only for communication between any of the nodes.