Generated on Thu Mar 22 10:39:43 2012 for Gecode by doxygen 1.6.3

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: 2009-08-26 21:10:00 +0200 (Wed, 26 Aug 2009) $ by $Author: schulte $
00011  *     $Revision: 9632 $
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_WORK:
00081         // Perform exploration work
00082         {
00083           m.acquire();
00084           if (idle) {
00085             m.release();
00086             // Try to find new work
00087             find();
00088           } else if (cur != NULL) {
00089             start();
00090             if (stop(engine().opt(),path.size())) {
00091               // Report stop
00092               m.release();
00093               engine().stop();
00094             } else {
00095               /*
00096                * The invariant maintained by the engine is:
00097                *   For all nodes stored at a depth less than mark, there
00098                *   is no guarantee of betterness. For those above the mark,
00099                *   betterness is guaranteed.
00100                */
00101               node++;
00102               switch (cur->status(*this)) {
00103               case SS_FAILED:
00104                 fail++;
00105                 delete cur;
00106                 cur = NULL;
00107                 Worker::current(NULL);
00108                 m.release();
00109                 break;
00110               case SS_SOLVED:
00111                 {
00112                   // Deletes all pending branchers
00113                   (void) cur->choice();
00114                   Space* s = cur->clone(false);
00115                   delete cur;
00116                   cur = NULL;
00117                   Worker::current(NULL);
00118                   m.release();
00119                   engine().solution(s);
00120                 }
00121                 break;
00122               case SS_BRANCH:
00123                 {
00124                   Space* c;
00125                   if ((d == 0) || (d >= engine().opt().c_d)) {
00126                     c = cur->clone();
00127                     d = 1;
00128                   } else {
00129                     c = NULL;
00130                     d++;
00131                   }
00132                   const Choice* ch = path.push(*this,cur,c);
00133                   Worker::push(c,ch);
00134                   cur->commit(*ch,0);
00135                   m.release();
00136                 }
00137                 break;
00138               default:
00139                 GECODE_NEVER;
00140               }
00141             }
00142           } else if (path.next(*this)) {
00143             cur = path.recompute(d,engine().opt().a_d,*this,best,mark);
00144             Worker::current(cur);
00145             m.release();
00146           } else {
00147             idle = true;
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    * Termination and deletion
00163    */
00164   BAB::Worker::~Worker(void) {
00165     delete best;
00166   }
00167 
00168   BAB::~BAB(void) {
00169     terminate();
00170     delete best;
00171     heap.rfree(_worker);
00172   }
00173 
00174 }}}
00175 
00176 #endif
00177 
00178 // STATISTICS: search-parallel