From fd472f70823a1157acdca204f02accd97918dccc Mon Sep 17 00:00:00 2001 From: alegrand Date: Sat, 20 Nov 2004 00:17:49 +0000 Subject: [PATCH] CPU can be created and used even though failures are not handled yet. SURF is now a working mini SimGrid. You can have a look at testsuite/surf/maxmin_usage.c to see how easy it is to use. Adding other resource types is really straightforward. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@522 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- src/include/surf/surf.h | 46 +++++++++------ src/surf/cpu.c | 107 +++++++++++++++++++++++++++------- src/surf/cpu_private.h | 12 +++- src/surf/surf.c | 72 ++++++++++++++++++----- src/surf/surf_private.h | 5 +- testsuite/Makefile.am | 4 +- testsuite/surf/maxmin_bench.c | 90 ++++++++++++++++++++++++++++ testsuite/surf/maxmin_usage.c | 70 ++++++++++++++++------ 8 files changed, 331 insertions(+), 75 deletions(-) create mode 100644 testsuite/surf/maxmin_bench.c diff --git a/src/include/surf/surf.h b/src/include/surf/surf.h index 536a63e86a..af93cc5020 100644 --- a/src/include/surf/surf.h +++ b/src/include/surf/surf.h @@ -26,6 +26,13 @@ typedef enum { SURF_ACTION_NOT_IN_THE_SYSTEM /* Not in the system anymore. Why did you ask ? */ } e_surf_action_state_t; +typedef struct surf_action_state { + xbt_swag_t ready_action_set; + xbt_swag_t running_action_set; + xbt_swag_t failed_action_set; + xbt_swag_t done_action_set; +} s_surf_action_state_t, *surf_action_state_t; + /* Never create s_surf_action_t by yourself !!!! */ /* Use action_new from the corresponding resource */ typedef struct surf_action { @@ -44,15 +51,21 @@ typedef struct surf_action { /***************************/ /* Generic resource object */ /***************************/ + typedef struct surf_resource { - void (*parse_file)(const char *file); + s_surf_action_state_t states; /* Any living action on this resource */ + + /* Moved to the initialization function */ + /* void (*parse_file)(const char *filename); */ + void *(*name_service)(const char *name); const char *(*get_resource_name)(void *resource_id); + int (*resource_used)(void *resource_id); /* surf_action_t (*action_new)(void *callback); */ /* Not defined here. Actions have to be created by actually performing it and prototype may therefore vary with the resource - implementation */ + implementationx */ e_surf_action_state_t (*action_get_state)(surf_action_t action); void (*action_free)(surf_action_t * action); /* Call it when you're done with this action */ @@ -60,11 +73,12 @@ typedef struct surf_resource { void (*action_recycle)(surf_action_t action); /* More efficient than free/new */ void (*action_change_state)(surf_action_t action, e_surf_action_state_t state); - xbt_heap_float_t (*share_resources)(void); /* Share the resources to the - actions and return the potential - next action termination */ - void (*solve)(xbt_heap_float_t date); /* Advance time to "date" and update - the actions' state*/ + xbt_heap_float_t (*share_resources)(xbt_heap_float_t now); /* Share the resources to the + actions and return in hom much time + the next action may terminate */ + void (*update_state)(xbt_heap_float_t now, + xbt_heap_float_t delta); /* Update the actions' state*/ + } s_surf_resource_t; /**************************************/ @@ -82,6 +96,7 @@ typedef struct surf_cpu_resource { e_surf_cpu_state_t (*get_state)(void *cpu); } s_surf_cpu_resource_t, *surf_cpu_resource_t; extern surf_cpu_resource_t surf_cpu_resource; +void surf_cpu_resource_init(const char* filename); /* Network resource */ typedef struct surf_network_resource { @@ -89,6 +104,7 @@ typedef struct surf_network_resource { surf_action_t (*communicate)(void *src, void *dst, xbt_maxmin_float_t size); } s_surf_network_resource_t, surf_network_resource_t; extern surf_network_resource_t surf_network_resource; +void surf_network_resource_init(const char* filename); /* Timer resource */ typedef struct surf_timer_resource { @@ -96,20 +112,16 @@ typedef struct surf_timer_resource { surf_action_t (*wait)(void *cpu, void *dst, xbt_maxmin_float_t size); } s_surf_timer_resource_t, surf_timer_resource_t; extern surf_timer_resource_t surf_timer_resource; +void surf_timer_resource_init(const char* filename); /*******************************************/ /*** SURF Globals **************************/ /*******************************************/ -typedef struct surf_global { - xbt_swag_t ready_action_set; - xbt_swag_t running_action_set; - xbt_swag_t failed_action_set; - xbt_swag_t done_action_set; -} s_surf_global_t; -/* The main function */ -extern s_surf_global_t surf_global; -void surf_init(void); /* initialize all resource objects */ -xbt_heap_float_t surf_solve(void); /* returns the next date */ +void surf_init(void); /* initialize common structures */ +xbt_heap_float_t surf_solve(void); /* update all states and returns + the time elapsed since last + event */ +xbt_heap_float_t surf_get_clock(void); #endif /* _SURF_SURF_H */ diff --git a/src/surf/cpu.c b/src/surf/cpu.c index 3f4c5100e4..ab00d8bf2e 100644 --- a/src/surf/cpu.c +++ b/src/surf/cpu.c @@ -10,16 +10,6 @@ surf_cpu_resource_t surf_cpu_resource = NULL; static xbt_dict_t cpu_set = NULL; static lmm_system_t sys = NULL; -typedef struct cpu { - const char *name; - xbt_maxmin_float_t power_scale; - xbt_maxmin_float_t current_power; - tmgr_trace_t power_trace; - e_surf_action_state_t current_state; - tmgr_trace_t state_trace; - lmm_constraint_t constraint; -} s_cpu_t, *cpu_t; - /* power_scale is the basic power of the cpu when the cpu is completely available. initial_power is therefore expected to be comprised between 0.0 and 1.0, just as the values of power_trace. @@ -39,7 +29,7 @@ static void *new_cpu(const char *name, xbt_maxmin_float_t power_scale, cpu->power_trace = power_trace; cpu->current_state = initial_state; cpu->state_trace = state_trace; - cpu->constraint = lmm_constraint_new(sys, cpu, cpu->current_power); + cpu->constraint = lmm_constraint_new(sys, cpu, cpu->current_power * cpu->power_scale); xbt_dict_set(cpu_set, name, cpu, NULL); @@ -48,8 +38,8 @@ static void *new_cpu(const char *name, xbt_maxmin_float_t power_scale, static void parse_file(const char *file) { - new_cpu("Cpu A", 200.0, 1.0, NULL, SURF_CPU_ON, NULL); - new_cpu("Cpu B", 100.0, 1.0, NULL, SURF_CPU_ON, NULL); + new_cpu("Cpu A", 20.0, 1.0, NULL, SURF_CPU_ON, NULL); + new_cpu("Cpu B", 120.0, 1.0, NULL, SURF_CPU_ON, NULL); } static void *name_service(const char *name) @@ -66,6 +56,11 @@ static const char *get_resource_name(void *resource_id) return ((cpu_t) resource_id)->name; } +static int resource_used(void *resource_id) +{ + return lmm_constraint_used(sys, ((cpu_t)resource_id)->constraint); +} + static surf_action_t action_new(void *callback) { return NULL; @@ -97,19 +92,69 @@ static void action_change_state(surf_action_t action, e_surf_action_state_t stat return; } -static xbt_heap_float_t share_resources(void) +static xbt_heap_float_t share_resources() { - return -1.0; + surf_action_cpu_t action = NULL; + xbt_swag_t running_actions= surf_cpu_resource->resource.states.running_action_set; + xbt_maxmin_float_t min = -1; + xbt_maxmin_float_t value = -1; + lmm_solve(sys); + + action = xbt_swag_getFirst(running_actions); + if(!action) return 0.0; + value = lmm_variable_getvalue(action->variable); + min = action->generic_action.remains / value ; + + xbt_swag_foreach(action,running_actions) { + /* If everything is stable... */ + value = action->generic_action.remains / + lmm_variable_getvalue(action->variable); + if(valueresource.states.running_action_set; + + xbt_swag_foreach_safe(action, next_action, running_actions) { + action->generic_action.remains -= + lmm_variable_getvalue(action->variable)*delta; +/* if(action->generic_action.remains<.00001) action->generic_action.remains=0; */ + if(action->generic_action.remains<=0) { + action_change_state((surf_action_t)action, SURF_ACTION_DONE); + } /* else if(host_failed..) */ + } + return; } static surf_action_t execute(void *cpu, xbt_maxmin_float_t size) { - return NULL; + lmm_variable_t var; + surf_action_cpu_t action = NULL; + + action=xbt_new0(s_surf_action_cpu_t,1); + + action->generic_action.cost=size; + action->generic_action.remains=size; + action->generic_action.start=-1.0; + action->generic_action.finish=-1.0; + action->generic_action.callback=cpu; + action->generic_action.resource_type=(surf_resource_t)surf_cpu_resource; + + action->generic_action.state_set=surf_cpu_resource->resource.states.running_action_set; + xbt_swag_insert(action,action->generic_action.state_set); + + action->variable = lmm_variable_new(sys, action, 1.0, -1.0, 1); + lmm_expand(sys, ((cpu_t)cpu)->constraint, action->variable, 1.0); + + return (surf_action_t) action; } static e_surf_cpu_state_t get_state(void *cpu) @@ -117,21 +162,31 @@ static e_surf_cpu_state_t get_state(void *cpu) return SURF_CPU_OFF; } - -surf_cpu_resource_t surf_cpu_resource_init(void) +static surf_cpu_resource_t surf_cpu_resource_init_internal(void) { + s_surf_action_t action; + surf_cpu_resource = xbt_new0(s_surf_cpu_resource_t,1); - surf_cpu_resource->resource.parse_file = parse_file; + surf_cpu_resource->resource.states.ready_action_set= + xbt_swag_new(xbt_swag_offset(action,state_hookup)); + surf_cpu_resource->resource.states.running_action_set= + xbt_swag_new(xbt_swag_offset(action,state_hookup)); + surf_cpu_resource->resource.states.failed_action_set= + xbt_swag_new(xbt_swag_offset(action,state_hookup)); + surf_cpu_resource->resource.states.done_action_set= + xbt_swag_new(xbt_swag_offset(action,state_hookup)); + surf_cpu_resource->resource.name_service = name_service; surf_cpu_resource->resource.get_resource_name = get_resource_name; + surf_cpu_resource->resource.resource_used = resource_used; surf_cpu_resource->resource.action_get_state=surf_action_get_state; surf_cpu_resource->resource.action_free = action_free; surf_cpu_resource->resource.action_cancel = action_cancel; surf_cpu_resource->resource.action_recycle = action_recycle; surf_cpu_resource->resource.action_change_state = action_change_state; surf_cpu_resource->resource.share_resources = share_resources; - surf_cpu_resource->resource.solve = solve; + surf_cpu_resource->resource.update_state = update_state; surf_cpu_resource->execute = execute; surf_cpu_resource->get_state = get_state; @@ -142,3 +197,13 @@ surf_cpu_resource_t surf_cpu_resource_init(void) return surf_cpu_resource; } + +void surf_cpu_resource_init(const char* filename) +{ + surf_resource_t CPU = NULL; + + surf_cpu_resource=surf_cpu_resource_init_internal(); + parse_file(filename); + CPU = &(surf_cpu_resource->resource); /* to make short */ + xbt_dynar_push(resource_list, &CPU); +} diff --git a/src/surf/cpu_private.h b/src/surf/cpu_private.h index 7315b42630..d802ccbf34 100644 --- a/src/surf/cpu_private.h +++ b/src/surf/cpu_private.h @@ -6,7 +6,6 @@ #ifndef _SURF_CPU_PRIVATE_H #define _SURF_CPU_PRIVATE_H -#include "surf/surf.h" #include "surf/surf_private.h" typedef struct surf_action_cpu { @@ -14,6 +13,15 @@ typedef struct surf_action_cpu { lmm_variable_t variable; } s_surf_action_cpu_t, *surf_action_cpu_t; -surf_cpu_resource_t surf_cpu_resource_init(void); +typedef struct cpu { + const char *name; + xbt_maxmin_float_t power_scale; + xbt_maxmin_float_t current_power; + tmgr_trace_t power_trace; + e_surf_action_state_t current_state; + tmgr_trace_t state_trace; + lmm_constraint_t constraint; +} s_cpu_t, *cpu_t; + #endif /* _SURF_SURF_PRIVATE_H */ diff --git a/src/surf/surf.c b/src/surf/surf.c index 8783348814..ecc3e9e770 100644 --- a/src/surf/surf.c +++ b/src/surf/surf.c @@ -4,19 +4,24 @@ under the terms of the license (GNU LGPL) which comes with this package. */ #include "surf_private.h" -#include "cpu_private.h" -s_surf_global_t surf_global; +static xbt_heap_float_t NOW=0; + +xbt_dynar_t resource_list = NULL; +tmgr_history_t history = NULL; +lmm_system_t maxmin_system = NULL; e_surf_action_state_t surf_action_get_state(surf_action_t action) { - if(action->state_set == surf_global.ready_action_set) + surf_action_state_t action_state = &(action->resource_type->states); + + if(action->state_set == action_state->ready_action_set) return SURF_ACTION_READY; - if(action->state_set == surf_global.running_action_set) + if(action->state_set == action_state->running_action_set) return SURF_ACTION_RUNNING; - if(action->state_set == surf_global.failed_action_set) + if(action->state_set == action_state->failed_action_set) return SURF_ACTION_FAILED; - if(action->state_set == surf_global.done_action_set) + if(action->state_set == action_state->done_action_set) return SURF_ACTION_DONE; return SURF_ACTION_NOT_IN_THE_SYSTEM; } @@ -30,15 +35,18 @@ void surf_action_free(surf_action_t * action) void surf_action_change_state(surf_action_t action, e_surf_action_state_t state) { + surf_action_state_t action_state = &(action->resource_type->states); + xbt_swag_extract(action, action->state_set); + if(state == SURF_ACTION_READY) - action->state_set = surf_global.ready_action_set; + action->state_set = action_state->ready_action_set; else if(state == SURF_ACTION_RUNNING) - action->state_set = surf_global.running_action_set; + action->state_set = action_state->running_action_set; else if(state == SURF_ACTION_FAILED) - action->state_set = surf_global.failed_action_set; + action->state_set = action_state->failed_action_set; else if(state == SURF_ACTION_DONE) - action->state_set = surf_global.done_action_set; + action->state_set = action_state->done_action_set; else action->state_set = NULL; if(action->state_set) xbt_swag_insert(action, action->state_set); @@ -46,10 +54,46 @@ void surf_action_change_state(surf_action_t action, e_surf_action_state_t state) void surf_init(void) { - surf_cpu_resource = surf_cpu_resource_init(); + if(!resource_list) resource_list = xbt_dynar_new(sizeof(surf_resource_t), NULL); + if(!history) history = tmgr_history_new(); + if(!maxmin_system) maxmin_system = lmm_system_new(); } -/* xbt_heap_float_t surf_solve(void) */ -/* { */ -/* } */ +xbt_heap_float_t surf_solve(void) +{ + xbt_heap_float_t min = -1.0; + xbt_heap_float_t next_event_date = -1.0; + xbt_heap_float_t resource_next_action_end = -1.0; + xbt_maxmin_float_t value = -1.0; + surf_resource_t resource = NULL; + int i; + + xbt_dynar_foreach (resource_list,i,resource) { + resource_next_action_end = resource->share_resources(NOW); + if((min<0) || (resource_next_action_end NOW+min) break; + while (tmgr_history_get_next_event_leq(history, next_event_date, + &value, (void **) &resource)) { + if(surf_cpu_resource->resource.resource_used(resource)) { + min = next_event_date-NOW; + } + } + } + xbt_dynar_foreach (resource_list,i,resource) { + resource->update_state(NOW, min); + } + + NOW=NOW+min; + + return min; +} + +xbt_heap_float_t surf_get_clock(void) +{ + return NOW; +} diff --git a/src/surf/surf_private.h b/src/surf/surf_private.h index 3be6b80779..47923e0e93 100644 --- a/src/surf/surf_private.h +++ b/src/surf/surf_private.h @@ -9,13 +9,14 @@ #include "surf/surf.h" #include "surf/maxmin.h" #include "surf/trace_mgr.h" -#include "cpu_private.h" /* Generic functions common to all ressources */ e_surf_action_state_t surf_action_get_state(surf_action_t action); void surf_action_free(surf_action_t * action); void surf_action_change_state(surf_action_t action, e_surf_action_state_t state); - +extern xbt_dynar_t resource_list; +extern lmm_system_t maxmin_system; +extern tmgr_history_t history; #endif /* _SURF_SURF_PRIVATE_H */ diff --git a/testsuite/Makefile.am b/testsuite/Makefile.am index e49653fc1f..f03368e88d 100644 --- a/testsuite/Makefile.am +++ b/testsuite/Makefile.am @@ -29,7 +29,8 @@ RL_tests = \ gras/datadesc_usage SG_tests = \ - surf/maxmin_usage surf/trace_usage surf/surf_usage + surf/maxmin_usage surf/maxmin_bench \ + surf/trace_usage surf/surf_usage check_PROGRAMS = $(xbt_tests) $(RL_tests) $(SG_tests) check_SCRIPTS = run_tests gras/trp_tcp_usage @@ -62,6 +63,7 @@ xbt_config_usage_LDADD= $(LDADD_UTILS) xbt_heap_bench_LDADD= $(LDADD_UTILS) surf_maxmin_usage_LDADD= $(LDADD_UTILS) +surf_maxmin_bench_LDADD= $(LDADD_UTILS) surf_trace_usage_LDADD= $(LDADD_UTILS) surf_surf_usage_LDADD= $(LDADD_UTILS) diff --git a/testsuite/surf/maxmin_bench.c b/testsuite/surf/maxmin_bench.c new file mode 100644 index 0000000000..ca70060936 --- /dev/null +++ b/testsuite/surf/maxmin_bench.c @@ -0,0 +1,90 @@ +/* A crash few tests for the maxmin library */ + +/* Authors: Arnaud Legrand */ + +/* 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 +#include +#include "surf/maxmin.h" +#include + +long date; + +/* Pour le bench */ +long us_time(void); +long us_time(void) +{ + struct timeval start; + gettimeofday(&start, NULL); + + return (start.tv_sec * 1000000 + start.tv_usec); +} + + +xbt_maxmin_float_t float_random(xbt_maxmin_float_t max); +xbt_maxmin_float_t float_random(xbt_maxmin_float_t max) +{ + return ((max * rand()) / (RAND_MAX + 1.0)); +} + +int int_random(int max); +int int_random(int max) +{ + return (int) (((max * 1.0) * rand()) / (RAND_MAX + 1.0)); +} + +void test(int nb_cnst, int nb_var, int nb_elem); +void test(int nb_cnst, int nb_var, int nb_elem) +{ + lmm_system_t Sys = NULL; + lmm_constraint_t *cnst = calloc(nb_cnst, sizeof(lmm_constraint_t)); + lmm_variable_t *var = calloc(nb_var, sizeof(lmm_variable_t)); + int *used = calloc(nb_cnst, sizeof(int)); + int i, j, k; + + Sys = lmm_system_new(); + + for (i = 0; i < nb_cnst; i++) { + cnst[i] = lmm_constraint_new(Sys, NULL, float_random(10.0)); + } + + for (i = 0; i < nb_var; i++) { + var[i] = lmm_variable_new(Sys, NULL, 1.0, -1.0, nb_elem); + for (j = 0; j < nb_cnst; j++) + used[j] = 0; + for (j = 0; j < nb_elem; j++) { + k = int_random(nb_cnst); + if (used[k]) { + j--; + continue; + } + lmm_expand(Sys, cnst[k], var[i], float_random(1.0)); + used[k] = 1; + } + } + + date = us_time(); + lmm_solve(Sys); + date = us_time() - date; + + lmm_system_free(Sys); + free(cnst); + free(var); + free(used); +} + + +int main(int argc, char **argv) +{ + int nb_cnst = 2000; + int nb_var = 2000; + int nb_elem = 20; + date = us_time(); + test(nb_cnst, nb_var, nb_elem); + printf("One shot execution time for a total of %d constraints, " + "%d variables with %d active constraint each : %ld microsecondes \n", + nb_cnst, nb_var, nb_elem, date); + return 0; +} diff --git a/testsuite/surf/maxmin_usage.c b/testsuite/surf/maxmin_usage.c index d5c267f73e..1937a6b0ac 100644 --- a/testsuite/surf/maxmin_usage.c +++ b/testsuite/surf/maxmin_usage.c @@ -9,12 +9,17 @@ #include #include "surf/maxmin.h" +#define PRINT_VAR(var) printf(#var " = %Lg\n",lmm_variable_getvalue(var)); + /* */ /* ______ */ /* ==l1== L2 ==L3== */ /* ------ */ /* */ +void test(void); +void test(void) +{ lmm_system_t Sys = NULL ; lmm_constraint_t L1 = NULL; lmm_constraint_t L2 = NULL; @@ -25,10 +30,6 @@ lmm_variable_t R_2 = NULL; lmm_variable_t R_3 = NULL; -void test(void); -void test(void) -{ - Sys = lmm_system_new(); L1 = lmm_constraint_new(Sys, (void *) "L1", 1.0); L2 = lmm_constraint_new(Sys, (void *) "L2", 10.0); @@ -49,30 +50,62 @@ void test(void) lmm_expand(Sys, L3, R_3, 1.0); -#define AFFICHE(var) printf(#var " = %Lg\n",lmm_variable_getvalue(var)); - AFFICHE(R_1_2_3); - AFFICHE(R_1); - AFFICHE(R_2); - AFFICHE(R_3); + PRINT_VAR(R_1_2_3); + PRINT_VAR(R_1); + PRINT_VAR(R_2); + PRINT_VAR(R_3); printf("\n"); lmm_solve(Sys); - AFFICHE(R_1_2_3); - AFFICHE(R_1); - AFFICHE(R_2); - AFFICHE(R_3); + PRINT_VAR(R_1_2_3); + PRINT_VAR(R_1); + PRINT_VAR(R_2); + PRINT_VAR(R_3); printf("\n"); lmm_update_variable_weight(R_1_2_3,.5); lmm_solve(Sys); - AFFICHE(R_1_2_3); - AFFICHE(R_1); - AFFICHE(R_2); - AFFICHE(R_3); -#undef AFFICHE + PRINT_VAR(R_1_2_3); + PRINT_VAR(R_1); + PRINT_VAR(R_2); + PRINT_VAR(R_3); + + lmm_system_free(Sys); +} + +void test2(void); +void test2(void) +{ + lmm_system_t Sys = NULL ; + lmm_constraint_t CPU1 = NULL; + lmm_constraint_t CPU2 = NULL; + + lmm_variable_t T1 = NULL; + lmm_variable_t T2 = NULL; + + Sys = lmm_system_new(); + CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0); + CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0); + + T1 = lmm_variable_new(Sys, (void *) "T1", 1.0 , -1.0 , 1); + T2 = lmm_variable_new(Sys, (void *) "T2", 1.0 , -1.0 , 1); + + lmm_expand(Sys, CPU1, T1, 1.0); + lmm_expand(Sys, CPU2, T2, 1.0); + + PRINT_VAR(T1); + PRINT_VAR(T2); + + printf("\n"); + lmm_solve(Sys); + + PRINT_VAR(T1); + PRINT_VAR(T2); + + printf("\n"); lmm_system_free(Sys); } @@ -81,5 +114,6 @@ void test(void) int main(int argc, char **argv) { test(); + test2(); return 0; } -- 2.20.1