基于BSP模型的异构计算模型设计

发布时间：2018-01-06 17:15

本文关键词：基于BSP模型的异构计算模型设计　出处：《吉林大学》2017年硕士论文　论文类型：学位论文

更多相关文章： Pi演算 BSP LS-BSP DDF-MM算法 Pict语言

【摘要】：近年来,由于越来越多计算复杂度高、计算规模大的任务在各个领域大量涌现,分布式的计算环境成为研究者的研究热点。其中,异构计算系统则以其更加贴近现实的思想和高效的计算性能,得到了研究者的广泛关注。如何将现有的并行计算经过改进,使其符合异构计算系统对时间性能上的要求,也成为了研究的方向之一。本文在总结前辈研究成果的基础之上,对BSP模型的各项特点进行了分析。最终,提出了一种适应异构计算环境的LS-BSP(Logic Super Step Bulk Synchronous Parallel)模型,研究内容主要包括:(1)改善超步的结构,提出“逻辑超步”的思想:将存在数据依赖的任务放在一个超步内。反之,相互独立的任务可以放在不同的超步内。由于不同的超步间不存在数据依赖,所以这些超步能够并行运行,从而提升了模型的并行性;(2)改变模型的超步中先计算,再通讯的机制,提出“Compute-CombainerSend机制”:为每个超步设定一个单独的同步线程Combainer,负责对数据的汇总。一方面,使不同处理节点间的计算阶段和通讯阶段并发执行;另一方面,数据同步后再发送给服务器端,减少了传输的数据量,提升了传输的效率;(3)改善模型任务分配机制:由于BSP模型应用于同构环境中,所以其任务分配主要考虑处理机是否闲置、任务数据是否为本地可分配的。在LS-BSP模型中,基于Max-min算法提出DDF-MM(Double Decision Factor Max-min)算法,使用各处理机任务处理时间的标准差系数和平均处理时长作为任务的优先级,并在分配过程中综合考虑所有处理机当前的负载情况。另外,进程演算语言——Pi演算可以通过传递通道名字的方式,改变网络的拓扑结构和状态,这使得Pi演算可以简洁明了的描述上述异构计算系统。所以,本文中使用Pi演算描述LS-BSP模型,并建立LS-BSP理论模型。随后,依靠Pi演算中常用的弱互模拟理论,验证了LS-BSP模型在理论上是正确的。基于Pi演算的Pict语言是一种自然的并行语言,能够以一种自然的语义对并行计算系统进行编程。本文中分别使用Pict语言和Java语言描述了LS-BSP模型,使用Java语言描述了BSP模型,并在处理机负载、整体任务处理的时间跨度方面验证了LS-BSP模型的性能提升以及Pict语言对并行计算模型的优化。
[Abstract]:In recent years, due to more and more high computational complexity, large-scale computing tasks have emerged in a large number of fields, distributed computing environment has become a research hotspot. Isomeric computing systems, for their more realistic ideas and efficient computing performance, have been widely concerned by researchers. How to improve the existing parallel computing. Making it meet the requirements of heterogeneous computing system on time performance has become one of the research directions. Based on the previous research results, this paper analyzes the characteristics of the BSP model. Finally. This paper presents a LS-BSP(Logic Super Step Bulk Synchronous parallel model for heterogeneous computing environments. The main contents of the research include: 1) improving the structure of superstep, and putting forward the idea of "logical overstep": putting the task of data dependence in one step. Conversely. Independent tasks can be placed in different supersteps. Because there is no data dependency among the different supersteps, these steps can run in parallel, thus enhancing the parallelism of the model. 2) change the mechanism of superstep calculation and communication of the model. Put forward "Compute-CombainerSend mechanism": set up a separate synchronization thread Combainer for each step, responsible for the data aggregation. On the one hand. The computation phase and communication phase of different processing nodes are executed concurrently; On the other hand, the data is synchronized and then sent to the server, which reduces the amount of data transferred and improves the efficiency of transmission. 3) improve the model task allocation mechanism: because the BSP model is applied in the isomorphic environment, its task assignment mainly considers whether the processor is idle or not. Whether the task data is locally distributable. In the LS-BSP model. DDF-MM(Double Decision Factor Max-min algorithm is proposed based on Max-min algorithm. The standard deviation coefficient of processing time and the average processing time of each processor are used as the priority of the task, and the current load of all processors is considered in the process of allocation. Process Calculation--Pi Calculus can change the topology and state of the network by passing the name of the channel, which makes the Pi Calculus can describe the heterogeneous computing system. In this paper, we use Pi calculus to describe the LS-BSP model and establish the LS-BSP theory model. Then, we rely on the weak mutual simulation theory commonly used in Pi calculus. The LS-BSP model is proved to be correct in theory. The Pict language based on Pi calculus is a natural parallel language. The parallel computing system can be programmed with a kind of natural semantics. In this paper, the LS-BSP model is described by Pict language and Java language, respectively. Use the Java language to describe the BSP model and load in the processor. The time span of overall task processing verifies the performance improvement of LS-BSP model and the optimization of parallel computing model by Pict language.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP338

【相似文献】