A Study On Diagonal Computing Model For GPGPU Platform

In the computer field, there is a kind of problems with such characteristics: calculation of next element depends on several successive previous elements and number of element which can compute in parallel has certain mutual relationship. Additionally, elements can be iteratively calculated in prarallel. In this paper, we define diagonal computing model as a computing model with previous calculation feature. Diagonal computing model is widely used, such as local alignment algorithm in bioinformatics area, algorithm of context-free grammar in the natural language processing, parallel sorting network algorithms in the basic research and so on. Generally, algorithms consistent with this model are required to deal with a huge amount of data. In addition, with the development of society and advances in technology, data is growing exponentially. Therefore, it is increasingly important to improve the computational efficiency of the model.Currently, there is a wide variety of high performance computing platform to meet the needs of high performance computing. GPGPU platform is one of them. Compared to other platforms, it is handy for GPGPU platform to improve the algorithm's efficiency with the high internal computing power and high inherent parallelism in condition that it don't need increase any hardware cost. Moreover, with the development of hardware and OpenCL programming model have been proposed, it is even more suitable and easy to map algorithms in the general purpose computing area to GPGPU platform. Hence, how to use GPGPU platform to improve the speed of general purpose computing has become a research hotspot.In GPGPU platform, many scholars have been raised lots of solutions for diagonal computing model problems. For example, Edans et al. proposed a block idea to deal with the large scale local alignment issue in GPGPU platform; Yan Zhang have been solved the three diagonal linear equation in GPGPU platform; and numerous approaches to handle sorting problems have been implemented in GPGPU platform. However, these paper are all made based on specific problems. A general solution for diagonal model problems still has not been proposed.Our main contribution in this paper is that we have proposed a general solution for diagonal computing model which makes it easy and efficient to map to the GPGPU platform. Firstly, we describe the model in detail and carefully analyze the feature of the model. Then, a detail analysis of GPGPU platform and some optimization principles have been made. On the basis of earlier discussion, we raised a general solution for diagonal computing model. Finally, four typical cases which are consistent with diagonal computing model have verified the feasibility and effectiveness of our solution. From the experimental results, we can find that our solution can make the problem easily mapped to the GPGPU platform. Moreover, experiment data also show that all algorithms have a good improvement. Smith-Waterman algorithm can achieve the maximum performance of more than 100x, which 50x is the average situation.The two sorting algorithms have about 7 to 8 times improvement. The solution algorithm for tridiagonal linear equations can be up to 10 times increase. The algorithm of context-free grammaralso made 4 to 5 times acceleration.