/home/coin/SVN-release/OS-2.4.0/Bcp/src/TM/BCP_tm_functions.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <cstdio>
00004 #include "BCP_os.hpp"
00005 #include "BCP_error.hpp"
00006 #include "BCP_node_change.hpp"
00007 #include "BCP_enum_tm.hpp"
00008 #include "BCP_tm.hpp"
00009 #include "BCP_tm_functions.hpp"
00010 
00011 static inline BCP_node_start_result BCP_tm_start_one_node(BCP_tm_prob& p);
00012 
00013 //#############################################################################
00014 
00015 BCP_vec< std::pair<int,int> >::iterator
00016 BCP_tm_identify_process(BCP_vec< std::pair<int,int> >& proclist, int proc)
00017 {
00018     BCP_vec< std::pair<int,int> >::iterator proci = proclist.begin();
00019     BCP_vec< std::pair<int,int> >::iterator lastproci = proclist.end();
00020     while (proci != lastproci) {
00021         if (proci->first == proc)
00022             break;
00023         ++proci;
00024     }
00025     return proci;
00026 }
00027 
00028 //#############################################################################
00029 
00030 bool
00031 BCP_tm_assign_processes(BCP_tm_prob& p, BCP_tm_node* node)
00032 {
00033     int lp = -1;
00034     int cg = -1;
00035     int vg = -1;
00036     int cp = -1;
00037     int vp = -1;
00038     bool so_far_so_good = true;
00039 
00040     if (so_far_so_good) {
00041         lp = p.lp_scheduler.request_node_id();
00042         if (lp == -1)
00043             return false;
00044         if (! p.msg_env->alive(lp)) {
00045             BCP_tm_remove_lp(p, lp);
00046             return false;
00047         }
00048     }
00049 
00050 #if ! defined(BCP_ONLY_LP_PROCESS_HANDLING_WORKS)
00051     if (so_far_so_good && p.slaves.cg) {
00052         cg = p.slaves.cg->get_free_proc();
00053         if (cg == -1)
00054             return false;
00055         if (! p.msg_env->alive(cg)) {
00056             BCP_tm_remove_cg(p, p.slaves.cg->index_of_proc(cg));
00057             so_far_so_good = false;
00058         }
00059     }
00060 
00061     if (so_far_so_good && p.slaves.vg) {
00062         vg = p.slaves.vg->get_free_proc();
00063         if (vg == -1)
00064             return false;
00065         if (! p.msg_env->alive(vg)) {
00066             BCP_tm_remove_vg(p, p.slaves.vg->index_of_proc(vg));
00067             so_far_so_good = false;
00068         }
00069     }
00070 
00071     if (so_far_so_good && p.slaves.cp) {
00072         while (true) {
00073             cp = p.slaves.cp->get_free_proc();
00074             if (cp == -1)
00075                 break;
00076             if (p.msg_env->alive(cp))
00077                 break;
00078             // *FIXME*
00079             throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
00080         }
00081         if (cp == -1) {
00082             // if there is no free CP, just keep the old one
00083             if (node->cp != -1 && ! p.msg_env->alive(node->cp)) {
00084                 // *FIXME*
00085                 throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
00086             }
00087         } else {
00088             if (node->cp != -1 && ! p.msg_env->alive(node->cp)) {
00089                 // *FIXME*
00090                 throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
00091             }
00092         } 
00093     }
00094 
00095     if (so_far_so_good && p.slaves.vp) {
00096         while (true) {
00097             vp = p.slaves.vp->get_free_proc();
00098             if (vp == -1)
00099                 break;
00100             if (p.msg_env->alive(vp))
00101                 break;
00102             // *FIXME*
00103             throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
00104         }
00105         if (vp == -1) {
00106             // if there is no free VP, just keep the old one
00107             if (node->vp != -1 && ! p.msg_env->alive(node->vp)) {
00108                 // *FIXME*
00109                 throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
00110             }
00111         } else {
00112             if (node->vp != -1 && ! p.msg_env->alive(node->vp)) {
00113                 // *FIXME*
00114                 throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
00115             }
00116         } 
00117     }
00118 #endif
00119 
00120     if (! so_far_so_good)
00121         return BCP_tm_assign_processes(p, node);
00122 
00123     node->lp = lp;
00124     node->cg = cg;
00125     node->vg = vg;
00126     if (cp != -1) {
00127         // *LATER* : copy the old CP over to the free one and let node have
00128         // this new CP.
00129         node->cp = cp;
00130     }
00131     if (vp != -1) {
00132         // *LATER* : copy the old VP over to the free one and let node have
00133         // this new VP.
00134         node->vp = vp;
00135     }
00136 
00137     return true;
00138 }
00139 
00140 //#############################################################################
00141 
00142 static void BCP_tm_free_nodes(BCP_tm_prob& p)
00143 {
00144     for (int i = p.nodes_to_free.size() - 1; i >= 0; --i) {
00145         BCP_tm_modify_pool_counters(p, p.nodes_to_free[i]);
00146         BCP_tm_remove_explored(p, p.nodes_to_free[i]);
00147     }
00148     p.nodes_to_free.clear();
00149 }
00150 
00151 //#############################################################################
00152 
00153 static inline BCP_node_start_result
00154 BCP_tm_start_one_node(BCP_tm_prob& p)
00155 {
00156     BCP_tm_node* next_node;
00157 
00158     while (true){
00159         if (p.candidate_list.empty()) {
00160             BCP_tm_free_nodes(p);
00161             return BCP_NodeStart_NoNode;
00162         }
00163         next_node = dynamic_cast<BCP_tm_node*>(p.candidate_list.top());
00164         p.candidate_list.pop();
00165 
00166         // if no UB yet or lb is lower than UB then go ahead
00167         if (! p.has_ub())
00168             break;
00169 
00170         bool process_this = true;
00171 
00172         if (next_node->getTrueLB() > p.ub() - p.granularity())
00173             process_this = false;
00174         if (next_node->getTrueLB() >
00175             p.ub() - p.param(BCP_tm_par::TerminationGap_Absolute))
00176             process_this = false;
00177         if (next_node->getTrueLB() >
00178             p.ub() * (1 - p.param(BCP_tm_par::TerminationGap_Relative)))
00179             process_this = false;
00180 
00181         if (process_this)
00182             break;
00183 
00184         // ok, so we do have an UB and true lb is "higher" than the UB.
00185         if (p.current_phase_colgen == BCP_DoNotGenerateColumns_Fathom) {
00186             // nothing is left to price or in this phase we just fathom the
00187             // over-the-bound nodes. in either case this node can be pruned
00188             // right here.
00189             next_node->status = BCP_PrunedNode_OverUB;
00190             if (p.param(BCP_tm_par::TmVerb_PrunedNodeInfo))
00191                 printf("TM: Pruning NODE %i LEVEL %i instead of sending it.\n",
00192                        next_node->index(), next_node->getDepth());
00193             p.nodes_to_free.push_back(next_node);
00194             BCP_print_memusage(p);
00195             continue;
00196         }
00197         if (p.current_phase_colgen == BCP_DoNotGenerateColumns_Send) {
00198             // the node would be sent back from the LP right away. save the
00199             // trouble and don't even send it out
00200             p.next_phase_nodes.push_back(next_node);
00201             next_node->status = BCP_NextPhaseNode_OverUB;
00202             if (p.param(BCP_tm_par::TmVerb_PrunedNodeInfo))
00203                 printf("\
00204 TM: Moving NODE %i LEVEL %i into the next phase list \n\
00205     instead of sending it.\n",
00206                        next_node->index(), next_node->getDepth());
00207             continue;
00208         }
00209         // must be BCP_GenerateColumns
00210         // all right, we want to send it out anyway for pricing
00211         break;
00212     }
00213 
00214     // assign processes to the node and send it off
00215     if (! BCP_tm_assign_processes(p, next_node)) {
00216         // couldn't find free processes
00217         p.candidate_list.push(next_node, false);
00218         BCP_tm_free_nodes(p);
00219         return BCP_NodeStart_Error;
00220     }
00221 
00222     p.active_nodes[next_node->lp] = next_node;
00223     next_node->status = BCP_ActiveNode;
00224     if (p.param(BCP_tm_par::MessagePassingIsSerial)) {
00225         BCP_tm_free_nodes(p);
00226     }
00227     BCP_tm_node_to_send* node_to_send =
00228         new BCP_tm_node_to_send(p, next_node, BCP_Msg_ActiveNodeData);
00229     if (node_to_send->send()) {
00230         delete node_to_send;
00231     }
00232 
00233 #ifdef BCP__DUMP_PROCINFO
00234 #if (BCP__DUMP_PROCINFO == 1)
00235     dump_procinfo(p, "start_one_node()");
00236 #endif
00237 #endif
00238         
00239     return BCP_NodeStart_OK;
00240 }
00241 
00242 #ifdef BCP__DUMP_PROCINFO
00243 #if (BCP__DUMP_PROCINFO == 1)
00244 void dump_procinfo(BCP_tm_prob& p, const char* str)
00245 {
00246     printf("TM: ***** dump_procinfo from %s *********\n", str);
00247     printf("TM: ********** Active nodes *********\n");
00248     for (int i = 0; i < p.slaves.lp->size(); ++i) {
00249         if (p.active_nodes[i])
00250             printf("TM:     %i, %i, %i\n",
00251                    i, p.active_nodes[i]->index(), p.active_nodes[i]->lp);
00252         else
00253             printf("TM:     %i, %i, %i\n",
00254                    i, -1, -1);
00255          
00256     }
00257     printf("TM: ********** All nodes *********\n");
00258     for (int i = 0; i < p.search_tree.size(); ++i) {
00259         printf("TM:     %i, %i\n", i, p.search_tree[i]->lp);
00260     }
00261 }
00262 #endif
00263 #endif
00264 
00265 //#############################################################################
00266 
00267 BCP_node_start_result BCP_tm_start_new_nodes(BCP_tm_prob& p)
00268 {
00269     while (p.lp_scheduler.has_free_node_id()) {
00270         switch (BCP_tm_start_one_node(p)){
00271         case BCP_NodeStart_NoNode:
00272             return BCP_NodeStart_NoNode;
00273         case BCP_NodeStart_Error:
00274             if (p.lp_scheduler.has_free_node_id()) {
00275                 throw BCP_fatal_error("\
00276 TM: couldn't start new node but there's a free LP ?!\n");
00277             }
00278             break;
00279         case BCP_NodeStart_OK:
00280             break;
00281         }
00282     }
00283     BCP_tm_free_nodes(p);
00284     return BCP_NodeStart_OK;
00285 }
00286 
00287 //#############################################################################
00288 
00289 void BCP_tm_list_candidates(BCP_tm_prob& p)
00290 {
00291     /* FIXME: must walk through the siblings... */
00292 #if 0
00293     CoinSearchTreeBase& candidates = *p.candidate_list.getTree();
00294     const int n = candidates.size();
00295     const std::vector<CoinTreeNode*>& nodes = candidates.getNodes();
00296     for (int i = 0; i < n; ++i) {
00297         printf("%5i", dynamic_cast<BCP_tm_node*>(nodes[i])->index());
00298     }
00299     printf("\n");
00300 #endif
00301 }
00302 
00303 //#############################################################################
00304 
00305 void BCP_check_parameters(BCP_tm_prob& p)
00306 {
00307     p.ub(p.param(BCP_tm_par::UpperBound));
00308 
00309     if (p.par.entry(BCP_tm_par::VerbosityShutUp)) {
00310         int i;
00311         BCP_parameter_set<BCP_tm_par>& tmpar = p.par;
00312         BCP_parameter_set<BCP_lp_par>& lppar = p.slave_pars.lp;
00313         BCP_parameter_set<BCP_cg_par>& cgpar = p.slave_pars.cg;
00314         BCP_parameter_set<BCP_vg_par>& vgpar = p.slave_pars.vg;
00315         char treestat = tmpar.entry(BCP_tm_par::TmVerb_FinalStatistics);
00316         char bestsol  = tmpar.entry(BCP_tm_par::TmVerb_BestFeasibleSolution);
00317         for (i = BCP_tm_par::TmVerb_First+1; i < BCP_tm_par::TmVerb_Last; ++i){
00318             if (tmpar.entry(static_cast<BCP_tm_par::chr_params>(i)) == 2) {
00319                 tmpar.set_entry(static_cast<BCP_tm_par::chr_params>(i), true);
00320             } else {
00321                 tmpar.set_entry(static_cast<BCP_tm_par::chr_params>(i), false);
00322             }
00323         }
00324         for (i = BCP_lp_par::LpVerb_First+1; i < BCP_lp_par::LpVerb_Last; ++i){
00325             if (lppar.entry(static_cast<BCP_lp_par::chr_params>(i)) == 2) {
00326                 lppar.set_entry(static_cast<BCP_lp_par::chr_params>(i), true);
00327             } else {
00328                 lppar.set_entry(static_cast<BCP_lp_par::chr_params>(i), false);
00329             }
00330         }
00331         for (i = BCP_cg_par::CgVerb_First+1; i < BCP_cg_par::CgVerb_Last; ++i){
00332             if (cgpar.entry(static_cast<BCP_cg_par::chr_params>(i)) == 2) {
00333                 cgpar.set_entry(static_cast<BCP_cg_par::chr_params>(i), true);
00334             } else {
00335                 cgpar.set_entry(static_cast<BCP_cg_par::chr_params>(i), false);
00336             }
00337         }
00338         /*
00339           for (i = BCP_vg_par::VgVerb_First+1; i < BCP_vg_par::VgVerb_Last; ++i){
00340           vgpar.set_entry(static_cast<BCP_vg_par::chr_params>(i), false);
00341           }
00342         */
00343         tmpar.set_entry(BCP_tm_par::TmVerb_FinalStatistics, treestat);
00344         tmpar.set_entry(BCP_tm_par::TmVerb_BestFeasibleSolution, bestsol);
00345         if (tmpar.entry(BCP_tm_par::ReportWhenDefaultIsExecuted) == 2) {
00346             tmpar.set_entry(BCP_tm_par::ReportWhenDefaultIsExecuted, true);
00347         } else {
00348             tmpar.set_entry(BCP_tm_par::ReportWhenDefaultIsExecuted, false);
00349         }
00350         if (lppar.entry(BCP_lp_par::ReportWhenDefaultIsExecuted) == 2) {
00351             lppar.set_entry(BCP_lp_par::ReportWhenDefaultIsExecuted, true);
00352         } else {
00353             lppar.set_entry(BCP_lp_par::ReportWhenDefaultIsExecuted, false);
00354         }
00355         if (cgpar.entry(BCP_cg_par::ReportWhenDefaultIsExecuted) == 2) {
00356             cgpar.set_entry(BCP_cg_par::ReportWhenDefaultIsExecuted, true);
00357         } else {
00358             cgpar.set_entry(BCP_cg_par::ReportWhenDefaultIsExecuted, false);
00359         }
00360         if (vgpar.entry(BCP_vg_par::ReportWhenDefaultIsExecuted) == 2) {
00361             vgpar.set_entry(BCP_vg_par::ReportWhenDefaultIsExecuted, true);
00362         } else {
00363             vgpar.set_entry(BCP_vg_par::ReportWhenDefaultIsExecuted, false);
00364         }
00365     }
00366     if (p.param(BCP_tm_par::MaxHeapSize) == 0) {
00367         long fm = BCP_free_mem();
00368         fm = fm == -1 ? 192 * (1<<20) /* 192M */ : fm;
00369         p.par.set_entry(BCP_tm_par::MaxHeapSize, fm);
00370         p.slave_pars.ts.set_entry(BCP_ts_par::MaxHeapSize, fm);
00371     }
00372 }
00373 
00374 //#############################################################################
00375 // A little bit of sanity check
00376 
00377 void BCP_sanity_checks(BCP_tm_prob& p)
00378 {
00379 }
00380 

Generated on Thu Sep 22 03:05:52 2011 by  doxygen 1.4.7