AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels

• URL: http://arxiv.org/abs/2604.05066v1
• Date: Mon, 06 Apr 2026 18:12:39 GMT
• Title: AutoLALA: Automatic Loop Algebraic Locality Analysis for AI and HPC Kernels
• Abstract summary: AutoLALA is an open-source tool that analyzes data locality in affine loop programs.<n>It produces closed-form symbolic formulas for reuse distance and data movement complexity.
• Score: 6.223124502234209
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Data movement is the primary bottleneck in modern computing systems. For loop-based programs common in high-performance computing (HPC) and AI workloads, including matrix multiplication, tensor contraction, stencil computation, and einsum operations, the cost of moving data through the memory hierarchy often exceeds the cost of arithmetic. This paper presents AutoLALA, an open-source tool that analyzes data locality in affine loop programs. The tool accepts programs written in a small domain-specific language (DSL), lowers them to polyhedral sets and maps, and produces closed-form symbolic formulas for reuse distance and data movement complexity. AutoLALA implements the fully symbolic locality analysis of Zhu et al. together with the data movement distance (DMD) framework of Smith et al. In particular, it computes reuse distance as the image of the access space under the access map, avoiding both stack simulation and Denning's recursive working-set formulation. We describe the DSL syntax and its formal semantics, the polyhedral lowering pipeline that constructs timestamp spaces and access maps via affine transformations, and the sequence of Barvinok counting operations used to derive symbolic reuse-interval and reuse-distance distributions. The system is implemented in Rust as a modular library spanning three crates, with safe bindings to the Barvinok library. We provide both a command-line interface and an interactive web playground with LaTeX rendering of the output formulas. The tool handles arbitrary affine loop nests, covering workloads such as tensor contractions, einsum expressions, stencil computations, and general polyhedral programs.

Related papers

• Quantifying Memory Use in Reinforcement Learning with Temporal Range [51.98491034847041]
  Temporal Range is a model-agnostic metric that treats first-order sensitivities of multiple vector outputs across a temporal window to the input sequence as a temporal influence profile.<n>We also report Temporal Range for a compact Long Expressive Memory (LEM) policy trained on the task, using it as a proxy readout of task-level memory.
  arXiv  Detail & Related papers  (2025-12-05T22:58:09Z)
• On the Holographic Geometry of Deterministic Computation [0.0]
  Standard simulations of Turing machines suggest a linear relationship between the temporal duration $t$ of a run and the amount of information that must be stored at time $t$.<n>We show that any length-$t$ run can be simulated using $O(sqrtt)$ work-tape cells via a Height Compression Theorem for succinct trees together with an Algebraic Replay Engine.
  arXiv  Detail & Related papers  (2025-11-29T19:47:22Z)
• From Loop Nests to Silicon: Mapping AI Workloads onto AMD NPUs with MLIR-AIR [6.2957456904504525]
  General-purpose compilers abstract away parallelism, locality, and synchronization, limiting their effectiveness on modern spatial architectures.<n>We introduce MLIR-AIR, a novel, open-source compiler stack built on MLIR.<n>We demonstrate MLIR-AIR's capabilities through two case studies: matrix multiplication and the multi-head attention block from the LLaMA 2 model.
  arXiv  Detail & Related papers  (2025-10-16T16:49:05Z)
• MAP: Memory-aware Automated Intra-op Parallel Training For Foundation Models [15.256207550970501]
  We introduce MAP, a compiler built upon PyTorch to implement Memory-aware Automated Parallelization. Compared with existing methods, MAP provides an easy-to-use symbolic profiler to generate memory and computing statistics of an arbitrary PyTorch model.
  arXiv  Detail & Related papers  (2023-02-06T07:22:49Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  We tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing algorithms are applicable. The challenges for designing an FL algorithm for X-risks lie in the non-decomability of the objective over multiple machines and the interdependency between different machines.
  arXiv  Detail & Related papers  (2022-10-26T00:23:36Z)
• PARTIME: Scalable and Parallel Processing Over Time with Deep Neural Networks [68.96484488899901]
  We present PARTIME, a library designed to speed up neural networks whenever data is continuously streamed over time. PARTIME starts processing each data sample at the time in which it becomes available from the stream. Experiments are performed in order to empirically compare PARTIME with classic non-parallel neural computations in online learning.
  arXiv  Detail & Related papers  (2022-10-17T14:49:14Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  We present NumS, an array programming library which optimize NumPy-like expressions on task-based distributed systems. This is achieved through a novel scheduler called Load Simulated Hierarchical Scheduling (LSHS) We show that LSHS enhances performance on Ray by decreasing network load by a factor of 2x, requiring 4x less memory, and reducing execution time by 10x on the logistic regression problem.
  arXiv  Detail & Related papers  (2022-06-28T20:13:40Z)
• Learning Implicit Feature Alignment Function for Semantic Segmentation [51.36809814890326]
  Implicit Feature Alignment function (IFA) is inspired by the rapidly expanding topic of implicit neural representations. We show that IFA implicitly aligns the feature maps at different levels and is capable of producing segmentation maps in arbitrary resolutions. Our method can be combined with improvement on various architectures, and it achieves state-of-the-art accuracy trade-off on common benchmarks.
  arXiv  Detail & Related papers  (2022-06-17T09:40:14Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• High-performance symbolic-numerics via multiple dispatch [52.77024349608834]
  Symbolics.jl is an extendable symbolic system which uses dynamic multiple dispatch to change behavior depending on the domain needs. We show that by formalizing a generic API on actions independent of implementation, we can retroactively add optimized data structures to our system. We demonstrate the ability to swap between classical term-rewriting simplifiers and e-graph-based term-rewriting simplifiers.
  arXiv  Detail & Related papers  (2021-05-09T14:22:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.