Representing Integer Sequences Using Piecewise-Affine Loops

Gabriel Rodríguez, Louis-Noël Pouchet and Juan Touriño
Additional contact information
Gabriel Rodríguez: CITIC, Computer Architecture Group, Universidade da Coruña, 15071 A Coruña, Spain
Louis-Noël Pouchet: Department of Computer Science, Colorado State University, Fort Collins, CO 80523, USA
Juan Touriño: CITIC, Computer Architecture Group, Universidade da Coruña, 15071 A Coruña, Spain

Mathematics, 2021, vol. 9, issue 19, 1-29

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 10 6 and 10 3 with respect to gzip for the original and tiled versions of the traces, respectively.

Keywords: program modeling; optimizing compilers; polyhedral optimization; memory traces (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/19/2368/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/19/2368/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:19:p:2368-:d:642071

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().