From: Paul Bédaride Date: Tue, 17 Dec 2013 08:59:03 +0000 (+0100) Subject: Replace swag by boost::intrusive::list in surf X-Git-Tag: v3_11_beta~166 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/a21681e5aca1a37efb2e9001e5055dec94c5de41?hp=5809f0f4cd75ca84bb4b4f47185801ddd054c462 Replace swag by boost::intrusive::list in surf --- diff --git a/buildtools/Cmake/DefinePackages.cmake b/buildtools/Cmake/DefinePackages.cmake index 5239989043..a5b79c9fdb 100644 --- a/buildtools/Cmake/DefinePackages.cmake +++ b/buildtools/Cmake/DefinePackages.cmake @@ -10,7 +10,7 @@ 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/maxmin.hpp src/include/surf/random_mgr.h src/include/surf/surf.h src/include/surf/surf_resource.h @@ -46,7 +46,7 @@ set(EXTRA_DIST src/surf/gtnets/gtnets_interface.h src/surf/gtnets/gtnets_simulator.h src/surf/gtnets/gtnets_topology.h - src/surf/maxmin_private.h + src/surf/maxmin_private.hpp src/surf/network_interface.hpp src/surf/network_gtnets.hpp src/surf/network_ns3_private.h @@ -302,11 +302,11 @@ set(SURF_SRC src/surf/cpu_interface.cpp src/surf/cpu_ti.cpp src/surf/cpu_cas01.cpp - 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/maxmin.cpp src/surf/network_interface.cpp src/surf/network_cm02.cpp src/surf/network_smpi.cpp diff --git a/src/include/surf/surf.h b/src/include/surf/surf.h index ca461b8d8f..61ca8f9cea 100644 --- a/src/include/surf/surf.h +++ b/src/include/surf/surf.h @@ -212,12 +212,13 @@ static inline void *surf_storage_resource_by_name(const char *name){ XBT_PUBLIC(char *) surf_routing_edge_name(sg_routing_edge_t edge); XBT_PUBLIC(void *) surf_as_cluster_get_backbone(AS_t as); -XBT_PUBLIC(void) surf_as_cluster_set_backbone(AS_t as, void* backbone); +XBT_PUBLIC(void) surf_as_cluster_set_backbone(AS_t as, void* backbone); XBT_PUBLIC(const char *) surf_model_name(surf_model_t model); -XBT_PUBLIC(xbt_swag_t) surf_model_done_action_set(surf_model_t model); -XBT_PUBLIC(xbt_swag_t) surf_model_failed_action_set(surf_model_t model); -XBT_PUBLIC(xbt_swag_t) surf_model_ready_action_set(surf_model_t model); -XBT_PUBLIC(xbt_swag_t) surf_model_running_action_set(surf_model_t model); +XBT_PUBLIC(surf_action_t) surf_model_extract_done_action_set(surf_model_t model); +XBT_PUBLIC(surf_action_t) surf_model_extract_failed_action_set(surf_model_t model); +XBT_PUBLIC(surf_action_t) surf_model_extract_ready_action_set(surf_model_t model); +XBT_PUBLIC(surf_action_t) surf_model_extract_running_action_set(surf_model_t model); +XBT_PUBLIC(int) surf_model_running_action_set_size(surf_model_t model); XBT_PUBLIC(surf_action_t) surf_workstation_model_execute_parallel_task(surf_workstation_model_t model, int workstation_nb, void **workstation_list, diff --git a/src/simdag/sd_global.c b/src/simdag/sd_global.c index c34f3d94b0..cbfc3713aa 100644 --- a/src/simdag/sd_global.c +++ b/src/simdag/sd_global.c @@ -313,7 +313,7 @@ xbt_swag_t SD_simulate_swag(double how_long) { /* FIXME: shoud look at model_list or model_list_invoke? */ /* let's see which tasks are done */ xbt_dynar_foreach(model_list, iter, model) { - while ((action = xbt_swag_extract(surf_model_done_action_set(model)))) { + while ((action = surf_model_extract_done_action_set(model))) { task = surf_action_get_data(action); task->start_time = surf_action_get_start_time(task->surf_action); @@ -380,7 +380,7 @@ xbt_swag_t SD_simulate_swag(double how_long) { } /* let's see which tasks have just failed */ - while ((action = xbt_swag_extract(surf_model_failed_action_set(model)))) { + while ((action = surf_model_extract_failed_action_set(model))) { task = surf_action_get_data(action); task->start_time = surf_action_get_start_time(task->surf_action); task->finish_time = surf_get_clock(); diff --git a/src/simix/smx_global.c b/src/simix/smx_global.c index e1f793e180..c80ef70ab9 100644 --- a/src/simix/smx_global.c +++ b/src/simix/smx_global.c @@ -215,7 +215,6 @@ void SIMIX_run(void) { double time = 0; smx_process_t process; - xbt_swag_t set; surf_action_t action; smx_timer_t timer; surf_model_t model; @@ -327,13 +326,11 @@ void SIMIX_run(void) /* Wake up all processes waiting for a Surf action to finish */ xbt_dynar_foreach(model_list, iter, model) { - set = surf_model_failed_action_set(model); - while ((action = xbt_swag_extract(set))) + while ((action = surf_model_extract_failed_action_set(model))) SIMIX_simcall_post((smx_action_t) surf_action_get_data(action)); - set = surf_model_done_action_set(model); - while ((action = xbt_swag_extract(set))) + while ((action = surf_model_extract_done_action_set(model))) if (surf_action_get_data(action) == NULL) XBT_DEBUG("probably vcpu's action %p, skip", action); else diff --git a/src/surf/cpu_cas01.cpp b/src/surf/cpu_cas01.cpp index 7d15235c6d..9d99c6a86a 100644 --- a/src/surf/cpu_cas01.cpp +++ b/src/surf/cpu_cas01.cpp @@ -6,7 +6,7 @@ #include "cpu_cas01.hpp" #include "cpu_ti.hpp" -#include "maxmin_private.h" +#include "maxmin_private.hpp" #include "simgrid/sg_config.h" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_cpu_cas, surf_cpu, @@ -57,9 +57,6 @@ void surf_cpu_model_init_Cas01() CpuCas01Model::CpuCas01Model() : CpuModel("cpu") { - ActionPtr action = NULL; - ActionLmmPtr actionlmm = NULL; - char *optim = xbt_cfg_get_string(_sg_cfg_set, "cpu/optim"); int select = xbt_cfg_get_boolean(_sg_cfg_set, "cpu/maxmin_selective_update"); @@ -78,8 +75,7 @@ CpuCas01Model::CpuCas01Model() : CpuModel("cpu") xbt_die("Unsupported optimization (%s) for this model", optim); } - p_cpuRunningActionSetThatDoesNotNeedBeingChecked = - xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); + p_cpuRunningActionSetThatDoesNotNeedBeingChecked = new ActionList(); if (getUpdateMechanism() == UM_LAZY) { shareResources = &CpuCas01Model::shareResourcesLazy; @@ -98,7 +94,7 @@ CpuCas01Model::CpuCas01Model() : CpuModel("cpu") if (getUpdateMechanism() == UM_LAZY) { p_actionHeap = xbt_heap_new(8, NULL); xbt_heap_set_update_callback(p_actionHeap, surf_action_lmm_update_index_heap); - p_modifiedSet = xbt_swag_new(xbt_swag_offset(*actionlmm, p_actionListHookup)); + p_modifiedSet = new ActionLmmList(); p_maxminSystem->keep_track = p_modifiedSet; } } @@ -110,11 +106,11 @@ CpuCas01Model::~CpuCas01Model() if (p_actionHeap) xbt_heap_free(p_actionHeap); - xbt_swag_free(p_modifiedSet); + delete p_modifiedSet; surf_cpu_model_pm = NULL; - xbt_swag_free(p_cpuRunningActionSetThatDoesNotNeedBeingChecked); + delete p_cpuRunningActionSetThatDoesNotNeedBeingChecked; } void CpuCas01Model::parseInit(sg_platf_host_cbarg_t host) @@ -323,9 +319,9 @@ CpuActionPtr CpuCas01Lmm::sleep(double duration) if (duration == NO_MAX_DURATION) { /* Move to the *end* of the corresponding action set. This convention is used to speed up update_resource_state */ - xbt_swag_remove(static_cast(action), action->getStateSet()); + action->getStateSet()->erase(action->getStateSet()->iterator_to(*action)); action->p_stateSet = static_cast(getModel())->p_cpuRunningActionSetThatDoesNotNeedBeingChecked; - xbt_swag_insert(static_cast(action), action->getStateSet()); + action->getStateSet()->push_back(*action); } lmm_update_variable_weight(surf_cpu_model_pm->getMaxminSystem(), @@ -335,7 +331,7 @@ CpuActionPtr CpuCas01Lmm::sleep(double duration) // this is necessary for a variable with weight 0 since such // variables are ignored in lmm and we need to set its max_duration // correctly at the next call to share_resources - xbt_swag_insert_at_head(static_cast(action), surf_cpu_model_pm->getModifiedSet()); + surf_cpu_model_pm->getModifiedSet()->push_front(*action); } XBT_OUT(); diff --git a/src/surf/cpu_cas01.hpp b/src/surf/cpu_cas01.hpp index 7fc07d0a52..ccac472ce1 100644 --- a/src/surf/cpu_cas01.hpp +++ b/src/surf/cpu_cas01.hpp @@ -32,7 +32,7 @@ public: xbt_dict_t cpu_properties); double shareResourcesFull(double now); void addTraces(); - xbt_swag_t p_cpuRunningActionSetThatDoesNotNeedBeingChecked; + ActionListPtr p_cpuRunningActionSetThatDoesNotNeedBeingChecked; }; /************ diff --git a/src/surf/cpu_interface.cpp b/src/surf/cpu_interface.cpp index dd9ee5a276..fa64436210 100644 --- a/src/surf/cpu_interface.cpp +++ b/src/surf/cpu_interface.cpp @@ -13,7 +13,6 @@ CpuModelPtr surf_cpu_model_vm; void CpuModel::updateActionsStateLazy(double now, double /*delta*/) { - void *_action; CpuActionLmmPtr action; while ((xbt_heap_size(getActionHeap()) > 0) && (double_equals(xbt_heap_maxkey(getActionHeap()), now))) { @@ -44,9 +43,10 @@ void CpuModel::updateActionsStateLazy(double now, double /*delta*/) //defining the last timestamp that we can safely dump to trace file //without losing the event ascending order (considering all CPU's) double smaller = -1; - xbt_swag_t actionSet = getRunningActionSet(); - xbt_swag_foreach(_action, actionSet) { - action = dynamic_cast(static_cast(_action)); + ActionListPtr actionSet = getRunningActionSet(); + for(ActionList::iterator it(actionSet->begin()), itend(actionSet->end()) + ; it != itend ; ++it) { + action = dynamic_cast(&*it); if (smaller < 0) { smaller = action->getLastUpdate(); continue; @@ -65,12 +65,13 @@ void CpuModel::updateActionsStateLazy(double now, double /*delta*/) void CpuModel::updateActionsStateFull(double now, double delta) { - void *_action, *_next_action; CpuActionLmmPtr action = NULL; - xbt_swag_t running_actions = getRunningActionSet(); + ActionListPtr running_actions = getRunningActionSet(); - xbt_swag_foreach_safe(_action, _next_action, running_actions) { - action = dynamic_cast(static_cast(_action)); + for(ActionList::iterator it(running_actions->begin()), itNext=it, itend(running_actions->end()) + ; it != itend ; it=itNext) { + ++itNext; + action = dynamic_cast(&*it); #ifdef HAVE_TRACING if (TRACE_is_enabled()) { CpuPtr x = (CpuPtr) lmm_constraint_id(lmm_get_cnst_from_var diff --git a/src/surf/cpu_interface.hpp b/src/surf/cpu_interface.hpp index 7cc5905a7e..852e63757a 100644 --- a/src/surf/cpu_interface.hpp +++ b/src/surf/cpu_interface.hpp @@ -1,5 +1,5 @@ #include "surf_interface.hpp" -#include "maxmin_private.h" +#include "maxmin_private.hpp" #ifndef SURF_CPU_INTERFACE_HPP_ #define SURF_CPU_INTERFACE_HPP_ diff --git a/src/surf/cpu_ti.cpp b/src/surf/cpu_ti.cpp index b7e0362e2e..2f0d04405d 100644 --- a/src/surf/cpu_ti.cpp +++ b/src/surf/cpu_ti.cpp @@ -408,11 +408,9 @@ void surf_cpu_model_init_ti() CpuTiModel::CpuTiModel() : CpuModel("cpu_ti") { - ActionPtr action = NULL; CpuTiPtr cpu = NULL; - p_runningActionSetThatDoesNotNeedBeingChecked = - xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); + p_runningActionSetThatDoesNotNeedBeingChecked = new ActionList(); p_modifiedCpu = xbt_swag_new(xbt_swag_offset(*cpu, p_modifiedCpuHookup)); @@ -426,7 +424,7 @@ CpuTiModel::~CpuTiModel() { surf_cpu_model_pm = NULL; - xbt_swag_free(p_runningActionSetThatDoesNotNeedBeingChecked); + delete p_runningActionSetThatDoesNotNeedBeingChecked; xbt_swag_free(p_modifiedCpu); xbt_heap_free(p_tiActionHeap); } @@ -846,9 +844,9 @@ CpuActionPtr CpuTi::sleep(double duration) if (duration == NO_MAX_DURATION) { /* Move to the *end* of the corresponding action set. This convention is used to speed up update_resource_state */ - xbt_swag_remove(static_cast(action), action->getStateSet()); + action->getStateSet()->erase(action->getStateSet()->iterator_to(*action)); action->p_stateSet = reinterpret_cast(getModel())->p_runningActionSetThatDoesNotNeedBeingChecked; - xbt_swag_insert(static_cast(action), action->getStateSet()); + action->getStateSet()->push_back(*static_cast(action)); } xbt_swag_insert(action, p_actionSet); @@ -896,7 +894,8 @@ int CpuTiAction::unref() { m_refcount--; if (!m_refcount) { - xbt_swag_remove(static_cast(this), getStateSet()); + if (actionHook::is_linked()) + getStateSet()->erase(getStateSet()->iterator_to(*this)); /* remove from action_set */ xbt_swag_remove(this, p_cpu->p_actionSet); /* remove from heap */ diff --git a/src/surf/cpu_ti.hpp b/src/surf/cpu_ti.hpp index 7e27e52b2e..35a85dcf7e 100644 --- a/src/surf/cpu_ti.hpp +++ b/src/surf/cpu_ti.hpp @@ -92,7 +92,7 @@ public: void updateActionsState(double now, double delta); void addTraces(); - xbt_swag_t p_runningActionSetThatDoesNotNeedBeingChecked; + ActionListPtr p_runningActionSetThatDoesNotNeedBeingChecked; xbt_swag_t p_modifiedCpu; xbt_heap_t p_tiActionHeap; diff --git a/src/surf/fair_bottleneck.c b/src/surf/fair_bottleneck.c deleted file mode 100644 index 8830107a0a..0000000000 --- a/src/surf/fair_bottleneck.c +++ /dev/null @@ -1,181 +0,0 @@ -/* Copyright (c) 2007-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 "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 index b4a09948f0..0b8a77acfd 100644 --- a/src/surf/fair_bottleneck.cpp +++ b/src/surf/fair_bottleneck.cpp @@ -1,12 +1,13 @@ -/* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team. +/* Copyright (c) 2007-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 "solver.hpp" +#include "maxmin_private.hpp" #include #include @@ -17,176 +18,172 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin); void bottleneck_solve(lmm_system_t sys) { - lmm_variable_t var_next = NULL; + void *_var, *_var_next, *_cnst, *_cnst_next, *_elem; + lmm_variable_t var = NULL; lmm_constraint_t cnst = NULL; - //s_lmm_constraint_t s_cnst; - lmm_constraint_t cnst_next = NULL; + s_lmm_constraint_t s_cnst; + 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; - vector cnstToUpdate; - if (!(lmm_system_modified(sys))) + if (!(sys->modified)) return; /* Init */ + xbt_swag_init(&(cnst_to_update), + xbt_swag_offset(s_cnst, saturated_constraint_set_hookup)); - 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) { + var_list = &(sys->variable_set); + XBT_DEBUG("Variable set : %d", xbt_swag_size(var_list)); + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; int nb = 0; - var = *varIt; - var->m_value = 0.0; + var->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_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); - sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var)); - var->m_value = 1.0; + var); + xbt_swag_remove(var, &(sys->saturated_variable_set)); + var->value = 1.0; } - if (var->m_weight <= 0.0) { + if (var->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)); + xbt_swag_remove(var, &(sys->saturated_variable_set)); } } - 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; + 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) { + cnst = (lmm_constraint_t)_cnst; + xbt_swag_insert(cnst, &(sys->saturated_constraint_set)); + } + cnst_list = &(sys->saturated_constraint_set); + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; + 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 *******", - cnstList->size()); - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();){ - cnst = *cnstIt; + xbt_swag_size(cnst_list)); + xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) { + cnst = (lmm_constraint_t)_cnst; 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) + elem_list = &(cnst->element_set); + cnst->usage = 0.0; + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; + if (elem->variable->weight <= 0) break; - if ((elem->m_value > 0) - && std::find(varList->begin(), varList->end(), elem->p_variable)!=varList->end()); + if ((elem->value > 0) + && xbt_swag_belongs(elem->variable, var_list)) nb++; } XBT_DEBUG("\tThere are %d variables", nb); - if (nb > 0 && !cnst->m_shared) + if (nb > 0 && !cnst->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)); + cnst->remaining = 0.0; + cnst->usage = cnst->remaining; + xbt_swag_remove(cnst, cnst_list); continue; } - cnst->m_usage = cnst->m_remaining / nb; + cnst->usage = cnst->remaining / nb; XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst, - cnst->m_usage, nb); - ++cnstIt; + cnst->usage, nb); } - 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); + xbt_swag_foreach_safe(_var, _var_next, var_list) { + var = (lmm_variable_t)_var; + 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); } - 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_swag_foreach_safe(_cnst, _cnst_next, cnst_list) { + cnst = (lmm_constraint_t)_cnst; 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) + elem_list = &(cnst->element_set); + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; + if (elem->variable->weight <= 0) break; - if (cnst->m_shared) { + if (cnst->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); + 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->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); + cnst, cnst->usage, elem->variable, elem->variable->mu); + cnst->usage = MIN(cnst->usage, elem->value * elem->variable->mu); } } - - if (!cnst->m_shared) { + if (!cnst->shared) { XBT_DEBUG("\tUpdate constraint %p (%g) by %g", - cnst, cnst->m_remaining, cnst->m_usage); + cnst, cnst->remaining, cnst->usage); - double_update(&(cnst->m_remaining), cnst->m_usage); + double_update(&(cnst->remaining), cnst->usage); } - XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->m_remaining); - if (cnst->m_remaining == 0.0) { + XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->remaining); + if (cnst->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) + xbt_swag_remove(cnst, cnst_list); + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; + if (elem->variable->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)); + if (elem->value > 0) { + XBT_DEBUG("\t\tGet rid of variable %p", elem->variable); + xbt_swag_remove(elem->variable, var_list); } } - } else - ++cnstIt; + } } - } while (!varList->empty()); - - cnstList->clear(); - sys->m_modified = 0; + } 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"); - sys->print(); + lmm_print(sys); } } diff --git a/src/surf/lagrange.c b/src/surf/lagrange.c deleted file mode 100644 index a07c2684f6..0000000000 --- a/src/surf/lagrange.c +++ /dev/null @@ -1,656 +0,0 @@ -/* Copyright (c) 2007-2013. 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. */ - -/* - * Modelling the proportional fairness using the Lagrange Optimization - * Approach. For a detailed description see: - * "ssh://username@scm.gforge.inria.fr/svn/memo/people/pvelho/lagrange/ppf.ps". - */ -#include "xbt/log.h" -#include "xbt/sysdep.h" -#include "maxmin_private.h" - -#include -#ifndef MATH -#include -#endif - -XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf, - "Logging specific to SURF (lagrange)"); -XBT_LOG_NEW_SUBCATEGORY(surf_lagrange_dichotomy, surf_lagrange, - "Logging specific to SURF (lagrange dichotomy)"); - -#define SHOW_EXPR(expr) XBT_CDEBUG(surf_lagrange,#expr " = %g",expr); - -double (*func_f_def) (lmm_variable_t, double); -double (*func_fp_def) (lmm_variable_t, double); -double (*func_fpi_def) (lmm_variable_t, double); - -/* - * Local prototypes to implement the lagrangian optimization with optimal step, also called dichotomy. - */ -//solves the proportional fairness using a lagrange optimizition with dichotomy step -void lagrange_solve(lmm_system_t sys); -//computes the value of the dichotomy using a initial values, init, with a specific variable or constraint -static double dichotomy(double init, double diff(double, void *), - void *var_cnst, double min_error); -//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, - int warn) -{ - xbt_swag_t elem_list = NULL; - lmm_element_t elem = NULL; - lmm_constraint_t cnst = NULL; - lmm_variable_t var = NULL; - - double tmp; - - xbt_swag_foreach(cnst, cnst_list) { - tmp = 0; - elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { - var = elem->variable; - if (var->weight <= 0) - continue; - tmp += var->value; - } - - if (double_positive(tmp - cnst->bound)) { - if (warn) - XBT_WARN - ("The link (%p) is over-used. Expected less than %f and got %f", - cnst, cnst->bound, tmp); - return 0; - } - XBT_DEBUG - ("Checking feasability for constraint (%p): sat = %f, lambda = %f ", - cnst, tmp - cnst->bound, cnst->lambda); - } - - xbt_swag_foreach(var, var_list) { - if (!var->weight) - break; - if (var->bound < 0) - continue; - XBT_DEBUG("Checking feasability for variable (%p): sat = %f mu = %f", var, - var->value - var->bound, var->mu); - - if (double_positive(var->value - var->bound)) { - if (warn) - XBT_WARN - ("The variable (%p) is too large. Expected less than %f and got %f", - var, var->bound, var->value); - return 0; - } - } - return 1; -} - -static double new_value(lmm_variable_t var) -{ - double tmp = 0; - int i; - - for (i = 0; i < var->cnsts_number; i++) { - tmp += (var->cnsts[i].constraint)->lambda; - } - if (var->bound > 0) - tmp += var->mu; - XBT_DEBUG("\t Working on var (%p). cost = %e; Weight = %e", var, tmp, - var->weight); - //uses the partial differential inverse function - return var->func_fpi(var, tmp); -} - -static double new_mu(lmm_variable_t var) -{ - double mu_i = 0.0; - double sigma_i = 0.0; - int j; - - for (j = 0; j < var->cnsts_number; j++) { - sigma_i += (var->cnsts[j].constraint)->lambda; - } - mu_i = var->func_fp(var, var->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) -{ - lmm_constraint_t cnst = NULL; - lmm_variable_t var = NULL; - - double obj = 0.0; - - xbt_swag_foreach(var, var_list) { - double sigma_i = 0.0; - int j; - - if (!var->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; - - 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); - - if (var->bound > 0) - obj += var->mu * var->bound; - } - - xbt_swag_foreach(cnst, cnst_list) - obj += cnst->lambda * cnst->bound; - - return obj; -} - -void lagrange_solve(lmm_system_t sys) -{ - /* - * Lagrange Variables. - */ - int max_iterations = 100; - double epsilon_min_error = MAXMIN_PRECISION; - double dichotomy_min_error = 1e-14; - double overall_modification = 1; - - /* - * Variables to manipulate the data structure proposed to model the maxmin - * fairness. See docummentation for more details. - */ - xbt_swag_t cnst_list = NULL; - lmm_constraint_t cnst = NULL; - - xbt_swag_t var_list = NULL; - lmm_variable_t var = NULL; - - /* - * Auxiliary variables. - */ - int iteration = 0; - double tmp = 0; - int i; - double obj, new_obj; - - XBT_DEBUG("Iterative method configuration snapshot =====>"); - XBT_DEBUG("#### Maximum number of iterations : %d", max_iterations); - XBT_DEBUG("#### Minimum error tolerated : %e", - epsilon_min_error); - XBT_DEBUG("#### Minimum error tolerated (dichotomy) : %e", - dichotomy_min_error); - - if (XBT_LOG_ISENABLED(surf_lagrange, xbt_log_priority_debug)) { - lmm_print(sys); - } - - if (!(sys->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); - } - - /* - * Initialize the var list variable with only the active variables. - * Associate an index in the swag variables. Initialize mu. - */ - var_list = &(sys->variable_set); - i = 0; - xbt_swag_foreach(var, var_list) { - if (!var->weight) - var->value = 0.0; - else { - int nb = 0; - if (var->bound < 0.0) { - XBT_DEBUG("#### NOTE var(%d) is a boundless variable", i); - var->mu = -1.0; - var->value = new_value(var); - } else { - var->mu = 1.0; - var->new_mu = 2.0; - var->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) - nb++; - } - if (nb == var->cnsts_number) - var->value = 1.0; - } - } - - /* - * Compute dual objective. - */ - obj = dual_objective(var_list, cnst_list); - - /* - * While doesn't reach a minimun error or a number maximum of iterations. - */ - while (overall_modification > epsilon_min_error - && iteration < max_iterations) { -/* int dual_updated=0; */ - - iteration++; - XBT_DEBUG("************** ITERATION %d **************", iteration); - XBT_DEBUG("-------------- Gradient Descent ----------"); - - /* - * Improve the value of mu_i - */ - xbt_swag_foreach(var, var_list) { - if (!var->weight) - break; - if (var->bound >= 0) { - XBT_DEBUG("Working on var (%p)", var); - var->new_mu = 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; - - new_obj = dual_objective(var_list, cnst_list); - XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, - obj - new_obj); - xbt_assert(obj - new_obj >= -epsilon_min_error, - "Our gradient sucks! (%1.20f)", obj - new_obj); - obj = new_obj; - } - } - - /* - * Improve the value of lambda_i - */ - xbt_swag_foreach(cnst, cnst_list) { - XBT_DEBUG("Working on cnst (%p)", cnst); - cnst->new_lambda = - dichotomy(cnst->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; - - new_obj = dual_objective(var_list, cnst_list); - XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, - obj - new_obj); - xbt_assert(obj - new_obj >= -epsilon_min_error, - "Our gradient sucks! (%1.20f)", obj - new_obj); - obj = new_obj; - } - - /* - * Now computes the values of each variable (\rho) based on - * the values of \lambda and \mu. - */ - XBT_DEBUG("-------------- Check convergence ----------"); - overall_modification = 0; - xbt_swag_foreach(var, var_list) { - if (var->weight <= 0) - var->value = 0.0; - else { - tmp = new_value(var); - - overall_modification = - MAX(overall_modification, fabs(var->value - tmp)); - - var->value = tmp; - XBT_DEBUG("New value of var (%p) = %e, overall_modification = %e", - var, var->value, overall_modification); - } - } - - XBT_DEBUG("-------------- Check feasability ----------"); - if (!__check_feasible(cnst_list, var_list, 0)) - overall_modification = 1.0; - XBT_DEBUG("Iteration %d: overall_modification : %f", iteration, - overall_modification); -/* if(!dual_updated) { */ -/* XBT_WARN("Could not improve the convergence at iteration %d. Drop it!",iteration); */ -/* break; */ -/* } */ - } - - __check_feasible(cnst_list, var_list, 1); - - if (overall_modification <= epsilon_min_error) { - XBT_DEBUG("The method converges in %d iterations.", iteration); - } - if (iteration >= max_iterations) { - XBT_DEBUG - ("Method reach %d iterations, which is the maximum number of iterations allowed.", - iteration); - } -/* XBT_INFO("Method converged after %d iterations", iteration); */ - - if (XBT_LOG_ISENABLED(surf_lagrange, xbt_log_priority_debug)) { - lmm_print(sys); - } -} - -/* - * Returns a double value corresponding to the result of a dichotomy proccess with - * respect to a given variable/constraint (\mu in the case of a variable or \lambda in - * case of a constraint) and a initial value init. - * - * @param init initial value for \mu or \lambda - * @param diff a function that computes the differential of with respect a \mu or \lambda - * @param var_cnst a pointer to a variable or constraint - * @param min_erro a minimun error tolerated - * - * @return a double correponding to the result of the dichotomyal process - */ -static double dichotomy(double init, double diff(double, void *), - void *var_cnst, double min_error) -{ - double min, max; - double overall_error; - double middle; - double min_diff, max_diff, middle_diff; - double diff_0 = 0.0; - min = max = init; - - XBT_IN(); - - if (init == 0.0) { - min = max = 0.5; - } - - min_diff = max_diff = middle_diff = 0.0; - overall_error = 1; - - if ((diff_0 = diff(1e-16, var_cnst)) >= 0) { - XBT_CDEBUG(surf_lagrange_dichotomy, "returning 0.0 (diff = %e)", diff_0); - XBT_OUT(); - return 0.0; - } - - min_diff = diff(min, var_cnst); - max_diff = diff(max, var_cnst); - - while (overall_error > min_error) { - XBT_CDEBUG(surf_lagrange_dichotomy, - "[min, max] = [%1.20f, %1.20f] || diffmin, diffmax = %1.20f, %1.20f", - min, max, min_diff, max_diff); - - if (min_diff > 0 && max_diff > 0) { - if (min == max) { - XBT_CDEBUG(surf_lagrange_dichotomy, "Decreasing min"); - min = min / 2.0; - min_diff = diff(min, var_cnst); - } else { - XBT_CDEBUG(surf_lagrange_dichotomy, "Decreasing max"); - max = min; - max_diff = min_diff; - } - } else if (min_diff < 0 && max_diff < 0) { - if (min == max) { - XBT_CDEBUG(surf_lagrange_dichotomy, "Increasing max"); - max = max * 2.0; - max_diff = diff(max, var_cnst); - } else { - XBT_CDEBUG(surf_lagrange_dichotomy, "Increasing min"); - min = max; - min_diff = max_diff; - } - } else if (min_diff < 0 && max_diff > 0) { - middle = (max + min) / 2.0; - XBT_CDEBUG(surf_lagrange_dichotomy, "Trying (max+min)/2 : %1.20f", - middle); - - if ((min == middle) || (max == middle)) { - XBT_CWARN(surf_lagrange_dichotomy, - "Cannot improve the convergence! min=max=middle=%1.20f, diff = %1.20f." - " Reaching the 'double' limits. Maybe scaling your function would help ([%1.20f,%1.20f]).", - min, max - min, min_diff, max_diff); - break; - } - middle_diff = diff(middle, var_cnst); - - if (middle_diff < 0) { - XBT_CDEBUG(surf_lagrange_dichotomy, "Increasing min"); - min = middle; - overall_error = max_diff - middle_diff; - min_diff = middle_diff; -/* SHOW_EXPR(overall_error); */ - } else if (middle_diff > 0) { - XBT_CDEBUG(surf_lagrange_dichotomy, "Decreasing max"); - max = middle; - overall_error = max_diff - middle_diff; - max_diff = middle_diff; -/* SHOW_EXPR(overall_error); */ - } else { - overall_error = 0; -/* SHOW_EXPR(overall_error); */ - } - } else if (min_diff == 0) { - max = min; - overall_error = 0; -/* SHOW_EXPR(overall_error); */ - } else if (max_diff == 0) { - min = max; - overall_error = 0; -/* SHOW_EXPR(overall_error); */ - } else if (min_diff > 0 && max_diff < 0) { - XBT_CWARN(surf_lagrange_dichotomy, - "The impossible happened, partial_diff(min) > 0 && partial_diff(max) < 0"); - xbt_abort(); - } else { - XBT_CWARN(surf_lagrange_dichotomy, - "diffmin (%1.20f) or diffmax (%1.20f) are something I don't know, taking no action.", - min_diff, max_diff); - xbt_abort(); - } - } - - XBT_CDEBUG(surf_lagrange_dichotomy, "returning %e", (min + max) / 2.0); - XBT_OUT(); - return ((min + max) / 2.0); -} - -static double partial_diff_lambda(double lambda, void *param_cnst) -{ - - int j; - xbt_swag_t elem_list = NULL; - lmm_element_t elem = NULL; - lmm_variable_t var = NULL; - lmm_constraint_t cnst = (lmm_constraint_t) param_cnst; - double diff = 0.0; - double sigma_i = 0.0; - - XBT_IN(); - elem_list = &(cnst->element_set); - - XBT_CDEBUG(surf_lagrange_dichotomy, "Computing diff of cnst (%p)", cnst); - - xbt_swag_foreach(elem, elem_list) { - var = elem->variable; - if (var->weight <= 0) - continue; - - XBT_CDEBUG(surf_lagrange_dichotomy, "Computing sigma_i for var (%p)", - var); - // Initialize the summation variable - sigma_i = 0.0; - - // Compute sigma_i - for (j = 0; j < var->cnsts_number; j++) { - sigma_i += (var->cnsts[j].constraint)->lambda; - } - - //add mu_i if this flow has a RTT constraint associated - if (var->bound > 0) - sigma_i += var->mu; - - //replace value of cnst->lambda by the value of parameter lambda - sigma_i = (sigma_i - cnst->lambda) + lambda; - - diff += -var->func_fpi(var, sigma_i); - } - - - diff += cnst->bound; - - XBT_CDEBUG(surf_lagrange_dichotomy, - "d D/d lambda for cnst (%p) at %1.20f = %1.20f", cnst, lambda, - diff); - XBT_OUT(); - return diff; -} - -/** \brief Attribute the value bound to var->bound. - * - * \param func_fpi inverse of the partial differential of f (f prime inverse, (f')^{-1}) - * - * 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)) -{ - func_f_def = func_f; - func_fp_def = func_fp; - func_fpi_def = func_fpi; -} - - -/**************** Vegas and Reno functions *************************/ -/* - * NOTE for Reno: all functions consider the network - * coeficient (alpha) equal to 1. - */ - -/* - * For Vegas: $f(x) = \alpha D_f\ln(x)$ - * Therefore: $fp(x) = \frac{\alpha D_f}{x}$ - * Therefore: $fpi(x) = \frac{\alpha D_f}{x}$ - */ -#define VEGAS_SCALING 1000.0 - -double func_vegas_f(lmm_variable_t var, double x) -{ - xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); - return VEGAS_SCALING * var->weight * log(x); -} - -double func_vegas_fp(lmm_variable_t var, double x) -{ - xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); - return VEGAS_SCALING * var->weight / x; -} - -double func_vegas_fpi(lmm_variable_t var, double x) -{ - xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); - return var->weight / (x / VEGAS_SCALING); -} - -/* - * For Reno: $f(x) = \frac{\sqrt{3/2}}{D_f} atan(\sqrt{3/2}D_f x)$ - * Therefore: $fp(x) = \frac{3}{3 D_f^2 x^2+2}$ - * Therefore: $fpi(x) = \sqrt{\frac{1}{{D_f}^2 x} - \frac{2}{3{D_f}^2}}$ - */ -#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!"); - - return RENO_SCALING * sqrt(3.0 / 2.0) / var->weight * - atan(sqrt(3.0 / 2.0) * var->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 + - 2.0); -} - -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(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); - if (res_fpi <= 0.0) - return 0.0; -/* xbt_assert(res_fpi>0.0,"Don't call me with stupid values!"); */ - return sqrt(res_fpi); -} - - -/* Implementing new Reno-2 - * For Reno-2: $f(x) = U_f(x_f) = \frac{{2}{D_f}}*ln(2+x*D_f)$ - * Therefore: $fp(x) = 2/(Weight*x + 2) - * Therefore: $fpi(x) = (2*Weight)/x - 4 - */ -#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 + - 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)); -} - -double func_reno2_fpi(lmm_variable_t var, double x) -{ - double res_fpi; - double tmp; - - xbt_assert(x > 0.0, "Don't call me with stupid values!"); - tmp = x * var->weight * var->weight; - res_fpi = tmp * (9.0 * x + 24.0); - - if (res_fpi <= 0.0) - return 0.0; - - res_fpi = RENO2_SCALING * (-3.0 * tmp + sqrt(res_fpi)) / (4.0 * tmp); - return res_fpi; -} diff --git a/src/surf/lagrange.cpp b/src/surf/lagrange.cpp index 1b4cc9550b..8128625240 100644 --- a/src/surf/lagrange.cpp +++ b/src/surf/lagrange.cpp @@ -1,4 +1,4 @@ -/* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team. +/* Copyright (c) 2007-2013. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -11,9 +11,8 @@ */ #include "xbt/log.h" #include "xbt/sysdep.h" -//#include "maxmin_private.h" -#include "solver.h" -#include "solver.hpp" +#include "maxmin_private.hpp" + #include #ifndef MATH #include @@ -41,58 +40,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(std::vector *cnstList, std::vector *varList, +static int __check_feasible(xbt_swag_t cnst_list, xbt_swag_t var_list, int warn) { - std::vector *elemList = NULL; + void *_cnst, *_elem, *_var; + xbt_swag_t elem_list = 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; - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { - cnst = (*cnstIt); + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; tmp = 0; - elemList = &(cnst->m_elementSet); - for (elemIt=elemList->begin(); elemIt!=elemList->end(); ++elemIt) { - var = (*elemIt)->p_variable; - if (var->m_weight <= 0) + elem_list = &(cnst->element_set); + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; + var = elem->variable; + if (var->weight <= 0) continue; - tmp += var->m_value; + tmp += var->value; } - if (double_positive(tmp - cnst->m_bound)) { + if (double_positive(tmp - cnst->bound)) { if (warn) XBT_WARN ("The link (%p) is over-used. Expected less than %f and got %f", - cnst, cnst->m_bound, tmp); + cnst, cnst->bound, tmp); return 0; } XBT_DEBUG ("Checking feasability for constraint (%p): sat = %f, lambda = %f ", - cnst, tmp - cnst->m_bound, cnst->m_lambda); + cnst, tmp - cnst->bound, cnst->lambda); } - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - if (!var->m_weight) + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) break; - if (var->m_bound < 0) + if (var->bound < 0) continue; XBT_DEBUG("Checking feasability for variable (%p): sat = %f mu = %f", var, - var->m_value - var->m_bound, var->m_mu); + var->value - var->bound, var->mu); - if (double_positive(var->m_value - var->m_bound)) { + if (double_positive(var->value - var->bound)) { if (warn) XBT_WARN ("The variable (%p) is too large. Expected less than %f and got %f", - var, var->m_bound, var->m_value); + var, var->bound, var->value); return 0; } - } + } return 1; } @@ -100,17 +99,16 @@ static double new_value(lmm_variable_t var) { double tmp = 0; int i; - std::vector::iterator elemIt; - for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { - tmp += ((*elemIt)->p_constraint)->m_lambda; + for (i = 0; i < var->cnsts_number; i++) { + tmp += (var->cnsts[i].constraint)->lambda; } - if (var->m_bound > 0) - tmp += var->m_mu; + if (var->bound > 0) + tmp += var->mu; XBT_DEBUG("\t Working on var (%p). cost = %e; Weight = %e", var, tmp, - var->m_weight); + var->weight); //uses the partial differential inverse function - return var->p_funcFPI(var, tmp); + return var->func_fpi(var, tmp); } static double new_mu(lmm_variable_t var) @@ -118,53 +116,51 @@ 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 (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { - sigma_i += ((*elemIt)->p_constraint)->m_lambda; + for (j = 0; j < var->cnsts_number; j++) { + sigma_i += (var->cnsts[j].constraint)->lambda; } - mu_i = var->p_funcFP(var, var->m_bound) - sigma_i; + mu_i = var->func_fp(var, var->bound) - sigma_i; if (mu_i < 0.0) return 0.0; return mu_i; } -static double dual_objective(std::vector *varList, std::vector *cnstList) +static double dual_objective(xbt_swag_t var_list, xbt_swag_t cnst_list) { + void *_cnst, *_var; 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; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = (*varIt); + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; double sigma_i = 0.0; int j; - if (!var->m_weight) + if (!var->weight) break; - 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; + for (j = 0; j < var->cnsts_number; j++) + sigma_i += (var->cnsts[j].constraint)->lambda; + + if (var->bound > 0) + sigma_i += var->mu; XBT_DEBUG("var %p : sigma_i = %1.20f", var, sigma_i); - obj += var->p_funcF(var, var->p_funcFPI(var, sigma_i)) - - sigma_i * var->p_funcFPI(var, sigma_i); + obj += var->func_f(var, var->func_fpi(var, sigma_i)) - + sigma_i * var->func_fpi(var, sigma_i); - if (var->m_bound > 0) - obj += var->m_mu * var->m_bound; + if (var->bound > 0) + obj += var->mu * var->bound; } - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) - obj += (*cnstIt)->m_lambda * (*cnstIt)->m_bound; - + xbt_swag_foreach(_cnst, cnst_list) + cnst = (lmm_constraint_t)_cnst; + obj += cnst->lambda * cnst->bound; + return obj; } @@ -182,18 +178,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. */ - std::vector *cnstList = NULL; - std::vector::iterator cnstIt; + xbt_swag_t cnst_list = NULL; + void *_cnst; lmm_constraint_t cnst = NULL; - std::vector *varList = NULL; - std::vector::iterator varIt; + xbt_swag_t var_list = NULL; + void *_var; lmm_variable_t var = NULL; - std::vector::iterator elemIt; - /* - * Auxiliar variables. + * Auxiliary variables. */ int iteration = 0; double tmp = 0; @@ -211,58 +205,59 @@ void lagrange_solve(lmm_system_t sys) lmm_print(sys); } - if (!(sys->m_modified)) + if (!(sys->modified)) return; + /* * Initialize 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); + cnst_list = &(sys->active_constraint_set); + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; + cnst->lambda = 1.0; + cnst->new_lambda = 2.0; + XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->lambda); } /* * Initialize the var list variable with only the active variables. * Associate an index in the swag variables. Initialize mu. */ - varList = &(sys->m_variableSet); + var_list = &(sys->variable_set); i = 0; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (!var->m_weight) - var->m_value = 0.0; + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) + var->value = 0.0; else { int nb = 0; - if (var->m_bound < 0.0) { + if (var->bound < 0.0) { XBT_DEBUG("#### NOTE var(%d) is a boundless variable", i); - var->m_mu = -1.0; - var->m_value = new_value(var); + var->mu = -1.0; + var->value = new_value(var); } else { - var->m_mu = 1.0; - var->m_newMu = 2.0; - var->m_value = new_value(var); + var->mu = 1.0; + var->new_mu = 2.0; + var->value = new_value(var); } - 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) + 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) nb++; } - if (nb == var->m_cnsts.size()) - var->m_value = 1.0; + if (nb == var->cnsts_number) + var->value = 1.0; } } /* * Compute dual objective. */ - obj = dual_objective(varList, cnstList); + obj = dual_objective(var_list, cnst_list); /* * While doesn't reach a minimun error or a number maximum of iterations. @@ -278,20 +273,20 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of mu_i */ - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (!var->m_weight) + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) break; - if (var->m_bound >= 0) { + if (var->bound >= 0) { XBT_DEBUG("Working on var (%p)", var); - var->m_newMu = new_mu(var); + var->new_mu = 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->m_mu, var->m_newMu); - var->m_mu = var->m_newMu; + var->mu, var->new_mu); + var->mu = var->new_mu; - new_obj = dual_objective(varList, cnstList); + new_obj = dual_objective(var_list, cnst_list); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -303,19 +298,19 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of lambda_i */ - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { - cnst = *cnstIt; + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; XBT_DEBUG("Working on cnst (%p)", cnst); - cnst->m_newLambda = - dichotomy(cnst->m_lambda, partial_diff_lambda, cnst, + cnst->new_lambda = + dichotomy(cnst->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->m_lambda, cnst->m_newLambda); - cnst->m_lambda = cnst->m_newLambda; + cnst, cnst->lambda, cnst->new_lambda); + cnst->lambda = cnst->new_lambda; - new_obj = dual_objective(varList, cnstList); + new_obj = dual_objective(var_list, cnst_list); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -329,24 +324,24 @@ void lagrange_solve(lmm_system_t sys) */ XBT_DEBUG("-------------- Check convergence ----------"); overall_modification = 0; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (var->m_weight <= 0) - var->m_value = 0.0; + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (var->weight <= 0) + var->value = 0.0; else { tmp = new_value(var); overall_modification = - MAX(overall_modification, fabs(var->m_value - tmp)); + MAX(overall_modification, fabs(var->value - tmp)); - var->m_value = tmp; + var->value = tmp; XBT_DEBUG("New value of var (%p) = %e, overall_modification = %e", - var, var->m_value, overall_modification); + var, var->value, overall_modification); } } XBT_DEBUG("-------------- Check feasability ----------"); - if (!__check_feasible(cnstList, varList, 0)) + if (!__check_feasible(cnst_list, var_list, 0)) overall_modification = 1.0; XBT_DEBUG("Iteration %d: overall_modification : %f", iteration, overall_modification); @@ -355,7 +350,8 @@ void lagrange_solve(lmm_system_t sys) /* break; */ /* } */ } - __check_feasible(cnstList, varList, 1); + + __check_feasible(cnst_list, var_list, 1); if (overall_modification <= epsilon_min_error) { XBT_DEBUG("The method converges in %d iterations.", iteration); @@ -387,7 +383,6 @@ 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; @@ -491,13 +486,13 @@ 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; + void *_elem; xbt_swag_t elem_list = NULL; lmm_element_t elem = NULL; lmm_variable_t var = NULL; @@ -510,7 +505,8 @@ static double partial_diff_lambda(double lambda, void *param_cnst) XBT_CDEBUG(surf_lagrange_dichotomy, "Computing diff of cnst (%p)", cnst); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; var = elem->variable; if (var->weight <= 0) continue; @@ -543,7 +539,6 @@ static double partial_diff_lambda(double lambda, void *param_cnst) diff); XBT_OUT(); return diff; - #endif } /** \brief Attribute the value bound to var->bound. @@ -553,9 +548,18 @@ 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; @@ -578,26 +582,20 @@ void lmm_set_default_protocol_function(double (*func_f) (lmm_variable_t var, dou 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 } /* @@ -608,15 +606,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->m_weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); - return RENO_SCALING * sqrt(3.0 / 2.0) / var->m_weight * - atan(sqrt(3.0 / 2.0) * var->m_weight * x); + return RENO_SCALING * sqrt(3.0 / 2.0) / var->weight * + atan(sqrt(3.0 / 2.0) * var->weight * x); } double func_reno_fp(lmm_variable_t var, double x) { - return RENO_SCALING * 3.0 / (3.0 * var->m_weight * var->m_weight * x * x + + return RENO_SCALING * 3.0 / (3.0 * var->weight * var->weight * x * x + 2.0); } @@ -624,15 +622,15 @@ double func_reno_fpi(lmm_variable_t var, double x) { double res_fpi; - xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->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->m_weight * var->m_weight * (x / RENO_SCALING)) - - 2.0 / (3.0 * var->m_weight * var->m_weight); + 1.0 / (var->weight * var->weight * (x / RENO_SCALING)) - + 2.0 / (3.0 * var->weight * var->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); } @@ -645,16 +643,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->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 + + 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 + 3.0)); } double func_reno2_fp(lmm_variable_t var, double x) { - return RENO2_SCALING * 3.0 / (var->m_weight * x * - (2.0 * var->m_weight * x + 3.0)); + return RENO2_SCALING * 3.0 / (var->weight * x * + (2.0 * var->weight * x + 3.0)); } double func_reno2_fpi(lmm_variable_t var, double x) @@ -663,7 +661,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->m_weight * var->m_weight; + tmp = x * var->weight * var->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.cpp similarity index 90% rename from src/surf/maxmin.c rename to src/surf/maxmin.cpp index 5eee02af67..876fa33d9c 100644 --- a/src/surf/maxmin.c +++ b/src/surf/maxmin.cpp @@ -8,7 +8,7 @@ #include "xbt/sysdep.h" #include "xbt/log.h" #include "xbt/mallocator.h" -#include "maxmin_private.h" +#include "maxmin_private.hpp" #include #include /* sprintf */ #include @@ -79,14 +79,14 @@ void lmm_system_free(lmm_system_t sys) lmm_variable_t var = NULL; lmm_constraint_t cnst = NULL; - while ((var = extract_variable(sys))) { + while ((var = (lmm_variable_t) 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))) + while ((cnst = (lmm_constraint_t) extract_constraint(sys))) lmm_cnst_free(sys, cnst); xbt_mallocator_free(sys->variable_mallocator); @@ -163,12 +163,12 @@ lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, return cnst; } -XBT_INLINE void lmm_constraint_shared(lmm_constraint_t cnst) +void lmm_constraint_shared(lmm_constraint_t cnst) { cnst->shared = 0; } -XBT_INLINE int lmm_constraint_is_shared(lmm_constraint_t cnst) +int lmm_constraint_is_shared(lmm_constraint_t cnst) { return (cnst->shared); } @@ -203,10 +203,10 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, 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 = (lmm_variable_t) 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)); + var->cnsts = (s_lmm_element_t *) 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; @@ -248,7 +248,7 @@ void lmm_variable_free(lmm_system_t sys, lmm_variable_t var) lmm_var_free(sys, var); } -XBT_INLINE double lmm_variable_getvalue(lmm_variable_t var) +double lmm_variable_getvalue(lmm_variable_t var) { return (var->value); } @@ -408,7 +408,7 @@ void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst, DIE_IMPOSSIBLE; } -XBT_INLINE lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, +lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/, lmm_variable_t var, int num) { @@ -418,7 +418,7 @@ XBT_INLINE lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, return NULL; } -XBT_INLINE double lmm_get_cnst_weight_from_var(lmm_system_t sys, +double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/, lmm_variable_t var, int num) { @@ -428,32 +428,32 @@ XBT_INLINE double lmm_get_cnst_weight_from_var(lmm_system_t sys, return 0.0; } -XBT_INLINE int lmm_get_number_of_cnst_from_var(lmm_system_t sys, +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_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)); + *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set)); else - *elem = xbt_swag_getNext(*elem, cnst->element_set.offset); + *elem = (lmm_element_t) 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) +void *lmm_constraint_id(lmm_constraint_t cnst) { return cnst->id; } -XBT_INLINE void *lmm_variable_id(lmm_variable_t var) +void *lmm_variable_id(lmm_variable_t var) { return var->id; } @@ -473,7 +473,7 @@ static XBT_INLINE void saturated_constraint_set_update(double usage, } 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 = (int*) 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++; @@ -486,13 +486,15 @@ static XBT_INLINE void saturated_variable_set_update( lmm_system_t sys) { lmm_constraint_light_t cnst = NULL; + void *_elem; 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) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; if (elem->variable->weight <= 0) break; if ((elem->value > 0)) @@ -503,6 +505,7 @@ static XBT_INLINE void saturated_variable_set_update( void lmm_print(lmm_system_t sys) { + void *_cnst, *_elem, *_var; lmm_constraint_t cnst = NULL; lmm_element_t elem = NULL; lmm_variable_t var = NULL; @@ -510,23 +513,24 @@ void lmm_print(lmm_system_t sys) xbt_swag_t var_list = NULL; xbt_swag_t elem_list = NULL; char print_buf[1024]; - char *trace_buf = xbt_malloc0(sizeof(char)); + char *trace_buf = (char*) xbt_malloc0(sizeof(char)); double sum = 0.0; /* Printing Objective */ var_list = &(sys->variable_set); sprintf(print_buf, "MAX-MIN ( "); - trace_buf = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); - xbt_swag_foreach(var, var_list) { + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight); - trace_buf = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); } sprintf(print_buf, ")"); - trace_buf = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); XBT_DEBUG("%20s", trace_buf); @@ -535,22 +539,24 @@ void lmm_print(lmm_system_t sys) XBT_DEBUG("Constraints"); /* Printing Constraints */ cnst_list = &(sys->active_constraint_set); - xbt_swag_foreach(cnst, cnst_list) { + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; sum = 0.0; elem_list = &(cnst->element_set); sprintf(print_buf, "\t"); - trace_buf = + trace_buf = (char*) 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 = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value, elem->variable->id_int, elem->variable->value,(cnst->shared)?"+":","); - trace_buf = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); @@ -560,13 +566,13 @@ void lmm_print(lmm_system_t sys) sum = MAX(sum,elem->value * elem->variable->value); } sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int); - trace_buf = + trace_buf = (char*) 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 = + trace_buf = (char*) xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); @@ -580,7 +586,8 @@ void lmm_print(lmm_system_t sys) XBT_DEBUG("Variables"); /* Printing Result */ - xbt_swag_foreach(var, var_list) { + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; if (var->bound > 0) { XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value, var->bound); @@ -597,9 +604,9 @@ void lmm_print(lmm_system_t sys) void lmm_solve(lmm_system_t sys) { + void *_var, *_cnst, *_cnst_next, *_elem; 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; @@ -622,11 +629,12 @@ void lmm_solve(lmm_system_t sys) XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); /* Init: Only modified code portions */ - xbt_swag_foreach(cnst, cnst_list) { + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; elem_list = &(cnst->element_set); //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list)); - xbt_swag_foreach(elem, elem_list) { - var = elem->variable; + xbt_swag_foreach(_elem, elem_list) { + var = ((lmm_element_t)_elem)->variable; if (var->weight <= 0.0) break; var->value = 0.0; @@ -639,14 +647,16 @@ void lmm_solve(lmm_system_t sys) 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) { + xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) { + cnst = (lmm_constraint_t)_cnst; /* INIT */ cnst->remaining = cnst->bound; if (cnst->remaining == 0) continue; cnst->usage = 0; elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; /* 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; @@ -657,8 +667,9 @@ void lmm_solve(lmm_system_t sys) cnst->usage = elem->value / elem->variable->weight; make_elem_active(elem); - if (sys->keep_track) - xbt_swag_insert(elem->variable->id, sys->keep_track); + ActionLmmPtr action = static_cast(elem->variable->id); + if (sys->keep_track && !action->is_linked()) + sys->keep_track->push_back(*action); } } XBT_DEBUG("Constraint Usage '%d' : %f", cnst->id_int, cnst->usage); @@ -684,7 +695,8 @@ void lmm_solve(lmm_system_t sys) /* Fix the variables that have to be */ var_list = &(sys->saturated_variable_set); - xbt_swag_foreach(var, var_list) { + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; if (var->weight <= 0.0) DIE_IMPOSSIBLE; /* First check if some of these variables have reach their upper @@ -703,7 +715,7 @@ void lmm_solve(lmm_system_t sys) } - while ((var = xbt_swag_getFirst(var_list))) { + while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) { int i; if (min_bound < 0) { @@ -746,7 +758,8 @@ void lmm_solve(lmm_system_t sys) cnst->usage = 0.0; make_elem_inactive(elem); elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; if (elem->variable->weight <= 0 || elem->variable->value > 0) break; if (elem->value > 0) @@ -875,12 +888,12 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, XBT_OUT(); } -XBT_INLINE double lmm_get_variable_weight(lmm_variable_t var) +double lmm_get_variable_weight(lmm_variable_t var) { return var->weight; } -XBT_INLINE void lmm_update_constraint_bound(lmm_system_t sys, +void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst, double bound) { @@ -889,7 +902,7 @@ XBT_INLINE void lmm_update_constraint_bound(lmm_system_t sys, cnst->bound = bound; } -XBT_INLINE int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) +int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) { return xbt_swag_belongs(cnst, &(sys->active_constraint_set)); } @@ -897,7 +910,7 @@ XBT_INLINE int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys) { - return xbt_swag_getFirst(&(sys->active_constraint_set)); + return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set)); } XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t @@ -905,7 +918,7 @@ XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t lmm_constraint_t cnst) { - return xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); + return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); } #ifdef HAVE_LATENCY_BOUND_TRACKING @@ -929,10 +942,10 @@ XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var) static void lmm_update_modified_set_rec(lmm_system_t sys, lmm_constraint_t cnst) { - lmm_element_t elem; + void* _elem; - xbt_swag_foreach(elem, &cnst->element_set) { - lmm_variable_t var = elem->variable; + xbt_swag_foreach(_elem, &cnst->element_set) { + lmm_variable_t var = ((lmm_element_t)_elem)->variable; s_lmm_element_t *cnsts = var->cnsts; int i; for (i = 0; var->visited != sys->visited_counter @@ -967,9 +980,9 @@ 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; + void *_var; + xbt_swag_foreach(_var, &sys->variable_set) + ((lmm_variable_t)_var)->visited = 0; } xbt_swag_reset(&sys->modified_constraint_set); } @@ -983,9 +996,11 @@ static void lmm_remove_all_modified_set(lmm_system_t sys) double lmm_constraint_get_usage(lmm_constraint_t cnst) { double usage = 0.0; xbt_swag_t elem_list = &(cnst->element_set); + void *_elem; lmm_element_t elem = NULL; - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; /* 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; diff --git a/src/surf/maxmin_private.h b/src/surf/maxmin_private.hpp similarity index 98% rename from src/surf/maxmin_private.h rename to src/surf/maxmin_private.hpp index a753f9653b..f7f75c0984 100644 --- a/src/surf/maxmin_private.h +++ b/src/surf/maxmin_private.hpp @@ -10,6 +10,7 @@ #include "surf/maxmin.h" #include "xbt/swag.h" #include "xbt/mallocator.h" +#include "surf_interface.hpp" typedef struct lmm_element { /* hookup to constraint */ @@ -84,7 +85,7 @@ typedef struct lmm_system { s_xbt_swag_t saturated_variable_set; /* a list of lmm_variable_t */ s_xbt_swag_t saturated_constraint_set; /* a list of lmm_constraint_t_t */ - xbt_swag_t keep_track; + ActionLmmListPtr keep_track; xbt_mallocator_t variable_mallocator; } s_lmm_system_t; diff --git a/src/surf/network_cm02.cpp b/src/surf/network_cm02.cpp index 00df321a38..64d7128ffa 100644 --- a/src/surf/network_cm02.cpp +++ b/src/surf/network_cm02.cpp @@ -1,5 +1,5 @@ #include "network_cm02.hpp" -#include "maxmin_private.h" +#include "maxmin_private.hpp" #include "simgrid/sg_config.h" XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_network); @@ -245,8 +245,6 @@ void surf_network_model_init_Vegas(void) void NetworkCm02Model::initialize() { - ActionLmmPtr comm = NULL; - char *optim = xbt_cfg_get_string(_sg_cfg_set, "network/optim"); int select = xbt_cfg_get_boolean(_sg_cfg_set, "network/maxmin_selective_update"); @@ -278,7 +276,7 @@ void NetworkCm02Model::initialize() if (p_updateMechanism == UM_LAZY) { p_actionHeap = xbt_heap_new(8, NULL); xbt_heap_set_update_callback(p_actionHeap, surf_action_lmm_update_index_heap); - p_modifiedSet = xbt_swag_new(xbt_swag_offset(*comm, p_actionListHookup)); + p_modifiedSet = new ActionLmmList(); p_maxminSystem->keep_track = p_modifiedSet; } @@ -409,7 +407,6 @@ ActionPtr NetworkCm02Model::communicate(RoutingEdgePtr src, RoutingEdgePtr dst, #endif action->m_weight = action->m_latency = latency; - //FIXME:REMOVxbt_swag_insert(action, action->p_stateSet); action->m_rate = rate; if (p_updateMechanism == UM_LAZY) { action->m_indexHeap = -1; @@ -450,7 +447,7 @@ ActionPtr NetworkCm02Model::communicate(RoutingEdgePtr src, RoutingEdgePtr dst, constraints_per_variable += xbt_dynar_length(back_route); if (action->m_latency > 0) { - action->p_variable = lmm_variable_new(p_maxminSystem, action, 0.0, -1.0, + action->p_variable = lmm_variable_new(p_maxminSystem, static_cast(action), 0.0, -1.0, constraints_per_variable); if (p_updateMechanism == UM_LAZY) { // add to the heap the event when the latency is payed @@ -459,7 +456,7 @@ ActionPtr NetworkCm02Model::communicate(RoutingEdgePtr src, RoutingEdgePtr dst, action->heapInsert(p_actionHeap, action->m_latency + action->m_lastUpdate, xbt_dynar_is_empty(route) ? NORMAL : LATENCY); } } else - action->p_variable = lmm_variable_new(p_maxminSystem, action, 1.0, -1.0, constraints_per_variable); + action->p_variable = lmm_variable_new(p_maxminSystem, static_cast(action), 1.0, -1.0, constraints_per_variable); if (action->m_rate < 0) { lmm_update_variable_bound(p_maxminSystem, action->getVariable(), (action->m_latCurrent > 0) ? sg_tcp_gamma / (2.0 * action->m_latCurrent) : -1.0); diff --git a/src/surf/network_constant.cpp b/src/surf/network_constant.cpp index ce29ef01e4..6934835d78 100644 --- a/src/surf/network_constant.cpp +++ b/src/surf/network_constant.cpp @@ -24,13 +24,13 @@ void surf_network_model_init_Constant() double NetworkConstantModel::shareResources(double /*now*/) { - void *_action = NULL; NetworkConstantActionLmmPtr action = NULL; double min = -1.0; - xbt_swag_t actionSet = getRunningActionSet(); - xbt_swag_foreach(_action, actionSet) { - action = dynamic_cast(static_cast(_action)); + ActionListPtr actionSet = getRunningActionSet(); + for(ActionList::iterator it(actionSet->begin()), itend(actionSet->end()) + ; it != itend ; ++it) { + action = dynamic_cast(&*it); if (action->m_latency > 0) { if (min < 0) min = action->m_latency; @@ -44,11 +44,12 @@ double NetworkConstantModel::shareResources(double /*now*/) void NetworkConstantModel::updateActionsState(double /*now*/, double delta) { - void *_action, *_next_action; NetworkConstantActionLmmPtr action = NULL; - xbt_swag_t actionSet = getRunningActionSet(); - xbt_swag_foreach_safe(_action, _next_action, actionSet) { - action = dynamic_cast(static_cast(_action)); + ActionListPtr actionSet = getRunningActionSet(); + for(ActionList::iterator it(actionSet->begin()), itNext=it, itend(actionSet->end()) + ; it != itend ; it=itNext) { + ++itNext; + action = dynamic_cast(&*it); if (action->m_latency > 0) { if (action->m_latency > delta) { double_update(&(action->m_latency), delta); @@ -124,7 +125,8 @@ int NetworkConstantActionLmm::unref() { m_refcount--; if (!m_refcount) { - xbt_swag_remove(static_cast(this), p_stateSet); + if (actionHook::is_linked()) + p_stateSet->erase(p_stateSet->iterator_to(*this)); delete this; return 1; } diff --git a/src/surf/network_constant.hpp b/src/surf/network_constant.hpp index 984779569d..8575f00867 100644 --- a/src/surf/network_constant.hpp +++ b/src/surf/network_constant.hpp @@ -20,7 +20,11 @@ typedef NetworkConstantActionLmm *NetworkConstantActionLmmPtr; *********/ class NetworkConstantModel : public NetworkCm02Model { public: - NetworkConstantModel() : NetworkCm02Model("constant time network") {}; + NetworkConstantModel() + : NetworkCm02Model("constant time network") + { + p_updateMechanism = UM_UNDEFINED; + }; double shareResources(double now); void updateActionsState(double now, double delta); ActionPtr communicate(RoutingEdgePtr src, RoutingEdgePtr dst, @@ -52,8 +56,9 @@ public: m_latency = latency; if (m_latency <= 0.0) { p_stateSet = getModel()->getDoneActionSet(); - xbt_swag_insert(static_cast(this), p_stateSet); + p_stateSet->push_back(*this); } + p_variable = NULL; }; int unref(); void recycle(); diff --git a/src/surf/network_interface.hpp b/src/surf/network_interface.hpp index bd5543f5f2..ed28c8663c 100644 --- a/src/surf/network_interface.hpp +++ b/src/surf/network_interface.hpp @@ -51,7 +51,7 @@ public: if (p_actionHeap) xbt_heap_free(p_actionHeap); if (p_modifiedSet) - xbt_swag_free(p_modifiedSet); + delete p_modifiedSet; } virtual NetworkLinkPtr createResource(const char *name, diff --git a/src/surf/storage_n11.cpp b/src/surf/storage_n11.cpp index b0d06837ac..419f064fda 100644 --- a/src/surf/storage_n11.cpp +++ b/src/surf/storage_n11.cpp @@ -290,12 +290,13 @@ double StorageN11Model::shareResources(double now) void StorageN11Model::updateActionsState(double /*now*/, double delta) { - void *_action, *_next_action; StorageActionLmmPtr action = NULL; - xbt_swag_t actionSet = getRunningActionSet(); - xbt_swag_foreach_safe(_action, _next_action, actionSet) { - action = dynamic_cast(static_cast(_action)); + ActionListPtr actionSet = getRunningActionSet(); + for(ActionList::iterator it(actionSet->begin()), itNext=it, itend(actionSet->end()) + ; it != itend ; it=itNext) { + ++itNext; + action = dynamic_cast(&*it); if(action->m_type == WRITE) { // Update the disk usage @@ -546,7 +547,8 @@ int StorageN11ActionLmm::unref() { m_refcount--; if (!m_refcount) { - xbt_swag_remove(static_cast(this), p_stateSet); + if (actionHook::is_linked()) + p_stateSet->erase(p_stateSet->iterator_to(*this)); if (getVariable()) lmm_variable_free(getModel()->getMaxminSystem(), getVariable()); #ifdef HAVE_TRACING diff --git a/src/surf/surf_c_bindings.cpp b/src/surf/surf_c_bindings.cpp index ae7612bf70..00959bb04a 100644 --- a/src/surf/surf_c_bindings.cpp +++ b/src/surf/surf_c_bindings.cpp @@ -222,20 +222,37 @@ const char *surf_model_name(surf_model_t model){ return model->getName(); } -xbt_swag_t surf_model_done_action_set(surf_model_t model){ - return model->getDoneActionSet(); -} - -xbt_swag_t surf_model_failed_action_set(surf_model_t model){ - return model->getFailedActionSet(); -} - -xbt_swag_t surf_model_ready_action_set(surf_model_t model){ - return model->getReadyActionSet(); -} - -xbt_swag_t surf_model_running_action_set(surf_model_t model){ - return model->getRunningActionSet(); +surf_action_t surf_model_extract_done_action_set(surf_model_t model){ + if (model->getDoneActionSet()->empty()) + return NULL; + surf_action_t res = &model->getDoneActionSet()->front(); + model->getDoneActionSet()->pop_front(); + return res; +} +surf_action_t surf_model_extract_failed_action_set(surf_model_t model){ + if (model->getFailedActionSet()->empty()) + return NULL; + surf_action_t res = &model->getFailedActionSet()->front(); + model->getFailedActionSet()->pop_front(); + return res; +} +surf_action_t surf_model_extract_ready_action_set(surf_model_t model){ + if (model->getReadyActionSet()->empty()) + return NULL; + surf_action_t res = &model->getReadyActionSet()->front(); + model->getReadyActionSet()->pop_front(); + return res; +} +surf_action_t surf_model_extract_running_action_set(surf_model_t model){ + if (model->getRunningActionSet()->empty()) + return NULL; + surf_action_t res = &model->getRunningActionSet()->front(); + model->getRunningActionSet()->pop_front(); + return res; +} + +int surf_model_running_action_set_size(surf_model_t model){ + return model->getRunningActionSet()->size(); } surf_action_t surf_workstation_model_execute_parallel_task(surf_workstation_model_t model, diff --git a/src/surf/surf_interface.cpp b/src/surf/surf_interface.cpp index 624b6cbdcf..b2607b8d94 100644 --- a/src/surf/surf_interface.cpp +++ b/src/surf/surf_interface.cpp @@ -457,15 +457,14 @@ void surf_exit(void) *********/ Model::Model(const char *name) - : p_maxminSystem(0), p_name(name), + : p_name(name), p_maxminSystem(0), m_resOnCB(0), m_resOffCB(0), m_actCancelCB(0), m_actSuspendCB(0), m_actResumeCB(0) { - ActionPtr action = NULL; - p_readyActionSet = xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); - p_runningActionSet = xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); - p_failedActionSet = xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); - p_doneActionSet = xbt_swag_new(xbt_swag_offset(*action, p_stateHookup)); + p_readyActionSet = new ActionList(); + p_runningActionSet = new ActionList(); + p_failedActionSet = new ActionList(); + p_doneActionSet = new ActionList(); p_modifiedSet = NULL; p_actionHeap = NULL; @@ -474,10 +473,10 @@ Model::Model(const char *name) } Model::~Model(){ -xbt_swag_free(p_readyActionSet); -xbt_swag_free(p_runningActionSet); -xbt_swag_free(p_failedActionSet); -xbt_swag_free(p_doneActionSet); + delete p_readyActionSet; + delete p_runningActionSet; + delete p_failedActionSet; + delete p_doneActionSet; } double Model::shareResources(double now) @@ -499,15 +498,17 @@ double Model::shareResourcesLazy(double now) XBT_DEBUG ("Before share resources, the size of modified actions set is %d", - xbt_swag_size(p_modifiedSet)); + p_modifiedSet->size()); lmm_solve(p_maxminSystem); XBT_DEBUG ("After share resources, The size of modified actions set is %d", - xbt_swag_size(p_modifiedSet)); + p_modifiedSet->size()); - while((action = static_cast(xbt_swag_extract(p_modifiedSet)))) { + while(!p_modifiedSet->empty()) { + action = dynamic_cast(&(p_modifiedSet->front())); + p_modifiedSet->pop_front(); int max_dur_flag = 0; if (action->getStateSet() != p_runningActionSet) @@ -568,7 +569,7 @@ double Model::shareResourcesFull(double /*now*/) { } -double Model::shareResourcesMaxMin(xbt_swag_t running_actions, +double Model::shareResourcesMaxMin(ActionListPtr running_actions, lmm_system_t sys, void (*solve) (lmm_system_t)) { @@ -579,14 +580,15 @@ double Model::shareResourcesMaxMin(xbt_swag_t running_actions, solve(sys); - xbt_swag_foreach(_action, running_actions) { - action = dynamic_cast(static_cast(_action)); + ActionList::iterator it(running_actions->begin()), itend(running_actions->end()); + for(; it != itend ; ++it) { + action = dynamic_cast(&*it); value = lmm_variable_getvalue(action->getVariable()); if ((value > 0) || (action->getMaxDuration() >= 0)) break; } - if (!_action) + if (!action) return -1.0; if (value > 0) { @@ -600,10 +602,8 @@ double Model::shareResourcesMaxMin(xbt_swag_t running_actions, min = action->getMaxDuration(); - for (_action = xbt_swag_getNext(static_cast(action), running_actions->offset); - _action; - _action = xbt_swag_getNext(static_cast(action), running_actions->offset)) { - action = dynamic_cast(static_cast(_action)); + for (++it; it != itend; ++it) { + action = dynamic_cast(&*it); value = lmm_variable_getvalue(action->getVariable()); if (value > 0) { if (action->getRemains() > 0) @@ -792,7 +792,7 @@ Action::Action(ModelPtr model, double cost, bool failed) else p_stateSet = getModel()->getRunningActionSet(); - xbt_swag_insert(this, p_stateSet); + p_stateSet->push_back(*this); } Action::~Action() { @@ -834,8 +834,7 @@ void Action::setState(e_surf_action_state_t state) { //surf_action_state_t action_state = &(action->model_type->states); XBT_IN("(%p,%s)", this, surf_action_state_names[state]); - xbt_swag_remove(this, p_stateSet); - + p_stateSet->erase(p_stateSet->iterator_to(*this)); if (state == SURF_ACTION_READY) p_stateSet = getModel()->getReadyActionSet(); else if (state == SURF_ACTION_RUNNING) @@ -848,7 +847,7 @@ void Action::setState(e_surf_action_state_t state) p_stateSet = NULL; if (p_stateSet) - xbt_swag_insert(this, p_stateSet); + p_stateSet->push_back(*this); XBT_OUT(); } @@ -913,7 +912,7 @@ void ActionLmm::setPriority(double priority) void ActionLmm::cancel(){ setState(SURF_ACTION_FAILED); if (getModel()->getUpdateMechanism() == UM_LAZY) { - xbt_swag_remove(this, getModel()->getModifiedSet()); + getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this)); heapRemove(getModel()->getActionHeap()); } } @@ -921,13 +920,15 @@ void ActionLmm::cancel(){ int ActionLmm::unref(){ m_refcount--; if (!m_refcount) { - xbt_swag_remove(static_cast(this), p_stateSet); + if (actionHook::is_linked()) + p_stateSet->erase(p_stateSet->iterator_to(*this)); if (getVariable()) lmm_variable_free(getModel()->getMaxminSystem(), getVariable()); if (getModel()->getUpdateMechanism() == UM_LAZY) { /* remove from heap */ heapRemove(getModel()->getActionHeap()); - xbt_swag_remove(this, getModel()->getModifiedSet()); + if (actionLmmHook::is_linked()) + getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this)); } delete this; return 1; diff --git a/src/surf/surf_interface.hpp b/src/surf/surf_interface.hpp index fd87a11604..1221cc446d 100644 --- a/src/surf/surf_interface.hpp +++ b/src/surf/surf_interface.hpp @@ -9,6 +9,7 @@ #include #include #include +#include #include "surf/trace_mgr.h" #include "xbt/lib.h" #include "surf/surf_routing.h" @@ -67,9 +68,18 @@ typedef boost::function ResourceCallback; typedef Action* ActionPtr; typedef boost::function ActionCallback; +typedef boost::intrusive::list ActionList; +typedef ActionList* ActionListPtr; +typedef boost::intrusive::list_base_hook<> actionHook; + //class ActionLmm; typedef ActionLmm* ActionLmmPtr; +struct lmmTag; +typedef boost::intrusive::list > > > ActionLmmList; +typedef ActionLmmList* ActionLmmListPtr; +typedef boost::intrusive::list_base_hook > actionLmmHook; + enum heap_action_type{ LATENCY = 100, MAX_DURATION, @@ -97,16 +107,16 @@ XBT_PUBLIC_DATA(xbt_dynar_t) model_list; class Model { const char *p_name; - xbt_swag_t p_readyActionSet; /**< Actions in state SURF_ACTION_READY */ - xbt_swag_t p_runningActionSet; /**< Actions in state SURF_ACTION_RUNNING */ - xbt_swag_t p_failedActionSet; /**< Actions in state SURF_ACTION_FAILED */ - xbt_swag_t p_doneActionSet; /**< Actions in state SURF_ACTION_DONE */ + ActionListPtr p_readyActionSet; /**< Actions in state SURF_ACTION_READY */ + ActionListPtr p_runningActionSet; /**< Actions in state SURF_ACTION_RUNNING */ + ActionListPtr p_failedActionSet; /**< Actions in state SURF_ACTION_FAILED */ + ActionListPtr p_doneActionSet; /**< Actions in state SURF_ACTION_DONE */ ResourceCallback m_resOnCB, m_resOffCB; ActionCallback m_actCancelCB, m_actSuspendCB, m_actResumeCB; protected: - xbt_swag_t p_modifiedSet; + ActionLmmListPtr p_modifiedSet; lmm_system_t p_maxminSystem; e_UM_t p_updateMechanism; @@ -118,11 +128,11 @@ public: virtual ~Model(); const char *getName() {return p_name;} - xbt_swag_t getReadyActionSet() {return p_readyActionSet;} - xbt_swag_t getRunningActionSet() {return p_runningActionSet;} - xbt_swag_t getFailedActionSet() {return p_failedActionSet;} - xbt_swag_t getDoneActionSet() {return p_doneActionSet;} - xbt_swag_t getModifiedSet() {return p_modifiedSet;} + ActionListPtr getReadyActionSet() {return p_readyActionSet;} + ActionListPtr getRunningActionSet() {return p_runningActionSet;} + ActionListPtr getFailedActionSet() {return p_failedActionSet;} + ActionListPtr getDoneActionSet() {return p_doneActionSet;} + ActionLmmListPtr getModifiedSet() {return p_modifiedSet;} lmm_system_t getMaxminSystem() {return p_maxminSystem;} e_UM_t getUpdateMechanism() {return p_updateMechanism;} xbt_heap_t getActionHeap() {return p_actionHeap;} @@ -131,7 +141,7 @@ public: virtual double shareResources(double now); virtual double shareResourcesLazy(double now); virtual double shareResourcesFull(double now); - double shareResourcesMaxMin(xbt_swag_t running_actions, + double shareResourcesMaxMin(ActionListPtr running_actions, lmm_system_t sys, void (*solve) (lmm_system_t)); virtual void updateActionsState(double now, double delta); @@ -215,8 +225,8 @@ public: * Action * **********/ -class Action { - xbt_swag_t p_modifiedSet; +class Action : public actionHook{ + ActionLmmListPtr p_modifiedSet; xbt_heap_t p_actionHeap; int m_selectiveUpdate; ModelPtr p_model; @@ -232,7 +242,7 @@ class Action { void *p_data; /**< for your convenience */ protected: - xbt_swag_t p_stateSet; + ActionListPtr p_stateSet; double m_priority; /**< priority (1.0 by default) */ int m_refcount; double m_remains; /**< How much of that cost remains to be done in the currently running task */ @@ -288,7 +298,7 @@ public: double getPriority() {return m_priority;}; - xbt_swag_t getStateSet() {return p_stateSet;}; + ActionListPtr getStateSet() {return p_stateSet;}; private: int resourceUsed(void *resource_id); @@ -305,8 +315,7 @@ private: //FIXME:REMOVE void surf_action_lmm_update_index_heap(void *action, int i); - -class ActionLmm: virtual public Action { +class ActionLmm: virtual public Action, public actionLmmHook { protected: lmm_variable_t p_variable; @@ -340,7 +349,7 @@ public: double getLastUpdate() {return m_lastUpdate;} void refreshLastUpdate() {m_lastUpdate = surf_get_clock();} enum heap_action_type getHat() {return m_hat;} - + bool is_linked() {return actionLmmHook::is_linked();} virtual int unref(); void cancel(); void suspend(); diff --git a/src/surf/workstation_ptask_L07.cpp b/src/surf/workstation_ptask_L07.cpp index 63e7594aad..c93b29da9d 100644 --- a/src/surf/workstation_ptask_L07.cpp +++ b/src/surf/workstation_ptask_L07.cpp @@ -43,16 +43,16 @@ WorkstationL07Model::~WorkstationL07Model() { double WorkstationL07Model::shareResources(double /*now*/) { - void *_action; WorkstationL07ActionLmmPtr action; - xbt_swag_t running_actions = getRunningActionSet(); + ActionListPtr running_actions = getRunningActionSet(); double min = this->shareResourcesMaxMin(running_actions, ptask_maxmin_system, bottleneck_solve); - xbt_swag_foreach(_action, running_actions) { - action = dynamic_cast(static_cast(_action)); + for(ActionList::iterator it(running_actions->begin()), itend(running_actions->end()) + ; it != itend ; ++it) { + action = dynamic_cast(&*it); if (action->m_latency > 0) { if (min < 0) { min = action->m_latency; @@ -74,13 +74,14 @@ double WorkstationL07Model::shareResources(double /*now*/) void WorkstationL07Model::updateActionsState(double /*now*/, double delta) { double deltap = 0.0; - void *_action, *_next_action; WorkstationL07ActionLmmPtr action; - xbt_swag_t actionSet = getRunningActionSet(); - xbt_swag_foreach_safe(_action, _next_action, actionSet) { - action = dynamic_cast(static_cast(_action)); + ActionListPtr actionSet = getRunningActionSet(); + for(ActionList::iterator it(actionSet->begin()), itNext = it, itend(actionSet->end()) + ; it != itend ; it=itNext) { + ++itNext; + action = dynamic_cast(&*it); deltap = delta; if (action->m_latency > 0) { if (action->m_latency > deltap) { @@ -655,7 +656,8 @@ int WorkstationL07ActionLmm::unref() { m_refcount--; if (!m_refcount) { - xbt_swag_remove(static_cast(this), p_stateSet); + if (actionHook::is_linked()) + p_stateSet->erase(p_stateSet->iterator_to(*this)); if (getVariable()) lmm_variable_free(ptask_maxmin_system, getVariable()); delete this; diff --git a/testsuite/surf/surf_usage.c b/testsuite/surf/surf_usage.c index 8ca71029e6..00faeb24c4 100644 --- a/testsuite/surf/surf_usage.c +++ b/testsuite/surf/surf_usage.c @@ -100,29 +100,29 @@ void test(char *platform) XBT_DEBUG("Next Event : %g", now); XBT_DEBUG("\t CPU actions"); while ((action = - xbt_swag_extract(surf_model_failed_action_set((surf_model_t)surf_cpu_model_pm)))) { + surf_model_extract_failed_action_set((surf_model_t)surf_cpu_model_pm))) { XBT_DEBUG("\t * Failed : %p", action); surf_action_unref(action); } while ((action = - xbt_swag_extract(surf_model_done_action_set((surf_model_t)surf_cpu_model_pm)))) { + surf_model_extract_done_action_set((surf_model_t)surf_cpu_model_pm))) { XBT_DEBUG("\t * Done : %p", action); surf_action_unref(action); } XBT_DEBUG("\t Network actions"); while ((action = - xbt_swag_extract(surf_model_failed_action_set((surf_model_t)surf_network_model)))) { + surf_model_extract_failed_action_set((surf_model_t)surf_network_model))) { XBT_DEBUG("\t * Failed : %p", action); surf_action_unref(action); } while ((action = - xbt_swag_extract(surf_model_done_action_set((surf_model_t)surf_network_model)))) { + surf_model_extract_done_action_set((surf_model_t)surf_network_model))) { XBT_DEBUG("\t * Done : %p", action); surf_action_unref(action); } - } while ((xbt_swag_size(surf_model_running_action_set((surf_model_t)surf_network_model)) || - xbt_swag_size(surf_model_running_action_set((surf_model_t)surf_cpu_model_pm))) && + } while ((surf_model_running_action_set_size((surf_model_t)surf_network_model) || + surf_model_running_action_set_size((surf_model_t)surf_cpu_model_pm)) && surf_solve(-1.0) >= 0.0); XBT_DEBUG("Simulation Terminated"); diff --git a/testsuite/surf/surf_usage2.c b/testsuite/surf/surf_usage2.c index d07a552a6b..8bb1a40e36 100644 --- a/testsuite/surf/surf_usage2.c +++ b/testsuite/surf/surf_usage2.c @@ -80,15 +80,15 @@ void test(char *platform) xbt_dynar_foreach(model_list, iter, model) { XBT_DEBUG("\t %s actions", surf_model_name(model)); - while ((action = xbt_swag_extract(surf_model_failed_action_set((surf_model_t)model)))) { + while ((action = surf_model_extract_failed_action_set((surf_model_t)model))) { XBT_DEBUG("\t * Failed : %p", action); surf_action_unref(action); } - while ((action = xbt_swag_extract(surf_model_done_action_set((surf_model_t)model)))) { + while ((action = surf_model_extract_done_action_set((surf_model_t)model))) { XBT_DEBUG("\t * Done : %p", action); surf_action_unref(action); } - if (xbt_swag_size(surf_model_running_action_set((surf_model_t)model))) { + if (surf_model_running_action_set_size((surf_model_t)model)) { XBT_DEBUG("running %s", surf_model_name(model)); running = 1; }