pbs.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, 2015
*
* 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.
*
*/
#include <algorithm>
namespace Gecode { namespace Search { namespace Par {
forceinline
CollectAll::CollectAll(void)
: solutions(heap) {}
forceinline bool
CollectAll::add(Space* s, Slave<CollectAll>*) {
solutions.push(s);
return true;
}
forceinline bool
CollectAll::constrain(const Space& b) {
(void) b;
return false;
}
forceinline bool
CollectAll::empty(void) const {
return solutions.empty();
}
forceinline Space*
CollectAll::get(Slave<CollectAll>*&) {
return solutions.pop();
}
forceinline
CollectAll::~CollectAll(void) {
while (!solutions.empty())
delete solutions.pop();
}
forceinline
CollectBest::CollectBest(void)
: b(NULL), reporter(NULL) {}
forceinline bool
CollectBest::add(Space* s, Slave<CollectBest>* r) {
if (b != NULL) {
b->constrain(*s);
if (b->status() == SS_FAILED) {
delete b;
} else {
delete s;
return false;
}
}
b = s;
reporter = r;
return true;
}
forceinline bool
CollectBest::constrain(const Space& s) {
if (b != NULL) {
b->constrain(s);
if (b->status() == SS_FAILED) {
delete b;
} else {
return false;
}
}
b = s.clone();
reporter = NULL;
return true;
}
forceinline bool
CollectBest::empty(void) const {
return reporter == NULL;
}
forceinline Space*
CollectBest::get(Slave<CollectBest>*& r) {
assert(!empty());
r = reporter;
reporter = NULL;
return b->clone();
}
forceinline
CollectBest::~CollectBest(void) {
delete b;
}
forceinline
PortfolioStop::PortfolioStop(Stop* so0)
: so(so0), tostop(NULL) {}
forceinline void
PortfolioStop::share(volatile bool* ts) {
tostop = ts;
}
template<class Collect>
forceinline
Slave<Collect>::Slave(PBS<Collect>* m, Engine* s, Stop* so)
: Support::Runnable(false), master(m), slave(s), stop(so) {}
template<class Collect>
forceinline Statistics
Slave<Collect>::statistics(void) const {
return slave->statistics();
}
template<class Collect>
forceinline bool
Slave<Collect>::stopped(void) const {
return slave->stopped();
}
template<class Collect>
forceinline void
Slave<Collect>::constrain(const Space& b) {
slave->constrain(b);
}
template<class Collect>
Slave<Collect>::~Slave(void) {
delete slave;
delete stop;
}
template<class Collect>
forceinline
PBS<Collect>::PBS(Engine** engines, Stop** stops, unsigned int n,
const Statistics& stat0)
: stat(stat0), slaves(heap.alloc<Slave<Collect>*>(n)),
n_slaves(n), n_active(n),
slave_stop(false), tostop(false), n_busy(0) {
// Initialize slaves
for (unsigned int i=0U; i<n_slaves; i++) {
slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
static_cast<PortfolioStop*>(stops[i])->share(&tostop);
}
}
template<class Collect>
forceinline bool
PBS<Collect>::report(Slave<Collect>* slave, Space* s) {
// If b is false the report should be repeated (solution was worse)
bool b = true;
m.acquire();
if (s != NULL) {
b = solutions.add(s,slave);
if (b)
tostop = true;
} else if (slave->stopped()) {
if (!tostop)
slave_stop = true;
} else {
// Move slave to inactive, as it has exhausted its engine
unsigned int i=0;
while (slaves[i] != slave)
i++;
assert(i < n_active);
assert(n_active > 0);
std::swap(slaves[i],slaves[--n_active]);
tostop = true;
}
if (b) {
if (--n_busy == 0)
idle.signal();
}
m.release();
return b;
}
template<class Collect>
void
Slave<Collect>::run(void) {
Space* s;
do {
s = slave->next();
} while (!master->report(this,s));
}
template<class Collect>
Space*
PBS<Collect>::next(void) {
m.acquire();
if (solutions.empty()) {
// Clear all
tostop = false;
slave_stop = false;
// Invariant: all slaves are idle!
assert(n_busy == 0);
assert(!tostop);
if (n_active > 0) {
// Run all active slaves
n_busy = n_active;
for (unsigned int i=0U; i<n_active; i++)
Support::Thread::run(slaves[i]);
m.release();
// Wait for all slaves to become idle
idle.wait();
m.acquire();
}
}
// Invariant all slaves are idle!
assert(n_busy == 0);
Space* s;
// Process solutions
if (solutions.empty()) {
s = NULL;
} else {
Slave<Collect>* r;
s = solutions.get(r);
if (Collect::best)
for (unsigned int i=0U; i<n_active; i++)
if (slaves[i] != r)
slaves[i]->constrain(*s);
}
m.release();
return s;
}
template<class Collect>
bool
PBS<Collect>::stopped(void) const {
return slave_stop;
}
template<class Collect>
Statistics
PBS<Collect>::statistics(void) const {
assert(n_busy == 0);
Statistics s(stat);
for (unsigned int i=0U; i<n_slaves; i++)
s += slaves[i]->statistics();
return s;
}
template<class Collect>
void
PBS<Collect>::constrain(const Space& b) {
assert(n_busy == 0);
if (!Collect::best)
throw NoBest("PBS::constrain");
if (solutions.constrain(b)) {
// The solution is better
for (unsigned int i=0U; i<n_active; i++)
slaves[i]->constrain(b);
}
}
template<class Collect>
PBS<Collect>::~PBS(void) {
assert(n_busy == 0);
heap.free<Slave<Collect>*>(slaves,n_slaves);
}
}}}
// STATISTICS: search-par
Gecode::Search::NoBest
Exception: Best solution search is not supported
Definition exception.hpp:60
Gecode::Search::Par::CollectAll::get
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition pbs.hpp:57
Gecode::Search::Par::CollectAll::empty
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:53
Gecode::Search::Par::CollectAll::solutions
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition pbs.hh:94
Gecode::Search::Par::CollectAll::add
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition pbs.hpp:43
Gecode::Search::Par::CollectAll::CollectAll
CollectAll(void)
Initialize.
Definition pbs.hpp:40
Gecode::Search::Par::CollectAll::~CollectAll
~CollectAll(void)
Destructor.
Definition pbs.hpp:61
Gecode::Search::Par::CollectAll::constrain
bool constrain(const Space &b)
Dummy function.
Definition pbs.hpp:48
Gecode::Search::Par::CollectBest::CollectBest
CollectBest(void)
Initialize.
Definition pbs.hpp:68
Gecode::Search::Par::CollectBest::constrain
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition pbs.hpp:86
Gecode::Search::Par::CollectBest::empty
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:100
Gecode::Search::Par::CollectBest::add
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition pbs.hpp:71
Gecode::Search::Par::CollectBest::get
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found).
Definition pbs.hpp:104
Gecode::Search::Par::CollectBest::reporter
Slave< CollectBest > * reporter
Who has reported the best solution (NULL if solution has already been reported).
Definition pbs.hh:118
Gecode::Search::Par::CollectBest::~CollectBest
~CollectBest(void)
Destructor.
Definition pbs.hpp:111
Gecode::Search::Par::CollectBest::b
Space * b
Currently best solution.
Definition pbs.hh:116
Gecode::Search::Par::Engine
Parallel depth-first search engine
Definition engine.hh:46
Gecode::Search::Par::Engine::Engine
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
Gecode::Search::Par::PBS
Parallel portfolio engine implementation.
Definition pbs.hh:138
Gecode::Search::Par::PBS::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:256
Gecode::Search::Par::PBS::slave_stop
bool slave_stop
Whether a slave has been stopped.
Definition pbs.hh:150
Gecode::Search::Par::PBS::~PBS
virtual ~PBS(void)
Destructor.
Definition pbs.hpp:284
Gecode::Search::Par::PBS::idle
Support::Event idle
Signal that number of busy slaves becomes zero.
Definition pbs.hh:160
Gecode::Search::Par::PBS::report
bool report(Slave< Collect > *slave, Space *s)
Process report from slave, return false if solution was ignored.
Definition pbs.hpp:170
Gecode::Search::Par::PBS< Gecode::Search::Par::CollectBest >::solutions
Gecode::Search::Par::CollectBest solutions
Definition pbs.hh:154
Gecode::Search::Par::PBS::Slave< Collect >
friend class Slave< Collect >
Definition pbs.hh:139
Gecode::Search::Par::PBS< Gecode::Search::Par::CollectBest >::m
Support::Mutex m
Definition pbs.hh:156
Gecode::Search::Par::PBS::slaves
Slave< Collect > ** slaves
Slave engines.
Definition pbs.hh:144
Gecode::Search::Par::PBS::n_active
unsigned int n_active
Number of active slave engines.
Definition pbs.hh:148
Gecode::Search::Par::PBS::tostop
volatile bool tostop
Shared stop flag.
Definition pbs.hh:152
Gecode::Search::Par::PBS::n_slaves
unsigned int n_slaves
Number of slave engines.
Definition pbs.hh:146
Gecode::Search::Par::PBS::stat
Statistics stat
Master statistics.
Definition pbs.hh:142
Gecode::Search::Par::PBS::PBS
PBS(Engine **s, Stop **so, unsigned int n, const Statistics &stat)
Initialize.
Definition pbs.hpp:155
Gecode::Search::Par::PBS::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:272
Gecode::Search::Par::PBS::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped).
Definition pbs.hpp:210
Gecode::Search::Par::PBS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:262
Gecode::Search::Par::PBS::n_busy
unsigned int n_busy
Number of busy slaves.
Definition pbs.hh:158
Gecode::Search::Par::PortfolioStop
Stop object used for controling slaves in a portfolio.
Definition pbs.hh:42
Gecode::Search::Par::PortfolioStop::share
void share(volatile bool *ts)
Set pointer to shared tostop variable.
Definition pbs.hpp:121
Gecode::Search::Par::PortfolioStop::PortfolioStop
PortfolioStop(Stop *so)
Initialize.
Definition pbs.hpp:117
Gecode::Search::Par::Slave
Runnable slave of a portfolio master.
Definition pbs.hh:67
Gecode::Search::Par::Slave::slave
Engine * slave
The slave engine.
Definition pbs.hh:72
Gecode::Search::Par::Slave::master
PBS< Collect > * master
The master engine.
Definition pbs.hh:70
Gecode::Search::Par::Slave::run
virtual void run(void)
Perform one run.
Definition pbs.hpp:201
Gecode::Search::Par::Slave::stopped
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:137
Gecode::Search::Par::Slave::~Slave
virtual ~Slave(void)
Delete slave.
Definition pbs.hpp:146
Gecode::Search::Par::Slave::statistics
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:132
Gecode::Search::Par::Slave::Slave
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition pbs.hpp:128
Gecode::Search::Par::Slave::constrain
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:142
Gecode::Search::Par::Slave::stop
Stop * stop
Stop object.
Definition pbs.hh:74
Gecode::Search::Statistics
Search engine statistics
Definition search.hh:147
Gecode::Search::Stop
Base-class for Stop-object.
Definition search.hh:799
Gecode::Search::Stop::Stop
Stop(void)
Default constructor.
Definition stop.hpp:41
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::Runnable::Runnable
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
Definition thread.hpp:40
Gecode::Support::Thread::run
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Space::constrain
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::Space::clone
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode::Support
Support algorithms and datastructures
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187