Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
[xbt/surf] Change the costly heapremove+heapinsert used in share resource lazy algorithm.
[simgrid.git] / src / surf / surf_interface.cpp
index 3ee6695..6de2b62 100644 (file)
@@ -25,29 +25,35 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_kernel, surf,
 
 /* This function is a pimple that we ought to fix. But it won't be easy.
  *
- * The surf_solve() function does properly return the set of actions that changed.
- * Instead, each model change a global data, and then the caller of surf_solve must
- * pick into these sets of action_failed and action_done.
+ * The surf_solve() function does properly return the set of actions that
+ * changed. Instead, each model change a global data, and then the caller of
+ * surf_solve must pick into these sets of action_failed and action_done.
  *
- * This was not clean but ok as long as we didn't had to restart the processes when the resource comes back up.
- * We worked by putting sentinel actions on every resources we are interested in,
- * so that surf informs us if/when the corresponding resource fails.
+ * This was not clean but ok as long as we didn't had to restart the processes
+ * when the resource comes back up.
+ * We worked by putting sentinel actions on every resources we are interested
+ * in, so that surf informs us if/when the corresponding resource fails.
  *
- * But this does not work to get Simix informed of when a resource comes back up, and this is where this pimple comes.
- * We have a set of resources that are currently down and for which simix needs to know when it comes back up.
- * And the current function is called *at every simulation step* to sweep over that set, searching for a resource
- * that was turned back up in the meanwhile. This is UGLY and slow.
+ * But this does not work to get Simix informed of when a resource comes back
+ * up, and this is where this pimple comes. We have a set of resources that are
+ * currently down and for which simix needs to know when it comes back up.
+ * And the current function is called *at every simulation step* to sweep over
+ * that set, searching for a resource that was turned back up in the meanwhile.
+ * This is UGLY and slow.
  *
- * The proper solution would be to not rely on globals for the action_failed and action_done swags.
- * They must be passed as parameter by the caller (the handling of these actions in simix may let you
- * think that these two sets can be merged, but their handling in SimDag induce the contrary unless this
- * simdag code can check by itself whether the action is done of failed -- seems very doable, but yet more
- * cleanup to do).
+ * The proper solution would be to not rely on globals for the action_failed and
+ * action_done swags. They must be passed as parameter by the caller (the
+ * handling of these actions in simix may let you think that these two sets can
+ * be merged, but their handling in SimDag induce the contrary unless this
+ * simdag code can check by itself whether the action is done of failed -- seems
+ * very doable, but yet more cleanup to do).
  *
- * Once surf_solve() is passed the set of actions that changed, you want to add a new set of resources back up
- * as parameter to this function. You also want to add a boolean field "restart_watched" to each resource, and
- * make sure that whenever a resource with this field enabled comes back up, it's added to that set so that Simix
- * sees it and react accordingly. This would kill that need for surf to call simix.
+ * Once surf_solve() is passed the set of actions that changed, you want to add
+ * a new set of resources back up as parameter to this function. You also want
+ * to add a boolean field "restart_watched" to each resource, and make sure that
+ * whenever a resource with this field enabled comes back up, it's added to that
+ * set so that Simix sees it and react accordingly. This would kill that need
+ * for surf to call simix.
  *
  */
 
@@ -93,13 +99,14 @@ xbt_dict_t watched_hosts_lib;
 surf_callback(void, void) surfExitCallbacks;
 
 s_surf_model_description_t surf_plugin_description[] = {
-                 {"Energy",
-                  "Cpu energy consumption.",
-                  sg_energy_plugin_init},
-                 {NULL, NULL,  NULL}      /* this array must be NULL terminated */
+    {"Energy",
+     "Cpu energy consumption.",
+     sg_energy_plugin_init},
+     {NULL, NULL,  NULL}      /* this array must be NULL terminated */
 };
 
-/* Don't forget to update the option description in smx_config when you change this */
+/* Don't forget to update the option description in smx_config when you change
+   this */
 s_surf_model_description_t surf_network_model_description[] = {
   {"LV08",
    "Realistic network analytic model (slow-start modeled by multiplying latency by 10.4, bandwidth by .92; bottleneck sharing uses a payload of S=8775 for evaluating RTT). ",
@@ -509,11 +516,11 @@ double Model::shareResources(double now)
 {
   //FIXME: set the good function once and for all
   if (p_updateMechanism == UM_LAZY)
-       return shareResourcesLazy(now);
+    return shareResourcesLazy(now);
   else if (p_updateMechanism == UM_FULL)
-       return shareResourcesFull(now);
+    return shareResourcesFull(now);
   else
-       xbt_die("Invalid cpu update mechanism!");
+    xbt_die("Invalid cpu update mechanism!");
 }
 
 double Model::shareResourcesLazy(double now)
@@ -541,7 +548,7 @@ double Model::shareResourcesLazy(double now)
       continue;
 
     /* bogus priority, skip it */
-    if (action->getPriority() <= 0 || action->getHeapActionType()==LATENCY)
+    if (action->getPriority() <= 0 || action->getHat()==LATENCY)
       continue;
 
     action->updateRemainingLazy(now);
@@ -576,17 +583,16 @@ double Model::shareResourcesLazy(double now)
         action->getMaxDuration());
 
     if (min != -1) {
-      action->heapRemove();
-      action->heapInsert(min, max_dur_flag ? MAX_DURATION : NORMAL);
+      action->heapUpdate(p_actionHeap, min, max_dur_flag ? MAX_DURATION : NORMAL);
       XBT_DEBUG("Insert at heap action(%p) min %f now %f", action, min,
                 now);
     } else DIE_IMPOSSIBLE;
   }
 
   //hereafter must have already the min value for this resource model
-  if (!p_actionHeap->empty()) {
-    min = p_actionHeap->topKey() - now;
-  else
+  if (xbt_heap_size(p_actionHeap) > 0)
+    min = xbt_heap_maxkey(p_actionHeap) - now;
+  else
     min = -1;
 
   XBT_DEBUG("The minimum with the HEAP %f", min);
@@ -610,7 +616,7 @@ double Model::shareResourcesMaxMin(ActionListPtr running_actions,
 
   ActionList::iterator it(running_actions->begin()), itend(running_actions->end());
   for(; it != itend ; ++it) {
-         action = &*it;
+    action = &*it;
     value = lmm_variable_getvalue(action->getVariable());
     if ((value > 0) || (action->getMaxDuration() >= 0))
       break;
@@ -665,10 +671,12 @@ void Model::updateActionsState(double now, double delta)
 
 void Model::updateActionsStateLazy(double /*now*/, double /*delta*/)
 {
+ THROW_UNIMPLEMENTED;
 }
 
 void Model::updateActionsStateFull(double /*now*/, double /*delta*/)
 {
+  THROW_UNIMPLEMENTED;
 }
 
 /************
@@ -738,7 +746,7 @@ const char *Resource::getName() {
 
 xbt_dict_t Resource::getProperties() {
   if (p_properties==NULL)
-       p_properties = xbt_dict_new();
+    p_properties = xbt_dict_new();
   return p_properties;
 }
 
@@ -851,7 +859,7 @@ void Action::setState(e_surf_action_state_t state)
     p_stateSet = NULL;
 
   if (p_stateSet)
-       p_stateSet->push_back(*this);
+    p_stateSet->push_back(*this);
   XBT_OUT();
 }
 
@@ -867,7 +875,7 @@ void Action::setBound(double bound)
     lmm_update_variable_bound(getModel()->getMaxminSystem(), getVariable(), bound);
 
   if (getModel()->getUpdateMechanism() == UM_LAZY && getLastUpdate()!=surf_get_clock())
-         heapRemove();
+    heapRemove(getModel()->getActionHeap());
   XBT_OUT();
 }
 
@@ -905,7 +913,7 @@ void Action::setMaxDuration(double duration)
   XBT_IN("(%p,%g)", this, duration);
   m_maxDuration = duration;
   if (getModel()->getUpdateMechanism() == UM_LAZY)      // remove action from the heap
-    heapRemove();
+    heapRemove(getModel()->getActionHeap());
   XBT_OUT();
 }
 
@@ -918,34 +926,34 @@ void Action::setPriority(double priority)
   lmm_update_variable_weight(getModel()->getMaxminSystem(), getVariable(), priority);
 
   if (getModel()->getUpdateMechanism() == UM_LAZY)
-       heapRemove();
+       heapRemove(getModel()->getActionHeap());
   XBT_OUT();
 }
 
 void Action::cancel(){
   setState(SURF_ACTION_FAILED);
   if (getModel()->getUpdateMechanism() == UM_LAZY) {
-       if (actionLmmHook::is_linked())
-         getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this));
-    heapRemove();
+    if (actionLmmHook::is_linked())
+      getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this));
+    heapRemove(getModel()->getActionHeap());
   }
 }
 
 int Action::unref(){
   m_refcount--;
   if (!m_refcount) {
-         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();
+    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());
       if (actionLmmHook::is_linked())
-             getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this));
+        getModel()->getModifiedSet()->erase(getModel()->getModifiedSet()->iterator_to(*this));
     }
-         delete this;
-         return 1;
+    delete this;
+    return 1;
   }
   return 0;
 }
@@ -957,7 +965,7 @@ void Action::suspend()
     lmm_update_variable_weight(getModel()->getMaxminSystem(), getVariable(), 0.0);
     m_suspended = 1;
     if (getModel()->getUpdateMechanism() == UM_LAZY)
-      heapRemove();
+      heapRemove(getModel()->getActionHeap());
   }
   XBT_OUT();
 }
@@ -969,7 +977,7 @@ void Action::resume()
     lmm_update_variable_weight(getModel()->getMaxminSystem(), getVariable(), m_priority);
     m_suspended = 0;
     if (getModel()->getUpdateMechanism() == UM_LAZY)
-      heapRemove();
+      heapRemove(getModel()->getActionHeap());
   }
   XBT_OUT();
 }
@@ -985,21 +993,39 @@ bool Action::isSuspended()
  * LATENCY = this is a heap entry to warn us when the latency is payed
  * MAX_DURATION =this is a heap entry to warn us when the max_duration limit is reached
  */
-void Action::heapInsert(double key, enum heap_action_type hat)
+void Action::heapInsert(xbt_heap_t heap, double key, enum heap_action_type hat)
 {
   m_hat = hat;
-  sp_heapHandle = getModel()->getActionHeap()->push(key, this);
+  xbt_heap_push(heap, this, key);
 }
 
-void Action::heapRemove()
+void Action::heapRemove(xbt_heap_t heap)
 {
   m_hat = NOTSET;
-  if (sp_heapHandle) {
-    getModel()->getActionHeap()->erase(sp_heapHandle);
-    sp_heapHandle.reset();
+  if (m_indexHeap >= 0) {
+    xbt_heap_remove(heap, m_indexHeap);
   }
 }
 
+void Action::heapUpdate(xbt_heap_t heap, double key, enum heap_action_type hat)
+{
+  m_hat = hat;
+  if (m_indexHeap >= 0) {
+    xbt_heap_update(heap, m_indexHeap, key);
+  }else{
+    xbt_heap_push(heap, this, key);
+  }
+}
+
+/* added to manage the communication action's heap */
+void surf_action_lmm_update_index_heap(void *action, int i) {
+  ((ActionPtr)action)->updateIndexHeap(i);
+}
+
+void Action::updateIndexHeap(int i) {
+  m_indexHeap = i;
+}
+
 double Action::getRemains()
 {
   XBT_IN("(%p)", this);
@@ -1060,12 +1086,12 @@ void Action::updateRemainingLazy(double now)
         (lmm_get_variable_weight(getVariable()) > 0)) {
       finish();
       setState(SURF_ACTION_DONE);
-      heapRemove();
+      heapRemove(getModel()->getActionHeap());
     } else if (((m_maxDuration != NO_MAX_DURATION)
         && (m_maxDuration <= 0))) {
       finish();
       setState(SURF_ACTION_DONE);
-      heapRemove();
+      heapRemove(getModel()->getActionHeap());
     }
   }