运用蒙特卡洛模拟法的数据流调度优化模型研究

摘要

传统的静态数据流任务调度方法,其任务执行时间是可预知的.但在实时流计算平台中,数据流的顺序与数据量的大小都是不确定的,导致任务的执行时间也是不确定的.论文提出一种运用蒙特卡洛模拟法的数据流任务调度方法,该方法利用随机数生成算法,在一定约束条件下大量模拟生成任务执行时间,通过经典的静态调度算法(HEFT)产生相应的预调度方案,经过综合比较最终得到一种最优的预调度方案.实验结果表明:论文提出的方法不仅大大缩短了任务的调度时间,而且具有非常强的通用性.%The task execution time of the traditional static data flow task scheduling method is predictable. But in the re-al-time flow computing platform,the order of the data flow and the size of the data are uncertain,leading to the task execution time is uncertain.This paper presents a data flow task scheduling method based on Monte Carlo simulation method.This method gener-ates a large amount of task execution time under a certain constraint condition by using a random number generation algorithm,and generates a corresponding precondition by the classical static scheduling algorithm(HEFT). Finally,an optimal pre-scheduling scheme is obtained through comprehensive comparison.The experimental results show that the method proposed in this paper not on-ly greatly shortens the task scheduling time,but also has a very strong universality.