Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
bab.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * Last modified:
10  * $Date: 2013-03-07 20:56:21 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13463 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/support.hh>
39 
40 #ifdef GECODE_HAS_THREADS
41 
43 
44 namespace Gecode { namespace Search { namespace Parallel {
45 
46  /*
47  * Statistics
48  */
49  Statistics
50  BAB::statistics(void) const {
51  Statistics s;
52  for (unsigned int i=0; i<workers(); i++)
53  s += worker(i)->statistics();
54  return s;
55  }
56 
57  /*
58  * Actual work
59  */
60  void
62  // Peform initial delay, if not first worker
63  if (this != engine().worker(0))
65  // Okay, we are in business, start working
66  while (true) {
67  switch (engine().cmd()) {
68  case C_WAIT:
69  // Wait
70  engine().wait();
71  break;
72  case C_TERMINATE:
73  // Acknowledge termination request
75  // Wait until termination can proceed
77  // Terminate thread
78  engine().terminated();
79  return;
80  case C_RESET:
81  // Acknowledge reset request
83  // Wait until reset has been performed
84  engine().wait_reset();
85  // Acknowledge that reset cycle is over
87  break;
88  case C_WORK:
89  // Perform exploration work
90  {
91  m.acquire();
92  if (idle) {
93  m.release();
94  // Try to find new work
95  find();
96  } else if (cur != NULL) {
97  start();
98  if (stop(engine().opt(),path.size())) {
99  // Report stop
100  m.release();
101  engine().stop();
102  } else {
103  /*
104  * The invariant maintained by the engine is:
105  * For all nodes stored at a depth less than mark, there
106  * is no guarantee of betterness. For those above the mark,
107  * betterness is guaranteed.
108  */
109  node++;
110  switch (cur->status(*this)) {
111  case SS_FAILED:
112  fail++;
113  delete cur;
114  cur = NULL;
115  Worker::current(NULL);
116  m.release();
117  break;
118  case SS_SOLVED:
119  {
120  // Deletes all pending branchers
121  (void) cur->choice();
122  Space* s = cur->clone(false);
123  delete cur;
124  cur = NULL;
125  Worker::current(NULL);
126  m.release();
127  engine().solution(s);
128  }
129  break;
130  case SS_BRANCH:
131  {
132  Space* c;
133  if ((d == 0) || (d >= engine().opt().c_d)) {
134  c = cur->clone();
135  d = 1;
136  } else {
137  c = NULL;
138  d++;
139  }
140  const Choice* ch = path.push(*this,cur,c);
141  Worker::push(c,ch);
142  cur->commit(*ch,0);
143  m.release();
144  }
145  break;
146  default:
147  GECODE_NEVER;
148  }
149  }
150  } else if (path.next(*this)) {
151  cur = path.recompute(d,engine().opt().a_d,*this,best,mark);
153  m.release();
154  } else {
155  idle = true;
156  m.release();
157  // Report that worker is idle
158  engine().idle();
159  }
160  }
161  break;
162  default:
163  GECODE_NEVER;
164  }
165  }
166  }
167 
168 
169  /*
170  * Perform reset
171  *
172  */
173  void
175  // Grab wait lock for reset
177  // Release workers for reset
178  release(C_RESET);
179  // Wait for reset cycle started
181  // All workers are marked as busy again
182  delete best;
183  best = NULL;
184  n_busy = workers();
185  for (unsigned int i=1; i<workers(); i++)
186  worker(i)->reset(NULL);
187  worker(0)->reset(s);
188  // Block workers again to ensure invariant
189  block();
190  // Release reset lock
192  // Wait for reset cycle stopped
194  }
195 
196 
197  /*
198  * Termination and deletion
199  */
201  delete best;
202  }
203 
204  BAB::~BAB(void) {
205  terminate();
206  delete best;
207  heap.rfree(_worker);
208  }
209 
210 }}}
211 
212 #endif
213 
214 // STATISTICS: search-parallel