typedef struct _WorkstationAttribute *WorkstationAttribute;
struct _WorkstationAttribute {
- /* Earliest time at wich a workstation is ready to execute a task*/
- double available_at;
+ /* Earliest time at wich a workstation is ready to execute a task */
+ double available_at;
+ SD_task_t last_scheduled_task;
};
-static void SD_workstation_allocate_attribute(SD_workstation_t workstation){
- void *data;
- data = calloc(1,sizeof(struct _WorkstationAttribute));
- SD_workstation_set_data(workstation, data);
+static void SD_workstation_allocate_attribute(SD_workstation_t workstation)
+{
+ void *data;
+ data = calloc(1, sizeof(struct _WorkstationAttribute));
+ SD_workstation_set_data(workstation, data);
}
-static void SD_workstation_free_attribute(SD_workstation_t workstation){
- free(SD_workstation_get_data(workstation));
- SD_workstation_set_data(workstation, NULL);
+static void SD_workstation_free_attribute(SD_workstation_t workstation)
+{
+ free(SD_workstation_get_data(workstation));
+ SD_workstation_set_data(workstation, NULL);
}
-static double SD_workstation_get_available_at( SD_workstation_t workstation){
+static double SD_workstation_get_available_at(SD_workstation_t workstation)
+{
+ WorkstationAttribute attr =
+ (WorkstationAttribute) SD_workstation_get_data(workstation);
+ return attr->available_at;
+}
+
+static void SD_workstation_set_available_at(SD_workstation_t workstation,
+ double time)
+{
+ WorkstationAttribute attr =
+ (WorkstationAttribute) SD_workstation_get_data(workstation);
+ attr->available_at = time;
+ SD_workstation_set_data(workstation, attr);
+}
+
+static SD_task_t SD_workstation_get_last_scheduled_task( SD_workstation_t workstation){
WorkstationAttribute attr =
(WorkstationAttribute) SD_workstation_get_data(workstation);
- return attr->available_at;
+ return attr->last_scheduled_task;
}
-static void SD_workstation_set_available_at(SD_workstation_t workstation,
- double time){
+static void SD_workstation_set_last_scheduled_task(SD_workstation_t workstation,
+ SD_task_t task){
WorkstationAttribute attr =
(WorkstationAttribute) SD_workstation_get_data(workstation);
- attr->available_at=time;
+ attr->last_scheduled_task=task;
SD_workstation_set_data(workstation, attr);
}
-
-static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax){
+static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
+{
unsigned int i;
xbt_dynar_t ready_tasks;
SD_task_t task;
- ready_tasks= xbt_dynar_new(sizeof(SD_task_t), NULL);
- xbt_dynar_foreach(dax, i, task){
+ ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
+ xbt_dynar_foreach(dax, i, task) {
if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ &&
- SD_task_get_state(task) == SD_SCHEDULABLE){
+ SD_task_get_state(task) == SD_SCHEDULABLE) {
xbt_dynar_push(ready_tasks, &task);
}
}
- DEBUG1("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
-
+ XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
+
return ready_tasks;
}
-static double finish_on_at(SD_task_t task, SD_workstation_t workstation){
+static double finish_on_at(SD_task_t task, SD_workstation_t workstation)
+{
+ volatile double result;
unsigned int i;
- double data_available=0.;
- double redist_time=0;
+ double data_available = 0.;
+ double redist_time = 0;
double last_data_available;
- SD_task_t parent,grand_parent;
+ SD_task_t parent, grand_parent;
xbt_dynar_t parents, grand_parents;
-
- int grand_parent_nworkstations;
+
SD_workstation_t *grand_parent_workstation_list;
-
+
parents = SD_task_get_parents(task);
-
- if (xbt_dynar_length(parents)) {
+
+ if (!xbt_dynar_is_empty(parents)) {
/* compute last_data_available */
- last_data_available=-1.0;
- xbt_dynar_foreach(parents, i, parent){
-
+ last_data_available = -1.0;
+ xbt_dynar_foreach(parents, i, parent) {
+
/* normal case */
if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
- grand_parents = SD_task_get_parents(parent);
-
- if (xbt_dynar_length(grand_parents) > 1) {
- ERROR1("Warning: transfer %s has 2 parents",
- SD_task_get_name(parent));
- }
- xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
-
- grand_parent_nworkstations =
- SD_task_get_workstation_count(grand_parent);
- grand_parent_workstation_list =
- SD_task_get_workstation_list(grand_parent);
- /* Estimate the redistribution time from this parent */
- redist_time =
- SD_route_get_communication_time(grand_parent_workstation_list[0],
- workstation,
- SD_task_get_amount(parent));
- data_available =
- SD_task_get_finish_time(grand_parent) + redist_time;
-
- xbt_dynar_free_container(&grand_parents);
+ grand_parents = SD_task_get_parents(parent);
+
+ if (xbt_dynar_length(grand_parents) > 1) {
+ XBT_ERROR("Warning: transfer %s has 2 parents",
+ SD_task_get_name(parent));
+ }
+ xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
+
+ grand_parent_workstation_list =
+ SD_task_get_workstation_list(grand_parent);
+ /* Estimate the redistribution time from this parent */
+ redist_time =
+ SD_route_get_communication_time(grand_parent_workstation_list
+ [0], workstation,
+ SD_task_get_amount(parent));
+ data_available =
+ SD_task_get_finish_time(grand_parent) + redist_time;
+
+ xbt_dynar_free_container(&grand_parents);
}
-
+
/* no transfer, control dependency */
if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
- data_available = SD_task_get_finish_time(parent);
+ data_available = SD_task_get_finish_time(parent);
}
-
+
if (last_data_available < data_available)
- last_data_available = data_available;
-
+ last_data_available = data_available;
+
}
-
+
xbt_dynar_free_container(&parents);
-
- return MAX(SD_workstation_get_available_at(workstation),
- last_data_available) +
- SD_workstation_get_computation_time(workstation,
- SD_task_get_amount(task));
+
+ result = MAX(SD_workstation_get_available_at(workstation),
+ last_data_available) +
+ SD_workstation_get_computation_time(workstation,
+ SD_task_get_amount(task));
} else {
xbt_dynar_free_container(&parents);
-
- return SD_workstation_get_available_at(workstation)+
- SD_workstation_get_computation_time(workstation,
- SD_task_get_amount(task));
+
+ result = SD_workstation_get_available_at(workstation) +
+ SD_workstation_get_computation_time(workstation,
+ SD_task_get_amount(task));
}
+ return result;
}
-static SD_workstation_t SD_task_get_best_workstation (SD_task_t task){
+static SD_workstation_t SD_task_get_best_workstation(SD_task_t task)
+{
int i;
- double EFT, min_EFT=-1.0;
- const SD_workstation_t *workstations = SD_workstation_get_list ();
- int nworkstations = SD_workstation_get_number ();
+ double EFT, min_EFT = -1.0;
+ const SD_workstation_t *workstations = SD_workstation_get_list();
+ int nworkstations = SD_workstation_get_number();
SD_workstation_t best_workstation;
-
+
best_workstation = workstations[0];
min_EFT = finish_on_at(task, workstations[0]);
-
- for (i=1; i<nworkstations;i++){
+
+ for (i = 1; i < nworkstations; i++) {
EFT = finish_on_at(task, workstations[i]);
- DEBUG3("%s finishes on %s at %f",
- SD_task_get_name(task),
- SD_workstation_get_name(workstations[i]),
- EFT);
-
+ XBT_DEBUG("%s finishes on %s at %f",
+ SD_task_get_name(task),
+ SD_workstation_get_name(workstations[i]), EFT);
+
if (EFT < min_EFT) {
min_EFT = EFT;
best_workstation = workstations[i];
return best_workstation;
}
-static void output_xml(FILE *out, xbt_dynar_t dax){
- unsigned int i,j, k;
+static void output_xml(FILE * out, xbt_dynar_t dax)
+{
+ unsigned int i, j, k;
int current_nworkstations;
const int nworkstations = SD_workstation_get_number();
- const SD_workstation_t * workstations = SD_workstation_get_list();
+ const SD_workstation_t *workstations = SD_workstation_get_list();
SD_task_t task;
- SD_workstation_t * list;
-
- fprintf(out,"<?xml version=\"1.0\"?>\n");
- fprintf(out,"<grid_schedule>\n");
- fprintf(out," <grid_info>\n");
- fprintf(out," <info name=\"nb_clusters\" value=\"1\"/>\n");
- fprintf(out," <clusters>\n");
- fprintf(out," <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
- nworkstations);
- fprintf(out," </clusters>\n");
- fprintf(out," </grid_info>\n");
- fprintf(out," <node_infos>\n");
-
- xbt_dynar_foreach(dax, i, task){
- fprintf(out," <node_statistics>\n");
- fprintf(out," <node_property name=\"id\" value=\"%s\"/>\n",
- SD_task_get_name(task));
- fprintf(out," <node_property name=\"type\" value=\"");
+ SD_workstation_t *list;
+
+ fprintf(out, "<?xml version=\"1.0\"?>\n");
+ fprintf(out, "<grid_schedule>\n");
+ fprintf(out, " <grid_info>\n");
+ fprintf(out, " <info name=\"nb_clusters\" value=\"1\"/>\n");
+ fprintf(out, " <clusters>\n");
+ fprintf(out,
+ " <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
+ nworkstations);
+ fprintf(out, " </clusters>\n");
+ fprintf(out, " </grid_info>\n");
+ fprintf(out, " <node_infos>\n");
+
+ xbt_dynar_foreach(dax, i, task) {
+ fprintf(out, " <node_statistics>\n");
+ fprintf(out, " <node_property name=\"id\" value=\"%s\"/>\n",
+ SD_task_get_name(task));
+ fprintf(out, " <node_property name=\"type\" value=\"");
if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
- fprintf(out,"computation\"/>\n");
+ fprintf(out, "computation\"/>\n");
if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
- fprintf(out,"transfer\"/>\n");
-
- fprintf(out," <node_property name=\"start_time\" value=\"%.3f\"/>\n",
- SD_task_get_start_time(task));
- fprintf(out," <node_property name=\"end_time\" value=\"%.3f\"/>\n",
- SD_task_get_finish_time(task));
- fprintf(out," <configuration>\n");
-
+ fprintf(out, "transfer\"/>\n");
+
+ fprintf(out,
+ " <node_property name=\"start_time\" value=\"%.3f\"/>\n",
+ SD_task_get_start_time(task));
+ fprintf(out,
+ " <node_property name=\"end_time\" value=\"%.3f\"/>\n",
+ SD_task_get_finish_time(task));
+ fprintf(out, " <configuration>\n");
+
current_nworkstations = SD_task_get_workstation_count(task);
-
- fprintf(out," <conf_property name=\"host_nb\" value=\"%d\"/>\n",
- current_nworkstations);
-
- fprintf(out," <host_lists>\n");
+
+ fprintf(out,
+ " <conf_property name=\"host_nb\" value=\"%d\"/>\n",
+ current_nworkstations);
+
+ fprintf(out, " <host_lists>\n");
list = SD_task_get_workstation_list(task);
- for (j=0;j<current_nworkstations;j++){
- for (k=0;k<nworkstations;k++){
- if (!strcmp(SD_workstation_get_name(workstations[k]),
- SD_workstation_get_name(list[j]))){
- fprintf(out," <hosts start=\"%u\" nb=\"1\"/>\n",k);
- fprintf(out,
- " <conf_property name=\"cluster_id\" value=\"0\"/>\n");
- break;
- }
+ for (j = 0; j < current_nworkstations; j++) {
+ for (k = 0; k < nworkstations; k++) {
+ if (!strcmp(SD_workstation_get_name(workstations[k]),
+ SD_workstation_get_name(list[j]))) {
+ fprintf(out, " <hosts start=\"%u\" nb=\"1\"/>\n",
+ k);
+ fprintf(out,
+ " <conf_property name=\"cluster_id\" value=\"0\"/>\n");
+ break;
+ }
}
}
- fprintf(out," </host_lists>\n");
- fprintf(out," </configuration>\n");
- fprintf(out," </node_statistics>\n");
+ fprintf(out, " </host_lists>\n");
+ fprintf(out, " </configuration>\n");
+ fprintf(out, " </node_statistics>\n");
}
- fprintf(out," </node_infos>\n");
- fprintf(out,"</grid_schedule>\n");
+ fprintf(out, " </node_infos>\n");
+ fprintf(out, "</grid_schedule>\n");
}
-int main(int argc, char **argv) {
- unsigned int cursor, selected_idx=0;
+int main(int argc, char **argv)
+{
+ unsigned int cursor;
double finish_time, min_finish_time = -1.0;
- SD_task_t task, selected_task=NULL;
+ SD_task_t task, selected_task = NULL, last_scheduled_task;
xbt_dynar_t ready_tasks;
- SD_workstation_t workstation, selected_workstation=NULL;
- int total_nworkstations=0;
- const SD_workstation_t *workstations=NULL;
+ SD_workstation_t workstation, selected_workstation = NULL;
+ int total_nworkstations = 0;
+ const SD_workstation_t *workstations = NULL;
xbt_dynar_t dax, changed;
- FILE *out=NULL;
+ FILE *out = NULL;
/* initialization of SD */
SD_init(&argc, argv);
/* Check our arguments */
if (argc < 3) {
- INFO1("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
- INFO1("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
- argv[0]);
+ XBT_INFO("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
+ XBT_INFO
+ ("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
+ argv[0]);
exit(1);
}
char *tracefilename;
if (argc == 3) {
- char *last=strrchr(argv[2],'.');
+ char *last = strrchr(argv[2], '.');
- tracefilename=bprintf("%.*s.jed",
- (int)(last==NULL?strlen(argv[2]):last-argv[2]),
- argv[2]);
+ tracefilename = bprintf("%.*s.jed",
+ (int) (last ==
+ NULL ? strlen(argv[2]) : last -
+ argv[2]), argv[2]);
} else {
tracefilename = xbt_strdup(argv[3]);
}
/* Allocating the workstation attribute */
total_nworkstations = SD_workstation_get_number();
workstations = SD_workstation_get_list();
-
- for(cursor=0; cursor<total_nworkstations; cursor++)
+
+ for (cursor = 0; cursor < total_nworkstations; cursor++)
SD_workstation_allocate_attribute(workstations[cursor]);
-
+
/* load the DAX file */
- dax=SD_daxload(argv[2]);
+ dax = SD_daxload(argv[2]);
- xbt_dynar_foreach(dax,cursor,task) {
- SD_task_watch(task,SD_DONE);
+ xbt_dynar_foreach(dax, cursor, task) {
+ SD_task_watch(task, SD_DONE);
}
- /* Schedule the root first */
+ /* Schedule the root first */
xbt_dynar_get_cpy(dax, 0, &task);
- workstation = SD_task_get_best_workstation(task);
+ workstation = SD_task_get_best_workstation(task);
SD_task_schedulel(task, 1, workstation);
-
- while(!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))){
+
+ while (!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))) {
/* Get the set of ready tasks */
- ready_tasks= get_ready_tasks(dax);
- if (!xbt_dynar_length(ready_tasks)) {
+ ready_tasks = get_ready_tasks(dax);
+ if (xbt_dynar_is_empty(ready_tasks)) {
xbt_dynar_free_container(&ready_tasks);
xbt_dynar_free_container(&changed);
/* there is no ready task, let advance the simulation */
* select the task that has the minimum completion time on
* its best workstation.
*/
- xbt_dynar_foreach(ready_tasks, cursor, task){
- DEBUG1("%s is ready", SD_task_get_name(task));
- workstation = SD_task_get_best_workstation(task);
+ xbt_dynar_foreach(ready_tasks, cursor, task) {
+ XBT_DEBUG("%s is ready", SD_task_get_name(task));
+ workstation = SD_task_get_best_workstation(task);
finish_time = finish_on_at(task, workstation);
if (min_finish_time == -1. || finish_time < min_finish_time) {
- min_finish_time = finish_time;
- selected_task = task;
- selected_workstation = workstation;
- selected_idx = cursor;
+ min_finish_time = finish_time;
+ selected_task = task;
+ selected_workstation = workstation;
}
}
- INFO2("Schedule %s on %s", SD_task_get_name(selected_task),
- SD_workstation_get_name(selected_workstation));
+ XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
+ SD_workstation_get_name(selected_workstation));
SD_task_schedulel(selected_task, 1, selected_workstation);
- SD_workstation_set_available_at(selected_workstation,
- min_finish_time);
+
+ /*
+ * SimDag allows tasks to be executed concurrently when they can by default.
+ * Yet schedulers take decisions assuming that tasks wait for resource
+ * availability to start.
+ * The solution (well crude hack is to keep track of the last task scheduled
+ * on a workstation and add a special type of dependency if needed to
+ * force the sequential execution meant by the scheduler.
+ * If the last scheduled task is already done, has failed or is a
+ * predecessor of the current task, no need for a new dependency
+ */
+
+ last_scheduled_task =
+ SD_workstation_get_last_scheduled_task(selected_workstation);
+ if (last_scheduled_task &&
+ (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
+ (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
+ !SD_task_dependency_exists(
+ SD_workstation_get_last_scheduled_task(selected_workstation),
+ selected_task))
+ SD_task_dependency_add("resource", NULL,
+ last_scheduled_task, selected_task);
+ SD_workstation_set_last_scheduled_task(selected_workstation, selected_task);
+
+ SD_workstation_set_available_at(selected_workstation, min_finish_time);
+
xbt_dynar_free_container(&ready_tasks);
/* reset the min_finish_time for the next set of ready tasks */
min_finish_time = -1.;
xbt_dynar_free_container(&changed);
}
-
- INFO1("Simulation Time: %f", SD_get_clock());
-
+
+ XBT_INFO("Simulation Time: %f", SD_get_clock());
- INFO0("------------------- Produce the trace file---------------------------");
- INFO1("Producing the trace of the run into %s",tracefilename);
- out = fopen(tracefilename,"w");
- xbt_assert1(out,"Cannot write to %s",tracefilename);
+
+ XBT_INFO
+ ("------------------- Produce the trace file---------------------------");
+ XBT_INFO("Producing the trace of the run into %s", tracefilename);
+ out = fopen(tracefilename, "w");
+ xbt_assert(out, "Cannot write to %s", tracefilename);
free(tracefilename);
output_xml(out, dax);
xbt_dynar_free_container(&ready_tasks);
xbt_dynar_free_container(&changed);
- xbt_dynar_foreach(dax,cursor,task) {
+ xbt_dynar_foreach(dax, cursor, task) {
SD_task_destroy(task);
}
+ xbt_dynar_free_container(&dax);
- for(cursor=0; cursor<total_nworkstations; cursor++)
+ for (cursor = 0; cursor < total_nworkstations; cursor++)
SD_workstation_free_attribute(workstations[cursor]);
-
+
/* exit */
SD_exit();
return 0;
