main page
modules
namespaces
classes
files
Gecode home
Generated on Sun Aug 26 2012 08:43:18 for Gecode by
doxygen
1.8.1.1
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: 2011-04-11 19:28:27 +1000 (Mon, 11 Apr 2011) $ by $Author: tack $
11
* $Revision: 11929 $
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,
size_t
sz,
DFS
& e);
54
DFS
&
engine
(
void
)
const
;
56
virtual
void
run
(
void
);
58
void
find
(
void
);
60
Space
*
reset
(
Space
* s);
61
};
63
Worker
**
_worker
;
64
public
:
66
Worker
*
worker
(
unsigned
int
i
)
const
;
67
69
70
71
void
solution
(
Space
* s);
73
Space
*
reset
(
Space
* s);
75
77
78
79
DFS
(
Space
* s,
size_t
sz,
const
Options
& o);
81
virtual
Statistics
statistics
(
void
)
const
;
83
virtual
~DFS
(
void
);
85
};
86
87
88
/*
89
* Basic access routines
90
*/
91
forceinline
DFS
&
92
DFS::Worker::engine
(
void
)
const
{
93
return
static_cast<
DFS
&
>
(
_engine
);
94
}
95
forceinline
DFS::Worker
*
96
DFS::worker
(
unsigned
int
i
)
const
{
97
return
_worker
[
i
];
98
}
99
100
101
/*
102
* Engine: initialization
103
*/
104
forceinline
105
DFS::Worker::Worker
(
Space
* s,
size_t
sz,
DFS
& e)
106
:
Engine
::
Worker
(s,sz,e) {}
107
forceinline
108
DFS::DFS
(
Space
* s,
size_t
sz,
const
Options
& o)
109
:
Engine
(o) {
110
// Create workers
111
_worker
=
static_cast<
Worker
**
>
112
(
heap
.
ralloc
(
workers
() *
sizeof
(
Worker
*)));
113
// The first worker gets the entire search tree
114
_worker
[0] =
new
Worker
(s,sz,*
this
);
115
// All other workers start with no work
116
for
(
unsigned
int
i
=1;
i
<
workers
();
i
++)
117
_worker
[
i
] =
new
Worker
(NULL,sz,*
this
);
118
// Block all workers
119
block
();
120
// Create and start threads
121
for
(
unsigned
int
i
=0;
i
<
workers
();
i
++)
122
Support::Thread::run
(
_worker
[
i
]);
123
}
124
125
/*
126
* Statistics
127
*/
128
forceinline
Space
*
129
DFS::Worker::reset
(
Space
* s) {
130
delete
cur
;
131
path
.
reset
();
132
d
= 0;
133
idle
=
false
;
134
if
((s == NULL) || (s->
status
(*
this
) ==
SS_FAILED
)) {
135
delete
s;
136
cur
= NULL;
137
Search::Worker::reset
();
138
return
NULL;
139
}
else
{
140
cur
= s;
141
Search::Worker::reset
(
cur
);
142
return
s->
clone
(
false
);
143
}
144
}
145
forceinline
Space
*
146
DFS::reset
(
Space
* s) {
147
// All workers are marked as busy again
148
n_busy
=
workers
();
149
for
(
unsigned
int
i
=1;
i
<
workers
();
i
++)
150
(
void
)
worker
(
i
)->
reset
(NULL);
151
return
worker
(0)->
reset
(s);
152
}
153
154
/*
155
* Engine: search control
156
*/
157
forceinline
void
158
DFS::solution
(
Space
* s) {
159
m_search
.
acquire
();
160
bool
bs =
signal
();
161
solutions
.
push
(s);
162
if
(bs)
163
e_search
.
signal
();
164
m_search
.
release
();
165
}
166
167
168
169
170
/*
171
* Worker: finding and stealing working
172
*/
173
forceinline
void
174
DFS::Worker::find
(
void
) {
175
// Try to find new work (even if there is none)
176
for
(
unsigned
int
i
=0;
i
<engine().workers();
i
++) {
177
unsigned
long
int
r_d = 0ul;
178
if
(
Space
* s = engine().worker(
i
)->steal(r_d)) {
179
// Reset this guy
180
m
.acquire();
181
idle
=
false
;
182
d
= 0;
183
cur = s;
184
Search::Worker::reset
(cur,r_d);
185
m
.release();
186
return
;
187
}
188
}
189
}
190
191
}}}
192
193
#endif
194
195
// STATISTICS: search-parallel