main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:30 for Gecode by
doxygen
1.8.4
gecode
search
parallel
dfs.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-10-24 16:42:20 +0200 (Thu, 24 Oct 2013) $ by $Author: schulte $
11
* $Revision: 14030 $
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/dfs.hh
>
43
44
namespace
Gecode {
namespace
Search {
namespace
Parallel {
45
46
/*
47
* Statistics
48
*/
49
Statistics
50
DFS::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
/*
59
* Engine: search control
60
*/
61
void
62
DFS::Worker::run
(
void
) {
63
// Peform initial delay, if not first worker
64
if
(
this
!=
engine
().
worker
(0))
65
Support::Thread::sleep
(
Config::initial_delay
);
66
// Okay, we are in business, start working
67
while
(
true
) {
68
switch
(
engine
().
cmd
()) {
69
case
C_WAIT
:
70
// Wait
71
engine
().
wait
();
72
break
;
73
case
C_TERMINATE
:
74
// Acknowledge termination request
75
engine
().
ack_terminate
();
76
// Wait until termination can proceed
77
engine
().
wait_terminate
();
78
// Terminate thread
79
engine
().
terminated
();
80
return
;
81
case
C_RESET
:
82
// Acknowledge reset request
83
engine
().
ack_reset_start
();
84
// Wait until reset has been performed
85
engine
().
wait_reset
();
86
// Acknowledge that reset cycle is over
87
engine
().
ack_reset_stop
();
88
break
;
89
case
C_WORK
:
90
// Perform exploration work
91
{
92
m
.
acquire
();
93
if
(
idle
) {
94
m
.
release
();
95
// Try to find new work
96
find
();
97
}
else
if
(
cur
!= NULL) {
98
start
();
99
if
(
stop
(
engine
().
opt
())) {
100
// Report stop
101
m
.
release
();
102
engine
().
stop
();
103
}
else
{
104
node
++;
105
switch
(
cur
->
status
(*
this
)) {
106
case
SS_FAILED
:
107
fail
++;
108
delete
cur
;
109
cur
= NULL;
110
m
.
release
();
111
break
;
112
case
SS_SOLVED
:
113
{
114
// Deletes all pending branchers
115
(void)
cur
->
choice
();
116
Space
* s =
cur
->
clone
(
false
);
117
delete
cur
;
118
cur
= NULL;
119
m
.
release
();
120
engine
().
solution
(s);
121
}
122
break
;
123
case
SS_BRANCH
:
124
{
125
Space
*
c
;
126
if
((
d
== 0) || (
d
>=
engine
().
opt
().
c_d
)) {
127
c =
cur
->
clone
();
128
d
= 1;
129
}
else
{
130
c = NULL;
131
d
++;
132
}
133
const
Choice
* ch =
path
.
push
(*
this
,
cur
,c);
134
cur
->
commit
(*ch,0);
135
m
.
release
();
136
}
137
break
;
138
default
:
139
GECODE_NEVER
;
140
}
141
}
142
}
else
if
(
path
.
next
()) {
143
cur
=
path
.
recompute
(
d
,
engine
().
opt
().
a_d
,*
this
);
144
m
.
release
();
145
}
else
{
146
idle
=
true
;
147
path
.
ngdl
(0);
148
m
.
release
();
149
// Report that worker is idle
150
engine
().
idle
();
151
}
152
}
153
break
;
154
default
:
155
GECODE_NEVER
;
156
}
157
}
158
}
159
160
161
/*
162
* Perform reset
163
*
164
*/
165
void
166
DFS::reset
(
Space
* s) {
167
// Grab wait lock for reset
168
m_wait_reset
.
acquire
();
169
// Release workers for reset
170
release
(
C_RESET
);
171
// Wait for reset cycle started
172
e_reset_ack_start
.
wait
();
173
// All workers are marked as busy again
174
n_busy
=
workers
();
175
for
(
unsigned
int
i
=1U;
i
<
workers
();
i
++)
176
worker
(
i
)->
reset
(NULL,0);
177
worker
(0U)->
reset
(s,
opt
().
nogoods_limit
);
178
// Block workers again to ensure invariant
179
block
();
180
// Release reset lock
181
m_wait_reset
.
release
();
182
// Wait for reset cycle stopped
183
e_reset_ack_stop
.
wait
();
184
}
185
186
187
188
/*
189
* Create no-goods
190
*
191
*/
192
NoGoods
&
193
DFS::nogoods
(
void
) {
194
NoGoods
* ng;
195
// Grab wait lock for reset
196
m_wait_reset
.
acquire
();
197
// Release workers for reset
198
release
(
C_RESET
);
199
// Wait for reset cycle started
200
e_reset_ack_start
.
wait
();
201
ng = &
worker
(0)->
nogoods
();
202
// Block workers again to ensure invariant
203
block
();
204
// Release reset lock
205
m_wait_reset
.
release
();
206
// Wait for reset cycle stopped
207
e_reset_ack_stop
.
wait
();
208
return
*ng;
209
}
210
211
212
/*
213
* Termination and deletion
214
*/
215
DFS::~DFS
(
void
) {
216
terminate
();
217
heap
.
rfree
(
_worker
);
218
}
219
220
}}}
221
222
#endif
223
224
// STATISTICS: search-parallel