Generated on Wed Nov 5 2014 05:18:31 for Gecode by doxygen 1.7.6.1
dfs.cpp
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-10-24 16:42:20 +0200 (Thu, 24 Oct 2013) $ by $Author: schulte $
00011  *     $Revision: 14030 $
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 #include <gecode/support.hh>
00039 
00040 #ifdef GECODE_HAS_THREADS
00041 
00042 #include <gecode/search/parallel/dfs.hh>
00043 
00044 namespace Gecode { namespace Search { namespace Parallel {
00045 
00046   /*
00047    * Statistics
00048    */
00049   Statistics 
00050   DFS::statistics(void) const {
00051     Statistics s;
00052     for (unsigned int i=0; i<workers(); i++)
00053       s += worker(i)->statistics();
00054     return s;
00055   }
00056 
00057 
00058   /*
00059    * Engine: search control
00060    */
00061   void
00062   DFS::Worker::run(void) {
00063     // Peform initial delay, if not first worker
00064     if (this != engine().worker(0))
00065       Support::Thread::sleep(Config::initial_delay);
00066     // Okay, we are in business, start working
00067     while (true) {
00068       switch (engine().cmd()) {
00069       case C_WAIT:
00070         // Wait
00071         engine().wait();
00072         break;
00073       case C_TERMINATE:
00074         // Acknowledge termination request
00075         engine().ack_terminate();
00076         // Wait until termination can proceed
00077         engine().wait_terminate();
00078         // Terminate thread
00079         engine().terminated();
00080         return;
00081       case C_RESET:
00082         // Acknowledge reset request
00083         engine().ack_reset_start();
00084         // Wait until reset has been performed
00085         engine().wait_reset();
00086         // Acknowledge that reset cycle is over
00087         engine().ack_reset_stop();
00088         break;
00089       case C_WORK:
00090         // Perform exploration work
00091         {
00092           m.acquire();
00093           if (idle) {
00094             m.release();
00095             // Try to find new work
00096             find();
00097           } else if (cur != NULL) {
00098             start();
00099             if (stop(engine().opt())) {
00100               // Report stop
00101               m.release();
00102               engine().stop();
00103             } else {
00104               node++;
00105               switch (cur->status(*this)) {
00106               case SS_FAILED:
00107                 fail++;
00108                 delete cur;
00109                 cur = NULL;
00110                 m.release();
00111                 break;
00112               case SS_SOLVED:
00113                 {
00114                   // Deletes all pending branchers
00115                   (void) cur->choice();
00116                   Space* s = cur->clone(false);
00117                   delete cur;
00118                   cur = NULL;
00119                   m.release();
00120                   engine().solution(s);
00121                 }
00122                 break;
00123               case SS_BRANCH:
00124                 {
00125                   Space* c;
00126                   if ((d == 0) || (d >= engine().opt().c_d)) {
00127                     c = cur->clone();
00128                     d = 1;
00129                   } else {
00130                     c = NULL;
00131                     d++;
00132                   }
00133                   const Choice* ch = path.push(*this,cur,c);
00134                   cur->commit(*ch,0);
00135                   m.release();
00136                 }
00137                 break;
00138               default:
00139                 GECODE_NEVER;
00140               }
00141             }
00142           } else if (path.next()) {
00143             cur = path.recompute(d,engine().opt().a_d,*this);
00144             m.release();
00145           } else {
00146             idle = true;
00147             path.ngdl(0);
00148             m.release();
00149             // Report that worker is idle
00150             engine().idle();
00151           }
00152         }
00153         break;
00154       default:
00155         GECODE_NEVER;
00156       }
00157     }
00158   }
00159 
00160 
00161   /*
00162    * Perform reset
00163    *
00164    */
00165   void
00166   DFS::reset(Space* s) {
00167     // Grab wait lock for reset
00168     m_wait_reset.acquire();
00169     // Release workers for reset
00170     release(C_RESET);
00171     // Wait for reset cycle started
00172     e_reset_ack_start.wait();
00173     // All workers are marked as busy again
00174     n_busy = workers();
00175     for (unsigned int i=1U; i<workers(); i++)
00176       worker(i)->reset(NULL,0);
00177     worker(0U)->reset(s,opt().nogoods_limit);
00178     // Block workers again to ensure invariant
00179     block();
00180     // Release reset lock
00181     m_wait_reset.release();
00182     // Wait for reset cycle stopped
00183     e_reset_ack_stop.wait();
00184   }
00185 
00186 
00187 
00188   /*
00189    * Create no-goods
00190    *
00191    */
00192   NoGoods&
00193   DFS::nogoods(void) {
00194     NoGoods* ng;
00195     // Grab wait lock for reset
00196     m_wait_reset.acquire();
00197     // Release workers for reset
00198     release(C_RESET);
00199     // Wait for reset cycle started
00200     e_reset_ack_start.wait();
00201     ng = &worker(0)->nogoods();
00202     // Block workers again to ensure invariant
00203     block();
00204     // Release reset lock
00205     m_wait_reset.release();
00206     // Wait for reset cycle stopped
00207     e_reset_ack_stop.wait();
00208     return *ng;
00209   }
00210 
00211 
00212   /*
00213    * Termination and deletion
00214    */
00215   DFS::~DFS(void) {
00216     terminate();
00217     heap.rfree(_worker);
00218   }
00219 
00220 }}}
00221 
00222 #endif
00223 
00224 // STATISTICS: search-parallel