CS 133 Discussion: Week 10

Homework 3

The proper way to approach this assignment is to divide it into phases. Phase 2 is setting up remote objects and communication among them. The starter code does most of this.

Phase 1 is to implement a single processor, single monitor, threaded solution. Each thread gets a row and executes the code shown in the assignment. A "broadcast" means entering the monitor, copying your row in, and executing a notifyAll(). "wait for row" means entering the monitor, and wait()'ing until row k is there, then copying row k.

Phase 3 is to distribute the threads onto multiple processors using the RMI servers. The threads should act as if they're on a local machine, accessing a local monitor. They needn't be aware that other threads are on other processors. The monitor functions for "broadcast" and/or "waitforrow" will handle the communication with other servers on other processors.

Checkerboard partitioning of All Pairs Shortest Path

Each entity is for one element A[myRow][myCol]. Since the algorithm to update A[i,j] requires A[i,k] and A[k,j], each entity needs these two values to proceed. A[i,k] is on the same row, A[k,j] is in the same column.

Be careful, though. In the sequential algorithm, A[1,2] will be updated before A[1,3]. In other words, if myCol is greater than k, then I need to wait until A[i,k] is updated before I get its value. Thus the "send to my row" loop is broken into two parts. 

message Elem{int row; int col; int elem};

entity RowEntity(int myRow,
                 int myCol,
                 int numberOfRows) {
  int   i, k;
  int   myElement;
  ename thisRow[N];
  ename thisCol[N];

  int   Akj, Aik;

  /* initialize */

  for (k = 0; k < numberOfRows; k++) {
    if (k == myRow) {
      /* broadcast my element to my column */
      for (i = 0; i < numberOfRows; i++) {
        if (i != myRow) /* to prevent wastefully sending to self */
          send Elem{myRow, myCol, myElement} to thisCol[i];
      }
      Akj = myElement;
    }
    else {
      receive (Elem elem) when (elem.row == k && elem.col == myCol) {
        Akj = elem.elem;
      }
    }


    if (k == myCol) {
      /* broadcast my element to my left */
      for (i = 0; i < myCol; i++) {
        send Elem{myRow, myCol, myElement} to thisRow[i];
      }
      Aik = myElement;
    }
    else {
      receive (Elem elem) when (elem.row == myRow && elem.col == k) {
        Aik = elem.elem;
      }
    }

    /* update my element */
    if (Aik + Akj < myElement)
      myElement = Aik + Akj;

    
    /* broadcast my element to my right */
    if (k == myCol) {
      for (i = myCol + 1; i < numberOfRows; i++) {
        send Elem{myRow, myCol, myElement} to thisRow[i];
      }
    }
  }

  /* send output */
}