# HG changeset patch # User Me # Date 1289217591 28800 # Node ID 5311bd32c3cbbc29674fbf2b696dd56e648ef072 # Parent 06c80cd3c3039bcbe762c8c238cef488658b4d69 Bug-free blocked Matrix Mult in VCilk -- uses Nov 8 version of VMS diff -r 06c80cd3c303 -r 5311bd32c3cb src/Application/VCilk__Matrix_Mult/Divide_Pr.c --- a/src/Application/VCilk__Matrix_Mult/Divide_Pr.c Sun Nov 07 06:55:26 2010 -0800 +++ b/src/Application/VCilk__Matrix_Mult/Divide_Pr.c Mon Nov 08 03:59:51 2010 -0800 @@ -10,6 +10,7 @@ #include "VCilk__Matrix_Mult.h" #include #include +#include //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 @@ -126,25 +127,29 @@ float32 *resultArray; //points to array to be put inside result // matrix - PRINT_DEBUG("start divide\n") + DEBUG( dbgAppFlow, "start divide\n") int32 divideProbe = VMS__create_single_interval_probe( "divideProbe", animPr ); VMS__record_sched_choice_into_probe( divideProbe, animPr ); VMS__record_interval_start_in_probe( divideProbe ); - + //=========== Setup -- make local copies of ptd-to-things, malloc, aso - int32 numResRows, numResCols; + int32 numResRows, numResCols, vectLength; dividerParams = (DividerParams *)_dividerParams; leftMatrix = dividerParams->leftMatrix; rightMatrix = dividerParams->rightMatrix; + vectLength = leftMatrix->numCols; numResRows = leftMatrix->numRows; numResCols = rightMatrix->numCols; resultArray = dividerParams->resultMatrix->array; + + //zero the result array + memset( resultArray, 0, numResRows * numResCols * sizeof(float32) ); //============== Do either sequential mult or do division ============== @@ -157,11 +162,21 @@ { int32 vectLength; //====== Do sequential multiply on a single core - PRINT_DEBUG("doing sequential") - vectLength = leftMatrix->numCols; + DEBUG( dbgAppFlow, "doing sequential") - multiplyMatrixArrays( vectLength, numResRows, numResCols, - leftMatrix->array, rightMatrix->array, + //transpose the right matrix + float32 * + transRightArray = VCilk__malloc( rightMatrix->numRows * + rightMatrix->numCols * + sizeof(float32), animPr ); + + //copy values from orig matrix to local + copyTranspose( rightMatrix->numRows, rightMatrix->numCols, + 0, 0, rightMatrix->numRows, + transRightArray, rightMatrix->array ); + + multiplyMatrixArraysTransposed( vectLength, numResRows, numResCols, + leftMatrix->array, transRightArray, resultArray ); } else @@ -176,17 +191,6 @@ calcIdealSizeAndSliceDimensions( leftMatrix, rightMatrix, animPr); - //Make the results processor, now that know how many to wait for -/* - resultsParams = VCilk__malloc( sizeof(ResultsParams) ); - resultsParams->dividerPr = animatingPr; - resultsParams->numSubMatrixPairs = - slicingStrucCarrier->leftRowSlices->numVals * - slicingStrucCarrier->rightColSlices->numVals * - slicingStrucCarrier->vecSlices->numVals; - resultsParams->numCols = rightMatrix->numCols; - resultsParams->numRows = leftMatrix->numRows; -*/ //Make the sub-matrices, and pair them up, then spawn processors to // calc product of each pair. @@ -204,10 +208,10 @@ // system, by entry-point Fn, and passed in through dividerParams. //So, nothing to do to send results back -- they're seen by side-effect - PRINT_DEBUG("end divide\n") + DEBUG( dbgAppFlow, "end divide\n") VMS__record_interval_end_in_probe( divideProbe ); - VMS__print_stats_of_all_probes; + VMS__print_stats_of_all_probes(); VCilk__dissipate_procr( animPr ); //all procrs dissipate self at end //when all of the processors have dissipated, the "create seed and do @@ -247,7 +251,7 @@ idealNumWorkUnits = VCilk__giveIdealNumWorkUnits(); idealSizeOfSide2 = leftMatrix->numRows / rint(cbrt( idealNumWorkUnits )); - idealSizeOfSide2 *= 0.6; //finer granularity to help load balance + idealSizeOfSide2 *= 0.8; //finer granularity to help load balance if( idealSizeOfSide1 > idealSizeOfSide2 ) idealSizeOfSide = idealSizeOfSide1; @@ -287,7 +291,7 @@ } -void +void inline makeSubMatricesAndSpawnAndSync( Matrix *leftMatrix, Matrix *rightMatrix, SlicingStrucCarrier *slicingStrucCarrier, float32 *resultArray, VirtProcr *animPr ) @@ -308,6 +312,10 @@ createSubMatrices( vecSlices, rightColSlices, rightMatrix, animPr ); + freeSlicingStruc( leftRowSlices, animPr ); + freeSlicingStruc( vecSlices, animPr ); + freeSlicingStruc( rightColSlices, animPr ); + //============== pair the sub-matrices and make processors ============== int32 numRowIdxs, numColIdxs, numVecIdxs; @@ -321,11 +329,6 @@ //It syncs inside, so know all work is done now: free the sub-matrices freeSubMatrices( leftRowSlices, vecSlices, leftSubMatrices, animPr ); freeSubMatrices( vecSlices, rightColSlices, rightSubMatrices, animPr ); - - - freeSlicingStruc( leftRowSlices, animPr ); - freeSlicingStruc( vecSlices, animPr ); - freeSlicingStruc( rightColSlices, animPr ); } @@ -336,7 +339,7 @@ * core * */ -void +void inline pairUpSubMatricesAndSpawnAndSync( SubMatrix **leftSubMatrices, SubMatrix **rightSubMatrices, int32 numRowIdxs, int32 numColIdxs, diff -r 06c80cd3c303 -r 5311bd32c3cb src/Application/VCilk__Matrix_Mult/VCilk__Matrix_Mult.h --- a/src/Application/VCilk__Matrix_Mult/VCilk__Matrix_Mult.h Sun Nov 07 06:55:26 2010 -0800 +++ b/src/Application/VCilk__Matrix_Mult/VCilk__Matrix_Mult.h Mon Nov 08 03:59:51 2010 -0800 @@ -10,6 +10,7 @@ #include "../../VCilk_lib/VCilk.h" #include "../Matrix_Mult.h" +#include "../../VCilk_lib/VMS/VMS.h" //=============================== Defines ============================== @@ -17,8 +18,8 @@ #define COLS_IN_BLOCK 32 #define VEC_IN_BLOCK 32 - -//#define PRINT_DEBUG(msg) //printf(msg); fflush(stdin); +#define copyMatrixSingleton 1 +#define copyTransposeSingleton 2 //============================== Structures ============================== typedef struct @@ -56,7 +57,7 @@ { VirtProcr *resultPr; SubMatrix *leftSubMatrix; SubMatrix *rightSubMatrix; - float32 *resultArray; + float32 *partialResultArray; } SMPairParams; diff -r 06c80cd3c303 -r 5311bd32c3cb src/Application/VCilk__Matrix_Mult/Vector_Pr.c --- a/src/Application/VCilk__Matrix_Mult/Vector_Pr.c Sun Nov 07 06:55:26 2010 -0800 +++ b/src/Application/VCilk__Matrix_Mult/Vector_Pr.c Mon Nov 08 03:59:51 2010 -0800 @@ -33,10 +33,12 @@ vecParams = (VecParams *)_vecParams; + #ifdef TURN_ON_DEBUG_PROBES int32 subMatrixVectorProbe = VMS__create_single_interval_probe( "subMtxVect", animPr ); VMS__record_sched_choice_into_probe( subMatrixVectorProbe, animPr ); VMS__record_interval_start_in_probe( subMatrixVectorProbe ); + #endif numVecIdxs = vecParams->numVecIdxs; @@ -55,7 +57,7 @@ for( vecIdx = 0; vecIdx < numVecIdxs; vecIdx++ ) { //Make the processor for the pair of sub-matrices - subMatrixPairParams = VCilk__malloc(sizeof(SMPairParams),animPr); + subMatrixPairParams = VCilk__malloc( sizeof(SMPairParams), animPr ); subMatrixPairParams->leftSubMatrix = leftSubMatrices[ leftRowIdxOffset + vecIdx ]; @@ -75,7 +77,7 @@ { subMatrixPairParams = vecOfSubMatrixParams[ vecIdx ]; - accumulateResult( resultArray, subMatrixPairParams->resultArray, + accumulateResult( resultArray, subMatrixPairParams->partialResultArray, subMatrixPairParams->leftSubMatrix->origStartRow, subMatrixPairParams->leftSubMatrix->numRows, subMatrixPairParams->rightSubMatrix->origStartCol, @@ -87,14 +89,16 @@ // core and re-use that array, and prevents writes from causing // thrashing of the cache -- as long as array big enough, the copy // overhead is miniscule vs the size-of-side reuse of each byte - VCilk__free( subMatrixPairParams->resultArray, animPr ); + VCilk__free( subMatrixPairParams->partialResultArray, animPr ); VCilk__free( subMatrixPairParams, animPr ); } VCilk__free( vecOfSubMatrixParams, animPr ); VCilk__free( vecParams, animPr ); + #ifdef TURN_ON_DEBUG_PROBES VMS__record_interval_end_in_probe( subMatrixVectorProbe ); - + #endif + VCilk__dissipate_procr( animPr ); } diff -r 06c80cd3c303 -r 5311bd32c3cb src/Application/VCilk__Matrix_Mult/subMatrix_Pr.c --- a/src/Application/VCilk__Matrix_Mult/subMatrix_Pr.c Sun Nov 07 06:55:26 2010 -0800 +++ b/src/Application/VCilk__Matrix_Mult/subMatrix_Pr.c Mon Nov 08 03:59:51 2010 -0800 @@ -6,6 +6,8 @@ * */ +#include + #include "VCilk__Matrix_Mult.h" @@ -24,7 +26,7 @@ int resStride, int inpStride ); void inline -multiplyMatrixArrays( int32 vecLength, int32 numResRows, int32 numResCols, +multiplyMatrixArraysTransposed( int32 vecLength, int32 numResRows, int32 numResCols, float32 *leftArray, float32 *rightArray, float32 *resArray ); @@ -48,11 +50,14 @@ float32 *leftArray, *rightArray, *resArray; SubMatrix *leftSubMatrix, *rightSubMatrix; - PRINT_DEBUG("start sub-matrix mult\n") - int32 subMatrixProbe = VMS__create_single_interval_probe( "subMtx", - animatingPr); + + DEBUG( dbgAppFlow, "start sub-matrix mult\n") + #ifdef TURN_ON_DEBUG_PROBES + int32 subMatrixProbe = + VMS__create_single_interval_probe( "subMtx", animatingPr); VMS__record_sched_choice_into_probe( subMatrixProbe, animatingPr ); VMS__record_interval_start_in_probe( subMatrixProbe ); + #endif params = (SMPairParams *)data; // resultPr = params->resultPr; @@ -90,14 +95,16 @@ numResRows = leftSubMatrix->numRows; numResCols = rightSubMatrix->numCols; - multiplyMatrixArrays( vectLength, numResRows, numResCols, + multiplyMatrixArraysTransposed( vectLength, numResRows, numResCols, leftArray, rightArray, resArray ); //send result by side-effect - params->resultArray = resArray; + params->partialResultArray = resArray; + #ifdef TURN_ON_DEBUG_PROBES VMS__record_interval_end_in_probe( subMatrixProbe ); + #endif VCilk__dissipate_procr( animatingPr ); } @@ -120,9 +127,10 @@ * of the two input matrices. */ void inline -multiplyMatrixArrays( int32 vecLength, int32 numResRows, int32 numResCols, - float32 *leftArray, float32 *rightArray, - float32 *resArray ) +multiplyMatrixArraysTransposed( int32 vecLength, int32 numResRows, + int32 numResCols, + float32 *leftArray, float32 *rightArray, + float32 *resArray ) { int resStride, inpStride; int resStartRow, resStartCol, resEndRow, resEndCol, startVec, endVec; @@ -133,19 +141,17 @@ for( resStartRow = 0; resStartRow < numResRows; ) { resEndRow = resStartRow + ROWS_IN_BLOCK -1; //start at zero, so -1 - if( resEndRow > numResRows ) resEndRow = numResRows; + if( resEndRow > numResRows ) resEndRow = numResRows -1; for( resStartCol = 0; resStartCol < numResCols; ) { resEndCol = resStartCol + COLS_IN_BLOCK -1; - if( resEndCol > numResCols ) resEndCol = numResCols; - resStartCol = resEndCol +1; - + if( resEndCol > numResCols ) resEndCol = numResCols -1; for( startVec = 0; startVec < vecLength; ) { endVec = startVec + VEC_IN_BLOCK -1; - if( endVec > vecLength ) endVec = vecLength; + if( endVec > vecLength ) endVec = vecLength -1; //By having the "vector" of sub-blocks in a sub-block slice // be marched down in inner loop, are re-using the result @@ -183,12 +189,12 @@ int leftOffset, rightOffset; float32 result; - //The result row is used only for the left matrix, res col for the right + //The result row is used for the left matrix, res col for the right for( resCol = resStartCol; resCol <= resEndCol; resCol++ ) - { + { for( resRow = resStartRow; resRow <= resEndRow; resRow++ ) - { - leftOffset = resRow * inpStride;//left & right inp strides always same + { + leftOffset = resRow * inpStride;//left & right inp strides same rightOffset = resCol * inpStride;// because right is transposed result = 0; for( vec = startVec; vec <= endVec; vec++ ) @@ -196,40 +202,21 @@ result += leftArray[ leftOffset + vec] * rightArray[ rightOffset + vec]; } - + resArray[ resRow * resStride + resCol ] += result; } } } -/*Note: don't do the copy when create, because create on a different core -- - * do the copy on the core that will do the calcs, then try to keep work on - * that core that reuses the array data + +/*Reuse this in divider when do the sequential multiply case */ void inline -copyTransposeFromOrig( SubMatrix *subMatrix, VirtProcr *animPr ) - { int numCols, numRows, origStartRow, origStartCol, origStride, stride; - Matrix *origMatrix; - float32 *origArray, *subArray; +copyTranspose( int32 numRows, int32 numCols, + int32 origStartRow, int32 origStartCol, int32 origStride, + float32 *subArray, float32 *origArray ) + { int32 stride = numRows; - 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; - - //This is free in Divide pr after all calcs are done - subArray = VCilk__malloc( numRows * numCols * sizeof(float32), animPr ); - subMatrix->array = subArray; - - //copy values from orig matrix to local int row, col, origOffset; for( row = 0; row < numRows; row++ ) { @@ -238,21 +225,60 @@ { //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 + // stride is the numRows now, so col * numRows + row subArray[ col * stride + row ] = origArray[ origOffset + col ]; - } + } } } void inline +copyTransposeFromOrig( SubMatrix *subMatrix, VirtProcr *animPr ) + { int numCols, numRows, origStartRow, origStartCol, origStride, stride; + Matrix *origMatrix; + float32 *origArray, *subArray; + + if( subMatrix->alreadyCopied ) return; + VCilk__start_singleton(copyMatrixSingleton,&&EndOfTranspSingleton,animPr); + + origMatrix = subMatrix->origMatrix; + origArray = origMatrix->array; + numCols = subMatrix->numCols; + numRows = subMatrix->numRows; + origStartRow = subMatrix->origStartRow; + origStartCol = subMatrix->origStartCol; + origStride = origMatrix->numCols; + + subArray = VCilk__malloc( numRows * numCols *sizeof(float32),animPr); + subMatrix->array = subArray; + + //copy values from orig matrix to local + copyTranspose( numRows, numCols, + origStartRow, origStartCol, origStride, + subArray, origArray ); + + subMatrix->alreadyCopied = TRUE; //must be last thing before label + EndOfTranspSingleton: + return; + } + + +void inline copyFromOrig( SubMatrix *subMatrix, VirtProcr *animPr ) { int numCols, numRows, origStartRow, origStartCol, stride, origStride; Matrix *origMatrix; float32 *origArray, *subArray; + + //This lets only a single VP execute the code between start and + // end -- using start and end so that work runs outside the master. + //Inside, if a second VP ever executes the start, it will be returned + // from the end-point. + //Note, for non-GCC, can add a second SSR call at the end, and inside + // that one, look at the stack at the return addr & save that in an + // array indexed by singletonID if( subMatrix->alreadyCopied ) return; + VCilk__start_singleton( copyMatrixSingleton, &&EndOfCopySingleton,animPr); - subMatrix->alreadyCopied = TRUE; origMatrix = subMatrix->origMatrix; origArray = origMatrix->array; @@ -260,14 +286,14 @@ numRows = subMatrix->numRows; origStartRow = subMatrix->origStartRow; origStartCol = subMatrix->origStartCol; - stride = numCols; origStride = origMatrix->numCols; - //This is freed in Divide pr after all calcs are done subArray = VCilk__malloc( numRows * numCols *sizeof(float32),animPr); subMatrix->array = subArray; //copy values from orig matrix to local + stride = numCols; + int row, col, offset, origOffset; for( row = 0; row < numRows; row++ ) { @@ -278,4 +304,8 @@ subArray[ offset + col ] = origArray[ origOffset + col ]; } } + + subMatrix->alreadyCopied = TRUE; //must be last thing before label + EndOfCopySingleton: + return; }