1 /* Copyright (c) 2009-2021. 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. */
8 #include "simgrid/simdag.h"
12 #if SIMGRID_HAVE_JEDULE
13 #include "simgrid/jedule/jedule_sd_binding.h"
16 XBT_LOG_NEW_DEFAULT_CATEGORY(test, "Logging specific to this SimDag example");
18 typedef struct _HostAttribute *HostAttribute;
19 struct _HostAttribute {
20 /* Earliest time at which a host is ready to execute a task */
22 SD_task_t last_scheduled_task;
25 static double sg_host_get_available_at(const_sg_host_t host)
27 const struct _HostAttribute* attr = (HostAttribute)sg_host_get_data(host);
28 return attr->available_at;
31 static void sg_host_set_available_at(sg_host_t host, double time)
33 HostAttribute attr = (HostAttribute)sg_host_get_data(host);
34 attr->available_at = time;
35 sg_host_set_data(host, attr);
38 static SD_task_t sg_host_get_last_scheduled_task(const_sg_host_t host)
40 const struct _HostAttribute* attr = (HostAttribute)sg_host_get_data(host);
41 return attr->last_scheduled_task;
44 static void sg_host_set_last_scheduled_task(sg_host_t host, SD_task_t task){
45 HostAttribute attr = (HostAttribute)sg_host_get_data(host);
46 attr->last_scheduled_task=task;
47 sg_host_set_data(host, attr);
50 static xbt_dynar_t get_ready_tasks(const_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 && SD_task_get_state(task) == SD_SCHEDULABLE) {
59 xbt_dynar_push(ready_tasks, &task);
62 XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
67 static double finish_on_at(const_SD_task_t task, const_sg_host_t host)
71 xbt_dynar_t parents = SD_task_get_parents(task);
73 if (!xbt_dynar_is_empty(parents)) {
75 double data_available = 0.;
76 double last_data_available;
77 /* compute last_data_available */
79 last_data_available = -1.0;
80 xbt_dynar_foreach(parents, i, parent) {
82 if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
83 sg_host_t * parent_host= SD_task_get_workstation_list(parent);
84 /* Estimate the redistribution time from this parent */
86 if (SD_task_get_amount(parent) <= 1e-6){
89 redist_time = sg_host_get_route_latency(parent_host[0], host) +
90 SD_task_get_amount(parent) / sg_host_get_route_bandwidth(parent_host[0], host);
92 data_available = SD_task_get_start_time(parent) + redist_time;
95 /* no transfer, control dependency */
96 if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
97 data_available = SD_task_get_finish_time(parent);
100 if (last_data_available < data_available)
101 last_data_available = data_available;
104 xbt_dynar_free_container(&parents);
107 fmax(sg_host_get_available_at(host), last_data_available) + SD_task_get_amount(task) / sg_host_get_speed(host);
109 xbt_dynar_free_container(&parents);
111 result = sg_host_get_available_at(host) + SD_task_get_amount(task) / sg_host_get_speed(host);
116 static sg_host_t SD_task_get_best_host(const_SD_task_t task)
118 sg_host_t *hosts = sg_host_list();
119 int nhosts = sg_host_count();
120 sg_host_t best_host = hosts[0];
121 double min_EFT = finish_on_at(task, hosts[0]);
123 for (int i = 1; i < nhosts; i++) {
124 double EFT = finish_on_at(task, hosts[i]);
125 XBT_DEBUG("%s finishes on %s at %f", SD_task_get_name(task), sg_host_get_name(hosts[i]), EFT);
129 best_host = hosts[i];
136 int main(int argc, char **argv)
139 double min_finish_time = -1.0;
141 SD_task_t selected_task = NULL;
142 xbt_dynar_t ready_tasks;
143 sg_host_t selected_host = NULL;
144 char * tracefilename = NULL;
146 /* initialization of SD */
147 SD_init(&argc, argv);
149 /* Check our arguments */
150 xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
151 "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed", argv[0], argv[0]);
154 tracefilename = xbt_strdup(argv[3]);
156 /* creation of the environment */
157 SD_create_environment(argv[1]);
159 /* Allocating the host attribute */
160 unsigned int total_nhosts = sg_host_count();
161 sg_host_t *hosts = sg_host_list();
163 for (cursor = 0; cursor < total_nhosts; cursor++)
164 sg_host_set_data(hosts[cursor], xbt_new0(struct _HostAttribute, 1));
166 /* load the DAX file */
167 xbt_dynar_t dax = SD_daxload(argv[2]);
169 xbt_dynar_foreach(dax, cursor, task) {
170 SD_task_watch(task, SD_DONE);
173 /* Schedule the root first */
174 xbt_dynar_get_cpy(dax, 0, &task);
175 sg_host_t host = SD_task_get_best_host(task);
176 SD_task_schedulel(task, 1, host);
177 xbt_dynar_t changed_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
178 SD_simulate_with_update(-1.0, changed_tasks);
180 while (!xbt_dynar_is_empty(changed_tasks)) {
181 /* Get the set of ready tasks */
182 ready_tasks = get_ready_tasks(dax);
183 xbt_dynar_reset(changed_tasks);
185 if (xbt_dynar_is_empty(ready_tasks)) {
186 xbt_dynar_free_container(&ready_tasks);
187 /* there is no ready task, let advance the simulation */
188 SD_simulate_with_update(-1.0, changed_tasks);
191 /* For each ready task:
192 * get the host that minimizes the completion time.
193 * select the task that has the minimum completion time on its best host.
195 xbt_dynar_foreach(ready_tasks, cursor, task) {
196 XBT_DEBUG("%s is ready", SD_task_get_name(task));
197 host = SD_task_get_best_host(task);
198 double finish_time = finish_on_at(task, host);
199 if (min_finish_time < 0 || finish_time < min_finish_time) {
200 min_finish_time = finish_time;
201 selected_task = task;
202 selected_host = host;
206 XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task), sg_host_get_name(selected_host));
207 SD_task_schedulel(selected_task, 1, selected_host);
210 * SimDag allows tasks to be executed concurrently when they can by default.
211 * Yet schedulers take decisions assuming that tasks wait for resource availability to start.
212 * The solution (well crude hack is to keep track of the last task scheduled on a host and add a special type of
213 * dependency if needed to force the sequential execution meant by the scheduler.
214 * If the last scheduled task is already done, has failed or is a predecessor of the current task, no need for a
218 SD_task_t last_scheduled_task = sg_host_get_last_scheduled_task(selected_host);
219 if (last_scheduled_task && (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
220 (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
221 !SD_task_dependency_exists(sg_host_get_last_scheduled_task(selected_host), selected_task))
222 SD_task_dependency_add(last_scheduled_task, selected_task);
224 sg_host_set_last_scheduled_task(selected_host, selected_task);
225 sg_host_set_available_at(selected_host, min_finish_time);
227 xbt_dynar_free_container(&ready_tasks);
228 /* reset the min_finish_time for the next set of ready tasks */
229 min_finish_time = -1.;
230 xbt_dynar_reset(changed_tasks);
231 SD_simulate_with_update(-1.0, changed_tasks);
234 XBT_INFO("Simulation Time: %f", simgrid_get_clock());
235 XBT_INFO("------------------- Produce the trace file---------------------------");
236 XBT_INFO("Producing a jedule output (if active) of the run into %s", tracefilename?tracefilename:"minmin_test.jed");
237 #if SIMGRID_HAVE_JEDULE
238 jedule_sd_dump(tracefilename);
242 xbt_dynar_free_container(&ready_tasks);
243 xbt_dynar_free(&changed_tasks);
245 xbt_dynar_foreach(dax, cursor, task) {
246 SD_task_destroy(task);
248 xbt_dynar_free_container(&dax);
250 for (cursor = 0; cursor < total_nhosts; cursor++) {
251 free(sg_host_get_data(hosts[cursor]));
252 sg_host_set_data(hosts[cursor], NULL);