/* 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. */
+/*
+ commit: e2d6799c4182f00443b3013aadb1c2412372460f
+ This commit retrieves the old implementation of CPU_TI with multi-levels.
+*/
+
#include "surf_private.h"
#include "trace_mgr_private.h"
#include "cpu_ti_private.h"
/* prototypes of new trace functions */
static double surf_cpu_integrate_trace(surf_cpu_ti_tgmr_t trace, double a,
double b);
-static double surf_cpu_integrate_trace_simple(surf_cpu_ti_tgmr_t trace,
- double a, double b);
static double surf_cpu_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
double amount);
static double surf_cpu_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t trace,
double a, double amount);
-static double surf_cpu_solve_trace_simple(surf_cpu_ti_tgmr_t trace, double a,
- double amount);
-static void surf_cpu_free_trace(surf_cpu_ti_tgmr_t trace);
-static void surf_cpu_free_time_series(surf_cpu_ti_timeSeries_t timeSeries);
-static double surf_cpu_integrate_exactly(surf_cpu_ti_tgmr_t trace, int index,
- double a, double b);
-static double surf_cpu_solve_exactly(surf_cpu_ti_tgmr_t trace, int index,
- double a, double amount);
+static void surf_cpu_free_tmgr(surf_cpu_ti_tgmr_t trace);
+
+static double surf_cpu_integrate_trace_simple(surf_cpu_ti_trace_t trace,
+ double a, double b);
+static double surf_cpu_integrate_trace_simple_point(surf_cpu_ti_trace_t trace,
+ double a);
+static double surf_cpu_solve_trace_simple(surf_cpu_ti_trace_t trace, double a,
+ double amount);
+static int surf_cpu_binary_search(double *array, double a, int low, int high);
/* end prototypes */
-static void surf_cpu_free_time_series(surf_cpu_ti_timeSeries_t timeSeries)
+static void surf_cpu_free_trace(surf_cpu_ti_trace_t trace)
{
- xbt_free(timeSeries->values);
- xbt_free(timeSeries->trace_index);
- xbt_free(timeSeries->trace_value);
- xbt_free(timeSeries);
+ if (trace->time_points)
+ xbt_free(trace->time_points);
+ if (trace->integral)
+ xbt_free(trace->integral);
+ xbt_free(trace);
}
-static void surf_cpu_free_trace(surf_cpu_ti_tgmr_t trace)
+static void surf_cpu_free_tmgr(surf_cpu_ti_tgmr_t trace)
{
- int i;
-
- for (i = 0; i < trace->nb_levels; i++)
- surf_cpu_free_time_series(trace->levels[i]);
-
- xbt_free(trace->levels);
+ if (trace->trace)
+ surf_cpu_free_trace(trace->trace);
xbt_free(trace);
}
-static surf_cpu_ti_timeSeries_t surf_cpu_ti_time_series_new(tmgr_trace_t
- power_trace,
- double spacing,
- double total_time)
+static surf_cpu_ti_trace_t surf_cpu_trace_new(tmgr_trace_t power_trace)
{
- surf_cpu_ti_timeSeries_t series;
- double time = 0.0, value = 0.0, sum_delta = 0.0;
- double previous_time = 0.0, old_time = 0.0;
- int event_lost = 0, next_index = 0;
- double next_time = 0.0;
- int total_alloc = 0;
+ surf_cpu_ti_trace_t trace;
s_tmgr_event_t val;
unsigned int cpt;
-
- series = xbt_new0(s_surf_cpu_ti_timeSeries_t, 1);
- series->spacing = spacing;
- series->power_trace = power_trace;
-
- /* alloc memory only once, it's faster than doing realloc each time */
- total_alloc = (int) ceil((total_time / spacing));
- series->values = xbt_malloc0(sizeof(double) * total_alloc);
- series->trace_index = xbt_malloc0(sizeof(int) * total_alloc);
- series->trace_value = xbt_malloc0(sizeof(double) * total_alloc);
-
+ double integral = 0;
+ double time = 0;
+ int i = 0;
+ trace = xbt_new0(s_surf_cpu_ti_trace_t, 1);
+ trace->time_points =
+ xbt_malloc0(sizeof(double) *
+ (xbt_dynar_length(power_trace->event_list) + 1));
+ trace->integral =
+ xbt_malloc0(sizeof(double) *
+ (xbt_dynar_length(power_trace->event_list) + 1));
+ trace->nb_points = xbt_dynar_length(power_trace->event_list);
xbt_dynar_foreach(power_trace->event_list, cpt, val) {
- /* delta = the next trace event
- * value = state until next event */
+ trace->time_points[i] = time;
+ trace->integral[i] = integral;
+ integral += val.delta * val.value;
time += val.delta;
-
- /* ignore events until next spacing */
- if (time < (series->nb_points + 1) * spacing) {
- value += val.value * val.delta;
- sum_delta += val.delta;
- old_time = time;
- event_lost = 1;
- continue;
- }
-
- /* update value and sum_delta with the space between last point in trace(old_time) and next spacing */
- value += val.value * ((series->nb_points + 1) * spacing - old_time);
- sum_delta += ((series->nb_points + 1) * spacing - old_time);
- /* calcule the value to next spacing */
- value /= sum_delta;
-
- while (previous_time + spacing <= time) {
- /* update first spacing with mean of points.
- * others with the right value */
- if (event_lost) {
- series->values[series->nb_points] = value;
- series->trace_index[series->nb_points] = next_index;
- series->trace_value[series->nb_points] = next_time;
- event_lost = 0;
- } else {
- series->trace_index[series->nb_points] = -1;
- series->values[series->nb_points] = val.value;
- }
- (series->nb_points)++;
- previous_time += spacing;
- }
- /* update value and sum_delta, interval: [time, next spacing] */
- value = (time - previous_time) * val.value;
- sum_delta = (time - previous_time);
- old_time = time;
- next_index = (int) cpt + 1;
- next_time = time;
- event_lost = 1;
- }
- /* last spacing
- * ignore small amount at end */
- double_update(&time, (series->nb_points) * spacing);
- if (time > 0) {
- /* here the value is divided by spacing in order to have exactly the value of last chunk (independently of its size). After, when we calcule the integral, we multiply by actual_last_time insted of last_time */
- value /= spacing;
- series->values[series->nb_points] = value;
- /* update first spacing with mean of points
- * others with the right value */
- if (event_lost) {
- series->trace_index[series->nb_points] = next_index;
- series->trace_value[series->nb_points] = next_time;
- } else
- series->trace_index[series->nb_points] = -1;
- (series->nb_points)++;
- }
- return series;
-}
-
-/**
-* \brief Create new levels of points.
-*
-* This function assumes that the input series is
-* evenly spaces, starting at time 0. That is the sort
-* of series produced by surf_cpu_ti_time_series_new()
-*
-* \param original Original timeSeries structure
-* \param factor New factor to spacing
-* \return New timeSeries structure with spacing*factor
-*/
-static surf_cpu_ti_timeSeries_t
-surf_cpu_ti_time_series_coarsen(surf_cpu_ti_timeSeries_t original, int factor)
-{
- surf_cpu_ti_timeSeries_t series;
- int j, i = 0;
- double dfactor = (double) (factor);
- double ave;
-
- if (original->nb_points <= factor) {
- DEBUG0("Warning: Not enough data points to coarsen time series");
- return NULL;
+ i++;
}
-
- series = xbt_new0(s_surf_cpu_ti_timeSeries_t, 1);
- series->spacing = (original->spacing) * dfactor;
-
- while (i + factor <= original->nb_points) {
- /* Averaging */
- ave = 0.0;
- for (j = i; j < i + factor; j++) {
- ave += original->values[j];
- }
- ave /= dfactor;
- /* Updating */
- series->values = xbt_realloc(series->values,
- (series->nb_points + 1) * sizeof(double));
- series->values[(series->nb_points)++] = ave;
- i += factor;
- }
-
- return series;
+ trace->time_points[i] = time;
+ trace->integral[i] = integral;
+ return trace;
}
/**
-* \brief Create a new integration trace from a tmgr_trace_t
+* \brief Creates a new integration trace from a tmgr_trace_t
*
* \param power_trace CPU availability trace
-* \param value Percentage of CPU power disponible (usefull to fixed tracing)
+* \param value Percentage of CPU power available (useful to fixed tracing)
* \param spacing Initial spacing
* \return Integration trace structure
*/
double value)
{
surf_cpu_ti_tgmr_t trace;
- surf_cpu_ti_timeSeries_t series;
- int i;
double total_time = 0.0;
s_tmgr_event_t val;
unsigned int cpt;
return trace;
}
+ trace->type = TRACE_DYNAMIC;
+ trace->power_trace = power_trace;
+
/* count the total time of trace file */
xbt_dynar_foreach(power_trace->event_list, cpt, val) {
total_time += val.delta;
}
- trace->actual_last_time = total_time;
-
- DEBUG2("Value %lf, Spacing %lf", value, power_trace->timestep);
- series =
- surf_cpu_ti_time_series_new(power_trace, power_trace->timestep,
- total_time);
- if (!series)
- return NULL;
-
- trace->type = TRACE_DYNAMIC;
-
- trace->levels = xbt_new0(surf_cpu_ti_timeSeries_t, 1);
- trace->levels[(trace->nb_levels)++] = series;
-
-/* Do the coarsening with some arbitrary factors */
- for (i = 1; i < TRACE_NB_LEVELS; i++) {
- series = surf_cpu_ti_time_series_coarsen(trace->levels[i - 1], 4 * i);
-
- if (series) { /* If coarsening was possible, add it */
- trace->levels = xbt_realloc(trace->levels,
- (trace->nb_levels +
- 1) * sizeof(s_surf_cpu_ti_timeSeries_t));
- trace->levels[(trace->nb_levels)++] = series;
- } else { /* otherwise stop */
- break;
- }
- }
-/* calcul of initial integrate */
- trace->last_time =
- power_trace->timestep * ((double) (trace->levels[0]->nb_points));
-
- trace->total =
- surf_cpu_integrate_trace(trace, 0.0, trace->actual_last_time);
+ trace->trace = surf_cpu_trace_new(power_trace);
+ trace->last_time = total_time;
+ trace->total = surf_cpu_integrate_trace_simple(trace->trace, 0, total_time);
- DEBUG3("Total integral %lf, last_time %lf actual_last_time %lf",
- trace->total, trace->last_time, trace->actual_last_time);
+ DEBUG2("Total integral %lf, last_time %lf ",
+ trace->total, trace->last_time);
return trace;
}
empty_trace = tmgr_empty_trace_new();
cpu->power_event =
tmgr_history_add_trace(history, empty_trace,
- cpu->avail_trace->actual_last_time, 0, cpu);
+ cpu->avail_trace->last_time, 0, cpu);
}
}
xbt_dict_set(surf_model_resource_set(surf_cpu_model), name, cpu,
DEBUG2("Add power trace: %s to CPU(%s)", trace_name, elm);
if (cpu->avail_trace)
- surf_cpu_free_trace(cpu->avail_trace);
+ surf_cpu_free_tmgr(cpu->avail_trace);
cpu->avail_trace = cpu_ti_parse_trace(trace, cpu->power_scale);
+
+ /* add a fake trace event if periodicity == 0 */
+ if (trace && xbt_dynar_length(trace->event_list) > 1) {
+ s_tmgr_event_t val;
+ xbt_dynar_get_cpy(trace->event_list,
+ xbt_dynar_length(trace->event_list) - 1, &val);
+ if (val.delta == 0) {
+ tmgr_trace_t empty_trace;
+ empty_trace = tmgr_empty_trace_new();
+ cpu->power_event =
+ tmgr_history_add_trace(history, empty_trace,
+ cpu->avail_trace->last_time, 0, cpu);
+ }
+ }
}
}
}
/**
-* \brief Update the remaning amount of actions
+* \brief Update the remaining amount of actions
*
* \param cpu Cpu on which the actions are running
* \param now Current time
cpu_update_remaining_amount(cpu, date);
xbt_swag_insert(cpu, modified_cpu);
- power_trace = cpu->avail_trace->levels[0]->power_trace;
+ power_trace = cpu->avail_trace->power_trace;
xbt_dynar_get_cpy(power_trace->event_list,
xbt_dynar_length(power_trace->event_list) - 1, &val);
/* free old trace */
- surf_cpu_free_trace(cpu->avail_trace);
+ surf_cpu_free_tmgr(cpu->avail_trace);
cpu->power_scale = val.value;
trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
if (tmgr_trace_event_free(event_type))
cpu->power_event = NULL;
+
} else if (event_type == cpu->state_event) {
if (value > 0)
cpu->state_current = SURF_RESOURCE_ON;
}
/**
-* \brief Auxiliar function to update the cpu power scale.
+* \brief Auxiliary function to update the CPU power scale.
*
* This function uses the trace structure to return the power scale at the determined time a.
* \param trace Trace structure to search the updated power scale
* \param a Time
-* \return Cpu power scale
+* \return CPU power scale
*/
static double surf_cpu_get_power_scale(surf_cpu_ti_tgmr_t trace, double a)
{
double reduced_a;
int point;
+ s_tmgr_event_t val;
reduced_a = a - floor(a / trace->last_time) * trace->last_time;
- point = (int) (reduced_a / trace->levels[0]->spacing);
- return trace->levels[0]->values[point];
+ point =
+ surf_cpu_binary_search(trace->trace->time_points, reduced_a, 0,
+ trace->trace->nb_points - 1);
+ xbt_dynar_get_cpy(trace->power_trace->event_list, 0, &val);
+ return val.value;
}
static double get_available_speed(void *cpu)
xbt_dict_foreach(surf_model_resource_set(surf_cpu_model), cursor, key, cpu) {
cpu_ti_t CPU = cpu;
xbt_swag_free(CPU->action_set);
- surf_cpu_free_trace(CPU->avail_trace);
+ surf_cpu_free_tmgr(CPU->avail_trace);
}
surf_model_exit(surf_cpu_model);
}
-///////////////// BEGIN INTEGRAL //////////////
-
/**
* \brief Integrate trace
*
b_index = (int) (floor(b / trace->last_time));
if (a_index > b_index) { /* Same chunk */
- return surf_cpu_integrate_trace_simple(trace,
+ return surf_cpu_integrate_trace_simple(trace->trace,
a - (a_index -
1) * trace->last_time,
b - (b_index) * trace->last_time);
}
- first_chunk = surf_cpu_integrate_trace_simple(trace,
+ first_chunk = surf_cpu_integrate_trace_simple(trace->trace,
a - (a_index -
1) * trace->last_time,
trace->last_time);
middle_chunk = (b_index - a_index) * trace->total;
- last_chunk = surf_cpu_integrate_trace_simple(trace,
+ last_chunk = surf_cpu_integrate_trace_simple(trace->trace,
0.0,
b -
(b_index) * trace->last_time);
}
/**
-* \brief Integrate the trace between a and b.
-*
-* integrates without taking cyclic-traces into account.
-* [a,b] \subset [0,last_time]
-*
-* \param trace Trace structure.
-* \param a Begin of interval
-* \param b End of interval
-* \return the integrate value. -1 if an error occurs.
+ * \brief Auxiliary function to calculate the integral between a and b.
+ * It simply calculates the integral at point a and b and returns the difference
+ * between them.
+ * \param trace Trace structure
+ * \param a Initial point
+ * \param b Final point
+ * \return Integral
*/
-static double surf_cpu_integrate_trace_simple(surf_cpu_ti_tgmr_t trace,
+static double surf_cpu_integrate_trace_simple(surf_cpu_ti_trace_t trace,
double a, double b)
{
- double integral = 0.0;
- int i;
- long index;
- int top_level = 0;
- long l_bounds[TRACE_NB_LEVELS];
- long u_bounds[TRACE_NB_LEVELS];
- double a_divided_by_spacing;
- double current_spacing;
- DEBUG2("Computing simple integral on [%.2f , %.2f]\n", a, b);
-
-/* Sanity checks */
- if ((a < 0.0) || (b < a) || (a > trace->last_time)
- || (b > trace->last_time)) {
- CRITICAL2
- ("Error, invalid integration interval [%.2f,%.2f]. You probably have a task executing with negative computation amount. Check your code.",
- a, b);
- xbt_abort();
- }
- if (b == a) {
- return 0.0;
- }
-
- for (i = 0; i < trace->nb_levels; i++) {
- a_divided_by_spacing = a / trace->levels[i]->spacing;
- if (ceil(a_divided_by_spacing) == a_divided_by_spacing)
- l_bounds[i] = 1 + (long) ceil(a_divided_by_spacing);
- else
- l_bounds[i] = (long) (ceil(a_divided_by_spacing));
- if (b == trace->last_time) {
- u_bounds[i] = (long) (floor(b / trace->levels[i]->spacing)) - 1;
- } else {
- u_bounds[i] = (long) (floor(b / trace->levels[i]->spacing));
- }
- DEBUG3("level %d: l%ld u%ld\n", i, l_bounds[i], u_bounds[i]);
-
- if (l_bounds[i] <= u_bounds[i])
- top_level = i;
- }
- DEBUG1("top_level=%d\n", top_level);
-
-/* Are a and b BOTH in the same chunk of level 0 ? */
- if (l_bounds[0] > u_bounds[0]) {
- return surf_cpu_integrate_exactly(trace, u_bounds[0], a, b);
-#if 0
- return (b - a) * (trace->levels[0]->values[u_bounds[0]]);
-#endif
- }
-
-/* first sub-level amount */
- integral += ((l_bounds[0]) * (trace->levels[0]->spacing) - a) *
- (trace->levels[0]->values[l_bounds[0] - 1]);
-
- DEBUG1("Initial level 0 amount is %.2f\n", integral);
-
-/* first n-1 levels */
- for (i = 0; i < top_level; i++) {
-
- if (l_bounds[i] >= u_bounds[i])
- break;
-
- current_spacing = trace->levels[i]->spacing;
- index = l_bounds[i];
-
- DEBUG1("L%d:", i);
-
- while (double_positive
- (l_bounds[i + 1] * trace->levels[i + 1]->spacing -
- index * current_spacing)) {
- integral += current_spacing * trace->levels[i]->values[index];
- DEBUG2("%.2f->%.2f|",
- index * (trace->levels[i]->spacing),
- (index + 1) * (trace->levels[i]->spacing));
- index++;
- }
-
- DEBUG0("\n");
- }
-
- DEBUG1("After going up: %.2f\n", integral);
-
-/* n-th level */
- current_spacing = trace->levels[top_level]->spacing;
- index = l_bounds[top_level];
-
- DEBUG1("L%d:", top_level);
-
- while (index < u_bounds[top_level]) {
- integral += current_spacing * trace->levels[top_level]->values[index];
-
- DEBUG2("%.2f->%.2f|",
- index * (trace->levels[top_level]->spacing),
- (index + 1) * (trace->levels[top_level]->spacing));
-
- index++;
- }
-
- DEBUG0("\n");
- DEBUG1("After steady : %.2f\n", integral);
-
-/* And going back down */
- for (i = top_level - 1; i >= 0; i--) {
- if (l_bounds[i] > u_bounds[i])
- break;
-
- current_spacing = trace->levels[i]->spacing;
- index = rint(u_bounds[i + 1] * (trace->levels[i + 1]->spacing /
- current_spacing));
- DEBUG1("L%d:", i);
- while (double_positive
- ((u_bounds[i]) * current_spacing - index * current_spacing)) {
- integral += current_spacing * trace->levels[i]->values[index];
- DEBUG2("%.2f->%.2f|",
- index * (trace->levels[i]->spacing),
- (index + 1) * (trace->levels[i]->spacing));
- index++;
- }
- }
-
- DEBUG1("After going down : %.2f", integral);
-
+ return surf_cpu_integrate_trace_simple_point(trace,
+ b) -
+ surf_cpu_integrate_trace_simple_point(trace, a);
+}
-/* Little piece at the end */
-#if 0
- integral += (b - u_bounds[0] * (trace->levels[0]->spacing)) *
- (trace->levels[0]->values[u_bounds[0]]);
-#endif
- integral +=
- surf_cpu_integrate_exactly(trace, u_bounds[0],
- u_bounds[0] * (trace->levels[0]->spacing), b);
- DEBUG1("After last bit : %.2f", integral);
+/**
+ * \brief Auxiliary function to calculate the integral at point a.
+ * \param trace Trace structure
+ * \param a point
+ * \return Integral
+*/
+static double surf_cpu_integrate_trace_simple_point(surf_cpu_ti_trace_t trace,
+ double a)
+{
+ double integral = 0;
+ int ind;
+ double a_aux = a;
+ ind =
+ surf_cpu_binary_search(trace->time_points, a, 0, trace->nb_points - 1);
+ integral += trace->integral[ind];
+ DEBUG7("a %lf ind %d integral %lf ind + 1 %lf ind %lf time +1 %lf time %lf",
+ a, ind, integral, trace->integral[ind + 1], trace->integral[ind],
+ trace->time_points[ind + 1], trace->time_points[ind]);
+ double_update(&a_aux, trace->time_points[ind]);
+ if (a_aux > 0)
+ integral +=
+ ((trace->integral[ind + 1] -
+ trace->integral[ind]) / (trace->time_points[ind + 1] -
+ trace->time_points[ind])) * (a -
+ trace->
+ time_points
+ [ind]);
+ DEBUG2("Integral a %lf = %lf", a, integral);
return integral;
}
-
/**
-* \brief Calcul the time needed to execute "amount" on cpu.
+* \brief Calculate the time needed to execute "amount" on cpu.
*
* Here, amount can span multiple trace periods
*
* \param trace CPU trace structure
* \param a Initial time
-* \param amount Amount of calcul to be executed
+* \param amount Amount to be executed
* \return End time
*/
static double surf_cpu_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
/* Re-map to the original b and amount */
b = (trace->last_time) * (int) (floor(a / trace->last_time)) +
- (quotient * trace->actual_last_time) + reduced_b;
+ (quotient * trace->last_time) + reduced_b;
return b;
}
/**
-* \brief Auxiliar function to solve integral
+* \brief Auxiliary function to solve integral
*
* Here, amount is <= trace->total
* and a <=trace->last_time
double b;
DEBUG2("Solve integral: [%.2f, amount=%.2f]", a, amount);
-
amount_till_end = surf_cpu_integrate_trace(trace, a, trace->last_time);
/*
fprintf(stderr,"amount_till_end=%.2f\n",amount_till_end);
*/
if (amount_till_end > amount) {
- b = surf_cpu_solve_trace_simple(trace, a, amount);
+ b = surf_cpu_solve_trace_simple(trace->trace, a, amount);
} else {
b = trace->last_time +
- surf_cpu_solve_trace_simple(trace, 0.0, amount - amount_till_end);
+ surf_cpu_solve_trace_simple(trace->trace, 0.0,
+ amount - amount_till_end);
}
-
return b;
}
/**
-* \brief Auxiliar function to solve integral
-* surf_cpu_solve_trace_simple()
-*
-* solve for the upper bound without taking
-* cyclic-traces into account.
-*
-* [a,y] \subset [0,last_time]
-*
+ * \brief Auxiliary function to solve integral.
+ * It returns the date when the requested amount of flops is available
+ * \param trace Trace structure
+ * \param a Initial point
+ * \param amount Amount of flops
+ * \return The date when amount is available.
*/
-static double surf_cpu_solve_trace_simple(surf_cpu_ti_tgmr_t trace, double a,
+static double surf_cpu_solve_trace_simple(surf_cpu_ti_trace_t trace, double a,
double amount)
{
- double next_chunk;
- double remains;
- int i;
- long index;
- int top_level;
- double b;
- int done;
- long l_bounds[TRACE_NB_LEVELS]; /* May be too bgi for this trace */
- double a_divided_by_spacing;
- double current_spacing;
-
- DEBUG2("Solving simple integral [x=%.2f,amount=%.2f]", a, amount);
-
-/* Sanity checks */
- if ((a < 0.0) || (amount < 0.0) || (a > trace->last_time)) {
- CRITICAL2
- ("Error, invalid parameters [a = %.2f, amount = %.2f]. You probably have a task executing with negative computation amount. Check your code.",
- a, amount);
- xbt_abort();
- }
- if (amount == 0.0) {
- /* fprintf(stderr,"Warning: trivial integral solve\n"); */
- return a;
- }
-
- for (i = 0; i < trace->nb_levels; i++) {
- a_divided_by_spacing = a / trace->levels[i]->spacing;
- if (ceil(a_divided_by_spacing) == a_divided_by_spacing)
- l_bounds[i] = 1 + (long) ceil(a_divided_by_spacing);
- else
- l_bounds[i] = (long) (ceil(a_divided_by_spacing));
-
- if ((l_bounds[i] + 1) * trace->levels[i]->spacing > trace->last_time)
- break;
-
- DEBUG2("level %d: l%ld", i, l_bounds[i]);
- }
- if (i == trace->nb_levels)
- top_level = trace->nb_levels - 1;
- else {
- top_level = i;
- }
-
- remains = amount;
-/* first sub-level amount */
-/* old code, keep here for a while */
-#if 0
- next_chunk = ((l_bounds[0]) * (trace->levels[0]->spacing) - a) *
- (trace->levels[0]->values[l_bounds[0] - 1]);
-#endif
- next_chunk =
- surf_cpu_integrate_exactly(trace, l_bounds[0] - 1, a,
- (l_bounds[0]) * (trace->levels[0]->spacing));
-
- if (remains - next_chunk < 0.0) {
-#if 0
- b = a + (amount / trace->levels[0]->values[l_bounds[0] - 1]);
-#endif
- b = a + surf_cpu_solve_exactly(trace, l_bounds[0] - 1, a, amount);
- DEBUG1("Returning sub-level[0] result %.2f", b);
-
- return b;
- } else {
- b = (l_bounds[0]) * (trace->levels[0]->spacing);
- remains -= next_chunk;
- }
- DEBUG2("After sub-0 stuff: remains %.2f (b=%.2f)", remains, b);
-
-/* first n-1 levels */
- DEBUG0("Going up levels");
-
- done = 0;
- for (i = 0; i < top_level; i++) {
-
- current_spacing = trace->levels[i]->spacing;
- index = l_bounds[i];
-
- DEBUG1("L%d:", i);
-
- while (double_positive
- (l_bounds[i + 1] * trace->levels[i + 1]->spacing -
- index * current_spacing)
- && ((index + 1) * (current_spacing) < trace->last_time)) {
-
- next_chunk = current_spacing * trace->levels[i]->values[index];
-
- DEBUG3("%.2f next_chunk= %.2f remains=%.2f",
- (index + 1) * (trace->levels[i]->spacing), next_chunk, remains);
-
- if (remains - next_chunk < 0.0) { /* Too far */
- done = 1;
- break;
- } else { /* Keep going */
- DEBUG2("%.2f->%.2f|",
- index * (trace->levels[i]->spacing),
- (index + 1) * (trace->levels[i]->spacing));
-
- remains -= next_chunk;
- b = (index + 1) * (current_spacing);
- }
- index++;
- }
- if (done) {
- /* found chunk, fix the index to top level */
- i++;
- break;
- }
- }
-
- DEBUG0("Steady");
- top_level = i;
-
-/* n-th level */
- current_spacing = trace->levels[top_level]->spacing;
- index = l_bounds[top_level];
-
- DEBUG1("L%d:", top_level);
-
-/* iterate over the last level only if it hasn't found the chunk where the amount is */
- if (!done) {
- while (index < trace->levels[top_level]->nb_points) {
- next_chunk = current_spacing * trace->levels[top_level]->values[index];
- if (remains - next_chunk <= 0.0) { /* Too far */
- break;
- } else {
- DEBUG2("%.2f->%.2f|",
- index * (trace->levels[top_level]->spacing),
- (index + 1) * (trace->levels[top_level]->spacing));
-
- remains -= next_chunk;
- b = (index + 1) * (current_spacing);
- }
- index++;
- }
- }
- DEBUG2("remains = %.2f b=%.2f", remains, b);
-
-/* And going back down */
- DEBUG0("Going back down");
- for (i = top_level - 1; i >= 0; i--) {
-
- current_spacing = trace->levels[i]->spacing;
- /* use rint to trunc index due to precision problems */
- index = rint(b / trace->levels[i]->spacing);
-
- DEBUG1("L%d:", i);
-
- while (index < trace->levels[i]->nb_points) {
- next_chunk = current_spacing * trace->levels[i]->values[index];
- DEBUG3("remains %lf nextchu %lf value %lf", remains, next_chunk,
- trace->levels[i]->values[index]);
- if (remains - next_chunk <= 0.0) { /* Too far */
- break;
- } else {
- DEBUG3("%.2f->%.2f| b %lf",
- index * (current_spacing), (index + 1) * (current_spacing), b);
-
- remains -= next_chunk;
- b += current_spacing;
- }
- index++;
- }
- }
-
- DEBUG2("remains = %.2f b=%.2f\n", remains, b);
- DEBUG1("Last bit index=%ld\n", index);
-
-/* Little piece at the end */
-#if 0
- b += (remains) / (trace->levels[0]->values[index]);
-#endif
- b += surf_cpu_solve_exactly(trace, index, b, remains);
- DEBUG1("Total b %lf", b);
- return b;
-}
-
-/**
-* \brief This function calcules the exactly value of integral between a and b. It uses directly the tmgr_trace_t strucure.
-* It works only if the two points are in the same timestep.
-* \param trace Trace structure
-* \param index Index of timestep where the points are located
-* \param a First point of interval
-* \param b Second point
-* \return the integral value
-*/
-static double surf_cpu_integrate_exactly(surf_cpu_ti_tgmr_t trace, int index,
- double a, double b)
-{
- int tmgr_index;
- double integral = 0.0;
- double time = a;
- double tmgr_date;
- s_tmgr_event_t elem;
-
- /* already at the end */
- if (index >= trace->levels[0]->nb_points && !double_positive(b - a))
- return 0.0;
- tmgr_index = trace->levels[0]->trace_index[index];
- tmgr_date = trace->levels[0]->trace_value[index];
-
- DEBUG6
- ("Start time: %lf End time: %lf index %d tmgr_index %d tmgr_date %lf value %lf",
- a, b, index, tmgr_index, tmgr_date, trace->levels[0]->values[index]);
-
- if (tmgr_index < 0)
- return (b - a) * (trace->levels[0]->values[index]);
-
- while (a > tmgr_date) {
- /* too big timestep */
- if (tmgr_index >=
- xbt_dynar_length(trace->levels[0]->power_trace->event_list)) {
- return (b - a) * (trace->levels[0]->values[index]);
- }
-
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
- &elem);
- tmgr_date += elem.delta;
- tmgr_index++;
- }
- /* sum first slice [a, tmgr_date[ */
- if (a < tmgr_date) {
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list,
- tmgr_index - 1, &elem);
- if (b < tmgr_date) {
- return (b - a) * elem.value;
- }
-
- integral = (tmgr_date - a) * elem.value;
- time = tmgr_date;
- }
-
- while (tmgr_index <
- xbt_dynar_length(trace->levels[0]->power_trace->event_list)) {
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
- &elem);
- if (b <= time + elem.delta) {
- integral += (b - time) * elem.value;
- break;
- }
- integral += elem.delta * elem.value;
- time += elem.delta;
- tmgr_index++;
- }
-
- return integral;
+ double integral_a;
+ int ind;
+ double time;
+ integral_a = surf_cpu_integrate_trace_simple_point(trace, a);
+ ind =
+ surf_cpu_binary_search(trace->integral, integral_a + amount, 0,
+ trace->nb_points - 1);
+ time = trace->time_points[ind];
+ time +=
+ (integral_a + amount -
+ trace->integral[ind]) / ((trace->integral[ind + 1] -
+ trace->integral[ind]) /
+ (trace->time_points[ind + 1] -
+ trace->time_points[ind]));
+
+ return time;
}
/**
-* \brief This function calcules the exactly time needed to compute amount flops. It uses directly the tmgr_trace_t structure.
-* It works only if the two points are in the same timestep.
-* \param trace Trace structure
-* \param index Index of timestep where the points are located
-* \param a Start time
-* \param amount Total amount
-* \return number of seconds needed to compute amount flops
+ * \brief Binary search in array.
+ * It returns the first point of the interval in which "a" is.
+ * \param array Array
+ * \param a Value to search
+ * \param low Low bound to search in array
+ * \param high Upper bound to search in array
+ * \return Index of point
*/
-static double surf_cpu_solve_exactly(surf_cpu_ti_tgmr_t trace, int index,
- double a, double amount)
+static int surf_cpu_binary_search(double *array, double a, int low, int high)
{
- int tmgr_index;
- double remains;
- double time, tmgr_date;
- double slice_amount;
- s_tmgr_event_t elem;
-
-
- tmgr_index = trace->levels[0]->trace_index[index];
- tmgr_date = trace->levels[0]->trace_value[index];
- remains = amount;
- time = a;
-
- DEBUG6
- ("Start time: %lf Amount: %lf index %d tmgr_index %d tmgr_date %lf value %lf",
- a, amount, index, tmgr_index, tmgr_date,
- trace->levels[0]->values[index]);
- if (tmgr_index < 0)
- return amount / (trace->levels[0]->values[index]);
-
- while (a > tmgr_date) {
- /* too big timestep */
- if (tmgr_index >=
- xbt_dynar_length(trace->levels[0]->power_trace->event_list)) {
- return (amount) * (trace->levels[0]->values[index]);
- }
-
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
- &elem);
- tmgr_date += elem.delta;
- tmgr_index++;
- }
- /* sum first slice [a, tmgr_date[ */
- if (a < tmgr_date) {
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list,
- tmgr_index - 1, &elem);
- slice_amount = (tmgr_date - a) * elem.value;
- DEBUG5("slice amount %lf a %lf tmgr_date %lf elem_value %lf delta %lf",
- slice_amount, a, tmgr_date, elem.value, elem.delta);
- if (remains <= slice_amount) {
- return (remains / elem.value);
- }
-
- remains -= (tmgr_date - a) * elem.value;
- time = tmgr_date;
- }
-
- while (1) {
- xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
- &elem);
- slice_amount = elem.delta * elem.value;
- DEBUG5("slice amount %lf a %lf tmgr_date %lf elem_value %lf delta %lf",
- slice_amount, a, tmgr_date, elem.value, elem.delta);
- if (remains <= slice_amount) {
- time += remains / elem.value;
- break;
- }
- time += elem.delta;
- remains -= elem.delta * elem.value;
- tmgr_index++;
- }
-
- return time - a;
+ int mid = low + (high - low) / 2;
+ DEBUG5("a %lf low %d high %d mid %d value %lf", a, low, high, mid,
+ array[mid]);
+ /* a == array[mid] */
+ if (array[mid] == a)
+ return mid;
+ /* a is between mid and mid+1 */
+ if (array[mid] < a && array[mid + 1] > a)
+ return mid;
+
+ if (array[mid] < a)
+ return surf_cpu_binary_search(array, a, mid + 1, high);
+ else
+ return surf_cpu_binary_search(array, a, low, mid - 1);
}
-
-//////////// END INTEGRAL /////////////////
