|
SPONSORS
|
||||
|
|
COLLABORATIONS
|
||||||||||
|
Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Publications of SPCL
| T. Grosser, T. Theodoridis, M. Falkenstein, A. Pitchanathan, M. Kruse, M. Rigger, Z. Su, T. 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. Vol , Nr. , ACM, Nov. 2020, ) Publisher Reference AbstractA 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.Documentsdownload article: access preprint on arxiv:  | ||
BibTeX | ||
| ||