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