// *********************************************************************** // Stenciler.c // author: Matthew Judd and John Karpovich // mrj2p@virginia.edu and jfk3w@Virginia.edu // University of Virginia // December 7, 1992 // // adapted from code by Ambar Sarkar // // compilation: // make serial - for serial version // make all - for MENTAT parallel version // // description: // Implements class definitions for Stenciler and related objects // // user responsibility: // Write setRowsAndCols() code - this code initializes the number of rows // and columns in the image. It also initializes the window variables to // include the whole image. // // Write getNextStencil() code - this function both returns the next stencil // to apply to the matrix, and decides whether or not to stop applying // filters. // // Write prepareDest() code - this function prepares the destination file // to receive the final image from the Stencilers. Any information // the destination file needs other than that image must be written here. // *********************************************************************** // **************************************************************************** // // Copyright (c) 1992 // University of Virginia // All Rights Reserved // // This software is the property of the University of Virginia. // This software is provided `as is' and without any express or // implied warrenties. // // Send problems & suggestions to: // Andrew Grimshaw (grimshaw@cs.virginia.edu) // // ************************************************************************** #include #include #include #include #include "Stenciler.h" // ************************************************************************ // ************************************************************************ // // USER DEFINED STENCILER FUNCTIONS // // ************************************************************************ // ************************************************************************ // VIRTUAL FUNCTIONS int Stenciler::setRowsCols() {return 0;} stencil* Stenciler::getNextStencil() {stencil* tmp = NULL; return tmp;} void Stenciler::prepareDest() {} void Stenciler::putMatrixPiece() {} void Stenciler::doStencilPiece(stencil *sten) {} void Stenciler::getMatrixPiece() {} void Stenciler::workers_alloc(int pieces) {} void Stenciler::destroy_workers(int pieces) {} float Stenciler::checkConvergence() {return 0.0;} float Stenciler::checkConvergencePiece() {return 0.0;} // ************************************************************************** // Output this section of final image to target file. // // This function should open the destination file, copy this workers piece // into that file in the correct place, and then close the output file. // Examples for both image convolution and pde's are in the example files; // both output images into files in .ppx format. // ************************************************************************** int Stenciler::putMatrix() { int i, tmp, tmp2; if (workerType == LEAF) putMatrixPiece(); else { for (i = 0; i < myPieces; i++) { tmp = workers[i].putMatrix(); tmp2 = tmp; } } #ifndef SERIAL mentat_return (0); #endif return (0); } // ************************************************************************** // Apply given stencil to workers section of image. // // This function coordinates calling the doStencilPiece functions for each // piece, exchanging boundaries as necessary and getting the next stencil. // The doStencilPiece function does the real stencil work. // ************************************************************************** int Stenciler::doStencilWork(stencil* sten) { int need_top, need_bottom, need_left, need_right, need_up_left, need_up_right, need_low_left, need_low_right; /* Booleans describing whether the each boundary region needs to be exchanged before the next stencil is run. */ int i, j; int chunkNum; int ret; int *returnInt; int *a,*b,*c,*d,*e,*f,*g,*h,*sum; if (workerType == LEAF) doStencilPiece(sten); else { nextStencil = sten; // allocate space for syncronization variables. a = new int[myPieces]; b = new int[myPieces]; c = new int[myPieces]; d = new int[myPieces]; e = new int[myPieces]; f = new int[myPieces]; g = new int[myPieces]; h = new int[myPieces]; sum = new int[myPieces]; returnInt = new int[myPieces]; need_top = test_top(); need_bottom = test_bottom(); need_left = test_left(); need_right = test_right(); need_up_left = test_up_left(); need_up_right = test_up_right(); need_low_left = test_low_left(); need_low_right = test_low_right(); chunkNum = 0; for (i=0; i < myRows; i++) for (j=0; j < myCols; j++) { if ( (i < (myRows - 1)) && need_bottom ) { a[chunkNum] = workers[chunkNum].put_boundary_bottom (workers[chunkNum + myCols]. get_boundary_top(nextStencil->num_row()/2)); if ( (j > 0) && need_low_left ) { b[chunkNum] = workers[chunkNum].put_boundary_low_left (workers[(chunkNum + myCols) - 1]. get_boundary_up_right(nextStencil->num_row()/2, nextStencil->num_col()/2)); } if ( (j < (myCols - 1)) && need_low_right ) { c[chunkNum] = workers[chunkNum].put_boundary_low_right (workers[chunkNum + myCols + 1]. get_boundary_up_left(nextStencil->num_row()/2, nextStencil->num_col()/2)); } } if ( (i > 0) && need_top ) { d[chunkNum] = workers[chunkNum].put_boundary_top (workers[chunkNum - myCols]. get_boundary_bottom( nextStencil->num_row()/2)); if ( (j > 0) && need_up_left ) e[chunkNum] = workers[chunkNum].put_boundary_up_left (workers[(chunkNum - myCols) - 1]. get_boundary_low_right(nextStencil->num_row()/2, nextStencil->num_col()/2)); if ( (j < (numColPieces - 1)) && need_up_right ) f[chunkNum] = workers[chunkNum].put_boundary_up_right (workers[(chunkNum - myCols) + 1]. get_boundary_low_left(nextStencil->num_row()/2, nextStencil->num_col()/2)); } if ( (j < (myCols - 1)) && need_right ) { g[chunkNum] = workers[chunkNum].put_boundary_right (workers[chunkNum + 1]. get_boundary_left( nextStencil->num_col()/2)); } if ( (j > 0) && need_left ) h[chunkNum] = workers[chunkNum].put_boundary_left (workers[chunkNum - 1]. get_boundary_right( nextStencil->num_col()/2)); #ifndef SERIAL force(); #endif chunkNum++; } // synch after exchanging boundaries for (i = 0; i < myPieces; i++) sum[i] = a[i] + b[i] + c[i] + d[i] + e[i] + f[i] + g[i] + h[i]; // call workers to do stencil iteration for (i=0; i < myPieces; i++) { ret = workers[i].doStencilWork(nextStencil); #ifndef SERIAL force(); #endif } delete a; delete b; delete c; delete d; delete e; delete f; delete g; delete h; delete sum; delete returnInt; } #ifndef SERIAL mentat_return(0); #endif return (0); } // ************************************************************************** // Read workers section of Matrix from given input file, using values sent // from Stenciler through init(). Called from the init() function. // // This function must get each workers pice from the input file. It should // use Stenciler member variables matrixCols, ulRow, ulCol, and numCols // to determine the offset from the beginning of the file to the start of the // first piece row, and the distance in the input file from the end of one // piece row to the beginning of the next. // ************************************************************************** int Stenciler::getMatrix() { int i, tmp; if (workerType == LEAF) getMatrixPiece(); else { for (i = 0; i < myPieces; i++) { tmp = workers[i].getMatrix(); #ifndef SERIAL force(); #endif } } #ifndef SERIAL mentat_return (0); #endif return (0); } //************************************************************************ //************************************************************************ // // PROVIDED STENCILER FUNCTIONS // //************************************************************************ //************************************************************************ int Stenciler::cleanup() { int ret_val; stencil_seq *temp, *del; temp = stencilList; ret_val = 0; while (temp != NULL) { del = temp; temp = del->next; delete del->st; delete del; ret_val++; } delete srcNm; delete destNm; destroy_workers(myPieces); return (ret_val); } //************************************************************************ // These functions can be used by the users program after setSource() has // been called to determine the size of the data matrix found in the // source file. //************************************************************************ int Stenciler::getNumRows() { #ifndef SERIAL mentat_return (numRows); #endif return (numRows); } int Stenciler::getNumCols() { #ifndef SERIAL mentat_return (numCols); #endif return (numCols); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the top // region of pieces need to be exchanged. A NULL stencil returns FALSE always // and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_top() { int rows, cols; int i; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point in rows above the center are non-zero, then // the top needs to be exchanged, else not. for (i=0; i < ((rows/2) * cols); i++) if (st[i] != 0) return(TRUE); return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // bottom boundary needs to be extracted from the piece below. // A NULL stencil returns FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_bottom() { int rows, cols; int i; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point in rows below the center are non-zero, then // the bottom needs to be exchanged, else not. for (i=(rows/2 + 1)*cols; i < rows*cols; i++) if (st[i] != 0) return(TRUE); return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // left region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_left() { int rows, cols; int i,j; int index; int leftCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point in cols to left of the center are non-zero, then // the left needs to be exchanged, else not. leftCols = cols/2; for (i=0; i < rows; i++) { index = i*cols; for(j=0;j < leftCols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // right region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_right() { int rows, cols; int i,j; int index; int startRightCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point in cols to right of the center are non-zero, then // the right needs to be exchanged, else not. startRightCols = (cols/2) + 1; for (i=0; i < rows; i++) { index = (i*cols) + startRightCols; for(j=startRightCols; j < cols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // upper left region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_up_left() { int rows, cols; int i,j; int index; int endCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point to upper left of the center are non-zero, then // the upper left needs to be exchanged, else not. endCols = cols/2; for (i=0; i < (rows/2); i++) { index = i*cols; for(j=0; j < endCols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // upper right region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_up_right() { int rows, cols; int i,j; int index; int startCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point to upper right of the center are non-zero, then // the upper right needs to be exchanged, else not. startCols = (cols/2) + 1; for (i=0; i < (rows/2); i++) { index = (i*cols) + startCols; for(j=startCols; j < cols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // lower left region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_low_left() { int rows, cols; int i,j; int index; int endCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point to lower left of the center are non-zero, then // the lower left needs to be exchanged, else not. endCols = cols/2; for (i=(rows/2) + 1; i < rows; i++) { index = i*cols; for(j=0; j < endCols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //************************************************************************ // Determines if to apply the stencil pointed to by nextStencil, the // lower right region of pieces need to be exchanged. A NULL stencil returns // FALSE always and a 1 x 1 stencil returns FALSE always. //************************************************************************ int Stenciler::test_low_right() { int rows, cols; int i,j; int index; int startCols; DATA_TYPE *st; // if nextStencil is NULL assume it is the first pass and return true if (nextStencil == NULL) return(FALSE); rows = nextStencil->num_row(); cols = nextStencil->num_col(); // if the stencil is 1 x 1, return FALSE if ((rows == 1) && (cols == 1)) return(FALSE); // get pointer to beginning of stencil matrix st = nextStencil->get_r_ptr(0); // if any stencil point to lower right of the center are non-zero, then // the lower right needs to be exchanged, else not. startCols = (cols/2) + 1; for (i=(rows/2) + 1; i < rows; i++) { index = (i*cols) + startCols; for(j=startCols; j < cols; j++) if (st[index++] != 0) return(TRUE); } return(FALSE); } //*********** // getRegion // // extracts a matrix from the workers of the given coords. Coords are the // upper left and lower right corners of the bounding rectangle for the matrix. // This function will figure out which worker regions need to be retrieved // and will assemble the results. // //************ MATRIX_TYPE* Stenciler::getRegion(int ulr, int ulc, int lrr, int lrc) { MATRIX_TYPE* outRegion; int get_ulr, get_ulc, get_lrr, get_lrc; int put_ulr, put_ulc; int i,j; rect w_coords; MATRIX_TYPE* tmpRegion; if (workerType == LEAF) { outRegion = srcArray->extract_region (ulr - ulRow + maxStencilRows, ulc - ulCol + maxStencilCols, lrr - ulRow + maxStencilRows, lrc - ulCol + maxStencilCols); } else { // allocate matrix to hold results. outRegion = new ((lrr - ulr) + 1, (lrc - ulc) + 1) MATRIX_TYPE ((lrr - ulr) + 1, (lrc - ulc) + 1); put_ulr = 0; for (i=0; i < myRows; i++) { put_ulc = 0; for(j=0; j < myCols; j++) { w_coords = workers[i*myCols+j].get_worker_coords(); // if worker has no part of region wanted, do nothing if ( (w_coords.lrr < ulr) || (w_coords.lrc < ulc) || (w_coords.ulr > lrr) || (w_coords.ulc > lrc) ) { } else // get piece from worker { // calc region of worker to get if (w_coords.ulr < ulr) get_ulr = ulr; else get_ulr = w_coords.ulr; if (w_coords.ulc < ulc) get_ulc = ulc; else get_ulc = w_coords.ulc; if (w_coords.lrr > lrr) get_lrr = lrr; else get_lrr = w_coords.lrr; if (w_coords.lrc > lrc) get_lrc = lrc; else get_lrc = w_coords.lrc; // save row size of piece. Add in to offset in destination // matrix at the end of the row. put_ulc = get_ulc - ulc; put_ulr = get_ulr - ulr; // get piece tmpRegion = workers[(i*myCols) + j]. getRegion(get_ulr, get_ulc, get_lrr, get_lrc); // overlay piece outRegion->overlay_region(put_ulr, put_ulc, tmpRegion); delete tmpRegion; } // end else } // end for j } // end for i } #ifndef SERIAL mentat_return (outRegion); delete outRegion; #endif return (outRegion); } //*********** // putRegion // // overlays the given matrix over the appropriate portion of the worker's // matrices. This function will figure out which workers are effected and will // overlay each worker's piece as necessary. // //************ int Stenciler::putRegion(int ulr, int ulc, MATRIX_TYPE* inRegion) { int get_ulr, get_ulc, get_lrr, get_lrc; int put_ulr, put_ulc, put_lrr, put_lrc; int i,j; rect w_coords; MATRIX_TYPE* tmpRegion; int lrr, lrc; int tmp, tmp2; if (workerType == LEAF) { srcArray->overlay_region(ulr - ulRow + maxStencilRows, ulc - ulCol + maxStencilCols, inRegion); } else { lrr = (ulr + inRegion->num_row()) - 1; lrc = (ulc + inRegion->num_col()) - 1; for (i=0; i < myRows; i++) { for(j=0; j < myCols; j++) { w_coords = workers[i*myCols+j].get_worker_coords(); // if worker has no part of region being overlayed, do nothing if ( (w_coords.lrr < ulr) || (w_coords.lrc < ulc) || (w_coords.ulr > lrr) || (w_coords.ulc > lrc) ) {} else // send piece to worker { if (w_coords.ulr < ulr) put_ulr = ulr; else put_ulr = w_coords.ulr; if (w_coords.ulc < ulc) put_ulc = ulc; else put_ulc = w_coords.ulc; if (w_coords.lrr > lrr) put_lrr = lrr; else put_lrr = w_coords.lrr; if (w_coords.lrc > lrc) put_lrc = lrc; else put_lrc = w_coords.lrc; // calc coords of input matrix to send to worker get_ulr = put_ulr - ulr; get_ulc = put_ulc - ulc; get_lrr = put_lrr - ulr; get_lrc = put_lrc - ulc; tmpRegion = inRegion-> extract_region(get_ulr, get_ulc, get_lrr, get_lrc); tmp = workers[i*myCols + j]. putRegion(put_ulr, put_ulc, tmpRegion); tmp2 = tmp; delete tmpRegion; } } } } #ifndef SERIAL mentat_return(0); #else delete inRegion; #endif return (0); } //************************************************************************* // Initializes private variables. //************************************************************************* void Stenciler::init() { srcNm = NULL; destNm = NULL; numPieces = 1; stencilList = NULL; currentStencil = NULL; stencilListTail = NULL; numRowPieces = 0; numColPieces = 0; numRows = numCols = 0; maxStencilRows = maxStencilCols = 0; ul_row_window = ul_col_window = 0; lr_row_window = lr_col_window = 0; currIter = 0; endIter = 0; workerType = NODE; myPieces = 1; myRows = 1; myCols = 1; myPiecesRows = 1; myPiecesCols = 1; #ifndef SERIAL mentat_return(0); #endif } //************************************************************************* // This function uses the user assigned value of numPieces and the values of // numRows and numCols to find the best values of numRowPieces and // numColPieces for the image. //************************************************************************* int Stenciler::calcRowPieces() { int bestx, besty, i, j; float goal, best, temp, ratio; // Initialize variables - goal is the desired ratio between RowPieces // and ColPieces. goal = numRows/numCols; bestx = 1; besty = numPieces; // Find initial best guess - with bestx = 1 ratio = (((float) bestx) / ((float) besty)); if (ratio < goal) temp = ratio / goal; else temp = goal / ratio; best = fabs(temp - 1.0); // For each i between 1 and pieces, determine whether i is a factor. // If so, determine if ratio i/j is closer to goal than best previously // found. If so, save i, j, and ratio as best found. for (i = 1; i <= numPieces; i++) { j = numPieces/i; if (numPieces == i*j) { ratio = ((float) i) / ((float) j); if (ratio < goal) temp = ratio / goal; else temp = goal / ratio; if (fabs (temp - 1.0) < best) { bestx = i; besty = j; best = fabs (temp - 1.0); } } } // Return best_x as best value for x_pieces of all factors of pieces. return (bestx); } //************************************************************************* // This function can be used by the main program to explicitly set the // number of rows and columns in the input matrix. //************************************************************************* int Stenciler::setRowsAndCols(int r, int c) { int ret_val; numRows = r; numCols = c; ulRow = 0; ulCol = 0; lrRow = numRows; lrCol = numCols; lr_row_window = numRows - 1; lr_col_window = numCols - 1; ret_val = numRows; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // Set window borders for part of matrix in which stencil will be applied // (Default is whole matrix) //************************************************************************* int Stenciler::setWindow (int w_ulRow, int w_ulCol, int w_lrRow, int w_lrCol) { int ret_val; ul_row_window = w_ulRow; ul_col_window = w_ulCol; lr_row_window = w_lrRow; lr_col_window = w_lrCol; ret_val = lr_col_window; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // P stenciler workers are to be created when running the stencil over the matrix //************************************************************************* int Stenciler::setPieces(int p) { int ret_val; numPieces = p; ret_val = numPieces; #ifndef SERIAL mentat_return(ret_val); #endif return(ret_val); } //************************************************************************* // numP workers are to be created in a square matrix with p rows of workers // and numP/p columns of workers. p must be a factor of numP; if p = 0, the // program will find the best fit values of p and numP/p. //************************************************************************* int Stenciler::setRowPieces(int p) { int ret_val; numRowPieces = p; ret_val = numRowPieces; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // This function sets Stenciler member variable endIter. It can be used // by getNextStencil() to determine whether or not to stop working. //************************************************************************* int Stenciler::setIterations (int p) { int ret_val; endIter = p; ret_val = endIter; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // This function sets the Stenciler member variable convVal. It can be used // by getNextStencil() to determine whether or not to stop working. //************************************************************************* int Stenciler::setGoal (float p) { int ret_val; convVal = p; ret_val = (int) convVal; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // Name of file with source image is sNm //************************************************************************* int Stenciler::setSource(string *sNm) { int ret_val; srcNm = new ((char *)sNm) string ((char *)sNm); ret_val = setRowsCols(); #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // output goes to file named dNm //************************************************************************* int Stenciler::setDest(string *dNm) { int ret_val; destNm = new ((char *)dNm) string ((char *)dNm); ret_val = destNm->size_of(); #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } //************************************************************************* // add another stencil to the list of stencils //************************************************************************* int Stenciler::addStencil(stencil *f) { int tmpRow, tmpCol; int ret_val; tmpRow = f->num_row()/2; tmpCol = f->num_col()/2; if (stencilList == NULL) { stencilList = new stencil_seq; stencilList->st = f->extract_region(0,0, f->num_row()-1, f->num_col()-1); stencilList->next = NULL; stencilListTail = stencilList; currentStencil = stencilList; } else { stencilListTail->next = new stencil_seq; stencilListTail = stencilListTail->next; stencilListTail->st = f->extract_region(0,0, f->num_row()-1, f->num_col()-1); stencilListTail->next = NULL; } if (tmpRow > maxStencilRows) maxStencilRows = tmpRow; if (tmpCol > maxStencilCols) maxStencilCols = tmpCol; ret_val = maxStencilCols; #ifndef SERIAL mentat_return(ret_val); #endif return (ret_val); } rect Stenciler::get_worker_coords() { rect coords; coords.ulr = ulRow; coords.ulc = ulCol; coords.lrr = lrRow; coords.lrc = lrCol; #ifndef SERIAL mentat_return (coords); #endif return (coords); } //************************************************************************** // get_worker_coords // // returns the corner coordinates for the portion of the main matrix which // is owned by the given worker number. // //************************************************************************** rect Stenciler::get_worker_coords(int workerNum) { rect coords; int chunkRows, chunkCols, extraRowsNeeded, extraColsNeeded; int i; chunkRows = numRows/myRows; extraRowsNeeded = numRows % myRows; chunkCols = numCols/myCols; extraColsNeeded = numCols % myCols; // calc upper left and lower right rows coords.ulr = 0; if (extraRowsNeeded > 0) { coords.lrr = chunkRows; extraRowsNeeded--; } else coords.lrr = chunkRows - 1; for (i=0; i < (workerNum/myCols); i++) { coords.ulr = coords.lrr + 1; if (extraRowsNeeded > 0) { coords.lrr += chunkRows + 1; extraRowsNeeded--; } else coords.lrr += chunkRows; } // calc upper left and lower right cols coords.ulc = 0; if (extraColsNeeded > 0) { coords.lrc = chunkCols; extraColsNeeded--; } else coords.lrc = chunkCols - 1; for (i=0; i < (workerNum % myCols); i++) { coords.ulc = coords.lrc + 1; if (extraColsNeeded > 0) { coords.lrc += chunkCols + 1; extraColsNeeded--; } else coords.lrc += chunkCols; } coords.ulr += ulRow; coords.ulc += ulCol; coords.lrr += ulRow; coords.lrc += ulCol; return(coords); } int Stenciler::bestFactor (int sz) { int ret_val, i; ret_val = 1; for (i = 1; i <= MAX_PIECES; i++) if ((sz % i) == 0) ret_val = i; return (ret_val); } void Stenciler::calcMyDecomp() { int tempRow, tempCol; if (numPieces <= MAX_PIECES) { myPieces = numPieces; myRows = numRowPieces; myCols = numColPieces; myPiecesRows = 1; myPiecesCols = 1; } else { if ((numColPieces <= MAX_PIECES) && (numColPieces > 1)) { myPieces = numColPieces; myRows = 1; myCols = myPieces; myPiecesRows = numRowPieces; myPiecesCols = 1; } else if ((numRowPieces <= MAX_PIECES) && (numRowPieces > 1)) { myPieces = numRowPieces; myRows = myPieces; myCols = 1; myPiecesRows = 1; myPiecesCols = numColPieces; } else { tempCol = bestFactor (numColPieces); if (tempCol != 1) { myPieces = tempCol; myRows = 1; myCols = myPieces; myPiecesRows = numRowPieces; myPiecesCols = numColPieces/myCols; } else { tempRow = bestFactor (numRowPieces); if (tempRow != 1) { myPieces = tempRow; myRows = myPieces; myCols = 1; myPiecesRows = numRowPieces/myRows; myPiecesCols = numColPieces; } else { fprintf (stderr, "ERROR - cannot Factor numPieces!!\n"); fflush (stderr); exit (-1); } } } } } int Stenciler::cleanup_workers() { int i, tmp, tmp2; tmp2 = 1; if (workerType == NODE) { for (i = 0; i < myPieces; i++) { tmp = workers[i].cleanup_workers(); tmp2 += tmp; } destroy_workers(myPieces); } #ifndef SERIAL mentat_return (tmp2); #endif return (tmp2); } //************************************************************************* // Create required number of stenciler workers. Initialize stencil // workers and pass them the needed parameters. After each pass, call // getNextStencil to retrieve next stencil to be run (can be the same stencil // or a different one). A stencil value of NULL means we're done. // For each stencil: // exchange boundaries between stencil workers with neighboring pieces. // tell each worker to do stencil // when all stencils are handled, kill the workers. //************************************************************************* int Stenciler::doStencil() { int i, j, tmp; int chunkNum; /* number of current worker being worked on. */ int *returnInt; /* Array to catch return values from stencil_ worker functions. */ rect worker_coords; /* coordinates of the current worker's piece. */ rect window_coords; int need_top, need_bottom, need_left, need_right, need_up_left, need_up_right, need_low_left, need_low_right; /* Booleans describing whether the each boundary region needs to be exchanged before the next stencil is run. */ int *a,*b,*c,*d,*e,*f,*g,*h,*sum; //********** // Prepare destination file to receive output //********** prepareDest(); // calc number of row and column pieces. if (numRowPieces == 0) numRowPieces = calcRowPieces(); numColPieces = numPieces / numRowPieces; if ((numColPieces * numRowPieces) != numPieces) { printf (" numPieces = %d numRowPieces = %d\n", numPieces, numRowPieces); fflush (stdout); fprintf (stderr, "ERROR - Desired value of numRowPieces"); fprintf (stderr, " is not a factor of numPieces!!\n"); fflush (stderr); exit (-1); } calcMyDecomp(); #ifdef STEN_DEBUG fprintf(stderr, "calculated decomposition\n\n"); #endif // allocate workers. workers_alloc(myPieces); #ifdef STEN_DEBUG fprintf(stderr, "workers allocated\n\n"); #endif returnInt = new int[myPieces]; chunkNum = 0; for(i = 0; i < myPieces; i++ ) { worker_coords = get_worker_coords(i); if (ul_row_window > worker_coords.ulr) window_coords.ulr = ul_row_window; else window_coords.ulr = worker_coords.ulr; if (lr_row_window < worker_coords.lrr) window_coords.lrr = lr_row_window; else window_coords.lrr = worker_coords.lrr; if (ul_col_window > worker_coords.ulc) window_coords.ulc = ul_col_window; else window_coords.ulc = worker_coords.ulc; if (lr_col_window < worker_coords.lrc) window_coords.lrc = lr_col_window; else window_coords.lrc = worker_coords.lrc; returnInt[i] = workers[chunkNum].S_init(srcNm, destNm, worker_coords, window_coords, maxStencilRows, numRows, numCols, myPiecesRows, myPiecesCols); tmp = workers[chunkNum].getMatrix(); #ifndef SERIAL force(); #endif chunkNum++; } #ifdef STEN_DEBUG fprintf(stderr, "workers initialized\n\n"); #endif //****************************************************************** // Apply each stencil to each piece until the StencilList is empty. The // function getNextStencil() checks for completion, and returns NULL // when no more stencils need be applied. //****************************************************************** nextStencil = getNextStencil(); // allocate space for syncronization variables. a = new int[myPieces]; b = new int[myPieces]; c = new int[myPieces]; d = new int[myPieces]; e = new int[myPieces]; f = new int[myPieces]; g = new int[myPieces]; h = new int[myPieces]; sum = new int[myPieces]; while (nextStencil != NULL) { //*************************************************************** // pass boundaries between regions //*************************************************************** // determine which boundary regions need to be passed around for this // stencil. need_top = test_top(); need_bottom = test_bottom(); need_left = test_left(); need_right = test_right(); need_up_left = test_up_left(); need_up_right = test_up_right(); need_low_left = test_low_left(); need_low_right = test_low_right(); chunkNum = 0; for (i=0; i < myRows; i++) for (j=0; j < myCols; j++) { // receive from lower neighbors if ( (i < (myRows - 1)) && need_bottom ) { a[chunkNum] = workers[chunkNum].put_boundary_bottom (workers[chunkNum + myCols]. get_boundary_top(nextStencil->num_row()/2)); // get from lower left and right neighbors if not leftmost or // rightmost column respectively if ( (j > 0) && need_low_left ) { b[chunkNum] = workers[chunkNum].put_boundary_low_left (workers[(chunkNum + myCols) - 1]. get_boundary_up_right(nextStencil->num_row()/2, nextStencil->num_col()/2)); } if ( (j < (myCols - 1)) && need_low_right ) { c[chunkNum] = workers[chunkNum].put_boundary_low_right (workers[chunkNum + myCols + 1]. get_boundary_up_left(nextStencil->num_row()/2, nextStencil->num_col()/2)); } } // receive from upper neighbors if ( (i > 0) && need_top ) { d[chunkNum] = workers[chunkNum].put_boundary_top (workers[chunkNum - myCols]. get_boundary_bottom( nextStencil->num_row()/2)); // get from upper left and right neighbors if not leftmost or // rightmost column respectively if ( (j > 0) && need_up_left ) e[chunkNum] = workers[chunkNum].put_boundary_up_left (workers[(chunkNum - myCols) - 1]. get_boundary_low_right(nextStencil->num_row()/2, nextStencil->num_col()/2)); if ( (j < (myCols - 1)) && need_up_right ) f[chunkNum] = workers[chunkNum].put_boundary_up_right (workers[(chunkNum - myCols) + 1]. get_boundary_low_left(nextStencil->num_row()/2, nextStencil->num_col()/2)); } // receive from right neighbors if ( (j < (myCols - 1)) && need_right ) { g[chunkNum] = workers[chunkNum].put_boundary_right (workers[chunkNum + 1]. get_boundary_left( nextStencil->num_col()/2)); } // receive from left neighbors if ( (j > 0) && need_left ) { h[chunkNum] = workers[chunkNum].put_boundary_left (workers[chunkNum - 1]. get_boundary_right( nextStencil->num_col()/2)); } #ifndef SERIAL force(); #endif chunkNum++; } // synchronize workers - all must finish exchanging boundaries // before doStencil can begin. for (i = 0; i < myPieces; i++) sum[i] = a[i] + b[i] + c[i] + d[i] + e[i] + f[i] + g[i] + h[i]; // call workers to do stencil iteration for (i=0; i < myPieces; i++) { returnInt[i] = workers[i].doStencilWork(nextStencil); #ifndef SERIAL force(); #endif } // synchronize workers - make sure all finish doStencil before proceeding. int tempInt = 0; for (i=0; i < myPieces; i++) { tempInt += returnInt[i]; } #ifdef STEN_DEBUG fprintf(stderr, "finished iteration\n\n"); #endif // call getNextStencil to get next stencil to work on -- NULL means we // are done. nextStencil = getNextStencil(); } // end while // ****************************************************************** // call workers to write out final matrix // ****************************************************************** for (i=0; i worker_coords.ulr) window_coords.ulr = w_ulRow; else window_coords.ulr = worker_coords.ulr; if (w_lrRow < worker_coords.lrr) window_coords.lrr = w_lrRow; else window_coords.lrr = worker_coords.lrr; if (w_ulCol > worker_coords.ulc) window_coords.ulc = w_ulCol; else window_coords.ulc = worker_coords.ulc; if (w_lrCol < worker_coords.lrc) window_coords.lrc = w_lrCol; else window_coords.lrc = worker_coords.lrc; workers[chunkNum].S_init(srcNm, destNm, worker_coords, window_coords, maxStencilRows, matrixRows, matrixCols, myPiecesRows, myPiecesCols); #ifndef SERIAL force(); #endif chunkNum++; } } #ifdef STEN_DEBUG fprintf(stderr, "OUT S_init\n\n"); #endif #ifndef SERIAL mentat_return(0); #endif return(0); } // ************************************************************************** // get the proper boundaries of the piece I possess // ************************************************************************** MATRIX_TYPE *Stenciler::get_boundary_top(int stRows) { MATRIX_TYPE *outArray; outArray = getRegion (ulRow, ulCol, stRows - 1+ulRow, numCols - 1+ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_bottom(int stRows) { MATRIX_TYPE *outArray; outArray = getRegion (numRows - stRows + ulRow, ulCol, numRows - 1 + ulRow, numCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_left(int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (ulRow, ulCol, numRows - 1 + ulRow, stCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_right(int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (ulRow, numCols - stCols + ulCol, numRows - 1 + ulRow, numCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_up_left(int stRows, int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (ulRow, ulCol, stRows - 1 + ulRow, stCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_up_right(int stRows, int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (ulRow, numCols - stCols + ulCol, stRows - 1 + ulRow, numCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_low_left(int stRows, int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (numRows - stRows + ulRow, ulCol, numRows - 1 + ulRow, stCols - 1 + ulCol); return(outArray); } MATRIX_TYPE *Stenciler::get_boundary_low_right(int stRows, int stCols) { MATRIX_TYPE *outArray; outArray = getRegion (numRows - stRows + ulRow, numCols - stCols + ulCol, numRows - 1 + ulRow, numCols - 1 + ulCol); return(outArray); } // ************************************************************************** // incorporate boundaries sent from other objects // ************************************************************************** int Stenciler::put_boundary_top(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow - inArray->num_row(), ulCol, inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_bottom(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow + numRows, ulCol, inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_left(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow, ulCol - inArray->num_col(), inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_right(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow, ulCol + numCols, inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_up_left(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow - inArray->num_row(), ulCol - inArray->num_col(), inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_up_right(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow - inArray->num_row(), ulCol + numCols, inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_low_left(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (ulRow + numRows, ulCol - inArray->num_col(), inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); } int Stenciler::put_boundary_low_right(MATRIX_TYPE *inArray) { int tmp, tmp2; tmp = putRegion (numRows + ulRow, numCols + ulCol, inArray); tmp2 = tmp; #ifdef SERIAL delete inArray; #endif return (tmp); }