An Asynchronous BSP Model and Optimization Techniques
Liu Zhi Fang · Chinese Journal of Computers · 2002
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.