main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:40 for Gecode by
doxygen
1.8.3.1
gecode
search
parallel
bab.hh
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
#ifndef __GECODE_SEARCH_PARALLEL_BAB_HH__
39
#define __GECODE_SEARCH_PARALLEL_BAB_HH__
40
41
#include <
gecode/search/parallel/engine.hh
>
42
43
namespace
Gecode {
namespace
Search {
namespace
Parallel {
44
46
class
BAB
:
public
Engine
{
47
protected
:
49
class
Worker
:
public
Engine::Worker
{
50
protected
:
52
int
mark
;
54
Space
*
best
;
55
public
:
57
Worker
(
Space
* s,
size_t
sz,
BAB
& e);
59
BAB
&
engine
(
void
)
const
;
61
virtual
void
run
(
void
);
63
void
better
(
Space
*
b
);
65
void
find
(
void
);
67
void
reset
(
Space
* s);
69
virtual
~Worker
(
void
);
70
};
72
Worker
**
_worker
;
74
Space
*
best
;
75
public
:
77
Worker
*
worker
(
unsigned
int
i
)
const
;
78
80
81
82
void
solution
(
Space
* s);
84
86
87
88
BAB
(
Space
* s,
size_t
sz,
const
Options
& o);
90
virtual
Statistics
statistics
(
void
)
const
;
92
virtual
void
reset
(
Space
* s);
94
virtual
~BAB
(
void
);
96
};
97
98
99
100
/*
101
* Engine: basic access routines
102
*/
103
forceinline
BAB
&
104
BAB::Worker::engine
(
void
)
const
{
105
return
static_cast<
BAB
&
>
(
_engine
);
106
}
107
forceinline
BAB::Worker
*
108
BAB::worker
(
unsigned
int
i
)
const
{
109
return
_worker
[
i
];
110
}
111
112
forceinline
void
113
BAB::Worker::reset
(
Space
* s) {
114
delete
cur;
115
delete
best
;
116
best
= NULL;
117
path
.reset();
118
d
=
mark
= 0;
119
idle
=
false
;
120
if
((s == NULL) || (s->
status
(*
this
) ==
SS_FAILED
)) {
121
delete
s;
122
cur = NULL;
123
Search::Worker::reset
();
124
}
else
{
125
cur = s;
126
Search::Worker::reset
(cur);
127
}
128
}
129
130
131
/*
132
* Engine: initialization
133
*/
134
forceinline
135
BAB::Worker::Worker
(
Space
* s,
size_t
sz,
BAB
& e)
136
:
Engine
::
Worker
(s,sz,e),
mark
(0),
best
(NULL) {}
137
138
forceinline
139
BAB::BAB
(
Space
* s,
size_t
sz,
const
Options
& o)
140
:
Engine
(o),
best
(NULL) {
141
// Create workers
142
_worker
=
static_cast<
Worker
**
>
143
(
heap
.
ralloc
(
workers
() *
sizeof
(
Worker
*)));
144
// The first worker gets the entire search tree
145
_worker
[0] =
new
Worker
(s,sz,*
this
);
146
// All other workers start with no work
147
for
(
unsigned
int
i
=1;
i
<
workers
();
i
++)
148
_worker
[
i
] =
new
Worker
(NULL,sz,*
this
);
149
// Block all workers
150
block
();
151
// Create and start threads
152
for
(
unsigned
int
i
=0;
i
<
workers
();
i
++)
153
Support::Thread::run
(
_worker
[
i
]);
154
}
155
156
157
/*
158
* Engine: search control
159
*/
160
forceinline
void
161
BAB::Worker::better
(
Space
*
b
) {
162
m
.
acquire
();
163
delete
best
;
164
best
= b->
clone
(
false
);
165
mark
=
path
.
entries
();
166
if
(
cur
!= NULL)
167
cur
->
constrain
(*
best
);
168
m
.
release
();
169
}
170
forceinline
void
171
BAB::solution
(
Space
* s) {
172
m_search
.
acquire
();
173
if
(
best
!= NULL) {
174
s->
constrain
(*
best
);
175
if
(s->
status
() ==
SS_FAILED
) {
176
delete
s;
177
m_search
.
release
();
178
return
;
179
}
else
{
180
delete
best
;
181
best
= s->
clone
();
182
}
183
}
else
{
184
best
= s->
clone
();
185
}
186
// Announce better solutions
187
for
(
unsigned
int
i
=0;
i
<
workers
();
i
++)
188
worker
(
i
)->
better
(
best
);
189
bool
bs =
signal
();
190
solutions
.push(s);
191
if
(bs)
192
e_search
.
signal
();
193
m_search
.
release
();
194
}
195
196
197
/*
198
* Worker: finding and stealing working
199
*/
200
forceinline
void
201
BAB::Worker::find
(
void
) {
202
// Try to find new work (even if there is none)
203
for
(
unsigned
int
i
=0;
i
<engine().workers();
i
++) {
204
unsigned
long
int
r_d = 0ul;
205
if
(
Space
* s = engine().worker(
i
)->steal(r_d)) {
206
// Reset this guy
207
m.acquire();
208
idle
=
false
;
209
d
= 0;
210
cur = s;
211
mark
= 0;
212
if
(
best
!= NULL)
213
cur->constrain(*
best
);
214
Search::Worker::reset
(cur,r_d);
215
m.release();
216
return
;
217
}
218
}
219
}
220
221
}}}
222
223
#endif
224
225
// STATISTICS: search-parallel