SPModel: libSPModel/src/SurfaceMeshIrregularDecomp.c Source File
VPAC - Computational Software Development
Main | SPModel | StGermain FrameWork |
Main Page | Alphabetical List | Class List | Directories | File List | Class Members | File Members

SurfaceMeshIrregularDecomp.c

Go to the documentation of this file.
00001 /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
00002 **
00003 ** Copyright (C), 2004, Victorian Partnership for Advanced Computing (VPAC) Ltd, 110 Victoria Street, Melbourne, 3053, Australia.
00004 **
00005 ** Authors:
00006 **  Ogar R. Widjaja, Computational Scientist, VPAC.
00007 **  Raquibul Hassan, Software Engineer, VPAC. (raq@vpac.org)
00008 **  Keith Hsuan, Computational Scientist, VPAC (keith@vpac.org)
00009 **  William F. Appelbe, Director, VPAC. (bill@vpac.org)
00010 **  Stevan M. Quenette, Senior Software Engineer, VPAC. (steve@vpac.org)
00011 **  Patrick D. Sunter, Software Engineer, VPAC. (patrick@vpac.org)
00012 **
00013 ** This file may be distributed under the terms of the VPAC Public License
00014 ** as defined by VPAC of Australia and appearing in the file
00015 ** LICENSE.VPL included in the packaging of this file.
00016 **
00017 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00018 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00019 **
00020 */
00030 #include <mpi.h>
00031 #include <StGermain/StGermain.h>
00032 #include <Cascade/cascade.h>
00033 
00034 #include <stdio.h>
00035 #include <stdlib.h>
00036 #include <string.h>
00037 #include <assert.h>
00038 #include <math.h>
00039 #include <limits.h>
00040 #include "types.h"
00041 #include "SurfaceMeshDecomp.h"
00042 #include "SurfaceMeshIrregularDecomp.h"
00043 #include "SurfaceMesh.h"
00044 #include "Catchment.h"
00045 #include "Misc.h"
00046 #include "CommHandler.h"
00047 
00048 const Type SurfaceMeshIrregularDecomp_Type = "SurfaceMeshIrregularDecomp";
00049 
00050 SurfaceMeshIrregularDecomp          *SurfaceMeshIrregularDecomp_DefaultNew( Name name )
00051 {
00052     return _SurfaceMeshIrregularDecomp_New( sizeof( SurfaceMeshIrregularDecomp ),
00053                                             SurfaceMeshIrregularDecomp_Type,
00054                                             _SurfaceMeshIrregularDecomp_Delete,
00055                                             _SurfaceMeshIrregularDecomp_Print,
00056                                             NULL,
00057                                             (void*)SurfaceMeshIrregularDecomp_DefaultNew,
00058                                             _SurfaceMeshIrregularDecomp_Construct,
00059                                             _SurfaceMeshIrregularDecomp_Build,
00060                                             _SurfaceMeshIrregularDecomp_Initialise,
00061                                             _SurfaceMeshIrregularDecomp_Execute,
00062                                             _SurfaceMeshIrregularDecomp_Destroy,
00063                                             name,
00064                                             False,
00065                                             NULL,
00066                                             NULL,
00067                                             NULL,
00068                                             _SurfaceMeshDecomp_SyncMesh,
00069                                             _SurfaceMeshDecomp_ComputeHaloNodes,
00070                                             SurfaceMeshIrregularDecomp_AllocateNodes );
00071 }
00072 
00073 SurfaceMeshIrregularDecomp          *SurfaceMeshIrregularDecomp_New( Name name, CatchmentList *cList,
00074                                                                         SurfaceMesh *mesh,
00075                                                                         Dictionary *dictionary )
00076 {
00077     return _SurfaceMeshIrregularDecomp_New( sizeof( SurfaceMeshIrregularDecomp ),
00078                                             SurfaceMeshIrregularDecomp_Type,
00079                                             _SurfaceMeshIrregularDecomp_Delete,
00080                                             _SurfaceMeshIrregularDecomp_Print,
00081                                             NULL,
00082                                             (void*)SurfaceMeshIrregularDecomp_DefaultNew,
00083                                             _SurfaceMeshIrregularDecomp_Construct,
00084                                             _SurfaceMeshIrregularDecomp_Build,
00085                                             _SurfaceMeshIrregularDecomp_Initialise,
00086                                             _SurfaceMeshIrregularDecomp_Execute,
00087                                             _SurfaceMeshIrregularDecomp_Destroy,
00088                                             name,
00089                                             True,
00090                                             dictionary,
00091                                             cList,
00092                                             mesh,
00093                                             _SurfaceMeshDecomp_SyncMesh,
00094                                             _SurfaceMeshDecomp_ComputeHaloNodes,
00095                                             SurfaceMeshIrregularDecomp_AllocateNodes );
00096 }
00097 
00098 SurfaceMeshIrregularDecomp          *_SurfaceMeshIrregularDecomp_New( SizeT                         _sizeOfSelf,
00099                                     Type                            type,
00100                                     Stg_Class_DeleteFunction*               _delete,
00101                                     Stg_Class_PrintFunction*                _print,
00102                                     Stg_Class_CopyFunction*             _copy, 
00103                                     Stg_Component_DefaultConstructorFunction*   _defaultConstructor,
00104                                     Stg_Component_ConstructFunction*            _construct,
00105                                     Stg_Component_BuildFunction*        _build,
00106                                     Stg_Component_InitialiseFunction*       _initialise,
00107                                     Stg_Component_ExecuteFunction*      _execute,
00108                                     Stg_Component_DestroyFunction*      _destroy,
00109                                     Name                            name,
00110                                     Bool                            initFlag,
00111                                     Dictionary                      *dictionary,
00112                                     CatchmentList                   *_catchmentList,
00113                                     SurfaceMesh                     *_mesh,
00114                                     SurfaceMeshDecomp_SyncMeshFunction *_syncMesh,
00115                                     SurfaceMeshDecomp_ComputeHaloNodesFunction *_computeHaloNodes,
00116                                     SurfaceMeshDecomp_AllocateNodesFunction *_allocateNodes )
00117 {
00118     SurfaceMeshIrregularDecomp *self = NULL;
00119     
00120     assert( _sizeOfSelf >= sizeof( SurfaceMeshIrregularDecomp ) );
00121 
00122     self = (SurfaceMeshIrregularDecomp*)_SurfaceMeshDecomp_New ( _sizeOfSelf,
00123                                                             type,
00124                                                             _delete,
00125                                                             _print,
00126                                                             _copy,
00127                                                             _defaultConstructor,
00128                                                             _construct,
00129                                                             _build,
00130                                                             _initialise,
00131                                                             _execute,
00132                                                             _destroy,
00133                                                             name,
00134                                                             initFlag,
00135                                                             dictionary,
00136                                                             _mesh,
00137                                                             _syncMesh,
00138                                                             _computeHaloNodes,
00139                                                             _allocateNodes );
00140 
00141     assert( _catchmentList );
00142     self->catchmentList = _catchmentList;
00143     
00144     if( initFlag ){
00145         _SurfaceMeshIrregularDecomp_Init( self );
00146     }
00147     
00148     return self;
00149 }
00150 
00151 void _SurfaceMeshIrregularDecomp_Init( SurfaceMeshIrregularDecomp *self )
00152 {
00153     int i = 0, numProcs = 0, rank = 0;
00154 
00155     assert( self );
00156 
00157     numProcs = self->mesh->numProcs;
00158     rank = self->mesh->rank;
00159     
00160     if( rank == MASTER_PROC ){
00161     
00162         self->processorCatchments = (LinkedList**) malloc( sizeof( LinkedList* ) * numProcs );
00163     
00164         for( i=0; i<numProcs; i++ ){
00165             self->processorCatchments[i] = LinkedList_New( catchmentCompareFunction,
00166                                                         NULL,
00167                                                         (LinkedList_dataPrintFunction*)catchmentPrintFunction,
00168                                                         NULL,
00169                                                         LINKEDLIST_UNSORTED );
00170         }
00171     }
00172     else{
00173 
00174     }
00175 }
00176 
00177 void _SurfaceMeshIrregularDecomp_Print( void *surfaceMeshIrregularDecomp, Stream *stream )
00178 {
00179     assert( surfaceMeshIrregularDecomp );
00180     assert( stream );
00181 
00182     /* Parent print */
00183     _SurfaceMeshDecomp_Print( (_SurfaceMeshDecomp*)surfaceMeshIrregularDecomp, stream );
00184     
00185     /* general info */
00186     Journal_Printf( stream, "SurfaceMeshIrregularDecomp (ptr): (%p)\n", surfaceMeshIrregularDecomp );
00187 
00188 }
00189 
00190 void _SurfaceMeshIrregularDecomp_Delete( void *surfaceMeshIrregularDecomp )
00191 {
00192     int i, rank, numProcs;
00193     SurfaceMeshIrregularDecomp *self = (SurfaceMeshIrregularDecomp*)surfaceMeshIrregularDecomp;
00194     
00195     assert( self );
00196 
00197     rank = self->mesh->rank;
00198     numProcs = self->mesh->numProcs;
00199     
00200     if( rank == MASTER_PROC ){
00201         _SurfaceMeshDecomp_Delete( self );
00202         if( self->processorCatchments ){
00203             for( i=0; i<numProcs; i++ ){
00204                 Stg_Class_Delete( self->processorCatchments[i] );
00205             }
00206             free( self->processorCatchments );
00207         }
00208     }
00209     else{
00210 
00211     }
00212 }
00213 
00214 void _SurfaceMeshIrregularDecomp_Construct( void *surfaceMeshIrregularDecomp, Stg_ComponentFactory *cf )
00215 {
00216     
00217 }
00218 
00219 void _SurfaceMeshIrregularDecomp_Build( void *surfaceMeshIrregularDecomp, void *data )
00220 {
00221     SurfaceMeshIrregularDecomp *self = (SurfaceMeshIrregularDecomp*)surfaceMeshIrregularDecomp;
00222     
00223     assert( self );
00224     
00225     _SurfaceMeshDecomp_Build( self, data );
00226     
00227 }
00228 
00229 void _SurfaceMeshIrregularDecomp_Initialise( void *surfaceMeshIrregularDecomp, void *data )
00230 {
00231     
00232 }
00233 
00234 void _SurfaceMeshIrregularDecomp_Execute( void *surfaceMeshIrregularDecomp, void *data )
00235 {
00236     SurfaceMeshIrregularDecomp *self = (SurfaceMeshIrregularDecomp*)surfaceMeshIrregularDecomp;
00237     
00238     assert( self );
00239     
00240     _SurfaceMeshDecomp_Execute( self, data );
00241 }
00242 
00243 void _SurfaceMeshIrregularDecomp_Destroy( void *surfaceMeshIrregularDecomp, void *data )
00244 {
00245     
00246 }
00247 
00250 void SurfaceMeshIrregularDecomp_SyncMesh( SurfaceMeshIrregularDecomp *surfaceMeshIrregularDecomp, SurfaceMesh *mesh )
00251 {
00252     SurfaceMeshIrregularDecomp *self = (SurfaceMeshIrregularDecomp*)surfaceMeshIrregularDecomp;
00253     
00254     assert( self );
00255     assert( mesh );
00256     
00257     _SurfaceMeshDecomp_SyncMesh( (_SurfaceMeshDecomp*)self, mesh );
00258 }
00259 
00260 void SurfaceMeshIrregularDecomp_ComputeHaloNodes( SurfaceMeshIrregularDecomp *surfaceMeshIrregularDecomp )
00261 {
00262     SurfaceMeshIrregularDecomp *self = (SurfaceMeshIrregularDecomp*)surfaceMeshIrregularDecomp;
00263     
00264     assert( self );
00265 
00266     _SurfaceMeshDecomp_ComputeHaloNodes( (_SurfaceMeshDecomp*)self );
00267 }
00268 
00269 void AssignProcessor( SurfaceMeshIrregularDecomp *surfaceMeshIrregularDecomp, int nodeId, int processor )
00270 {
00271     SurfaceMesh *mesh = NULL;
00272     int *result = NULL;
00273     int i;
00274     
00275     assert( surfaceMeshIrregularDecomp );
00276 
00277     mesh = surfaceMeshIrregularDecomp->mesh;
00278     assert( mesh );
00279     
00280     mesh->processor[nodeId-1] = processor;
00281     for (i=0; i<mesh->nodeProviders[nodeId-1]->nodeCount; i++) {
00282         result = LinkedList_ReturnNodeDataAt(mesh->nodeProviders[nodeId-1], i, int);
00283         assert(result);
00284         
00285         AssignProcessor( surfaceMeshIrregularDecomp, *result, processor );
00286     }   
00287 }
00288 
00289 void SurfaceMeshIrregularDecomp_AllocateNodes( _SurfaceMeshDecomp *surfaceMeshDecomp )
00290 {   
00291     typedef struct optimumCatchment_t{
00292         float dr;
00293         Catchment *catchment;
00294     }optimumCatchment;
00295     
00296     SurfaceMeshIrregularDecomp *surfaceMeshIrregularDecomp = NULL;
00297     SurfaceMesh *mesh = NULL;
00298     CatchmentList *cList = NULL;
00299     BTreeIterator *iter = NULL;
00300     LinkedListIterator *listIter = NULL;
00301     Catchment *currentPtr;
00302     int i = 0, j = 0, k = 0;
00303     optimumCatchment *score = NULL;
00304     float dr = 0.0f;
00305     int targetProc = 0;
00306     int *allocatedCatchments = NULL;
00307     int allocatedCatchmentIndex = 0;
00308     float minX, minY, minH, maxX, maxY, maxH, temp;
00309     Coord centre;
00310     Catchment  *targetCatchment = NULL;
00311     Catchment *tempCatchment = NULL;
00312     int minCatchmentSize = 0;
00313     float radius, radiusSq;
00314     float pi2 = 22.0f / 7.0f * 2.0f;
00315     float theta = 0.0f;
00316     Coord direc;
00317     Coord point;
00318     Coord *procCentres = NULL;
00319     
00320     surfaceMeshIrregularDecomp = ( SurfaceMeshIrregularDecomp* ) surfaceMeshDecomp;
00321     assert( surfaceMeshIrregularDecomp ); 
00322 
00323     cList = surfaceMeshIrregularDecomp->catchmentList;
00324     mesh = surfaceMeshIrregularDecomp->mesh;
00325 
00326     for( i=0; i<cList->numProcs; i++ ){
00327         surfaceMeshIrregularDecomp->processorLoad[i] = 0;
00328     }
00329 
00330     for( i=0; i<mesh->numNodes; i++ ){
00331         mesh->processor[i] = -1;
00332     }
00333 
00334     score = malloc( sizeof( optimumCatchment ) * mesh->numProcs );
00335     memset( score, 0, sizeof( optimumCatchment ) * mesh->numProcs );
00336     allocatedCatchments = malloc( sizeof( int ) * cList->catchments->nodeCount );
00337     memset( allocatedCatchments, 0, sizeof( int ) * cList->catchments->nodeCount );
00338     procCentres = malloc( sizeof(Coord)*mesh->numProcs );
00339     
00340     tempCatchment = NULL;
00341     j = 0;
00342     minX = 1e32;
00343     minY = 1e32;
00344     minH = 1e32;
00345     maxX = -1e32;
00346     maxY = -1e32;
00347     maxH = -1e32;
00348     for( i=0; i<mesh->numNodes; i++ ){
00349         if( minX > mesh->x[i] ){
00350             minX = mesh->x[i];
00351         }
00352         if( minY > mesh->y[i] ){
00353             minY = mesh->y[i];
00354         }
00355         if( minH > mesh->h[i] ){
00356             minH = mesh->h[i];
00357         }
00358         
00359         if( maxX < mesh->x[i] ){
00360             maxX = mesh->x[i];
00361         }
00362         if( maxY < mesh->y[i] ){
00363             maxY = mesh->y[i];
00364         }
00365         if( maxH < mesh->h[i] ){
00366             maxH = mesh->h[i];
00367         }
00368     }
00369 
00370     centre[0] = (maxX - minX) / 2.0f;
00371     centre[1] = (maxY - minY) / 2.0f;
00372     centre[2] = (maxH - minH) / 2.0f;
00373 
00374     /*printf( "centre %lf, %lf, %lf\n", centre[0], centre[1], centre[2] );*/
00375 
00376     radiusSq = -1e32;
00377     for( i=0; i<mesh->numNodes; i++ ){
00378         temp = pow( centre[0] - mesh->x[i], 2.0f ) +
00379                 pow( centre[1] - mesh->y[i], 2.0f ) ;
00380 
00381         if( radiusSq < temp ){
00382             radiusSq = temp;
00383         }
00384     }
00385     radius = sqrt( radiusSq );
00386     /*printf( "radius %lf\n", radius );*/
00387 
00388     direc[0] = 1.0f;
00389     direc[1] = 0.0f;
00390     direc[2] = 0.0f;
00391 
00392     theta = 0.0f;
00393     iter = BTreeIterator_New( cList->catchments );
00394     currentPtr = (Catchment*)BTreeIterator_First( iter );
00395     assert( currentPtr );
00396     minCatchmentSize = mesh->numNodes / (currentPtr->netSize * mesh->numProcs);
00397     for( i=0; i<mesh->numProcs; i++ ){
00398         point[0] = centre[0] + radius * (cos( theta ) * direc[0] + sin( theta ) * direc[1]);
00399         point[1] = centre[1] + radius * (-sin( theta ) * direc[0] + cos(theta)*direc[1]);
00400         point[2] = 0.0f;
00401 
00402         dr = 1e32;
00403         for (currentPtr = (Catchment*) BTreeIterator_First( iter ), k = 0;
00404                 currentPtr != NULL;
00405                 currentPtr = (Catchment*) BTreeIterator_Next( iter ), k++){
00406             
00407             if( allocatedCatchments[k] ){
00408                 continue;
00409             }
00410             
00411             temp =  sqrt(pow((mesh->x[currentPtr->localMinimum-1] - point[0]), 2.0f) +
00412                 pow((mesh->y[currentPtr->localMinimum-1] - point[1]), 2.0f) );
00413 
00414             if(dr > temp /*&& currentPtr->netSize > minCatchmentSize*/){
00415                 
00416                 targetCatchment = currentPtr;
00417                 dr = temp;
00418                 allocatedCatchmentIndex = k;
00419             }
00420         }
00421         
00422         assert( targetCatchment );
00423             
00424         AssignProcessor( surfaceMeshIrregularDecomp, targetCatchment->localMinimum, i );
00425         surfaceMeshIrregularDecomp->processorLoad[i] += targetCatchment->netSize;
00426         
00427         LinkedList_InsertNode( surfaceMeshIrregularDecomp->processorCatchments[i], (void*)targetCatchment, sizeof(int) );
00428         allocatedCatchments[allocatedCatchmentIndex]++;
00429 
00430         procCentres[i][0] = targetCatchment->catchmentCentre.x;
00431         procCentres[i][1] = targetCatchment->catchmentCentre.y;
00432         procCentres[i][2] = targetCatchment->catchmentCentre.h;
00433 
00434         theta += pi2 / (float)(mesh->numProcs);
00435         /*printf( "theta %lf\n", theta );
00436         printf( "point - %lf, %lf, %lf\n", point[0], point[1], point[2] );*/
00437     }
00438     
00439     for (currentPtr = (Catchment*) BTreeIterator_First( iter ), k = 0;
00440             currentPtr != NULL;
00441             currentPtr = (Catchment*) BTreeIterator_Next( iter ), k++){
00442         
00443         if( allocatedCatchments[k] ){
00444             continue;
00445         }
00446 
00447         for( i=0; i<mesh->numProcs; i++ ){
00448             listIter = LinkedListIterator_New( surfaceMeshIrregularDecomp->processorCatchments[i] );
00449 
00450             dr = 1e32;
00451 #if 0
00452             for( tempCatchment = LinkedListIterator_First( listIter );
00453                     tempCatchment; tempCatchment = LinkedListIterator_Next( listIter )){
00454 
00455                 temp =  sqrt(pow((mesh->x[currentPtr->localMinimum-1] - mesh->x[tempCatchment->localMinimum-1]), 2.0f) +
00456                     pow((mesh->y[currentPtr->localMinimum-1] - mesh->y[tempCatchment->localMinimum-1]), 2.0f) +
00457                     pow((mesh->h[currentPtr->localMinimum-1] - mesh->h[tempCatchment->localMinimum-1]), 2.0f));
00458                     /*sqrt(pow((currentPtr->catchmentCentre.x - tempCatchment->catchmentCentre.x), 2.0f) +
00459                     pow((currentPtr->catchmentCentre.y - tempCatchment->catchmentCentre.y), 2.0f) +
00460                     pow((currentPtr->catchmentCentre.h  - tempCatchment->catchmentCentre.h), 2.0f));*/
00461 
00462                 if( dr > temp ){
00463                     dr = temp;
00464                     score[i].dr = dr;
00465                     score[i].catchment = tempCatchment;
00466                 }
00467             }
00468             
00469             Stg_Class_Delete( listIter );
00470 #endif
00471             score[i].dr = sqrt(pow((mesh->x[currentPtr->localMinimum-1] - procCentres[i][0]), 2.0f) +
00472                     pow((mesh->y[currentPtr->localMinimum-1] - procCentres[i][1]), 2.0f) +
00473                     pow((mesh->h[currentPtr->localMinimum-1] - procCentres[i][2]), 2.0f));
00474         }
00475 
00476         dr = 1e32;
00477         for( i=0; i<mesh->numProcs; i++ ){
00478             if( dr > score[i].dr ){
00479                 dr = score[i].dr;
00480                 targetProc = i;
00481             }
00482         }
00483         
00484         AssignProcessor( surfaceMeshIrregularDecomp, currentPtr->localMinimum, targetProc );
00485         surfaceMeshIrregularDecomp->processorLoad[targetProc] += currentPtr->netSize;
00486 
00487         LinkedList_InsertNode( surfaceMeshIrregularDecomp->processorCatchments[targetProc], (void*)currentPtr, sizeof(int) );
00488         assert(!allocatedCatchments[k]);
00489         allocatedCatchments[k]++;
00490     }
00491     
00492     Stg_Class_Delete( iter );
00493     free( score );
00494     free( allocatedCatchments );
00495     
00496     {
00497         int j = 0;
00498         for( i=0; i<cList->numProcs; i++ ){
00499             printf( "on processor[%d] %d nodes %d catchments\n", i, surfaceMeshIrregularDecomp->processorLoad[i],
00500                     surfaceMeshIrregularDecomp->processorCatchments[i]->nodeCount );
00501             for( j=0; j<mesh->numNodes; j++ ){
00502                 if( mesh->processor[j] == i ){
00503                     /*printf( "\tnode id - %d\n", mesh->id[j] );*/
00504                 }
00505             }
00506         }
00507     }
00508 }
00509