/***
  Author :
    
    Nicholas N. Bali
    1996-Feb-26
    Adapted for Maisie v. 3.0 on 2-28-97

  Usage :

    mm2-new -input filename1 -output filename2 [-block n]

  Notes :

    The driver entity issues and exit command at the end, thereby killing
    all processes.
    A segmentation fault will result if the input and output filenames are 
    not specified.
    The default block size is set to 4.
    The largest block size is 16.
***/

/***
  Algorithm :

    This Parallel Matrix Multiply algorithm is based on Canon's algorithm
    but has been extended to allow block sizes of greater than 1.

    First, the initial A and B matrices are read in.  Each matrix has its
    elements shifted.  The A matrix has its elements shifted left on a row
    - subblock basis.  Thus the 0th subblock row is shifted left 0, and the
    1st subblock row shifted left 1, and so on.  The B matrix is shifted
    up on a row - subblock basis.

    These larger matrices are then checkerboard partitioned into smaller
    submatrices which are then passed to the matrix multiply entities.
    These entities multiply their A and B submatrices and then give their
    A submatrix to their left neighbor and their B submatrix to their
    up neighbor.  This process continues until each entity has had a chance
    to multiply/add each subblock in its row and column.

    These entities then pass their computed submatrix to the printer which
    collects and stores the submatrices into their correct position in the
    larger matrix and the proceeds to print out the matrix, nicely.
***/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "maisie.h"

#define MAX_MATRIX_SIZE    64 /* maximum NxN size of the matrix */
#define MAX_SUBMATRIX_SIZE 16 /* maximum NxN size of submatrix */

/***
 printMatrix :

   neatly prints a matrix

 Parameters :

   outFile : handle to output file
   matrix : matrix to be printed
   numberOfRows : number of rows in the matrix
   numberOfColumns : number of columns in the matrix
   padding : width of each printed element

 Return :
   integer (not used)
***/

int printMatrix(outFile, matrix, numberOfRows, numberOfColumns,padding)
FILE *outFile;
int matrix[MAX_MATRIX_SIZE][MAX_MATRIX_SIZE];
int numberOfRows;
int numberOfColumns;
int padding;
{
  int i,j; /* loop indices for extracting matrix elements */
  int temp; /* temporary holding place for matrix element */
  int spaces; /* number of spaces to print */
 
  for(i=0;i<numberOfRows;i++) {
    for(j=0;j<numberOfColumns;j++) {
      spaces=padding;
      temp = matrix[i][j];
      while(temp = temp/10)
        spaces--;
      while(spaces--)
        fprintf(outFile," ");
      fprintf(outFile,"%d",matrix[i][j]);
    }
    fprintf(outFile,"\n");
  }
}

/***
 matrixMultiply :

   takes two matrices, multiplies them, sends one up, one left and starts
   over again until its submatrix is computed

 Parameters :

   matrixSize : size of the original matrix
   submatrixSize : size of the matrix it will work on
   numberOfMultiplers : number of other entities (NxN), useful for knowing
                        how many times to send/receive matrices
***/

entity matrixMultiply{ int matrixSize, int submatrixSize, int numberOfMultipliers}
{
  int c[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE]; /* computed matrix */
  int tempA[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE]; /* temporay A matrix */
  int tempB[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE]; /* temporary B matrix */
  int i,j,k,s;
  int myRow, myCol; /* where my top left element belongs in big matrix */
  ename leftNeighbor, upNeighbor, printer; /* neighbors and printer */

  message Neighbors{ename leftNeighbor; ename upNeighbor; ename printer;}
          neighbors;
  message InitMatrix{int rowNumber; int colNumber;
                     int submatrixA[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];
                     int submatrixB[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];}
                     initMatrix;
  message LeftMatrix{int submatrixA[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];}
          leftMatrix;
  message UpMatrix{int submatrixB[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];}
          upMatrix;

/***
  Find out who my neighbors are and who the printer is
***/

  wait until {
    mtype(Neighbors) {
      leftNeighbor = msg.Neighbors.leftNeighbor;
      upNeighbor = msg.Neighbors.upNeighbor;
      printer = msg.Neighbors.printer;
    }
  }

/***
  Get the initial A and B submatrices, and where my top left
  element belongs in the big matrix
***/

  wait until {
    mtype(InitMatrix) {
      initMatrix = msg.InitMatrix;
      myRow = initMatrix.rowNumber;
      myCol = initMatrix.colNumber;
      for(i=0;i<submatrixSize;i++)
        for(j=0;j<submatrixSize;j++) {
          c[i][j]=0;
          tempA[i][j]=initMatrix.submatrixA[i][j];
          tempB[i][j]=initMatrix.submatrixB[i][j];
          for(k=0;k<submatrixSize;k++)
            c[i][j]=c[i][j] + initMatrix.submatrixA[i][k] *
                              initMatrix.submatrixB[k][j];
        }
    }
  }

/***
  Send my submatrix A left, my submatrix B left and receive
  my two new matrices.
  Multiply these matrices and store the computed values.
***/

  for(s=0;s<numberOfMultipliers - 1;s++) {  
    invoke leftNeighbor with LeftMatrix{tempA};
    invoke upNeighbor with UpMatrix{tempB}; 
    wait until {
      leftMatrix = mtype(LeftMatrix)
      and upMatrix = mtype(UpMatrix) {
        for(i=0;i<submatrixSize;i++)
          for(j=0;j<submatrixSize;j++) {
            tempA[i][j] = leftMatrix.submatrixA[i][j];
            tempB[i][j] = upMatrix.submatrixB[i][j];
            for(k=0;k<submatrixSize;k++)
              c[i][j]=c[i][j] + leftMatrix.submatrixA[i][k] *
                                upMatrix.submatrixB[k][j];
          }
      }
    }
  }
/***
  Return my computed submatrix to the printer
***/
  invoke printer with Done{myRow, myCol, c};
}


/***
 driver :

   the driver and printer

 Paramters :

   command line paramaters

 Return :

   actually exits so as to end the program
***/

entity driver {int argc, char **argv}
{
  FILE *inFile, *outFile; /* handles for input/output files */
  char *inFileName, *outFileName; /* input/output filenames */
  int matrixSize, submatrixSize; /* sizes of the matrices */

  /* various needed matrices */
  int a[MAX_MATRIX_SIZE][MAX_MATRIX_SIZE], b[MAX_MATRIX_SIZE][MAX_MATRIX_SIZE];
  int finishedMatrix[MAX_MATRIX_SIZE][MAX_MATRIX_SIZE];

  int i,j,s,t; /* loop variables */

  /* various variables needed to calculate spacing parameters */
  int currentDigitCount,highestDigitCount,temp;

  
  int row,col; /* loop variables */
  int leftNeighbor,upNeighbor; /* index for left / up neighbors */
  int shiftValue; /* shifting value */
  int numberOfMultipliers; /* number of multiplier entities (NxN) */

  /* submatrices, passed to the matrixMultiply entities */
  int submatrixA[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE],
      submatrixB[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];

  /* collection of all matrixMultiply entities */
  ename matrixMultiplier[MAX_MATRIX_SIZE][MAX_MATRIX_SIZE];

  message Done{int rowNumber; int colNumber;
               int submatrix[MAX_SUBMATRIX_SIZE][MAX_SUBMATRIX_SIZE];} done;


/***
  Initialize some variables
***/

  submatrixSize=4;
  highestDigitCount=1;
  i=1;

/***
  Read in Command Line parameters
***/
  while(i<argc) {
    if(strcmp(argv[i],"-input")==0) {
      i++;
      inFileName=argv[i++];
      printf("INFILE: %s\n",inFileName);
    }
    else if(strcmp(argv[i],"-output")==0) {
      i++;
      outFileName=argv[i++];
      printf("OUTFILE: %s\n",outFileName);
    }
    else if(strcmp(argv[i], "-block")==0) {
      i++;
      submatrixSize = atoi(argv[i++]);
    }
    else
      i++;
  }


  inFile = fopen(inFileName, "r");
  fscanf(inFile, "%d", &matrixSize);
  
/***
  Figure out the number multiplier enitites needed
***/

  numberOfMultipliers=matrixSize/submatrixSize;

/***
   Read in the first matrix, A
   While reading it in, do left shift on a subblock basis
***/
  for(row=0;row<matrixSize;row++) {
    shiftValue = row/submatrixSize;
    for(col=0;col<matrixSize;col++) {      
      fscanf(inFile,"%d",&a[row][(col+matrixSize-shiftValue*submatrixSize)%matrixSize]);
    }
  }

/***
   Read in the second matrix, B
   While reading it in, do up shift on a subblock basis
***/
  for(row=0;row<matrixSize;row++) {
    for(col=0;col<matrixSize;col++) {
      shiftValue = col/submatrixSize;
      fscanf(inFile,"%d",&b[(row+matrixSize-shiftValue*submatrixSize)%matrixSize][col]);
    }
  }

  fclose(inFile);

  printf("\n");
    
/***
   Create all matrixMultiply entities 
***/

  for(i=0;i<numberOfMultipliers;i++)
    for(j=0;j<numberOfMultipliers;j++) {
      matrixMultiplier[i][j] =
          new matrixMultiply{matrixSize,submatrixSize,numberOfMultipliers}
              at (i*numberOfMultipliers + j);
    }

/***
   Tell each matrixMultiply entity who its left and up neighbors are
***/

  for(i=0;i<numberOfMultipliers;i++) {
    if(i==0) 
      upNeighbor = numberOfMultipliers - 1;
    else
      upNeighbor = i - 1;
    for(j=0;j<numberOfMultipliers;j++) {
      if(j==0)
        leftNeighbor = numberOfMultipliers - 1;
      else
        leftNeighbor = j - 1;
      invoke matrixMultiplier[i][j] with
          Neighbors{matrixMultiplier[i][leftNeighbor],
                    matrixMultiplier[upNeighbor][j], self};
    }
  }

/***
   Give each matrixMultiply entity it submatrix, and tell where
   its top left entry is in relation to the entire matrix
***/
  for(i=0;i<numberOfMultipliers;i++) {
    for(j=0;j<numberOfMultipliers;j++) {
      for(s=0;s<submatrixSize;s++) {
        for(t=0;t<submatrixSize;t++) {
          submatrixA[s][t] = a[(i*submatrixSize)+s][(j*submatrixSize)+t];
          submatrixB[s][t] = b[(i*submatrixSize)+s][(j*submatrixSize)+t];
        }
      }

      invoke matrixMultiplier[i][j]
          with InitMatrix{i*submatrixSize,j*submatrixSize,submatrixA,submatrixB};

    }
  }


/***
   Wait for each matrixMultiplier to send back its computed submatrix
   and then print it
***/

   for(i=0;i<numberOfMultipliers;i++)
     for(j=0;j<numberOfMultipliers;j++) 
       wait until {
         mtype(Done) {
           done = msg.Done;
/***
  Place the submatrix back into to its correct position
***/
           for(s=0;s<submatrixSize;s++) {
             for(t=0;t<submatrixSize;t++) {
               finishedMatrix[done.rowNumber + s][done.colNumber + t]=
                   done.submatrix[s][t];

/***
  Calculate spacing parameter
***/
               temp = done.submatrix[s][t];
               currentDigitCount = 1;
               while(temp = temp / 10) currentDigitCount++;
               if(currentDigitCount > highestDigitCount)
                 highestDigitCount = currentDigitCount;
             }
           }
         }
       }
/***
  Print the final matrix and exit
***/

   outFile = fopen(outFileName,"w");
   printMatrix(outFile,finishedMatrix,
               matrixSize,matrixSize,highestDigitCount);
   close(outFile);
   terminate();
}