【作者】 赵琴；

【导师】 高丽；

【作者基本信息】 华中师范大学 ， 计算机系统结构， 2013， 硕士

【摘要】 现在,并行计算的平台绝大部分是分布式并行系统。分布式并行系统能否快速有效处理并行计算,除了依赖于分布式并行系统性能、网络带宽、并行算法等,还与任务分配和调度顺序有关。以一种合适的顺序将任务分配到处理器群上,以便提高系统使用效率和减少周转时间是任务分配的目。图划分算法为任务分配问题提供了解决方法。将任务分配问题转换为图模型,使用图划分算法解决任务分配问题。本文的研究环境是异构的分布式并行系统,使用任务交互图(TIG)和多层图划分算法来研究任务分配问题。多层图划分算法分为三个阶段：粗化(聚类)阶段、初始化分阶段和细化阶段。以往的聚类方法中,某两个任务是否能聚类仅仅取决于它们之间的通信代价。然而这是不够准确的,如果一个任务能被分配到一个更好的处理器上,也即在这个处理器上该任务总的执行代价要优于在之前的处理器上的执行代价。因此本文提出的聚类启发式算法考虑了任务之间的通信代价以及它们的不同。同时,任务分配到处理器的顺序会影响分配质量,因此本文提出了在两阶段方法中采用改进的度量方式来决定分配顺序,并在细化阶段改进了FM算法。最后,本文提出了一种基于迭代改进的启发式多层划分算法NTAT。文中提出的改进的任务分配算法是静态的,也就是说在程序开始执行时任务分配已经完成。但是,很多应用中可能会使用动态的任务分配方法以适应各种突然出现的情况,如工作量增加、处理器故障和链路故障等。改进的算法不适于动态划分的情况,因为动态的任务分配方法需要考虑与系统组件之间的交互,如与进程迁移机制的交互,同时还必须考虑其在细化阶段时的代价。因此,本文所有算法的改进是在静态划分的基础上进行的。更多还原

【Abstract】 Now, the platforms of parallel computing is mostly distributed and parallel system Distributed and parallel system can perform parallel computing quickly and efficiently, not only rely on performance of the distributed and parallel system, network bandwidth, parallel algorithm, but also relate to the task allocation and scheduling order.The object of task assignment is to improve efficiency of the system and reduce turnaround time by assigning task in an appropriate order. Graph partitioning algorithm provides a solution to task assignment. Convert the task assignment problem into graph model, and using graph partitioning algorithm to solve the problem..The research environment is heterogeneous distributed and parallel systems, using task interaction diagrams (TIG) and multi-graph partitioning algorithm to study assignment problem. Multilevel-graph partitioning algorithm is divided into three phases: coarsening (clustering) phase, the initialization phases and refinement phase. Clustering method we mentioned in the paper is not accurate enough, because a two task clustering depends solely on whether the communication cost between them. But these two tasks may be dissimilar in the sense that their total execution cost may be inferior when assigned to the favorite processor of either one, where the favorite processor of a task is the processor that has the minimum execution time for that task. So, we propose a clustering heuristic which considers the communication costs between two tasks as well as their dissimilarity. Meanwhile, the order of task assignment to the processors will affect the quality of distribution, this paper proposes a metric to determine the allocation sequence in two-phase method, and we improve FM in refinement phase. Finally, we propose a improved heuristic multilevel algorithm named NTAT based on iterativeThis paper presenting an proposed task assignment algorithm is static, which means before the program starts, the task assignment has been completed. However, many applications may use dynamic task assignment methods to accommodate a variety of sudden occurrences, such as increased workload, processor failure and link failure. The improved algorithm is not suitable for dynamic partitioning, because the dynamic task assignment method needs to consider the interaction between the system components, such as process migration mechanisms and interactions must also be considered in the refinement stage of consideration. Therefore, this algorithm is on the basis of the static partitioning.更多还原