分布式内存机器中优化调度问题的数学模型  

Mathematical module for optimal scheduling in distributed-memory machines

作　　者：何琨[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2008年第2期61-65,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60673057);国家重点基础研究发展计划基金资助项目(G2004CB318000)

摘　　要：对分布式内存机器中相互依赖多任务的优化调度问题,将约束条件归纳为任务约束、链路约束和资源约束,建立了允许任务复制情况下多任务静态调度问题的数学模型.描述了有向无回路图的构造性定义,指出问题一定有不超过所有任务执行时间总和的解.推出以最短时间完成任务集所需的最小资源数与任务数一样大.阐明了问题具有可计算性.研究结果改进了原有的问题描述和数学模型,使对问题的认识更深入,并有利于寻求更好的求解策略.Optimal scheduling of mutual dependent multi-tasks in distributed-memory machines was considered. A mathematical model was built for static scheduling multi-tasks under the task duplication after constraints were divided into task constraints, link ones and resource ones. A constructible definition of the directed acyclic graph was described, and the reason why exists a solution that does not exceed the total execution time of all tasks was explained. It is proved that the problem＇s optimal solution is not worse than that of a scheduling problem having unlimited resources if the number of resources is equal to the number of the tasks. The computability of the scheduling was elucidated. The results could improve the description of the scheduling and mathematic formulation, making the scheduling explicit and being helpful to find good solving strategies.

关 键 词：分布式内存 任务调度 有向无回路图 跨度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]