1 /* Copyright (c) 2009-2016. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
7 /* simple test to schedule a DAX file with the Min-Min algorithm. */
11 #include "simgrid/simdag.h"
16 #include "simgrid/jedule/jedule_sd_binding.h"
19 XBT_LOG_NEW_DEFAULT_CATEGORY(test, "Logging specific to this SimDag example");
21 typedef struct _HostAttribute *HostAttribute;
22 struct _HostAttribute {
23 /* Earliest time at which a host is ready to execute a task */
25 SD_task_t last_scheduled_task;
28 static void sg_host_allocate_attribute(sg_host_t host)
31 data = calloc(1, sizeof(struct _HostAttribute));
32 sg_host_user_set(host, data);
35 static void sg_host_free_attribute(sg_host_t host)
37 free(sg_host_user(host));
38 sg_host_user_set(host, NULL);
41 static double sg_host_get_available_at(sg_host_t host)
43 HostAttribute attr = (HostAttribute) sg_host_user(host);
44 return attr->available_at;
47 static void sg_host_set_available_at(sg_host_t host, double time)
49 HostAttribute attr = (HostAttribute) sg_host_user(host);
50 attr->available_at = time;
51 sg_host_user_set(host, attr);
54 static SD_task_t sg_host_get_last_scheduled_task( sg_host_t host){
55 HostAttribute attr = (HostAttribute) sg_host_user(host);
56 return attr->last_scheduled_task;
59 static void sg_host_set_last_scheduled_task(sg_host_t host, SD_task_t task){
60 HostAttribute attr = (HostAttribute) sg_host_user(host);
61 attr->last_scheduled_task=task;
62 sg_host_user_set(host, attr);
65 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
68 xbt_dynar_t ready_tasks;
71 ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
72 xbt_dynar_foreach(dax, i, task) {
73 if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ && SD_task_get_state(task) == SD_SCHEDULABLE) {
74 xbt_dynar_push(ready_tasks, &task);
77 XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
82 static double finish_on_at(SD_task_t task, sg_host_t host)
84 volatile double result;
86 double data_available = 0.;
87 double redist_time = 0;
88 double last_data_available;
89 SD_task_t parent, grand_parent;
90 xbt_dynar_t parents, grand_parents;
92 sg_host_t *grand_parent_host_list;
94 parents = SD_task_get_parents(task);
96 if (!xbt_dynar_is_empty(parents)) {
97 /* compute last_data_available */
98 last_data_available = -1.0;
99 xbt_dynar_foreach(parents, i, parent) {
101 if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
102 grand_parents = SD_task_get_parents(parent);
104 xbt_assert(xbt_dynar_length(grand_parents) <2, "Error: transfer %s has 2 parents", SD_task_get_name(parent));
106 xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
108 grand_parent_host_list = SD_task_get_workstation_list(grand_parent);
109 /* Estimate the redistribution time from this parent */
110 if (SD_task_get_amount(parent) == 0){
113 redist_time = SD_route_get_latency(grand_parent_host_list[0], host) +
114 SD_task_get_amount(parent) / SD_route_get_bandwidth(grand_parent_host_list[0], host);
116 data_available = SD_task_get_finish_time(grand_parent) + redist_time;
118 xbt_dynar_free_container(&grand_parents);
121 /* no transfer, control dependency */
122 if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
123 data_available = SD_task_get_finish_time(parent);
126 if (last_data_available < data_available)
127 last_data_available = data_available;
130 xbt_dynar_free_container(&parents);
132 result = MAX(sg_host_get_available_at(host), last_data_available) + SD_task_get_amount(task)/sg_host_speed(host);
134 xbt_dynar_free_container(&parents);
136 result = sg_host_get_available_at(host) + SD_task_get_amount(task)/sg_host_speed(host);
141 static sg_host_t SD_task_get_best_host(SD_task_t task)
144 double EFT, min_EFT = -1.0;
145 const sg_host_t *hosts = sg_host_list();
146 int nhosts = sg_host_count();
149 best_host = hosts[0];
150 min_EFT = finish_on_at(task, hosts[0]);
152 for (i = 1; i < nhosts; i++) {
153 EFT = finish_on_at(task, hosts[i]);
154 XBT_DEBUG("%s finishes on %s at %f", SD_task_get_name(task), sg_host_get_name(hosts[i]), EFT);
158 best_host = hosts[i];
164 int main(int argc, char **argv)
167 double finish_time, min_finish_time = -1.0;
168 SD_task_t task, selected_task = NULL, last_scheduled_task;
169 xbt_dynar_t ready_tasks;
170 sg_host_t host, selected_host = NULL;
171 int total_nhosts = 0;
172 const sg_host_t *hosts = NULL;
173 char * tracefilename = NULL;
176 /* initialization of SD */
177 SD_init(&argc, argv);
179 /* Check our arguments */
180 xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
181 "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed", argv[0], argv[0]);
184 tracefilename = xbt_strdup(argv[3]);
186 /* creation of the environment */
187 SD_create_environment(argv[1]);
189 /* Allocating the host attribute */
190 total_nhosts = sg_host_count();
191 hosts = sg_host_list();
193 for (cursor = 0; cursor < total_nhosts; cursor++)
194 sg_host_allocate_attribute(hosts[cursor]);
196 /* load the DAX file */
197 dax = SD_daxload(argv[2]);
199 xbt_dynar_foreach(dax, cursor, task) {
200 SD_task_watch(task, SD_DONE);
203 /* Schedule the root first */
204 xbt_dynar_get_cpy(dax, 0, &task);
205 host = SD_task_get_best_host(task);
206 SD_task_schedulel(task, 1, host);
208 while (!xbt_dynar_is_empty(SD_simulate(-1.0))) {
209 /* Get the set of ready tasks */
210 ready_tasks = get_ready_tasks(dax);
211 if (xbt_dynar_is_empty(ready_tasks)) {
212 xbt_dynar_free_container(&ready_tasks);
213 /* there is no ready task, let advance the simulation */
216 /* For each ready task:
217 * get the host that minimizes the completion time.
218 * select the task that has the minimum completion time on its best host.
220 xbt_dynar_foreach(ready_tasks, cursor, task) {
221 XBT_DEBUG("%s is ready", SD_task_get_name(task));
222 host = SD_task_get_best_host(task);
223 finish_time = finish_on_at(task, host);
224 if (min_finish_time == -1. || finish_time < min_finish_time) {
225 min_finish_time = finish_time;
226 selected_task = task;
227 selected_host = host;
231 XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task), sg_host_get_name(selected_host));
232 SD_task_schedulel(selected_task, 1, selected_host);
235 * SimDag allows tasks to be executed concurrently when they can by default.
236 * Yet schedulers take decisions assuming that tasks wait for resource availability to start.
237 * The solution (well crude hack is to keep track of the last task scheduled on a host and add a special type of
238 * dependency if needed to force the sequential execution meant by the scheduler.
239 * If the last scheduled task is already done, has failed or is a predecessor of the current task, no need for a
243 last_scheduled_task = sg_host_get_last_scheduled_task(selected_host);
244 if (last_scheduled_task && (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
245 (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
246 !SD_task_dependency_exists(sg_host_get_last_scheduled_task(selected_host), selected_task))
247 SD_task_dependency_add("resource", NULL, last_scheduled_task, selected_task);
249 sg_host_set_last_scheduled_task(selected_host, selected_task);
250 sg_host_set_available_at(selected_host, min_finish_time);
252 xbt_dynar_free_container(&ready_tasks);
253 /* reset the min_finish_time for the next set of ready tasks */
254 min_finish_time = -1.;
257 XBT_INFO("Simulation Time: %f", SD_get_clock());
258 XBT_INFO("------------------- Produce the trace file---------------------------");
259 XBT_INFO("Producing a jedule output (if active) of the run into %s", tracefilename?tracefilename:"minmin_test.jed");
261 jedule_sd_dump(tracefilename);
265 xbt_dynar_free_container(&ready_tasks);
267 xbt_dynar_foreach(dax, cursor, task) {
268 SD_task_destroy(task);
270 xbt_dynar_free_container(&dax);
272 for (cursor = 0; cursor < total_nhosts; cursor++)
273 sg_host_free_attribute(hosts[cursor]);