【作者】 罗飞；

【导师】 金海；

【作者基本信息】 华中科技大学 ， 计算机系统结构， 2008， 博士

【摘要】 对等高性能计算系统为解决在任务级并行的计算密集型对等高性能应用所提供的潜在计算能力能够超过以往任何计算系统,因而受到越来越多的关注。然而,现有的典型对等高性能计算系统由于不支持具有数据依赖关系的对等高性能应用而受到限制。因此,有必要研究新的对等高性能计算技术,使对等高性能计算系统支持具有数据依赖关系的应用,从而达到推广对等高性能计算系统的目的。为了支持任务间具有数据依赖关系的对等高性能应用,重点研究对等高性能计算中的计算资源管理策略、任务调度机制和编程模型这三种关键技术;基于这些技术提出对等高性能计算系统P2HP-2(A Peer-to-peer based High performance computingPlatform-Ⅱ),并结合一个运行实例,对系统的总体性能进行综合评价。根据具有数据依赖关系的任务对资源分配的要求,通过对等网络GTapestry管理对等高性能计算资源。GTapestry是一个基于无结构工作组的结构化对等网络,从两方面考虑网络匹配要求:其一是对象分派与区域网络构造之间的匹配,其二是虚拟网络和物理网络之间的邻近匹配。为了提高路由效率,GTapestry采用一个对象指针备份机制,即在任务的发布路径上备份任务对象地址,若在路由过程中遇到目标对象的备份地址,则根据该地址直接重定向到对象的实际寄存节点。为了对具有数据依赖关系的应用进行调度,提出了一种协商协同任务调度策略,它根据任务间的数据依赖关系和计算资源的局部邻居表,通过局部协商的方式对依赖任务进行分派和调度。其中,依赖任务的分派通过协商机制完成,即节点将当前任务的依赖任务赋予优先级,并在与它的邻居节点进行协商后,将依赖任务分派给其中的一个邻居节点。任务的运行通过协同调度机制完成,即在设置好任务运行所需的程序、参数和依赖数据后,运行时系统对任务进行非抢占式单任务调度。同时,各个计算节点根据当前的任务负载,通过局部协商方式动态调整任务的分配,从而实现动态负载平衡。为了对具有数据依赖关系的应用进行并行化编程,以任务与运行时系统的交互模型为基础,研究了一种单边消息通信编程模型OMP(One-sided Message Passingprogramming model),它由通信库和软件开发包组成。通信库提供了一种单边消息通信机制,并在此基础上实现了软件开发包;应用程序员利用开发包提供的应用编程接口(API,Application Programming Interface),可以通过模块分割的方式对串行程序进行分布式改造。基于编程模型OMP,依赖任务可以利用它所提供的应用编程接口,在应用级主动发起数据请求,进而结合GTapestry的节点通信机制和协商协同任务调度策略,满足任务对依赖数据的请求。为了验证基于GTapestry的计算资源管理策略、协商协同任务调度机制和单边消息通信编程模型这三种对等高性能计算技术能够支持具有数据依赖关系的应用,利用它们实现了对等高性能计算系统P2HP-2,并针对蛋白质折叠应用,提出并实现了具有静态树状任务依赖关系的1-level-core并行Threading算法,依据该并行算法对系统进行测试和综合性能分析。与结构化对等网络Tapestry相比,GTapestry更加稳定,且路由效率更高,而动态维护开销更少,通过理论分析和实验,表明基于GTapestry的计算资源管理策略能够满足依赖任务之间的通信需求,并且通信延迟较小;并且协商协同任务调度机制能够对具有数据依赖关系的应用进行调度,它能够自适应于动态计算环境。最后,综合性能分析验证了基于GTapestry的计算资源管理策略、协商协同任务调度机制以及单边消息通信编程模型,使得对等高性能计算系统P2HP-2能够支持具有数据依赖关系的对等高性能应用。更多还原

【Abstract】 In order to resolve the compute-intensive applications whose parallism is in the task level, Peer-to-peer (P2P) based high performance computing (HPC) systems have the potential capability to construct a powerful virtual supercomputer far beyond any current computing center by assembling idle internet cycles. Therefore, more and more such systems are coming into being. However, most typical systems currently are limited because they can not support applications with data-dependable relationship. Therefore, in order to promote P2P based HPC systems, it is necessary to investigate the key technologies of such systems, whick drive them to support more general applications with data-dependency.Therefore, a new P2P based HPC platform, P2HP-2, is designed in this paper. The key technologies of P2HP-2 are studied, such as the resource management strategy, the task scheduling policy, as well as the application programming model. Furthermore, combined with an application instance, the overall performance of P2HP-2 is evaluated.To fill the requirement of the resource allocation for the dependent tasks, the computing resources of P2HP-2 are self-organized in GTapestry, which is a structured overlay based on unstructured workgroups. The construction of GTapestry considers the overall proximity matching, including the matching between the object’s distribution and the domain’s construction, and the location matching between the virtual and physical networks. Moreover, dynamic maintaining metrics for nodes and groups and an object pointer backup policy are exploited to boost the routing efficiency. The structural design of GTapestry provides such characteristic as self-adaptation and self-organization, and the efficient communication mechanism between workgroups helps P2HP-2 to support applications with task-dependent relationship.In order to schedule the execution of the applications with data-dependency, a negotiated coscheduling policy is proposed. According to the dependable relationship reflected in the project description file and the local neighbor tables of the nodes, it dispatches and coschedules dependable tasks with local negotiation. First, the dependable task will be endowed with a task priority, and it will be dispatched to one of the neighbors of the current node with the negotiation among the neighbor nodes. Then the task will be coscheduled with the non-preemptive single-task scheduling, which follows the complete configuration of the necessary programs, parameters and dependent data for the task. At the mean time, according to their current load, the nodes will dynamically adjust the distribution of tasks with local negotiation among them. The programming model attacks the problem at the level of the model that acts as an interface between applications and computing systems, and a one-sided message passing programming model (OMP) is implemented to drive the development of P2HP-2. Based on the communication mode between tasks and the runtime, OMP consists of a communication library (ComLib) and a software development kit (SDK). In the ComLib, a one-sided communication mechanism is provided with the help of the runtime. Then the SDK is implemented based on the ComLib, where the application programming interfaces (API) can be exploited to parallelize applications through module division. Therefore, the tasks can meet their dependent data by initiating a data request with the APIs in OMP, where the request is resolved by the combination of the communication mechanism in GTapestry and the negotiated coscheduling policy of P2HP-2.In order to verify P2HP-2’s capability to support the tasks with interactive tasks, a parallel benchmark is presented, where the 1-level-core parallel threading algorithm is proposed and is implemented as the parallel threading program with OMP. In the parallel 1-level-core threading program, the threading process between one protein template and one target sequence is divided as tasks, which are parallel executed and have the static tree-like task-dependent relationship among them.Compared with the structured P2P network as Tapestry, GTapestry is more statble, routes more efficiently, and costs less for dynamic maintenance. It is shown that the structural design of GTapestry can meet the high efficient communication requirements for the dependent tasks. Moreover, according to the theoretical and experimental analysis, it is presented that the negotiated coscheduling policy can schedule the execution of the applications with data-dependency, which can be suitable to the dynamic environment. Finally, in terms of the performance tests of the parallel threading algorithm in P2HP-2, it is shown that such key technologies as the resource management strategy of GTapestry, the negotiated coscheduling policy, and the one-sided message passing programming model can make the P2P based HPC systems to support applications with data-dependency.更多还原