# HG changeset patch # User Me # Date 1284748108 25200 # Node ID 3b0e43240104dc642b9ee0a9aa4deda19873b520 Initial add -- works on 9x9 but dies on larger diff -r 000000000000 -r 3b0e43240104 src/Application/Matrix_Mult.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/Matrix_Mult.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,165 @@ +/* + * Copyright 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: seanhalle@yahoo.com + * + * Created on November 15, 2009, 2:35 AM + */ + +#include +#include + +#include "Matrix_Mult.h" +#include "ParamHelper/Param.h" + + + + void +initialize_Input_Matrices_Via( Matrix **leftMatrix, Matrix **rightMatrix, + ParamBag *paramBag ) + { char *leftMatrixFileName, *rightMatrixFileName; + int leftMatrixRows, leftMatrixCols, rightMatrixRows, rightMatrixCols; + + ParamStruc *param; + param = getParamFromBag( "leftMatrixRows", paramBag ); + leftMatrixRows = param->intValue; + param = getParamFromBag( "leftMatrixCols", paramBag ); + leftMatrixCols = param->intValue; + *leftMatrix = makeMatrix_WithResMat( leftMatrixRows, leftMatrixCols ); + + param = getParamFromBag( "leftMatrixFileName", paramBag ); + leftMatrixFileName = param->strValue; //no need to copy + read_Matrix_From_File( *leftMatrix, leftMatrixFileName ); + + param = getParamFromBag( "rightMatrixRows", paramBag ); + rightMatrixRows = param->intValue; + param = getParamFromBag( "rightMatrixCols", paramBag ); + rightMatrixCols = param->intValue; + *rightMatrix = makeMatrix_WithResMat( rightMatrixRows, rightMatrixCols ); + + param = getParamFromBag( "rightMatrixFileName", paramBag ); + rightMatrixFileName = param->strValue; + read_Matrix_From_File( *rightMatrix, rightMatrixFileName ); + } + + +void parseLineIntoRow( char *line, float32* row ); + + + void +read_Matrix_From_File( Matrix *matrixStruc, char *matrixFileName ) + { int row, maxRead, numRows, numCols; + float32 *matrixStart; + size_t lineSz = 0; + FILE *file; + char *line = NULL; + + lineSz = 50000; //max length of line in a matrix data file + line = (char *) malloc( lineSz ); + if( line == NULL ) printf( "no mem for matrix line" ); + + numRows = matrixStruc->numRows; + numCols = matrixStruc->numCols; + matrixStart = matrixStruc->matrix; + + file = fopen( matrixFileName, "r" ); + if( file == NULL ) { printf( "\nCouldn't open file!!\n"); exit(1);} + fseek( file, 0, SEEK_SET ); + for( row = 0; row < numRows; row++ ) + { + if( feof( file ) ) printf( "file ran out too soon" ); + maxRead = getline( &line, &lineSz, file ); + if( maxRead == -1 ) printf( "prob reading mat line"); + + if( *line == '\n') continue; //blank line + if( *line == '/' ) continue; //comment line + + parseLineIntoRow( line, matrixStart + row * numCols ); + } + free( line ); + } + +/*This function relies on each line having the proper number of cols. It + * doesn't check, nor enforce, so if the file is improperly formatted it + * can write over unrelated memory + */ + void +parseLineIntoRow( char *line, float32* row ) + { + char *valueStr, *searchPos; + + //read the float values + searchPos = valueStr = line; //start + + for( ; *searchPos != 0; searchPos++) //bit dangerous, should use buff len + { + if( *searchPos == '\n' ) //last col.. relying on well-formatted file + { *searchPos = 0; + *row = atof( valueStr ); + break; //end FOR loop + } + if( *searchPos == ',' ) + { *searchPos = 0; //mark end of string + *row = (float32) atof( valueStr ); + row += 1; //address arith + //skip any spaces before digits.. use searchPos + 1 to skip the 0 + for( ; *(searchPos + 1)== ' ' && *(searchPos + 1) !=0; searchPos++); + valueStr = searchPos + 1; + } + } + } + + //========================================================================== + +/*In the "_Flat" version of constructor, do only malloc of the top data struc + * and set values in that top-level. Don't malloc any sub-structures. + */ + Matrix * +makeMatrix_Flat( int32 numRows, int32 numCols ) + { Matrix * retMatrix; + retMatrix = malloc( sizeof( Matrix ) ); + retMatrix->numRows = numRows; + retMatrix->numCols = numCols; + + return retMatrix; + } + + Matrix * +makeMatrix_WithResMat( int32 numRows, int32 numCols ) + { Matrix * retMatrix; + retMatrix = malloc( sizeof( Matrix ) ); + retMatrix->numRows = numRows; + retMatrix->numCols = numCols; + retMatrix->matrix = malloc( numRows * numCols * sizeof(float32) ); + + return retMatrix; + } + + void +freeMatrix_Flat( Matrix * matrix ) + { //( matrix ); + } + void +freeMatrix( Matrix * matrix ) + { free( matrix->matrix ); + free( matrix ); + } + +void +printMatrix( Matrix *matrix ) + { int r, c, numRows, numCols; + float32 *matrixArray; + + numRows = matrix->numRows; + numCols = matrix->numCols; + matrixArray = matrix->matrix; + + for( r = 0; r < numRows; r++ ) + { for( c = 0; c < numCols; c++ ) + { printf( "%f | ", *(matrixArray + r*numCols + c) ); + } + printf("\n"); + } + } + diff -r 000000000000 -r 3b0e43240104 src/Application/Matrix_Mult.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/Matrix_Mult.h Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,77 @@ +/* + * Copyright Oct 24, 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + */ + +#ifndef MATRIX_MULT_H_ +#define MATRIX_MULT_H_ + +#include +#include +#include + +#include "../VPThread__lib/VMS/VMS_primitive_data_types.h" +#include "ParamHelper/Param.h" + +//============================== Structures ============================== + +typedef +struct + { int32 numRows; + int32 numCols; + float32 *matrix; //2D, but dynamically sized, so use addr arith + } +Matrix; + +/* This is the "appSpecificPiece" that is carried inside a DKUPiece. + * In the DKUPiece data struc it is declared to be of type "void *". This + * allows the application to define any data structure it wants and put it + * into a DKUPiece. + * When the app specific info is used, it is in app code, so it is cast to + * the correct type to tell the compiler how to access fields. + * This keeps all app-specific things out of the DKU directory, as per the + * DKU standard. */ +typedef +struct + { + // pointers to shared data.. the result matrix must be created when the + // left and right matrices are put into the root ancestor DKUPiece. + Matrix * leftMatrix; + Matrix * rightMatrix; + Matrix * resultMatrix; + + // define the starting and ending boundaries for this piece of the + // result matrix. These are derivable from the left and right + // matrices, but included them for readability of code. + int prodStartRow, prodEndRow; + int prodStartCol, prodEndCol; + // Start and end of the portion of the left matrix that contributes to + // this piece of the product + int leftStartRow, leftEndRow; + int leftStartCol, leftEndCol; + // Start and end of the portion of the right matrix that contributes to + // this piece of the product + int rightStartRow, rightEndRow; + int rightStartCol, rightEndCol; + } +MatrixProdPiece; + +//============================== Functions ================================ +void readFile(); + +Matrix *makeMatrix( int32 numRows, int32 numCols ); +Matrix *makeMatrix_Flat( int32 numRows, int32 numCols ); +Matrix *makeMatrix_WithResMat( int32 numRows, int32 numCols ); +void freeMatrix_Flat( Matrix * matrix ); +void freeMatrix( Matrix * matrix ); +void printMatrix( Matrix *matrix ); + +void read_Matrix_From_File( Matrix *matrixStruc, char *matrixFileName ); + +void +initialize_Input_Matrices_Via( Matrix **leftMatrix, Matrix **rightMatrix, + ParamBag *paramBag ); + +//=========================================================================== + +#endif /*MATRIX_MULT_H_*/ diff -r 000000000000 -r 3b0e43240104 src/Application/VPThread__Matrix_Mult/Divide_Pr.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/VPThread__Matrix_Mult/Divide_Pr.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,116 @@ +/* + * Copyright 2009 OpenSourceStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: seanhalle@yahoo.com + * + */ + + +#include "VPThread__Matrix_Mult.h" + +/*Divider creates one processor for every row-col pair. + * 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, + * 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 VPThread system. + */ +void divideIntoVectors( void *_dividerParams, VirtProcr *animatingThd ) + { VirtProcr *resultsThd; + DividerParams *dividerParams; + ResultsParams *resultsParams; + VectorParams *vectParams; + Matrix *leftMatrix, *rightMatrix, *resultMatrix; + void *msg; + MatrixMultGlobals *globals; + +// printf("start divide\n"); fflush(stdin); + + dividerParams = (DividerParams *)_dividerParams; + + leftMatrix = dividerParams->leftMatrix; + rightMatrix = dividerParams->rightMatrix; + + resultsParams = malloc( sizeof(ResultsParams) ); + resultsParams->dividerThd = animatingThd; + resultsParams->numCols = rightMatrix->numCols; + resultsParams->numRows = leftMatrix->numRows; + + //=========== Set up global vars, including conds and mutexes =========== + globals = malloc( sizeof(MatrixMultGlobals) ); + VPThread__set_globals_to( globals ); + + globals->results_mutex = VPThread__make_mutex( animatingThd ); + globals->results_cond = VPThread__make_cond( globals->results_mutex, + animatingThd ); + + globals->vector_mutex = VPThread__make_mutex( animatingThd ); + globals->vector_cond = VPThread__make_cond( globals->vector_mutex, + animatingThd ); + + globals->start_mutex = VPThread__make_mutex( animatingThd ); + globals->start_cond = VPThread__make_cond( globals->start_mutex, + animatingThd ); + //======================================================================== + + //get results-comm lock before create results-thd, to ensure it can't + // signal that results are available before this thd is waiting on cond + VPThread__mutex_lock( globals->results_mutex, animatingThd ); + + //also get the start lock & use to ensure no vector threads send a + // signal before the results thread is waiting on vector cond + VPThread__mutex_lock( globals->start_mutex, animatingThd ); + + + VPThread__create_thread( &gatherResults, resultsParams, animatingThd ); + + //Now wait for results thd to signal that it has vector lock + VPThread__cond_wait( globals->start_cond, animatingThd ); + VPThread__mutex_unlock( globals->start_mutex, animatingThd );//done w/lock + + + //make the vector thds + int row, col; + for( row = 0; row < leftMatrix->numRows; row++ ) + { for( col = 0; col < rightMatrix->numCols; col++ ) + { + vectParams = malloc( sizeof(VectorParams) ); + vectParams->myCol = col; + vectParams->myRow = row; + vectParams->vectLength = leftMatrix->numCols; + vectParams->leftMatrix = leftMatrix; + vectParams->rightMatrix = rightMatrix; + + VPThread__create_thread( &calcVector, vectParams, animatingThd ); + } + //=================== DEBUG =================== + #ifdef PRINT_DEBUG_1 + printf("created thread: %d, %d\n", row, col); + #endif + //============================================== + } + + //Wait for results thread to say results are good + VPThread__cond_wait( globals->results_cond, animatingThd ); + + //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 = malloc( sizeof(Matrix) ); + resultMatrix->numCols = rightMatrix->numCols; + resultMatrix->numRows = leftMatrix->numRows; + dividerParams->resultMatrix = resultMatrix; + resultMatrix->matrix = globals->results; + + //done with communication, release lock + VPThread__mutex_unlock( globals->results_mutex, animatingThd ); + + + VPThread__dissipate_thread( animatingThd ); //all Thds dissipate when done + //when all of the threads have dissipated, the "create seed and do + // work" call in the entry point function returns + } diff -r 000000000000 -r 3b0e43240104 src/Application/VPThread__Matrix_Mult/EntryPoint.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/VPThread__Matrix_Mult/EntryPoint.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,48 @@ +/* + * Copyright 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: seanhalle@yahoo.com + * + */ + +#include + +#include "VPThread__Matrix_Mult.h" + + + +/*Every VPThread system has an "entry point" function that creates the first + * processor, which starts the chain of creating more processors.. + * eventually all of the processors will dissipate themselves, and + * return. + * + *This entry-point function follows the same pattern as all entry-point + * functions do: + *1) it creates the params for the seed processor, from the + * parameters passed into the entry-point function + *2) it calls VPThread__create_seed_procr_and_do_work + *3) it gets the return value from the params struc, frees the params struc, + * and returns the value from the function + * + */ +Matrix * +multiplyTheseMatrices( Matrix *leftMatrix, Matrix *rightMatrix ) + { Matrix *resMatrix; + DividerParams *dividerParams; + + + dividerParams = malloc( sizeof( DividerParams ) ); + dividerParams->leftMatrix = leftMatrix; + dividerParams->rightMatrix = rightMatrix; + + + //create divider processor, start doing the work, and wait till done + //This function is the "border crossing" between normal code and VPThread + VPThread__create_seed_procr_and_do_work( ÷IntoVectors, dividerParams ); + + //get result matrix and return it + resMatrix = dividerParams->resultMatrix; + free( dividerParams ); + return resMatrix; + } diff -r 000000000000 -r 3b0e43240104 src/Application/VPThread__Matrix_Mult/Result_Pr.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/VPThread__Matrix_Mult/Result_Pr.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,86 @@ +/* + * Copyright 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: seanhalle@yahoo.com + * + */ + +#include "VPThread__Matrix_Mult.h" + +/*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. + * + *After the count reaches the point that all results have been received, it + * returns the result matrix and dissipates. + */ +void gatherResults( void *_params, VirtProcr *animatingPr ) + { VirtProcr *dividerPr; + ResultsParams *params; + int numRows, numCols, numCells, count=0; + float32 *resultMatrixArray; + void *msg; + VectorParams *aResult; + MatrixMultGlobals *globals =(MatrixMultGlobals *)VPThread__give_globals(); + + + //get vector-comm lock before loop, so that this thd keeps lock after + // one wait until it enters the next wait -- forces see-saw btwn + // waiters and signalers -- wait-signal-wait-signal-... + VPThread__mutex_lock( globals->vector_mutex, animatingPr ); + + //Tell divider that have the vector lock -- so it's sure won't miss any + // signals from the vector-threads it's about to create + VPThread__cond_signal( globals->start_cond, animatingPr ); + VPThread__mutex_unlock( globals->start_mutex, animatingPr );//finish wait + + //===================== DEBUG ====================== + #ifdef PRINT_DEBUG + printf("**Result Pr has the lock**\n" ); + fflush(stdin); + #endif + //==================================================== + + params = (ResultsParams *)_params; + dividerPr = params->dividerThd; + numCols = params->numCols; + numRows = params->numRows; + numCells = numRows * numCols; + + resultMatrixArray = malloc( numCells * sizeof( float32 ) ); + + + while( count < numCells ) + { + //receive a vector-result from a vector-thread + VPThread__cond_wait( globals->vector_cond, animatingPr ); + + aResult = globals->currVector; + *(resultMatrixArray + aResult->myRow * numCols + aResult->myCol) = + aResult->result; + count++; + //===================== DEBUG ====================== + #ifdef PRINT_DEBUG_1 + if( count - count/numRows * numRows == 0 ) + { printf("%d vector result: %f\n", count, aResult->result ); + fflush(stdin); + } + #endif + //==================================================== + + } + //all comms done, release lock + VPThread__mutex_unlock( globals->vector_mutex, animatingPr ); + + //Send result to divider (seed) thread + // note, divider thd had to hold the results-comm lock before creating + // this thread, to be sure no race + VPThread__mutex_lock( globals->results_mutex, animatingPr ); + globals->results = resultMatrixArray; + VPThread__cond_signal( globals->results_cond, animatingPr ); + VPThread__mutex_unlock( globals->results_mutex, animatingPr ); //releases + //divider thread from its wait, at point this executes + + VPThread__dissipate_thread( animatingPr ); //frees any data owned by procr + } diff -r 000000000000 -r 3b0e43240104 src/Application/VPThread__Matrix_Mult/VPThread__Matrix_Mult.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/VPThread__Matrix_Mult/VPThread__Matrix_Mult.h Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,75 @@ +/* + * Copyright Oct 24, 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + */ + +#ifndef _VPThread__MATRIX_MULT_H_ +#define _VPThread__MATRIX_MULT_H_ + +#include + +#include "../../VPThread__lib/VPThread.h" +#include "../Matrix_Mult.h" + +//============================== Structures ============================== +typedef struct + { + Matrix *leftMatrix; + Matrix *rightMatrix; + Matrix *resultMatrix; + } +DividerParams; + +typedef struct + { + VirtProcr *dividerThd; + int numRows; + int numCols; + } +ResultsParams; + +typedef struct + { VirtProcr *resultsThd; + int myCol; + int myRow; + int vectLength; + Matrix *leftMatrix; + Matrix *rightMatrix; + float32 result; + } +VectorParams; + +typedef struct + { + //for communicating vector results to results Thd + int32 vector_mutex; + int32 vector_cond; + VectorParams *currVector; + + //for communicating results array back to seed (divider) Thd + int32 results_mutex; + int32 results_cond; + float32 *results; + + //for ensuring results thd has vector lock before making vector thds + int32 start_mutex; + int32 start_cond; + + Matrix *rightMatrix; + Matrix *resultMatrix; + } +MatrixMultGlobals; + + +//============================= Processor Functions ========================= +void divideIntoVectors( void *data, VirtProcr *animatingPr ); +void calcVector( void *data, VirtProcr *animatingPr ); +void gatherResults( void *data, VirtProcr *animatingPr ); + + +//================================ Entry Point ============================== +Matrix * +multiplyTheseMatrices( Matrix *leftMatrix, Matrix *rightMatrix ); + + +#endif /*_VPThread__MATRIX_MULT_H_*/ diff -r 000000000000 -r 3b0e43240104 src/Application/VPThread__Matrix_Mult/Vector_Pr.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/VPThread__Matrix_Mult/Vector_Pr.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,59 @@ +/* + * Copyright 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * Author: SeanHalle@yahoo.com + * + */ + +#include "VPThread__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; + MatrixMultGlobals *globals =(MatrixMultGlobals *)VPThread__give_globals(); + + params = (VectorParams *)data; + myCol = params->myCol; + myRow = params->myRow; + vectLength = params->vectLength; + leftMatrix = params->leftMatrix; + rightMatrix = params->rightMatrix; + leftMatrixArray = leftMatrix->matrix; + rightMatrixArray = rightMatrix->matrix; + //===================== DEBUG ====================== + #ifdef PRINT_DEBUG_1 + if( myCol == 0 ) + printf("start vector: %d, %d\n", myRow, myCol ); fflush(stdin); + #endif + //==================================================== + + for( pos = 0; pos < vectLength; pos++ ) + { + result += *(leftMatrixArray + myRow * vectLength + pos) * + *(rightMatrixArray + pos * vectLength + myCol); + } + params->result = result; + + //Send result to results thread + VPThread__mutex_lock( globals->vector_mutex, animatingPr );//only get + //the lock when results thd is inside wait. + globals->currVector = params; + VPThread__cond_signal( globals->vector_cond, animatingPr ); + VPThread__mutex_unlock( globals->vector_mutex, animatingPr );//release + //wait-er -- cond_signal implemented such that wait-er gets lock, no other + + VPThread__dissipate_thread( animatingPr ); + } diff -r 000000000000 -r 3b0e43240104 src/Application/main.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Application/main.c Fri Sep 17 11:28:28 2010 -0700 @@ -0,0 +1,35 @@ +/* + * Copyright Oct 24, 2009 OpenSourceCodeStewardshipFoundation.org + * Licensed under GNU General Public License version 2 + * + * author seanhalle@yahoo.com + */ + +#include +#include + +#include "Matrix_Mult.h" +#include "VPThread__Matrix_Mult/VPThread__Matrix_Mult.h" + +/** + *Matrix multiply program written using VMS_HW piggy-back language + * + */ +int main( int argc, char **argv ) + { Matrix *leftMatrix, *rightMatrix, *resultMatrix; + ParamBag *paramBag; + + paramBag = makeParamBag(); + readParamFileIntoBag( argv[1], paramBag ); + initialize_Input_Matrices_Via( &leftMatrix, &rightMatrix, paramBag ); + + resultMatrix = multiplyTheseMatrices( leftMatrix, rightMatrix ); + + printf("\nresult matrix: \n"); + +// printMatrix( resultMatrix ); + +// VPThread__print_stats(); + + exit(0); //cleans up + }