src/OpenFOAM/containers/Lists/SortableList/ParSortableList.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 1991-2008 OpenCFD Ltd.
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software; you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by the
  13     Free Software Foundation; either version 2 of the License, or (at your
  14     option) any later version.
  15
  16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with OpenFOAM; if not, write to the Free Software Foundation,
  23     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  24
  25 \*---------------------------------------------------------------------------*/
  26
  27 #include "ParSortableList.H"
  28 #include "SortableList.H"
  29 #include "Pstream.H"
  30 #include "ListListOps.H"
  31 #include "PstreamReduceOps.H"
  32
  33 // * * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * //
  34
  35 template <class Type>
  36 void Foam::ParSortableList<Type>::write
  37 (
  38     const List<Type>& elems,
  39     Ostream& os
  40 ) const
  41 {
  42     os << '(';
  43
  44     forAll(elems, elemI)
  45     {
  46         os << ' ' << elems[elemI];
  47     }
  48     os << ')';
  49 }
  50
  51
  52 // Copy src, starting at destI into dest.
  53 template <class Type>
  54 void Foam::ParSortableList<Type>::copyInto
  55 (
  56     const List<Type>& values,
  57     const labelList& indices,
  58     const label fromProcNo,
  59     label& destI,
  60     List<taggedValue>& dest
  61 ) const
  62 {
  63     forAll(values, elemI)
  64     {
  65         taggedValue& tagVal = dest[destI];
  66
  67         tagVal.value() = values[elemI];
  68         tagVal.index() = indices[elemI];
  69         tagVal.procID() = fromProcNo;
  70
  71         destI++;
  72     }
  73 }
  74
  75
  76 template <class Type>
  77 void Foam::ParSortableList<Type>::getPivots
  78 (
  79     const List<Type>& elems,
  80     List<Type>& pivots
  81 ) const
  82 {
  83     pivots.setSize(Pstream::nProcs());
  84
  85     label pivotPos = 0;
  86
  87     forAll(pivots, pivotI)
  88     {
  89         pivots[pivotI] = elems[pivotPos];
  90
  91         pivotPos += elems.size()/Pstream::nProcs();
  92     }
  93 }
  94
  95
  96 template <class Type>
  97 void Foam::ParSortableList<Type>::checkAndSend
  98 (
  99     List<Type>& values,
 100     labelList& indices,
 101     const label bufSize,
 102     const label destProcI
 103 ) const
 104 {
 105     if (destProcI != Pstream::myProcNo())
 106     {
 107         values.setSize(bufSize);
 108         indices.setSize(bufSize);
 109
 110         if (debug)
 111         {
 112             Pout<<  "Sending to " << destProcI << " elements:" << values
 113                 << endl;
 114         }
 115
 116         {
 117             OPstream toSlave(destProcI);
 118             toSlave << values << indices;
 119         }
 120     }
 121 }
 122
 123
 124 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
 125
 126 // Construct from List, sorting the elements
 127 template <class Type>
 128 Foam::ParSortableList<Type>::ParSortableList(const List<Type>& values)
 129 :
 130     List<Type>(values),
 131     indices_(0),
 132     procs_(0)
 133 {
 134     sort();
 135 }
 136
 137
 138 // Construct given size. Sort later on.
 139 template <class Type>
 140 Foam::ParSortableList<Type>::ParSortableList(const label size)
 141 :
 142     List<Type>(size),
 143     indices_(0),
 144     procs_(0)
 145 {}
 146
 147
 148 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 149
 150 // Sort
 151 template <class Type>
 152 void Foam::ParSortableList<Type>::sort()
 153 {
 154     //
 155     // 0. Get total size of dataset.
 156     //
 157
 158     label n = this->size();
 159
 160     reduce(n, sumOp<label>());
 161
 162
 163     // 1. Sort list locally
 164     SortableList<Type> sorted(*this);
 165
 166     // Collect elements at pivot points
 167     labelListList sortedGatherList(Pstream::nProcs());
 168
 169     labelList& pivots = sortedGatherList[Pstream::myProcNo()];
 170
 171     getPivots(sorted, pivots);
 172
 173     if (debug)
 174     {
 175         Pout<< "pivots:";
 176         write(pivots, Pout);
 177         Pout<< endl;
 178     }
 179
 180
 181     //
 182     // 2. Combine pivotlist per processor onto master, sort, get pivots.
 183     //
 184
 185     Pstream::gatherList(sortedGatherList);
 186
 187     if (Pstream::master())
 188     {
 189         labelList allPivots =
 190             ListListOps::combine<labelList>
 191             (
 192                 sortedGatherList,
 193                 accessOp<labelList>()
 194             );
 195
 196         SortableList<Type> sortedPivots(allPivots);
 197
 198         if (debug)
 199         {
 200             Pout<< "allPivots:";
 201             write(allPivots, Pout);
 202             Pout<< endl;
 203         }
 204
 205         getPivots(sortedPivots, pivots);
 206     }
 207     Pstream::scatter(pivots);
 208
 209     if (debug)
 210     {
 211         Pout<< "new pivots:";
 212         write(pivots, Pout);
 213         Pout<< endl;
 214     }
 215
 216
 217     //
 218     // 3. Distribute pivots & distribute.
 219     //
 220
 221     label pivotI = 1;
 222     label destProcI = 0;
 223
 224     // Buffer for my own data. Keep original index together with value.
 225     labelList ownValues(sorted.size());
 226     labelList ownIndices(sorted.size());
 227     label ownI = 0;
 228
 229     // Buffer for sending data
 230     labelList sendValues(sorted.size());
 231     labelList sendIndices(sorted.size());
 232     label sendI = 0;
 233
 234     forAll(sorted, sortedI)
 235     {
 236         if ((pivotI < Pstream::nProcs()) && (sorted[sortedI] > pivots[pivotI]))
 237         {
 238             checkAndSend(sendValues, sendIndices, sendI, destProcI);
 239
 240             // Reset buffer.
 241             sendValues.setSize(sorted.size());
 242             sendIndices.setSize(sorted.size());
 243             sendI = 0;
 244
 245             pivotI++;
 246             destProcI++;
 247         }
 248
 249         if (destProcI != Pstream::myProcNo())
 250         {
 251             sendValues[sendI] = sorted[sortedI];
 252             sendIndices[sendI] = sorted.indices()[sortedI];
 253             sendI++;
 254         }
 255         else
 256         {
 257             ownValues[ownI] = sorted[sortedI];
 258             ownIndices[ownI] = sorted.indices()[sortedI];
 259             ownI++;
 260         }
 261     }
 262
 263
 264     // Handle trailing send buffer
 265     if (sendI != 0)
 266     {
 267         checkAndSend(sendValues, sendIndices, sendI, destProcI);
 268     }
 269
 270     // Print ownValues
 271     ownValues.setSize(ownI);
 272     ownIndices.setSize(ownI);
 273
 274     if (debug & 2)
 275     {
 276         Pout<< "Not sending (to myself) elements "
 277             << ownValues << endl;
 278     }
 279
 280     //
 281     // 4. Combine pieces from all processors & sort. Use indices() from
 282     // SortableList to remember source processor number.
 283     //
 284
 285     // Allocate receive buffer. Acc. to paper upper bound is 2*n/p
 286     // (n=total size, p=nProcs). Resize later on.
 287     List<taggedValue> combinedValues(2 * n/Pstream::nProcs());
 288
 289     label combinedI = 0;
 290
 291     for (label procI = 0; procI < Pstream::nProcs(); procI++)
 292     {
 293         if (procI == Pstream::myProcNo())
 294         {
 295             if (debug & 2)
 296             {
 297                 Pout<< "Copying from own:" << ownValues << endl;
 298             }
 299
 300             // Copy ownValues,ownIndices into combined buffer
 301             copyInto(ownValues, ownIndices, procI, combinedI, combinedValues);
 302         }
 303         else
 304         {
 305             labelList recValues;
 306             labelList recIndices;
 307
 308             {
 309                 if (debug)
 310                 {
 311                     Pout<< "Receiving from " << procI << endl;
 312                 }
 313
 314                 IPstream fromSlave(procI);
 315
 316                 fromSlave >> recValues >> recIndices;
 317
 318                 if (debug & 2)
 319                 {
 320                     Pout<< "Received from " << procI
 321                         << " elements:" << recValues << endl;
 322                 }
 323             }
 324
 325             if (debug)
 326             {
 327                 Pout<< "Copying starting at:" << combinedI << endl;
 328             }
 329             copyInto(recValues, recIndices, procI, combinedI, combinedValues);
 330         }
 331     }
 332     combinedValues.setSize(combinedI);
 333
 334     // Sort according to values
 335     Foam::sort(combinedValues);
 336
 337     // Copy into *this
 338     this->setSize(combinedI);
 339     indices_.setSize(combinedI);
 340     procs_.setSize(combinedI);
 341
 342     forAll(combinedValues, elemI)
 343     {
 344         this->operator[](elemI) = combinedValues[elemI].value();
 345         indices_[elemI] = combinedValues[elemI].index();
 346         procs_[elemI] = combinedValues[elemI].procID();
 347     }
 348 }
 349
 350
 351 // ************************************************************************* //