摘要
在许多实际工程问题中经常遇到一些大型线形规划问题,通常的计算过程需要占用大量的计算时间,效率低下。文中提出了一种基于BSP模型的大规模线性规划并行算法———修正单纯形并行算法,分析了其代价函数和加速比,在所研制的集群计算机上进行了实现和测试。结果表明:当问题规模比较大时,此并行算法能获得较好的加速比。
There are some large - scale linear programming problems in many projects. Their computational process needs more working time and the efficiency is influenced. In this paper,present a BSP （bulk synchronous parallel） large scale linear programming parallel algorithm, which can be implemented on PC cluster. Investigate the cost function and speedup of this algorithm. An implementation has been tested on PC cluster developed by us using the Oxford BSPIib, The results show that the BSP algorithm is of great value to a large scale LP problem in practice.
出处
《微机发展》
2005年第12期9-11,共3页
Microcomputer Development
关键词
BSP模型
PC集群
线性规划
并行算法
bulk synchronous parallel
PC cluster
linear programming
parallel algorithm
