X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/dee506dc59257b5afd49259f00de04913a2d3f29..759e00e7ad42a922ae00763324da351e5f196815:/src/surf/maxmin.cpp diff --git a/src/surf/maxmin.cpp b/src/surf/maxmin.cpp index b3b9103844..5d5cff5ae6 100644 --- a/src/surf/maxmin.cpp +++ b/src/surf/maxmin.cpp @@ -8,7 +8,6 @@ #include "xbt/sysdep.h" #include "xbt/log.h" -#include "xbt/strbuff.h" #include "xbt/mallocator.h" #include "maxmin_private.hpp" #include @@ -22,11 +21,11 @@ typedef struct s_dyn_light { int size; } s_dyn_light_t, *dyn_light_t; -double sg_maxmin_precision = 0.00001; -double sg_surf_precision = 0.00001; -int sg_concurrency_limit= 100; +double sg_maxmin_precision = 0.00001; /* Change this with --cfg=maxmin/precision:VALUE */ +double sg_surf_precision = 0.00001; /* Change this with --cfg=surf/precision:VALUE */ +int sg_concurrency_limit = -1; /* Change this with --cfg=maxmin/concurrency-limit:VALUE */ -static void *lmm_variable_mallocator_new_f(void); +static void *lmm_variable_mallocator_new_f(); static void lmm_variable_mallocator_free_f(void *var); #define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)nullptr) static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst); @@ -74,7 +73,7 @@ inline void lmm_increase_concurrency(lmm_element_t elem) { "Concurrency limit overflow!"); } -lmm_system_t lmm_system_new(int selective_update) +lmm_system_t lmm_system_new(bool selective_update) { lmm_system_t l = nullptr; s_lmm_variable_t var; @@ -102,6 +101,8 @@ lmm_system_t lmm_system_new(int selective_update) lmm_variable_mallocator_free_f, lmm_variable_mallocator_reset_f); + l->solve_fun = &lmm_solve; + return l; } @@ -110,7 +111,7 @@ void lmm_system_free(lmm_system_t sys) lmm_variable_t var = nullptr; lmm_constraint_t cnst = nullptr; - if (!sys) + if (sys == nullptr) return; while ((var = (lmm_variable_t) extract_variable(sys))) { @@ -148,7 +149,7 @@ static inline void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) xbt_swag_remove(elem, &(elem->constraint->active_element_set)); nelements=xbt_swag_size(&(elem->constraint->enabled_element_set)) + xbt_swag_size(&(elem->constraint->disabled_element_set)); - if (!nelements) + if (not nelements) make_constraint_inactive(sys, elem->constraint); else lmm_on_disabled_var(sys,elem->constraint); @@ -196,7 +197,7 @@ lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, double bound_val cnst->bound = bound_value; cnst->concurrency_maximum=0; cnst->concurrency_current=0; - cnst->concurrency_limit=sg_concurrency_limit; + cnst->concurrency_limit = sg_concurrency_limit; cnst->usage = 0; cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */ insert_constraint(sys, cnst); @@ -247,14 +248,15 @@ int lmm_constraint_sharing_policy(lmm_constraint_t cnst) */ inline void lmm_constraint_free(lmm_system_t sys,lmm_constraint_t cnst) { - xbt_assert(!xbt_swag_size(&(cnst->active_element_set)),"Removing constraint but it still has active elements"); - xbt_assert(!xbt_swag_size(&(cnst->enabled_element_set)),"Removing constraint but it still has enabled elements"); - xbt_assert(!xbt_swag_size(&(cnst->disabled_element_set)),"Removing constraint but it still has disabled elements"); + xbt_assert(not xbt_swag_size(&(cnst->active_element_set)), "Removing constraint but it still has active elements"); + xbt_assert(not xbt_swag_size(&(cnst->enabled_element_set)), "Removing constraint but it still has enabled elements"); + xbt_assert(not xbt_swag_size(&(cnst->disabled_element_set)), + "Removing constraint but it still has disabled elements"); remove_constraint(sys, cnst); lmm_cnst_free(sys, cnst); } -static void *lmm_variable_mallocator_new_f(void) +static void *lmm_variable_mallocator_new_f() { lmm_variable_t var = xbt_new(s_lmm_variable_t, 1); var->cnsts = nullptr; /* will be created by realloc */ @@ -267,7 +269,8 @@ static void lmm_variable_mallocator_free_f(void *var) xbt_free(var); } -lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, double weight, double bound, int number_of_constraints) +lmm_variable_t lmm_variable_new(lmm_system_t sys, simgrid::surf::Action* id, double weight, double bound, + int number_of_constraints) { lmm_variable_t var = nullptr; int i; @@ -352,7 +355,7 @@ void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var) } } - if (!found) { + if (not found) { XBT_DEBUG("cnst %p is not found in var %p", cnst, var); return; } @@ -418,7 +421,7 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, dou lmm_on_disabled_var(sys,var->cnsts[i].constraint); value=0; var->staged_weight=weight; - xbt_assert(!var->weight); + xbt_assert(not var->weight); } xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints"); @@ -435,7 +438,7 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, dou } else xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set)); - if(!sys->selective_update_active) { + if (not sys->selective_update_active) { make_constraint_active(sys, cnst); } else if(elem->value>0 || var->weight >0) { make_constraint_active(sys, cnst); @@ -478,7 +481,7 @@ void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, for (j = 0; j < var->cnsts_number; j++) lmm_on_disabled_var(sys,var->cnsts[j].constraint); var->staged_weight=weight; - xbt_assert(!var->weight); + xbt_assert(not var->weight); } lmm_increase_concurrency(&var->cnsts[i]); } @@ -512,18 +515,18 @@ int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/, lmm_variable_t var) lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/, lmm_constraint_t cnst, lmm_element_t * elem) { - if (!(*elem)) { + if (*elem == nullptr) { // That is the first call, pick the first element among enabled_element_set (or disabled_element_set if // enabled_element_set is empty) *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set)); - if (!(*elem)) + if (*elem == nullptr) *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); } else { //elem is not null, so we carry on if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){ //Look at enabled_element_set, and jump to disabled_element_set when finished *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset); - if (!(*elem)) + if (*elem == nullptr) *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); } else { *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset); @@ -540,10 +543,10 @@ lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/, lmm_constraint_t cnst lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/, lmm_constraint_t cnst, lmm_element_t * elem, lmm_element_t * nextelem, int * numelem) { - if (!(*elem)){ + if (*elem == nullptr) { *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set)); *numelem = xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set))-1; - if (!(*elem)) + if (*elem == nullptr) *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); }else{ *elem = *nextelem; @@ -557,7 +560,7 @@ lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/, lmm_constraint_t if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){ //Look at enabled_element_set, and jump to disabled_element_set when finished *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset); - if (!(*nextelem)) + if (*nextelem == nullptr) *nextelem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); } else { *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset); @@ -622,26 +625,27 @@ static inline void saturated_variable_set_update(s_lmm_constraint_light_t *cnst_ void lmm_print(lmm_system_t sys) { - void *_cnst, *_elem, *_var; + void* _cnst; + void* _elem; + void* _var; lmm_constraint_t cnst = nullptr; - lmm_element_t elem = nullptr; - lmm_variable_t var = nullptr; - xbt_swag_t cnst_list = nullptr; - xbt_swag_t var_list = nullptr; - xbt_swag_t elem_list = nullptr; - xbt_strbuff_t buf = xbt_strbuff_new(); + lmm_element_t elem = nullptr; + lmm_variable_t var = nullptr; + xbt_swag_t cnst_list = nullptr; + xbt_swag_t var_list = nullptr; + xbt_swag_t elem_list = nullptr; + std::string buf = std::string("MAX-MIN ( "); double sum = 0.0; /* Printing Objective */ var_list = &(sys->variable_set); - xbt_strbuff_append(buf, "MAX-MIN ( "); xbt_swag_foreach(_var, var_list) { var = (lmm_variable_t)_var; - xbt_strbuff_printf(buf, "'%d'(%f) ", var->id_int, var->weight); + buf = buf + "'" + std::to_string(var->id_int) + "'(" + std::to_string(var->weight) + ") "; } - xbt_strbuff_append(buf, ")"); - XBT_DEBUG("%20s", buf->data); - xbt_strbuff_clear(buf); + buf += ")"; + XBT_DEBUG("%20s", buf.c_str()); + buf.clear(); XBT_DEBUG("Constraints"); /* Printing Constraints */ @@ -651,12 +655,12 @@ void lmm_print(lmm_system_t sys) sum = 0.0; //Show the enabled variables elem_list = &(cnst->enabled_element_set); - xbt_strbuff_append(buf, "\t"); - xbt_strbuff_printf(buf, "%s(", (cnst->sharing_policy)?"":"max"); + buf += "\t"; + buf += ((cnst->sharing_policy) ? "(" : "max("); xbt_swag_foreach(_elem, elem_list) { elem = (lmm_element_t)_elem; - xbt_strbuff_printf(buf, "%f.'%d'(%f) %s ", elem->value, - elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":","); + buf = buf + std::to_string(elem->value) + ".'" + std::to_string(elem->variable->id_int) + "'(" + + std::to_string(elem->variable->value) + ")" + ((cnst->sharing_policy) ? " + " : " , "); if(cnst->sharing_policy) sum += elem->value * elem->variable->value; else @@ -666,25 +670,25 @@ void lmm_print(lmm_system_t sys) elem_list = &(cnst->disabled_element_set); xbt_swag_foreach(_elem, elem_list) { elem = (lmm_element_t)_elem; - xbt_strbuff_printf(buf, "%f.'%d'(%f) %s ", elem->value, - elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":","); + buf = buf + std::to_string(elem->value) + ".'" + std::to_string(elem->variable->id_int) + "'(" + + std::to_string(elem->variable->value) + ")" + ((cnst->sharing_policy) ? " + " : " , "); if(cnst->sharing_policy) sum += elem->value * elem->variable->value; else sum = MAX(sum,elem->value * elem->variable->value); } - xbt_strbuff_printf(buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int); + buf = buf + "0) <= " + std::to_string(cnst->bound) + " ('" + std::to_string(cnst->id_int) + "')"; - if (!cnst->sharing_policy) { - xbt_strbuff_printf(buf, " [MAX-Constraint]"); + if (not cnst->sharing_policy) { + buf += " [MAX-Constraint]"; } - XBT_DEBUG("%s", buf->data); - xbt_strbuff_clear(buf); - xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision), - "Incorrect value (%f is not smaller than %f): %g", sum, cnst->bound, sum - cnst->bound); - //if(double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision)) - //XBT_ERROR("Incorrect value (%f is not smaller than %f): %g",sum, cnst->bound, sum - cnst->bound); + XBT_DEBUG("%s", buf.c_str()); + buf.clear(); + xbt_assert(not double_positive(sum - cnst->bound, cnst->bound * sg_maxmin_precision), + "Incorrect value (%f is not smaller than %f): %g", sum, cnst->bound, sum - cnst->bound); + // if(double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision)) + // XBT_ERROR("Incorrect value (%f is not smaller than %f): %g",sum, cnst->bound, sum - cnst->bound); } XBT_DEBUG("Variables"); @@ -693,14 +697,12 @@ void lmm_print(lmm_system_t sys) var = (lmm_variable_t)_var; if (var->bound > 0) { XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value, var->bound); - xbt_assert(!double_positive(var->value - var->bound, var->bound*sg_maxmin_precision), - "Incorrect value (%f is not smaller than %f", var->value, var->bound); + xbt_assert(not double_positive(var->value - var->bound, var->bound * sg_maxmin_precision), + "Incorrect value (%f is not smaller than %f", var->value, var->bound); } else { XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value); } } - - xbt_strbuff_free(buf); } void lmm_solve(lmm_system_t sys) @@ -715,7 +717,7 @@ void lmm_solve(lmm_system_t sys) double min_usage = -1; double min_bound = -1; - if (!(sys->modified)) + if (not sys->modified) return; XBT_IN("(sys=%p)", sys); @@ -750,7 +752,7 @@ void lmm_solve(lmm_system_t sys) /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) * into cnst_light_tab. */ cnst->remaining = cnst->bound; - if (!double_positive(cnst->remaining, cnst->bound*sg_maxmin_precision)) + if (not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) continue; cnst->usage = 0; elem_list = &(cnst->enabled_element_set); @@ -765,7 +767,7 @@ void lmm_solve(lmm_system_t sys) make_elem_active(elem); simgrid::surf::Action *action = static_cast(elem->variable->id); - if (sys->keep_track && !action->is_linked()) + if (sys->keep_track && not action->is_linked()) sys->keep_track->push_back(*action); } } @@ -841,8 +843,8 @@ void lmm_solve(lmm_system_t sys) double_update(&(cnst->remaining), elem->value * var->value, cnst->bound*sg_maxmin_precision); double_update(&(cnst->usage), elem->value / var->weight, sg_maxmin_precision); //If the constraint is saturated, remove it from the set of active constraints (light_tab) - if(!double_positive(cnst->usage,sg_maxmin_precision) || - !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) { + if (not double_positive(cnst->usage, sg_maxmin_precision) || + not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) { if (cnst->cnst_light) { int index = (cnst->cnst_light-cnst_light_tab); XBT_DEBUG("index: %d \t cnst_light_num: %d \t || usage: %f remaining: %f bound: %f ", @@ -872,8 +874,8 @@ void lmm_solve(lmm_system_t sys) cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight); } //If the constraint is saturated, remove it from the set of active constraints (light_tab) - if(!double_positive(cnst->usage,sg_maxmin_precision) || - !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) { + if (not double_positive(cnst->usage, sg_maxmin_precision) || + not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) { if(cnst->cnst_light) { int index = (cnst->cnst_light-cnst_light_tab); XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p " @@ -965,7 +967,7 @@ int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){ //This is only an optimization, to avoid looking at more constraints when slack is already zero //Disable it when debugging to let lmm_concurrency_slack catch nasty things - if(!slack && !XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) + if (not slack && not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) return 0; if(minslack>slack) @@ -1020,7 +1022,7 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ int i; lmm_element_t elem; - xbt_assert(!var->staged_weight,"Staged weight should have been cleared"); + xbt_assert(not var->staged_weight, "Staged weight should have been cleared"); //Disabling the variable, move to var to list tail. Subtility is: here, we need to call lmm_update_modified_set BEFORE //moving the last element of var. xbt_swag_remove(var, &(sys->variable_set)); @@ -1051,23 +1053,20 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ * And then add it to enabled variables */ void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ - lmm_element_t elem; - lmm_element_t nextelem; - int numelem; if(cnstr->concurrency_limit<0) return; - numelem=xbt_swag_size(&(cnstr->disabled_element_set)); - if(!numelem) + int numelem = xbt_swag_size(&(cnstr->disabled_element_set)); + if (not numelem) return; - elem= (lmm_element_t) xbt_swag_getFirst(&(cnstr->disabled_element_set)); + lmm_element_t elem = (lmm_element_t)xbt_swag_getFirst(&(cnstr->disabled_element_set)); //Cannot use xbt_swag_foreach, because lmm_enable_var will modify disabled_element_set.. within the loop - while(numelem-- && elem ){ + while (numelem-- && elem) { - nextelem = (lmm_element_t) xbt_swag_getNext(elem, cnstr->disabled_element_set.offset); + lmm_element_t nextelem = (lmm_element_t)xbt_swag_getNext(elem, cnstr->disabled_element_set.offset); if (elem->variable->staged_weight>0 ){ //Found a staged variable @@ -1096,7 +1095,6 @@ void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ */ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double weight) { - int minslack; xbt_assert(weight>=0,"Variable weight should not be negative!"); @@ -1113,8 +1111,8 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double wei //Are we enabling this variable? if (enabling_var){ var->staged_weight = weight; - minslack=lmm_cnstrs_min_concurrency_slack(var); - if(minslackconcurrency_share){ + int minslack = lmm_cnstrs_min_concurrency_slack(var); + if (minslack < var->concurrency_share) { XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f and concurrency" " share %i", minslack, weight, var->concurrency_share); return; @@ -1131,7 +1129,6 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double wei lmm_check_concurrency(sys); XBT_OUT(); - return; } double lmm_get_variable_weight(lmm_variable_t var) @@ -1180,7 +1177,7 @@ static void lmm_update_modified_set_rec(lmm_system_t sys, lmm_constraint_t cnst) s_lmm_element_t *cnsts = var->cnsts; int i; for (i = 0; var->visited != sys->visited_counter && i < var->cnsts_number ; i++) { - if (cnsts[i].constraint != cnst && !xbt_swag_belongs(cnsts[i].constraint, &sys->modified_constraint_set)) { + if (cnsts[i].constraint != cnst && not xbt_swag_belongs(cnsts[i].constraint, &sys->modified_constraint_set)) { xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set); lmm_update_modified_set_rec(sys, cnsts[i].constraint); } @@ -1193,7 +1190,7 @@ static void lmm_update_modified_set_rec(lmm_system_t sys, lmm_constraint_t cnst) static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst) { /* nothing to do if selective update isn't active */ - if (sys->selective_update_active && !xbt_swag_belongs(cnst, &sys->modified_constraint_set)) { + if (sys->selective_update_active && not xbt_swag_belongs(cnst, &sys->modified_constraint_set)) { xbt_swag_insert(cnst, &sys->modified_constraint_set); lmm_update_modified_set_rec(sys, cnst); } @@ -1220,25 +1217,28 @@ static void lmm_remove_all_modified_set(lmm_system_t sys) } /** - * Returns total resource load + * Returns resource load (in flop per second, or byte per second, or similar) * - * \param cnst the lmm_constraint_t associated to the resource + * If the resource is shared (the default case), the load is sum of + * resource usage made by every variables located on this resource. * - * This is dead code, but we may use it later for debug/trace. + * If the resource is not shared (ie in FATPIPE mode), then the the + * load is the max (not the sum) of all resource usages located on this resource. + * . + * \param cnst the lmm_constraint_t associated to the resource */ double lmm_constraint_get_usage(lmm_constraint_t cnst) { double usage = 0.0; xbt_swag_t elem_list = &(cnst->enabled_element_set); void *_elem; - lmm_element_t elem = nullptr; xbt_swag_foreach(_elem, elem_list) { - elem = (lmm_element_t)_elem; - if ((elem->value > 0)) { + lmm_element_t elem = (lmm_element_t)_elem; + if (elem->value > 0) { if (cnst->sharing_policy) usage += elem->value * elem->variable->value; else if (usage < elem->value * elem->variable->value) - usage = elem->value * elem->variable->value; + usage = std::max(usage, elem->value * elem->variable->value); } } return usage; @@ -1281,7 +1281,7 @@ void lmm_check_concurrency(lmm_system_t sys){ xbt_swag_foreach(_var, &(sys->variable_set)) { var= (lmm_variable_t) _var; - if(!var->cnsts_number) + if (not var->cnsts_number) continue; elem = &var->cnsts[0];