Scaling performance of interior-point method on large-scale chip multiprocessor system
Mikhail Smelyanskiy, Victor W. Lee, Daehyun Kim, Anthony D. Nguyen, Pradeep Kumar Dubey · 2007
In this paper we describe parallelization of interior-point method (IPM) aimed at achieving high scalability on large-scale chip-multiprocessors (CMPs). IPM is an important computational technique used to solve optimization problems in many areas of science, engineering and finance. IPM spends most of its computation time in a few sparse linear algebra kernels. While each of these kernels contains a large amount of parallelism, sparse irregular datasets seen in many optimization problems make parallelism difficult to exploit. As a result, most researchers have shown only a relatively low scalability of 4X-12X on medium to large scale parallel machines.