Paper Info
Title
Mixed-Precision Parallel Linear Programming Solver
Abstract
We use mixed-precision technique, which is used to exploit the high single precision performance of modern processors, to build the first sparse mixed-precision linear programming solver on the Cell BE processor. The technique is used to enhance the performance of an LP IPM-based solver by implementing mixed-precision sparse Cholesky factorization, the most time consuming part of LP solvers. Moreover, we implemented sparse matrix multiplication of the form required by the solver as it is also very time consuming for some LP problems. Implemented on the Cell BE processor (Playstation 3) and tested using Netlib data sets, our LP solver achieved a maximum speedup of 2.9 just by using the mixed-precision technique. Moreover, we found that some problems, especially in final iterations, result in ill-conditioned matrices where mixed-precision can not be used. As a result, the solver needs to switch to double-precision if a more accurate solution of an LP problem is required.
Year
DOI
Venue
2010
10.1109/SBAC-PAD.2010.14
Computer Architecture and High Performance Computing
Keywords
Field
DocType
linear programming,parallel programming,Cell BE processor,LP IPM based solver,mixed precision parallel linear programming,mixed precision technique,sparse Cholesky factorization,sparse matrix multiplication,Cell BE processor,Cholesky factorization,Linear Programming,Mixed-precsision
Single-precision floating-point format,Computer science,Matrix (mathematics),Netlib,Parallel computing,Linear programming,Solver,Sparse matrix,Speedup,Cholesky decomposition
Conference
ISSN
ISBN
Citations 
1550-6533 E-ISBN : 978-0-7695-4216-4
978-0-7695-4216-4
1
PageRank 
References 
Authors
0.36
8
2
Name
Order
Citations
PageRank
Mujahed Eleyat172.98
Lasse Natvig210919.61