Scaling performance of interior-point method on large-scale chip multiprocessor system

ABSTRACT

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.

This paper proposes and evaluates several algorithmic and hardware features to improve IPM parallel performance on large-scale CMPs. Through detailed simulations, we demonstrate how exploring multiple levels of parallelism with hardware support for low overhead task queues and parallel reduction enables IPM to achieve up to 48X parallel speedup on a 64-core CMP.

REFERENCES

• 1: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'Excellent , Jacko Koster, A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.15-41, 2001 [doi>10.1137/S0895479899358194]
• 2: Robert E. Bixby, Solving Real-World Linear Programs: A Decade and More of Progress, Operations Research, v.50 n.1, p.3-15, January 2002 [doi>10.1287/opre.50.1.3.17780]
• 3: {Czyzyk96} J. Czyzyk, S. Mehrotra, and S. J. Wright. PCx User Guide. Technical Report OTC 96/01, Optimization Technology Center, Argonne National Lab and Northwestern University, May 1996.
• 4: {Eckstein92} J. Eckstein, R. Qi, V. I. Ragulin and S. A. Zenios. Data parallel implementation of dense linear programming algorithms. Technical Report TMC-230, Thinking Machines Corporation, Cambridge, MA, 1992.
• 5: María Jesús Garzarán , Milos Prvulovic , Ye Zhangy , Josep Torrellas , Alin Jula , Hao Yu , Lawrence Rauchwerger, Architectural Support for Parallel Reductions in Scalable Shared-Memory Multiprocessors, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.243, September 08-12, 2001
• 6: {Gay88} D. M. Gay. Electronic Mail Distribution of Linear Programming Test Problems. In Committee on Algorithms Newsletter, No. 13, pages 10--12.
• 7: {Gochman06} S. Gochman, A. Mendelson, A. Naveh, E. Rotem. Introduction to Intel® Core#8482; Duo Processor Architecture. Intel Technology Journal, Volume 10, Issue 2, 2006.
• 8: Michael Gschwind, Chip multiprocessing and the cell broadband engine, Proceedings of the 3rd conference on Computing frontiers, p.1-8, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128023]
• 9: {Gondzio04} Gondzio, J. and A. Grothey. Exploiting Structure in Parallel Implementation of Interior Point Methods for Optimization. Technical Report MS-04-004, School of Mathematics, The University of Edinburgh, 2004.
• 10: A. Gottlieb , R. Grishman , C. P. Kruskal , K. P. McAuliffe , L. Rudolph , M. Snir, The NYU Ultracomputer Designing an MIMD Shared Memory Parallel Computer, IEEE Transactions on Computers, v.32 n.2, p.175-189, February 1983 [doi>10.1109/TC.1983.1676201]
• 11: {Gupta00} A. Gupta. WSMP: Watson Sparse Matrix Package (Part-II: Direct Solution of General Sparse Systems). Technical Report RC 21888 (98472), IBM T. J. Watson Research Center, 2000.
• 12: George Karypis , Anshul Gupta , Vipin Kumar, A parallel formulation of interior point algorithms, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C. [doi>10.1145/602770.602808]
• 13: {Karypis98} G. Karypis and V. Kumar. METIS - A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 4.0. University of Minnesota, 1998.
• 14: Daehyun Kim , Mainak Chaudhuri , Mark Heinrich, Active Memory Techniques for ccNUMA Multiprocessors, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.10.2, April 22-26, 2003
• 15: {Koka04} P. Koka, T. Suh, M. Smelyanskiy, R. Grzeszczuk, and C. Dulong. Construction and Performance Characterization of Parallel Interior Point Solver on 4-way Intel Itanium Multiprocessor System. IEEE 7th Annual Workshop on Workload Characterization (WWC-7), 2004.
• 16: Sanjeev Kumar , Christopher J. Hughes , Anthony Nguyen, Carbon: architectural support for fine-grained parallelism on chip multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 17: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 18: Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , W. Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong-Chan , Shaw-Wen Yang , Robert Zak, The network architecture of the connection machine CM-5, Journal of Parallel and Distributed Computing, v.33 n.2, p.145-158, March 15, 1996 [doi>10.1006/jpdc.1996.0033]
• 19: Xiaoye Sherry Li , James W. Demmel, Sparse gaussian elimination on high-performance computers, University of California, Berkeley, 1996
• 20: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 21: {Lustig92} J. Lustig and G. Li. An implementation of parallel primal and dual interior-point method for block structured linear programs. Computational Optimization and Applications (COAP), 1 (1992)141--161.
• 22: {Lustig96} I. J. Lustig and E. Rothberg. Gigaflops in Linear Programming. Operations Research Letters, 18(4): 157--165, 1996.
• 23: {MKL07}Inte® Math Kernel Library Reference Manual, 2007
• 24: Esmond G. Ng , Barry W. Peyton, Block sparse Cholesky algorithms on advanced uniprocessor computers, SIAM Journal on Scientific Computing, v.14 n.5, p.1034-1056, Sept. 1993 [doi>10.1137/0914063]
• 25: {Nocedal06} J. Nocedal and S. J. Wright. Numerical Optimization, Springer, 2nd edition, 2006.
• 26: E. Rothburg , A. Gupta, An efficient block-oriented approach to parallel sparse Cholesky factorization, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.503-512, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169791]
• 27: {Schenk00} O. Schenk. Scalable Parallel Sparse LU Factorization Methods on Shared memory Multiprocessors. Ph.D. Dissertation, Swiss Federal Institute of Technology, Zurich, Switzerland, 2000.