并行计算中图划分算法的研究

发布时间：2018-06-17 09:38

本文选题：分布式并行系统 + 图划分　；参考：《华中师范大学》2013年硕士论文

【摘要】：现在,并行计算的平台绝大部分是分布式并行系统。分布式并行系统能否快速有效处理并行计算,除了依赖于分布式并行系统性能、网络带宽、并行算法等,还与任务分配和调度顺序有关。以一种合适的顺序将任务分配到处理器群上,以便提高系统使用效率和减少周转时间是任务分配的目。图划分算法为任务分配问题提供了解决方法。将任务分配问题转换为图模型,使用图划分算法解决任务分配问题。本文的研究环境是异构的分布式并行系统,使用任务交互图(TIG)和多层图划分算法来研究任务分配问题。多层图划分算法分为三个阶段：粗化(聚类)阶段、初始化分阶段和细化阶段。以往的聚类方法中,某两个任务是否能聚类仅仅取决于它们之间的通信代价。然而这是不够准确的,如果一个任务能被分配到一个更好的处理器上,也即在这个处理器上该任务总的执行代价要优于在之前的处理器上的执行代价。因此本文提出的聚类启发式算法考虑了任务之间的通信代价以及它们的不同。同时,任务分配到处理器的顺序会影响分配质量,因此本文提出了在两阶段方法中采用改进的度量方式来决定分配顺序,并在细化阶段改进了FM算法。最后,本文提出了一种基于迭代改进的启发式多层划分算法NTAT。文中提出的改进的任务分配算法是静态的,也就是说在程序开始执行时任务分配已经完成。但是,很多应用中可能会使用动态的任务分配方法以适应各种突然出现的情况,如工作量增加、处理器故障和链路故障等。改进的算法不适于动态划分的情况,因为动态的任务分配方法需要考虑与系统组件之间的交互,如与进程迁移机制的交互,同时还必须考虑其在细化阶段时的代价。因此,本文所有算法的改进是在静态划分的基础上进行的。
[Abstract]:Nowadays, the platform of parallel computing is distributed parallel system. Whether distributed parallel system can deal with parallel computing quickly and effectively depends not only on the performance of distributed parallel system, network bandwidth, parallel algorithm, but also on task allocation and scheduling order. Tasks are assigned to the processor population in a suitable order in order to improve system efficiency and reduce turnaround time. The graph partition algorithm provides a solution to the task assignment problem. The task assignment problem is transformed into graph model, and the graph partition algorithm is used to solve the task assignment problem. The research environment of this paper is a heterogeneous distributed parallel system. Task interaction graph (TIGG) and multi-layer graph partition algorithm are used to study the task assignment problem. The multilayer graph partition algorithm is divided into three stages: coarsening (clustering) phase, initialization stage and thinning stage. In previous clustering methods, whether two tasks can be clustered only depends on the communication cost between them. However, this is not accurate, if a task can be assigned to a better processor, that is, the overall execution cost of the task on this processor is higher than that on the previous processor. Therefore, the proposed clustering heuristic algorithm takes into account the communication cost between tasks and their differences. At the same time, the order in which tasks are assigned to the processor will affect the allocation quality. Therefore, an improved measurement method is proposed to determine the allocation order in the two-phase method, and the FM algorithm is improved in the thinning stage. Finally, a heuristic multilayer partition algorithm based on iteration is proposed in this paper. The proposed improved task allocation algorithm is static, that is, the task assignment is completed by the time the program begins to execute. However, many applications may use dynamic task allocation methods to adapt to various sudden situations, such as increased workload, processor failures and link failures. The improved algorithm is not suitable for dynamic partitioning because the dynamic task allocation method needs to consider the interaction with system components such as the process migration mechanism and the cost of the process migration mechanism. Therefore, all the algorithms in this paper are improved on the basis of static partitioning.
【学位授予单位】：华中师范大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6

【参考文献】