From 919aa0b38b1c25ae816a6659555f4ffe4387a25a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Paul=20B=C3=A9daride?= Date: Thu, 8 Aug 2013 17:42:04 +0200 Subject: [PATCH] Make surf++ compile --- CMakeLists.txt | 5 +- buildtools/Cmake/DefinePackages.cmake | 11 +- src/include/surf/datatypes.h | 6 - src/include/surf/maxmin.h | 130 ---- src/include/surf/surf.h | 1 + src/include/surf/trace_mgr.h | 2 +- src/msg/msg_private.h | 1 + src/simdag/private.h | 1 + src/simgrid/sg_config.c | 3 +- src/simix/smx_private.h | 1 + src/surf/cpu_cas01.c | 2 +- src/surf/fair_bottleneck.c | 181 ------ src/surf/fair_bottleneck.cpp | 192 ++++++ src/surf/{lagrange.c => lagrange.cpp} | 260 ++++---- src/surf/maxmin.c | 891 -------------------------- src/surf/maxmin_private.h | 3 +- src/surf/network.c | 2 +- src/surf/network_ns3.c | 3 +- src/surf/solver.cpp | 735 +++++++++++++++++++++ src/surf/solver.h | 153 +++++ src/surf/solver.hpp | 174 +++++ src/surf/solver_c.cpp | 159 +++++ src/surf/storage.c | 7 +- src/surf/surf_private.h | 2 +- 24 files changed, 1581 insertions(+), 1344 deletions(-) delete mode 100644 src/include/surf/maxmin.h delete mode 100644 src/surf/fair_bottleneck.c create mode 100644 src/surf/fair_bottleneck.cpp rename src/surf/{lagrange.c => lagrange.cpp} (71%) delete mode 100644 src/surf/maxmin.c create mode 100644 src/surf/solver.cpp create mode 100644 src/surf/solver.h create mode 100644 src/surf/solver.hpp create mode 100644 src/surf/solver_c.cpp diff --git a/CMakeLists.txt b/CMakeLists.txt index a1b4f44744..d7a0107d45 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -7,6 +7,9 @@ project(SimGrid C) if (enable_gtnets OR enable_ns3) enable_language(CXX) endif() + +enable_language(CXX) + if (NOT DEFINED enable_smpi OR enable_smpi) # smpi is enabled by default # Call enable_language(Fortran) in order to load the build rules for # this language, needed by teshsuite/smpi/mpich-test/. Use @@ -32,7 +35,7 @@ if (NOT DEFINED enable_smpi OR enable_smpi) # smpi is enabled by default endif() set(CMAKE_C_FLAGS "" CACHE TYPE INTERNAL FORCE) -set(CMAKE_CXX_FLAGS "" CACHE TYPE INTERNAL FORCE) +set(CMAKE_CXX_FLAGS " -std=c++11 " CACHE TYPE INTERNAL FORCE) set(CMAKE_EXE_LINKER_FLAGS "" CACHE TYPE INTERNAL FORCE) set(CMAKE_C_LINK_FLAGS "" CACHE TYPE INTERNAL FORCE) set(CMAKE_Fortran_FLAGS "" CACHE TYPE INTERNAL FORCE) diff --git a/buildtools/Cmake/DefinePackages.cmake b/buildtools/Cmake/DefinePackages.cmake index f8436b725c..faa5eb4272 100644 --- a/buildtools/Cmake/DefinePackages.cmake +++ b/buildtools/Cmake/DefinePackages.cmake @@ -10,7 +10,6 @@ set(EXTRA_DIST src/include/simgrid/sg_config.h src/include/smpi/smpi_interface.h src/include/surf/datatypes.h - src/include/surf/maxmin.h src/include/surf/random_mgr.h src/include/surf/surf.h src/include/surf/surf_resource.h @@ -45,7 +44,10 @@ set(EXTRA_DIST src/surf/gtnets/gtnets_interface.h src/surf/gtnets/gtnets_simulator.h src/surf/gtnets/gtnets_topology.h + src/surf/solver.hpp + src/surf/solver.h src/surf/maxmin_private.h + src/surf/maxmin_private_.h src/surf/network_gtnets_private.h src/surf/network_ns3_private.h src/surf/network_private.h @@ -284,11 +286,12 @@ set(NS3_SRC set(SURF_SRC src/surf/cpu_cas01.c src/surf/cpu_ti.c - src/surf/fair_bottleneck.c + src/surf/fair_bottleneck.cpp src/surf/instr_routing.c src/surf/instr_surf.c - src/surf/lagrange.c - src/surf/maxmin.c + src/surf/lagrange.cpp + src/surf/solver.cpp + src/surf/solver_c.cpp src/surf/network.c src/surf/network_constant.c src/surf/platf_generator.c diff --git a/src/include/surf/datatypes.h b/src/include/surf/datatypes.h index 3171b355f0..1cb5edf5b1 100644 --- a/src/include/surf/datatypes.h +++ b/src/include/surf/datatypes.h @@ -25,12 +25,6 @@ typedef struct surf_action *surf_action_t; typedef struct surf_file *surf_file_t; typedef struct surf_stat *surf_stat_t; -typedef struct lmm_element *lmm_element_t; -typedef struct lmm_variable *lmm_variable_t; -typedef struct lmm_constraint *lmm_constraint_t; -typedef struct lmm_constraint_light *lmm_constraint_light_t; -typedef struct lmm_system *lmm_system_t; - typedef struct tmgr_history *tmgr_history_t; typedef struct tmgr_trace_event *tmgr_trace_event_t; diff --git a/src/include/surf/maxmin.h b/src/include/surf/maxmin.h deleted file mode 100644 index 5445c62471..0000000000 --- a/src/include/surf/maxmin.h +++ /dev/null @@ -1,130 +0,0 @@ -/* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#ifndef _SURF_MAXMIN_H -#define _SURF_MAXMIN_H - -#include "portable.h" -#include "xbt/misc.h" -#include "surf/datatypes.h" -#include - -extern double sg_maxmin_precision; -#define MAXMIN_PRECISION sg_maxmin_precision -static XBT_INLINE void double_update(double *variable, double value) -{ - *variable -= value; - if (*variable < MAXMIN_PRECISION) - *variable = 0.0; -} - -static XBT_INLINE int double_positive(double value) -{ - return (value > MAXMIN_PRECISION); -} - -static XBT_INLINE int double_equals(double value1, double value2) -{ - return (fabs(value1 - value2) < MAXMIN_PRECISION); -} - -XBT_PUBLIC(lmm_system_t) lmm_system_new(int selective_update); -XBT_PUBLIC(void) lmm_system_free(lmm_system_t sys); -void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var); - -XBT_PUBLIC(lmm_constraint_t) lmm_constraint_new(lmm_system_t sys, void *id, - double bound_value); -void lmm_constraint_shared(lmm_constraint_t cnst); -int lmm_constraint_is_shared(lmm_constraint_t cnst); - -void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst); - -XBT_PUBLIC(lmm_variable_t) lmm_variable_new(lmm_system_t sys, void *id, - double weight_value, - double bound, - int number_of_constraints); -XBT_PUBLIC(void) lmm_variable_free(lmm_system_t sys, lmm_variable_t var); -XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var); -XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var); - -XBT_PUBLIC(void) lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value); -void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value); -void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value); - -lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, - lmm_variable_t var, int num); -double lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var, - int num); -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); - -lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys); -lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, - lmm_constraint_t cnst); -#ifdef HAVE_LATENCY_BOUND_TRACKING -XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var); -#endif - -void *lmm_constraint_id(lmm_constraint_t cnst); -void *lmm_variable_id(lmm_variable_t var); - -void lmm_update(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value); -void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, - double bound); - - -XBT_PUBLIC(void) lmm_update_variable_weight(lmm_system_t sys, - lmm_variable_t var, - double weight); -double lmm_get_variable_weight(lmm_variable_t var); - -XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys, - lmm_constraint_t cnst, - double bound); - -int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst); - - -XBT_PUBLIC(void) lmm_solve(lmm_system_t sys); - -XBT_PUBLIC(void) lagrange_solve(lmm_system_t sys); -XBT_PUBLIC(void) bottleneck_solve(lmm_system_t sys); - -/** - * Default functions associated to the chosen protocol. When - * using the lagrangian approach. - */ - -XBT_PUBLIC(void) lmm_set_default_protocol_function(double (*func_f) - (lmm_variable_t var, - double x), - double (*func_fp) - (lmm_variable_t var, - double x), - double (*func_fpi) - (lmm_variable_t var, - double x)); - -XBT_PUBLIC(double func_reno_f) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_reno_fp) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_reno_fpi) (lmm_variable_t var, double x); - -XBT_PUBLIC(double func_reno2_f) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_reno2_fp) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_reno2_fpi) (lmm_variable_t var, double x); - -XBT_PUBLIC(double func_vegas_f) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_vegas_fp) (lmm_variable_t var, double x); -XBT_PUBLIC(double func_vegas_fpi) (lmm_variable_t var, double x); - - -#endif /* _SURF_MAXMIN_H */ diff --git a/src/include/surf/surf.h b/src/include/surf/surf.h index 3b684fed50..6290d615f6 100644 --- a/src/include/surf/surf.h +++ b/src/include/surf/surf.h @@ -16,6 +16,7 @@ #include "xbt/config.h" #include "surf/datatypes.h" #include "xbt/lib.h" +#include "surf/solver.h" #include "surf/surf_routing.h" #include "simgrid/platf_interface.h" diff --git a/src/include/surf/trace_mgr.h b/src/include/surf/trace_mgr.h index c9961a601b..1ec1d95979 100644 --- a/src/include/surf/trace_mgr.h +++ b/src/include/surf/trace_mgr.h @@ -9,7 +9,7 @@ #include "xbt/heap.h" #include "xbt/dynar.h" -#include "surf/maxmin.h" +#include "surf/solver.h" #include "surf/datatypes.h" #include "simgrid/platf_interface.h" diff --git a/src/msg/msg_private.h b/src/msg/msg_private.h index 02af63d702..4d8150077c 100644 --- a/src/msg/msg_private.h +++ b/src/msg/msg_private.h @@ -9,6 +9,7 @@ #include "msg/msg.h" #include "simgrid/simix.h" +#include "surf/solver.h" #include "surf/surf.h" #include "xbt/fifo.h" #include "xbt/dynar.h" diff --git a/src/simdag/private.h b/src/simdag/private.h index e48de288e1..e0bb1e0e1f 100644 --- a/src/simdag/private.h +++ b/src/simdag/private.h @@ -12,6 +12,7 @@ #include "xbt/fifo.h" #include "simdag/simdag.h" #include "simdag/datatypes.h" +#include "surf/solver.h" #include "surf/surf.h" #include "xbt/swag.h" #include "xbt/mallocator.h" diff --git a/src/simgrid/sg_config.c b/src/simgrid/sg_config.c index 3022b610d4..0871374063 100644 --- a/src/simgrid/sg_config.c +++ b/src/simgrid/sg_config.c @@ -13,8 +13,9 @@ #include "xbt/str.h" #include "xbt/lib.h" #include "xbt/sysdep.h" +#include "surf/solver.h" #include "surf/surf.h" -#include "surf/maxmin.h" +#include "surf/solver.h" #include "instr/instr_interface.h" #include "simgrid/simix.h" #include "simgrid/sg_config.h" diff --git a/src/simix/smx_private.h b/src/simix/smx_private.h index 1130ff9329..f15d3c123b 100644 --- a/src/simix/smx_private.h +++ b/src/simix/smx_private.h @@ -8,6 +8,7 @@ #define _SIMIX_PRIVATE_H #include "simgrid/simix.h" +#include "surf/solver.h" #include "surf/surf.h" #include "xbt/fifo.h" #include "xbt/swag.h" diff --git a/src/surf/cpu_cas01.c b/src/surf/cpu_cas01.c index f704612a5c..53b1e30b64 100644 --- a/src/surf/cpu_cas01.c +++ b/src/surf/cpu_cas01.c @@ -409,7 +409,7 @@ static void surf_cpu_model_init_internal() surf_action_lmm_update_index_heap); surf_cpu_model->model_private->modified_set = xbt_swag_new(xbt_swag_offset(comp, generic_lmm_action.action_list_hookup)); - surf_cpu_model->model_private->maxmin_system->keep_track = surf_cpu_model->model_private->modified_set; + //TOREPAIR: cpu_model->model_private->maxmin_system->m_keepTrack = cpu_model->model_private->modified_set; } } diff --git a/src/surf/fair_bottleneck.c b/src/surf/fair_bottleneck.c deleted file mode 100644 index aa9c4fa634..0000000000 --- a/src/surf/fair_bottleneck.c +++ /dev/null @@ -1,181 +0,0 @@ -/* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - - -#include "xbt/sysdep.h" -#include "xbt/log.h" -#include "maxmin_private.h" -#include -#include - -XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin); -#define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g",expr); -#define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d",expr); -#define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p",expr); - -void bottleneck_solve(lmm_system_t sys) -{ - lmm_variable_t var = NULL; - lmm_variable_t var_next = NULL; - lmm_constraint_t cnst = NULL; - s_lmm_constraint_t s_cnst; - lmm_constraint_t cnst_next = NULL; - lmm_element_t elem = NULL; - xbt_swag_t cnst_list = NULL; - xbt_swag_t var_list = NULL; - xbt_swag_t elem_list = NULL; - int i; - - static s_xbt_swag_t cnst_to_update; - - if (!(sys->modified)) - return; - - /* Init */ - xbt_swag_init(&(cnst_to_update), - xbt_swag_offset(s_cnst, saturated_constraint_set_hookup)); - - var_list = &(sys->variable_set); - XBT_DEBUG("Variable set : %d", xbt_swag_size(var_list)); - xbt_swag_foreach(var, var_list) { - int nb = 0; - var->value = 0.0; - XBT_DEBUG("Handling variable %p", var); - xbt_swag_insert(var, &(sys->saturated_variable_set)); - for (i = 0; i < var->cnsts_number; i++) { - if (var->cnsts[i].value == 0.0) - nb++; - } - if ((nb == var->cnsts_number) && (var->weight > 0.0)) { - XBT_DEBUG("Err, finally, there is no need to take care of variable %p", - var); - xbt_swag_remove(var, &(sys->saturated_variable_set)); - var->value = 1.0; - } - if (var->weight <= 0.0) { - XBT_DEBUG("Err, finally, there is no need to take care of variable %p", - var); - xbt_swag_remove(var, &(sys->saturated_variable_set)); - } - } - var_list = &(sys->saturated_variable_set); - - cnst_list = &(sys->active_constraint_set); - XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); - xbt_swag_foreach(cnst, cnst_list) { - xbt_swag_insert(cnst, &(sys->saturated_constraint_set)); - } - cnst_list = &(sys->saturated_constraint_set); - xbt_swag_foreach(cnst, cnst_list) { - cnst->remaining = cnst->bound; - cnst->usage = 0.0; - } - - XBT_DEBUG("Fair bottleneck Initialized"); - - /* - * Compute Usage and store the variables that reach the maximum. - */ - do { - if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { - XBT_DEBUG("Fair bottleneck done"); - lmm_print(sys); - } - XBT_DEBUG("******* Constraints to process: %d *******", - xbt_swag_size(cnst_list)); - xbt_swag_foreach_safe(cnst, cnst_next, cnst_list) { - int nb = 0; - XBT_DEBUG("Processing cnst %p ", cnst); - elem_list = &(cnst->element_set); - cnst->usage = 0.0; - xbt_swag_foreach(elem, elem_list) { - if (elem->variable->weight <= 0) - break; - if ((elem->value > 0) - && xbt_swag_belongs(elem->variable, var_list)) - nb++; - } - XBT_DEBUG("\tThere are %d variables", nb); - if (nb > 0 && !cnst->shared) - nb = 1; - if (!nb) { - cnst->remaining = 0.0; - cnst->usage = cnst->remaining; - xbt_swag_remove(cnst, cnst_list); - continue; - } - cnst->usage = cnst->remaining / nb; - XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst, - cnst->usage, nb); - } - - xbt_swag_foreach_safe(var, var_next, var_list) { - double min_inc = - var->cnsts[0].constraint->usage / var->cnsts[0].value; - for (i = 1; i < var->cnsts_number; i++) { - lmm_element_t elm = &var->cnsts[i]; - min_inc = MIN(min_inc, elm->constraint->usage / elm->value); - } - if (var->bound > 0) - min_inc = MIN(min_inc, var->bound - var->value); - var->mu = min_inc; - XBT_DEBUG("Updating variable %p maximum increment: %g", var, var->mu); - var->value += var->mu; - if (var->value == var->bound) { - xbt_swag_remove(var, var_list); - } - } - - xbt_swag_foreach_safe(cnst, cnst_next, cnst_list) { - XBT_DEBUG("Updating cnst %p ", cnst); - elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { - if (elem->variable->weight <= 0) - break; - if (cnst->shared) { - XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", - cnst, cnst->remaining, elem->variable, - elem->variable->mu); - double_update(&(cnst->remaining), - elem->value * elem->variable->mu); - } else { - XBT_DEBUG - ("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", - cnst, cnst->usage, elem->variable, elem->variable->mu); - cnst->usage = MIN(cnst->usage, elem->value * elem->variable->mu); - } - } - if (!cnst->shared) { - XBT_DEBUG("\tUpdate constraint %p (%g) by %g", - cnst, cnst->remaining, cnst->usage); - - double_update(&(cnst->remaining), cnst->usage); - } - - XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->remaining); - if (cnst->remaining == 0.0) { - XBT_DEBUG("\tGet rid of constraint %p", cnst); - - xbt_swag_remove(cnst, cnst_list); - xbt_swag_foreach(elem, elem_list) { - if (elem->variable->weight <= 0) - break; - if (elem->value > 0) { - XBT_DEBUG("\t\tGet rid of variable %p", elem->variable); - xbt_swag_remove(elem->variable, var_list); - } - } - } - } - } while (xbt_swag_size(var_list)); - - xbt_swag_reset(cnst_list); - sys->modified = 0; - if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { - XBT_DEBUG("Fair bottleneck done"); - lmm_print(sys); - } -} diff --git a/src/surf/fair_bottleneck.cpp b/src/surf/fair_bottleneck.cpp new file mode 100644 index 0000000000..b4a09948f0 --- /dev/null +++ b/src/surf/fair_bottleneck.cpp @@ -0,0 +1,192 @@ +/* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "xbt/sysdep.h" +#include "xbt/log.h" +#include "solver.hpp" +#include +#include + +XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin); +#define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g",expr); +#define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d",expr); +#define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p",expr); + +void bottleneck_solve(lmm_system_t sys) +{ + lmm_variable_t var_next = NULL; + lmm_constraint_t cnst = NULL; + //s_lmm_constraint_t s_cnst; + lmm_constraint_t cnst_next = NULL; + xbt_swag_t cnst_list = NULL; + + xbt_swag_t elem_list = NULL; + int i; + + static s_xbt_swag_t cnst_to_update; + vector cnstToUpdate; + + if (!(lmm_system_modified(sys))) + return; + + /* Init */ + + lmm_variable_t var = NULL; + lmm_element_t elem = NULL; + std::vector *varList; + std::vector::iterator varIt; + std::vector *elemList; + std::vector::iterator elemIt; + std::vector *cnstList; + std::vector::iterator cnstIt; + + varList = &(sys->m_variableSet); + XBT_DEBUG("Variable set : %d", varList->size()); + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + int nb = 0; + var = *varIt; + var->m_value = 0.0; + XBT_DEBUG("Handling variable %p", var); + sys->m_saturatedVariableSet.push_back(var); + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) + if ((*elemIt)->m_value == 0.0) + nb++; + if ((nb == var->getNumberOfCnst()) && (var->m_weight > 0.0)) { + XBT_DEBUG("Err, finally, there is no need to take care of variable %p", + var); + sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var)); + var->m_value = 1.0; + } + if (var->m_weight <= 0.0) { + XBT_DEBUG("Err, finally, there is no need to take care of variable %p", + var); + sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var)); + } + } + varList = &(sys->m_saturatedVariableSet); + cnstList = &(sys->m_activeConstraintSet); + XBT_DEBUG("Active constraints : %d", cnstList->size()); + sys->m_saturatedConstraintSet.insert(sys->m_saturatedConstraintSet.end(), cnstList->begin(), cnstList->end()); + cnstList = &(sys->m_saturatedConstraintSet); + for(cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + (*cnstIt)->m_remaining = (*cnstIt)->m_bound; + (*cnstIt)->m_usage = 0.0; + } + XBT_DEBUG("Fair bottleneck Initialized"); + + /* + * Compute Usage and store the variables that reach the maximum. + */ + + do { + if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { + XBT_DEBUG("Fair bottleneck done"); + lmm_print(sys); + } + XBT_DEBUG("******* Constraints to process: %d *******", + cnstList->size()); + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();){ + cnst = *cnstIt; + int nb = 0; + XBT_DEBUG("Processing cnst %p ", cnst); + elemList = &(cnst->m_elementSet); + cnst->m_usage = 0.0; + for(elemIt=elemList->begin(); elemIt!=elemList->end(); elemIt++) { + if (elem->p_variable->m_weight <= 0) + break; + if ((elem->m_value > 0) + && std::find(varList->begin(), varList->end(), elem->p_variable)!=varList->end()); + nb++; + } + XBT_DEBUG("\tThere are %d variables", nb); + if (nb > 0 && !cnst->m_shared) + nb = 1; + if (!nb) { + cnst->m_remaining = 0.0; + cnst->m_usage = cnst->m_remaining; + cnstList->erase(std::find(cnstList->begin(), cnstList->end(), *cnstIt)); + continue; + } + cnst->m_usage = cnst->m_remaining / nb; + XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst, + cnst->m_usage, nb); + ++cnstIt; + } + + for (varIt=varList->begin(); varIt!=varList->end();){ + var = *varIt; + double minInc = + var->m_cnsts.front()->p_constraint->m_usage / var->m_cnsts.front()->m_value; + for (elemIt=++var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { + elem = (*elemIt); + minInc = MIN(minInc, elem->p_constraint->m_usage / elem->m_value); + } + if (var->m_bound > 0) + minInc = MIN(minInc, var->m_bound - var->m_value); + var->m_mu = minInc; + XBT_DEBUG("Updating variable %p maximum increment: %g", var, var->m_mu); + var->m_value += var->m_mu; + if (var->m_value == var->m_bound) { + varList->erase(std::find(varList->begin(), varList->end(), var)); + } else + ++varIt; + } + + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();) { + cnst = *cnstIt; + XBT_DEBUG("Updating cnst %p ", cnst); + elemList = &(cnst->m_elementSet); + for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) { + elem = *elemIt; + if (elem->p_variable->m_weight <= 0) + break; + if (cnst->m_shared) { + XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", + cnst, cnst->m_remaining, elem->p_variable, + elem->p_variable->m_mu); + double_update(&(cnst->m_remaining), + elem->m_value * elem->p_variable->m_mu); + } else { + XBT_DEBUG + ("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", + cnst, cnst->m_usage, elem->p_variable, elem->p_variable->m_mu); + cnst->m_usage = MIN(cnst->m_usage, elem->m_value * elem->p_variable->m_mu); + } + } + + if (!cnst->m_shared) { + XBT_DEBUG("\tUpdate constraint %p (%g) by %g", + cnst, cnst->m_remaining, cnst->m_usage); + + double_update(&(cnst->m_remaining), cnst->m_usage); + } + + XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->m_remaining); + if (cnst->m_remaining == 0.0) { + XBT_DEBUG("\tGet rid of constraint %p", cnst); + + cnstList->erase(std::find(cnstList->begin(), cnstList->end(), cnst)); + + for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) { + if (elem->p_variable->m_weight <= 0) + break; + if (elem->m_value > 0) { + XBT_DEBUG("\t\tGet rid of variable %p", elem->p_variable); + varList->erase(std::find(varList->begin(), varList->end(), elem->p_variable)); + } + } + } else + ++cnstIt; + } + } while (!varList->empty()); + + cnstList->clear(); + sys->m_modified = 0; + if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { + XBT_DEBUG("Fair bottleneck done"); + sys->print(); + } +} diff --git a/src/surf/lagrange.c b/src/surf/lagrange.cpp similarity index 71% rename from src/surf/lagrange.c rename to src/surf/lagrange.cpp index 0eec4fb677..1b4cc9550b 100644 --- a/src/surf/lagrange.c +++ b/src/surf/lagrange.cpp @@ -11,8 +11,9 @@ */ #include "xbt/log.h" #include "xbt/sysdep.h" -#include "maxmin_private.h" - +//#include "maxmin_private.h" +#include "solver.h" +#include "solver.hpp" #include #ifndef MATH #include @@ -40,54 +41,58 @@ static double dichotomy(double init, double diff(double, void *), //computes the value of the differential of constraint param_cnst applied to lambda static double partial_diff_lambda(double lambda, void *param_cnst); -static int __check_feasible(xbt_swag_t cnst_list, xbt_swag_t var_list, +static int __check_feasible(std::vector *cnstList, std::vector *varList, int warn) { - xbt_swag_t elem_list = NULL; + std::vector *elemList = NULL; lmm_element_t elem = NULL; lmm_constraint_t cnst = NULL; lmm_variable_t var = NULL; + std::vector::iterator varIt; + std::vector::iterator elemIt; + std::vector::iterator cnstIt; double tmp; - xbt_swag_foreach(cnst, cnst_list) { + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + cnst = (*cnstIt); tmp = 0; - elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { - var = elem->variable; - if (var->weight <= 0) + elemList = &(cnst->m_elementSet); + for (elemIt=elemList->begin(); elemIt!=elemList->end(); ++elemIt) { + var = (*elemIt)->p_variable; + if (var->m_weight <= 0) continue; - tmp += var->value; + tmp += var->m_value; } - if (double_positive(tmp - cnst->bound)) { + if (double_positive(tmp - cnst->m_bound)) { if (warn) XBT_WARN ("The link (%p) is over-used. Expected less than %f and got %f", - cnst, cnst->bound, tmp); + cnst, cnst->m_bound, tmp); return 0; } XBT_DEBUG ("Checking feasability for constraint (%p): sat = %f, lambda = %f ", - cnst, tmp - cnst->bound, cnst->lambda); + cnst, tmp - cnst->m_bound, cnst->m_lambda); } - xbt_swag_foreach(var, var_list) { - if (!var->weight) + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + if (!var->m_weight) break; - if (var->bound < 0) + if (var->m_bound < 0) continue; XBT_DEBUG("Checking feasability for variable (%p): sat = %f mu = %f", var, - var->value - var->bound, var->mu); + var->m_value - var->m_bound, var->m_mu); - if (double_positive(var->value - var->bound)) { + if (double_positive(var->m_value - var->m_bound)) { if (warn) XBT_WARN ("The variable (%p) is too large. Expected less than %f and got %f", - var, var->bound, var->value); + var, var->m_bound, var->m_value); return 0; } - } + } return 1; } @@ -95,16 +100,17 @@ static double new_value(lmm_variable_t var) { double tmp = 0; int i; + std::vector::iterator elemIt; - for (i = 0; i < var->cnsts_number; i++) { - tmp += (var->cnsts[i].constraint)->lambda; + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { + tmp += ((*elemIt)->p_constraint)->m_lambda; } - if (var->bound > 0) - tmp += var->mu; + if (var->m_bound > 0) + tmp += var->m_mu; XBT_DEBUG("\t Working on var (%p). cost = %e; Weight = %e", var, tmp, - var->weight); + var->m_weight); //uses the partial differential inverse function - return var->func_fpi(var, tmp); + return var->p_funcFPI(var, tmp); } static double new_mu(lmm_variable_t var) @@ -112,48 +118,53 @@ static double new_mu(lmm_variable_t var) double mu_i = 0.0; double sigma_i = 0.0; int j; + std::vector::iterator elemIt; - for (j = 0; j < var->cnsts_number; j++) { - sigma_i += (var->cnsts[j].constraint)->lambda; + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { + sigma_i += ((*elemIt)->p_constraint)->m_lambda; } - mu_i = var->func_fp(var, var->bound) - sigma_i; + mu_i = var->p_funcFP(var, var->m_bound) - sigma_i; if (mu_i < 0.0) return 0.0; return mu_i; } -static double dual_objective(xbt_swag_t var_list, xbt_swag_t cnst_list) +static double dual_objective(std::vector *varList, std::vector *cnstList) { lmm_constraint_t cnst = NULL; lmm_variable_t var = NULL; double obj = 0.0; + std::vector::iterator varIt; + std::vector::iterator elemIt; + std::vector::iterator cnstIt; - xbt_swag_foreach(var, var_list) { + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + var = (*varIt); double sigma_i = 0.0; int j; - if (!var->weight) + if (!var->m_weight) break; - for (j = 0; j < var->cnsts_number; j++) - sigma_i += (var->cnsts[j].constraint)->lambda; - - if (var->bound > 0) - sigma_i += var->mu; + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) + sigma_i += ((*elemIt)->p_constraint)->m_lambda; + + if (var->m_bound > 0) + sigma_i += var->m_mu; XBT_DEBUG("var %p : sigma_i = %1.20f", var, sigma_i); - obj += var->func_f(var, var->func_fpi(var, sigma_i)) - - sigma_i * var->func_fpi(var, sigma_i); + obj += var->p_funcF(var, var->p_funcFPI(var, sigma_i)) - + sigma_i * var->p_funcFPI(var, sigma_i); - if (var->bound > 0) - obj += var->mu * var->bound; + if (var->m_bound > 0) + obj += var->m_mu * var->m_bound; } - xbt_swag_foreach(cnst, cnst_list) - obj += cnst->lambda * cnst->bound; - + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) + obj += (*cnstIt)->m_lambda * (*cnstIt)->m_bound; + return obj; } @@ -171,12 +182,16 @@ void lagrange_solve(lmm_system_t sys) * Variables to manipulate the data structure proposed to model the maxmin * fairness. See docummentation for more details. */ - xbt_swag_t cnst_list = NULL; + std::vector *cnstList = NULL; + std::vector::iterator cnstIt; lmm_constraint_t cnst = NULL; - xbt_swag_t var_list = NULL; + std::vector *varList = NULL; + std::vector::iterator varIt; lmm_variable_t var = NULL; + std::vector::iterator elemIt; + /* * Auxiliar variables. */ @@ -196,57 +211,58 @@ void lagrange_solve(lmm_system_t sys) lmm_print(sys); } - if (!(sys->modified)) + if (!(sys->m_modified)) return; - /* * Initialize lambda. */ - cnst_list = &(sys->active_constraint_set); - xbt_swag_foreach(cnst, cnst_list) { - cnst->lambda = 1.0; - cnst->new_lambda = 2.0; - XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->lambda); + cnstList = &(sys->m_activeConstraintSet); + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + cnst = *cnstIt; + cnst->m_lambda = 1.0; + cnst->m_newLambda = 2.0; + XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->m_lambda); } /* * Initialize the var list variable with only the active variables. * Associate an index in the swag variables. Initialize mu. */ - var_list = &(sys->variable_set); + varList = &(sys->m_variableSet); i = 0; - xbt_swag_foreach(var, var_list) { - if (!var->weight) - var->value = 0.0; + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + var = *varIt; + if (!var->m_weight) + var->m_value = 0.0; else { int nb = 0; - if (var->bound < 0.0) { + if (var->m_bound < 0.0) { XBT_DEBUG("#### NOTE var(%d) is a boundless variable", i); - var->mu = -1.0; - var->value = new_value(var); + var->m_mu = -1.0; + var->m_value = new_value(var); } else { - var->mu = 1.0; - var->new_mu = 2.0; - var->value = new_value(var); + var->m_mu = 1.0; + var->m_newMu = 2.0; + var->m_value = new_value(var); } - XBT_DEBUG("#### var(%p) ->weight : %e", var, var->weight); - XBT_DEBUG("#### var(%p) ->mu : %e", var, var->mu); - XBT_DEBUG("#### var(%p) ->weight: %e", var, var->weight); - XBT_DEBUG("#### var(%p) ->bound: %e", var, var->bound); - for (i = 0; i < var->cnsts_number; i++) { - if (var->cnsts[i].value == 0.0) + XBT_DEBUG("#### var(%p) ->weight : %e", var, var->m_weight); + XBT_DEBUG("#### var(%p) ->mu : %e", var, var->m_mu); + XBT_DEBUG("#### var(%p) ->weight: %e", var, var->m_weight); + XBT_DEBUG("#### var(%p) ->bound: %e", var, var->m_bound); + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { + if ((*elemIt)->m_value == 0.0) nb++; } - if (nb == var->cnsts_number) - var->value = 1.0; + if (nb == var->m_cnsts.size()) + var->m_value = 1.0; } } /* * Compute dual objective. */ - obj = dual_objective(var_list, cnst_list); + obj = dual_objective(varList, cnstList); /* * While doesn't reach a minimun error or a number maximum of iterations. @@ -262,19 +278,20 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of mu_i */ - xbt_swag_foreach(var, var_list) { - if (!var->weight) + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + var = *varIt; + if (!var->m_weight) break; - if (var->bound >= 0) { + if (var->m_bound >= 0) { XBT_DEBUG("Working on var (%p)", var); - var->new_mu = new_mu(var); + var->m_newMu = new_mu(var); /* dual_updated += (fabs(var->new_mu-var->mu)>dichotomy_min_error); */ /* XBT_DEBUG("dual_updated (%d) : %1.20f",dual_updated,fabs(var->new_mu-var->mu)); */ XBT_DEBUG("Updating mu : var->mu (%p) : %1.20f -> %1.20f", var, - var->mu, var->new_mu); - var->mu = var->new_mu; + var->m_mu, var->m_newMu); + var->m_mu = var->m_newMu; - new_obj = dual_objective(var_list, cnst_list); + new_obj = dual_objective(varList, cnstList); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -286,18 +303,19 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of lambda_i */ - xbt_swag_foreach(cnst, cnst_list) { + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + cnst = *cnstIt; XBT_DEBUG("Working on cnst (%p)", cnst); - cnst->new_lambda = - dichotomy(cnst->lambda, partial_diff_lambda, cnst, + cnst->m_newLambda = + dichotomy(cnst->m_lambda, partial_diff_lambda, cnst, dichotomy_min_error); /* dual_updated += (fabs(cnst->new_lambda-cnst->lambda)>dichotomy_min_error); */ /* XBT_DEBUG("dual_updated (%d) : %1.20f",dual_updated,fabs(cnst->new_lambda-cnst->lambda)); */ XBT_DEBUG("Updating lambda : cnst->lambda (%p) : %1.20f -> %1.20f", - cnst, cnst->lambda, cnst->new_lambda); - cnst->lambda = cnst->new_lambda; + cnst, cnst->m_lambda, cnst->m_newLambda); + cnst->m_lambda = cnst->m_newLambda; - new_obj = dual_objective(var_list, cnst_list); + new_obj = dual_objective(varList, cnstList); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -311,23 +329,24 @@ void lagrange_solve(lmm_system_t sys) */ XBT_DEBUG("-------------- Check convergence ----------"); overall_modification = 0; - xbt_swag_foreach(var, var_list) { - if (var->weight <= 0) - var->value = 0.0; + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + var = *varIt; + if (var->m_weight <= 0) + var->m_value = 0.0; else { tmp = new_value(var); overall_modification = - MAX(overall_modification, fabs(var->value - tmp)); + MAX(overall_modification, fabs(var->m_value - tmp)); - var->value = tmp; + var->m_value = tmp; XBT_DEBUG("New value of var (%p) = %e, overall_modification = %e", - var, var->value, overall_modification); + var, var->m_value, overall_modification); } } XBT_DEBUG("-------------- Check feasability ----------"); - if (!__check_feasible(cnst_list, var_list, 0)) + if (!__check_feasible(cnstList, varList, 0)) overall_modification = 1.0; XBT_DEBUG("Iteration %d: overall_modification : %f", iteration, overall_modification); @@ -336,8 +355,7 @@ void lagrange_solve(lmm_system_t sys) /* break; */ /* } */ } - - __check_feasible(cnst_list, var_list, 1); + __check_feasible(cnstList, varList, 1); if (overall_modification <= epsilon_min_error) { XBT_DEBUG("The method converges in %d iterations.", iteration); @@ -369,6 +387,7 @@ void lagrange_solve(lmm_system_t sys) static double dichotomy(double init, double diff(double, void *), void *var_cnst, double min_error) { + #ifdef TOREPAIR double min, max; double overall_error; double middle; @@ -472,11 +491,12 @@ static double dichotomy(double init, double diff(double, void *), XBT_CDEBUG(surf_lagrange_dichotomy, "returning %e", (min + max) / 2.0); XBT_OUT(); return ((min + max) / 2.0); + #endif } static double partial_diff_lambda(double lambda, void *param_cnst) { - + #ifdef TOREPAIR int j; xbt_swag_t elem_list = NULL; lmm_element_t elem = NULL; @@ -523,6 +543,7 @@ static double partial_diff_lambda(double lambda, void *param_cnst) diff); XBT_OUT(); return diff; + #endif } /** \brief Attribute the value bound to var->bound. @@ -532,18 +553,9 @@ static double partial_diff_lambda(double lambda, void *param_cnst) * Set default functions to the ones passed as parameters. This is a polimorfism in C pure, enjoy the roots of programming. * */ -void lmm_set_default_protocol_function(double (*func_f) - - - - - - - (lmm_variable_t var, double x), - double (*func_fp) (lmm_variable_t - var, double x), - double (*func_fpi) (lmm_variable_t - var, double x)) +void lmm_set_default_protocol_function(double (*func_f) (lmm_variable_t var, double x), + double (*func_fp) (lmm_variable_t var, double x), + double (*func_fpi) (lmm_variable_t var, double x)) { func_f_def = func_f; func_fp_def = func_fp; @@ -566,20 +578,26 @@ void lmm_set_default_protocol_function(double (*func_f) double func_vegas_f(lmm_variable_t var, double x) { + #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return VEGAS_SCALING * var->weight * log(x); + #endif } double func_vegas_fp(lmm_variable_t var, double x) { + #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return VEGAS_SCALING * var->weight / x; + #endif } double func_vegas_fpi(lmm_variable_t var, double x) { + #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return var->weight / (x / VEGAS_SCALING); + #endif } /* @@ -590,15 +608,15 @@ double func_vegas_fpi(lmm_variable_t var, double x) #define RENO_SCALING 1.0 double func_reno_f(lmm_variable_t var, double x) { - xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); - return RENO_SCALING * sqrt(3.0 / 2.0) / var->weight * - atan(sqrt(3.0 / 2.0) * var->weight * x); + return RENO_SCALING * sqrt(3.0 / 2.0) / var->m_weight * + atan(sqrt(3.0 / 2.0) * var->m_weight * x); } double func_reno_fp(lmm_variable_t var, double x) { - return RENO_SCALING * 3.0 / (3.0 * var->weight * var->weight * x * x + + return RENO_SCALING * 3.0 / (3.0 * var->m_weight * var->m_weight * x * x + 2.0); } @@ -606,15 +624,15 @@ double func_reno_fpi(lmm_variable_t var, double x) { double res_fpi; - xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); xbt_assert(x > 0.0, "Don't call me with stupid values!"); res_fpi = - 1.0 / (var->weight * var->weight * (x / RENO_SCALING)) - - 2.0 / (3.0 * var->weight * var->weight); + 1.0 / (var->m_weight * var->m_weight * (x / RENO_SCALING)) - + 2.0 / (3.0 * var->m_weight * var->m_weight); if (res_fpi <= 0.0) return 0.0; -/* xbt_assert(res_fpi>0.0,"Don't call me with stupid values!"); */ +// xbt_assert(res_fpi>0.0,"Don't call me with stupid values!"); return sqrt(res_fpi); } @@ -627,16 +645,16 @@ double func_reno_fpi(lmm_variable_t var, double x) #define RENO2_SCALING 1.0 double func_reno2_f(lmm_variable_t var, double x) { - xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); - return RENO2_SCALING * (1.0 / var->weight) * log((x * var->weight) / - (2.0 * x * var->weight + + xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); + return RENO2_SCALING * (1.0 / var->m_weight) * log((x * var->m_weight) / + (2.0 * x * var->m_weight + 3.0)); } double func_reno2_fp(lmm_variable_t var, double x) { - return RENO2_SCALING * 3.0 / (var->weight * x * - (2.0 * var->weight * x + 3.0)); + return RENO2_SCALING * 3.0 / (var->m_weight * x * + (2.0 * var->m_weight * x + 3.0)); } double func_reno2_fpi(lmm_variable_t var, double x) @@ -645,7 +663,7 @@ double func_reno2_fpi(lmm_variable_t var, double x) double tmp; xbt_assert(x > 0.0, "Don't call me with stupid values!"); - tmp = x * var->weight * var->weight; + tmp = x * var->m_weight * var->m_weight; res_fpi = tmp * (9.0 * x + 24.0); if (res_fpi <= 0.0) diff --git a/src/surf/maxmin.c b/src/surf/maxmin.c deleted file mode 100644 index 3d49f84d12..0000000000 --- a/src/surf/maxmin.c +++ /dev/null @@ -1,891 +0,0 @@ -/* Copyright (c) 2004-2011. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - - -#include "xbt/sysdep.h" -#include "xbt/log.h" -#include "xbt/mallocator.h" -#include "maxmin_private.h" -#include -#include /* sprintf */ -#include -XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, - "Logging specific to SURF (maxmin)"); - -typedef struct s_dyn_light { - int *data; - int pos; - int size; -} s_dyn_light_t, *dyn_light_t; - -XBT_EXPORT_NO_IMPORT(double) sg_maxmin_precision = 0.00001; - -static void *lmm_variable_mallocator_new_f(void); -static void lmm_variable_mallocator_free_f(void *var); -#define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)NULL) -static void lmm_update_modified_set(lmm_system_t sys, - lmm_constraint_t cnst); -static void lmm_remove_all_modified_set(lmm_system_t sys); -static int Global_debug_id = 1; -static int Global_const_debug_id = 1; - -static void lmm_var_free(lmm_system_t sys, lmm_variable_t var); -static XBT_INLINE void lmm_cnst_free(lmm_system_t sys, - lmm_constraint_t cnst); - -lmm_system_t lmm_system_new(int selective_update) -{ - lmm_system_t l = NULL; - s_lmm_variable_t var; - s_lmm_constraint_t cnst; - - l = xbt_new0(s_lmm_system_t, 1); - - l->modified = 0; - l->selective_update_active = selective_update; - l->visited_counter = 1; - - XBT_DEBUG("Setting selective_update_active flag to %d\n", - l->selective_update_active); - - xbt_swag_init(&(l->variable_set), - xbt_swag_offset(var, variable_set_hookup)); - xbt_swag_init(&(l->constraint_set), - xbt_swag_offset(cnst, constraint_set_hookup)); - - xbt_swag_init(&(l->active_constraint_set), - xbt_swag_offset(cnst, active_constraint_set_hookup)); - - xbt_swag_init(&(l->modified_constraint_set), - xbt_swag_offset(cnst, modified_constraint_set_hookup)); - xbt_swag_init(&(l->saturated_variable_set), - xbt_swag_offset(var, saturated_variable_set_hookup)); - xbt_swag_init(&(l->saturated_constraint_set), - xbt_swag_offset(cnst, saturated_constraint_set_hookup)); - - l->variable_mallocator = xbt_mallocator_new(65536, - lmm_variable_mallocator_new_f, - lmm_variable_mallocator_free_f, - lmm_variable_mallocator_reset_f); - - return l; -} - -void lmm_system_free(lmm_system_t sys) -{ - lmm_variable_t var = NULL; - lmm_constraint_t cnst = NULL; - - while ((var = extract_variable(sys))) { - XBT_WARN - ("Variable %p (%d) still in LMM system when freing it: this may be a bug", - var, var->id_int); - lmm_var_free(sys, var); - } - - while ((cnst = extract_constraint(sys))) - lmm_cnst_free(sys, cnst); - - xbt_mallocator_free(sys->variable_mallocator); - free(sys); -} - -XBT_INLINE void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var) -{ - int i; - int n; - - lmm_element_t elem = NULL; - - XBT_IN("(sys=%p, var=%p)", sys, var); - sys->modified = 1; - - n = 0; - for (i = 0; i < var->cnsts_number; i++) { - elem = &var->cnsts[i]; - xbt_swag_remove(elem, &(elem->constraint->element_set)); - xbt_swag_remove(elem, &(elem->constraint->active_element_set)); - if (!xbt_swag_size(&(elem->constraint->element_set))) - make_constraint_inactive(sys, elem->constraint); - else { - if (n < i) - var->cnsts[n].constraint = elem->constraint; - n++; - } - } - if (n) { - var->cnsts_number = n; - lmm_update_modified_set(sys, var->cnsts[0].constraint); - } - - var->cnsts_number = 0; - XBT_OUT(); -} - -static void lmm_var_free(lmm_system_t sys, lmm_variable_t var) -{ - - lmm_variable_disable(sys, var); - xbt_mallocator_release(sys->variable_mallocator, var); -} - -static XBT_INLINE void lmm_cnst_free(lmm_system_t sys, - lmm_constraint_t cnst) -{ -/* xbt_assert(xbt_swag_size(&(cnst->element_set)), */ -/* "This list should be empty!"); */ - make_constraint_inactive(sys, cnst); - free(cnst); -} - -lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, - double bound_value) -{ - lmm_constraint_t cnst = NULL; - s_lmm_element_t elem; - - cnst = xbt_new0(s_lmm_constraint_t, 1); - cnst->id = id; - cnst->id_int = Global_const_debug_id++; - xbt_swag_init(&(cnst->element_set), - xbt_swag_offset(elem, element_set_hookup)); - xbt_swag_init(&(cnst->active_element_set), - xbt_swag_offset(elem, active_element_set_hookup)); - - cnst->bound = bound_value; - cnst->usage = 0; - cnst->shared = 1; - insert_constraint(sys, cnst); - - return cnst; -} - -XBT_INLINE void lmm_constraint_shared(lmm_constraint_t cnst) -{ - cnst->shared = 0; -} - -XBT_INLINE int lmm_constraint_is_shared(lmm_constraint_t cnst) -{ - return (cnst->shared); -} - -XBT_INLINE void lmm_constraint_free(lmm_system_t sys, - lmm_constraint_t cnst) -{ - remove_constraint(sys, cnst); - lmm_cnst_free(sys, cnst); -} - -static void *lmm_variable_mallocator_new_f(void) -{ - lmm_variable_t var = xbt_new(s_lmm_variable_t, 1); - var->cnsts = NULL; /* will be created by realloc */ - return var; -} - -static void lmm_variable_mallocator_free_f(void *var) -{ - xbt_free(((lmm_variable_t) var)->cnsts); - 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 var = NULL; - int i; - - XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", - sys, id, weight, bound, number_of_constraints); - - var = xbt_mallocator_get(sys->variable_mallocator); - var->id = id; - var->id_int = Global_debug_id++; - var->cnsts = xbt_realloc(var->cnsts, number_of_constraints * sizeof(s_lmm_element_t)); - for (i = 0; i < number_of_constraints; i++) { - var->cnsts[i].element_set_hookup.next = NULL; - var->cnsts[i].element_set_hookup.prev = NULL; - var->cnsts[i].active_element_set_hookup.next = NULL; - var->cnsts[i].active_element_set_hookup.prev = NULL; - var->cnsts[i].constraint = NULL; - var->cnsts[i].variable = NULL; - var->cnsts[i].value = 0.0; - } - var->cnsts_size = number_of_constraints; - var->cnsts_number = 0; - var->weight = weight; - var->bound = bound; - var->value = 0.0; - var->visited = sys->visited_counter - 1; - var->mu = 0.0; - var->new_mu = 0.0; - var->func_f = func_f_def; - var->func_fp = func_fp_def; - var->func_fpi = func_fpi_def; - - var->variable_set_hookup.next = NULL; - var->variable_set_hookup.prev = NULL; - var->saturated_variable_set_hookup.next = NULL; - var->saturated_variable_set_hookup.prev = NULL; - - if (weight) - xbt_swag_insert_at_head(var, &(sys->variable_set)); - else - xbt_swag_insert_at_tail(var, &(sys->variable_set)); - - XBT_OUT(" returns %p", var); - return var; -} - -void lmm_variable_free(lmm_system_t sys, lmm_variable_t var) -{ - remove_variable(sys, var); - lmm_var_free(sys, var); -} - -XBT_INLINE double lmm_variable_getvalue(lmm_variable_t var) -{ - return (var->value); -} - -XBT_INLINE double lmm_variable_getbound(lmm_variable_t var) -{ - return (var->bound); -} - -void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value) -{ - lmm_element_t elem = NULL; - - sys->modified = 1; - - xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints"); - - elem = &(var->cnsts[var->cnsts_number++]); - - elem->value = value; - elem->constraint = cnst; - elem->variable = var; - - if (var->weight) - xbt_swag_insert_at_head(elem, &(elem->constraint->element_set)); - else - xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set)); - if(!sys->selective_update_active) { - make_constraint_active(sys, cnst); - } else if(elem->value>0 || var->weight >0) { - make_constraint_active(sys, cnst); - lmm_update_modified_set(sys, cnst); - if (var->cnsts_number > 1) - lmm_update_modified_set(sys, var->cnsts[0].constraint); - } -} - -void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value) -{ - int i; - sys->modified = 1; - - for (i = 0; i < var->cnsts_number; i++) - if (var->cnsts[i].constraint == cnst) - break; - - if (i < var->cnsts_number) { - if (cnst->shared) - var->cnsts[i].value += value; - else - var->cnsts[i].value = MAX(var->cnsts[i].value, value); - lmm_update_modified_set(sys, cnst); - } else - lmm_expand(sys, cnst, var, value); -} - -void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value) -{ - int i; - - for (i = 0; i < var->cnsts_number; i++) - if (var->cnsts[i].constraint == cnst) - break; - - if (i < var->cnsts_number) { - var->cnsts[i].value = value; - sys->modified = 1; - lmm_update_modified_set(sys, cnst); - } else - DIE_IMPOSSIBLE; -} - -XBT_INLINE lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, - lmm_variable_t var, - int num) -{ - if (num < var->cnsts_number) - return (var->cnsts[num].constraint); - else - return NULL; -} - -XBT_INLINE double lmm_get_cnst_weight_from_var(lmm_system_t sys, - lmm_variable_t var, - int num) -{ - if (num < var->cnsts_number) - return (var->cnsts[num].value); - else - return 0.0; -} - -XBT_INLINE int lmm_get_number_of_cnst_from_var(lmm_system_t sys, - lmm_variable_t var) -{ - return (var->cnsts_number); -} - -lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys, - lmm_constraint_t cnst, - lmm_element_t * elem) -{ - if (!(*elem)) - *elem = xbt_swag_getFirst(&(cnst->element_set)); - else - *elem = xbt_swag_getNext(*elem, cnst->element_set.offset); - if (*elem) - return (*elem)->variable; - else - return NULL; -} - -XBT_INLINE void *lmm_constraint_id(lmm_constraint_t cnst) -{ - return cnst->id; -} - -XBT_INLINE void *lmm_variable_id(lmm_variable_t var) -{ - return var->id; -} - -static XBT_INLINE void saturated_constraint_set_update(double usage, - int cnst_light_num, - dyn_light_t saturated_constraint_set, - double *min_usage) -{ - xbt_assert(usage > 0,"Impossible"); - - if (*min_usage < 0 || *min_usage > usage) { - *min_usage = usage; - // XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage); - saturated_constraint_set->data[0] = cnst_light_num; - saturated_constraint_set->pos = 1; - } else if (*min_usage == usage) { - if(saturated_constraint_set->pos == saturated_constraint_set->size) { // realloc the size - saturated_constraint_set->size *= 2; - saturated_constraint_set->data = xbt_realloc(saturated_constraint_set->data, (saturated_constraint_set->size) * sizeof(int)); - } - saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num; - saturated_constraint_set->pos++; - } -} - -static XBT_INLINE void saturated_variable_set_update( - s_lmm_constraint_light_t *cnst_light_tab, - dyn_light_t saturated_constraint_set, - lmm_system_t sys) -{ - lmm_constraint_light_t cnst = NULL; - lmm_element_t elem = NULL; - xbt_swag_t elem_list = NULL; - int i; - for(i = 0; i< saturated_constraint_set->pos; i++){ - cnst = &cnst_light_tab[saturated_constraint_set->data[i]]; - elem_list = &(cnst->cnst->active_element_set); - xbt_swag_foreach(elem, elem_list) { - if (elem->variable->weight <= 0) - break; - if ((elem->value > 0)) - xbt_swag_insert(elem->variable, &(sys->saturated_variable_set)); - } - } -} - -void lmm_print(lmm_system_t sys) -{ - lmm_constraint_t cnst = NULL; - lmm_element_t elem = NULL; - lmm_variable_t var = NULL; - xbt_swag_t cnst_list = NULL; - xbt_swag_t var_list = NULL; - xbt_swag_t elem_list = NULL; - char print_buf[1024]; - char *trace_buf = xbt_malloc0(sizeof(char)); - double sum = 0.0; - - /* Printing Objective */ - var_list = &(sys->variable_set); - sprintf(print_buf, "MAX-MIN ( "); - trace_buf = - xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - xbt_swag_foreach(var, var_list) { - sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight); - trace_buf = - xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - } - sprintf(print_buf, ")"); - trace_buf = - xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - XBT_DEBUG("%20s", trace_buf); - trace_buf[0] = '\000'; - - XBT_DEBUG("Constraints"); - /* Printing Constraints */ - cnst_list = &(sys->active_constraint_set); - xbt_swag_foreach(cnst, cnst_list) { - sum = 0.0; - elem_list = &(cnst->element_set); - sprintf(print_buf, "\t"); - trace_buf = - xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - sprintf(print_buf, "%s(",(cnst->shared)?"":"max"); - trace_buf = - xbt_realloc(trace_buf, - strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - xbt_swag_foreach(elem, elem_list) { - sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value, - elem->variable->id_int, elem->variable->value,(cnst->shared)?"+":","); - trace_buf = - xbt_realloc(trace_buf, - strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - if(cnst->shared) - sum += elem->value * elem->variable->value; - else - sum = MAX(sum,elem->value * elem->variable->value); - } - sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int); - trace_buf = - xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - - if (!cnst->shared) { - sprintf(print_buf, " [MAX-Constraint]"); - trace_buf = - xbt_realloc(trace_buf, - strlen(trace_buf) + strlen(print_buf) + 1); - strcat(trace_buf, print_buf); - } - XBT_DEBUG("%s", trace_buf); - trace_buf[0] = '\000'; - xbt_assert(!double_positive(sum - cnst->bound), - "Incorrect value (%f is not smaller than %f): %g", - sum, cnst->bound, sum - cnst->bound); - } - - XBT_DEBUG("Variables"); - /* Printing Result */ - xbt_swag_foreach(var, var_list) { - 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), - "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); - } - } - - free(trace_buf); -} - -void lmm_solve(lmm_system_t sys) -{ - lmm_variable_t var = NULL; - lmm_constraint_t cnst = NULL; - lmm_constraint_t cnst_next = NULL; - lmm_element_t elem = NULL; - xbt_swag_t cnst_list = NULL; - xbt_swag_t var_list = NULL; - xbt_swag_t elem_list = NULL; - double min_usage = -1; - double min_bound = -1; - - if (!(sys->modified)) - return; - - XBT_IN("(sys=%p)", sys); - - /* - * Compute Usage and store the variables that reach the maximum. - */ - cnst_list = - sys-> - selective_update_active ? &(sys->modified_constraint_set) : - &(sys->active_constraint_set); - - XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); - /* Init: Only modified code portions */ - xbt_swag_foreach(cnst, cnst_list) { - elem_list = &(cnst->element_set); - //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list)); - xbt_swag_foreach(elem, elem_list) { - var = elem->variable; - if (var->weight <= 0.0) - break; - var->value = 0.0; - } - } - - s_lmm_constraint_light_t *cnst_light_tab = (s_lmm_constraint_light_t *)xbt_malloc0(xbt_swag_size(cnst_list)*sizeof(s_lmm_constraint_light_t)); - int cnst_light_num = 0; - dyn_light_t saturated_constraint_set = xbt_new0(s_dyn_light_t,1); - saturated_constraint_set->size = 5; - saturated_constraint_set->data = xbt_new0(int, saturated_constraint_set->size); - - xbt_swag_foreach_safe(cnst, cnst_next, cnst_list) { - /* INIT */ - cnst->remaining = cnst->bound; - if (cnst->remaining == 0) - continue; - cnst->usage = 0; - elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { - /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */ - if (elem->variable->weight <= 0) - break; - if ((elem->value > 0)) { - if (cnst->shared) - cnst->usage += elem->value / elem->variable->weight; - else if (cnst->usage < elem->value / elem->variable->weight) - cnst->usage = elem->value / elem->variable->weight; - - make_elem_active(elem); - if (sys->keep_track) - xbt_swag_insert(elem->variable->id, sys->keep_track); - } - } - XBT_DEBUG("Constraint Usage '%d' : %f", cnst->id_int, cnst->usage); - /* Saturated constraints update */ - - if(cnst->usage > 0) { - cnst_light_tab[cnst_light_num].cnst = cnst; - cnst->cnst_light = &(cnst_light_tab[cnst_light_num]); - cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage; - saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage, - cnst_light_num, saturated_constraint_set, &min_usage); - cnst_light_num++; - } - } - - saturated_variable_set_update( cnst_light_tab, - saturated_constraint_set, - sys); - - /* Saturated variables update */ - - do { - /* Fix the variables that have to be */ - var_list = &(sys->saturated_variable_set); - - xbt_swag_foreach(var, var_list) { - if (var->weight <= 0.0) - DIE_IMPOSSIBLE; - /* First check if some of these variables have reach their upper - bound and update min_usage accordingly. */ - XBT_DEBUG - ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f", - var->id_int, var->bound, var->weight, min_usage, - var->bound * var->weight); - if ((var->bound > 0) && (var->bound * var->weight < min_usage)) { - if (min_bound < 0) - min_bound = var->bound; - else - min_bound = MIN(min_bound, var->bound); - XBT_DEBUG("Updated min_bound=%f", min_bound); - } - } - - - while ((var = xbt_swag_getFirst(var_list))) { - int i; - - if (min_bound < 0) { - var->value = min_usage / var->weight; - } else { - if (min_bound == var->bound) - var->value = var->bound; - else { - xbt_swag_remove(var, var_list); - continue; - } - } - XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ", - min_usage, var->id_int, var->weight, var->id_int, var->value); - - - /* Update usage */ - - for (i = 0; i < var->cnsts_number; i++) { - elem = &var->cnsts[i]; - cnst = elem->constraint; - if (cnst->shared) { - double_update(&(cnst->remaining), elem->value * var->value); - double_update(&(cnst->usage), elem->value / var->weight); - if(cnst->usage<=0 || cnst->remaining<=0) { - 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 \t cnst_light_tab: %p ", - index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab); - cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1]; - cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index]; - cnst_light_num--; - cnst->cnst_light = NULL; - } - } else { - cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage; - } - make_elem_inactive(elem); - } else { - cnst->usage = 0.0; - make_elem_inactive(elem); - elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { - if (elem->variable->weight <= 0 || elem->variable->value > 0) - break; - if (elem->value > 0) - cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight); - } - if (cnst->usage<=0 || cnst->remaining<=0) { - 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 \t cnst_light_tab: %p ", - index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab); - cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1]; - cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index]; - cnst_light_num--; - cnst->cnst_light = NULL; - } - } else { - cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage; - } - } - } - xbt_swag_remove(var, var_list); - } - - /* Find out which variables reach the maximum */ - min_usage = -1; - min_bound = -1; - saturated_constraint_set->pos = 0; - int pos; - for(pos=0; pos 0); - - sys->modified = 0; - if (sys->selective_update_active) - lmm_remove_all_modified_set(sys); - - if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { - lmm_print(sys); - } - - xbt_free(saturated_constraint_set->data); - xbt_free(saturated_constraint_set); - xbt_free(cnst_light_tab); - XBT_OUT(); -} - -/* Not a O(1) function */ - -void lmm_update(lmm_system_t sys, lmm_constraint_t cnst, - lmm_variable_t var, double value) -{ - int i; - - for (i = 0; i < var->cnsts_number; i++) - if (var->cnsts[i].constraint == cnst) { - var->cnsts[i].value = value; - sys->modified = 1; - lmm_update_modified_set(sys, cnst); - return; - } -} - -/** \brief Attribute the value bound to var->bound. - * - * \param sys the lmm_system_t - * \param var the lmm_variable_t - * \param bound the new bound to associate with var - * - * Makes var->bound equal to bound. Whenever this function is called - * a change is signed in the system. To - * avoid false system changing detection it is a good idea to test - * (bound != 0) before calling it. - * - */ -void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, - double bound) -{ - sys->modified = 1; - var->bound = bound; - - if (var->cnsts_number) - lmm_update_modified_set(sys, var->cnsts[0].constraint); -} - - -void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, - double weight) -{ - int i; - lmm_element_t elem; - - if (weight == var->weight) - return; - XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight); - sys->modified = 1; - var->weight = weight; - xbt_swag_remove(var, &(sys->variable_set)); - if (weight) - xbt_swag_insert_at_head(var, &(sys->variable_set)); - else - xbt_swag_insert_at_tail(var, &(sys->variable_set)); - - for (i = 0; i < var->cnsts_number; i++) { - elem = &var->cnsts[i]; - xbt_swag_remove(elem, &(elem->constraint->element_set)); - if (weight) - xbt_swag_insert_at_head(elem, &(elem->constraint->element_set)); - else - xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set)); - - if (i == 0) - lmm_update_modified_set(sys, elem->constraint); - } - if (!weight) - var->value = 0.0; - - XBT_OUT(); -} - -XBT_INLINE double lmm_get_variable_weight(lmm_variable_t var) -{ - return var->weight; -} - -XBT_INLINE void lmm_update_constraint_bound(lmm_system_t sys, - lmm_constraint_t cnst, - double bound) -{ - sys->modified = 1; - lmm_update_modified_set(sys, cnst); - cnst->bound = bound; -} - -XBT_INLINE int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) -{ - return xbt_swag_belongs(cnst, &(sys->active_constraint_set)); -} - -XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t - sys) -{ - return xbt_swag_getFirst(&(sys->active_constraint_set)); -} - -XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t - sys, - lmm_constraint_t - cnst) -{ - return xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); -} - -#ifdef HAVE_LATENCY_BOUND_TRACKING -XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var) -{ - return (double_equals(var->bound, var->value)); -} -#endif - - -/** \brief Update the constraint set propagating recursively to - * other constraints so the system should not be entirely computed. - * - * \param sys the lmm_system_t - * \param cnst the lmm_constraint_t affected by the change - * - * A recursive algorithm to optimize the system recalculation selecting only - * constraints that have changed. Each constraint change is propagated - * to the list of constraints for each variable. - */ -static void lmm_update_modified_set_rec(lmm_system_t sys, - lmm_constraint_t cnst) -{ - lmm_element_t elem; - - xbt_swag_foreach(elem, &cnst->element_set) { - lmm_variable_t var = elem->variable; - 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)) { - xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set); - lmm_update_modified_set_rec(sys, cnsts[i].constraint); - } - } - var->visited = sys->visited_counter; - } -} - -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)) { - xbt_swag_insert(cnst, &sys->modified_constraint_set); - lmm_update_modified_set_rec(sys, cnst); - } -} - -/** \brief Remove all constraints of the modified_constraint_set. - * - * \param sys the lmm_system_t - */ -static void lmm_remove_all_modified_set(lmm_system_t sys) -{ - if (++sys->visited_counter == 1) { - /* the counter wrapped around, reset each variable->visited */ - lmm_variable_t var; - xbt_swag_foreach(var, &sys->variable_set) - var->visited = 0; - } - xbt_swag_reset(&sys->modified_constraint_set); -} diff --git a/src/surf/maxmin_private.h b/src/surf/maxmin_private.h index 2239cd2b3e..f14d003320 100644 --- a/src/surf/maxmin_private.h +++ b/src/surf/maxmin_private.h @@ -7,7 +7,8 @@ #ifndef _SURF_MAXMIN_PRIVATE_H #define _SURF_MAXMIN_PRIVATE_H -#include "surf/maxmin.h" +//#include "surf/maxmin.h" +#include "surf/solver.h" #include "xbt/swag.h" #include "xbt/mallocator.h" diff --git a/src/surf/network.c b/src/surf/network.c index 04c576314d..9133c1ab8b 100644 --- a/src/surf/network.c +++ b/src/surf/network.c @@ -820,7 +820,7 @@ static void surf_network_model_init_internal(void) surf_action_lmm_update_index_heap); surf_network_model->model_private->modified_set = xbt_swag_new(xbt_swag_offset(comm, generic_lmm_action.action_list_hookup)); - surf_network_model->model_private->maxmin_system->keep_track = surf_network_model->model_private->modified_set; + //TOREPAIR: surf_network_model->model_private->maxmin_system->keep_track = surf_network_model->model_private->modified_set; } surf_network_model->gap_remove = NULL; diff --git a/src/surf/network_ns3.c b/src/surf/network_ns3.c index e180da04f3..9e0707dabe 100644 --- a/src/surf/network_ns3.c +++ b/src/surf/network_ns3.c @@ -5,7 +5,8 @@ * under the terms of the license (GNU LGPL) which comes with this package. */ #include "surf_private.h" -#include "surf/maxmin.h" +//#include "surf/maxmin.h" +#include "surf/solver.h" #include "surf/ns3/ns3_interface.h" #include "xbt/lib.h" #include "surf/network_ns3_private.h" diff --git a/src/surf/solver.cpp b/src/surf/solver.cpp new file mode 100644 index 0000000000..74abd69ae3 --- /dev/null +++ b/src/surf/solver.cpp @@ -0,0 +1,735 @@ +#include "solver.hpp" + +#include "xbt/log.h" +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, + "Logging specific to SURF (maxmin)"); + +static int Global_debug_id = 1; +static int Global_const_debug_id = 1; + +Solver::Solver(int selectiveUpdate) +{ + VariablePtr var; + ConstraintPtr cnst; + + m_modified = 0; + m_selectiveUpdateActive = selectiveUpdate; + m_visitedCounter = 1; + + XBT_DEBUG("Setting selective_update_active flag to %d\n", + this->m_selectiveUpdateActive); + + /*xbt_swag_init(&(l->variable_set), + xbt_swag_offset(var, variable_set_hookup)); + xbt_swag_init(&(l->constraint_set), + xbt_swag_offset(cnst, constraint_set_hookup)); + + xbt_swag_init(&(l->active_constraint_set), + xbt_swag_offset(cnst, active_constraint_set_hookup)); + + xbt_swag_init(&(l->modified_constraint_set), + xbt_swag_offset(cnst, modified_constraint_set_hookup)); + xbt_swag_init(&(l->saturated_variable_set), + xbt_swag_offset(var, saturated_variable_set_hookup)); + xbt_swag_init(&(l->saturated_constraint_set), + xbt_swag_offset(cnst, saturated_constraint_set_hookup)); + + l->variable_mallocator = xbt_mallocator_new(65536, + lmm_variable_mallocator_new_f, + lmm_variable_mallocator_free_f, + lmm_variable_mallocator_reset_f);*/ +} + +ConstraintPtr Solver::createConstraint(void *id, double bound) +{ + ConstraintPtr cnst = m_constraintAllocator.construct(id, bound); + m_constraintSet.push_back(cnst); + return cnst; +} + +void Solver::destroyConstraint(Constraint* cnst) +{ + m_constraintAllocator.destroy(cnst); +} + + +VariablePtr Solver::createVariable(void *id, double weight, double bound) +{ + void *mem = m_variableAllocator.malloc(); + VariablePtr var = new (mem) Variable(id, weight, bound, m_visitedCounter - 1); + var->m_visited = m_visitedCounter - 1; + if (weight) + m_variableSet.insert(m_variableSet.begin(), var); + else + m_variableSet.push_back(var); + return var; +} + +void Solver::destroyVariable(Variable* var) +{ + m_variableAllocator.destroy(var); +} + +void Solver::destroyElement(Element* elem) +{ + m_elementAllocator.destroy(elem); +} + +void Solver::expand(ConstraintPtr cnst, VariablePtr var, double value) +{ + m_modified = 1; + + ElementPtr elem = m_elementAllocator.construct(cnst, var, value); + var->m_cnsts.push_back(elem); + + if (var->m_weight) + cnst->m_elementSet.insert(cnst->m_elementSet.begin(), elem); + else + cnst->m_elementSet.push_back(elem); + if(!m_selectiveUpdateActive) { + activateConstraint(cnst); + } else if(value>0 || var->m_weight >0) { + activateConstraint(cnst); + updateModifiedSet(cnst); + if (var->m_cnsts.size() > 1) + updateModifiedSet(var->m_cnsts.front()->p_constraint); + } +} + +void Solver::expandAdd(ConstraintPtr cnst, VariablePtr var, double value) +{ + m_modified = 1; + + std::vector::iterator it; + for (it=var->m_cnsts.begin(); it!=var->m_cnsts.end(); ++it ) + if ((*it)->p_constraint == cnst) + break; + + if (it != var->m_cnsts.end()) { + if (cnst->isShared()) + (*it)->m_value += value; + else + (*it)->m_value = MAX((*it)->m_value, value); + updateModifiedSet(cnst); + } else + expand(cnst, var, value); +} + +void Solver::elementSetValue(ConstraintPtr cnst, VariablePtr var, double value) +{ + std::vector::iterator it; + for (it=var->m_cnsts.begin(); it!=var->m_cnsts.end(); ++it ) { + ElementPtr elem = (*it); + if (elem->p_constraint == cnst) { + elem->m_value = value; + m_modified = 1; + updateModifiedSet(cnst); + } + } + if (it==var->m_cnsts.end()) { + DIE_IMPOSSIBLE; + } +} + +//XBT_INLINE +ConstraintPtr Variable::getCnst(int num) +{ + if (num < m_cnsts.size()) + return m_cnsts.at(num)->p_constraint; + else { + ConstraintPtr res; + return res; + } +} + +//XBT_INLINE +double Variable::getCnstWeight(int num) +{ + if (num < m_cnsts.size()) + return (m_cnsts.at(num)->m_value); + else + return 0.0; +} + +//XBT_INLINE +int Variable::getNumberOfCnst() +{ + return m_cnsts.size(); +} + +VariablePtr Constraint::getVar(ElementPtr elem) +{ + vector::iterator it; + if (!elem) + elem = m_elementSet.front(); + else + elem = *(++find(m_elementSet.begin(), m_elementSet.end(), elem)); + if (elem) + return elem->p_variable; + else { + VariablePtr res; + return res; + } +} + +//XBT_INLINE +void* Constraint::id() +{ + return p_id; +} + +//XBT_INLINE +void* Variable::id() +{ + return p_id; +} + +//static XBT_INLINE +void Solver::saturatedConstraintSetUpdate(double usage, + ConstraintLightPtr cnstLight, + vector saturatedConstraintSet, + double *minUsage) +{ + xbt_assert(usage > 0,"Impossible"); + + if (*minUsage < 0 || *minUsage > usage) { + *minUsage = usage; + saturatedConstraintSet.clear(); + saturatedConstraintSet.push_back(cnstLight); + XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *minUsage, usage); + } else if (*minUsage == usage) { + saturatedConstraintSet.push_back(cnstLight); + } +} + +//static XBT_INLINE +void Solver::saturatedVariableSetUpdate(vector cnstLightList, + vector saturatedCnstSet) +{ + ConstraintLight* cnst = NULL; + Element* elem = NULL; + vector* elem_list; + std::vector::iterator it; + std::vector::iterator elemIt; + for (it=saturatedCnstSet.begin(); it!=saturatedCnstSet.end(); ++it) { + cnst = (*it); + elem_list = &(cnst->p_cnst->m_activeElementSet); + for (elemIt=elem_list->begin(); elemIt!=elem_list->end(); ++elemIt) { + elem = (*elemIt); + if (elem->p_variable->m_weight <= 0) + break; + if (elem->m_value >0) + m_saturatedVariableSet.push_back(elem->p_variable); + } + } +} + +void Element::activate() +{ + p_constraint->m_activeElementSet.push_back(this); +} + +void Element::inactivate() +{ + std::vector::iterator it; + vector elemSet = p_constraint->m_activeElementSet; + it = find(elemSet.begin(), elemSet.end(), this); + if (it != elemSet.end()) + elemSet.erase(it); +} + +void Solver::activateConstraint(ConstraintPtr cnst) +{ + m_activeConstraintSet.push_back(cnst); +} + +void Solver::inactivateConstraint(ConstraintPtr cnst) +{ + std::vector::iterator it; + it = find(m_activeConstraintSet.begin(), m_activeConstraintSet.end(), cnst); + if (it != m_activeConstraintSet.end()) + m_activeConstraintSet.erase(it); + m_modifiedConstraintSet.erase(std::find(m_modifiedConstraintSet.begin(), m_modifiedConstraintSet.end(), cnst)); +} + +template +void vector_remove_first(vector vec, T obj) { + typename vector::iterator it; + for (it=vec.begin(); it != vec.end(); ++it) { + if ((*it) == (obj)) { + vec.erase(it); + break; + } + } +} + +void Solver::print() +{ + //TODO +} + +void Solver::solve() +{ + Variable* var = NULL; + Constraint* cnst = NULL; + Element* elem = NULL; + vector* cnstList = NULL; + std::vector::iterator cnstIt; + vector* varList = NULL; + std::vector::iterator varIt; + vector* elemList = NULL; + std::vector::iterator elemIt; + vector* elemListB = NULL; + std::vector::iterator elemItB; + double minUsage = -1; + double minBound = -1; + + if (!m_modified) + return; + + XBT_IN("(sys=%p)", this); + + /* + * Compute Usage and store the variables that reach the maximum. + */ + cnstList = m_selectiveUpdateActive ? &m_modifiedConstraintSet : + &m_activeConstraintSet; + + XBT_DEBUG("Active constraintsSolver : %d", cnstList->size()); + /* Init: Only modified code portions */ + + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + elemList = &((*cnstIt)->m_elementSet); + for (elemIt=elemList->begin(); elemIt!=elemList->end(); ++elemIt) { + var = ((*elemIt)->p_variable); + if (var->m_weight <= 0.0) + break; + var->m_value = 0.0; + } + } + + vector cnstLightList; + std::vector::iterator cnstLightIt; + + vector saturatedConstraintSet; + saturatedConstraintSet.reserve(5); + + for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { + /* INIT */ + cnst = (*cnstIt); + if (cnst->m_remaining == 0) + continue; + cnst->m_usage = 0; + elemList = &(cnst->m_elementSet); + for (elemIt=elemList->begin(); elemIt!=elemList->end(); ++elemIt) { + /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */ + elem = (*elemIt); + if (elem->p_variable->m_weight <= 0) + break; + if ((elem->m_value > 0)) { + if (cnst->m_shared) + cnst->m_usage += elem->m_value / elem->p_variable->m_weight; + else if (cnst->m_usage < elem->m_value / elem->p_variable->m_weight) + cnst->m_usage = elem->m_value / elem->p_variable->m_weight; + + elem->activate(); + if (m_keepTrack.size()) //TODO: check good semantic + m_keepTrack.push_back(elem->p_variable->p_id); + } + } + XBT_DEBUG("Constraint Usage '%d' : %f", cnst->m_idInt, cnst->m_usage); + /* Saturated constraints update */ + if(cnst->m_usage > 0) { + ConstraintLightPtr cnstLight (new ConstraintLight((*cnstIt), cnst->m_remaining / cnst->m_usage)); + cnst->p_cnstLight = cnstLight; + saturatedConstraintSetUpdate(cnstLight->m_remainingOverUsage, cnstLight, saturatedConstraintSet, &minUsage); + cnstLightList.push_back(cnstLight); + } + } + + saturatedVariableSetUpdate(cnstLightList, saturatedConstraintSet); + + /* Saturated variables update */ + do { + /* Fix the variables that have to be */ + varList = &m_saturatedVariableSet; + + for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { + var = (*varIt); + if (var->m_weight <= 0.0) { + DIE_IMPOSSIBLE; + } + /* First check if some of these variables have reach their upper + bound and update min_usage accordingly. */ + XBT_DEBUG + ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f", + var->m_idInt, var->m_bound, var->m_weight, minUsage, + var->m_bound * var->m_weight); + + if ((var->m_bound > 0) && (var->m_bound * var->m_weight < minUsage)) { + if (minBound < 0) + minBound = var->m_bound; + else + minBound = MIN(minBound, var->m_bound); + XBT_DEBUG("Updated min_bound=%f", minBound); + } + } + + while (varList->size()>0) { + var = varList->front(); + int i; + + if (minBound < 0) { + var->m_value = minUsage / var->m_weight; + } else { + if (minBound == var->m_bound) + var->m_value = var->m_bound; + else { + vector_remove_first(*varList, varList->front()); + continue; + } + } + XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ", + minUsage, var->m_idInt, var->m_weight, var->m_idInt, var->m_value); + + /* Update usage */ + + for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { + elem = (*elemIt); + cnst = elem->p_constraint; + if (cnst->m_shared) { + double_update(&(cnst->m_remaining), elem->m_value * var->m_value); + double_update(&(cnst->m_usage), elem->m_value / var->m_weight); + if(cnst->m_usage<=0 || cnst->m_remaining<=0) { + if (cnst->p_cnstLight) { + // TODO: reformat message + XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p ", + elemIt - var->m_cnsts.begin(), var->m_cnsts.size(), cnst, cnst->p_cnstLight, &cnstLightList); + vector_remove_first(cnstLightList, cnst->p_cnstLight); + cnst->p_cnstLight = ConstraintLightPtr(); + } + } else { + cnst->p_cnstLight->m_remainingOverUsage = cnst->m_remaining / cnst->m_usage; + } + elem->inactivate(); + } else { + cnst->m_usage = 0.0; + elem->inactivate(); + elemListB = &(cnst->m_elementSet); + for (elemItB=elemListB->begin(); elemItB!=elemListB->end(); ++elemItB) { + elem = (*elemItB); + if (elem->p_variable->m_weight <= 0 || elem->p_variable->m_value > 0) + break; + if (elem->m_value > 0) + cnst->m_usage = MAX(cnst->m_usage, elem->m_value / elem->p_variable->m_weight); + } + if (cnst->m_usage<=0 || cnst->m_remaining<=0) { + if(cnst->p_cnstLight) { + vector_remove_first(cnstLightList, cnst->p_cnstLight); + // TODO: reformat message + XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p ", + elemIt - var->m_cnsts.begin(), var->m_cnsts.size(), cnst, cnst->p_cnstLight, &cnstLightList); + cnst->p_cnstLight = ConstraintLightPtr(); + } + } else { + cnst->p_cnstLight->m_remainingOverUsage = cnst->m_remaining / cnst->m_usage; + } + } + } + vector_remove_first(*varList, varList->front()); + } + + /* Find out which variables reach the maximum */ + minUsage = -1; + minBound = -1; + m_saturatedConstraintSet.clear(); + + for (cnstLightIt=cnstLightList.begin(); cnstLightIt!=cnstLightList.end(); ++cnstLightIt) + saturatedConstraintSetUpdate((*cnstLightIt)->m_remainingOverUsage, + (*cnstLightIt), + saturatedConstraintSet, + &minUsage); + saturatedVariableSetUpdate(cnstLightList, saturatedConstraintSet); + + } while (cnstLightList.size() > 0); + + m_modified = 0; + + if (m_selectiveUpdateActive) + removeAllModifiedSet(); + + + if (m_selectiveUpdateActive) + removeAllModifiedSet(); + + if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { + print(); + } + + /*TODO: xbt_free(saturated_constraint_set->data); + xbt_free(saturated_constraint_set); + xbt_free(cnst_light_tab);*/ + XBT_OUT(); +} + +/* Not a O(1) function */ + +void Solver::update(ConstraintPtr cnst, VariablePtr var, double value) +{ + std::vector::iterator it; + for (it=var->m_cnsts.begin(); it!=var->m_cnsts.end(); ++it ) + if ((*it)->p_constraint == cnst) { + (*it)->m_value = value; + m_modified = true; + updateModifiedSet(cnst); + return; + } +} + +/** \brief Attribute the value bound to var->bound. + * + * \param sys the lmm_system_t + * \param var the lmm_variable_t + * \param bound the new bound to associate with var + * + * Makes var->bound equal to bound. Whenever this function is called + * a change is signed in the system. To + * avoid false system changing detection it is a good idea to test + * (bound != 0) before calling it. + * + */ +void Solver::updateVariableBound(VariablePtr var, double bound) +{ + m_modified = 1; + var->m_bound = bound; + + if (var->m_cnsts.size() > 0) + updateModifiedSet(var->m_cnsts.front()->p_constraint); +} + +void Solver::updateVariableWeight(VariablePtr var, double weight) +{ + int i; + + if (weight == var->m_weight) + return; + XBT_IN("(sys=%p, var=%p, weight=%f)", this, var, weight); + m_modified = 1; + var->m_weight = weight; + vector_remove_first(m_variableSet, var); + if (weight) // TODO: use swap instead + m_variableSet.insert(m_variableSet.begin(), var); + else + m_variableSet.push_back(var); + + vector elemList; + vector::iterator it; + for (it=var->m_cnsts.begin(); it!=var->m_cnsts.end(); ++it ) { + elemList = (*it)->p_constraint->m_elementSet; + vector_remove_first(elemList, (*it)); + if (weight) + elemList.insert(elemList.begin(), *it); + else + elemList.push_back(*it); + if (it == var->m_cnsts.begin()) + updateModifiedSet((*it)->p_constraint); + } + if (!weight) + var->m_value = 0.0; + + XBT_OUT(); +} + +double Variable::getWeight() +{ return m_weight; } + +//XBT_INLINE +void Solver::updateConstraintBound(ConstraintPtr cnst, double bound) +{ + m_modified = 1; + updateModifiedSet(cnst); + cnst->m_bound = bound; +} + +//XBT_INLINE +bool Solver::constraintUsed(ConstraintPtr cnst) +{ + return std::find(m_activeConstraintSet.begin(), + m_activeConstraintSet.end(), cnst)!=m_activeConstraintSet.end(); +} + +//XBT_INLINE +ConstraintPtr Solver::getFirstActiveConstraint() +{ + return m_activeConstraintSet.front(); +} + +//XBT_INLINE +ConstraintPtr Solver::getNextActiveConstraint(ConstraintPtr cnst) +{ + return *(++std::find(m_activeConstraintSet.begin(), m_activeConstraintSet.end(), cnst)); +} + +#ifdef HAVE_LATENCY_BOUND_TRACKING +//XBT_INLINE +bool Variable::isLimitedByLatency() +{ + return (double_equals(m_bound, m_value)); +} +#endif + +/** \brief Update the constraint set propagating recursively to + * other constraints so the system should not be entirely computed. + * + * \param sys the lmm_system_t + * \param cnst the lmm_constraint_t affected by the change + * + * A recursive algorithm to optimize the system recalculation selecting only + * constraints that have changed. Each constraint change is propagated + * to the list of constraints for each variable. + */ +//static +void Solver::updateModifiedSetRec(ConstraintPtr cnst) +{ + std::vector::iterator elemIt; + for (elemIt=cnst->m_elementSet.begin(); elemIt!=cnst->m_elementSet.end(); ++elemIt) { + VariablePtr var = (*elemIt)->p_variable; + vector cnsts = var->m_cnsts; + std::vector::iterator cnstIt; + for (cnstIt=cnsts.begin(); var->m_visited != m_visitedCounter + && cnstIt!=cnsts.end(); ++cnstIt){ + if ((*cnstIt)->p_constraint != cnst + && std::find(m_modifiedConstraintSet.begin(), + m_modifiedConstraintSet.end(), (*cnstIt)->p_constraint) + == m_modifiedConstraintSet.end()) { + m_modifiedConstraintSet.push_back((*cnstIt)->p_constraint); + updateModifiedSetRec((*cnstIt)->p_constraint); + } + } + var->m_visited = m_visitedCounter; + } +} + +//static +void Solver::updateModifiedSet(ConstraintPtr cnst) +{ + /* nothing to do if selective update isn't active */ + if (m_selectiveUpdateActive + && std::find(m_modifiedConstraintSet.begin(), + m_modifiedConstraintSet.end(), cnst) + == m_modifiedConstraintSet.end()) { + m_modifiedConstraintSet.push_back(cnst); + updateModifiedSetRec(cnst); + } +} + +/** \brief Remove all constraints of the modified_constraint_set. + * + * \param sys the lmm_system_t + */ +//static +void Solver::removeAllModifiedSet() +{ + if (++m_visitedCounter == 1) { + /* the counter wrapped around, reset each variable->visited */ + std::vector::iterator it; + for (it=m_variableSet.begin(); it!=m_variableSet.end(); ++it) + (*it)->m_visited = 0; + } + m_modifiedConstraintSet.clear(); +} + +inline void Solver::disableVariable(VariablePtr var) +{ + int i; + bool m = false; + + ElementPtr elem; + + XBT_IN("(sys=%p, var=%p)", this, var); + m_modified = 1; + + std::vector::iterator varIt, elemIt; + for (varIt=var->m_cnsts.begin(); varIt!=var->m_cnsts.end(); ) { + vector elemSet = (*varIt)->p_constraint->m_elementSet; + elemSet.erase(std::find(elemSet.begin(), elemSet.end(), *varIt)); + vector activeElemSet = (*varIt)->p_constraint->m_activeElementSet; + activeElemSet.erase(std::find(activeElemSet.begin(), activeElemSet.end(), *varIt)); + if (elemSet.empty()) { + inactivateConstraint((*varIt)->p_constraint); + var->m_cnsts.erase(varIt); + } else { + ++varIt; + m = true; + } + } + if (m) + updateModifiedSet(var->m_cnsts.front()->p_constraint); + var->m_cnsts.clear(); + + XBT_OUT(); +} + +Constraint::Constraint(void *id, double bound): + p_id(id), m_idInt(1), m_bound(bound), m_usage(0), m_shared(1), + m_elementsZeroWeight(0) +{ + m_idInt = Global_const_debug_id++; +} + +void Constraint::addElement(ElementPtr elem) +{ + m_elementSet.push_back(elem); + if (elem->p_variable->m_weight<0) + std::swap(m_elementSet[m_elementSet.size()-1], m_elementSet[m_elementsZeroWeight++]); +} + +void Constraint::shared() { + m_shared = 0; +} + +bool Constraint::isShared() { + return m_shared; +} + +Variable::Variable(void *id, double weight, double bound, int visited) +{ + int i; + + // TODO: reformat + XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", + 0, id, weight, bound, 0); + + p_id = id; + m_idInt = Global_debug_id++; + + // TODO: optimize cache + + m_weight = weight; + m_bound = bound; + m_value = 0.0; + m_visited = visited;//sys->visited_counter - 1; + m_mu = 0.0; + m_newMu = 0.0; + //m_func_f = func_f_def; + //m_func_fp = func_fp_def; + //m_func_fpi = func_fpi_def; + + + XBT_OUT(" returns %p", this); +} + +double Variable::value() +{ + return m_value; +} + +double Variable::bound() +{ + return m_bound; +} + +Element::Element(ConstraintPtr cnst, VariablePtr var, double value): + p_constraint(cnst), p_variable(var), m_value(value) +{} + diff --git a/src/surf/solver.h b/src/surf/solver.h new file mode 100644 index 0000000000..e59483186f --- /dev/null +++ b/src/surf/solver.h @@ -0,0 +1,153 @@ +#include +#include + +#ifndef SURF_SOLVER_H_ +#define SURF_SOLVER_H_ + +static double MAXMIN_PRECISION = 0.001; +extern double sg_maxmin_precision; + +static XBT_INLINE int double_equals(double value1, double value2) +{ + return (fabs(value1 - value2) < MAXMIN_PRECISION); +} + +static XBT_INLINE void double_update(double *variable, double value) +{ + *variable -= value; + if (*variable < MAXMIN_PRECISION) + *variable = 0.0; +} + +#ifdef __cplusplus +#include +#include +#include +#include + +using namespace std; + +static XBT_INLINE int double_positive(double value) +{ + return (value > MAXMIN_PRECISION); +} + +class Solver; +class Element; +class Constraint; +class ConstraintLight; +class Variable; + +/*struct ElementPtrOps +{ + bool operator()( const ElementPtr & a, const ElementPtr & b ) + { return true; } //a > b; } +};*/ + +#else + typedef struct Solver Solver; + typedef struct Element Element; + typedef struct Constraint Constraint; + typedef struct ConstraintLight ConstraintLight; + typedef struct Variable Variable; + +#endif +typedef Element *ElementPtr; +typedef Variable *VariablePtr; +typedef Constraint *ConstraintPtr; +typedef ConstraintLight *ConstraintLightPtr; +typedef Solver *SolverPtr; + +typedef ElementPtr lmm_element_t; +typedef VariablePtr lmm_variable_t; +typedef ConstraintPtr lmm_constraint_t; +typedef ConstraintLightPtr lmm_constraint_light_t; +typedef SolverPtr lmm_system_t; + +extern double (*func_f_def) (lmm_variable_t, double); +extern double (*func_fp_def) (lmm_variable_t, double); +extern double (*func_fpi_def) (lmm_variable_t, double); + +#ifdef __cplusplus +extern "C" { +#endif + + extern void _simgrid_log_category__surf_lagrange__constructor__(void); + extern void _simgrid_log_category__surf_maxmin__constructor__(void); + extern void _simgrid_log_category__surf_lagrange_dichotomy__constructor__(void); + + extern void lmm_set_default_protocol_function(double (*func_f)(lmm_variable_t var, double x), + double (*func_fp) (lmm_variable_t var, double x), + double (*func_fpi) (lmm_variable_t var, double x)); + extern double func_reno_f(lmm_variable_t var, double x); + extern double func_reno_fp(lmm_variable_t var, double x); + extern double func_reno_fpi(lmm_variable_t var, double x); + extern double func_reno2_f(lmm_variable_t var, double x); + extern double func_reno2_fp(lmm_variable_t var, double x); + extern double func_reno2_fpi(lmm_variable_t var, double x); + extern double func_vegas_f(lmm_variable_t var, double x); + extern double func_vegas_fp(lmm_variable_t var, double x); + extern double func_vegas_fpi(lmm_variable_t var, double x); + + + //extern int double_equals(double value1, double value2); + //extern void double_update(double *variable, double value); + + extern lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys, lmm_constraint_t cnst, lmm_element_t * elem); + extern lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, lmm_variable_t var, int num); + extern double lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var, int num); + extern int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var); + + extern lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, + double weight_value, + double bound, + int number_of_constraints); + extern void *lmm_variable_id(lmm_variable_t var); + extern double lmm_variable_getvalue(lmm_variable_t var); + extern double lmm_get_variable_weight(lmm_variable_t var); + extern void lmm_variable_free(lmm_system_t sys, lmm_variable_t var); + + extern lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, + double bound_value); + extern void *lmm_constraint_id(lmm_constraint_t cnst); + extern void lmm_constraint_shared(lmm_constraint_t cnst); + extern int lmm_constraint_is_shared(lmm_constraint_t cnst); + extern int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst); + extern void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst); + + extern lmm_system_t lmm_system_new(int selective_update); + extern int lmm_system_modified(lmm_system_t solver); + extern void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value); + extern void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, + lmm_variable_t var, double value); + extern void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, + double bound); + extern void lmm_update_variable_weight(lmm_system_t sys, + lmm_variable_t var, + double weight); + extern void lmm_update_constraint_bound(lmm_system_t sys, + lmm_constraint_t cnst, + double bound); + extern void lmm_solve(lmm_system_t solver); + extern void lagrange_solve(lmm_system_t solver); + extern void bottleneck_solve(lmm_system_t solver); + extern void lmm_system_free(lmm_system_t solver); + + extern void c_function(lmm_system_t); /* ANSI C prototypes */ + extern lmm_system_t cplusplus_callback_function(lmm_system_t); + extern void lmm_print(lmm_system_t sys); + + /********* + * FIXES * + *********/ + extern int fix_constraint_is_active(lmm_system_t sys, lmm_constraint_t cnst); + +#ifdef __cplusplus +} +#endif + + + + + +#endif /* SURF_SOLVER_H_ */ diff --git a/src/surf/solver.hpp b/src/surf/solver.hpp new file mode 100644 index 0000000000..76d3275af8 --- /dev/null +++ b/src/surf/solver.hpp @@ -0,0 +1,174 @@ +#include +#include +#include "solver.h" +#include +#include + +#ifndef SURF_SOLVER_HPP_ +#define SURF_SOLVER_HPP_ +using namespace std; + +/*static void double_update(double *variable, double value) +{ + *variable -= value; + if (*variable < MAXMIN_PRECISION) + *variable = 0.0; +}*/ + +class Solver; +class Element; +class Constraint; +class ConstraintLight; +class Variable; + +struct ElementOps +{ + bool operator()( const Element & a, const Element & b ) + { return true; } //a > b; } +}; + +class Element { +public: + Element(ConstraintPtr cnst, VariablePtr var, double value); + ConstraintPtr p_constraint; + VariablePtr p_variable; + double m_value; + + void activate(); + void inactivate(); +}; + +class ConstraintLight { +public: + ConstraintLight(ConstraintPtr cnst, double remainingOverUsage): + m_remainingOverUsage(remainingOverUsage), p_cnst(cnst) {}; + double m_remainingOverUsage; + ConstraintPtr p_cnst; +}; + +class Constraint { +public: + Constraint(void *id, double bound); + ~Constraint() { + std::cout << "Del Const:" << m_bound << std::endl; + }; + + void shared(); + bool isShared(); + void* id(); + VariablePtr getVar(ElementPtr elem); + void addElement(ElementPtr elem); + + vector m_elementSet; /* a list of lmm_element_t */ + int m_elementsZeroWeight; + vector m_activeElementSet; /* a list of lmm_element_t */ + double m_remaining; + double m_usage; + double m_bound; + int m_shared; + void *p_id; + int m_idInt; + double m_lambda; + double m_newLambda; + ConstraintLightPtr p_cnstLight; +}; + +class Variable { +public: + Variable(void *id, double weight, double bound, int visited); + ~Variable() { + std::cout << "Del Variable" << std::endl; + }; + + double value(); + double bound(); + void* id(); + double getWeight(); + int getNumberOfCnst(); + ConstraintPtr getCnst(int num); + double getCnstWeight(int num); + double isLimitedByLatency(); + + /* \begin{For Lagrange only} */ + double (*p_funcF) (VariablePtr var, double x); /* (f) */ + double (*p_funcFP) (VariablePtr var, double x); /* (f') */ + double (*p_funcFPI) (VariablePtr var, double x); /* (f')^{-1} */ + /* \end{For Lagrange only} */ + vector m_cnsts; + + unsigned m_visited; /* used by lmm_update_modified_set */ + double m_weight; + double m_bound; + double m_value; + void *p_id; + int m_idInt; + double m_mu; + double m_newMu; + +protected: + /* \begin{For Lagrange only} */ + /* \end{For Lagrange only} */ +}; + +class Solver { +public: + Solver(int selective_update); + ~Solver() { + std::cout << "Del Solver" << std::endl; + } + + inline void disableVariable(VariablePtr var); + ConstraintPtr createConstraint(void *id, double bound_value); + VariablePtr createVariable(void *id, double weight, double bound); + void expand(ConstraintPtr cnst, VariablePtr var, double value); + void expandAdd(ConstraintPtr cnst, VariablePtr var, double value); + void elementSetValue(ConstraintPtr cnst, VariablePtr var, double value); + void saturatedConstraintSetUpdate(double usage, ConstraintLightPtr cnstLight, + vector saturatedConstraintSet, + double *minUsage); + void saturatedVariableSetUpdate(vector cnstLightList, + vector saturatedConstraintSet); + void solve(); + void update(ConstraintPtr cnst, VariablePtr var, double value); + void updateVariableBound(VariablePtr var, double bound); + void updateVariableWeight(VariablePtr var, double weight); + void updateConstraintBound(ConstraintPtr cnst, double bound); + bool constraintUsed(ConstraintPtr cnst); + ConstraintPtr getFirstActiveConstraint(); + ConstraintPtr getNextActiveConstraint(ConstraintPtr cnst); + void updateModifiedSetRec(ConstraintPtr cnst); + void updateModifiedSet(ConstraintPtr cnst); + void removeAllModifiedSet(); + void activateConstraint(ConstraintPtr cnst); + void inactivateConstraint(ConstraintPtr cnst); + void print(); + + vector m_variableSet; /* a list of lmm_variable_t */ + vector m_saturatedVariableSet; /* a list of lmm_variable_t */ + vector m_activeConstraintSet; /* a list of lmm_constraint_t */ + vector m_constraintSet; /* a list of lmm_constraint_t */ + vector m_modifiedConstraintSet; /* a list of modified lmm_constraint_t */ + vector m_saturatedConstraintSet; /* a list of lmm_constraint_t_t */ + + bool m_modified; +private: + + +protected: + bool m_selectiveUpdateActive; /* flag to update partially the system only selecting changed portions */ + unsigned m_visitedCounter; /* used by lmm_update_modified_set */ + + + boost::object_pool m_constraintAllocator; + boost::object_pool m_variableAllocator; + boost::object_pool m_elementAllocator; + void destroyConstraint(Constraint* cnst); + void destroyVariable(Variable* var); + void destroyElement(Element* elem); + + vector m_keepTrack; + + //xbt_mallocator_t variable_mallocator; +}; + +#endif /* SURF_SOLVER_H_ */ diff --git a/src/surf/solver_c.cpp b/src/surf/solver_c.cpp new file mode 100644 index 0000000000..5774f86d4f --- /dev/null +++ b/src/surf/solver_c.cpp @@ -0,0 +1,159 @@ +#include "solver.hpp" +#include +#include +#include + +double sg_maxmin_precision = 0.00001; +#define RENO_SCALING 1.0 + +void lmm_solve(lmm_system_t solver) +{ + solver->solve(); +} + +void lmm_print(lmm_system_t solver) +{ + solver->print(); +} + +lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys, lmm_constraint_t cnst, lmm_element_t * elem) +{ + cnst->getVar(*elem); +} + +lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, lmm_variable_t var, int num) +{ + var->getCnst(num); +} + +double lmm_get_cnst_weight_from_var(lmm_system_t sys, lmm_variable_t var, int num) +{ + var->getCnstWeight(num); +} + +int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var) +{ + var->getNumberOfCnst(); +} + +lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, + double weight_value, + double bound, + int number_of_constraints) +{ + return sys->createVariable(id, weight_value, bound); +} + +void *lmm_variable_id(lmm_variable_t var) +{ + return var->id(); +} + +double lmm_variable_getvalue(lmm_variable_t var) +{ + return var->m_value; +} + +double lmm_get_variable_weight(lmm_variable_t var) +{ + return var->m_weight; +} + +void lmm_variable_free(lmm_system_t sys, lmm_variable_t var) +{ + //TOREPAIR free +} + +lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, + double bound_value) +{ + return sys->createConstraint(id, bound_value); +} + +void *lmm_constraint_id(lmm_constraint_t cnst) +{ + return cnst->id(); +} + +void lmm_constraint_shared(lmm_constraint_t cnst) +{ + cnst->shared(); +} + +int lmm_constraint_is_shared(lmm_constraint_t cnst) +{ + return cnst->isShared(); +} + +int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) +{ + return (int) sys->constraintUsed(cnst); +} + +void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst) +{ + //TOREPAIR free +} + +lmm_system_t lmm_system_new(int selective_update) { + return new Solver(selective_update); +} + +void lmm_system_free(lmm_system_t sys) { + //TOREPAIR free +} + +int lmm_system_modified(lmm_system_t solver) +{ + solver->m_modified; +} +void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) +{ + sys->expand(cnst, var, value); +} + +void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, + lmm_variable_t var, double value) +{ + sys->expandAdd(cnst, var, value); +} + +void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, + double bound) +{ + sys->updateVariableBound(var, bound); +} + +void lmm_update_variable_weight(lmm_system_t sys, + lmm_variable_t var, + double weight) +{ + sys->updateVariableWeight(var, weight); +} + +void lmm_update_constraint_bound(lmm_system_t sys, + lmm_constraint_t cnst, + double bound) +{ + sys->updateConstraintBound(cnst, bound); +} + + +/********* + * FIXES * + *********/ +int fix_constraint_is_active(lmm_system_t sys, lmm_constraint_t cnst) +{ + int found = 0; + std::vector::iterator cnstIt; + lmm_constraint_t cnst_tmp; + for (cnstIt=sys->m_activeConstraintSet.begin(); cnstIt!=sys->m_activeConstraintSet.end(); ++cnstIt) { + cnst_tmp = *cnstIt; + if (cnst_tmp == cnst) { + found = 1; + break; + } + } + return found; +} + diff --git a/src/surf/storage.c b/src/surf/storage.c index df2d0d44cd..599210cb0d 100644 --- a/src/surf/storage.c +++ b/src/surf/storage.c @@ -163,8 +163,8 @@ static surf_action_t storage_action_execute (void *storage, size_t size, e_surf_ GENERIC_LMM_ACTION(action).suspended = 0; /* Should be useless because of the calloc but it seems to help valgrind... */ - GENERIC_LMM_ACTION(action).variable = - lmm_variable_new(storage_maxmin_system, action, 1.0, -1.0 , 3); + /* TOREPAIR GENERIC_LMM_ACTION(action).variable = + lmm_variable_new(storage_maxmin_system, action, 1.0, -1.0 , 3);*/ // Must be less than the max bandwidth for all actions lmm_expand(storage_maxmin_system, STORAGE->constraint, @@ -213,8 +213,9 @@ static void* storage_create_resource(const char* id, const char* model,const cha double Bconnection = atof(xbt_dict_get(storage_type->properties,"Bconnection")); XBT_DEBUG("Create resource with Bconnection '%f' Bread '%f' Bwrite '%f' and Size '%lu'",Bconnection,Bread,Bwrite,(unsigned long)storage_type->size); storage->constraint = lmm_constraint_new(storage_maxmin_system, storage, Bconnection); + /* TOREPAIR: storage->constraint = lmm_constraint_new(storage_maxmin_system, storage, Bconnection); storage->constraint_read = lmm_constraint_new(storage_maxmin_system, storage, Bread); - storage->constraint_write = lmm_constraint_new(storage_maxmin_system, storage, Bwrite); + storage->constraint_write = lmm_constraint_new(storage_maxmin_system, storage, Bwrite);*/ storage->content = parse_storage_content((char*)content_name,&(storage->used_size)); storage->size = storage_type->size; diff --git a/src/surf/surf_private.h b/src/surf/surf_private.h index dd54c47b5e..b6152bd44e 100644 --- a/src/surf/surf_private.h +++ b/src/surf/surf_private.h @@ -6,8 +6,8 @@ #ifndef _SURF_SURF_PRIVATE_H #define _SURF_SURF_PRIVATE_H +#include "surf/solver.h" #include "surf/surf.h" -#include "surf/maxmin.h" #include "surf/trace_mgr.h" #include "xbt/log.h" #include "surf/surfxml_parse.h" -- 2.20.1