High performance inplace transpose operations

Patent metadata

Field	Value
Publication number	US-10067911-B2
Application number	US-201615219672-A
Country	US
Kind code	B2
Filing date	Jul 26, 2016
Priority date	Jul 26, 2016
Publication date	Sep 4, 2018
Grant date	Sep 4, 2018

Abstract

Systems, apparatuses, and methods for performing in-place matrix transpose operations are disclosed. Operations for transposing tiles of a matrix are scheduled in an order determined by moving diagonally through tiles of the matrix. When a diagonal line hits a boundary, then a tile on a new diagonal line of the matrix is selected and operations are scheduled for transposing this tile. Only tiles within a triangular region of the matrix are scheduled for being transposed. This allows memory access operations to be performed in parallel, expediting the matrix transpose operation compared to linear tile indexing.

First claim

What is claimed is:

1. A system comprising:
one or more processors; and
a memory device comprising a plurality of memory channels, wherein the memory is configured to store program instructions and a matrix of data elements;
wherein the program instructions are executable by the one or more processors to:
detect a request to perform an in-place transpose of the matrix;
schedule operations for transposing tiles of the matrix in the memory, wherein the operations are scheduled in an order determined by moving diagonally through tiles of the matrix; and
perform the in-place transpose of the matrix by moving diagonally through tiles of the matrix and exchanging data elements from each tile stored in the memory with a transpose tile stored in the memory, wherein moving diagonally through tiles of the matrix causes each tile being transposed to be stored on a different memory channel of the plurality of memory channels from a next tile being transposed.

2. The system as recited in claim 1 , wherein the operations are scheduled in an order determined by moving diagonally from a top left corner to a bottom right corner of the matrix, and wherein subsequent operations are scheduled in an order determined by moving through the matrix in diagonal lines parallel to a line from the top left corner to the bottom right corner.

3. The system as recited in claim 1 , wherein the program instructions are further executable by the one or more processors to:
schedule operations for transposing a first tile of the matrix by accessing a first memory channel;
select a second tile of an adjacent row and an adjacent column from the first tile; and
schedule operations for transposing the second tile of the matrix by accessing a second memory channel different from the first memory channel.

4. The system as recited in claim 1 , wherein the program instructions are further executable by the one or more processors to schedule operations for transposing tiles that are located within only a triangular portion of the matrix, and wherein tiles located outside of the triangular portion of the matrix are not scheduled for being transposed.

5. The system as recited in claim 1 , wherein the program instructions are further executable by the one or more processors to calculate tile indices for scheduling tiles of the matrix according to a formula, wherein each index is calculated as being equal to |Y−X|*N+X−½*(Y−X)(Y−X−1), wherein X is a row of the matrix, wherein Y is a column of the matrix, and wherein N is a number of rows of the matrix.

6. The system as recited in claim 1 , wherein the operations are scheduled in an order that allows for parallel accesses to be performed to memory locations storing the matrix of data elements.

7. The system as recited in claim 1 , wherein the matrix is stored in row-major format in the memory.

8. A method comprising:
detecting a request to perform an in-place transpose of a matrix stored in a memory device comprising a plurality of memory channels, responsive to a processor comprising circuitry executing a program instruction to initiate an in-place transpose of the matrix;
scheduling operations for transposing tiles of the matrix in the memory, wherein the operations are scheduled in an order determined by moving diagonally through tiles of the matrix; and
performing the in-place transpose of the matrix by moving diagonally through tiles of the matrix and exchanging data from each tile with a transpose tile store in the memory, wherein moving diagonally through tiles of the matrix causes each tile being transposed to be stored on a different memory channel of the plurality of memory channels from a next tile being transposed.

9. The method as recited in claim 8 , wherein the operations are scheduled in an order determined by moving diagonally from a top left corner to a bottom right corner of the matrix, and wherein subsequent operations are scheduled in an order determined by moving through the matrix in diagonal lines parallel to a line from the top left corner to the bottom right corner.

10. The method as recited in claim 8 , further comprising executing one or more programs instructions for:
scheduling operations for transposing a first tile of the matrix by accessing a first memory channel;
selecting a second tile of an adjacent row and an adjacent column from the first tile; and
scheduling operations for transposing the second tile of the matrix by accessing a second memory channel different from the first memory channel.

11. The method as recited in claim 8 , further comprising scheduling operations for transposing tiles that are located within only a triangular portion of the matrix, and wherein tiles located outside of the triangular portion of the matrix are not scheduled for being transposed.

12. The method as recited in claim 8 , further comprising calculating tile indices for scheduling operations for transposing tiles of the matrix according to a formula, wherein each index is calculated as being equal to |Y−X|*N+X−½*(Y−X)(Y−X−1), wherein X is a row of the matrix, wherein Y is a column of the matrix, and wherein N is a number of rows of the matrix.

13. The method as recited in claim 8 , wherein the operations are scheduled in an order that allows for parallel accesses to be performed to memory locations storing the matrix of data elements.

14. The method as recited in claim 8 , wherein the matrix is stored in row-major format in the memory.

15. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a processor to:
detect a request to perform an in-place transpose of a matrix stored in a memory device comprising a plurality of memory channels, responsive to the processor executing a program instruction to initiate an in-place transpose of the matrix;
schedule operations for transposing tiles of the matrix in the, wherein the operations are scheduled in an order determined by moving diagonally through tiles of the matrix; and
perform the in-place transpose of the matrix by moving diagonally through tiles of the matrix and exchanging data from each tile with a transpose tile, wherein moving diagonally through tiles of the matrix causes each tile being transposed to be stored on a different memory channel of the plurality of memory channels from a next tile being transposed.

16. The non-transitory computer readable storage medium as recited in claim 15 , wherein the operations are scheduled in an order determined by moving diagonally from a top left corner to a bottom right corner of the matrix, and wherein subsequent operations are scheduled in an order determined by moving through the matrix in diagonal lines parallel to a line from the top left corner to the bottom right corner.

17. The non-transitory computer readable storage medium as recited in claim 15 , wherein program instructions are further executable by a processor to:
schedule operations for transposing a first tile of the matrix by accessing a first memory channel;
select a second tile of an adjacent row and an adjacent column from the first tile; and
schedule operations for transposing the second tile of the matrix by accessing a second memory channel different from the first memory channel.

18. The non-transitory computer readable storage medium as recited in claim 15 , wherein the program instructions are further executable by a processor to schedule operations for transposing tiles that are located within only a triangular portion of the matrix, and wherein tiles located outside of the

Assignees

• Advanced Micro Devices Inc

Inventors

• Gholaminejad Amir
• Natarajan Bragadeesh

Classifications

• G06F13/4282

  on a serial bus, e.g. I2C bus, SPI bus (on daisy chain buses G06F13/4247) · CPC title

• G06F2213/0042

  Universal serial bus [USB] · CPC title

• G06F2213/0026

  PCI express · CPC title

• G06F13/16

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title