Asymptotic Speedups for Free through Automatic Incremental Computing

Introduction

The energy consumption of data centers and ICT devices grows at an alarming rate and will be responsible for up to 20% of the global energy consumption by 2030. To sustain the ongoing digital transformation, we must find ways to run software dramatically more efficiently. A promising direction is incremental computing.

Incremental Computing

Incremental computations react to input changes rather than recomputing their result from scratch, which is known to deliver asymptotic speedups in theory and order-of-magnitude speedups in practice. However, current approaches to incrementality have limited applicability:

1. They either require expert knowledge,
2. Only support specialized domains (e.g., database queries),
3. Or only yield modest speedups.

The goal of this project is to develop a methodology for automatically incrementalizing computations and significantly improving their time and energy efficiency.

Project Overview

The AutoInc project achieves this ambitious goal by establishing a novel foundation for incremental computing in three complementary parts:

1. Incremental Operators: The project develops a library of incremental operators for atomic and other essential data types as part of a novel framework of differential theories, which ensure the correctness and composability of the operators.

2. Intermediate Representation: The project designs a low-level intermediate representation (IR) for describing compositional incremental computations as computation networks and provides a novel differential recomputing semantics for the IR.

3. Optimizing Compiler: The project develops an optimizing compiler that translates existing code to the low-level incremental IR and uses operators from differential theories where possible.

Each part is useful in its own right, but together AutoInc enables developers to automatically incrementalize the reactive parts of existing programs.

Expected Outcomes

Besides improving the efficiency of programs, this project will produce fundamental insights about the nature and limits of automatic incremental computing.