Processing array data on SIMD multi-core processor architectures

• US 8,484,276 B2
• Filed: 03/18/2009
• Issued: 07/09/2013
• Est. Priority Date: 03/18/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Carlson, David G., Drucker, Travis M., Mullins, Timothy J., McAllister, Jeffrey S., Ramirez, Nelson
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US12/406,247
• Publication Number:
  US 20100241824A1
• Time in Patent Office: 1,574 Days
• Field of Search: 708/403, 712/22
• US Class Current: 708/403
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

Techniques are disclosed for converting data into a format tailored for efficient multidimensional fast Fourier transforms (FFTS) on single instruction, multiple data (SIMD) multi-core processor architectures. The technique includes converting data from a multidimensional array stored in a conventional row-major order into SIMD format. Converted data in SIMD format consists of a sequence of blocks, where each block interleaves s rows such that SIMD vector processors may operate on s rows simultaneously. As a result, the converted data in SIMD format enables smaller-sized 1D FFTs to be optimized in SIMD multi-core processor architectures.

Claims

1. A computer-implemented method for generating a single instruction, multiple data (SIMD) data structure tailored for processing fast Fourier transforms (FFTs) on a SIMD multi-core processor architecture, comprising:

receiving input data, wherein the input data is a matrix having m rows and n columns;

converting the input data into a SIMD format to produce converted data for simultaneous processing of s rows of the input data, wherein s is a power of two, wherein m and n are greater than and divisible by s, wherein the converted data includes a sequence of blocks, wherein each block includes s consecutive rows of the input data that are interleaved such that a set of each first element of the s consecutive rows immediately precedes a set of each second element of the s consecutive rows in terms of sequential memory addresses and such that the set of each second element of the s consecutive rows immediately precedes a set of each third element of the s consecutive rows in terms of sequential memory addresses, to produce s interleaved rows; and

storing the converted data in sequential memory addresses, wherein a SIMD operation, comprising an FFT, is performed on the converted data.

2. The method of claim 1, further comprising:

performing at least one SIMD operation, including the SIMD operation, on the converted data to compute a result, wherein the computed result includes a sequence of blocks, wherein each block includes s consecutive rows of data that are interleaved such that all of the first elements of the s consecutive rows precede any of the second elements of the s consecutive rows in terms of sequential memory addresses; and

converting the computed result from the SIMD format by;

unweaving the s interleaved rows of data in each block of the computed result, such that the first row of the computed result precedes the second row of the computed result in terms of sequential memory addresses.

3. The method of claim 1, wherein m equals n.

4. The method of claim 1, wherein s equals four.

5. The method of claim 1, wherein the input data is converted into SIMD format by an application, wherein the application is configured to independently convert the input data from each individual format selected from row-major order and column-major order, wherein the input data when in row-major order is arranged differently than the input data when in column-major order.

6. The method of claim 5, wherein the input data is converted into SIMD format from row-major order in a first instance, wherein the input data is converted into SIMD format from column-major order in a second instance to produce converted data for simultaneous processing of s columns of the input data in the second instance, wherein the converted data in the second instance includes a sequence of blocks, wherein each block includes s consecutive columns of the input data that are interleaved such that a set of each first element of the s consecutive columns immediately precedes a set of each second element of the s consecutive columns in terms of sequential memory addresses and such that the set of each second element of the s consecutive columns immediately precedes a set of each third element of the s consecutive columns in terms of sequential memory addresses, to produce s interleaved columns.

7. The method of claim 6, wherein the application is further configured to:

performing at least one SIMD operation on the converted data in the first instance to compute a result, wherein the computed result includes a sequence of blocks, wherein each block includes s consecutive rows of data that are interleaved such that all of the first elements of the s consecutive rows precede any of the second elements of the s consecutive rows in terms of sequential memory addresses; and

converting the computed result from the SIMD format to row-major order by unweaving the s interleaved rows of data in each block of the computed result, such that a set of values in the computed result that corresponds to the first row of the received input data immediately precedes a set of values in the computed result that corresponds to the second row of the received input data in terms of sequential memory addresses and such the set of values in the computed result that corresponds to the second row of the received input data immediately precedes a set of values in the computed result that corresponds to the third row of the received input data in terms of sequential memory addresses.

8. The method of claim 7, wherein the application is further configured to:

performing at least one SIMD operation on the converted data in the second instance to compute a result, wherein the computed result in the second instance includes a sequence of blocks, wherein each block includes s consecutive columns of data that are interleaved such that all of the first elements of the s consecutive columns precede any of the second elements of the s consecutive columns in terms of sequential memory addresses; and

converting the computed result in the second instance from the SIMD format to column-major order by unweaving the s interleaved columns of data in each block of the computed result, such that a set of values in the computed result that corresponds to the first column of the received input data in the second instance immediately precedes a set of values in the computed result that corresponds to the second column of the received input data in terms of sequential memory addresses and such the set of values in the computed result that corresponds to the second column of the received input data immediately precedes a set of values in the computed result that corresponds to the third column of the received input data in terms of sequential memory addresses.

9. The method of claim 8, wherein the application is further configured to independently convert the received input data in each of the first and second instances such that the set of each first element of the s consecutive rows immediately precedes the set of each second element of the s consecutive rows in terms of sequential memory addresses and such that the set of each second element of the s consecutive rows immediately precedes the set of each third element of the s consecutive rows in terms of sequential memory addresses, for each individual memory address orientation selected from increasing memory address order and decreasing memory address order.

10. A computer readable storage medium containing a program which, when executed, performs an operation for generating a single instruction, multiple data (SIMD) data structure tailored for processing fast Fourier transforms (FFTs) on a SIMD multi-core processor architecture, comprising:

receiving input data, wherein the input data is a matrix having m rows and n columns;

converting the input data into a SIMD format by operation of one or more computer processors when executing the program, to produce converted data for simultaneous processing of s rows of the input data, wherein s is a power of two, wherein m and n are greater than and divisible by s, wherein the converted data includes a sequence of blocks, wherein each block includes s consecutive rows of the input data that are interleaved such that a set of each first element of the s consecutive rows immediately precedes a set of each second element of the s consecutive rows in terms of sequential memory addresses and such that the set of each second element of the s consecutive rows immediately precedes a set of each third element of the s consecutive rows in terms of sequential memory addresses, to produce s interleaved rows; and

storing the converted data in sequential memory addresses, wherein a SIMD operation, comprising an FFT, is performed on the converted data.

11. The computer readable storage medium of claim 10, wherein the program further comprises:

performing at least one SIMD operation, including the SIMD operation, on the converted data to compute a result, wherein the computed result includes a sequence of blocks, wherein each block includes s consecutive rows of data that are interleaved such that all of the first elements of the s consecutive rows precede any of the second elements of the s consecutive rows in terms of sequential memory addresses; and

converting the computed result from the SIMD format by;

unweaving the s interleaved rows of data in each block of the computed result, such that the first row of the computed result precedes the second row of the computed result in terms of sequential memory addresses.

12. The computer readable storage medium of claim 10, wherein m equals n.

13. The computer readable storage medium of claim 10, wherein s equals four.

14. A system, comprising:

a processor; and

a memory containing a program, which when executed by the processor is configured to perform an operation for generating a single instruction, multiple data (SIMD) data structure tailored for processing fast Fourier transforms (FFTs) on a SIMD multi-core processor architecture, comprising;

receiving input data, wherein the input data is a matrix having m rows and n columns;

converting the input data into a SIMD format to produce converted data for simultaneous processing of s rows of the input data, wherein s is a power of two, wherein m and n are greater than and divisible by s, wherein the converted data includes a sequence of blocks, wherein each block includes s consecutive rows of the input data that are interleaved such that a set of each first element of the s consecutive rows immediately precedes a set of each second element of the s consecutive rows in terms of sequential memory addresses and such that the set of each second element of the s consecutive rows immediately precedes a set of each third element of the s consecutive rows in terms of sequential memory addresses, to produce s interleaved rows; and

storing the converted data in sequential memory addresses, wherein a SIMD operation, comprising an FFT, is performed on the converted data.

15. The system of claim 14, wherein the program further comprises:

performing at least one SIMD operation, including the SIMD operation, on the converted data to compute a result, wherein the computed result includes a sequence of blocks, wherein each block includes s consecutive rows of data that are interleaved such that all of the first elements of the s consecutive rows precede any of the second elements of the s consecutive rows in terms of sequential memory addresses; and

converting the computed result from the SIMD format by;

unweaving the s interleaved rows of data in each block of the computed result, such that the first row of the computed result precedes the second row of the computed result in terms of sequential memory addresses.

16. The system of claim 14, wherein m equals n.

17. The system of claim 14, wherein s equals four.

18. A computer-implemented method for generating a single instruction, multiple data (SIMD) data structure tailored for processing fast Fourier transforms (FFTs) on a SIMD multi-core processor architecture, comprising:

receiving input data, wherein the input data is a matrix having m rows and n columns, wherein the matrix includes b blocks, and wherein each block includes s consecutive rows, wherein s is a power of two, wherein m and n are greater than and divisible by s; and

copying the b blocks into sequential memory addresses to generate the SIMD data structure, wherein a SIMD operation, comprising an FFT, is performed on the generated SIMD data structure, wherein copying a block comprises;

copying, into sequential memory addresses, each first element of the s consecutive rows of the block, immediately followed by each second element of the s consecutive rows of the block, immediately followed by each third element of the s consecutive rows of the block, followed by remaining elements of the s consecutive rows in a similar manner, ending with last elements of the s consecutive rows of the block.

19. The method of claim 18, further comprising:

performing at least one SIMD operation, including the SIMD operation, on the converted data to compute a result;

storing the result as b result blocks in sequential memory addresses, wherein each result block includes s consecutive rows; and

copying the b result blocks from sequential memory addresses into a result matrix having m rows and n columns, wherein the result matrix includes b blocks, and wherein each block includes s consecutive rows, and wherein copying a result block comprises;

copying values of the result block from sequential memory addresses into first elements of the s consecutive rows of the block in the result matrix, then into second elements of the s consecutive rows of the block in the result matrix, then into remaining elements of the s consecutive rows in a similar manner, and finally into last elements of the s consecutive rows of the block in the result matrix.