main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:07 for Gecode by
doxygen
1.8.4
gecode
search
parallel
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-07-12 18:20:11 +0200 (Fri, 12 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13877 $
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
42
#include <
gecode/search/parallel/bab.hh
>
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
61
BAB::Worker::run
(
void
) {
62
// Peform initial delay, if not first worker
63
if
(
this
!=
engine
().
worker
(0))
64
Support::Thread::sleep
(
Config::initial_delay
);
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
74
engine
().
ack_terminate
();
75
// Wait until termination can proceed
76
engine
().
wait_terminate
();
77
// Terminate thread
78
engine
().
terminated
();
79
return
;
80
case
C_RESET
:
81
// Acknowledge reset request
82
engine
().
ack_reset_start
();
83
// Wait until reset has been performed
84
engine
().
wait_reset
();
85
// Acknowledge that reset cycle is over
86
engine
().
ack_reset_stop
();
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
())) {
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
m
.
release
();
116
break
;
117
case
SS_SOLVED
:
118
{
119
// Deletes all pending branchers
120
(void)
cur
->
choice
();
121
Space
* s =
cur
->
clone
(
false
);
122
delete
cur
;
123
cur
= NULL;
124
m
.
release
();
125
engine
().
solution
(s);
126
}
127
break
;
128
case
SS_BRANCH
:
129
{
130
Space
*
c
;
131
if
((
d
== 0) || (
d
>=
engine
().
opt
().
c_d
)) {
132
c =
cur
->
clone
();
133
d
= 1;
134
}
else
{
135
c = NULL;
136
d
++;
137
}
138
const
Choice
* ch =
path
.
push
(*
this
,
cur
,c);
139
cur
->
commit
(*ch,0);
140
m
.
release
();
141
}
142
break
;
143
default
:
144
GECODE_NEVER
;
145
}
146
}
147
}
else
if
(
path
.
next
()) {
148
cur
=
path
.
recompute
(
d
,
engine
().
opt
().
a_d
,*
this
,
best
,
mark
);
149
m
.
release
();
150
}
else
{
151
idle
=
true
;
152
path
.
ngdl
(0);
153
m
.
release
();
154
// Report that worker is idle
155
engine
().
idle
();
156
}
157
}
158
break
;
159
default
:
160
GECODE_NEVER
;
161
}
162
}
163
}
164
165
166
/*
167
* Perform reset
168
*
169
*/
170
void
171
BAB::reset
(
Space
* s) {
172
// Grab wait lock for reset
173
m_wait_reset
.
acquire
();
174
// Release workers for reset
175
release
(
C_RESET
);
176
// Wait for reset cycle started
177
e_reset_ack_start
.
wait
();
178
// All workers are marked as busy again
179
delete
best
;
180
best
= NULL;
181
n_busy
=
workers
();
182
for
(
unsigned
int
i
=1;
i
<
workers
();
i
++)
183
worker
(
i
)->
reset
(NULL,0);
184
worker
(0)->
reset
(s,
opt
().
nogoods_limit
);
185
// Block workers again to ensure invariant
186
block
();
187
// Release reset lock
188
m_wait_reset
.
release
();
189
// Wait for reset cycle stopped
190
e_reset_ack_stop
.
wait
();
191
}
192
193
194
/*
195
* Create no-goods
196
*
197
*/
198
NoGoods
&
199
BAB::nogoods
(
void
) {
200
NoGoods
* ng;
201
// Grab wait lock for reset
202
m_wait_reset
.
acquire
();
203
// Release workers for reset
204
release
(
C_RESET
);
205
// Wait for reset cycle started
206
e_reset_ack_start
.
wait
();
207
ng = &
worker
(0)->
nogoods
();
208
// Block workers again to ensure invariant
209
block
();
210
// Release reset lock
211
m_wait_reset
.
release
();
212
// Wait for reset cycle stopped
213
e_reset_ack_stop
.
wait
();
214
return
*ng;
215
}
216
217
/*
218
* Termination and deletion
219
*/
220
BAB::Worker::~Worker
(
void
) {
221
delete
best
;
222
}
223
224
BAB::~BAB
(
void
) {
225
terminate
();
226
delete
best
;
227
heap
.
rfree
(
_worker
);
228
}
229
230
}}}
231
232
#endif
233
234
// STATISTICS: search-parallel