开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >CUDA fft - cooley tukey，如何利用并行性？

问CUDA fft - cooley tukey，如何利用并行性？
EN

Stack Overflow用户

提问于 2012-09-09 14:19:27

回答 1查看 1.7K关注 0票数 5

我知道FFT实现是如何工作的(Cooley-Tuckey algorithm)，我知道有一个CUFFT CUDA库可以快速计算1D或2DFFT，但我想知道在这个过程中CUDA并行性是如何被利用的。

它与蝶形计算有关吗？(类似于每个线程将部分数据加载到共享内存中，然后每个线程计算一个偶数项或奇数项？)

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-09-10 09:48:23

我不认为他们使用Cooley-Tuckey算法，因为它的索引排列阶段使其在共享内存体系结构中不是很方便。此外，该算法适用于2的幂内存步长，这也不利于内存合并。最有可能的是他们使用了一些斯托克汉姆自排序快速傅立叶变换的公式:例如Bailey's algorithm。

关于实现的问题，你是对的，通常人们会将一个大的FFT分成几个较小的FFT，它们完全适合一个线程块。在my work中，我使用了512或1024点的FFT(当然是完全展开的)，每个线程块有128个线程。通常，由于需要进行大量数据传输，因此不能在GPU上使用经典的基数-2算法。取而代之的是，人们选择基数-8甚至基数-16算法，以便每个线程一次执行一个大的“蝶形”。例如实现，你也可以访问Vasily Volkov页面，或者查看this的“经典”论文。

票数 6

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/12339864

复制

相关文章

Cooley-Tukey算法（蝶形算法）

编程算法 java https 网络安全

Cooley－Tukey算法差别于其它FFT算法的一个重要事实就是N的因子能够随意选取。这样也就能够使用N＝r S的Radix－r算法了。最流行的算法都是以r＝2或r＝4为基的，最简单的DFT不须要不论什么乘法就能够实现。比如：在S级且r＝2的情形下，下列索引映射的结果是：

全栈程序员站长

2021/12/03

1.1K0

Cooley-Tukey算法（蝶形算法）

快速傅里叶变换（FFT）算法【详解】

快速傅里叶变换（Fast Fourier Transform）是信号处理与数据分析领域里最重要的算法之一。我打开一本老旧的算法书，欣赏了JW Cooley 和 John Tukey 在1965年的文章中，以看似简单的计算技巧来讲解这个东西。本文的目标是，深入Cooley-Tukey FFT 算法，解释作为其根源的“对称性”，并以一些直观的python代码将其理论转变为实际。我希望这次研究能对这个算法的背景原理有更全面的认识。 FFT（快速傅里叶变换）本身就是离散傅里叶变换（Discrete Fourie

Angel_Kitty

2018/04/09

5.2K0

快速傅里叶变换（FFT）算法【详解】

快速傅里叶变换（FFT）算法【详解】[通俗易懂]

编程算法 ftp python numpy

快速傅里叶变换（Fast Fourier Transform）是信号处理与数据分析领域里最重要的算法之一。我打开一本老旧的算法书，欣赏了JW Cooley 和 John Tukey 在1965年的文章中，以看似简单的计算技巧来讲解这个东西。

全栈程序员站长

2022/09/07

6.8K0

快速傅里叶变换（FFT）算法【详解】[通俗易懂]

转：fft算法（快速傅里叶变换算法）

fft 编程算法

FFT (Fast Fourier Transform) 是一种快速傅里叶变换算法。它是用来将一个信号从时域转换到频域的算法。这个算法通过分治策略，将一个长度为 N 的复数序列分解成 N/2 个长度为 2 的复数序列，然后对这些小的序列分别进行 FFT 计算。

啵啵鳐

2023/07/04

4230

【STM32F407的DSP教程】第25章 DSP变换运算-快速傅里叶变换原理（FFT）

在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此导致DFT被发现以来，在很长的一段时间内都不能被应用到实际工程项目中，直到一种快速的离散傅立叶计算方法——FFT被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。

Simon223

2020/05/27

1.1K0

【STM32F407的DSP教程】第25章 DSP变换运算-快速傅里叶变换原理（FFT）

【STM32H7的DSP教程】第25章 DSP变换运算-快速傅里叶变换原理（FFT）

在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此导致DFT被发现以来，在很长的一段时间内都不能被应用到实际工程项目中，直到一种快速的离散傅立叶计算方法——FFT被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。

Simon223

2020/05/27

1.1K0

【STM32F429的DSP教程】第25章 DSP变换运算-快速傅里叶变换原理（FFT）

在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此导致DFT被发现以来，在很长的一段时间内都不能被应用到实际工程项目中，直到一种快速的离散傅立叶计算方法——FFT被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。

Simon223

2020/05/27

5450

改变世界的5大算法

[导读] 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。周末了，今天来轻松概念性总结分享一下改变世界5大算法，当然足以改变世界的算法远不止这5个。比如还有卡尔曼滤波算法啦等等，等以后有机会整理

逸珺

2020/06/02

1.7K0

在介绍Tukey方法前，首先了解学生化极差分布。在概率论和统计学中，学生化极差分布是极差的抽样分布。该分布是一种连续型概率分布，用于在样本量较小且总体标准差未知的情况下估计正态分布总体的极差。假设要比较的组数为k，那么在零假设成立的条件下，下面的随机变量服从学生化极差分布。

狼啸风云

2019/12/03

1.1K0

EDA算法探究--20世纪10个影响最大的算法在EDA领域的应用

21世纪初，科研人员总结了上个世纪对工业界影响最大的10个算法，其中大多数算法都在EDA领域有重要应用。我们今天来看一下，这10大算法，你在大学期间学过哪些？在工作中学过和用到哪些？如果10个算法你全部在工作中应用到，说明你已经对人类一个世纪以来研究的精华掌握得很好了。

网络交换FPGA

2019/10/29

3.2K0

Nature盘点：从Fortran、arXiv到AlexNet，这些代码改变了科学界

tcp/ip ide python 编程算法

2019 年，「事件视界望远镜」团队拍下了第一张黑洞照片。这张照片并非传统意义上的照片，而是计算得来的——将美国、墨西哥、智利、西班牙和南极多台射电望远镜捕捉到的数据进行数学转换。该团队公开了所用代码，使科学社区可以看到，并基于此做进一步的探索。

机器之心

2021/01/27

4330

Nature盘点：从Fortran、arXiv到AlexNet，这些代码改变了科学界

xilinx FFT IP的介绍与仿真

tcp/ip 数据库一体机 TData 数据分析

Xilinx快速傅立叶变换（FFT IP）内核实现了Cooley-Tukey FFT算法，这是一种计算有效的方法，用于计算离散傅立叶变换（DFT）。

FPGA开源工作室

2020/06/29

2.2K0

Matlab中fft与fwelch有什么区别？如何用fft求功率谱？

做信号处理的朋友应该都会fft比较熟悉，就是求傅里叶变换。我在这里也不再去讲这个函数了，但需要注意的一点：实信号的频谱关于0频对称，是偶函数，如果st = cos(2pif0*t)+1; t的长度为4000，那么0频的位置在第一个点，做fftshift后，0频的位置在低2001个点的位置，fft后的信号关于第2001个点对称，而不是4000个点左右对称。

猫叔Rex

2020/06/29

2.6K0

如何卸载cuda

java https 网络安全

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/151766.html原文链接：https://javaforall.cn

全栈程序员站长

2022/06/24

1.4K0

MATLAB实现利用FFT和IFFT计算线性卷积

一、实验目的 1.学习用 FFT和IFFT计算线性卷积的方法。 2.编制 IFFT程序。 3.实现用 FFT 程序计算线性卷积。

timerring

2022/07/20

2.1K0

MATLAB实现利用FFT和IFFT计算线性卷积

这个 FFT ，看得我都 FFT 了

FFT 即快速傅立叶变换。在很多计算机领域都用用处，例如数字图像处理、计算机网络。但他在算法竞赛中主要是用于多项式和生成函数相关的题目。

ACM算法日常

2021/09/07

1.2K0

PyTorch 1.7 发布！支持CUDA 11，Windows 分布式训练，以及FFT新API

rpc api c++分布式 pytorch

今天，我们正式发布 PyTorch 1.7，以及升级的域库。PyTorch 1.7版本包括了一些新的 API，比如对兼容 numpy 的 FFT 操作的支持、性能分析工具以及对分布式数据并行(DDP)和基于远程过程调用(RPC)的分布式训练的重要更新。此外，还有一些特性移到了 stable 状态，包括自定义 C++ 类、内存分析器、通过自定义类张量对象实现的扩展、 RPC 中的用户异步函数以及 torch.distributed 中的其他一些特性，如 Per-RPC 超时、 DDP dynamic bucketing 和 RRef helper。

McGL

2020/10/30

1.1K0

Nature盘点的这些代码，个个都改变了科学：Fortran、AlexNet还有arXiv等

数据库 sql 编程算法腾讯云开发者社区深度学习

在过去的一年中，Nature对数十名研究人员进行了调查，以选出这几十年以来，改变研究的关键代码。

量子位

2021/01/28

3770

Nature盘点的这些代码，个个都改变了科学：Fortran、AlexNet还有arXiv等

【留言送书】PyTorch1.8版本发布！更有TorchVision等期待的更新！

pytorch https 网络安全 api github

近日，Facebook发布了PyTorch 1.8新版本。自1.7版以来，此版本包含3,000多次提交。它包括众多更新和优化：编译，代码优化，用于科学计算的前端API，以及通过pytorch.org提供的二进制文件对AMD ROCm的支持。它还为管道和模型并行性以及梯度压缩的大规模训练提供了改进的功能。几个重大更新包括：

lujohn3li

2021/03/16

1K0

【留言送书】PyTorch1.8版本发布！更有TorchVision等期待的更新！

点击加载更多

相似问题

Cooley-Tukey FFT - float与double的精度

11

python中的cooley-tukey FFT算法问题

112

R基-2 DIT情形下的Cooley-Tukey FFT

16

FFT (Bluestein和Cooley-Tukey )...始料未及的高峰

19

FFT Cooley Tukey算法-不适用于多个数字

11

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

社区富文本编辑器全新改版！诚邀体验～

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验