基于BSP模型的大规模线性规划并行算法研究  

Research on BSP-Based Large Scale Linear Programming Parallel Algorithm

作　　者：田媛[1] 彭勤科[2] 

机构地区：[1]上海交通大学信息中心,上海200030 [2]西安交通大学系统工程研究所,陕西西安710049

出　　处：《微机发展》2005年第12期9-11,共3页Microcomputer Development

摘　　要：在许多实际工程问题中经常遇到一些大型线形规划问题,通常的计算过程需要占用大量的计算时间,效率低下。文中提出了一种基于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.

关 键 词：BSP模型 PC集群 线性规划 并行算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]