Title :
Cache-aware matrix multiplication on multicore systems for IPM-based LP solvers
Author :
Eleyat, Mujahed ; Natvig, Lasse ; Amundsen, Jørn
Author_Institution :
Miriam AS, NTNU, Trondheim, Norway
Abstract :
We profile GLPK, an open source linear programming solver, and show empirically that the form of matrix multiplication used in interior point methods takes a significant portion of the total execution time when solving some of the Netlib and other LP data sets. Then, we discuss the drawbacks of the matrix multiplication algorithm used in GLPK in terms of cache utilization and use blocking to develop two cache-aware implementations. We apply OpenMP to develop parallel implementations with load balancing. The best implementation achieved a median speedup of 21.9 when executed on a 12-core AMD Opteron.
Keywords :
application program interfaces; cache storage; digital arithmetic; linear programming; matrix multiplication; multiprocessing systems; resource allocation; 12-core AMD Opteron; GLPK; IPM-based LP solvers; Netlib; OpenMP; cache utilization; cache-aware matrix multiplication; interior point methods; load balancing; multicore systems; open source linear programming solver; Arrays; Multicore processing; Partitioning algorithms; Program processors; Sparse matrices; Symmetric matrices; Vectors; cache optimization; interior point methods; multicore systems; sparse matrix multiplication;
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2011 Federated Conference on
Conference_Location :
Szczecin
Print_ISBN :
978-1-4577-0041-5
Electronic_ISBN :
978-83-60810-35-4
