Asynchronous BSP model and optimization techniques

Based on BSP model and the concept of computation-send segments, this paper proposes 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, the execution time of a process can be estimated and its performance equation can be got. In this model, two processes can execute in different super steps, at most p-1 super steps away from each other. Using program is executing time as the parameter, authors 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 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. Theoretical analysis and experiment results show 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 is efficiency and from increasing the throughput of computer systems.