Title:	DSP algorithm design space exploration
DNr:	LiU-compute-2023-23
Project Type:	LiU Compute
Principal Investigator:	Oscar Gustafsson <oscar.gustafsson@liu.se>
Affiliation:	Linköpings universitet
Duration:	2023-08-15 – 2024-02-01
Classification:	20205
Keywords:

Abstract

We are currently performing design space explorations for some basic DSP algorithms. Despite being well established, only a small subset of the possible options are covered in the literature and the goal is to provide both fundamental understanding of the bounds and also provide better algorithms and architectures for these. One possible reason that this has not been done before is that these are large combinatorial problems. For example, the number of possible 2^N-point FFT-architectures are O((N!)^N). While we have developed techniques and identified patterns to reduce the search space significantly, we have also reached a situation where we need more compute resources to continue in a reasonable way. The three day limit may pose a problem (and we do not really have a good estimate for the expected run-time for the different cases), but as the problems are easy to parallelize, it is worth giving it a go (and also enable the possibility to continue a run at a later stage). The other problems will be solved by integer programming. The primary three problems are: Streaming FFT-architectures Fast FIR filter algorithms for symmetric filters FFT algorithms although there are some variants that may also be considered given that there are resources remaining and/or we hit another run time limit.