Generated on Wed Nov 5 2014 05:18:31 for Gecode by doxygen 1.7.6.1
bab.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2009
00008  *
00009  *  Last modified:
00010  *     $Date: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13840 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_SEARCH_PARALLEL_BAB_HH__
00039 #define __GECODE_SEARCH_PARALLEL_BAB_HH__
00040 
00041 #include <gecode/search/parallel/engine.hh>
00042 
00043 namespace Gecode { namespace Search { namespace Parallel {
00044 
00046   class BAB : public Engine {
00047   protected:
00049     class Worker : public Engine::Worker {
00050     protected:
00052       int mark;
00054       Space* best;
00055     public:
00057       Worker(Space* s, BAB& e);
00059       BAB& engine(void) const;
00061       virtual void run(void);
00063       void better(Space* b);
00065       void find(void);
00067       void reset(Space* s, int ngdl);
00069       virtual ~Worker(void);
00070     };
00072     Worker** _worker;
00074     Space* best;
00075   public:
00077     Worker* worker(unsigned int i) const;
00078 
00080 
00081 
00082     void solution(Space* s);
00084 
00086 
00087 
00088     BAB(Space* s, const Options& o);
00090     virtual Statistics statistics(void) const;
00092     virtual void reset(Space* s);
00094     virtual NoGoods& nogoods(void);
00096     virtual ~BAB(void);
00098   };
00099 
00100 
00101 
00102   /*
00103    * Engine: basic access routines
00104    */
00105   forceinline BAB&
00106   BAB::Worker::engine(void) const {
00107     return static_cast<BAB&>(_engine);
00108   }
00109   forceinline BAB::Worker*
00110   BAB::worker(unsigned int i) const {
00111     return _worker[i];
00112   }
00113 
00114   forceinline void
00115   BAB::Worker::reset(Space* s, int ngdl) {
00116     delete cur;
00117     delete best;
00118     best = NULL;
00119     path.reset((s == NULL) ? 0 : ngdl);
00120     d = mark = 0;
00121     idle = false;
00122     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00123       delete s;
00124       cur = NULL;
00125     } else {
00126       cur = s;
00127     }
00128     Search::Worker::reset();
00129   }
00130 
00131 
00132   /*
00133    * Engine: initialization
00134    */
00135   forceinline
00136   BAB::Worker::Worker(Space* s, BAB& e)
00137     : Engine::Worker(s,e), mark(0), best(NULL) {}
00138 
00139   forceinline
00140   BAB::BAB(Space* s, const Options& o)
00141     : Engine(o), best(NULL) {
00142     // Create workers
00143     _worker = static_cast<Worker**>
00144       (heap.ralloc(workers() * sizeof(Worker*)));
00145     // The first worker gets the entire search tree
00146     _worker[0] = new Worker(s,*this);
00147     // All other workers start with no work
00148     for (unsigned int i=1; i<workers(); i++)
00149       _worker[i] = new Worker(NULL,*this);
00150     // Block all workers
00151     block();
00152     // Create and start threads
00153     for (unsigned int i=0; i<workers(); i++)
00154       Support::Thread::run(_worker[i]);
00155   }
00156 
00157 
00158   /*
00159    * Engine: search control
00160    */
00161   forceinline void
00162   BAB::Worker::better(Space* b) {
00163     m.acquire();
00164     delete best;
00165     best = b->clone(false);
00166     mark = path.entries();
00167     if (cur != NULL)
00168       cur->constrain(*best);
00169     m.release();
00170   }
00171   forceinline void 
00172   BAB::solution(Space* s) {
00173     m_search.acquire();
00174     if (best != NULL) {
00175       s->constrain(*best);
00176       if (s->status() == SS_FAILED) {
00177         delete s;
00178         m_search.release();
00179         return;
00180       } else {
00181         delete best;
00182         best = s->clone();
00183       }
00184     } else {
00185       best = s->clone();
00186     }
00187     // Announce better solutions
00188     for (unsigned int i=0; i<workers(); i++)
00189       worker(i)->better(best);
00190     bool bs = signal();
00191     solutions.push(s);
00192     if (bs)
00193       e_search.signal();
00194     m_search.release();
00195   }
00196   
00197 
00198   /*
00199    * Worker: finding and stealing working
00200    */
00201   forceinline void
00202   BAB::Worker::find(void) {
00203     // Try to find new work (even if there is none)
00204     for (unsigned int i=0; i<engine().workers(); i++) {
00205       unsigned long int r_d = 0ul;
00206       if (Space* s = engine().worker(i)->steal(r_d)) {
00207         // Reset this guy
00208         m.acquire();
00209         idle = false;
00210         // Not idle but also does not have the root of the tree
00211         path.ngdl(0);
00212         d = 0;
00213         cur = s;
00214         mark = 0;
00215         if (best != NULL)
00216           cur->constrain(*best);
00217         Search::Worker::reset(r_d);
00218         m.release();
00219         return;
00220       }
00221     }
00222   }
00223 
00224 }}}
00225 
00226 #endif
00227 
00228 // STATISTICS: search-parallel