SYSTEM, METHOD, AND COMPUTER PROGRAM PRODUCT FOR TRANSPOSING A MATRIX

• US 20140149480A1
• Filed: 10/24/2013
• Published: 05/29/2014
• Est. Priority Date: 11/28/2012
• Status: Abandoned Application

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Kudlur, Manjunath, Catanzaro, Bryan Christopher
• Application Number:
  US14/062,820
• Publication Number:
  US 20140149480A1
• Time in Patent Office: Days
• US Class Current: 708/520
• CPC Class Codes: G06F 7/766 Generation of all possible permutations

Abstract

A system, method, and computer program product are provided for transposing a matrix. In use, a matrix is identified. Additionally, the matrix is transposed utilizing row-wise operations and column-wise operations, where the row-wise operations and the column-wise operations are performed independently.

Claims

1. A method, comprising:

identifying a matrix;

transposing the matrix by performing row-wise operations and column-wise operations, where the row-wise operations and the column-wise operations are performed independently.

2. The method of claim 1, wherein the matrix is transposed utilizing a row-to-column (R2C) transposition.

3. The method of claim 1, wherein the matrix is transposed utilizing a column-to-row (C2R) transposition.

4. The method of claim 1, wherein the row-wise operations include a row shuffle operation that selects a row of the matrix and rearranges elements within the row of the matrix.

5. The method of claim 4, wherein the row shuffle operation creates a reordered row containing a rearrangement of the elements within the row of the matrix, where the rearrangement is made according to an order identified by an input vector.

6. The method of claim 5, wherein the row of the matrix may be overwritten with the reordered row.

7. The method of claim 1, wherein the column-wise operations include a column rotation operation that rotates a column of the matrix by a predetermined distance, such that elements are consecutively removed from a top of the column and added to a bottom of the column.

8. The method of claim 1, wherein the column-wise operations include a row permutation operation that interchanges an entire row of the matrix with another entire row of the matrix.

9. The method of claim 1, wherein the row-wise operations and the column-wise operations are performed independently such that each operation is performed independently of the other operations.

10. The method of claim 1, wherein conflicts are avoided when the row-wise operations and the column-wise operations are performed.

11. The method of claim 1, wherein all row-wise operations and column-wise operations are performed without needing to send one or more elements in the matrix to more than one location within the matrix at the same time.

12. The method of claim 1, wherein transposing the matrix includes preparing the matrix to eliminate conflicts.

13. The method of claim 12, wherein the matrix is prepared by performing one or more column rotation operations and row permutation operations on the matrix.

14. The method of claim 12, wherein transposing the matrix includes performing one or more row shuffle operations on the matrix once the matrix has been prepared.

15. The method of claim 14, wherein transposing the matrix includes performing one or more column rotation operations and one or more row permutation operations to ensure entries in the matrix are in a proper order after the one or more row shuffle operations have been performed.

16. The method of claim 1, wherein conflicts are eliminated during the transposing.

17. The method of claim 1, wherein auxiliary storage is used to store a row or column of the matrix when transposing the matrix.

18. The method of claim 1, wherein identifying and transposing the matrix are performed as part of one or more single instruction, multiple data (SIMD) vector memory accesses.

19. The method of claim 1, wherein identifying and transposing the matrix are performed as part of a memory controller implementation.

20. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:

identifying a matrix;

transposing the matrix by performing row-wise operations and column-wise operations, where the row-wise operations and the column-wise operations are performed independently.

21. A system, comprising:

a processor for identifying a matrix and transposing the matrix by performing row-wise operations and column-wise operations, where the row-wise operations and the column-wise operations are performed independently.