Accelerating the Regina Network Flow Simulator on Multi-core Systems

Abstract

Emerging multi-core processors, which came as a result of manufacturers inability to keep increasing the frequency of single core processors, represent a great but also challenging opportunity to accelerate compute-intensive applications. Challenges are related to the fact that not all time-consuming applications are easy to parallelize efficiently. In addition to that, emerging multi-core systems have different architectures and efficient utilization still requires the programmer to have deep knowledge of the architecture of the target multi-core system, which also strongly raises the issue of portability.

The main goal of this thesis is to investigate the use of the inherent parallelism of multi-core systems to accelerate a gas flow simulator called MIRIAM Regina and developed by a company called Miriam AS. MIRIAM Regina spends most time solving a series of sparse linear programming (LP) problems. Therefore, most of the research was focused on building an IPM-based parallel LP solver and testing it using different architectures with different characteristics. The solver was first tested using the heterogeneous Cell BE processor found in PlayStation 3, which was of high interest to Miriam AS because of its high “FLOP/dollar” ratio. We have also tested the solver on the 2 x 6-core AMD Opteron processor (Istanbul), a good representative of the large class of modern homogeneous multicore processors.

We started with a serial IPM-based implementation that is part of the GLPK solver. Inaddition, we justified using interior point methods for solving these problems which consequently lead our research to investigating ways to enhance the efficiency of sparse Cholesky factorization. The main focus was how to parallelize Cholesky factorization and utilize cache efficiently. Moreover, a new method has been suggested to enhance the amalgamation of small blocks and to create bigger blocks to reduce the overhead of processing small tasks. The data sets provided by the company were too small to give any significant speedup and large data sets were not available. Therefore, we tested our solver using some large NETLIB problems and were able to accelerate the solution of them.

For some customers, MIRIAM Regina also spends relatively long time finding the maximum flow in a network under upper and lower flow constraints on each pipe. We suggest a heuristic to find a near optimal solution and investigate a way to parallelize the method. Both the heuristic and its parallelization were implemented and tested on the 2 x 6-core AMD Opteron processor (Istanbul).