Tadashi: Enabling AI-Based Automated Code Generation With Guaranteed Correctness

Emil Vatai, Aleksandr Drozd, Ivan R. Ivanov, Yinghao Ren, Mohamed WahibarXiv 2024 · DOI · arXiv

Introduction

Optimizing nested loops for modern hardware is a complex task, often requiring expert knowledge in compiler theory. While Machine Learning (ML) and Large Language Models (LLMs) offer promising automated solutions for code generation, they suffer from a "black-box" reliability problem. An AI-suggested optimization might yield significant speedups but could inadvertently alter program logic, rendering the result useless. Current verification methods, like unit testing, can prove the presence of bugs but not their absence.

The Tadashi Framework

Tadashi is an end-to-end Python library designed to bridge the gap between ML-driven optimization and formal code verification. It utilizes the polyhedral model—a mathematical framework representing loop nests as multi-dimensional points—to provide formal guarantees of correctness. By treating loop nests as hierarchical "schedule trees," Tadashi allows AI agents to manipulate code structure while ensuring the resulting program remains functionally identical to the original.

Internal logic of the Tadashi system, illustrating the path from input code to verified output via dependency analysis.

Key Components

  • Pythonic Interface: Tadashi provides a high-level Python front-end to complex C++ polyhedral libraries like ISL and PET, making it accessible to ML researchers.
  • Formal Legality Checking: Every proposed transformation (e.g., tiling, fusing, or interchanging loops) undergoes rigorous dependency analysis. Transformations are only accepted if they are "lexicographically positive," ensuring no data dependencies are violated.
  • Code Generation: Once a legal and high-performing schedule is identified, Tadashi automatically generates optimized C code.

Methods and Integration

Tadashi acts as a "safe sandbox" for AI agents. It allows models to be as aggressive or creative as desired, acting as a referee that instantly rejects illegal moves. This enables the use of various search strategies, such as Monte-Carlo Tree Search (MCTS) and Genetic Programming (GP), to explore the massive space of possible code transformations.

The end-to-end workflow of Tadashi, illustrating the integration of various ML models with formal verification and code generation.

Evaluation and Results

The researchers evaluated Tadashi using standard benchmarks (Polybench/C 4.2.1) and real-world applications like the FDTD electromagnetic simulation kernel and miniAMR physics simulations.

Key findings include:

  • Significant Performance Gains: Simple ML search strategies built on Tadashi achieved dramatic improvements, such as a 31x speedup for Correlation and 34.6x for Covariance kernels. The FDTD simulation saw a 13x speedup.
  • Guaranteed Correctness: In all tests, the transformed code produced bit-for-bit identical results to the original, empirically verifying the system's formal guarantees.
  • High Throughput: The system is lightweight enough to sustain hundreds of iterations per second, making it practical for high-scale ML training cycles.

Conclusion and Future Work

Tadashi demonstrates that formal verification can be integrated into AI-driven code generation without sacrificing performance or flexibility. While currently limited to "Static Control Parts" (SCoPs), future work aims to expand support for more complex code structures and scale the system for larger High-Performance Computing (HPC) clusters to discover optimizations beyond current compiler literature.

Summary updated

Abstract

Frameworks and domain-specific languages for auto-generating code have traditionally depended on human experts to implement rigorous methods ensuring the legality of code transformations. Recently, machine learning (ML) has gained traction for generating code optimized for specific hardware targets. However, ML approaches-particularly black-box neural networks-offer no guarantees on the correctness or legality of the transformations they produce. To address this gap, we introduce Tadashi, an end-to-end system that leverages the polyhedral model to support researchers in curating datasets critical for ML-based code generation. Tadashi provides an end-to-end system capable of applying, verifying, and evaluating candidate transformations on polyhedral schedules with both reliability and practicality. We formally prove that Tadashi guarantees the legality of generated transformations, demonstrate its low runtime overhead, and showcase its broad applicability. Tadashi available at https://github.com/vatai/tadashi/.
BibTeX
@misc{vatai2024tadashi,
  author = {Emil Vatai and Aleksandr Drozd and Ivan R. Ivanov and Yinghao Ren and Mohamed Wahib},
  title = {{Tadashi: Enabling AI-Based Automated Code Generation With Guaranteed Correctness}},
  year = {2024},
  eprint = {2410.03210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.03210},
}
Figure