dfs.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Search { namespace Par {
/*
* Basic access routines
*/
template<class Tracer>
forceinline DFS<Tracer>&
DFS<Tracer>::Worker::engine(void) const {
return static_cast<DFS<Tracer>&>(_engine);
}
template<class Tracer>
forceinline typename DFS<Tracer>::Worker*
DFS<Tracer>::worker(unsigned int i) const {
return _worker[i];
}
/*
* Engine: initialization
*/
template<class Tracer>
forceinline
DFS<Tracer>::Worker::Worker(Space* s, DFS& e)
: Engine<Tracer>::Worker(s,e) {}
template<class Tracer>
forceinline
DFS<Tracer>::DFS(Space* s, const Options& o)
: Engine<Tracer>(o) {
WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
workers());
// Create workers
_worker = static_cast<Worker**>
(heap.ralloc(workers() * sizeof(Worker*)));
// The first worker gets the entire search tree
_worker[0] = new Worker(s,*this);
// All other workers start with no work
for (unsigned int i=1; i<workers(); i++)
_worker[i] = new Worker(NULL,*this);
// Block all workers
block();
// Create and start threads
for (unsigned int i=0U; i<workers(); i++)
Support::Thread::run(_worker[i]);
}
/*
* Reset
*/
template<class Tracer>
forceinline void
DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
delete cur;
tracer.round();
path.reset((s != NULL) ? ngdl : 0);
d = 0;
idle = false;
if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
delete s;
cur = NULL;
} else {
cur = s;
}
Search::Worker::reset();
}
/*
* Engine: search control
*/
template<class Tracer>
forceinline void
DFS<Tracer>::solution(Space* s) {
m_search.acquire();
bool bs = signal();
solutions.push(s);
if (bs)
e_search.signal();
m_search.release();
}
/*
* Worker: finding and stealing working
*/
template<class Tracer>
forceinline void
DFS<Tracer>::Worker::find(void) {
// Try to find new work (even if there is none)
for (unsigned int i=0U; i<engine().workers(); i++) {
unsigned long int r_d = 0ul;
typename Engine<Tracer>::Worker* wi = engine().worker(i);
if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
// Reset this guy
m.acquire();
idle = false;
// Not idle but also does not have the root of the tree
path.ngdl(0);
d = 0;
cur = s;
Statistics t = *this;
Search::Worker::reset(r_d);
(*this) += t;
m.release();
return;
}
}
}
/*
* Statistics
*/
template<class Tracer>
Statistics
DFS<Tracer>::statistics(void) const {
Statistics s;
for (unsigned int i=0U; i<workers(); i++)
s += worker(i)->statistics();
return s;
}
/*
* Engine: search control
*/
template<class Tracer>
void
DFS<Tracer>::Worker::run(void) {
/*
* The engine maintains the following invariant:
* - If the current space (cur) is not NULL, the path always points
* to exactly that space.
* - If the current space (cur) is NULL, the path always points
* to the next space (if there is any).
*
* This invariant is needed so that no-goods can be extracted properly
* when the engine is stopped or has found a solution.
*
*/
// Peform initial delay, if not first worker
if (this != engine().worker(0))
Support::Thread::sleep(Config::initial_delay);
// Okay, we are in business, start working
while (true) {
switch (engine().cmd()) {
case C_WAIT:
// Wait
engine().wait();
break;
case C_TERMINATE:
// Acknowledge termination request
engine().ack_terminate();
// Wait until termination can proceed
engine().wait_terminate();
// Thread will be terminated by returning from run
return;
case C_RESET:
// Acknowledge reset request
engine().ack_reset_start();
// Wait until reset has been performed
engine().wait_reset();
// Acknowledge that reset cycle is over
engine().ack_reset_stop();
break;
case C_WORK:
// Perform exploration work
{
m.acquire();
if (idle) {
m.release();
// Try to find new work
find();
} else if (cur != NULL) {
start();
if (stop(engine().opt())) {
// Report stop
m.release();
engine().stop();
} else {
node++;
SearchTracer::EdgeInfo ei;
if (tracer) {
if (path.entries() > 0) {
typename Path<Tracer>::Edge& top = path.top();
ei.init(tracer.wid(), top.nid(), top.truealt(),
*cur, *top.choice());
} else if (*tracer.ei()) {
ei = *tracer.ei();
tracer.invalidate();
}
}
unsigned int nid = tracer.nid();
switch (cur->status(*this)) {
case SS_FAILED:
if (tracer) {
SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
tracer.wid(), nid, *cur);
tracer.node(ei,ni);
}
fail++;
delete cur;
cur = NULL;
path.next();
m.release();
break;
case SS_SOLVED:
{
if (tracer) {
SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
tracer.wid(), nid, *cur);
tracer.node(ei,ni);
}
// Deletes all pending branchers
(void) cur->choice();
Space* s = cur->clone();
delete cur;
cur = NULL;
path.next();
m.release();
engine().solution(s);
}
break;
case SS_BRANCH:
{
Space* c;
if ((d == 0) || (d >= engine().opt().c_d)) {
c = cur->clone();
d = 1;
} else {
c = NULL;
d++;
}
const Choice* ch = path.push(*this,cur,c,nid);
if (tracer) {
SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
tracer.wid(), nid, *cur, ch);
tracer.node(ei,ni);
}
cur->commit(*ch,0);
m.release();
}
break;
default:
GECODE_NEVER;
}
}
} else if (!path.empty()) {
cur = path.recompute(d,engine().opt().a_d,*this,tracer);
if (cur == NULL)
path.next();
m.release();
} else {
idle = true;
path.ngdl(0);
m.release();
// Report that worker is idle
engine().idle();
}
}
break;
default:
GECODE_NEVER;
}
}
}
/*
* Perform reset
*
*/
template<class Tracer>
void
DFS<Tracer>::reset(Space* s) {
// Grab wait lock for reset
m_wait_reset.acquire();
// Release workers for reset
release(C_RESET);
// Wait for reset cycle started
e_reset_ack_start.wait();
// All workers are marked as busy again
n_busy = workers();
for (unsigned int i=1U; i<workers(); i++)
worker(i)->reset(NULL,0);
worker(0U)->reset(s,opt().nogoods_limit);
// Block workers again to ensure invariant
block();
// Release reset lock
m_wait_reset.release();
// Wait for reset cycle stopped
e_reset_ack_stop.wait();
}
/*
* Create no-goods
*
*/
template<class Tracer>
NoGoods&
DFS<Tracer>::nogoods(void) {
NoGoods* ng;
// Grab wait lock for reset
m_wait_reset.acquire();
// Release workers for reset
release(C_RESET);
// Wait for reset cycle started
e_reset_ack_start.wait();
ng = &worker(0)->nogoods();
// Block workers again to ensure invariant
block();
// Release reset lock
m_wait_reset.release();
// Wait for reset cycle stopped
e_reset_ack_stop.wait();
return *ng;
}
/*
* Termination and deletion
*/
template<class Tracer>
DFS<Tracer>::~DFS(void) {
terminate();
heap.rfree(_worker);
}
}}}
// STATISTICS: search-par
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::NoGoods
No-goods recorded from restarts.
Definition core.hpp:1588
Gecode::SearchTracer::EdgeInfo
Edge information.
Definition search.hh:242
Gecode::SearchTracer::EdgeInfo::init
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
Gecode::SearchTracer::NodeInfo
Node information.
Definition search.hh:282
Gecode::SearchTracer::FAILED
@ FAILED
A solution node.
Definition search.hh:278
Gecode::SearchTracer::BRANCH
@ BRANCH
A failed node.
Definition search.hh:279
Gecode::SearchTracer::SOLVED
@ SOLVED
Definition search.hh:277
Gecode::SearchTracer::DFS
@ DFS
Engine is a DFS engine.
Definition search.hh:194
Gecode::Search::Options
Search engine options
Definition search.hh:746
Gecode::Search::Options::tracer
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:769
Gecode::Search::Par::DFS::Worker
Parallel depth-first search worker
Definition dfs.hh:66
Gecode::Search::Par::DFS::Worker::Worker
Worker(Space *s, DFS &e)
Initialize for space s with engine e.
Definition dfs.hpp:56
Gecode::Search::Par::DFS::Worker::find
void find(void)
Try to find some work.
Definition dfs.hpp:122
Gecode::Search::Par::DFS::Worker::reset
void reset(Space *s, unsigned int ngdl)
Reset worker to restart at space s.
Definition dfs.hpp:85
Gecode::Search::Par::DFS::Worker::engine
DFS & engine(void) const
Provide access to engine.
Definition dfs.hpp:41
Gecode::Search::Par::DFS::Worker::run
virtual void run(void)
Start execution of worker.
Definition dfs.hpp:162
Gecode::Search::Par::DFS
Parallel depth-first search engine
Definition dfs.hh:43
Gecode::Search::Par::DFS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:149
Gecode::Search::Par::DFS::solution
void solution(Space *s)
Report solution s.
Definition dfs.hpp:106
Gecode::Search::Par::DFS::reset
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition dfs.hpp:308
Gecode::Search::Par::DFS::DFS
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition dfs.hpp:60
Gecode::Search::Par::DFS::worker
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition dfs.hpp:46
Gecode::Search::Par::DFS::_worker
Worker ** _worker
Array of worker references.
Definition dfs.hh:91
Gecode::Search::Par::DFS::nogoods
virtual NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:336
Gecode::Search::Par::DFS::~DFS
virtual ~DFS(void)
Destructor.
Definition dfs.hpp:359
Gecode::Search::Par::Engine::Worker
Parallel depth-first search worker
Definition engine.hh:49
Gecode::Search::Par::Engine::Worker::m
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:57
Gecode::Search::Par::Engine::Worker::_engine
Engine & _engine
Reference to engine.
Definition engine.hh:55
Gecode::Search::Par::Engine::Worker::nogoods
NoGoods & nogoods(void)
Return no-goods.
Definition engine.hpp:289
Gecode::Search::Par::Engine::Worker::statistics
Statistics statistics(void)
Return statistics.
Definition engine.hpp:134
Gecode::Search::Par::Engine::Worker::cur
Space * cur
Current space being explored.
Definition engine.hh:61
Gecode::Search::Par::Engine::Worker::tracer
Tracer tracer
Search tracer.
Definition engine.hh:52
Gecode::Search::Par::Engine::Worker::steal
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available).
Definition engine.hpp:265
Gecode::Search::Par::Engine::Worker::d
unsigned int d
Distance until next clone.
Definition engine.hh:63
Gecode::Search::Par::Engine::Worker::idle
bool idle
Whether the worker is idle.
Definition engine.hh:65
Gecode::Search::Par::Engine::Worker::path
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:59
Gecode::Search::Par::Engine::opt
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Gecode::Search::Par::Engine::e_reset_ack_stop
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Gecode::Search::Par::Engine::e_search
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Definition engine.hh:169
Gecode::Search::Par::Engine::solutions
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
Gecode::Search::Par::Engine::stop
void stop(void)
Report that worker has been stopped.
Definition engine.hpp:172
Gecode::Search::Par::Engine::block
void block(void)
Block all workers.
Definition engine.hpp:73
Gecode::Search::Par::Engine::m_wait_reset
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:153
Gecode::Search::Par::Engine::m_search
Support::Mutex m_search
Mutex for search.
Definition engine.hh:167
Gecode::Search::Par::Engine::e_reset_ack_start
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:149
Gecode::Search::Par::Engine::cmd
Cmd cmd(void) const
Return current command.
Definition engine.hpp:68
Gecode::Search::Par::Engine::Engine
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
Gecode::Search::Par::Engine::release
void release(Cmd c)
Release all workers.
Definition engine.hpp:79
Gecode::Search::Par::Engine::signal
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:147
Gecode::Search::Par::Engine::terminate
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
Gecode::Search::Par::Engine::n_busy
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
Gecode::Search::Par::Engine::workers
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
Gecode::Search::Par::Engine::C_WORK
@ C_WORK
Perform work.
Definition engine.hh:94
Gecode::Search::Par::Engine::C_RESET
@ C_RESET
Perform reset operation.
Definition engine.hh:96
Gecode::Search::Par::Engine::C_WAIT
@ C_WAIT
Run into wait lock.
Definition engine.hh:95
Gecode::Search::Par::Engine::C_TERMINATE
@ C_TERMINATE
Terminate.
Definition engine.hh:97
Gecode::Search::Par::Path::Edge
Search tree edge for recomputation
Definition path.hh:66
Gecode::Search::Par::Path::Edge::truealt
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:76
Gecode::Search::Par::Path::Edge::nid
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
Gecode::Search::Par::Path::Edge::choice
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Gecode::Search::Statistics
Search engine statistics
Definition search.hh:147
Gecode::Search::Statistics::Statistics
Statistics(void)
Initialize.
Definition statistics.hpp:45
Gecode::Search::Statistics::fail
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Gecode::Search::Statistics::node
unsigned long int node
Number of nodes expanded.
Definition search.hh:152
Gecode::Search::Worker::start
void start(void)
Reset stop information.
Definition worker.hh:74
Gecode::Search::Worker::Worker
Worker(void)
Initialize.
Definition worker.hh:70
Gecode::Search::WrapTraceRecorder::engine
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Definition trace-recorder.hpp:152
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::StatusStatistics::reset
void reset(void)
Reset information.
Definition core.hpp:4690
Gecode::Support::Thread::run
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
Gecode::Support::Thread::sleep
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition none.hpp:74
Gecode::Tracer
Tracer.
Definition tracer.hpp:149
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::SS_BRANCH
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
Gecode::SS_SOLVED
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Search::Config::initial_delay
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:120
Gecode::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56