并行高斯消去法在云计算平台上的研究

Study of Parallel Gaussian Elimination Algorithm on Cloud Platform

为了解决串行部分选主元的高斯消去算法不能充分利用多核处理器的问题,提出并实现了并行多线程的部分选主元的高斯消去算法,并将整个算法进行了分析和优化,使数据的存储布局和算法的访存模式匹配,从而大幅提高了程序的性能。通过对本地Linux服务器以及美国亚马逊EC2云的多种平台上的实验结果的比较和分析,确定了部分选主元的高斯消去算法受缓存影响较大,所以在CPU和内存/缓存配置较为均衡的平台上运行性能最好。文中展现了一种高效率、扩展性好的多线程并行部分选主元的高斯消去算法以及将一般性串行算法进行并行化和优化的方法。

To solve the problem that the sequential Gaussian elimination algorithm with partial pivoting cannot utilize all the cores of a multi-core CPU,a novel parallel multi-threaded Gaussian elimination algorithm with partial pivoting is proposed and implemented. The whole algorithm is analyzed and optimized which makes the storage layout of data matches the access pattern of the algorithm,therefore the application performance is greatly improved. The application is executed on multiple computer platforms including a Linux server and several platforms in Amazon Elastic Compute Cloud. The comparison and analysis of the experiment results show that the performance of the multi-threaded Gaussian elimination algorithm with partial pivoting extremely depends on the cache system. The best performance is achieved on a platform with proportionate CPU and memory/cache hardware. Thus a high-efficiency and scalable multi-threaded Gaussi-an elimination algorithm with partial pivoting along with approaches to parallelize and optimize general sequential algorithms are presen-ted.