static int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var);
static void lmm_check_concurrency(lmm_system_t sys);
-
-inline void lmm_decrease_concurrency(lmm_constraint_t cnstr){
- xbt_assert(cnstr->concurrency_current>0);
- cnstr->concurrency_current--;
+
+inline int lmm_element_concurrency(lmm_element_t elem) {
+ //Ignore element with weight less than one (e.g. cross-traffic)
+ return (elem->value>=1)?1:0;
+ //There are other alternatives, but they will change the behaviour of the model..
+ //So do not use it unless you want to make a new model.
+ //If you do, remember to change the variables concurrency share to reflect it.
+ //Potential examples are:
+ //return (elem->weight>0)?1:0;//Include element as soon as weight is non-zero
+ //return (int)ceil(elem->weight);//Include element as the rounded-up integer value of the element weight
+}
+
+inline void lmm_decrease_concurrency(lmm_element_t elem) {
+ xbt_assert(elem->constraint->concurrency_current>=lmm_element_concurrency(elem));
+ elem->constraint->concurrency_current-=lmm_element_concurrency(elem);
}
-inline void lmm_increase_concurrency(lmm_constraint_t cnstr){
- if(++cnstr->concurrency_current > cnstr->concurrency_maximum)
- cnstr->concurrency_maximum=cnstr->concurrency_current;
+inline void lmm_increase_concurrency(lmm_element_t elem) {
+
+ elem->constraint->concurrency_current+= lmm_element_concurrency(elem);
+
+ lmm_constraint_t cnstr=elem->constraint;
+
+ if(cnstr->concurrency_current > cnstr->concurrency_maximum)
+ cnstr->concurrency_maximum= cnstr->concurrency_current;
+
xbt_assert(cnstr->concurrency_limit<0 || cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency limit overflow!");
}
for (i = 0; i < var->cnsts_number; i++) {
elem = &var->cnsts[i];
if(var->weight>0)
- lmm_decrease_concurrency(elem->constraint);
+ lmm_decrease_concurrency(elem);
xbt_swag_remove(elem, &(elem->constraint->enabled_element_set));
xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
xbt_swag_remove(elem, &(elem->constraint->active_element_set));
xbt_swag_size(&(elem->constraint->disabled_element_set));
if (!nelements)
make_constraint_inactive(sys, elem->constraint);
- //Check if we can enable new variables going through the constraints where var was.
else
lmm_on_disabled_var(sys,elem->constraint);
}
-
+
+ //Check if we can enable new variables going through the constraints where var was.
+ //Do it after removing all elements, so he first disabled variables get priority over those with smaller
+ //requirement
+ for (i = 0; i < var->cnsts_number; i++) {
+ elem = &var->cnsts[i];
+ if(xbt_swag_size(&(elem->constraint->disabled_element_set)))
+ lmm_on_disabled_var(sys,elem->constraint);
+ }
+
var->cnsts_number = 0;
+
+ lmm_check_concurrency(sys);
+
XBT_OUT();
}
return cnst;
}
+int lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst)
+{
+ return cnst->concurrency_limit;
+}
+
void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit)
{
+ xbt_assert(concurrency_limit<0 || cnst->concurrency_maximum<=concurrency_limit,"New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call lmm_constraint_concurrency_maximum_reset() to reset the maximum?");
cnst->concurrency_limit = concurrency_limit;
}
int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst)
{
+ xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_maximum<=cnst->concurrency_limit,"Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it.");
return cnst->concurrency_maximum;
}
lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up enabled_element_set of this constraint, and then each var in the enabled_element_set, and each var->cnsts[i].
if(xbt_swag_remove(elem, &(elem->constraint->enabled_element_set)))
- lmm_decrease_concurrency(elem->constraint);
+ lmm_decrease_concurrency(elem);
xbt_swag_remove(elem, &(elem->constraint->active_element_set));
elem->constraint = NULL;
{
lmm_element_t elem = NULL;
double weight;
- int i;
+ int i,current_share;
+
sys->modified = 1;
- if(var->weight>0 && lmm_concurrency_slack(cnst)==0){
+ //Check if this variable already has an active element in this constraint
+ //If it does, substract it from the required slack
+ current_share=0;
+ if(var->concurrency_share>1){
+ for( i=0; i<var->cnsts_number;i++){
+ if(var->cnsts[i].constraint==cnst && xbt_swag_belongs(&var->cnsts[i],&(var->cnsts[i].constraint->enabled_element_set)))
+ current_share+=lmm_element_concurrency(&(var->cnsts[i]));
+ }
+ }
+
+ //Check if we need to disable the variable
+ if(var->weight>0 && var->concurrency_share-current_share>lmm_concurrency_slack(cnst))
+ {
weight=var->weight;
lmm_disable_var(sys,var);
for (i = 0; i < var->cnsts_number; i++)
if (var->weight){
xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
- lmm_increase_concurrency(elem->constraint);
+ lmm_increase_concurrency(elem);
}
else
xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
lmm_variable_t var, double value)
{
- int i;
+ int i,j;
+ double weight;
sys->modified = 1;
-
+
lmm_check_concurrency(sys);
+ //BEWARE: In case you have multiple elements in one constraint, this will always
+ //add value to the first element.
for (i = 0; i < var->cnsts_number; i++)
if (var->cnsts[i].constraint == cnst)
break;
if (i < var->cnsts_number) {
+ if (var->weight)
+ lmm_decrease_concurrency(&var->cnsts[i]);
+
if (cnst->sharing_policy)
var->cnsts[i].value += value;
else
var->cnsts[i].value = MAX(var->cnsts[i].value, value);
+
+ //We need to check that increasing value of the element does not cross the concurrency limit
+ if (var->weight){
+ if(lmm_concurrency_slack(cnst)<lmm_element_concurrency(&var->cnsts[i])){
+ weight=var->weight;
+ lmm_disable_var(sys,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);
+ }
+ lmm_increase_concurrency(&var->cnsts[i]);
+ }
+
lmm_update_modified_set(sys, cnst);
} else
lmm_expand(sys, cnst, var, value);
lmm_print(sys);
}
+ lmm_check_concurrency(sys);
+
xbt_free(saturated_constraint_set->data);
xbt_free(saturated_constraint_set);
xbt_free(cnst_light_tab);
int lmm_concurrency_slack(lmm_constraint_t cnstr){
- xbt_assert(xbt_swag_size(&(cnstr->enabled_element_set))==cnstr->concurrency_current,"concurrency_current is not up to date!");
-
//FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
if(cnstr->concurrency_limit<0)
return 666;
elem = &var->cnsts[i];
xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
- lmm_increase_concurrency(elem->constraint);
+ lmm_increase_concurrency(elem);
}
if (var->cnsts_number)
lmm_update_modified_set(sys, var->cnsts[0].constraint);
- lmm_check_concurrency(sys);
+ //When used within lmm_on_disabled_var, we would get an assertion fail, because transiently there can be variables that are staged and could be activated.
+ //Anyway, caller functions all call lmm_check_concurrency() in the end.
+ // lmm_check_concurrency(sys);
}
void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){
xbt_swag_remove(elem, &(elem->constraint->active_element_set));
- lmm_decrease_concurrency(elem->constraint);
+ lmm_decrease_concurrency(elem);
}
var->weight=0.0;
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;
-
- int concurrency=cnstr->concurrency_current;
- xbt_swag_foreach(elem, &(cnstr->disabled_element_set)) {
+
+ numelem=xbt_swag_size(&(cnstr->disabled_element_set));
+ if(!numelem)
+ return;
+
+ 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 ){
+
+ nextelem = (lmm_element_t) xbt_swag_getNext(elem, cnstr->disabled_element_set.offset);
if (elem->variable->staged_weight>0 )
{
- //Found a staged variable
- //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called?
- if(lmm_can_enable_var(elem->variable)){
- lmm_enable_var(sys,elem->variable);
- concurrency++;
- }
+ //Found a staged variable
+ //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called?
+ if(lmm_can_enable_var(elem->variable)){
+ lmm_enable_var(sys,elem->variable);
+ }
}
- xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!");
- if(concurrency==cnstr->concurrency_limit)
+ xbt_assert(cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency overflow!");
+ if(cnstr->concurrency_current==cnstr->concurrency_limit)
break;
+
+ elem = nextelem;
}
- lmm_check_concurrency(sys);
+ //We could get an assertion fail, because transiently there can be variables that are staged and could be activated.
+ //And we need to go through all constraints of the disabled var before getting back a coherent state.
+ //Anyway, caller functions all call lmm_check_concurrency() in the end.
+ // lmm_check_concurrency(sys);
}
if (enabling_var){
var->staged_weight = weight;
minslack=lmm_cnstrs_min_concurrency_slack(var);
- if(minslack==0){
- XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight);
+ 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;
}
XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
void *_var;
xbt_swag_foreach(_var, &sys->variable_set)
((lmm_variable_t)_var)->visited = 0;
- }
+ }
xbt_swag_reset(&sys->modified_constraint_set);
}
void lmm_check_concurrency(lmm_system_t sys){
void* _cnst;
void* _elem;
+ void* _var;
lmm_element_t elem;
lmm_constraint_t cnst;
+ lmm_variable_t var;
int concurrency;
-
+ int i,belong_to_enabled,belong_to_disabled,belong_to_active;
+
//These checks are very expensive, so do them only if we want to debug SURF LMM
if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
xbt_swag_foreach(_cnst, &(sys->constraint_set)) {
cnst = (lmm_constraint_t) _cnst;
concurrency=0;
-
xbt_swag_foreach(_elem, &(cnst->enabled_element_set)) {
- elem = (lmm_element_t)_elem;
- xbt_assert(elem->variable->weight > 0);
- concurrency++;
+ elem = (lmm_element_t)_elem;
+ xbt_assert(elem->variable->weight > 0);
+ concurrency+=lmm_element_concurrency(elem);
}
-
+
xbt_swag_foreach(_elem, &(cnst->disabled_element_set)) {
elem = (lmm_element_t)_elem;
- //We should have staged variables only if conccurency is reached in some constraint
+ //We should have staged variables only if concurrency is reached in some constraint
xbt_assert(cnst->concurrency_limit<0 || elem->variable->staged_weight==0 || lmm_cnstrs_min_concurrency_slack(elem->variable) < elem->variable->concurrency_share,"should not have staged variable!");
}
xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_limit >= concurrency,"concurrency check failed!");
xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!");
- xbt_assert(cnst->concurrency_current == xbt_swag_size(&(cnst->enabled_element_set)), "concurrency_current is out-of-date (2) !");
-
}
+
+ //Check that for each variable, all corresponding elements are in the same state (i.e. same element sets)
+ xbt_swag_foreach(_var, &(sys->variable_set)) {
+ var= (lmm_variable_t) _var;
+
+ if(!var->cnsts_number)
+ continue;
+
+ elem = &var->cnsts[0];
+ belong_to_enabled=xbt_swag_belongs(elem,&(elem->constraint->enabled_element_set));
+ belong_to_disabled=xbt_swag_belongs(elem,&(elem->constraint->disabled_element_set));
+ belong_to_active=xbt_swag_belongs(elem,&(elem->constraint->active_element_set));
+
+ for (i = 1; i < var->cnsts_number; i++) {
+ elem = &var->cnsts[i];
+ xbt_assert(belong_to_enabled==xbt_swag_belongs(elem,&(elem->constraint->enabled_element_set)),
+ "Variable inconsistency (1): enabled_element_set");
+ xbt_assert(belong_to_disabled==xbt_swag_belongs(elem,&(elem->constraint->disabled_element_set)),
+ "Variable inconsistency (2): disabled_element_set");
+ xbt_assert(belong_to_active==xbt_swag_belongs(elem,&(elem->constraint->active_element_set)),
+ "Variable inconsistency (3): active_element_set");
+ }
+
+ }
}
}
return (int) (((max * 1.0) * rand()) / (RAND_MAX + 1.0));
}
-void test(int nb_cnst, int nb_var, int nb_elem);
-void test(int nb_cnst, int nb_var, int nb_elem)
+void test(int nb_cnst, int nb_var, int nb_elem, int pw_base_limit, int pw_max_limit, float rate_no_limit, int max_share, int testmode);
+void test(int nb_cnst, int nb_var, int nb_elem, int pw_base_limit, int pw_max_limit, float rate_no_limit, int max_share, int testmode)
{
lmm_system_t Sys = NULL;
lmm_constraint_t *cnst = xbt_new0(lmm_constraint_t, nb_cnst);
lmm_variable_t *var = xbt_new0(lmm_variable_t, nb_var);
int *used = xbt_new0(int, nb_cnst);
- int i, j, k;
-
+ int i, j, k,l;
+ int concurrency_share;
+
Sys = lmm_system_new(1);
for (i = 0; i < nb_cnst; i++) {
cnst[i] = lmm_constraint_new(Sys, NULL, float_random(10.0));
+ if(rate_no_limit>float_random(1.0))
+ //Look at what happens when there is no concurrency limit
+ l=-1;
+ else
+ //Badly logarithmically random concurrency limit in [2^pw_base_limit+1,2^pw_base_limit+2^pw_max_limit]
+ l=(1<<pw_base_limit)+(1<<int_random(pw_max_limit));
+
+ lmm_constraint_concurrency_limit_set(cnst[i],l );
}
-
+
for (i = 0; i < nb_var; i++) {
var[i] = lmm_variable_new(Sys, NULL, 1.0, -1.0, nb_elem);
+ //Have a few variables with a concurrency share of two (e.g. cross-traffic in some cases)
+ concurrency_share=1+int_random(max_share);
+ lmm_variable_concurrency_share_set(var[i],concurrency_share);
+
for (j = 0; j < nb_cnst; j++)
used[j] = 0;
for (j = 0; j < nb_elem; j++) {
k = int_random(nb_cnst);
- if (used[k]) {
+ if (used[k]>=concurrency_share) {
j--;
continue;
}
- lmm_expand(Sys, cnst[k], var[i], float_random(1.0));
- used[k] = 1;
+ lmm_expand(Sys, cnst[k], var[i], float_random(1.5));
+ lmm_expand_add(Sys, cnst[k], var[i], float_random(1.5));
+ used[k]++;
}
}
lmm_solve(Sys);
date = xbt_os_time() * 1000000 - date;
+ if(testmode){
+ printf("Max concurrency:\n");
+ l=0;
+ for (i = 0; i < nb_cnst; i++) {
+ j=lmm_constraint_concurrency_maximum_get(cnst[i]);
+ k=lmm_constraint_concurrency_limit_get(cnst[i]);
+ xbt_assert(k<0 || j<=k);
+ if(j>l)
+ l=j;
+ printf("(%i):%i/%i ",i,j,k);
+ lmm_constraint_concurrency_maximum_reset(cnst[i]);
+ xbt_assert(!lmm_constraint_concurrency_maximum_get(cnst[i]));
+ if(i%10==9)
+ printf("\n");
+ }
+ printf("\nTotal maximum concurrency is %i\n",l);
+
+ lmm_print(Sys);
+ }
+
for (i = 0; i < nb_var; i++)
lmm_variable_free(Sys, var[i]);
lmm_system_free(Sys);
free(cnst);
free(var);
free(used);
+
}
+int TestClasses [][4]=
+ //Nbcnst Nbvar Baselimit Maxlimit
+ {{ 10 ,10 ,1 ,2 }, //small
+ { 100 ,100 ,3 ,6 }, //medium
+ { 2000,2000 ,5 ,8 }, //big
+ { 20000,20000 ,7 ,10} //huge
+ };
+
int main(int argc, char **argv)
{
- int nb_cnst = 2000;
- int nb_var = 2000;
- int nb_elem = 80;
+ int nb_cnst, nb_var,nb_elem,pw_base_limit,pw_max_limit,max_share;
+ float rate_no_limit=0.2;
+ float acc_date=0,acc_date2=0;
+ int testclass,testmode,testcount;
+ int i;
+
+ if(argc<3) {
+ printf("Syntax: <small|medium|big|huge> <count> [test]\n");
+ return -1;
+ }
+
+ //what class?
+ if(!strcmp(argv[1],"small"))
+ testclass=0;
+ else if(!strcmp(argv[1],"medium"))
+ testclass=1;
+ else if(!strcmp(argv[1],"big"))
+ testclass=2;
+ else if(!strcmp(argv[1],"huge"))
+ testclass=3;
+ else {
+ printf("Unknown class \"%s\", aborting!\n",argv[1]);
+ return -2;
+ }
+
+ //How many times?
+ testcount=atoi(argv[2]);
+
+ //Show me everything!
+ testmode=(argc>=4 && strcmp(argv[3],"test")==0);
+
+ if(testmode)
+ xbt_log_control_set("surf/maxmin.threshold:DEBUG surf.threshold:DEBUG");
+
+ nb_cnst= TestClasses[testclass][0];
+ nb_var= TestClasses[testclass][1];
+ pw_base_limit= TestClasses[testclass][2];
+ pw_max_limit= TestClasses[testclass][3];
+ max_share=2; //1<<(pw_base_limit/2+1);
+
+ //If you want to test concurrency, you need nb_elem >> 2^pw_base_limit:
+ nb_elem= (1<<pw_base_limit)+(1<<(8*pw_max_limit/10));
+ //Otherwise, just set it to a constant value (and set rate_no_limit to 1.0):
+ //nb_elem=200
+
xbt_init(&argc, argv);
- date = xbt_os_time() * 1000000;
- test(nb_cnst, nb_var, nb_elem);
- printf("One shot execution time for a total of %d constraints, "
- "%d variables with %d active constraint each : %g microsecondes \n",
- nb_cnst, nb_var, nb_elem, date);
+
+ for(i=0;i<testcount;i++){
+ test(nb_cnst, nb_var, nb_elem, pw_base_limit, pw_max_limit, rate_no_limit,max_share,testmode);
+ acc_date+=date;
+ acc_date2+=date*date;
+ }
+
+ float mean_date= acc_date/(float)testcount;
+ float stdev_date= sqrt(acc_date2/(float)testcount-mean_date*mean_date);
+
+ printf("%ix One shot execution time for a total of %d constraints, "
+ "%d variables with %d active constraint each, concurrency in [%i,%i] and max concurrency share %i: %g +- %g microseconds \n",
+ testcount,nb_cnst, nb_var, nb_elem, (1<<pw_base_limit), (1<<pw_base_limit)+(1<<pw_max_limit), max_share, mean_date, stdev_date);
return 0;
}
