一种异步BSP模型及其程序优化技术

基于BSP模型，该文提出了异步计算模型（CSA－BSP）。该模型更准确地描述了并行机的性能参数，引导用户编写高效率的并行程序，在CSA－BSP模型下，两个进程异步执行的位置至多相差p-1个超步；基于程序的执行时间，作者分析了BSP、A－BSP和CSA－BSP程序的效率，得出CSA－BSP程序的效率是最高的，在曙光并行机上，用“红黑格法”和“矩阵乘法”进行了验证，和BSP模型相比，这两个CSA－BSP程序的效率分别提高20％和37％；同时，其进程执行时间和最大可以降低8％，因此，按照CSA－BSP模型编程对于提高程序效率和改善系统的吞吐率，都有良好的效果。

An Asynchronous BSP Model and Optimization Techniques

Parallel computing models, the bridges between system architecture and application, are widely investigated. Many models, such as BSP and LogP, have been proposed. But no one has been accepted as the unique model for parallel computation. In BSP model, communication operations are arranged at the end of each super step. This means that each process will send or receive data almost at the same time, which increases the possibility of communication congestion. In this paper, based on BSP model and the concept of computation send segments, we propose an asynchronous parallel computing model, CSA BSP, which can more accurately describe the performance parameters of parallel computers and guide programmers to write high efficient programs. This model utilizes the overlap of computation and communication and makes communications spread around a super step, which will reduce the congestion of communication in a traditional BSP super step.Under CSA BSP model, we can estimate the execution time of a process and give its performance equation. In this model, two processes can execute in different super steps, at most p-1 super steps away from each other. Using program's executing time as the parameter, we analyze the efficiencies of parallel programs under BSP, A BSP and CSA BSP models. Compared with the BSP and A BSP programs, CSA BSP programs are more efficient. The results are verified by the programs of the "Red and Black" method and the matrix multiplication. In our examples, compared to BSP programs, the efficiencies of CSA BSP programs increase by 20% and 37%. To analyze the throughput of CSA BSP model, another parameter, the total time used by all the processes in one application (PTS) is proposed. The CSA BSP program of "Red and Black" method can reduce the PTS time by 8% against that in the BSP program. During this time all resources have been released and they can be used by other tasks. From theoretical analysis and experiment results, we can see that CSA BSP model can more accurately analyze the performance parameters of parallel computers. Programming with CSA BSP model can enhance the performance both from improving the program's efficiency and from increasing the throughput of computer systems.