src/OpenFOAM/meshes/ProcessorTopology/commSchedule.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2004-2010 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
  13     the Free Software Foundation, either version 3 of the License, or
  14     (at your 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, see <http://www.gnu.org/licenses/>.
  23
  24 \*---------------------------------------------------------------------------*/
  25
  26 #include "commSchedule.H"
  27 #include "SortableList.H"
  28 #include "boolList.H"
  29 #include "IOstreams.H"
  30 #include "IOmanip.H"
  31 #include "OStringStream.H"
  32 #include "Pstream.H"
  33
  34 // * * * * * * * * * * * * * * Static Data Members * * * * * * * * * * * * * //
  35
  36 defineTypeNameAndDebug(Foam::commSchedule, 0);
  37
  38
  39 // * * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * //
  40
  41 Foam::label Foam::commSchedule::outstandingComms
  42 (
  43     const labelList& commToSchedule,
  44     DynamicList<label>& procComms
  45 ) const
  46 {
  47     label nOutstanding = 0;
  48
  49     forAll(procComms, i)
  50     {
  51         if (commToSchedule[procComms[i]] == -1)
  52         {
  53             nOutstanding++;
  54         }
  55     }
  56     return nOutstanding;
  57 }
  58
  59
  60 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  61
  62 // Construct from separate addressing
  63 Foam::commSchedule::commSchedule
  64 (
  65     const label nProcs,
  66     const List<labelPair>& comms
  67 )
  68 :
  69     schedule_(comms.size()),
  70     procSchedule_(nProcs)
  71 {
  72     // Determine comms per processor.
  73     List<DynamicList<label> > procToComms(nProcs);
  74
  75     forAll(comms, commI)
  76     {
  77         label proc0 = comms[commI][0];
  78         label proc1 = comms[commI][1];
  79
  80         if (proc0 < 0 || proc0 >= nProcs || proc1 < 0 || proc1 >= nProcs)
  81         {
  82             FatalErrorIn
  83             (
  84                 "commSchedule::commSchedule"
  85                 "(const label, const List<labelPair>&)"
  86             )   << "Illegal processor " << comms[commI] << abort(FatalError);
  87         }
  88
  89         procToComms[proc0].append(commI);
  90         procToComms[proc1].append(commI);
  91     }
  92     // Note: no need to shrink procToComms. Are small.
  93
  94     if (debug && Pstream::master())
  95     {
  96         Pout<< "commSchedule::commSchedule : Wanted communication:" << endl;
  97
  98         forAll(comms, i)
  99         {
 100             const labelPair& twoProcs = comms[i];
 101
 102             Pout<< i << ": "
 103                 << twoProcs[0] << " with " << twoProcs[1] << endl;
 104         }
 105         Pout<< endl;
 106
 107
 108         Pout<< "commSchedule::commSchedule : Schedule:" << endl;
 109
 110         // Print header. Use buffered output to prevent parallel output messing
 111         // up.
 112         {
 113             OStringStream os;
 114             os  << "iter|";
 115             for (int i = 0; i < nProcs; i++)
 116             {
 117                 os  << setw(3) << i;
 118             }
 119             Pout<< os.str().c_str() << endl;
 120         }
 121         {
 122             OStringStream os;
 123             os  << "----+";
 124             for (int i = 0; i < nProcs; i++)
 125             {
 126                 os  << "---";
 127             }
 128             Pout<< os.str().c_str() << endl;
 129         }
 130     }
 131
 132     // Schedule all. Note: crap scheduler. Assumes all communication takes
 133     // equally long.
 134
 135     label nScheduled = 0;
 136
 137     label iter = 0;
 138
 139     // Per index into comms the time when it was scheduled
 140     labelList commToSchedule(comms.size(), -1);
 141
 142     while (nScheduled < comms.size())
 143     {
 144         label oldNScheduled = nScheduled;
 145
 146         // Find unscheduled comms. This is the comms where the two processors
 147         // still have the most unscheduled comms.
 148
 149         boolList busy(nProcs, false);
 150
 151         while (true)
 152         {
 153             label maxCommI = -1;
 154             label maxNeed = labelMin;
 155
 156             forAll(comms, commI)
 157             {
 158                 label proc0 = comms[commI][0];
 159                 label proc1 = comms[commI][1];
 160
 161                 if
 162                 (
 163                     commToSchedule[commI] == -1             // unscheduled
 164                 && !busy[proc0]
 165                 && !busy[proc1]
 166                 )
 167                 {
 168                     label need =
 169                         outstandingComms(commToSchedule, procToComms[proc0])
 170                       + outstandingComms(commToSchedule, procToComms[proc1]);
 171
 172                     if (need > maxNeed)
 173                     {
 174                         maxNeed = need;
 175                         maxCommI = commI;
 176                     }
 177                 }
 178             }
 179
 180
 181             if (maxCommI == -1)
 182             {
 183                 // Found no unscheduled procs.
 184                 break;
 185             }
 186
 187             // Schedule commI in this iteration
 188             commToSchedule[maxCommI] = nScheduled++;
 189             busy[comms[maxCommI][0]] = true;
 190             busy[comms[maxCommI][1]] = true;
 191         }
 192
 193         if (debug && Pstream::master())
 194         {
 195             label nIterComms = nScheduled-oldNScheduled;
 196
 197             if (nIterComms > 0)
 198             {
 199                 labelList procToComm(nProcs, -1);
 200
 201                 forAll(commToSchedule, commI)
 202                 {
 203                     label sched = commToSchedule[commI];
 204
 205                     if (sched >= oldNScheduled && sched < nScheduled)
 206                     {
 207                         label proc0 = comms[commI][0];
 208                         procToComm[proc0] = commI;
 209                         label proc1 = comms[commI][1];
 210                         procToComm[proc1] = commI;
 211                     }
 212                 }
 213
 214                 // Print it
 215                 OStringStream os;
 216                 os  << setw(3) << iter << " |";
 217                 forAll(procToComm, procI)
 218                 {
 219                     if (procToComm[procI] == -1)
 220                     {
 221                         os  << "   ";
 222                     }
 223                     else
 224                     {
 225                         os  << setw(3) << procToComm[procI];
 226                     }
 227                 }
 228                 Pout<< os.str().c_str() << endl;
 229             }
 230         }
 231
 232         iter++;
 233     }
 234
 235     if (debug && Pstream::master())
 236     {
 237         Pout<< endl;
 238     }
 239
 240
 241     // Sort commToSchedule and obtain order in comms
 242     schedule_ = SortableList<label>(commToSchedule).indices();
 243
 244     // Sort schedule_ by processor
 245
 246     labelList nProcScheduled(nProcs, 0);
 247
 248     // Count
 249     forAll(schedule_, i)
 250     {
 251         label commI = schedule_[i];
 252         const labelPair& twoProcs = comms[commI];
 253
 254         nProcScheduled[twoProcs[0]]++;
 255         nProcScheduled[twoProcs[1]]++;
 256     }
 257     // Allocate
 258     forAll(procSchedule_, procI)
 259     {
 260         procSchedule_[procI].setSize(nProcScheduled[procI]);
 261     }
 262     nProcScheduled = 0;
 263     // Fill
 264     forAll(schedule_, i)
 265     {
 266         label commI = schedule_[i];
 267         const labelPair& twoProcs = comms[commI];
 268
 269         label proc0 = twoProcs[0];
 270         procSchedule_[proc0][nProcScheduled[proc0]++] = commI;
 271
 272         label proc1 = twoProcs[1];
 273         procSchedule_[proc1][nProcScheduled[proc1]++] = commI;
 274     }
 275
 276     if (debug && Pstream::master())
 277     {
 278         Pout<< "commSchedule::commSchedule : Per processor:" << endl;
 279
 280         forAll(procSchedule_, procI)
 281         {
 282             const labelList& procComms = procSchedule_[procI];
 283
 284             Pout<< "Processor " << procI << " talks to processors:" << endl;
 285
 286             forAll(procComms, i)
 287             {
 288                 const labelPair& twoProcs = comms[procComms[i]];
 289
 290                 label nbr = (twoProcs[1] == procI ? twoProcs[0] : twoProcs[1]);
 291
 292                 Pout<< "    " << nbr << endl;
 293             }
 294         }
 295         Pout<< endl;
 296     }
 297 }
 298
 299
 300 // ************************************************************************* //