main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11
* $Revision: 14967 $
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,
unsigned
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,
unsigned
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
Gecode::Search::Parallel::Engine::idle
void idle(void)
Report that worker is idle.
Definition:
engine.hh:298
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::Search::Options
Search engine options
Definition:
search.hh:446
Gecode::Support::Mutex::acquire
void acquire(void)
Acquire the mutex and possibly block.
Definition:
none.hpp:46
Gecode::Search::Parallel::DFS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition:
dfs.cpp:50
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Heap::ralloc
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition:
heap.hpp:361
Gecode::Search::Parallel::DFS::Worker
Parallel depth-first search worker
Definition:
dfs.hh:49
Gecode::Search::Parallel::Engine::Worker::path
Path path
Current path ins search tree.
Definition:
engine.hh:59
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Search::Parallel::Engine
Parallel depth-first search engine
Definition:
engine.hh:49
Gecode::Search::Parallel::DFS::Worker::run
virtual void run(void)
Start execution of worker.
Definition:
dfs.cpp:62
Gecode::Search::Parallel::Engine::Worker::cur
Space * cur
Current space being explored.
Definition:
engine.hh:61
Gecode
Gecode toplevel namespace
engine.hh
Gecode::NoGoods
No-goods recorded from restarts.
Definition:
core.hpp:1595
Gecode::Search::Parallel::Engine::block
void block(void)
Block all workers.
Definition:
engine.hh:227
Gecode::Search::Worker::Worker
Worker(void)
Initialize.
Definition:
worker.hh:74
Gecode::Search::Parallel::DFS::nogoods
virtual NoGoods & nogoods(void)
Return no-goods.
Definition:
dfs.cpp:208
Gecode::Search::Parallel::DFS
Parallel depth-first search engine
Definition:
dfs.hh:46
Gecode::Search::Parallel::DFS::DFS
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition:
dfs.hh:110
Gecode::Support::Thread::run
static void run(Runnable *r)
Construct a new thread and run r.
Definition:
thread.hpp:120
Gecode::Search::Parallel::DFS::reset
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition:
dfs.cpp:181
Gecode::Search::Parallel::Path::reset
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition:
path.hh:309
Gecode::Search::Parallel::DFS::Worker::find
void find(void)
Try to find some work.
Definition:
dfs.hh:165
Gecode::Search::Parallel::Engine::signal
bool signal(void) const
Whether search state changed such that signal is needed.
Definition:
engine.hh:294
Gecode::Search::Parallel::Engine::Worker::idle
bool idle
Whether the worker is idle.
Definition:
engine.hh:65
Gecode::Search::Parallel::Engine::e_search
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition:
engine.hh:167
Gecode::Search::Parallel::Engine::Worker::d
unsigned int d
Distance until next clone.
Definition:
engine.hh:63
Gecode::Search::Parallel::Engine::Worker::_engine
Engine & _engine
Reference to engine.
Definition:
engine.hh:55
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition:
core.cpp:224
Gecode::heap
Heap heap
The single global heap.
Definition:
heap.cpp:48
Gecode::Search::Meta::Sequential::engine
Engine * engine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, const Search::Options &opt, bool best)
Create sequential portfolio engine.
Definition:
pbs.cpp:48
Gecode::Support::Event::signal
void signal(void)
Signal the event.
Definition:
none.hpp:63
Gecode::Search::Parallel::DFS::solution
void solution(Space *s)
Report solution s.
Definition:
dfs.hh:150
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::Search::Parallel::Engine::Worker
Parallel depth-first search worker
Definition:
engine.hh:52
Gecode::Search::Parallel::DFS::Worker::engine
DFS & engine(void) const
Provide access to engine.
Definition:
dfs.hh:94
Gecode::Search::Parallel::Engine::solutions
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition:
engine.hh:169
Gecode::path
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition:
circuit.cpp:128
Gecode::Search::Parallel::DFS::_worker
Worker ** _worker
Array of worker references.
Definition:
dfs.hh:63
Gecode::Search::Statistics::reset
void reset(void)
Reset.
Definition:
statistics.hpp:43
Gecode::Search::Parallel::Engine::m_search
Support::Mutex m_search
Mutex for search.
Definition:
engine.hh:165
Gecode::Search::Parallel::DFS::worker
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition:
dfs.hh:98
Gecode::Support::Mutex::release
void release(void)
Release the mutex.
Definition:
none.hpp:52
Gecode::Search::Parallel::Engine::workers
unsigned int workers(void) const
Return number of workers.
Definition:
engine.hh:209
Gecode::Search::Parallel::DFS::~DFS
virtual ~DFS(void)
Destructor.
Definition:
dfs.cpp:230
Gecode::Search::Statistics
Search engine statistics
Definition:
search.hh:140
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition:
core.hpp:1689