一种用于并行FFT计算的数据存取方法及装置

摘要

本发明提供一种用于并行FFT计算的数据存取方法及装置。该方法将FFT计算数据和旋转因子存放在多粒度并行存储器中，并用统一的蝶形表达式对整个计算过程中的FFT数据和对应的旋转因子进行分组，每分组数据包含多个蝶形，可并行计算；同时根据该蝶形表达式，可方便生成各个分组的数据地址和旋转因子系数地址，利用不同的读写粒度，可从多粒度存储器中并行读写数据和对应的旋转因子。本发明还提供一种用于并行FFT计算的数据存取装置。利用本发明，数据的读写过程中不会产生存储器冲突，也不需要额外的步骤再对读写数据进行排序，同时，本发明可根据具体实现灵活指定并行粒度。

主权项

一种用于并行FFT蝶形计算的数据存取方法，其特征在于，该方法包括以下步骤：步骤1，按照2B的并行粒度，将长度为N的初始FFT数据，分为2G个数据组，其中，G＝log2N‑B；并将2G个数据组存放在多粒度并行存储器(300)或(302)中的2B个存储块(804)的各个存储行(805)中，每个存储块(804)包含2G‑B个数据组，占用2G‑B个存储行(805)；步骤2，将每个蝶形组(402)计算需要的2B‑1个旋转因子依次存放在多粒度并行存储器(303)的存储行中；步骤3，读取多粒度并行存储器(300)或(302)中第i个存储块(804)的第j个存储行(805)中存储的FFT蝶形计算所需的数据，读取粒度为2B，其中，i、j的初始值均为0；并以2B的粒度从多粒度并行存储器(303)中按照存储行的顺序依次读取FFT蝶形计算所需的旋转因子；步骤4，根据读取出的旋转因子，按2B的粒度对读出的第j个存储行(805)所存储的数据进行并行蝶形计算；步骤5，按1的粒度将蝶形计算结果数据并行写回到多粒度并行存储器(300)或(302)中，当步骤3中从存储器(300)读取数据时，步骤5将蝶形计算结果数据写回到存储器(302)中，反之亦然；步骤6，判断当前存储行号j是否满足j＜2G‑B，如果满足，则将j加1后返回到步骤3；否则将j置0，跳到步骤7；步骤7，判断当前存储块号i是否满足i＜2B，如果满足，则将i加1后跳到步骤3，否则结束。