Fast Linear Programming through Transprecision Computing on Small and Sparse Data

Tobias Grosser, Theodoros Theodoridis, Maximilian Falkenstein, Arjun Pitchanathan, Michael Kruse, Manuel Rigger, Zhendong Su, Torsten Hoefler

Research output: Contribution to journalArticlepeer-review

Abstract

A plethora of program analysis and optimization techniques rely on linear programming at their heart. However, such techniques are often considered too slow for production use. While today’s best solvers are optimized for complex problems with thousands of dimensions, linear programming, as used in compilers, is typically applied to small and seemingly trivial problems, but to many instances in a single compilation run. As a result, compilers do not benefit from decades of research on optimizing large-scale linear programming. We design a simplex solver targeted at compilers. A novel theory of transprecision computation applied from individual elements to full data-structures provides the computational foundation. By carefully combining it with optimized representations for small and sparse matrices and specialized small-coefficient algorithms, we (1) reduce memory traffic, (2) exploit wide vectors, and (3) use low-precision arithmetic units effectively. We evaluate our work by embedding our solver into a state-of-the-art integer set library and implement one essential operation, coalescing, on top of our transprecision solver. Our evaluation shows more than an order-of-magnitude speedup on the core simplex pivot operation and a mean speedup of 3.2x (vs. GMP) and 4.6x (vs. IMath) for the optimized coalescing operation. Our results demonstrate that our optimizations exploit the wide SIMD instructions of modern microarchitectures effectively. We expect our work to provide foundations for a future integer set library that uses transprecision arithmetic to accelerate compiler analyses.
Original languageEnglish
Article number195
Number of pages28
JournalProceedings of the ACM on Programming Languages
Volume4
Issue numberOOPSLA
DOIs
Publication statusPublished - 13 Nov 2020

Keywords

  • Simplex
  • Linear Programming
  • Transprecision
  • Presburger Arithmetic

Fingerprint

Dive into the research topics of 'Fast Linear Programming through Transprecision Computing on Small and Sparse Data'. Together they form a unique fingerprint.

Cite this