Generated on Tue May 22 09:40:12 2018 for Gecode by doxygen 1.6.3

dfs.hpp

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Search { namespace Par {
00035 
00036   /*
00037    * Basic access routines
00038    */
00039   template<class Tracer>
00040   forceinline DFS<Tracer>&
00041   DFS<Tracer>::Worker::engine(void) const {
00042     return static_cast<DFS<Tracer>&>(_engine);
00043   }
00044   template<class Tracer>
00045   forceinline typename DFS<Tracer>::Worker*
00046   DFS<Tracer>::worker(unsigned int i) const {
00047     return _worker[i];
00048   }
00049 
00050 
00051   /*
00052    * Engine: initialization
00053    */
00054   template<class Tracer>
00055   forceinline
00056   DFS<Tracer>::Worker::Worker(Space* s, DFS& e)
00057     : Engine<Tracer>::Worker(s,e) {}
00058   template<class Tracer>
00059   forceinline
00060   DFS<Tracer>::DFS(Space* s, const Options& o)
00061     : Engine<Tracer>(o) {
00062     WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
00063                               workers());
00064     // Create workers
00065     _worker = static_cast<Worker**>
00066       (heap.ralloc(workers() * sizeof(Worker*)));
00067     // The first worker gets the entire search tree
00068     _worker[0] = new Worker(s,*this);
00069     // All other workers start with no work
00070     for (unsigned int i=1; i<workers(); i++)
00071       _worker[i] = new Worker(NULL,*this);
00072     // Block all workers
00073     block();
00074     // Create and start threads
00075     for (unsigned int i=0; i<workers(); i++)
00076       Support::Thread::run(_worker[i]);
00077   }
00078 
00079 
00080   /*
00081    * Reset
00082    */
00083   template<class Tracer>
00084   forceinline void
00085   DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
00086     delete cur;
00087     tracer.round();
00088     path.reset((s != NULL) ? ngdl : 0);
00089     d = 0;
00090     idle = false;
00091     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00092       delete s;
00093       cur = NULL;
00094     } else {
00095       cur = s;
00096     }
00097     Search::Worker::reset();
00098   }
00099 
00100 
00101   /*
00102    * Engine: search control
00103    */
00104   template<class Tracer>
00105   forceinline void
00106   DFS<Tracer>::solution(Space* s) {
00107     m_search.acquire();
00108     bool bs = signal();
00109     solutions.push(s);
00110     if (bs)
00111       e_search.signal();
00112     m_search.release();
00113   }
00114 
00115 
00116 
00117   /*
00118    * Worker: finding and stealing working
00119    */
00120   template<class Tracer>
00121   forceinline void
00122   DFS<Tracer>::Worker::find(void) {
00123     // Try to find new work (even if there is none)
00124     for (unsigned int i=0; i<engine().workers(); i++) {
00125       unsigned long int r_d = 0ul;
00126       typename Engine<Tracer>::Worker* wi = engine().worker(i);
00127       if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
00128         // Reset this guy
00129         m.acquire();
00130         idle = false;
00131         // Not idle but also does not have the root of the tree
00132         path.ngdl(0);
00133         d = 0;
00134         cur = s;
00135         Statistics t = *this;
00136         Search::Worker::reset(r_d);
00137         (*this) += t;
00138         m.release();
00139         return;
00140       }
00141     }
00142   }
00143 
00144   /*
00145    * Statistics
00146    */
00147   template<class Tracer>
00148   Statistics
00149   DFS<Tracer>::statistics(void) const {
00150     Statistics s;
00151     for (unsigned int i=0; i<workers(); i++)
00152       s += worker(i)->statistics();
00153     return s;
00154   }
00155 
00156 
00157   /*
00158    * Engine: search control
00159    */
00160   template<class Tracer>
00161   void
00162   DFS<Tracer>::Worker::run(void) {
00163     /*
00164      * The engine maintains the following invariant:
00165      *  - If the current space (cur) is not NULL, the path always points
00166      *    to exactly that space.
00167      *  - If the current space (cur) is NULL, the path always points
00168      *    to the next space (if there is any).
00169      *
00170      * This invariant is needed so that no-goods can be extracted properly
00171      * when the engine is stopped or has found a solution.
00172      *
00173      */
00174     // Peform initial delay, if not first worker
00175     if (this != engine().worker(0))
00176       Support::Thread::sleep(Config::initial_delay);
00177     // Okay, we are in business, start working
00178     while (true) {
00179       switch (engine().cmd()) {
00180       case C_WAIT:
00181         // Wait
00182         engine().wait();
00183         break;
00184       case C_TERMINATE:
00185         // Acknowledge termination request
00186         engine().ack_terminate();
00187         // Wait until termination can proceed
00188         engine().wait_terminate();
00189         // Thread will be terminated by returning from run
00190         return;
00191       case C_RESET:
00192         // Acknowledge reset request
00193         engine().ack_reset_start();
00194         // Wait until reset has been performed
00195         engine().wait_reset();
00196         // Acknowledge that reset cycle is over
00197         engine().ack_reset_stop();
00198         break;
00199       case C_WORK:
00200         // Perform exploration work
00201         {
00202           m.acquire();
00203           if (idle) {
00204             m.release();
00205             // Try to find new work
00206             find();
00207           } else if (cur != NULL) {
00208             start();
00209             if (stop(engine().opt())) {
00210               // Report stop
00211               m.release();
00212               engine().stop();
00213             } else {
00214               node++;
00215               SearchTracer::EdgeInfo ei;
00216               if (tracer) {
00217                 if (path.entries() > 0) {
00218                   typename Path<Tracer>::Edge& top = path.top();
00219                   ei.init(tracer.wid(), top.nid(), top.truealt(),
00220                           *cur, *top.choice());
00221                 } else if (*tracer.ei()) {
00222                   ei = *tracer.ei();
00223                   tracer.invalidate();
00224                 }
00225               }
00226               unsigned int nid = tracer.nid();
00227               switch (cur->status(*this)) {
00228               case SS_FAILED:
00229                 if (tracer) {
00230                   SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00231                                             tracer.wid(), nid, *cur);
00232                   tracer.node(ei,ni);
00233                 }
00234                 fail++;
00235                 delete cur;
00236                 cur = NULL;
00237                 path.next();
00238                 m.release();
00239                 break;
00240               case SS_SOLVED:
00241                 {
00242                   if (tracer) {
00243                     SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
00244                                               tracer.wid(), nid, *cur);
00245                     tracer.node(ei,ni);
00246                   }
00247                   // Deletes all pending branchers
00248                   (void) cur->choice();
00249                   Space* s = cur->clone();
00250                   delete cur;
00251                   cur = NULL;
00252                   path.next();
00253                   m.release();
00254                   engine().solution(s);
00255                 }
00256                 break;
00257               case SS_BRANCH:
00258                 {
00259                   Space* c;
00260                   if ((d == 0) || (d >= engine().opt().c_d)) {
00261                     c = cur->clone();
00262                     d = 1;
00263                   } else {
00264                     c = NULL;
00265                     d++;
00266                   }
00267                   const Choice* ch = path.push(*this,cur,c,nid);
00268                   if (tracer) {
00269                     SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00270                                               tracer.wid(), nid, *cur, ch);
00271                     tracer.node(ei,ni);
00272                   }
00273                   cur->commit(*ch,0);
00274                   m.release();
00275                 }
00276                 break;
00277               default:
00278                 GECODE_NEVER;
00279               }
00280             }
00281           } else if (!path.empty()) {
00282             cur = path.recompute(d,engine().opt().a_d,*this,tracer);
00283             if (cur == NULL)
00284               path.next();
00285             m.release();
00286           } else {
00287             idle = true;
00288             path.ngdl(0);
00289             m.release();
00290             // Report that worker is idle
00291             engine().idle();
00292           }
00293         }
00294         break;
00295       default:
00296         GECODE_NEVER;
00297       }
00298     }
00299   }
00300 
00301 
00302   /*
00303    * Perform reset
00304    *
00305    */
00306   template<class Tracer>
00307   void
00308   DFS<Tracer>::reset(Space* s) {
00309     // Grab wait lock for reset
00310     m_wait_reset.acquire();
00311     // Release workers for reset
00312     release(C_RESET);
00313     // Wait for reset cycle started
00314     e_reset_ack_start.wait();
00315     // All workers are marked as busy again
00316     n_busy = workers();
00317     for (unsigned int i=1U; i<workers(); i++)
00318       worker(i)->reset(NULL,0);
00319     worker(0U)->reset(s,opt().nogoods_limit);
00320     // Block workers again to ensure invariant
00321     block();
00322     // Release reset lock
00323     m_wait_reset.release();
00324     // Wait for reset cycle stopped
00325     e_reset_ack_stop.wait();
00326   }
00327 
00328 
00329 
00330   /*
00331    * Create no-goods
00332    *
00333    */
00334   template<class Tracer>
00335   NoGoods&
00336   DFS<Tracer>::nogoods(void) {
00337     NoGoods* ng;
00338     // Grab wait lock for reset
00339     m_wait_reset.acquire();
00340     // Release workers for reset
00341     release(C_RESET);
00342     // Wait for reset cycle started
00343     e_reset_ack_start.wait();
00344     ng = &worker(0)->nogoods();
00345     // Block workers again to ensure invariant
00346     block();
00347     // Release reset lock
00348     m_wait_reset.release();
00349     // Wait for reset cycle stopped
00350     e_reset_ack_stop.wait();
00351     return *ng;
00352   }
00353 
00354 
00355   /*
00356    * Termination and deletion
00357    */
00358   template<class Tracer>
00359   DFS<Tracer>::~DFS(void) {
00360     terminate();
00361     heap.rfree(_worker);
00362   }
00363 
00364 }}}
00365 
00366 // STATISTICS: search-par