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
dfs.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-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13840 $
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_DFS_HH__
39
#define __GECODE_SEARCH_PARALLEL_DFS_HH__
40
41
#include <
gecode/search/parallel/engine.hh
>
42
43
namespace
Gecode {
namespace
Search {
namespace
Parallel {
44
46
class
DFS
:
public
Engine
{
47
protected
:
49
class
Worker
:
public
Engine::Worker
{
50
public
:
52
Worker
(
Space
* s,
DFS
& e);
54
DFS
&
engine
(
void
)
const
;
56
virtual
void
run
(
void
);
58
void
find
(
void
);
60
void
reset
(
Space
* s,
int
ngdl);
61
};
63
Worker
**
_worker
;
64
public
:
66
Worker
*
worker
(
unsigned
int
i
)
const
;
67
69
70
void
solution
(
Space
* s);
73
75
76
DFS
(
Space
* s,
const
Options
& o);
79
virtual
Statistics
statistics
(
void
)
const
;
81
virtual
void
reset
(
Space
* s);
83
virtual
NoGoods
&
nogoods
(
void
);
85
virtual
~DFS
(
void
);
87
};
88
89
90
/*
91
* Basic access routines
92
*/
93
forceinline
DFS
&
94
DFS::Worker::engine
(
void
)
const
{
95
return
static_cast<
DFS
&
>
(
_engine
);
96
}
97
forceinline
DFS::Worker
*
98
DFS::worker
(
unsigned
int
i
)
const
{
99
return
_worker
[
i
];
100
}
101
102
103
/*
104
* Engine: initialization
105
*/
106
forceinline
107
DFS::Worker::Worker
(
Space
* s,
DFS
& e)
108
:
Engine
::
Worker
(s,e) {}
109
forceinline
110
DFS::DFS
(
Space
* s,
const
Options
& o)
111
:
Engine
(o) {
112
// Create workers
113
_worker
=
static_cast<
Worker
**
>
114
(
heap
.
ralloc
(
workers
() *
sizeof
(
Worker
*)));
115
// The first worker gets the entire search tree
116
_worker
[0] =
new
Worker
(s,*
this
);
117
// All other workers start with no work
118
for
(
unsigned
int
i
=1;
i
<
workers
();
i
++)
119
_worker
[
i
] =
new
Worker
(NULL,*
this
);
120
// Block all workers
121
block
();
122
// Create and start threads
123
for
(
unsigned
int
i
=0;
i
<
workers
();
i
++)
124
Support::Thread::run
(
_worker
[
i
]);
125
}
126
127
/*
128
* Reset
129
*/
130
forceinline
void
131
DFS::Worker::reset
(
Space
* s,
int
ngdl) {
132
delete
cur
;
133
path
.
reset
((s != NULL) ? ngdl : 0);
134
d
= 0;
135
idle
=
false
;
136
if
((s == NULL) || (s->
status
(*
this
) ==
SS_FAILED
)) {
137
delete
s;
138
cur
= NULL;
139
}
else
{
140
cur
= s;
141
}
142
Search::Worker::reset
();
143
}
144
145
146
/*
147
* Engine: search control
148
*/
149
forceinline
void
150
DFS::solution
(
Space
* s) {
151
m_search
.
acquire
();
152
bool
bs =
signal
();
153
solutions
.push(s);
154
if
(bs)
155
e_search
.
signal
();
156
m_search
.
release
();
157
}
158
159
160
161
/*
162
* Worker: finding and stealing working
163
*/
164
forceinline
void
165
DFS::Worker::find
(
void
) {
166
// Try to find new work (even if there is none)
167
for
(
unsigned
int
i
=0;
i
<engine().workers();
i
++) {
168
unsigned
long
int
r_d = 0ul;
169
if
(
Space
* s = engine().worker(
i
)->steal(r_d)) {
170
// Reset this guy
171
m.acquire();
172
idle
=
false
;
173
// Not idle but also does not have the root of the tree
174
path
.ngdl(0);
175
d
= 0;
176
cur = s;
177
Search::Worker::reset
(r_d);
178
m.release();
179
return
;
180
}
181
}
182
}
183
184
}}}
185
186
#endif
187
188
// STATISTICS: search-parallel