Sparsity Propagation Analysis

██████ ██████ ██████
█····· █····█ █····█
██████ ██████ ██████
·····█ █····· █····█
██████ █····· █····█

About

This repository implements the Sparsity Propagation Analysis (SPA).

SPA is a static analysis capable of propagating structured sparsity in n-dimensional tensors within a computational graph, where nodes represent kernels such as general einsum expressions or addition operations.

For example, given a matrix multiplication with structured sparsity:

0000   1011   0000
1110 * 1011 = ?0??
0000   1011   0000
1110   0000   ?0??

SPA can infer the sparsity of the resulting matrix without actually performing the multiplication.

Furthermore, the analysis is not limited to matrices or matrix multiplication. It can be applied to n-dimensional tensors, general einsum expressions, and addition operations.

Dependencies

SPA is built on top of the Tensor Algebra Compiler. The project expects the taco library to be installed in ../taco relative to the root directory.

The project was implemented using Clang 14 Build Dependencies:

• CMake
• Ninja

How to build

1. Clone and build taco
2. Clone SPA

$ git clone https://github.com/lac-dcc/adlet

3. Build

$ mkdir build && cd build
$ cmake -G Ninja ../ && ninja

Running tests

Once built, you can run the test files:

$ ./tests

Artifact

The artifact will generate the data and figures used in the paper using Docker.

Build the image:

docker build -t spa-artifact .

Run the experiments:

docker run -d -v $(pwd)/results:/app/results --rm --name spa-experiments spa-artifact

By default, the artifact generates all 6 figures in the /results/ directory using the average of 5 iterations for each.

It is possible to specify the figures and the number of executions:

docker run -d \
  -v $(pwd)/results:/app/results \
  --rm \
  --name spa-experiments \
  spa-artifact \
  --figures 7,10,12 \
  --repeat 10

Contributing

Contributions are welcome!

You'll need pre-commit for contributing to the project.

After installation, run:

$ pre-commit install