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