1
$\begingroup$

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly at a loss as to how to begin writing the message passing code to solve this. Any help on knowing how to break this problem down would be greatly appreciated.

The question is as follows:

Suppose $N^2$ processes are arranged in an $N$ by $N$ square grid. $P_{i j}$ refers to at the grid position (row $i$, column $j$). A process can communicate, using message passing, only with its neighbors to the left and right, and above and below. (Processes on the corners have only two neighbors; others on the edges of the grid have three neighbors.) Every process has a local integer value $v_{i j}$. Show an efficient computation scheme at each of the nodes that will eventually result in every process knowing the maximum of all values in the grid.

$\endgroup$
  • 1
    $\begingroup$ It's impossible for any information to reach from one end of the grid to the other in less than $O(N)$ wall clock time, because nodes can only communicate with their neighbors and the diameter of the $N \times N$ grid graph is $2N$. So what are you measuring for "efficiency"? $\endgroup$ – Aaron Rotenberg Dec 6 '19 at 21:19
  • $\begingroup$ From what I understand, after a certain number of iterations, each process would have computed a correct maximum value. $\endgroup$ – Travis Tubbs Dec 6 '19 at 21:50
  • 2
    $\begingroup$ Right, but there is a trivial algorithm for this: just iterate having each node set its new value to the maximum of its current value and the current values of the adjacent nodes. This converges to every node having the global maximum within $2N$ iterations. It may be possible to use fewer total messages, which is why I was asking what "efficient" meant here. $\endgroup$ – Aaron Rotenberg Dec 6 '19 at 22:11
2
$\begingroup$

Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes.

After this, the last row would contain the maximum values of each column. Then, we could have the last row propagate the maximum value in the right direction so that the (n,n)th element contains the maximum value from this row. Since this row contained the maximum values from each column, (n,n)th element will essentially possess the maximum value from the entire grid.

We could then choose to propagate this value through the grid in parallel backwards till all the nodes know about this maximum value.

Complexity will be O(n) and there will be 4n hops of message passing through this proposed scheme.

Edit: Here's A pseudo-code. Disclaimer: not tested, might contain bugs

findMaxAllThreads(){
    int maxVal;

    // At the start, each element's max value will exactly be its value itself.
    maxVal = procId.val;

    // If this is the first element in the column, simply send the current 
    // max value to the next element within the column.
    if(procId.row == 1)
        sendMessage(procId.row + 1, procId.col, maxVal);

    // For any other element in a particular column, except the last one, 
    // compare the received value with the current max value and send the
    // updated value to the next element.
    else if(procId.row < n)
    {
        // wait for the message from the previous element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value till this node.
        if(val > maxVal)
            maxVal = val;

        // send the updated max value to the next element in the column.
        sendMessage(procId.row + 1, procId.col, maxVal);
    }

    // If we reach the last element in the column, we need to propagate the 
    // values rightwards to the next element within the last row.
    else 
    {
        // Receive the message from the (n-1)th element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value. Note that this will be the maximum value of 
        // this particular column.
        if(val > maxVal)
            maxVal = val;

        // If this is the (n,1)th element in the whole grid (bottom left), then
        // simply propagate the max value to the next element rightwards in the
        // row.
        if(procId.col == 1)
            sendMessage(procId.row, procId.col + 1, maxVal);
        else 
        {
            // Wait for the value from the previous element in this row. 
            recvMessage(procId.row, procId.col - 1, val);

            // Update the max value till now. 
            if(val > maxVal)
                maxVal = val;

            // If this is not the (n,n)th element in the grid, propagate the 
            // value to the right.
            if(procId.col != n)
            {
                // Propagate the max value to the right.
                sendMessage(procId.row, procId.col + 1, maxVal);
            }

            // if this is the bottom-right (n,n)th element in the grid, wait 
            // for the final value arriving from  the (n, n-1)th element from 
            // the left. 
            else
            {
                // Receive the message from the (n-1)the element in the nth row.
                recvMessage(procId.row, procId.col - 1, val);

                // Update the value. Note that this is also the maximum value 
                // in the entire grid.
                if(val > maxVal)
                    maxVal = val;

                // Now maxVal contains the maximum value from all the processes.
                // We could choose to report it or if we want, we could 
                // propagate it all the way back to the first node, so that 
                // it's known globally as the max value.
            }
        }
    }
}
$\endgroup$
  • $\begingroup$ I kind of follow what you're saying, but would you mind showing what you mean in sudo code? $\endgroup$ – Travis Tubbs Dec 7 '19 at 0:02
  • $\begingroup$ There are a a lot of assumptions in this pseudo code that I've posted above. Hope it conveys the idea. this piece of code is intended to run on all of the processes as is and takes care of handling message passing. $\endgroup$ – ss09 Dec 7 '19 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.