Non-homongeneous Linear Stencils (NHLS)

Fast Fourier transform acceleration for inhomogenous linear stencil computations. Please see / cite

@inproceedings{bentley2025applying,
  title={Applying Fast Fourier Transforms to Accelerate Spatially and Temporally Inhomogeneous Stencil Computations},
  author={Bentley, Russell and Chowdhury, Rezaul and Gregory, Aaron and Santomauro, Michael},
  booktitle={Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures},
  pages={17--33},
  year={2025}
}

Example

A number of example executables are included that demonstrate different linear stencil problems and solvers. They provide a CLI interface, try using --help for more information. Consider this example where we generate a short animation of a time-varying stencil computation.

cargo run \
    --example tv_rotating_2d \
    --release \
    -- \
    --wisdom-file target/tv_rotating_2d/wisdom \
    --write-images target/tv_rotating_2d \
    --plan-type measure \
    --domain-size 1000 \
    --steps-per-image 1000 \
    --images 31 \
    --ic-type impulse \
    --ic-dial 10 \
    --task-min 4 \
    --task-mult 2 \
    --threads 8
    
cd target/tv_rotating_2d
ffmpeg \
	-framerate 30 \
	-pattern_type glob -i 'frame_*.png' \
	-c:v libx264 \
	-pix_fmt yuv420p \
	out.mp4
open out.mp4

For Developers

NHLS requires using the nightly Rust toolchain. Please refer to the official Install Rust guide for obtaining rustup, the rust toolchain manager. All changes should be made through pull requests, which must pass CI.

Cargo Commands

To build the library use

cargo build           # Debug build
cargo build --release # Release Build

Note that the first time you build a project, all the dependencies need to be downloaded and built as well. This is mostly a one time expense, as these will all be saved locally.

Tests can be run with

cargo test

Documentation for our library and our dependencies can be generated with

cargo doc
cargo doc --open # Opens the index.html page

Cargo also includes a source formatter, which is required to pass CI

cargo fmt

Lastly, library projects can include example executables, included in the examples directory. For example, to run the file examples/example_1.rs

cargo run --example example_1  # Debug 

cargo run --release \          # Release, recommended
    --example example_1 \      # Runs examples/example_1.rs
    -- \                       # Args following -- are passed to example
    --example-arg1
    --example-arg2

Profiling

NHLS and the fftw3-bindings are instrumented with macros from the profiling crate. When built with the profiling-with-puffin feature, examples become clients for the Puffin profiler. In the following example we profile heat_2d_ap_fft using puffin_viewer.

# Start the puffin viewer.
# You can run it from source with:
# Run in the background, or on another terminal
puffin_viewer&

# Here we run an expensive operation
cargo run \
    --example heat_2d_ap_fft \
    --release \
    --features profile-with-puffin \  # The image_*_example start a puffin client
    -- \
    --domain-size 4000 \
    --steps-per-image 4000 \
    --images 2 \                      # We just want one solver application
    --threads 8

# Wait for the example to finish running.
# Sometimes the profiling takes a while to buffer before it starts streaming

Note that when building with the profile-with-puffin feature, executables will have an additional --puffin-url flag that can be used to set a custom url if the default one isn't preferred (127.0.0.1:8585).