commSchedule.C
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | Copyright (C) 2011-2016 OpenFOAM Foundation
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 namespace Foam
37 {
38  defineTypeNameAndDebug(commSchedule, 0);
39 }
40 
41 
42 // * * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * //
43 
44 Foam::label Foam::commSchedule::outstandingComms
45 (
46  const labelList& commToSchedule,
47  DynamicList<label>& procComms
48 ) const
49 {
50  label nOutstanding = 0;
51 
52  forAll(procComms, i)
53  {
54  if (commToSchedule[procComms[i]] == -1)
55  {
56  nOutstanding++;
57  }
58  }
59  return nOutstanding;
60 }
61 
62 
63 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
64 
66 (
67  const label nProcs,
68  const List<labelPair>& comms
69 )
70 :
71  schedule_(comms.size()),
72  procSchedule_(nProcs)
73 {
74  // Determine comms per processor.
75  List<DynamicList<label>> procToComms(nProcs);
76 
77  forAll(comms, commI)
78  {
79  label proc0 = comms[commI][0];
80  label proc1 = comms[commI][1];
81 
82  if (proc0 < 0 || proc0 >= nProcs || proc1 < 0 || proc1 >= nProcs)
83  {
85  << "Illegal processor " << comms[commI] << abort(FatalError);
86  }
87 
88  procToComms[proc0].append(commI);
89  procToComms[proc1].append(commI);
90  }
91  // Note: no need to shrink procToComms. Are small.
92 
93  if (debug && Pstream::master())
94  {
95  Pout<< "commSchedule::commSchedule : Wanted communication:" << endl;
96 
97  forAll(comms, i)
98  {
99  const labelPair& twoProcs = comms[i];
100 
101  Pout<< i << ": "
102  << twoProcs[0] << " with " << twoProcs[1] << endl;
103  }
104  Pout<< endl;
105 
106 
107  Pout<< "commSchedule::commSchedule : Schedule:" << endl;
108 
109  // Print header. Use buffered output to prevent parallel output messing
110  // up.
111  {
112  OStringStream os;
113  os << "iter|";
114  for (int i = 0; i < nProcs; i++)
115  {
116  os << setw(3) << i;
117  }
118  Pout<< os.str().c_str() << endl;
119  }
120  {
121  OStringStream os;
122  os << "----+";
123  for (int i = 0; i < nProcs; i++)
124  {
125  os << "---";
126  }
127  Pout<< os.str().c_str() << endl;
128  }
129  }
130 
131  // Schedule all. Note: crap scheduler. Assumes all communication takes
132  // equally long.
133 
134  label nScheduled = 0;
135 
136  label iter = 0;
137 
138  // Per index into comms the time when it was scheduled
139  labelList commToSchedule(comms.size(), -1);
140 
141  while (nScheduled < comms.size())
142  {
143  label oldNScheduled = nScheduled;
144 
145  // Find unscheduled comms. This is the comms where the two processors
146  // still have the most unscheduled comms.
147 
148  boolList busy(nProcs, false);
149 
150  while (true)
151  {
152  label maxCommI = -1;
153  label maxNeed = labelMin;
154 
155  forAll(comms, commI)
156  {
157  label proc0 = comms[commI][0];
158  label proc1 = comms[commI][1];
159 
160  if
161  (
162  commToSchedule[commI] == -1 // unscheduled
163  && !busy[proc0]
164  && !busy[proc1]
165  )
166  {
167  label need =
168  outstandingComms(commToSchedule, procToComms[proc0])
169  + outstandingComms(commToSchedule, procToComms[proc1]);
170 
171  if (need > maxNeed)
172  {
173  maxNeed = need;
174  maxCommI = commI;
175  }
176  }
177  }
178 
179 
180  if (maxCommI == -1)
181  {
182  // Found no unscheduled procs.
183  break;
184  }
185 
186  // Schedule commI in this iteration
187  commToSchedule[maxCommI] = nScheduled++;
188  busy[comms[maxCommI][0]] = true;
189  busy[comms[maxCommI][1]] = true;
190  }
191 
192  if (debug && Pstream::master())
193  {
194  label nIterComms = nScheduled-oldNScheduled;
195 
196  if (nIterComms > 0)
197  {
198  labelList procToComm(nProcs, -1);
199 
200  forAll(commToSchedule, commI)
201  {
202  label sched = commToSchedule[commI];
203 
204  if (sched >= oldNScheduled && sched < nScheduled)
205  {
206  label proc0 = comms[commI][0];
207  procToComm[proc0] = commI;
208  label proc1 = comms[commI][1];
209  procToComm[proc1] = commI;
210  }
211  }
212 
213  // Print it
214  OStringStream os;
215  os << setw(3) << iter << " |";
216  forAll(procToComm, proci)
217  {
218  if (procToComm[proci] == -1)
219  {
220  os << " ";
221  }
222  else
223  {
224  os << setw(3) << procToComm[proci];
225  }
226  }
227  Pout<< os.str().c_str() << endl;
228  }
229  }
230 
231  iter++;
232  }
233 
234  if (debug && Pstream::master())
235  {
236  Pout<< endl;
237  }
238 
239 
240  // Sort commToSchedule and obtain order in comms
241  schedule_ = SortableList<label>(commToSchedule).indices();
242 
243  // Sort schedule_ by processor
244 
245  labelList nProcScheduled(nProcs, 0);
246 
247  // Count
248  forAll(schedule_, i)
249  {
250  label commI = schedule_[i];
251  const labelPair& twoProcs = comms[commI];
252 
253  nProcScheduled[twoProcs[0]]++;
254  nProcScheduled[twoProcs[1]]++;
255  }
256  // Allocate
257  forAll(procSchedule_, proci)
258  {
259  procSchedule_[proci].setSize(nProcScheduled[proci]);
260  }
261  nProcScheduled = 0;
262  // Fill
263  forAll(schedule_, i)
264  {
265  label commI = schedule_[i];
266  const labelPair& twoProcs = comms[commI];
267 
268  label proc0 = twoProcs[0];
269  procSchedule_[proc0][nProcScheduled[proc0]++] = commI;
270 
271  label proc1 = twoProcs[1];
272  procSchedule_[proc1][nProcScheduled[proc1]++] = commI;
273  }
274 
275  if (debug && Pstream::master())
276  {
277  Pout<< "commSchedule::commSchedule : Per processor:" << endl;
278 
279  forAll(procSchedule_, proci)
280  {
281  const labelList& procComms = procSchedule_[proci];
282 
283  Pout<< "Processor " << proci << " talks to processors:" << endl;
284 
285  forAll(procComms, i)
286  {
287  const labelPair& twoProcs = comms[procComms[i]];
288 
289  label nbr = (twoProcs[1] == proci ? twoProcs[0] : twoProcs[1]);
290 
291  Pout<< " " << nbr << endl;
292  }
293  }
294  Pout<< endl;
295  }
296 }
297 
298 
299 // ************************************************************************* //
#define forAll(list, i)
Loop across all elements in list.
Definition: UList.H:428
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
error FatalError
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
Definition: error.H:319
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:60
A list that is sorted upon construction or when explicitly requested with the sort() method...
Definition: List.H:73
void size(const label)
Override size to be inconsistent with allocated storage.
Definition: ListI.H:163
Ostream & endl(Ostream &os)
Add newline and flush stream.
Definition: Ostream.H:253
static bool master(const label communicator=0)
Am I the master process.
Definition: UPstream.H:412
commSchedule(const label nProcs, const List< labelPair > &comms)
Construct from wanted communication. Wanted communication is between.
Definition: commSchedule.C:66
Useful combination of include files which define Sin, Sout and Serr and the use of IO streams general...
An ordered pair of two objects of type <T> with first() and second() elements.
Definition: contiguous.H:49
void append(const T &)
Append an element at the end of the list.
Definition: ListI.H:184
List< label > labelList
A List of labels.
Definition: labelList.H:56
errorManip< error > abort(error &err)
Definition: errorManip.H:131
Istream and Ostream manipulators taking arguments.
defineTypeNameAndDebug(combustionModel, 0)
prefixOSstream Pout(cout, "Pout")
Definition: IOstreams.H:53
string str() const
Return the string.
Omanip< int > setw(const int i)
Definition: IOmanip.H:199
Output to memory buffer stream.
Definition: OStringStream.H:49
static const label labelMin
Definition: label.H:61
Namespace for OpenFOAM.