FreeFOAM The Cross-Platform CFD Toolkit
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) 1991-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 <OpenFOAM/SortableList.H>
28 #include <OpenFOAM/boolList.H>
29 #include <OpenFOAM/IOstreams.H>
30 #include <OpenFOAM/IOmanip.H>
31 #include <OpenFOAM/OStringStream.H>
32 #include <OpenFOAM/Pstream.H>
33 
34 // * * * * * * * * * * * * * * Static Data Members * * * * * * * * * * * * * //
35 
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
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  {
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 // ************************ vim: set sw=4 sts=4 et: ************************ //