Transposing array data on SIMD multi-core processor architectures
Systems, methods and articles of manufacture are disclosed for transposing array data on a SIMD multi-core processor architecture. A matrix in a SIMD format may be received. The matrix may comprise a SIMD conversion of a matrix M in a conventional data format. A mapping may be defined from each element of the matrix to an element of a SIMD conversion of a transpose of matrix M. A SIMD-transposed matrix T may be generated based on matrix M and the defined mapping. A row-wise algorithm may be applied to T, without modification, to operate on columns of matrix M.
1. A computer-implemented method for transposing a matrix on a SIMD multi-core processor architecture, comprising configuring the SIMD (Single Instruction Multiple Data) multi-core processor architecture to perform an operation comprising:
converting a matrix M in a first format to a matrix S in a SIMD format, wherein the SIMD format allows a plurality of cores on the SIMD multi-core processor architecture to each perform a 1D FFT (Fast Fourier Transform) operation on a row of data in the matrix M in parallel;
retrieving a mapping for each element of the matrix S to an element in a transpose of matrix M in a SIMD format, wherein the mappings preserve the SIMD format of S for a transposition of the matrix M; and
generating, based on the retrieved mappings, a SIMD-transposed matrix T, wherein the transposed SIMD matrix T allows the plurality of cores on the SIMD multi-core processor architecture to each perform an 1D FFT operation on a transposed row of data in the matrix M in parallel.
2. The computer-implemented method of claim 1 , wherein the matrix in the SIMD format is configured for simultaneous processing of r rows of matrix M, wherein the converted data includes a sequence of blocks, wherein each block includes r consecutive rows of matrix M that are interleaved such that first elements of the r consecutive rows precede any second elements of the r consecutive rows in terms of sequential memory addresses to produce r interleaved rows.
3. The computer-implemented method of claim 1 , wherein the first format is one of a row-major format and a column-major format.
4. The computer-implemented method of claim 1 , wherein the operation further comprises:
generating s segments based on the matrix S;
assigning the s segments to s processing elements of the SIMD multi-core processor architecture, and wherein generating the SIMD-transposed matrix T comprises:
transposing each segment on a respective processing element.
5. The computer-implemented method of claim 4 , wherein transposing each segment on each respective processing element occurs on memory local to each respective processing element, and wherein generating the transposed matrix T further comprises scattering, by each of the processing elements, each transposed segment to memory not local to any of the processing elements.
6. The computer-implemented method of claim 4 , wherein transposing each segment on each respective processing element comprises:
dividing the respective segment into d subdivisions, each subdivision not exceeding a size of memory local to the respective processing element; and
transposing each subdivision of the respective segment on each respective processing element.
7. The computer-implemented method of claim 1 , wherein the matrix M stores a portion of image data captured from an MRI (Magnetic Resonance Imaging) device in a 256×256, 512×512, or 1024×1024 sized matrix.
8. A non-transitory computer-readable storage medium storing an application program configured for transposing a matrix on a SIMD (Single Instruction Multiple Data) multi-core processor architecture by performing an operation, comprising:
converting a matrix M in a first format to a matrix S in a SIMD format, wherein the SIMD format allows a plurality of cores on the SIMD multi-core processor architecture to each perform a 1D FFT (Fast Fourier Transform) operation on a row of data in the matrix M in parallel;
retrieving a mapping for each element of the matrix S to an element in a transpose of matrix M in a SIMD format, wherein the mappings preserve the SIMD format of S for a transposition of the matrix M; and
generating, based on the retrieved mappings, a SIMD-transposed matrix T, wherein the transposed SIMD matrix T allows the plurality of cores on the SIMD multi-core processor architecture to each perform an 1D FFT operation on a transposed row of data in the matrix M in parallel.
9. The non-transitory computer-readable storage medium of claim 8 , wherein the matrix in the SIMD format is configured for simultaneous processing of r rows of matrix M, wherein the converted data includes a sequence of blocks, wherein each block includes r consecutive rows of matrix M that are interleaved such that first elements of the r consecutive rows precede any second elements of the r consecutive rows in terms of sequential memory addresses to produce r interleaved rows.
10. The non-transitory computer-readable storage medium of claim 8 , wherein the first format is one of a row-major format and a column-major format.
11. The non-transitory computer-readable storage medium of claim 8 , wherein the operation further comprises:
generating s segments based on the matrix S;
assigning the s segments to s processing elements of the SIMD multi-core processor architecture, and wherein generating the SIMD-transposed matrix T comprises:
transposing each segment on a respective processing element.
12. The non-transitory computer-readable storage medium of claim 11 , wherein transposing each segment on each respective processing element occurs on memory local to each respective processing element, and wherein generating the transposed matrix T further comprises scattering, by each of the processing elements, each transposed segment to memory not local to any of the processing elements.
13. The non-transitory computer-readable storage medium of claim 11 , wherein transposing each segment on each respective processing element comprises:
dividing the respective segment into d subdivisions, each subdivision not exceeding a size of memory local to the respective processing element; and
transposing each subdivision of the respective segment on each respective processing element.
14. The non-transitory computer-readable storage medium of claim 8 , wherein the matrix M stores a portion of image data captured from an MRI (Magnetic Resonance Imaging) device in a 256×256, 512×512, 1024×1024, or 2048×2048 sized matrix.
15. A system, comprising:
a SIMD (Single Instruction Multiple Data) multi-core processor; and
a memory containing an application program configured for transposing a matrix on the SIMD multi-core processor architecture by performing an operation comprising:
converting a matrix M in a first format to a matrix S in a SIMD format, wherein the SIMD format allows a plurality of cores on the SIMD multi-core processor architecture to each perform a 1D FFT (Fast Fourier Transform) operation on a row of data in the matrix M in parallel,
retrieving a mapping for each element of the matrix S to an element in a transpose of matrix M in a SIMD format, wherein the mappings preserve the SIMD format of S for a transposition of the matrix M, and
generating, based on the retrieved mappings, a SIMD-transposed matrix T, wherein the transposed SIMD matrix T allows the plurality of cores on the SIMD multi-core processor architecture to each perform an 1D FFT on a transposed row of data in the matrix M in parallel.
16. The system of claim 15 , wherein the matrix in the SIMD format is configured for simultaneous processing of r rows of matrix M, wherein the converted data includes a sequence of blocks, wherein each block includes r consecutive rows of matrix M that are interleaved such that first elements of the r consecutive rows precede any second elements of the r consecutive rows in terms of sequential memory addresses to produce r interleaved rows.
17. The system of claim 15 , wherein the first format is one of a row-major format and a column-major format.
18. The system of claim 15 , wherein the operation further comprises:
generating s segments based on the matrix S;
assigning the s segments to s processing elements of the SIMD multi-core processor architecture, and wherein generating the SIMD-transposed matrix T comprises:
transposing each segment on a respective processing element.
19. The system of claim 18 , wherein transposing each segment on each respective processing element occurs on memory local to each respective processing element, and wherein generating the transposed matrix T further comprises scattering, by each of the processing elements, each transposed segment to memory not local to any of the processing elements.
20. The system of claim 18 , wherein transposing each segment on each respective processing element comprises:
dividing the respective segment into d subdivisions, each subdivision not exceeding a size of memory local to the respective processing element; and
transposing each subdivision of the respective segment on each respective processing element.
21. The system of claim 15 , wherein the matrix M stores a portion of image data captured from an MRI (Magnetic Resonance Imaging) device in a 256×256, 512×512, or 1024×1024 sized matrix.