simgrid-MSG-DAG调度.docx

DAG任务调度1.程序基本框架#include simdag/simdag.hint main(int argc, char *argv) SD_init(&argc, argv); /* Insert your code here */ SD_exit(); return 0;2.描述DAG2.1定义有向无环图Directed Acyclic Graph G = (V; E)其中V=vi|i=1,.,v，表示任务集合E=ei,j|(I,j)属于1,.,v*1,v，表示任务依赖关系或者数据流向。l 串行计算使用SD task t of type SD TASK COMP SEQConstructor: SD task create comp seq(name, data, amount)name: the name of the task, as given by the userdata: some user data attached to the task，Useful for scheduling attributesamount: the number of ops computed by this taskDestructor: SD task destroy(task)l 并行计算No type (SD TASK NOT TYPED), default kind of SD task tConstructor: SD task create(name, data, amount) amount: represents the sequential cost of the task2.2手工描述2.2.1描述边/依赖关系控制流：SD task dependency add (name, data,目的,源)数据流：SD task dependency add (name, data,目的,任务)；SD task dependency add (name, data,任务,源)2.2.2描述传输任务点对点通信：SD task create comm e2e(name, data, amount)MxN data redistributions：SD task create(name, data, amount)例1：描述下图所示的DAG任务答案： c1 = SD_task_create_comp_seq(c1, NULL, 1E9); c2 = SD_task_create_comp_seq(c2, NULL, 5E9); c3 = SD_task_create_comp_seq(c3, NULL, 2E9); t1 = SD_task_create_comm_e2e(t1, NULL, 5e8); SD_task_dependency_add (c1-t1, NULL, c1, t1); SD_task_dependency_add (t1-c3, NULL, t1, c3); SD_task_dependency_add (c2-c3, NULL, c2, c3);2.2.3管理一组任务使用动态数组，需要用到头文件xbt.h相关函数：my dynar = xbt dynar new (elm size, free method)xbt dynar free container (&my dynar)xbt dynar push (my dynar, &element)xbt dynar pop(my dynar, &element)xbt dynar foreach(my dynar, ctr, element)xbt dynar length(my dynar)xbt dynar is empty(my dynar)2.2.4查询任务信息Parameters of the constructor：SD task get name(task)SD task get data(task)SD task get amount(task)SD task get kind(task)Dependencies of task T：T所依赖的任务：SD task get parents(T)依赖T的任务：SD task get children(T)两个函数的返回类型都是xbt dynar t获取所有信息：SD task dump(task)例2：#include simdag/simdag.h#include xbt.hint main(int argc, char *argv) SD_task_t c1, c2, c3, t1, tmp; unsigned int ctr; xbt_dynar_t tasks = xbt_dynar_new(sizeof(SD_task_t), &xbt_free);/创建任务列表 SD_init(&argc, argv);/任务描述 c1 = SD_task_create_comp_seq(c1, NULL, 1E9); c2 = SD_task_create_comp_seq(c2, NULL, 5E9); c3 = SD_task_create_comp_seq(c3, NULL, 2E9); t1 = SD_task_create_comm_e2e(t1, NULL, 5e8); SD_task_dependency_add (c1-t1, NULL, c1, t1); SD_task_dependency_add (t1-c3, NULL, t1, c3); SD_task_dependency_add (c2-c3, NULL, c2, c3); /向任务列表添加任务 xbt_dynar_push(tasks, &c1); xbt_dynar_push(tasks, &c2); xbt_dynar_push(tasks, &c3); xbt_dynar_push(tasks, &t1); /获取每个任务的所有信息 xbt_dynar_foreach(tasks, ctr, tmp) SD_task_dump(tmp); SD_task_destroy(tmp); xbt_dynar_free_container(&tasks); SD_exit(); return 0;2.3 使用工具描述自动创建任务和依赖关系增加了两个特殊的dummy任务：root和end返回SD task t类型的xbt dynar t2.3.1 DAX format：使用SD daxload(filename)加载文件Header：Job description：Described by: id, name, runtime, input and output _lesl Only computations are described (amount = runtime _ 4:2e9)l Output of task1 is a input of task2 ) Transfer task + data ow dependencyControl ow dependencies：l task3 cannot start before the completion of task2，While there is no data flow dependency例3： 2.3.2 DOT format：使用SD dotload(filename)加载文件例4：题目同例3digraph G c1 size=1e9; c2 size=5e9; c3 size=2e9; root-c1 size=2e8; root-c2 size=1e8; c1-c3 size=5e8; c2-c3 size=-1.; c3-end size=2e8;例5：使用DAX或DOT加载器include simdag/simdag.h#include xbt.hint main(int argc, char *argv) unsigned int cpt; int nworkstations; const SD_workstation_t * workstations; SD_task_t task; xbt_dynar_t dag; SD_init(&argc, argv); dag = SD_daxload(argv1); xbt_dynar_foreach(dag, cpt, task) SD_task_dump(task); xbt_dynar_foreach(dag, cpt, task) SD_task_destroy(task); SD_create_environment(argv2); nworkstations = SD_workstation_get_number(); workstations = SD_workstation_get_list(); for (cpt = 0; cpt nworkstations; cpt+) SD_workstation_dump(workstationscpt); SD_exit(); return 0;3.描述资源3.1资源类型资源按AS分组，并且用XML格式描述。一个host和link组合成一个workstationSingle Hosts：id和powerLinks:id,latency和bandwidthClusters:id和namepowerprivate link latency (lat) and bandwidth (bw)backbone latency (bb lat) and bandwidth (bb bw)routerroutes: src and dst例6： 3.2创建环境（1） 加载平台文件SD create environment（2） get所有的workstation SD workstation get number()，SD workstation get list()（3） 查询workstation信息SD workstation get name(workstation)SD workstation get power(workstation)SD workstation get data(workstation)SD workstation dump(workstation)3.3查询网络信息（1） get所有连接（2） 查询连接信息：SD link get name(link)SD link get data(workstation)SD link get sharing policy (link)（3） 查询路由信息：SD route get size (src workstation, dst workstation)SD route get list (src workstation, dst workstation)例7：#include simdag/simdag.h#include xbt.hint main(int argc, char *argv) unsigned int cpt; int nworkstations; const SD_workstation_t * workstations; SD_task_t task; xbt_dynar_t dag; SD_init(&argc, argv); dag = SD_daxload(argv1); xbt_dynar_foreach(dag, cpt, task) SD_task_dump(task); xbt_dynar_foreach(dag, cpt, task) SD_task_destroy(task); SD_create_environment(argv2); nworkstations = SD_workstation_get_number(); workstations = SD_workstation_get_list(); for (cpt = 0; cpt available_at;static void SD_workstation_set_available_at(SD_workstation_t ws, double time) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); attr-available_at = time; SD_workstation_set_data(ws, attr);static void SD_workstation_allocate_attribute(SD_workstation_t ws) void *data = calloc(1, sizeof(struct _WorkstationAttribute); SD_workstation_set_data(ws, data);static void SD_workstation_free_attribute(SD_workstation_t ws) free(SD_workstation_get_data(ws); SD_workstation_set_data(ws, NULL);static SD_task_t SD_workstation_get_last_scheduled_task(SD_workstation_t ws) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); return attr-last_scheduled_task;static void SD_workstation_set_last_scheduled_task(SD_workstation_t ws, SD_task_t task) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); attr-last_scheduled_task=task; SD_workstation_set_data(ws, attr);4.写DAG调度程序4.1基本原理对每个任务：分配资源并定义执行顺序考虑任务依赖关系：一个任务只有等待其所有前驱任务完成后才可以开始执行。调度类型：offline，online（静态调度与动态调度）4.2 模型任务执行（1） 静态调度任务执行前确定调度顺序，调用SD task schedule*，然后调用SD simulate(-1.)（2） 动态调度在任务执行的过程中进行调度，有两种情况：每隔X秒调度一次SD simulate(X)；在任务状态总添加watchpoints，调用SD task watch (task, state)。每个watch点到达时将进行调度4.3 执行模拟后的工作SD task get start time (task)可获取开始时间SD task get finish time (task)获取结束时间SD task get workstation count (task)任务使用资源数量SD task get workstation list (task)执行任务的资源生成干特图，并分析性能：使用内置的Jedule or Paj_e4.4 A Simple Static Round-Robin Scheduler假设：DAG调度时，每个任务只在一个主机上执行，数据传输采用点到点通信创建：compute task = SD task create comp seq(name, data, amount) transfer task = SD task create comm e2e(name, data, amount)调度：SD task schedulev(task, workstation nb, workstation list)SD task schedulel(task, workstation nb, .)#include simdag/simdag.h#include xbt.htypedef struct _WorkstationAttribute double available_at; SD_task_t last_scheduled_task; *WorkstationAttribute;static double SD_workstation_get_available_at(SD_workstation_t ws) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); return attr-available_at;static void SD_workstation_set_available_at(SD_workstation_t ws, double time) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); attr-available_at = time; SD_workstation_set_data(ws, attr);static void SD_workstation_allocate_attribute(SD_workstation_t ws) void *data = calloc(1, sizeof(struct _WorkstationAttribute); SD_workstation_set_data(ws, data);static void SD_workstation_free_attribute(SD_workstation_t ws) free(SD_workstation_get_data(ws); SD_workstation_set_data(ws, NULL);static SD_task_t SD_workstation_get_last_scheduled_task(SD_workstation_t ws) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); return attr-last_scheduled_task;static void SD_workstation_set_last_scheduled_task(SD_workstation_t ws, SD_task_t task) WorkstationAttribute attr = (WorkstationAttribute) SD_workstation_get_data(ws); attr-last_scheduled_task=task; SD_workstation_set_data(ws, attr);int main(int argc, char *argv) unsigned int cpt, cpt2; int nworkstations; const SD_workstation_t * workstations; SD_task_t task; xbt_dynar_t dag; SD_init(&argc, argv); dag = SD_daxload(argv1); xbt_dynar_foreach(dag, cpt, task) SD_task_dump(task); SD_create_environment(argv2