Hybrid Parallelization of Standard Full Tableau Simplex Method with MPI and OpenMP
作者： Basilis Mamalis , Marios Perlitis
关键词:
摘要: The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches have also extensively studied due to the intensive computations required, especially solution of large (LPs). In this paper we present a highly scalable implementation framework standard full tableau on hybrid parallel environment, which consists multiple multicore processing nodes interconnected via high-speed communication network. Specifically, designed and implemented suitable column-based distribution scheme, following three different parallelization models: (a) pure MPI (one process each core), (b) OpenMP-based (OpenMP constructs over cores node), (c) MPI-based (MPI 3.0 shared memory functions node). We then compare our (i) among other variable number nodes/cores problem size, (ii) recent valuable corresponding efforts literature. all cases scheme performs quite/much better than two schemes. Moreover, schemes lead particularly high speed-up efficiency values, whereas values are considerably ones achieved similar research implementations.
acm.org
sci-hub.se 参考文章(13)
Piotr Luszczek, Jack Dongarra, Reducing the time to tune parallel dense linear algebra routines with partial execution and performance modeling parallel processing and applied mathematics. pp. 730- 739 ,(2011) , 10.1007/978-3-642-31464-3_74
Rolf Rabenseifner, Gerhard Wellein, Comparison of Parallel Programming Models on Clusters of SMP Nodes HPSC. pp. 409- 425 ,(2005) , 10.1007/3-540-27170-8_31
J.A.J. Hall, K.I.M. McKinnon, ASYNPLEX, an asynchronous parallelrevised simplex algorithm Annals of Operations Research. ,vol. 81, pp. 27- 50 ,(1998) , 10.1023/A:1018957107705
Jiangning Qin, Duc T. Nguyen, A Parallel-Vector Simplex Algorithm on Distributed-Memory Computers Structural Optimization. ,vol. 11, pp. 405- 410 ,(1996) , 10.1007/978-3-642-79654-8_67
Miles Lubin, J. A. Julian Hall, Cosmin G. Petra, Mihai Anitescu, Parallel distributed-memory simplex for large-scale stochastic LP problems Computational Optimization and Applications. ,vol. 55, pp. 571- 596 ,(2013) , 10.1007/S10589-013-9542-Y
Gavriel Yarmish, Richard Van Slyke, A distributed, scaleable simplex method The Journal of Supercomputing. ,vol. 49, pp. 373- 381 ,(2009) , 10.1007/S11227-008-0253-6
I. Maros, G. Mitra, Investigating the sparse simplex algorithm on a distributed memory multiprocessor ieee international conference on high performance computing data and analytics. ,vol. 26, pp. 151- 170 ,(2000) , 10.1016/S0167-8191(99)00100-3
Kartik Krishnan Sivaramakrishnan, A parallel interior point decomposition algorithm for block angular semidefinite programs Computational Optimization and Applications. ,vol. 46, pp. 1- 29 ,(2010) , 10.1007/S10589-008-9187-4
Diego Klabjan, Ellis L. Johnson, George L. Nemhauser, A parallel primal–dual simplex algorithm Operations Research Letters. ,vol. 27, pp. 47- 55 ,(2000) , 10.1016/S0167-6377(00)00017-1
Angelo Sifaleras, Konstantinos Paparrizos, Nikolaos Samaras, Mahmoud Moussa, El-Said Badr, Some Computational Results on MPI Parallel Implementation of Dense Simplex Method World Academy of Science, Engineering and Technology, International Journal of Computer, Electrical, Automation, Control and Information Engineering. ,vol. 2, pp. 3856- 3859 ,(2008)