摘要
由于线性规划在理论和实践中的重要性 ,对求解大规模规划问题并行算法的研究已引起许多学者的兴趣 .本文根据 Galperin提出的线性规划的一种线性时间的立方算法特别适合并行的特点 ,提出了一种基于 SPMD模型和主从式 MPI的线性规划并行算法 ,并对算法性能进行了深入分析 ,理论分析和在曙光 30 0 0上的实验结果表明 :该算法具有粗粒度并行、良好的可扩展性和理想加速比模型等优点 ,明显优于目前为止求解同类不对称线性规划问题的其他并行算法 。
As the importance in theory and practice of Linear Programming(LP), more and more attention have been paid on the research of parallel algorithm of LP. Recently, Galperin presented a linear time cubic algorithm of it. Following its good parallelism, a parallel cubic algorithm which is basing on SPMD parallel machine model and MPI programming environments is presented. Then its performance is intensively analyzed and its experimental results on DAWNING 3000 machine are also given. Theoretical analysis and experimental results show that it has some merits such as good scalability and ideal speedup model which by present other LP algorithms do not have, therefore, it can be used in computation of solving this sort of large scale LP problems.
出处
《小型微型计算机系统》
CSCD
北大核心
2003年第9期1718-1721,共4页
Journal of Chinese Computer Systems
基金
国家"8 63"高技术研究发展规划资助 (863 -3 0 6-ZD11-0 1-6)
国家高性能计算基金资助
关键词
并行算法
线性规划
可扩展性
高性能计算
parallel algorithm
linear programming
scalability
supercomputing
