Affine Modeling of Program Traces

Gabriel Rodriguez, Mahmut T. Kandemir, Juan Tourino

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 presents 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 statement 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 percent of the static control parts in PolyBench/C applications and 99.9 percent in the Pluto-tiled versions of these benchmarks.

Original languageEnglish (US)
Article number8408540
Pages (from-to)294-300
Number of pages7
JournalIEEE Transactions on Computers
Issue number2
StatePublished - Feb 1 2019

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Affine Modeling of Program Traces'. Together they form a unique fingerprint.

Cite this