EvolvingObjects
eoMpiAssignmentAlgorithm.h
00001 /*
00002 (c) Thales group, 2012
00003 
00004     This library is free software; you can redistribute it and/or
00005     modify it under the terms of the GNU Lesser General Public
00006     License as published by the Free Software Foundation;
00007     version 2 of the License.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Lesser General Public License for more details.
00013 
00014     You should have received a copy of the GNU Lesser General Public
00015     License along with this library; if not, write to the Free Software
00016     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00017 Contact: http://eodev.sourceforge.net
00018 
00019 Authors:
00020     Benjamin Bouvier <benjamin.bouvier@gmail.com>
00021 */
00022 # ifndef __MPI_ASSIGNMENT_ALGORITHM_H__
00023 # define __MPI_ASSIGNMENT_ALGORITHM_H__
00024 
00025 # include <vector> // std::vector
00026 # include "eoMpiNode.h"
00027 
00028 namespace eo
00029 {
00030     namespace mpi
00031     {
00038         const int REST_OF_THE_WORLD = -1;
00039 
00049         struct AssignmentAlgorithm
00050         {
00056             virtual int get( ) = 0;
00057 
00067             virtual int availableWorkers( ) = 0;
00068 
00074             virtual void confirm( int wrkRank ) = 0;
00075 
00085             virtual std::vector<int> idles( ) = 0;
00086 
00095             virtual void reinit( int runs ) = 0;
00096         };
00097 
00111         struct DynamicAssignmentAlgorithm : public AssignmentAlgorithm
00112         {
00113             public:
00114 
00118                 DynamicAssignmentAlgorithm( )
00119                 {
00120                     for(int i = 1; i < Node::comm().size(); ++i)
00121                     {
00122                         availableWrk.push_back( i );
00123                     }
00124                 }
00125 
00131                 DynamicAssignmentAlgorithm( int unique )
00132                 {
00133                     availableWrk.push_back( unique );
00134                 }
00135 
00141                 DynamicAssignmentAlgorithm( const std::vector<int> & workers )
00142                 {
00143                     availableWrk = workers;
00144                 }
00145 
00153                 DynamicAssignmentAlgorithm( int first, int last )
00154                 {
00155                     if( last == REST_OF_THE_WORLD )
00156                     {
00157                         last = Node::comm().size() - 1;
00158                     }
00159 
00160                     for( int i = first; i <= last; ++i)
00161                     {
00162                         availableWrk.push_back( i );
00163                     }
00164                 }
00165 
00166                 virtual int get( )
00167                 {
00168                     int assignee = -1;
00169                     if (! availableWrk.empty() )
00170                     {
00171                         assignee = availableWrk.back();
00172                         availableWrk.pop_back();
00173                     }
00174                     return assignee;
00175                 }
00176 
00177                 int availableWorkers()
00178                 {
00179                     return availableWrk.size();
00180                 }
00181 
00182                 void confirm( int rank )
00183                 {
00184                     availableWrk.push_back( rank );
00185                 }
00186 
00187                 std::vector<int> idles( )
00188                 {
00189                     return availableWrk;
00190                 }
00191 
00192                 void reinit( int _ )
00193                 {
00194                     ++_;
00195                     // nothing to do
00196                 }
00197 
00198             protected:
00199                 std::vector< int > availableWrk;
00200         };
00201 
00217         struct StaticAssignmentAlgorithm : public AssignmentAlgorithm
00218         {
00219             public:
00226                 StaticAssignmentAlgorithm( std::vector<int>& workers, int runs )
00227                 {
00228                     init( workers, runs );
00229                 }
00230 
00239                 StaticAssignmentAlgorithm( int first, int last, int runs )
00240                 {
00241                     std::vector<int> workers;
00242 
00243                     if( last == REST_OF_THE_WORLD )
00244                     {
00245                         last = Node::comm().size() - 1;
00246                     }
00247 
00248                     for(int i = first; i <= last; ++i)
00249                     {
00250                         workers.push_back( i );
00251                     }
00252                     init( workers, runs );
00253                 }
00254 
00261                 StaticAssignmentAlgorithm( int runs = 0 )
00262                 {
00263                     std::vector<int> workers;
00264                     for(int i = 1; i < Node::comm().size(); ++i)
00265                     {
00266                         workers.push_back( i );
00267                     }
00268 
00269                     init( workers, runs );
00270                 }
00271 
00278                 StaticAssignmentAlgorithm( int unique, int runs )
00279                 {
00280                     std::vector<int> workers;
00281                     workers.push_back( unique );
00282                     init( workers, runs );
00283                 }
00284 
00285             private:
00295                 void init( std::vector<int> & workers, int runs )
00296                 {
00297                     unsigned int nbWorkers = workers.size();
00298                     freeWorkers = nbWorkers;
00299 
00300                     busy.clear();
00301                     busy.resize( nbWorkers, false );
00302                     realRank = workers;
00303 
00304                     if( runs <= 0 )
00305                     {
00306                         return;
00307                     }
00308 
00309                     attributions.clear();
00310                     attributions.reserve( nbWorkers );
00311 
00312                     // Let be the euclidean division of runs by nbWorkers :
00313                     // runs == q * nbWorkers + r, 0 <= r < nbWorkers
00314                     // This one liner affects q requests to each worker
00315                     for (unsigned int i = 0; i < nbWorkers; attributions[i++] = runs / nbWorkers) ;
00316                     // The first line computes r and the one liner affects the remaining
00317                     // r requests to workers, in ascending order
00318                     unsigned int diff = runs - (runs / nbWorkers) * nbWorkers;
00319                     for (unsigned int i = 0; i < diff; ++attributions[i++]);
00320                 }
00321 
00322             public:
00323                 int get( )
00324                 {
00325                     int assignee = -1;
00326                     for( unsigned i = 0; i < busy.size(); ++i )
00327                     {
00328                         if( !busy[i] && attributions[i] > 0 )
00329                         {
00330                             busy[i] = true;
00331                             --freeWorkers;
00332                             assignee = realRank[ i ];
00333                             break;
00334                         }
00335                     }
00336                     return assignee;
00337                 }
00338 
00339                 int availableWorkers( )
00340                 {
00341                     return freeWorkers;
00342                 }
00343 
00344                 std::vector<int> idles()
00345                 {
00346                     std::vector<int> ret;
00347                     for(unsigned int i = 0; i < busy.size(); ++i)
00348                     {
00349                         if( !busy[i] )
00350                         {
00351                             ret.push_back( realRank[i] );
00352                         }
00353                     }
00354                     return ret;
00355                 }
00356 
00357                 void confirm( int rank )
00358                 {
00359                     int i = -1; // i is the real index in table
00360                     for( unsigned int j = 0; j < realRank.size(); ++j )
00361                     {
00362                         if( realRank[j] == rank )
00363                         {
00364                             i = j;
00365                             break;
00366                         }
00367                     }
00368 
00369                     --attributions[ i ];
00370                     busy[ i ] = false;
00371                     ++freeWorkers;
00372                 }
00373 
00374                 void reinit( int runs )
00375                 {
00376                     init( realRank, runs );
00377                 }
00378 
00379             private:
00380                 std::vector<int> attributions;
00381                 std::vector<int> realRank;
00382                 std::vector<bool> busy;
00383                 unsigned int freeWorkers;
00384         };
00385     }
00386 }
00387 # endif // __MPI_ASSIGNMENT_ALGORITHM_H__
 All Classes Namespaces Files Functions Variables Typedefs Friends