# HG changeset patch # User Me # Date 1287101362 25200 # Node ID 47802166a7aef7a8a758ec6ed9d5b8896971f82f # Parent b8b71da62a09eed071e1043c8076ea5ef22df886 Either working correctly, or close.. diff -r b8b71da62a09 -r 47802166a7ae src/Application/Matrix_Mult.c --- a/src/Application/Matrix_Mult.c Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/Matrix_Mult.c Thu Oct 14 17:09:22 2010 -0700 @@ -61,7 +61,7 @@ numRows = matrixStruc->numRows; numCols = matrixStruc->numCols; - matrixStart = matrixStruc->matrix; + matrixStart = matrixStruc->array; file = fopen( matrixFileName, "r" ); if( file == NULL ) { printf( "\nCouldn't open file!!\n"); exit(1);} @@ -131,7 +131,7 @@ retMatrix = malloc( sizeof( Matrix ) ); retMatrix->numRows = numRows; retMatrix->numCols = numCols; - retMatrix->matrix = malloc( numRows * numCols * sizeof(float32) ); + retMatrix->array = malloc( numRows * numCols * sizeof(float32) ); return retMatrix; } @@ -142,22 +142,24 @@ } void freeMatrix( Matrix * matrix ) - { free( matrix->matrix ); + { free( matrix->array ); free( matrix ); } void printMatrix( Matrix *matrix ) - { int r, c, numRows, numCols; + { int r, c, numRows, numCols, rowsToPrint, colsToPrint, rowIncr, colIncr; float32 *matrixArray; - numRows = matrix->numRows; - numCols = matrix->numCols; - matrixArray = matrix->matrix; + numRows = rowsToPrint = matrix->numRows; + numCols = colsToPrint = matrix->numCols; + matrixArray = matrix->array; - for( r = 0; r < numRows; r++ ) - { for( c = 0; c < numCols; c++ ) - { printf( "%f | ", *(matrixArray + r*numCols + c) ); + rowIncr = numRows/20; if(rowIncr == 0) rowIncr = 1;//20 to 39 rows printed + colIncr = numCols/20; if(colIncr == 0) colIncr = 1;//20 to 39 cols printed + for( r = 0; r < numRows; r += rowIncr ) + { for( c = 0; c < numCols; c += colIncr ) + { printf( "%3.1f | ", matrixArray[ r * numCols + c ] ); } printf("\n"); } diff -r b8b71da62a09 -r 47802166a7ae src/Application/Matrix_Mult.h --- a/src/Application/Matrix_Mult.h Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/Matrix_Mult.h Thu Oct 14 17:09:22 2010 -0700 @@ -19,7 +19,7 @@ struct { int32 numRows; int32 numCols; - float32 *matrix; //2D, but dynamically sized, so use addr arith + float32 *array; //2D, but dynamically sized, so use addr arith } Matrix; diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/Divide_Pr.c --- a/src/Application/SSR_Matrix_Mult/Divide_Pr.c Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/SSR_Matrix_Mult/Divide_Pr.c Thu Oct 14 17:09:22 2010 -0700 @@ -8,78 +8,485 @@ #include "SSR_Matrix_Mult.h" +#include -/*Divider creates one processor for every row-col pair. + //The time to compute this many result values should equal the time to + // perform this division on a matrix of size gives that many result calcs + //IE, size this so that sequential time to calc equals divide time + // find the value by experimenting -- but divide time and calc time scale + // same way, so this value should remain valid across hardware +#define NUM_CELLS_IN_SEQUENTIAL_CUTOFF 1000 + + +int +measureMatrixMultPrimitive(); + + +SlicingStrucCarrier * +calcIdealSizeAndSliceDimensions( Matrix *leftMatrix, Matrix *rightMatrix ); + +SlicingStruc * +sliceUpDimension( float32 idealSizeOfPiece, int startVal, int endVal ); + +SubMatrix ** +createSubMatrices( SlicingStruc *rowSlices, SlicingStruc *colSlices, + Matrix *origMatrix ); + + +void +pairUpSubMatricesAndMakeProcessors( SubMatrix **leftSubMatrices, + SubMatrix **rightSubMatrices, + int32 numRowIdxs, int32 numColIdxs, + int32 numVecIdxs, + VirtProcr *resultPr, + VirtProcr *animatingPr ); + +void +makeSubMatricesAndProcrs( Matrix *leftMatrix, Matrix *rightMatrix, + SlicingStrucCarrier *slicingStrucCarrier, + VirtProcr *resultPr, VirtProcr *animatingPr ); + + + +/*Divider creates one processor for every sub-matrix * It hands them: * the name of the result processor that they should send their results to, - * the left and right matrices, and the row and col they should multiply - * the length of the vector - * It first creates the result processor, then all the vector processors, + * the left and right matrices, and the rows and cols they should multiply + * It first creates the result processor, then all the sub-matrixPair + * processors, * then does a receive of a message from the result processor that gives * the divider ownership of the result matrix. * Finally, the divider returns the result matrix out of the SSR system. + * + * Divider chooses the size of sub-matrices via an algorithm that tries to + * keep the minimum work above a threshold. The threshold is machine- + * dependent, so ask SSR for min work-unit time to get a + * given overhead + * + * Divide min work-unit cycles by measured-cycles for one matrix-cell + * product -- gives the number of products need to have in min size + * matrix. + * + * So then, take cubed root of this to get the size of a side of min sub- + * matrix. That is the size of the ideal square sub-matrix -- so tile + * up the two input matrices into ones as close as possible to that size, + * and create the pairs of sub-matrices. + * + *======================== STRATEGIC OVERVIEW ======================= + * + *This division is a bit tricky, because have to create things in advance + * that it's not at first obvious need to be created.. + * + *First slice up each dimension -- three of them.. this is because will have + * to create the sub-matrix's data-structures before pairing the sub-matrices + * with each other -- so, have three dimensions to slice up before can + * create the sub-matrix data-strucs -- also, have to be certain that the + * cols of the left input have the exact same slicing as the rows of the + * left matrix, so just to be sure, do the slicing calc once, then use it + * for both. + * + *So, goes like this: + *1) calculate the start & end values of each dimension in each matrix. + *2) use those values to create sub-matrix structures + *3) combine sub-matrices into pairs, as the tasks to perform. + * + *Have to calculate separately from creating the sub-matrices because of the + * nature of the nesting -- would either end up creating the same sub-matrix + * multiple times, or else would have to put in detection of whether had + * made a particular one already if tried to combine steps 1 and 2. + * + *Step 3 has to be separate because of the nesting, as well -- same reason, + * would either create same sub-matrix multiple times, or else have to + * add detection of whether was already created. + * + *Another way to look at it: there's one level of loop to divide dimensions, + * two levels of nesting to create sub-matrices, and three levels to pair + * up the sub-matrices. */ -void divideIntoVectors( void *_dividerParams, VirtProcr *animatingPr ) + +void divideWorkIntoSubMatrixPairProcrs( void *_dividerParams, + VirtProcr *animatingPr ) { VirtProcr *resultPr; DividerParams *dividerParams; ResultsParams *resultsParams; - VectorParams *vectParams; Matrix *leftMatrix, *rightMatrix, *resultMatrix; void *msg; + SlicingStrucCarrier *slicingStrucCarrier; + float32 *resultArray; //points to array to be put inside result + // matrix + + PRINT_DEBUG("start divide\n") -// printf("start divide\n"); fflush(stdin); - + + //=========== Setup -- make local copies of ptd-to-things, malloc, aso + dividerParams = (DividerParams *)_dividerParams; leftMatrix = dividerParams->leftMatrix; rightMatrix = dividerParams->rightMatrix; - resultsParams = SSR__malloc_size_to( sizeof(ResultsParams), - animatingPr ); - resultsParams->dividerPr = animatingPr; - resultsParams->numCols = rightMatrix->numCols; - resultsParams->numRows = leftMatrix->numRows; - - resultPr = SSR__create_procr_with(&gatherResults, resultsParams, - animatingPr); - int row, col; - for( row = 0; row < leftMatrix->numRows; row++ ) - { for( col = 0; col < rightMatrix->numCols; col++ ) - { - vectParams = SSR__malloc_size_to(sizeof(VectorParams), - animatingPr); - vectParams->resultPr = resultPr; - vectParams->myCol = col; - vectParams->myRow = row; - vectParams->vectLength = leftMatrix->numCols; - vectParams->leftMatrix = leftMatrix; - vectParams->rightMatrix = rightMatrix; - - SSR__create_procr_with( &calcVector, vectParams, animatingPr ); - //vectParams ownership transferred to the newly created processor - } + //============== Do either sequential mult or do division ============== + + //Check if input matrices too small -- if yes, just do sequential + if( leftMatrix->numRows * leftMatrix->numCols * rightMatrix->numCols + < NUM_CELLS_IN_SEQUENTIAL_CUTOFF ) //curoff is determined by overhead + // of this divider -- relatively machine-independent + { int32 vectLength, numResRows, numResCols; + + //====== Do sequential multiply on a single core + + vectLength = leftMatrix->numCols; + numResRows = leftMatrix->numRows; + numResCols = rightMatrix->numCols; + + resultArray = malloc( numResRows * numResCols * sizeof(float32) ); + + multiplyMatrixArrays( vectLength, numResRows, numResCols, + leftMatrix->array, rightMatrix->array, + resultArray ); + } + else + { + //====== Do parallel multiply across cores + + //Calc the ideal size of sub-matrix and slice up the dimensions of + // the two matrices. + //The ideal size is the one takes the number of cycles to calculate + // such that calc time is equal or greater than min work-unit size + slicingStrucCarrier = + calcIdealSizeAndSliceDimensions( leftMatrix, rightMatrix ); + + //Make the results processor, now that know how many to wait for + resultsParams = SSR__malloc_size_to(sizeof(ResultsParams),animatingPr); + resultsParams->dividerPr = animatingPr; + resultsParams->numSubMatrixPairs = + slicingStrucCarrier->leftRowSlices->numVals * + slicingStrucCarrier->rightColSlices->numVals * + slicingStrucCarrier->vecSlices->numVals; + resultsParams->numCols = rightMatrix->numCols; + resultsParams->numRows = leftMatrix->numRows; + + resultPr = + SSR__create_procr_with( &gatherResults, resultsParams, animatingPr); + + //Make the sub-matrices, and pair them up, and make processor to + // calc product of each pair. + makeSubMatricesAndProcrs( leftMatrix, rightMatrix, + slicingStrucCarrier, + resultPr, animatingPr); + + //Get result from result procr + msg = SSR__receive_from_to( resultPr, animatingPr ); + resultArray = (float32 *) msg; } - //Get result from result procr - msg = SSR__receive_from_to( resultPr, animatingPr ); + + //=============== Work done -- send results back ================= + //prepare results to persist outside of SSR when return from entry pt //The results of the all the work have to be linked-to from the data // struc given to the seed procr -- this divide func is animated by // that seed procr, so have to link results to the _dividerParams. - resultMatrix = SSR__malloc_size_to( sizeof(Matrix), - animatingPr ); + resultMatrix = SSR__malloc_size_to(sizeof(Matrix),animatingPr); + resultMatrix->array = resultArray; resultMatrix->numCols = rightMatrix->numCols; resultMatrix->numRows = leftMatrix->numRows; + + dividerParams->resultMatrix = resultMatrix; - resultMatrix->matrix = (float32 *) msg; SSR__transfer_ownership_to_outside( msg ); //so not freed SSR__transfer_ownership_to_outside( resultMatrix ); - //printf("end divide\n"); fflush(stdin); + PRINT_DEBUG("end divide\n") SSR__dissipate_procr( animatingPr ); //all procrs dissipate self at end //when all of the processors have dissipated, the "create seed and do // work" call in the entry point function returns } + + +SlicingStrucCarrier * +calcIdealSizeAndSliceDimensions( Matrix *leftMatrix, Matrix *rightMatrix ) +{ + float32 idealSizeOfSide, idealSizeOfSide1, idealSizeOfSide2; + SlicingStruc *leftRowSlices, *vecSlices, *rightColSlices; + SlicingStrucCarrier *slicingStrucCarrier = + malloc(sizeof(SlicingStrucCarrier)); + + int minWorkUnitCycles, primitiveCycles, idealNumWorkUnits; + float64 numPrimitiveOpsInMinWorkUnit; + + + //======= Calc ideal size of min-sized sub-matrix ======== + + //ask SSR for the number of cycles of the minimum work unit, at given + // percent overhead then add a guess at overhead from this divider + minWorkUnitCycles = SSR__giveMinWorkUnitCycles( .05 ); + + //ask SSR for number of cycles of the "primitive" op of matrix mult + primitiveCycles = measureMatrixMultPrimitive(); + + numPrimitiveOpsInMinWorkUnit = + (float64)minWorkUnitCycles / (float64)primitiveCycles; + + //take cubed root -- that's number of these in a "side" of sub-matrix + // then multiply by 5 because the primitive is 5x5 + idealSizeOfSide1 = 5 * cbrt( numPrimitiveOpsInMinWorkUnit ); + + idealNumWorkUnits = SSR__giveIdealNumWorkUnits(); + + idealSizeOfSide2 = leftMatrix->numRows / rint(cbrt( idealNumWorkUnits )); + + if( idealSizeOfSide1 > idealSizeOfSide2 ) + idealSizeOfSide = idealSizeOfSide1; + else + idealSizeOfSide = idealSizeOfSide2; + + //The multiply inner loop blocks the array to fit into L1 cache +// if( idealSizeOfSide < ROWS_IN_BLOCK ) idealSizeOfSide = ROWS_IN_BLOCK; + + //============ Slice up dimensions, now that know target size =========== + + //Tell the slicer the target size of a side (floating pt), the start + // value to start slicing at, and the end value to stop slicing at + //It returns an array of start value of each chunk, plus number of them + int32 startLeftRow, endLeftRow, startVec,endVec,startRightCol,endRightCol; + startLeftRow = 0; + endLeftRow = leftMatrix->numRows -1; + startVec = 0; + endVec = leftMatrix->numCols -1; + startRightCol = 0; + endRightCol = rightMatrix->numCols -1; + + leftRowSlices = + sliceUpDimension( idealSizeOfSide, startLeftRow, endLeftRow ); + + vecSlices = + sliceUpDimension( idealSizeOfSide, startVec, endVec ); + + rightColSlices = + sliceUpDimension( idealSizeOfSide, startRightCol, endRightCol ); + + slicingStrucCarrier->leftRowSlices = leftRowSlices; + slicingStrucCarrier->vecSlices = vecSlices; + slicingStrucCarrier->rightColSlices = rightColSlices; + + return slicingStrucCarrier; +} + + +void +makeSubMatricesAndProcrs( Matrix *leftMatrix, Matrix *rightMatrix, + SlicingStrucCarrier *slicingStrucCarrier, + VirtProcr *resultPr, VirtProcr *animatingPr ) + { + SlicingStruc *leftRowSlices, *vecSlices, *rightColSlices; + + leftRowSlices = slicingStrucCarrier->leftRowSlices; + vecSlices = slicingStrucCarrier->vecSlices; + rightColSlices = slicingStrucCarrier->rightColSlices; + + //================ Make sub-matrices, given the slicing ================ + SubMatrix **leftSubMatrices, **rightSubMatrices; + leftSubMatrices = + createSubMatrices( leftRowSlices, vecSlices, + leftMatrix ); + rightSubMatrices = + createSubMatrices( vecSlices, rightColSlices, + rightMatrix ); + + //============== pair the sub-matrices and make processors ============== + int32 numRowIdxs, numColIdxs, numVecIdxs; + + numRowIdxs = leftRowSlices->numVals; + numColIdxs = rightColSlices->numVals; + numVecIdxs = vecSlices->numVals; + pairUpSubMatricesAndMakeProcessors( leftSubMatrices, + rightSubMatrices, + numRowIdxs, numColIdxs, + numVecIdxs, + resultPr, + animatingPr ); + } + + + + +void +pairUpSubMatricesAndMakeProcessors( SubMatrix **leftSubMatrices, + SubMatrix **rightSubMatrices, + int32 numRowIdxs, int32 numColIdxs, + int32 numVecIdxs, + VirtProcr *resultPr, + VirtProcr *animatingPr ) + { + int32 resRowIdx, resColIdx, vecIdx; + int32 numLeftColIdxs, numRightColIdxs; + int32 leftRowIdxOffset; + SMPairParams *subMatrixPairParams; + + numLeftColIdxs = numColIdxs; + numRightColIdxs = numVecIdxs; + + for( resRowIdx = 0; resRowIdx < numRowIdxs; resRowIdx++ ) + { + leftRowIdxOffset = resRowIdx * numLeftColIdxs; + + for( resColIdx = 0; resColIdx < numColIdxs; resColIdx++ ) + { + + for( vecIdx = 0; vecIdx < numVecIdxs; vecIdx++ ) + { + //Make the processor for the pair of sub-matrices + subMatrixPairParams = SSR__malloc_size_to(sizeof(SMPairParams), + animatingPr); + subMatrixPairParams->leftSubMatrix = + leftSubMatrices[ leftRowIdxOffset + vecIdx ]; + + subMatrixPairParams->rightSubMatrix = + rightSubMatrices[ vecIdx * numRightColIdxs + resColIdx ]; + + subMatrixPairParams->resultPr = resultPr; + + SSR__create_procr_with( &calcSubMatrixProduct, + subMatrixPairParams, + animatingPr ); + } + } + } + + } + + + +/*Walk through the two slice-strucs, making sub-matrix strucs as go + */ +SubMatrix ** +createSubMatrices( SlicingStruc *rowSlices, SlicingStruc *colSlices, + Matrix *origMatrix ) + { + int32 numRowIdxs, numColIdxs, rowIdx, colIdx; + int32 startRow, endRow, startCol, endCol; + int32 *rowStartVals, *colStartVals; + int32 rowOffset; + SubMatrix **subMatrices, *newSubMatrix; + + numRowIdxs = rowSlices->numVals; + numColIdxs = colSlices->numVals; + + rowStartVals = rowSlices->startVals; + colStartVals = colSlices->startVals; + + subMatrices = malloc( numRowIdxs * numColIdxs * sizeof(SubMatrix *) ); + + for( rowIdx = 0; rowIdx < numRowIdxs; rowIdx++ ) + { + rowOffset = rowIdx * numColIdxs; + + startRow = rowStartVals[rowIdx]; + endRow = rowStartVals[rowIdx + 1] -1; //"fake" start above last is + // at last valid idx + 1 & is + // 1 greater than end value + for( colIdx = 0; colIdx < numColIdxs; colIdx++ ) + { + startCol = colStartVals[colIdx]; + endCol = colStartVals[colIdx + 1] -1; + + newSubMatrix = malloc( sizeof(SubMatrix) ); + newSubMatrix->numRows = endRow - startRow +1; + newSubMatrix->numCols = endCol - startCol +1; + newSubMatrix->origMatrix = origMatrix; + newSubMatrix->origStartRow = startRow; + newSubMatrix->origStartCol = startCol; + newSubMatrix->alreadyCopied = FALSE; + + subMatrices[ rowOffset + colIdx ] = newSubMatrix; + } + } + return subMatrices; + } + + + + +SlicingStruc * +sliceUpDimension( float32 idealSizeOfSide, int startVal, int endVal ) + { float32 residualAcc = 0; + int numSlices, i, *startVals, sizeOfSlice, endCondition; + SlicingStruc *slicingStruc = malloc( sizeof(SlicingStruc) ); + + //calc size of matrix need to hold start vals -- + numSlices = (int32)( (float32)(endVal -startVal +1) / idealSizeOfSide); + + startVals = malloc( (numSlices + 1) * sizeof(int32) ); + + //Calc the upper limit of start value -- when get above this, end loop + // by saving highest value of the matrix dimension to access, plus 1 + // as the start point of the imaginary slice following the last one + //Plus 1 because go up to value but not include when process last slice + //The stopping condition is half-a-size less than highest value because + // don't want any pieces smaller than half the ideal size -- just tack + // little ones onto end of last one + endCondition = endVal - (int) (idealSizeOfSide/2); //end *value*, not size + for( i = 0; startVal <= endVal; i++ ) + { + startVals[i] = startVal; + residualAcc += idealSizeOfSide; + sizeOfSlice = (int)residualAcc; + residualAcc -= (float32)sizeOfSlice; + startVal += sizeOfSlice; //ex @size = 2 get 0, 2, 4, 6, 8.. + + if( startVal > endCondition ) + { startVal = endVal + 1; + startVals[ i + 1 ] = startVal; + } + } + + slicingStruc->startVals = startVals; + slicingStruc->numVals = i; //loop incr'd, so == last valid start idx+1 + // which means is num sub-matrices in dim + // also == idx of the fake start just above + return slicingStruc; + } + + +int inline +measureMatrixMultPrimitive() + { + int r, c, v, numCycles; + float32 *res, *left, *right; + + //setup inputs + left = malloc( 5 * 5 * sizeof( float32 ) ); + right = malloc( 5 * 5 * sizeof( float32 ) ); + res = malloc( 5 * 5 * sizeof( float32 ) ); + + for( r = 0; r < 5; r++ ) + { + for( c = 0; c < 5; c++ ) + { + left[ r * 5 + c ] = r; + right[ r * 5 + c ] = c; + } + } + + //do primitive + SSR__start_primitive(); //for now, just takes time stamp + for( r = 0; r < 5; r++ ) + { + for( c = 0; c < 5; c++ ) + { + for( v = 0; v < 5; v++ ) + { + res[ r * 5 + c ] = left[ r * 5 + v ] * right[ v * 5 + c ]; + } + } + } + numCycles = + SSR__end_primitive_and_give_cycles(); + + return numCycles; + } + diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/EntryPoint.c --- a/src/Application/SSR_Matrix_Mult/EntryPoint.c Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/SSR_Matrix_Mult/EntryPoint.c Thu Oct 14 17:09:22 2010 -0700 @@ -39,7 +39,8 @@ //create divider processor, start doing the work, and wait till done //This function is the "border crossing" between normal code and SSR - SSR__create_seed_procr_and_do_work( ÷IntoVectors, dividerParams ); + SSR__create_seed_procr_and_do_work( ÷WorkIntoSubMatrixPairProcrs, + dividerParams ); //get result matrix and return it resMatrix = dividerParams->resultMatrix; diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/Result_Pr.c --- a/src/Application/SSR_Matrix_Mult/Result_Pr.c Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/SSR_Matrix_Mult/Result_Pr.c Thu Oct 14 17:09:22 2010 -0700 @@ -8,6 +8,15 @@ #include "SSR_Matrix_Mult.h" +void inline +accumulateResult( float32 *resultArray, float32 *subMatrixResultArray, + int32 startRow, + int32 numRows, + int32 startCol, + int32 numCols, + int32 numOrigCols ); + + /*The Result Processor gets a message from each of the vector processors, * puts the result from the message in its location in the result- * matrix, and increments the count of results. @@ -18,34 +27,68 @@ void gatherResults( void *_params, VirtProcr *animatingPr ) { VirtProcr *dividerPr; ResultsParams *params; - int numRows, numCols, numCells, count=0; - float32 *resultMatrix; + int row, col, numRows, numCols, numSubMatrixPairs, count=0; + float32 *resultArray; void *msg; - VectorParams *aResult; + SMPairParams *resParams; -// printf("start resultPr\n"); fflush(stdin); - + PRINT_DEBUG("start resultPr\n") + params = (ResultsParams *)_params; dividerPr = params->dividerPr; - numCols = params->numCols; - numRows = params->numRows; - numCells = numRows * numCols; + numSubMatrixPairs = params->numSubMatrixPairs; + numRows = params->numRows; + numCols = params->numCols; - resultMatrix = SSR__malloc_size_to( numCells*sizeof( float32 ), animatingPr); - - while( count < numCells ) + resultArray = SSR__malloc_size_to( numRows * numCols * sizeof(float32), + animatingPr ); + + //zero out the results array -- will be accumulating, so must start 0 + for( row = 0; row < numRows; row++ ) + { + for( col = 0; col < numCols; col++ ) + { + resultArray[ row * numCols + col ] = 0; + } + } + + while( count < numSubMatrixPairs ) { msg = SSR__receive_type_to( RESULTS_MSG, animatingPr ); - aResult = (VectorParams *)msg; - *(resultMatrix + aResult->myRow * numCols + aResult->myCol) = - aResult->result; + resParams = (SMPairParams *)msg; + accumulateResult( resultArray, resParams->resultArray, + resParams->leftSubMatrix->origStartRow, + resParams->leftSubMatrix->numRows, + resParams->rightSubMatrix->origStartCol, + resParams->rightSubMatrix->numCols, + resParams->rightSubMatrix->origMatrix->numCols ); count++; } //if were real lang, would have auto-nested transfer -- but HelloWorld // language, so have to transfer ownership of each allocated block of // locations separately - SSR__transfer_ownership_of_from_to( resultMatrix, animatingPr, dividerPr ); - SSR__send_from_to( resultMatrix, animatingPr, dividerPr ); + SSR__transfer_ownership_of_from_to( resultArray, animatingPr, dividerPr ); + SSR__send_from_to( resultArray, animatingPr, dividerPr ); SSR__dissipate_procr( animatingPr ); //frees any data owned by procr } + +void inline +accumulateResult( float32 *resultArray, float32 *subMatrixResultArray, + int32 startRow, + int32 numRows, + int32 startCol, + int32 numCols, + int32 numOrigCols ) + { int32 row, col; + + for( row = 0; row < numRows; row++ ) + { + for( col = 0; col < numCols; col++ ) + { + resultArray[ (row + startRow) * numOrigCols + col + startCol ] += + subMatrixResultArray[ row * numCols + col ]; + } + } + + } diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/SSR_Matrix_Mult.h --- a/src/Application/SSR_Matrix_Mult/SSR_Matrix_Mult.h Tue Oct 05 10:00:11 2010 -0700 +++ b/src/Application/SSR_Matrix_Mult/SSR_Matrix_Mult.h Thu Oct 14 17:09:22 2010 -0700 @@ -11,6 +11,15 @@ #include "../../SSR_lib/SSR.h" #include "../Matrix_Mult.h" + +//=============================== Defines ============================== +#define ROWS_IN_BLOCK 32 +#define COLS_IN_BLOCK 32 +#define VEC_IN_BLOCK 32 + + +#define PRINT_DEBUG(msg) //printf(msg); fflush(stdin); + //============================== Structures ============================== typedef struct { @@ -25,19 +34,45 @@ VirtProcr *dividerPr; int numRows; int numCols; + int numSubMatrixPairs; } ResultsParams; +typedef +struct + { int32 numRows; + int32 numCols; + Matrix *origMatrix; + int32 origStartRow; + int32 origStartCol; + int32 alreadyCopied; + float32 *array; //2D, but dynamically sized, so use addr arith + } +SubMatrix; + typedef struct { VirtProcr *resultPr; - int myCol; - int myRow; - int vectLength; - Matrix *leftMatrix; - Matrix *rightMatrix; - float32 result; + SubMatrix *leftSubMatrix; + SubMatrix *rightSubMatrix; + float32 *resultArray; } -VectorParams; +SMPairParams; + +typedef +struct + { int32 numVals; + int32 *startVals; + } +SlicingStruc; + +typedef +struct + { + SlicingStruc *leftRowSlices; + SlicingStruc *vecSlices; + SlicingStruc *rightColSlices; + } +SlicingStrucCarrier; enum MMMsgType { @@ -45,8 +80,8 @@ }; //============================= Processor Functions ========================= -void divideIntoVectors( void *data, VirtProcr *animatingPr ); -void calcVector( void *data, VirtProcr *animatingPr ); +void divideWorkIntoSubMatrixPairProcrs( void *data, VirtProcr *animatingPr ); +void calcSubMatrixProduct( void *data, VirtProcr *animatingPr ); void gatherResults( void *data, VirtProcr *animatingPr ); diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/Vector_Pr.c --- a/src/Application/SSR_Matrix_Mult/Vector_Pr.c Tue Oct 05 10:00:11 2010 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,47 +0,0 @@ -/* - * Copyright 2009 OpenSourceStewardshipFoundation.org - * Licensed under GNU General Public License version 2 - * - * Author: SeanHalle@yahoo.com - * - */ - -#include "SSR_Matrix_Mult.h" - -/*A Vector processor is created with an environment that holds two matrices, - * the row and col that it owns, and the name of a result gathering - * processor. - *It calculates its vector product then sends the result to the result - * processor, which puts it into the result matrix and returns that matrix - * when all is done. - */ - void -calcVector( void *data, VirtProcr *animatingPr ) - { - VectorParams *params; - VirtProcr *resultPr; - int myRow, myCol, vectLength, pos; - float32 *leftMatrixArray, *rightMatrixArray, result = 0.0; - Matrix *leftMatrix, *rightMatrix; - -// printf("start vector\n"); fflush(stdin); - - params = (VectorParams *)data; - resultPr = params->resultPr; - myCol = params->myCol; - myRow = params->myRow; - vectLength = params->vectLength; - leftMatrix = params->leftMatrix; - rightMatrix = params->rightMatrix; - leftMatrixArray = leftMatrix->matrix; - rightMatrixArray = rightMatrix->matrix; - - for( pos = 0; pos < vectLength; pos++ ) - { - result += *(leftMatrixArray + myRow * vectLength + pos) * - *(rightMatrixArray + pos * vectLength + myCol); - } - params->result = result; - SSR__send_of_type_to( animatingPr, params, RESULTS_MSG, resultPr ); - SSR__dissipate_procr( animatingPr ); - } diff -r b8b71da62a09 -r 47802166a7ae src/Application/SSR_Matrix_Mult/subMatrix_Pr.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/SSR_Matrix_Mult/subMatrix_Pr.c Thu Oct 14 17:09:22 2010 -0700 @@ -0,0 +1,245 @@ +/* + * Copyright 2009 OpenSourceStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: SeanHalle@yahoo.com + * + */ + +#include "SSR_Matrix_Mult.h" + + +void inline +copyFromOrig( SubMatrix *subMatrix ); + +void inline +copyTransposeFromOrig( SubMatrix *subMatrix ); + +void inline +multiplySubBlocksTransposed( float32 *leftArray, float32 *rightArray, + float32 *resArray, + int startRow, int endRow, + int startCol, int endCol, + int startVec, int endVec, + int resStride, int inpStride ); + +void inline +multiplyMatrixArrays( int32 vecLength, int32 numResRows, int32 numResCols, + float32 *leftArray, float32 *rightArray, + float32 *resArray ); + + +/*A processor is created with an environment that holds two matrices, + * the row and col that it owns, and the name of a result gathering + * processor. + *It calculates the product of two sub-portions of the input matrices + * by using Intel's mkl library for single-core. + * + *This demonstrates using optimized single-threaded code inside scheduled + * work-units. + * + *When done, it sends the result to the result processor + */ +void +calcSubMatrixProduct( void *data, VirtProcr *animatingPr ) + { + SMPairParams *params; + VirtProcr *resultPr; + float32 *leftArray, *rightArray, *resArray; + SubMatrix *leftSubMatrix, *rightSubMatrix; + + PRINT_DEBUG("start sub-matrix mult\n") + + params = (SMPairParams *)data; + resultPr = params->resultPr; + leftSubMatrix = params->leftSubMatrix; + rightSubMatrix = params->rightSubMatrix; + + //make sure the input sub-matrices have been copied out of orig + copyFromOrig( leftSubMatrix ); + copyTransposeFromOrig( rightSubMatrix ); + + leftArray = leftSubMatrix->array; + rightArray = rightSubMatrix->array; + + resArray = malloc( leftSubMatrix->numRows * rightSubMatrix->numCols * + sizeof( float32 ) ); + + + int32 numResRows, numResCols, vectLength; + + vectLength = leftSubMatrix->numCols; + numResRows = leftSubMatrix->numRows; + numResCols = rightSubMatrix->numCols; + + multiplyMatrixArrays( vectLength, numResRows, numResCols, + leftArray, rightArray, + resArray ); + + //send result to result processor + params->resultArray = resArray; + SSR__send_of_type_to( animatingPr, params, RESULTS_MSG, resultPr ); + SSR__dissipate_procr( animatingPr ); + } + + +/*Divides into 32x32 sub-matrices, 3 of which fit into 32KB L1 cache + * Would be nice to embed this within another level that divided into + * 8x8 tiles of those, where one 8x8 tile fits within 2MB L2 cache + * + *Eventually want these divisions to be automatic, using DKU pattern + * embedded into SSR, and with VMS controlling the divisions according to + * the cache sizes, which it knows about. + *And, want VMS to work with language to split among main-mems, so a socket + * only cranks on data in its local segment of main mem + * + */ +void inline +multiplyMatrixArrays( int32 vecLength, int32 numResRows, int32 numResCols, + float32 *leftArray, float32 *rightArray, + float32 *resArray ) + { + int resStride, inpStride; + int startRow, startCol, endRow, endCol, startVec, endVec; + + resStride = numResCols; + inpStride = vecLength; + + for( startRow = 0; startRow < numResRows; ) + { + endRow = startRow + ROWS_IN_BLOCK; + if( endRow > numResRows ) endRow = numResRows; + + for( startCol = 0; startCol < numResCols; ) + { + endCol = startCol + COLS_IN_BLOCK; + if( endCol > numResCols ) endCol = numResCols; + + for( startVec = 0; startVec < vecLength; ) + { + endVec = startVec + VEC_IN_BLOCK; + if( endVec > vecLength ) endVec = vecLength; + + //By having the "vector" of sub-blocks in a sub-block slice + // be marched down in inner loop, are re-using the result + // matrix, which stays in L1 cache -- can only re-use one of + // the three, so this is the most important -- avoids writing + // dirty blocks until those result-locations fully done + //Row and Col is position in result matrix -- so row and vec + // for left array, then vec and col for right array + multiplySubBlocksTransposed( leftArray, rightArray, + resArray, + startRow, endRow, + startCol, endCol, + startVec, endVec, + resStride, inpStride ); + startVec = endVec; + } + startCol = endCol; + } + startRow = endRow; + } + } + + +void inline +multiplySubBlocksTransposed( float32 *leftArray, float32 *rightArray, + float32 *resArray, + int startRow, int endRow, + int startCol, int endCol, + int startVec, int endVec, + int resStride, int inpStride ) + { + int row, col, vec; + int leftOffset, rightOffset; + float32 result; + + for( row = startRow; row < endRow; row++ ) + { + for( col = startCol; col < endCol; col++ ) + { + leftOffset = row * inpStride;//left & right inp strides always same + rightOffset = col * inpStride;// because right is transposed + result = 0; + for( vec = startVec; vec < endVec; vec++ ) + { + result += + leftArray[ leftOffset + vec] * rightArray[ rightOffset + vec]; + } + + resArray[ row * resStride + col ] += result; + } + } + } + +void inline +copyTransposeFromOrig( SubMatrix *subMatrix ) + { int numCols, numRows, origStartRow, origStartCol, origStride, stride; + Matrix *origMatrix; + float32 *origArray, *subArray; + + if( subMatrix->alreadyCopied ) return; + + subMatrix->alreadyCopied = TRUE; + + origMatrix = subMatrix->origMatrix; + origArray = origMatrix->array; + numCols = subMatrix->numCols; + numRows = subMatrix->numRows; + stride = numRows; + origStartRow = subMatrix->origStartRow; + origStartCol = subMatrix->origStartCol; + origStride = origMatrix->numCols; + + subArray = malloc( numRows * numCols * sizeof(float32) ); + subMatrix->array = subArray; + + //copy values from orig matrix to local + int row, col, origOffset; + for( row = 0; row < numRows; row++ ) + { + origOffset = (row + origStartRow) * origStride + origStartCol; + for( col = 0; col < numCols; col++ ) + { + //transpose means swap row & col -- traverse orig matrix normally + // but put into reversed place in local array -- means the + // stride is the num rows now, so col * numRows + row + subArray[ col * stride + row ] = origArray[ origOffset + col ]; + } + } + } + +void inline +copyFromOrig( SubMatrix *subMatrix ) + { int numCols, numRows, origStartRow, origStartCol, stride, origStride; + Matrix *origMatrix; + float32 *origArray, *subArray; + + if( subMatrix->alreadyCopied ) return; + + subMatrix->alreadyCopied = TRUE; + + origMatrix = subMatrix->origMatrix; + origArray = origMatrix->array; + numCols = subMatrix->numCols; + numRows = subMatrix->numRows; + origStartRow = subMatrix->origStartRow; + origStartCol = subMatrix->origStartCol; + stride = numCols; + origStride = origMatrix->numCols; + + subArray = malloc( numRows * numCols * sizeof(float32) ); + subMatrix->array = subArray; + + //copy values from orig matrix to local + int row, col, offset, origOffset; + for( row = 0; row < numRows; row++ ) + { + offset = row * stride; + origOffset = (row + origStartRow) * origStride + origStartCol; + for( col = 0; col < numCols; col++ ) + { + subArray[ offset + col ] = origArray[ origOffset + col ]; + } + } + }