•将输入文件分成（键，值）对。
•这些对
被馈入“ Map”算法，该算法根据您放入Map中的内容将您的（（键，值）
对转换为其他（键，值）对。 。
•然后，框架从Maps收集所有的（键，值）
输出，并按键对它们进行排序，以及将具有相同键的
值聚合为一对。您最终得到（key，
list（value1，value2，..））对
•然后将这些对
馈入“ Reduce”算法中，该算法又输出更多（key ，值）
作为最终结果（写入文件）。
在处理诸如处理服务器日志之类的实用内容中，此模型有很多应用程序，但是我有很难将框架应用于将FFT分解为“ map”和“ reduce”任务，例如特别是因为我不太熟悉DSP。
我不会打扰您，因为这是DSP的问答环节。但是，我对存在哪些并行计算FFT的算法感到困惑；映射和归约任务无法（在技术上）彼此对话，因此必须将FFT分为独立的问题，然后才能以某种方式重新组合结果。
我已经编写了Cooley-Tukey Radix 2 DIT的一个简单实现，该实现可以在较小的示例上运行，但是将其用于递归计算十亿字节的奇/偶索引DFT将不起作用。我花了几周时间阅读许多论文，包括一篇关于MapReduce FFT算法的文章（由Tsz-Wo Sze作为其关于SSA乘法的论文的一部分撰写，我不能链接两个以上的超链接）和“四步FFT” （此处和此处），看起来彼此相似，也与我要完成的任务相似。但是，我在数学上是绝望的，将这些方法中的任何一种手工应用于{1,2,3,4,5,6,7,8}（所有虚部均为0）这样的简单集合，可以得出我非常不正确的结果。谁能用简单的英语（我链接的或其他链接的）向我解释一种有效的并行FFT算法，以便我可以尝试对其进行编程？
编辑：Jim Clay和其他可能感到困惑的人根据我的解释，我正在尝试对TB文件进行一次FFT。但是我希望能够在多台服务器上同时执行此操作，以加快该过程。
#1 楼
我认为您的主要问题不是如何并行化算法（实际上可以做到），而是数值精度。数值上很大的FFT在数值上非常棘手。 FFT系数的形式为
$ e ^ {-j \ cdot 2 \ cdot \ pi \ cdot \ frac {k} {N}} $，如果N很大，则系数计算会变得嘈杂。假设您有$ N = 2 ^ {40} $，并且使用64位双精度算术。前1000个系数的真实部分完全是一个整数（尽管不应该这样），因此您将需要更高精度的数学运算，这效率非常低并且使用起来很麻烦。
您还会累积很多舍入和截断错误，因为进入单个输出数字的操作数也非常大。由于FFT具有“每个输出都取决于每个输入”的性质，因此错误传播非常普遍。
我不知道解决此问题的简单方法。您的要求是不寻常的。大多数对大型数据集进行频谱分析的应用程序都会在没有问题的情况下进行运行分析。也许如果您可以描述您的应用程序及其更多限制，我们可以为您提供更合适的解决方案。
评论
$ \ begingroup $
很正确的一点..我将不得不更多地考虑这一点。就像您说的那样，也许最终我会求助于“运行分析”。
$ \ endgroup $
– Philipp
2012年6月25日14:22
$ \ begingroup $
我知道我真的来晚了，但是由于您提到可以做到这一点，您是否有机会了解如何做到这一点？
$ \ endgroup $
– Claudio Brasser
18年6月8日在12:56
#2 楼
除了尝试重新编写FFT之外，您还可以尝试使用现有的FFT实现（例如FFTW），并通过重叠加法或重叠法沿信号的长度（无论其大小）重复应用它。保存方法。这可以通过将FFT表示为卷积来实现。这些较短长度的FFT不需要相互通信，并且整个方案与map-reduce步骤匹配。
通常，您的目标是将信号X分成较小的段，这些段也可以重叠（例如X [0:10]，X [5:15]，X [10:20] ... ）。对这些小段执行FFT，最后将它们重新组合以产生最后一个。这与map-reduce运算符非常吻合。
在“ map”过程中，您可以生成（键，值）对，其中“ key”是每个段的一些顺序ID（0、1,2 ，3,4,5，....），“值”是信号文件中段的第一个值的INDEX（或文件位置）。因此，例如，如果您的文件中充满了INT32，则第二段（上方）的索引为5 * sizeof（INT32）。 （或者，如果它采用任何其他格式，则可能需要一个lib）。
现在，每个工作人员都会收到一个（键，值）打开一个文件，查找到正确的位置，从中读取M个样本（其中M等于10），执行FFT并将其保存到某个名称的文件中，例如“ RES_ [INKEY] .dat”，并返回一个（键，值）对。在这种情况下，“键”将是INDEX（传入（键，值）元组的“值”），“值”将是包含FFT结果的文件的名称。 （我们将返回到此）
现在，在“ reduce”中，您可以通过接受“ map”步骤中的一个（键，值），打开该文件，加载FFT结果，执行oa或os，然后将其保存到输出文件中正确的INDEX。 （请参阅此（或此）中的伪代码，“ map”步骤并行处理“ yt = ...”，而“ reduce”步骤处理“ y（i，k）= ...”部分。） br />
这里可能需要进行一些文件处理，以减少网络流量或可能包含实际数据文件的服务器的负载。
评论
$ \ begingroup $
我不确定重叠加法和重叠保存法来组合较小的块以检索较大尺寸的FFT的有效性-据我所知，必须进行第二次FFT操作（DFT大小为N = AB的DFT可以分解为大小为B的A DFT，应用旋转因子，然后分解为大小为A的B DFT。如果我们想要较低的分辨率输出，可能会起作用...
$ \ endgroup $
–小食
2012年6月23日在10:44
$ \ begingroup $
您好，picenettes，谢谢您，我心中的想法是（engineeringproductivitytools.com/stuff/T0001/PT11.HTM），我将在答案中包括这些内容。
$ \ endgroup $
– A_A
2012年6月23日10:56
#3 楼
让我们假设您的数据大小为$ 2 ^ N $。否则用零填充。在您的情况下，由于您提到的是“ TB级”大小，因此我们将N设为40。由于$ 2 ^ {N / 2} $很大-但对于单个变量来说绝对合理机器-FFT大小，建议您只对基数$ N / 2 $进行一次Cooley-Tukey迭代，然后让适当的FFT库（如FFTW）在较小大小的$ 2 ^上在每台机器上完成工作N / 2} $。更明确地说，在整个递归过程中都不需要使用MR，这确实效率很低。您的问题可以分解为百万兆字节的内部和外部FFT，而这些兆字节FFT可以使用FFTW或类似方法完美计算。 MR将仅负责监督数据改组和重组，而不是实际的FFT计算...
我的第一个想法是，但我怀疑这可以在单个MR中完成更智能的数据表示。
让$ s $作为输入信号，$ R = 2 ^ {N / 2} $
第一个MR：内部FFT
Map：及时执行抽取，将样本分组进行内部FFT
输入：$（k，v）$其中$ k $是$ 0中的样本索引。2 ^ N- 1 $; $ v $ $ s [k] $
发出的值：$（k \％R，（k / R，v））$-其中％代表模和/整数除法。 br />
减少：计算内部FFT
输入：$（k，vs）$其中$ k $是块索引；而$ vs $是$（i，v）$对的列表。
填充一个大小为$ R $的向量$ in $，使得$ in [i] = v $ list。
对$ in $执行大小$ R $ FFT，以得到$ i $ in $ 0 .. R的向量$ out $，大小为$ R $
-1 $，发出$（k，（i，out [i]））$$
第二个MR：外部FFT
Map：对外部fft进行分组采样并应用旋转factor
输入：$（k，（i，v））$其中$ k $是块索引，$（i，v）$该块的内部FFT样本。
发出$（i，（k，v \ times \ exp \ frac {-2 \ pi jik} {2 ^ N}））$
减少：执行外部FFT
输入：$（k，vs）$其中$ k $是块索引；而$ vs $是$（i，v）$对的列表。
填充大小为$ R $的向量$ in $，使得$ in [i] = v $ list。
对$ in $进行大小$ R $ FFT，以得到$ i $ in $ 0 .. R的向量$ out $，大小为$ R $
。 -1 $，发出$（i \ times R + k，out [i]））$
概念证明python代码在这里。
如您所见，映射器仅改组数据的顺序，因此在以下假设下：
时间上的抽取（映射器1）可以在上一步中完成（例如，通过将数据转换成正确的输入格式。
您的MR框架支持Reducer写入与其输入密钥不同的密钥（在Google的实现中，reduces只能将数据输出到接收到的相同密钥，我认为这是由于SSTable造成的）
所有这些都可以在一个MR中完成，映射器中的内部FFT，缩减器中的外部FFT。这里的概念证明。
评论
$ \ begingroup $
您的实现看似很有希望，我现在正在研究它，但是在内部FFT减少器中，您编写了“执行大小为2 ^ R的FFT以获得大小为2 ^ R的矢量”。如果R为2 ^（N / 2），则此FFT的大小是否为2 ^（2 ^ N / 2），因此不正确吗？您是说R大小的FFT吗？
$ \ endgroup $
– Philipp
2012年6月25日14:08
$ \ begingroup $
是的，好像我在几个地方混用了$ R $和$ 2 ^ R $ ...编辑过。请注意，Hilmar的评论适用于我的方法-您必须使用比double更高的精度，否则，一些旋转因素（$ \ exp \ frac {-2 \ pi jik} {2 ^ N} $）将具有他们不应拥有的1的实数部分-导致数值不正确。
$ \ endgroup $
–小食
2012年6月25日15:14
#4 楼
如果您的信号是多维的，则可以很容易地完成FFT的并行化。在MPI过程中保持一个维连续，执行FFT，然后转置（全部）以处理下一维。 FFTW会执行此操作。如果数据是一维的，则问题要困难得多。例如，FFTW没有使用MPI编写一维FFT。如果使用基数2的频率抽取算法，则前几个阶段可以作为朴素的DFT执行，从而允许一个节点使用2或4个节点而不会损失任何精度（这是因为，第一阶段是-1或i，可以很好地工作。）
顺便说一下，一旦转换了数据，您打算如何处理数据？如果人们知道输出会发生什么（即卷积，低通滤波器等），可能会有所作为。
评论
您到底想完成什么？您要对TB级信号文件执行单个FFT，还是对每个文件进行多个较小的FFT？