分布式Kahn处理网络的一种集群调度算法  

Cluster scheduling algorithm for distributed Kahn process networks

作　　者：钱正平[1] 齐德昱[1] 曾鸣[2] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510640 [2]华南理工大学理学院,广州510640

出　　处：《计算机应用研究》2009年第12期4463-4466,4470,共5页Application Research of Computers

基　　金：粤港关键领域重点突破项目(2008A011400010);国家技术创新基金资助项目(08C26214411198);广州市创新基金资助项目(2007V41C0301)

摘　　要：研究并提出一种采用分布式Kahn处理网络表达的并行程序在多处理器集群环境下的任务———处理器动态分配算法。由于Kahn处理网络的不可判定性,静态作业调度算法不能适用,而忽略其显式数据依赖关系的动态负载均衡策略存在很大的随机性,往往带来不必要的进程迁移。基于运行时动态生成的离散事件序列,预测Kahn处理网络在不同分配方案下的执行效率(处理器资源利用率),迭代寻求最优动态分配方案,仿真效果良好。This paper proposed a novel task-processor assignment algorithm for parallel applications expressed by distributed Kahn process networks in a multi-processor cluster. Static job scheduling algorithms did not work for that a model of Kahn process networks was undecidable, and dynamic load balancing strategies which ignore the data dependencies among tasks may also bring unwanted process migrations. The algorithm presented was based on the sequence of dynamic recorded runtime events in a discrete timed manner, tt predicted the efficiency （ or processor utilization rate） of the Kahn process networks under various assignments, to iterately found out the optimal solution. Simulations have shown satisfying results.

关 键 词：分布式Kahn处理网络 处理器分配 集群调度 负载均衡 离散事件 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]