Publications of Torsten Hoefler

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

Fast Linear Programming through Transprecision Computing on Small and Sparse Data

(OOPSLA '20: Proceedings of the ACM international conference on Object oriented programming systems languages and applications. ACM, Nov. 2020)

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 seemingly trivial problems – but many instances in a single compilation run. As a result, compilers do not benefit from the decades of research on optimizing large-scale linear programming. We design a simplex solver targeted at compilers. A novel theory of transprecison 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 (a) reduce memory traffic, (b) exploit wide vectors, and (c) 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 orders-of-magnitude speedup on the core simplex pivot and a 6.3x runtime reduction for the optimized operation. Our results demonstrate that optimizations for low dimensionality and small (often zero) coefficients exploit the wide SIMD instruction of modern microarchitectures effectively. By providing a highly-optimized key operation we lay new foundations for the development of next-generation integer arithmetic libraries that will power future compiler analysis and optimization frameworks.

Documents

download article:

BibTeX

@article{,
  author={Tobias Grosser and Theodoros Theodoridis and Maxmilian Falkenstein and Arjun Pitchanathan and Michael Kruse and Manuel Rigger and Zhendong Su and Torsten Hoefler},
  title={{Fast Linear Programming through Transprecision Computing on Small and Sparse Data}},
  journal={OOPSLA '20: Proceedings of the ACM international conference on Object oriented programming systems languages and applications},
  year={2020},
  month={Nov.},
  publisher={ACM},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 3.15.186.56:42926	© Torsten Hoefler