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->element_set));
++ 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));
- nelements=xbt_swag_size(&(elem->constraint->element_set));
+ nelements=xbt_swag_size(&(elem->constraint->enabled_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();
}
*/
lmm_update_modified_set(sys, cnst);
//Useful in case var was already removed from the constraint
- lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up element_set of this constraint, and then each var in the element_set, and each var->cnsts[i].
+ 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->element_set)) && var->weight>0)
+ 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->element_set));
+ 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->element_set));
+ xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
if(!sys->selective_update_active) {
make_constraint_active(sys, cnst);
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!");
- int slack;
- int concurrency=0;
- void* _elem;
- lmm_element_t elem;
--
//FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
if(cnstr->concurrency_limit<0)
return 666;
xbt_swag_insert_at_head(var, &(sys->variable_set));
for (i = 0; i < var->cnsts_number; i++) {
elem = &var->cnsts[i];
- xbt_swag_remove(elem, &(elem->constraint->element_set));
- xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
+ 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){
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)) {
- int concurrency=0;
- xbt_swag_foreach(elem, &(cnstr->element_set)) {
-
- //active variables are checked to see if we already reached the maximum (SHOULD NOT HAPPEN BECAUSE WE SHOULD HAVE JUST DEACTIVATED ONE)
- if (elem->variable->weight > 0){
- concurrency+=lmm_element_concurrency(elem);
- xbt_assert(elem->variable->staged_weight==0.0,"Staged weight should have been reset");
- } else if (elem->variable->staged_weight>0 )
++
++ 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);
- concurrency+=lmm_element_concurrency(elem);
- }
++ }
}
-- 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);
//To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that were in the modified a long (long long) time ago are not wrongly skipped here, which would lead to very nasty bugs (i.e. not readibily reproducible, and requiring a lot of run time before happening).
if (++sys->visited_counter == 1) {
/* the counter wrapped around, reset each variable->visited */
- void *_var;
+ 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;
-
- if(cnst->concurrency_limit<0)
- continue;
- xbt_swag_foreach(_elem, &(cnst->element_set)) {
+ 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;
- if (elem->variable->weight > 0)
- concurrency+=lmm_element_concurrency(elem);
- else {
- //We should have staged variables only if conccurency 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(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);
-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)
++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);
- lmm_variable_concurrency_share_set(var[i],1+int_random(max_share));
+ //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;
- 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);
++ 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);
++ 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_elem;
- int pw_base_limit=5;
- int pw_max_limit=8;
++ int nb_cnst, nb_var,nb_elem,pw_base_limit,pw_max_limit,max_share;
+ float rate_no_limit=0.2;
- int max_share=1<<(pw_base_limit/2+1);
++ 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);
- test(nb_cnst, nb_var, nb_elem, pw_base_limit, pw_max_limit, rate_no_limit,max_share);
-- printf("One shot execution time for a total of %d constraints, "
- "%d variables with %d active constraint each : %g microsecondes \n",
- "%d variables with %d active constraint each : %g microseconds \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;
}
