NFFT.jl Restructuring

[tknopp]

I am working right now on splitting the abstract NFFT interface stuff into a new package AbstractNFFTs, which will allow us to switch implementations of the core algorithm. There are several motivations for it. One is that I would like to have a common interface for NFFT.jl and NFFT3.jl another more practical one is that right now NFFT.jl depends on CUDA.jl which adds 4 seconds of package load time, which is too much. We will therefore have a third package CuNFFT.jl, which implements CUDA NFFTs.

AbstractNFFTs.jl, NFFT.jl, and CuNFFT.jl will all remain in the same git repository which makes maintaining much easier. Tests, docu, ... will all be shared. But NFFT3.jl may implement the interface of AbstractNFFTs.jl without the need to depend on NFFT.jl

This is work in progress: Some TODO items

• formalize and finalize the interface of AbstractNFFTs.jl
• generalize the directional NFFT and make the standard one a special case of the directional
• improve tests to have a common set of tests executed on several backends
• write documentation
• write a benchmark suite that can exchange and compare backends
• register AbstractNFFTs.jl
• write NFFT3.jl wrapper
• register CuNFFT.jl
• make release of NFFT.jl
• extract NFFTTools.jl

[tknopp]

@mischmi96 @michaelquellmalz: The interface of AbstractNFFTs.jl is not set in stone, I want to change this to using the LinearAlgebra methods * and mul!. The constructor part also need some additional throughs.

Still I would like to get your input on the following: I am pretty sure that NFFT3.jl wants to stick with its default interface, which is a 1to1 mapping of the C interface. My idea would be to have an additional interface that basically wraps NFFT3.jl. It will be just a very thin wrapper that maps some function names and arguments.

The question now is where this wrapper should live. In my opinion it could be integrated in NFF3.jl, which would allow the end user to basically exchange NFFT.jl and NFFT3.jl. Of course NFFT.jl and NFFT3.jl have their own unique functionality and I thus refer just to the most common NFFT functionality.

[JeffFessler]

Having a common interface sounds great. Following the AbstractFFT approach of supporting mul! seems reasonable. I will likely continue to wrap my own LinearMap* around fft! and nfft! anyway to facilitate operator products and stacks, so the mul! functionality is less important to me, but it is likely helpful for some users.

Maybe someday this could all go side-by-side with FFTW and AbstractFFT in https://github.com/JuliaMath?

[tknopp]

Maybe someday this could all go side-by-side with FFTW and AbstractFFT in https://github.com/JuliaMath?

Yes that sounds good from my side. I am just not sure I want these split into multiple git repositories. Keeping things together seems to be easier for now.

[tknopp]

And just for the records what we gain by this:

julia> @time using NFFT
  2.061486 seconds (2.89 M allocations: 176.794 MiB, 2.47% gc time, 56.64% compilation time)

julia> @time using CuNFFT
  4.726514 seconds (12.69 M allocations: 809.155 MiB, 9.92% gc time, 29.53% compilation time)

So NFFT gets more lightweight again.

[JakobAsslaender]

That all sounds like a good idea! I am wondering though, how we would go about the Toeplitz constructors. It would be nice, if one could switch out the NFFT implementation that is used to construct the Kernel. Should that live in AbstractNFFT? If done right, it would allow to switch out both NFFT implementation used in the constructor, as well as the FFT implementation used in mul! (right now FFTW is hard-coded).

[tknopp]

No, that remains in NFFT.jl. Think of NFFT.jl to be right now two parts

1. the Julia CPU implementation of AbstractNFFTs
2. high level operations acting on the AbstractNFFTs interface
   We might want to split these two into two packages / modules but I am not entirely sure there. That decision can be deferred until the other things have settled.

[tknopp]

Hi @mischmi96 @michaelquellmalz:

I now have implemented an NFFT3.jl wrapper implementing the current AbstractNFFTPlan interface. It works really great, we can now simply exchange the plan and I even made the plan interface the same such that it is really generic. The implementation can be found here:

https://github.com/tknopp/NFFT.jl/blob/master/test/NFFT3.jl

The question remains if we want to transfer this to your repository at some point. Two other things I would like to get you input:

• As indicated elsewhere, NFFT3 (or NFFT.jl?) has a column/ row-major issue. I now solved this by reversing N but I also needed to reverse the nodes. I think this is faster than permutdims on the vectors.
• I tried to make the plan not allocate so that the Julia buffers can be reused, which is important for performance comparisons. But I do not understand why I need this line: https://github.com/tknopp/NFFT.jl/blob/master/test/NFFT3.jl#L67 can it be that still a buffer is allocated?

[mischmi96]

Hi @tknopp, thank you for your efforts and apologize my inactivity. However, I am handing in my PhD thesis in the next few weeks and that really takes up all of my time at the moment.

I would very much like a common interface and we can of course transfer it to the repository. At some point you asked about precomputations: they are done when setting the nodes. Our interface uses the memory allocated by C for everything. This is also causing the difference for row- and column major. We can think about adding a choice wether to use C or Julia allocated memory.

[tknopp]

Thanks! No hurry. Things can evolve gradually. I would like to make AbstractNFFTs a joint effort that we both are satisfied with. While I of course also push the pure Julia implementation, I think for the Julia community a pluggable interface is what counts.
I wish you the best for finalizing the thesis!

[tknopp]

The restructuring runs quite smoothly and I am quite satisfied now. I moved the Toeplitz and sampling density functions into a new package NFFTTools.jl that still needs to be registered. With that I have accomplished my goal. It will be possible to use

using NFFT, NFFTTools

which will use our own NFFT in the Toeplitz code, or use

using NFFT3, NFFTTools

which will use the NFFT3 code. The only missing bit for that is that we need to move the NFFT wrapper to NFFT3.jl. Thats it.

[tknopp]

This starts to make really fun. I just wrote a wrapper for FINUFFT:
https://github.com/JuliaMath/NFFT.jl/blob/master/Wrappers/FINUFFT.jl
Certainly not perfect but it passes tests! So we have already four different NFFT implementations that can be used via AbstractNFFTs.jl.

[ahbarnett]

Cool! Curious about the CPU benchmark comparison when you get a chance... PS see my interface design responses here: ludvigak/FINUFFT.jl#38 (comment)

[mischmi96]

My thesis is handed in now, so I have spare time for the NFFT :)

Very impressive work! It is great to be able to switch out the different implementations. The performance comparison is also very interesting. However, the only thing that remains is basically to move the wrapper?