1 /* simple test to schedule a DAX file with the Min-Min algorithm. */
3 /* Copyright (c) 2009, 2010. The SimGrid Team.
4 * All rights reserved. */
6 /* This program is free software; you can redistribute it and/or modify it
7 * under the terms of the license (GNU LGPL) which comes with this package. */
11 #include "simdag/simdag.h"
16 XBT_LOG_NEW_DEFAULT_CATEGORY(test,
17 "Logging specific to this SimDag example");
19 typedef struct _WorkstationAttribute *WorkstationAttribute;
20 struct _WorkstationAttribute {
21 /* Earliest time at wich a workstation is ready to execute a task*/
25 static void SD_workstation_allocate_attribute(SD_workstation_t workstation){
27 data = calloc(1,sizeof(struct _WorkstationAttribute));
28 SD_workstation_set_data(workstation, data);
31 static void SD_workstation_free_attribute(SD_workstation_t workstation){
32 free(SD_workstation_get_data(workstation));
33 SD_workstation_set_data(workstation, NULL);
36 static double SD_workstation_get_available_at( SD_workstation_t workstation){
37 WorkstationAttribute attr =
38 (WorkstationAttribute) SD_workstation_get_data(workstation);
39 return attr->available_at;
42 static void SD_workstation_set_available_at(SD_workstation_t workstation,
44 WorkstationAttribute attr =
45 (WorkstationAttribute) SD_workstation_get_data(workstation);
46 attr->available_at=time;
47 SD_workstation_set_data(workstation, attr);
51 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax){
53 xbt_dynar_t ready_tasks;
56 ready_tasks= xbt_dynar_new(sizeof(SD_task_t), NULL);
57 xbt_dynar_foreach(dax, i, task){
58 if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ &&
59 SD_task_get_state(task) == SD_SCHEDULABLE){
60 xbt_dynar_push(ready_tasks, &task);
63 DEBUG1("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
68 static double finish_on_at(SD_task_t task, SD_workstation_t workstation){
70 double data_available=0.;
72 double last_data_available;
73 SD_task_t parent,grand_parent;
74 xbt_dynar_t parents, grand_parents;
76 int grand_parent_nworkstations;
77 SD_workstation_t *grand_parent_workstation_list;
79 parents = SD_task_get_parents(task);
81 if (xbt_dynar_length(parents)) {
82 /* compute last_data_available */
83 last_data_available=-1.0;
84 xbt_dynar_foreach(parents, i, parent){
87 if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
88 grand_parents = SD_task_get_parents(parent);
90 if (xbt_dynar_length(grand_parents) > 1) {
91 ERROR1("Warning: transfer %s has 2 parents",
92 SD_task_get_name(parent));
94 xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
96 grand_parent_nworkstations =
97 SD_task_get_workstation_count(grand_parent);
98 grand_parent_workstation_list =
99 SD_task_get_workstation_list(grand_parent);
100 /* Estimate the redistribution time from this parent */
102 SD_route_get_communication_time(grand_parent_workstation_list[0],
104 SD_task_get_amount(parent));
106 SD_task_get_finish_time(grand_parent) + redist_time;
108 xbt_dynar_free_container(&grand_parents);
111 /* no transfer, control dependency */
112 if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
113 data_available = SD_task_get_finish_time(parent);
116 if (last_data_available < data_available)
117 last_data_available = data_available;
121 xbt_dynar_free_container(&parents);
123 return MAX(SD_workstation_get_available_at(workstation),
124 last_data_available) +
125 SD_workstation_get_computation_time(workstation,
126 SD_task_get_amount(task));
128 xbt_dynar_free_container(&parents);
130 return SD_workstation_get_available_at(workstation)+
131 SD_workstation_get_computation_time(workstation,
132 SD_task_get_amount(task));
136 static SD_workstation_t SD_task_get_best_workstation (SD_task_t task){
138 double EFT, min_EFT=-1.0;
139 const SD_workstation_t *workstations = SD_workstation_get_list ();
140 int nworkstations = SD_workstation_get_number ();
141 SD_workstation_t best_workstation;
143 best_workstation = workstations[0];
144 min_EFT = finish_on_at(task, workstations[0]);
146 for (i=1; i<nworkstations;i++){
147 EFT = finish_on_at(task, workstations[i]);
148 DEBUG3("%s finishes on %s at %f",
149 SD_task_get_name(task),
150 SD_workstation_get_name(workstations[i]),
155 best_workstation = workstations[i];
159 return best_workstation;
162 static void output_xml(FILE *out, xbt_dynar_t dax){
164 int current_nworkstations;
165 const int nworkstations = SD_workstation_get_number();
166 const SD_workstation_t * workstations = SD_workstation_get_list();
168 SD_workstation_t * list;
170 fprintf(out,"<?xml version=\"1.0\"?>\n");
171 fprintf(out,"<grid_schedule>\n");
172 fprintf(out," <grid_info>\n");
173 fprintf(out," <info name=\"nb_clusters\" value=\"1\"/>\n");
174 fprintf(out," <clusters>\n");
175 fprintf(out," <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
177 fprintf(out," </clusters>\n");
178 fprintf(out," </grid_info>\n");
179 fprintf(out," <node_infos>\n");
181 xbt_dynar_foreach(dax, i, task){
182 fprintf(out," <node_statistics>\n");
183 fprintf(out," <node_property name=\"id\" value=\"%s\"/>\n",
184 SD_task_get_name(task));
185 fprintf(out," <node_property name=\"type\" value=\"");
186 if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
187 fprintf(out,"computation\"/>\n");
188 if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
189 fprintf(out,"transfer\"/>\n");
191 fprintf(out," <node_property name=\"start_time\" value=\"%.3f\"/>\n",
192 SD_task_get_start_time(task));
193 fprintf(out," <node_property name=\"end_time\" value=\"%.3f\"/>\n",
194 SD_task_get_finish_time(task));
195 fprintf(out," <configuration>\n");
197 current_nworkstations = SD_task_get_workstation_count(task);
199 fprintf(out," <conf_property name=\"host_nb\" value=\"%d\"/>\n",
200 current_nworkstations);
202 fprintf(out," <host_lists>\n");
203 list = SD_task_get_workstation_list(task);
204 for (j=0;j<current_nworkstations;j++){
205 for (k=0;k<nworkstations;k++){
206 if (!strcmp(SD_workstation_get_name(workstations[k]),
207 SD_workstation_get_name(list[j]))){
208 fprintf(out," <hosts start=\"%u\" nb=\"1\"/>\n",k);
210 " <conf_property name=\"cluster_id\" value=\"0\"/>\n");
215 fprintf(out," </host_lists>\n");
216 fprintf(out," </configuration>\n");
217 fprintf(out," </node_statistics>\n");
219 fprintf(out," </node_infos>\n");
220 fprintf(out,"</grid_schedule>\n");
223 int main(int argc, char **argv) {
224 unsigned int cursor, selected_idx=0;
225 double finish_time, min_finish_time = -1.0;
226 SD_task_t task, selected_task=NULL;
227 xbt_dynar_t ready_tasks;
228 SD_workstation_t workstation, selected_workstation=NULL;
229 int total_nworkstations=0;
230 const SD_workstation_t *workstations=NULL;
231 xbt_dynar_t dax, changed;
234 /* initialization of SD */
235 SD_init(&argc, argv);
237 /* Check our arguments */
239 INFO1("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
240 INFO1("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
246 char *last=strrchr(argv[2],'.');
248 tracefilename=bprintf("%.*s.jed",
249 (int)(last==NULL?strlen(argv[2]):last-argv[2]),
252 tracefilename = xbt_strdup(argv[3]);
255 /* creation of the environment */
256 SD_create_environment(argv[1]);
258 /* Allocating the workstation attribute */
259 total_nworkstations = SD_workstation_get_number();
260 workstations = SD_workstation_get_list();
262 for(cursor=0; cursor<total_nworkstations; cursor++)
263 SD_workstation_allocate_attribute(workstations[cursor]);
266 /* load the DAX file */
267 dax=SD_daxload(argv[2]);
269 xbt_dynar_foreach(dax,cursor,task) {
270 SD_task_watch(task,SD_DONE);
273 /* Schedule the root first */
274 xbt_dynar_get_cpy(dax, 0, &task);
275 workstation = SD_task_get_best_workstation(task);
276 SD_task_schedulel(task, 1, workstation);
278 while(!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))){
279 /* Get the set of ready tasks */
280 ready_tasks= get_ready_tasks(dax);
281 if (!xbt_dynar_length(ready_tasks)) {
282 xbt_dynar_free_container(&ready_tasks);
283 xbt_dynar_free_container(&changed);
284 /* there is no ready task, let advance the simulation */
287 /* For each ready task:
288 * get the workstation that minimizes the completion time.
289 * select the task that has the minimum completion time on
290 * its best workstation.
292 xbt_dynar_foreach(ready_tasks, cursor, task){
293 DEBUG1("%s is ready", SD_task_get_name(task));
294 workstation = SD_task_get_best_workstation(task);
295 finish_time = finish_on_at(task, workstation);
296 if (min_finish_time == -1. || finish_time < min_finish_time) {
297 min_finish_time = finish_time;
298 selected_task = task;
299 selected_workstation = workstation;
300 selected_idx = cursor;
304 INFO2("Schedule %s on %s", SD_task_get_name(selected_task),
305 SD_workstation_get_name(selected_workstation));
307 SD_task_schedulel(selected_task, 1, selected_workstation);
308 SD_workstation_set_available_at(selected_workstation,
311 xbt_dynar_free_container(&ready_tasks);
312 /* reset the min_finish_time for the next set of ready tasks */
313 min_finish_time = -1.;
314 xbt_dynar_free_container(&changed);
317 INFO1("Simulation Time: %f", SD_get_clock());
322 INFO0("------------------- Produce the trace file---------------------------");
323 INFO1("Producing the trace of the run into %s",tracefilename);
324 out = fopen(tracefilename,"w");
325 xbt_assert1(out,"Cannot write to %s",tracefilename);
328 output_xml(out, dax);
333 xbt_dynar_free_container(&ready_tasks);
334 xbt_dynar_free_container(&changed);
336 xbt_dynar_foreach(dax,cursor,task) {
337 SD_task_destroy(task);
340 for(cursor=0; cursor<total_nworkstations; cursor++)
341 SD_workstation_free_attribute(workstations[cursor]);