engine.hh
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.
*
*/
#ifndef __GECODE_SEARCH_PAR_ENGINE_HH__
#define __GECODE_SEARCH_PAR_ENGINE_HH__
#include <gecode/search.hh>
#include <gecode/search/support.hh>
#include <gecode/search/worker.hh>
#include <gecode/search/par/path.hh>
namespace Gecode { namespace Search { namespace Par {
template<class Tracer>
class Engine : public Search::Engine, public Support::Terminator {
protected:
class Worker : public Search::Worker, public Support::Runnable {
public:
Tracer tracer;
protected:
Engine& _engine;
Support::Mutex m;
Path<Tracer> path;
Space* cur;
unsigned int d;
bool idle;
public:
Worker(Space* s, Engine& e);
Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot);
Statistics statistics(void);
Engine& engine(void) const;
NoGoods& nogoods(void);
virtual ~Worker(void);
virtual Support::Terminator* terminator(void) const;
};
Options _opt;
public:
const Options& opt(void) const;
unsigned int workers(void) const;
enum Cmd {
C_WORK,
C_WAIT,
C_RESET,
C_TERMINATE
};
protected:
volatile Cmd _cmd;
Support::Mutex _m_wait;
public:
Cmd cmd(void) const;
void block(void);
void release(Cmd c);
void wait(void);
protected:
Support::Mutex _m_term;
volatile unsigned int _n_term_not_ack;
Support::Event _e_term_ack;
Support::Mutex _m_wait_terminate;
volatile unsigned int _n_not_terminated;
Support::Event _e_terminate;
public:
void ack_terminate(void);
virtual void terminated(void);
void wait_terminate(void);
void terminate(void);
protected:
Support::Mutex _m_reset;
volatile unsigned int _n_reset_not_ack;
Support::Event e_reset_ack_start;
Support::Event e_reset_ack_stop;
Support::Mutex m_wait_reset;
public:
void ack_reset_start(void);
void ack_reset_stop(void);
void wait_reset(void);
protected:
Support::Mutex m_search;
Support::Event e_search;
Support::DynamicQueue<Space*,Heap> solutions;
volatile unsigned int n_busy;
volatile bool has_stopped;
bool signal(void) const;
public:
void idle(void);
void busy(void);
void stop(void);
Engine(const Options& o);
virtual Space* next(void);
virtual bool stopped(void) const;
};
}}}
#include <gecode/search/par/engine.hpp>
#endif
// STATISTICS: search-par
Gecode::NoGoods
No-goods recorded from restarts.
Definition core.hpp:1588
Gecode::Search::Engine
Search engine implementation interface
Definition search.hh:899
Gecode::Search::Options
Search engine options
Definition search.hh:746
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::Worker
Worker(Space *s, Engine &e)
Initialize for space s with engine e.
Definition engine.hpp:95
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::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_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::Engine::ack_terminate
void ack_terminate(void)
For worker to acknowledge termination command.
Definition engine.hpp:200
Gecode::Search::Par::Path
Depth-first path (stack of edges) supporting recomputation.
Definition path.hh:60
Gecode::Search::Statistics::Statistics
Statistics(void)
Initialize.
Definition statistics.hpp:45
Gecode::Search::Worker
Search worker statistics
Definition worker.hh:44
Gecode::Search::Worker::Worker
Worker(void)
Initialize.
Definition worker.hh:70
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::DynamicQueue
Queue with arbitrary number of elements.
Definition dynamic-queue.hpp:42
Gecode::Support::Event
An event for synchronization.
Definition thread.hpp:215
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::Support::Runnable
An interface for objects that can be run by a thread.
Definition thread.hpp:264
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::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
engine.hpp
path.hh
support.hh
search.hh
worker.hh