公开(公告)号：US07640284B1

公开(公告)日：2009-12-29

申请号：US11424514

申请日：2006-06-15

申请人： Nolan D. Goodnight ,  John R. Nickolls

发明人： Nolan D. Goodnight ,  John R. Nickolls

IPC分类号： G06F17/14

CPC分类号： G06F17/142 ,  G06F7/76

摘要： Parallelism in a processor is exploited to permute a data set based on bit reversal of indices associated with data points in the data set. Permuted data can be stored in a memory having entries arranged in banks, where entries in different banks can be accessed in parallel. A destination location in the memory for a particular data point from the data set is determined based on the bit-reversed index associated with that data point. The bit-reversed index can be further modified so that at least some of the destination locations determined by different parallel processes are in different banks, allowing multiple points of the bit-reversed data set to be written in parallel.

摘要翻译： 处理器中的并行性被利用以基于与数据集中的数据点相关联的索引的位反转来置换数据集。 被许可的数据可以存储在具有排列在存储体中的条目的存储器中，其中可以并行地访问不同存储体中的条目。 基于与该数据点相关联的位反转索引来确定来自数据集的用于特定数据点的存储器中的目的地位置。 可以进一步修改位反转索引，使得由不同并行进程确定的至少一些目的地位置在不同的存储体中，允许并行写入位反转数据集的多个点。

公开(公告)号：US07836116B1

公开(公告)日：2010-11-16

申请号：US11424511

申请日：2006-06-15

申请人： Nolan D. Goodnight ,  John R. Nickolls ,  Radoslav Danilak

发明人： Nolan D. Goodnight ,  John R. Nickolls ,  Radoslav Danilak

IPC分类号： G06F17/14

CPC分类号： G06F17/142 ,  G06F9/3012 ,  G06F9/3851 ,  G06F9/3885 ,  G06F9/3887

摘要： A linear transform such as a Fast Fourier Transform (FFT) is performed on an input data set having a number of points using one or more arrays of concurrent threads that are capable of sharing data with each other. Each thread of one thread array reads two or more of the points, performs an appropriate “butterfly” calculation to generate two or more new points, then stores the new points in a memory location that is accessible to other threads of the array. Each thread determines which points it is to read based at least in part on a unique thread identifier assigned thereto. Multiple transform stages can be handled by a single thread array, or different levels can be handled by different thread arrays.

摘要翻译： 对具有能够彼此共享数据的一个或多个并行线程阵列的具有多个点的输入数据集执行诸如快速傅立叶变换（FFT）的线性变换。 一个线程数组的每个线程读取两个或更多个点，执行适当的“蝴蝶”计算以生成两个或多个新点，然后将新点存储在阵列的其他线程可访问的存储器位置。 至少部分地基于分配给它的唯一线程标识符，每个线程确定要读取哪些点。 多个变换阶段可以由单个线程数组处理，也可以由不同的线程数组来处理不同的级别。