You have access to a high performance computer consisting of 10,000 processors.
The processors are connected in a 2-dimensional mesh of 100 rows and 100 columns without any wrap around edges.
You need to find the sum of 1,000,000 integers stored in a file.
Assuming you can only perform I/O with processor (0,0), how would you take advantage of the mesh to perform the summation in parallel? Give an algorithm.
Remember that in a mesh a processor could only communicate with its north, south, west, and east processor except for those processors on the edges.
Assume adding two integers takes unit time and processors can perform infinite precision addition.
Assume a pair of processors can send and receive a message containing any number of integers in unit time.
Further assume that a processor can send at most 4 simultaneous messages to its neighbors but can only receive one message at a time.
In other words, send is non-blocking but receive is a blocking action.
How much time does your algorithm take?