JuliaMath / JuliaMath/NFFT.jl

Implement Autotuning of Kernel Size and Oversampling Parameter

Open
#104 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
156
Forks
29
Avg merge
8h 57m
Merged PRs (30d)
1

Description

Right now NFFT.jl gives the user no hint on how to chose the kernel size and the oversampling parameter. This was on purpose since I don't want too much "magic" within the code. Keeping `m` and `sigma` static has the additional advantage that it allows to compare different libraries on a fine level and understand bottlenecks better.

However, for the enduser we need an automatic parameter selection. The idea is that the user inputs the desired accuracy and then `m` and `sigma` are chosen to give the best performance. The tasks to be implemented are:
* **Good accuracy model:** There currently is the function `https://github.com/JuliaMath/NFFT.jl/blob/master/AbstractNFFTs/src/misc.jl#L55`, which, however needs to be adapted. I am not sure if we can / should take literature accuracy bounds here or just develop a generic cost model and tune that in a data driven fashion. This means developing some function `` gamma*(alpha / sigma)^(beta*m)`` and tune the parameters gamma, alpha and beta.
* **Performance model:** We then need some performance model. Here I am right now not sure, how much heuristics and how much measurements we should do. A measurement would sweep over the kernel size and automatically chose the appropriate oversampling factor. This would be similar to `FFTW_MEASURE`. I would, however, also like some heuristic `FFTW_ESITMATE` like code.

These are my initial thoughts. `ducc` has an implementation for this here: https://gitlab.mpcdf.mpg.de/mtr/ducc/-/blob/ducc0/src/ducc0/nufft/nufft.h#L147

Here is a small explanation from @mreineck regarding their idea:

>To determine the oversampling factor I'm using a simple cost model: the higher the oversampling factor, the more expensive the FFT, but the lower the kernel support and therefore the gridding/degridding cost. For all the possible oversampling factors I estimate the computation time using heuristic formulas and pick the one that is expected to run fastest.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.