Representing Integer Sequences Using Piecewise-Affine Loops
| Autor: | Louis-Noël Pouchet, Juan Touriño, Gabriel Rodríguez |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Source code
Computer science General Mathematics media_common.quotation_subject Polyhedral optimization computer.software_genre memory traces Memory traces program modeling Memory address optimizing compilers QA1-939 Computer Science (miscellaneous) Algebraic number Representation (mathematics) Engineering (miscellaneous) polyhedral optimization media_common TRACE (psycholinguistics) Integer sequence Program modeling Compiler Affine transformation computer Algorithm Mathematics Optimizing compilers |
| Zdroj: | RUC. Repositorio da Universidade da Coruña instname Mathematics, Vol 9, Iss 2368, p 2368 (2021) Mathematics Volume 9 Issue 19 |
| Popis: | This article belongs to the Special Issue Current Trends in Computer Architecture and High Performance Computing (HPC) with Their Mathematical Foundations [Abstract] A formal, high-level representation of programs is typically needed for static and dynamic analyses performed by compilers. However, the source code of target applications is not always available in an analyzable form, e.g., to protect intellectual property. To reason on such applications, it becomes necessary to build models from observations of its execution. This paper details an algebraic approach which, taking as input the trace of memory addresses accessed by a single memory reference, synthesizes an affine loop with a single perfectly nested reference that generates the original trace. This approach is extended to support the synthesis of unions of affine loops, useful for minimally modeling traces generated by automatic transformations of polyhedral programs, such as tiling. The resulting system is capable of processing hundreds of gigabytes of trace data in minutes, minimally reconstructing 100% of the static control parts in PolyBench/C applications and 99.99% in the Pluto-tiled versions of these benchmarks. As an application example of the trace modeling method, trace compression is explored. The affine representations built for the memory traces of PolyBench/C codes achieve compression factors of the order of 106 and 103 with respect to gzip for the original and tiled versions of the traces, respectively. This research was supported by the Ministry of Science and Innovation of Spain (grant PID2019-104184RB-I00/AEI/10.13039/501100011033), and by Xunta de Galicia and FEDER funds of the EU (CITIC—Centro de Investigación de Galicia accreditation, grant ED431G 2019/01; Consolidation Program of Competitive Reference Groups, grant ED431C 2021/30). Xunta de Galicia; ED431G 2019/01 Xunta de Galicia; ED431C 2021/30 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|