CUDA: 在CUDA中进行一维立方样条插值

Question

我正在制作一台医学成像设备。我想使用CUDA来使设备更快。

我从CCD接收到1024个大小为1d的数据，这样重复了512次。 在我执行IFFT之前， 我必须对每个1024大小的数据应用高性能插值算法（如三次样条插值）， 然后是1d插值512次。

1. 是否有任何CUDA库可以执行三次样条插值？ （我发现有一个库，但它适用于2或3维图像。 由于我需要执行其他复杂的滤波功能，我需要数据存在全局内存中，而不是纹理内存。）

2. 是否有任何NUFFT（非均匀快速傅里叶变换）库（不需要编写CUDA）？ 我认为如果我有NUFFT函数，我就不必分别进行插值和IFFT，可以使设备更快。

- user1431861

---

这里有一个关于优化CUDA内核插值非均匀节点的讨论Optimizing CUDA kernel interpolation with nonuniform node points，或许对您有所帮助。 - Vitality

Answer 1

由于有更多人提出这个问题，我已经扩展了我的CUDA三次插值代码，加入了1D三次插值。您可以在此处找到更新后的代码：http://www.dannyruijters.nl/cubicinterpolation/

一个包含1D三次插值的可工作的CUDA示例可以在CI.zip的examples子目录中的cudaAccuracyTest示例中找到。

对于那些更感兴趣SSE方法的人，我有一些工作的SSE优化多线程三次插值代码（虽然是3D而不是1D）可以在examples子目录中的referenceCubicTexture3D示例中找到。

编辑：三次插值代码现在在github上可用。1D三次插值代码在这里。

- Danny Ruijters

---

这是关于插值一个一维网格还是从一些控制点生成一个一维曲线（例如scipy.interpolate.BSpline）的问题吗？ - Ziyuan

@Ziyuan：这是关于在1D均匀网格上插值，所以不像scipy.interpolate.BSpline。 - Danny Ruijters

Answer 2

关于＃1

我认为您指的是Ruijters的三/双立方样条插值http://dannyruijters.nl/cubicinterpolation，（已编辑！）现在可以处理一维数据，谢谢！请参见该页面上Danny Ruijters的回答。

关于＃2

以下是我所知道的几个NUFFT实现，并对它们进行了简要的介绍。

1. @ardiyu07提到的第一个库是Greengard等人实现的快速高斯网格化，使用Fortran编写，我不熟悉，所以没有深入研究（但它确实提供了类型III非均匀到非均匀转换）。
2. 第二个是Ferrara在Matlab/MEX中实现的Greengard算法，我无法得到正确的解决方案（请参见我在Mathworks FileExchange上的评论，我刚刚发布了这个评论）。
3. Potts等人的http://www-user.tu-chemnitz.de/~potts/nfft/，我无法在Windows中编译它，所以放弃了。它也有类型III NUFFTs。
4. Fessler等人的http://web.eecs.umich.edu/~fessler/code/，用Matlab/MEX编写，并为Linux和Windows提供预编译的二进制文件。明显是由非专业程序员编写的，但这是我成功运行的4个库中唯一一个。我甚至在改变他们的Matlab源代码的几个地方后，在GNU Octave中使其正常工作（基本上是通过查看Octave引发错误的地方），因为Octave可以使用预编译的MEX二进制文件。它还使用与Greengard或Potts不同的算法，基于最小-最大准则（其解决方案保证最小化最大DFT误差），但缺少类型III NUFFTs（仅类型I和II：其中一个域必须是均匀的）。
5. 我相信第五个NUFFT /“网格化”实现是由Hargreaves等人完成的：http://www-mrsrl.stanford.edu/~brian/gridding/（论文在http://dx.doi.org/10.1109/TMI.2005.848376）。它在Matlab/MEX中。按原样，它不像此列表中前四个那样通用，因为它非常嵌入其MRI上下文中。
6. 这里有第六个实现，使用Cython（快速Python），具有类型III非均匀到非均匀转换和其他一些不错的功能，但遗憾的是受GPL限制：https://github.com/mrbell/gfft

我正在以极其缓慢的速度将Fessler算法移植到Python/Cython，也许还会用CUDA（“也许”是因为只需对标准（CU）FFT进行零填充和线性插值似乎已经足够好了）。祝你好运。

- Ahmed Fasih

Answer 3

1. 我不知道那个算法，但是如果你觉得你发现的足够快适用于你的设备，为什么不改变实现方式，从使用纹理内存改为简单数组，并且也许你可以使用共享内存来加速？

2. 我找到了一些用Matlab和Fortran 77写的：

   http://www.cims.nyu.edu/cmcl/nufft/nufft.html

   http://www.mathworks.com/matlabcentral/fileexchange/25135-nufft-nufft-usffft

- ardiyu07

Answer 4

说实话，你的并行性对于GPU来说似乎有点低。一个带有SSE优化的6核处理器在这里可能会比GPU表现更好。

- Michel Müller