engine.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 Engine<Tracer>&
Engine<Tracer>::Worker::engine(void) const {
return _engine;
}
template<class Tracer>
forceinline const Options&
Engine<Tracer>::opt(void) const {
return _opt;
}
template<class Tracer>
forceinline unsigned int
Engine<Tracer>::workers(void) const {
return static_cast<unsigned int>(opt().threads);
}
template<class Tracer>
forceinline bool
Engine<Tracer>::stopped(void) const {
return has_stopped;
}
/*
* Engine: command and wait handling
*/
template<class Tracer>
forceinline typename Engine<Tracer>::Cmd
Engine<Tracer>::cmd(void) const {
return _cmd;
}
template<class Tracer>
forceinline void
Engine<Tracer>::block(void) {
_cmd = C_WAIT;
_m_wait.acquire();
}
template<class Tracer>
forceinline void
Engine<Tracer>::release(Cmd c) {
_cmd = c;
_m_wait.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::wait(void) {
_m_wait.acquire(); _m_wait.release();
}
/*
* Engine: initialization
*/
template<class Tracer>
forceinline
Engine<Tracer>::Worker::Worker(Space* s, Engine& e)
: tracer(e.opt().tracer), _engine(e),
path(s == NULL ? 0 : e.opt().nogoods_limit), d(0),
idle(false) {
tracer.worker();
if (s != NULL) {
if (s->status(*this) == SS_FAILED) {
fail++;
cur = NULL;
if (!engine().opt().clone)
delete s;
} else {
cur = snapshot(s,engine().opt());
}
} else {
cur = NULL;
}
}
template<class Tracer>
forceinline
Engine<Tracer>::Engine(const Options& o)
: _opt(o), solutions(heap) {
// Initialize termination information
_n_term_not_ack = workers();
_n_not_terminated = workers();
// Initialize search information
n_busy = workers();
has_stopped = false;
// Initialize reset information
_n_reset_not_ack = workers();
}
/*
* Statistics
*/
template<class Tracer>
forceinline Statistics
Engine<Tracer>::Worker::statistics(void) {
m.acquire();
Statistics s = *this;
m.release();
return s;
}
/*
* Engine: search control
*/
template<class Tracer>
forceinline bool
Engine<Tracer>::signal(void) const {
return solutions.empty() && (n_busy > 0) && !has_stopped;
}
template<class Tracer>
forceinline void
Engine<Tracer>::idle(void) {
m_search.acquire();
bool bs = signal();
n_busy--;
if (bs && (n_busy == 0))
e_search.signal();
m_search.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::busy(void) {
m_search.acquire();
assert(n_busy > 0);
n_busy++;
m_search.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::stop(void) {
m_search.acquire();
bool bs = signal();
has_stopped = true;
if (bs)
e_search.signal();
m_search.release();
}
/*
* Engine: termination control
*/
template<class Tracer>
forceinline void
Engine<Tracer>::terminated(void) {
unsigned int n;
_m_term.acquire();
n = --_n_not_terminated;
_m_term.release();
// The signal must be outside of the look, otherwise a thread might be
// terminated that still holds a mutex.
if (n == 0)
_e_terminate.signal();
}
template<class Tracer>
forceinline void
Engine<Tracer>::ack_terminate(void) {
_m_term.acquire();
if (--_n_term_not_ack == 0)
_e_term_ack.signal();
_m_term.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::wait_terminate(void) {
_m_wait_terminate.acquire();
_m_wait_terminate.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::terminate(void) {
// Grab the wait mutex for termination
_m_wait_terminate.acquire();
// Release all threads
release(C_TERMINATE);
// Wait until all threads have acknowledged termination request
_e_term_ack.wait();
// Release waiting threads
_m_wait_terminate.release();
// Wait until all threads have in fact terminated
_e_terminate.wait();
// Now all threads are terminated!
}
/*
* Engine: reset control
*/
template<class Tracer>
forceinline void
Engine<Tracer>::ack_reset_start(void) {
_m_reset.acquire();
if (--_n_reset_not_ack == 0)
e_reset_ack_start.signal();
_m_reset.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::ack_reset_stop(void) {
_m_reset.acquire();
if (++_n_reset_not_ack == workers())
e_reset_ack_stop.signal();
_m_reset.release();
}
template<class Tracer>
forceinline void
Engine<Tracer>::wait_reset(void) {
m_wait_reset.acquire();
m_wait_reset.release();
}
/*
* Worker: finding and stealing working
*/
template<class Tracer>
forceinline Space*
Engine<Tracer>::Worker::steal(unsigned long int& d,
Tracer& myt, Tracer& ot) {
/*
* Make a quick check whether the worker might have work
*
* If that is not true any longer, the worker will be asked
* again eventually.
*/
if (!path.steal())
return NULL;
m.acquire();
Space* s = path.steal(*this,d,myt,ot);
m.release();
// Tell that there will be one more busy worker
if (s != NULL)
engine().busy();
return s;
}
/*
* Return No-Goods
*/
template<class Tracer>
forceinline NoGoods&
Engine<Tracer>::Worker::nogoods(void) {
return path;
}
/*
* Engine: search control
*/
template<class Tracer>
Space*
Engine<Tracer>::next(void) {
// Invariant: the worker holds the wait mutex
m_search.acquire();
if (!solutions.empty()) {
// No search needs to be done, take leftover solution
Space* s = solutions.pop();
m_search.release();
return s;
}
// We ignore stopped (it will be reported again if needed)
has_stopped = false;
// No more solutions?
if (n_busy == 0) {
m_search.release();
return NULL;
}
m_search.release();
// Okay, now search has to continue, make the guys work
release(C_WORK);
/*
* Wait until a search related event has happened. It might be that
* the event has already been signalled in the last run, but the
* solution has been removed. So we have to try until there has
* something new happened.
*/
while (true) {
e_search.wait();
m_search.acquire();
if (!solutions.empty()) {
// Report solution
Space* s = solutions.pop();
m_search.release();
// Make workers wait again
block();
return s;
}
// No more solutions or stopped?
if ((n_busy == 0) || has_stopped) {
m_search.release();
// Make workers wait again
block();
return NULL;
}
m_search.release();
}
GECODE_NEVER;
return NULL;
}
template<class Tracer>
Support::Terminator*
Engine<Tracer>::Worker::terminator(void) const {
return &_engine;
}
/*
* Termination and deletion
*/
template<class Tracer>
Engine<Tracer>::Worker::~Worker(void) {
delete cur;
path.reset(0);
tracer.done();
}
}}}
// STATISTICS: search-par
Gecode::NoGoods
No-goods recorded from restarts.
Definition core.hpp:1588
Gecode::Search::Options
Search engine options
Definition search.hh:746
Gecode::Search::Options::threads
double threads
Number of threads to use.
Definition search.hh:751
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::~Worker
virtual ~Worker(void)
Destructor.
Definition engine.hpp:358
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::Worker::terminator
virtual Support::Terminator * terminator(void) const
Terminator (engine).
Definition engine.hpp:350
Gecode::Search::Par::Engine::Worker::engine
Engine & engine(void) const
Provide access to engine.
Definition engine.hpp:42
Gecode::Search::Par::Engine
Parallel depth-first search engine
Definition engine.hh:46
Gecode::Search::Par::Engine::idle
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
Gecode::Search::Par::Engine::wait
void wait(void)
Ensure that worker waits.
Definition engine.hpp:85
Gecode::Search::Par::Engine::_e_terminate
Support::Event _e_terminate
Event for termination (all threads have terminated).
Definition engine.hh:129
Gecode::Search::Par::Engine::ack_reset_stop
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition engine.hpp:244
Gecode::Search::Par::Engine::opt
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Gecode::Search::Par::Engine::_m_wait_terminate
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition engine.hh:125
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::_m_wait
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition engine.hh:103
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::has_stopped
volatile bool has_stopped
Whether a worker had been stopped.
Definition engine.hh:175
Gecode::Search::Par::Engine::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped).
Definition engine.hpp:298
Gecode::Search::Par::Engine::_e_term_ack
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition engine.hh:123
Gecode::Search::Par::Engine::solutions
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
Gecode::Search::Par::Engine::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition engine.hpp:57
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::_m_term
Support::Mutex _m_term
Mutex for access to termination information.
Definition engine.hh:119
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::_opt
Options _opt
Search options.
Definition engine.hh:83
Gecode::Search::Par::Engine::busy
void busy(void)
Report that worker is busy.
Definition engine.hpp:163
Gecode::Search::Par::Engine::_cmd
volatile Cmd _cmd
The current command.
Definition engine.hh:101
Gecode::Search::Par::Engine::_n_reset_not_ack
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition engine.hh:147
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::ack_reset_start
void ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition engine.hpp:235
Gecode::Search::Par::Engine::_n_term_not_ack
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition engine.hh:121
Gecode::Search::Par::Engine::wait_reset
void wait_reset(void)
For worker to wait for all workers to reset.
Definition engine.hpp:253
Gecode::Search::Par::Engine::_n_not_terminated
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition engine.hh:127
Gecode::Search::Par::Engine::terminated
virtual void terminated(void)
For worker to register termination.
Definition engine.hpp:187
Gecode::Search::Par::Engine::terminate
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
Gecode::Search::Par::Engine::_m_reset
Support::Mutex _m_reset
Mutex for access to reset information.
Definition engine.hh:145
Gecode::Search::Par::Engine::n_busy
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
Gecode::Search::Par::Engine::wait_terminate
void wait_terminate(void)
For worker to wait until termination is legal.
Definition engine.hpp:209
Gecode::Search::Par::Engine::workers
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
Gecode::Search::Par::Engine::Cmd
Cmd
Commands from engine to workers.
Definition engine.hh:93
Gecode::Search::Par::Engine::C_WORK
@ C_WORK
Perform work.
Definition engine.hh:94
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::Engine::ack_terminate
void ack_terminate(void)
For worker to acknowledge termination command.
Definition engine.hpp:200
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::Worker::Worker
Worker(void)
Initialize.
Definition worker.hh:70
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::Terminator
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:251
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_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode::Search::snapshot
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition support.hh:71
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