Method and structure for cache aware transposition via rectangular subsections

1. A method of improving at least one of an efficiency and a speed of a linear algebra processing on a computer, said method comprising:

downloading an application program from a memory of said computer holding one or more application programs in storage for execution by said computer, said application program directed to an application having at least one processing involving a linear algebra processing of matrix data; and

executing said application program on a processor of said computer,

wherein said application program accesses a library accessible to said processor of subroutines for said linear algebra processing, said library including a subroutine for performing an in-place data transposition processing of matrix data stored in a memory of said computer that stores data during execution of said application program, said subroutine comprising a method for transposing data of a rectangular matrix A to form a transpose A′ of said matrix A, said method comprising:

determining, using a processor on said computer, a largest order square submatrix within a residual of said rectangular matrix A not yet transposed;

subdividing said residual of said rectangular matrix A into one or more square submatrices A ij , each having said largest order;

executing an in-place transposition of each of said square submatrices A ij ; and

storing said transposed square submatrices A ij in a memory as data structures representing said transposed square submatrices, said data structures mapped as being concatenated in a formation of said transpose A′.

2. The method of claim 1 , wherein said transposed data is stored in a format that can be retrieved as contiguous transposed data in a stride one memory retrieval.

3. The method of claim 1 , wherein said subdividing and said in-place transposition are iteratively executed over a remaining portion of the subdivided rectangular matrix A, such that said remaining portion and said residual largest order square submatrix becomes progressively smaller.

4. The method of claim 3 , wherein the repetitive iteration of said in-place transposition is stopped at a stage before said rectangular matrix A is completely subdivided into square submatrices, said method further comprising reorganizing a remaining portion of data in said matrix A in a corresponding portion of said memory allocated for storing a transposed version of said remaining portion of data.

5. The method of claim 3 , wherein the iterative subdivision and said in-place transpositions are continued until said rectangular matrix A is completely subdivided into square submatrices, including any of a final stage wherein the largest order square submatrix is 1×1.

6. The method of claim 1 , further comprising:

establishing a mapping to re-orient said transposed square submatrices A ij ′ as representing transposed rectangular matrix A′.

7. The method of claim 6 , wherein the re-orienting is executed in an order reverse from said subdividing.

8. The method of claim 7 , wherein, if a column direction and a row direction of said rectangular matrix A are considered as complements of each other, then said mapping to re-orient each transposed square submatrices A ij ′ to form transposed rectangular matrix A′ comprises a re-orienting of said transposed submatrices A ij ′ in a complement relationship from a manner in which said square submatrices A ij were subdivided from said rectangular matrix A.

9. The method of claim 1 , wherein said in-place transposition comprises a swapping of submatrix elements via a register.

10. The method of claim 1 , as embedded in a subroutine executing a matrix operation.

11. The method of claim 10 , wherein said subroutine comprises a part of a Basic Linear Algebra Subprograms (BLAS).

12. A computer, comprising a memory system to store:

matrix data to be transposed;

a square sub-divider module, as comprising a set of instructions to be executed by a processor of said computer, to subdivide said matrix data into at least one square submatrix; and

an in-place square transpose module, as comprising a set of instructions to be executed by said processor, to transpose each said at least one square submatrix to form a transposed square submatrix,

wherein said square sub-divider module determines a size of a largest square submatrix of a residual amount of said matrix data not yet transposed and uses said determined size for the subdividing, and

wherein said square sub-divider module and said in-place square transpose module are stored in a library of subroutines, as available to an application being executed on said computer and having at least one processing involving a linear algebra processing of matrix data.

13. The computer of claim 12 , further comprising:

a re-organizer module, as executed by said processor, to determine how each said transposed square submatrix is fitted back to form a transposed matrix data.

14. The computer of claim 13 , further comprising:

an extra space module, as executed by said processor, to determine an amount of extra memory space to be reserved for a residual portion of said matrix data; and

a control module to supervise and coordinate an operation of said square sub-divider module, said in-place square transpose module, and said re-organizer module.

15. A non-transitory storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of transposing data of a matrix, said instructions comprising at least one of:

a square sub-divider module to determine a largest residual square submatrix in a matrix stored as matrix data in a memory, said matrix data associated with an application program that will use said matrix data as data for processing and that includes at least one processing involving a linear algebra processing of said matrix data, and to subdivide said matrix data into at least one square submatrix;

an in-place square transpose module to transpose each said at least one square submatrix to form a transposed square submatrix;

a re-organizer module to determine how each said transposed square submatrix is fitted back to form transposed matrix data;

an extra space module to determine an amount of extra memory space to be reserved for a residual portion of said matrix data; and

a control module to supervise and coordinate an operation of one or more of said square sub-divider module, said in-place square transpose module, said re-organizer module, and said extra space module,

wherein said square sub-divider module, said in-place square transpose module, said re-organizer module, said extra space module, and said control module are stored as components in one of:

a library of subroutines available to said application program for processing said at least one processing involving a linear algebra processing;

a library of subroutines available to a kernel that defines an execution of said linear algebra processing; and

at least one subroutine in said application program.

16. The storage medium of claim 15 , wherein said instructions are encoded on a stand-alone diskette intended to be selectively inserted into a computer drive module.

17. The storage medium of claim 15 , wherein said instructions are stored in a computer memory.

18. The storage medium of claim 17 , wherein said computer comprises a server on a network, said server at least one of:

making said instruction available to a user via said network; and

executing said instructions on data provided by said user via said network.

19. An apparatus, comprising:

means for subdividing a matrix data into one or more square submatrices of data, said matrix having size m×n, where m and n are two integers, including means to determine a largest square submatrix of a residual amount of matrix data not yet transposed;

means for executing an in-place square matrix transposition of data subdivided from said matrix data; and

means for selectively repeating said subdividing by determining a remaining largest square submatrix and executing said in-place square matrix transposition until said matrix data is completely transposed,

wherein said means for subdividing a matrix data, said means for executing an in-place square matrix transposition, and said means for selectively repeating said subdividing comprise subroutine components in a library of subroutines that are available to an application program executing on said apparatus, said application program having at least one processing involving a linear algebra processing of matrix data.

20. An apparatus according to claim 19 , further comprising:

means for re-organizing a result of said in-place square matrix transposition to form a transposed matrix data of said matrix data.