Method and structure for fast in-place transformation of standard full and packed matrix data formats

1. A computerized method for an in-place transformation of matrix data, said method comprising:

for a matrix A having a size M×N, as stored in a memory of a computer in one of a standard full format or a packed format in one of a column major format or a row major format, and for a transformation T having a compact representation, choosing blocking parameters MB and NB based on a cache size of the computer such that MB*NB lies between an L1 cache size and an L2 cache size, and using a processor on the computer to perform the steps of:

determining a size M 1 ×N 1 for blocking matrix A into a plurality of sub-matrices, and values m and n, such that M 1 =m*MB and N 1 =n*NB;

determining whether any residual exists in said matrix A data if matrix A is blocked into sub-matrices, by determining whether either r or q is greater than zero, where M=m*MB+r and N=n*NB+q, and, if so, allocating at least one buffer area in memory and moving any said residuals r and/or q, respectively, into said at least one buffer area;

executing a contraction processing on data of matrix A 1 =A(0:M 1 −1,0:N 1 −1) to convert said data in-place to an array space A(0:M 1 *N 1 −1);

converting said array space A(0:M 1 *N 1 −1) into a New Data Structure (NDS) matrix A 1 wherein said data is stored in memory as contiguous data in increments of blocks of said size MB×NB;

transforming, in-place, said matrix A 1 in NDS format by sequentially reading into the cache, transforming, and storing each MB×NB block;

executing an expansion processing to convert said transformed matrix A 1 in NDS format back into said one of column major format or row major format, leaving a hole or holes to replace the residual data of said at least one buffer area; and

executing an out-of-place transformation of contents of said at least one buffer area and storing the out-of-place transformed data into said hole or holes.

2. The method of claim 1 , wherein said matrix A is stored as said standard full format and said NDS comprises a rectangular block (RB) format.

3. The method of claim 1 , wherein said matrix A is stored as said packed format and said NDS comprises a Square Block Packed (SBP) format.

4. The method of claim 1 , wherein said data transformation comprises a matrix transposition.

5. The method of claim 1 , as implemented by an entity providing consultation services.

6. The method of claim 1 , wherein a transformation T has a compact representation if said transformation, having size N, can be represented by a formula that uses a constant amount of space, independent of N.

7. The method of claim 1 , wherein said data transformation comprises a matrix transformation between lower Square Block Packed Format (SBPF) and upper SBPF formats or between upper SBFT and lower SBPF formats.

8. The method of claim 1 , wherein said data transformation comprises a matrix transformation between a packed format and a rectangular full packed (RFP) format or between RFP and packed formats.

9. The method of claim 1 , wherein “in-place” means that a permutation of data is returned to a same location in a memory as used for the data originally.

10. An apparatus, comprising

a memory to store a matrix A of size M×N in one of a standard full format or a packed format, as stored in one of a column major format or a row major format, and instructions for performing a transformation T having a compact representation;

a hierarchical cache system comprising at least one an L1 cache and an L2 cache; and

a processor performing said transformation on said matrix A by:

choosing blocking parameters MB and NB based on a cache size such that MB*NB lies between a size of the L1 cache and a size of the L2 cache;

determining a size M 1 ×N 1 for blocking matrix A into a plurality of sub-matrices Ai, and values m and n, such that M 1 =m*MB and N 1 =n*NB;

determining whether any residual exists in said matrix A data if matrix A is blocked into submatrices Ai by determining whether either r or q is greater than zero, where M=m*MB+r and N=n*NB+q, and, if so, allocating at least one buffer area in memory and moving any said residuals r and/or q, respectively, into said at least one buffer area;

executing a contraction processing on data of matrix A 1 =A(0:M 1 −1,0:N 1 −1) to convert said data in-place to an array space A(0:M 1 *N 1 −1);

converting said array space A(0:M 1 *N 1 −1) into a New Data Structure (NDS) matrix A 1 wherein said data is stored in memory as contiguous data in increments of blocks of said size MB×NB;

transforming, in-place, said matrix A 1 in NDS format by sequentially reading into the cache, transforming, and storing each MB×NB block;

executing an expansion processing to convert said transformed matrix A 1 in NDS format back into said one of column major format or row major format, leaving holes to replace the residual data of said buffer areas; and

executing an out-of-place transformation of contents of said at least one buffer area and storing the out-of-place transformed data into said holes.

11. The apparatus of claim 10 , wherein said matrix A is stored as said standard full format and said NDS comprises a rectangular block (RB) format.

12. The apparatus of claim 10 , wherein said matrix A is stored as said packed format and said NDS comprises a Square Block Packed (SBP) format.

13. The apparatus of claim 10 , wherein said data transformation comprises a matrix transposition.

14. A non-transitory, machine-readable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a computerized method for an in-place transformation of matrix data, wherein said digital processing apparatus comprises a hierarchical cache system comprising at least one an L1 cache and an L2 cache, a memory, and a processor executing said method comprising:

for a matrix A having size M×N, as stored in the memory in one of a standard full format or a packed format in a column major format or a row major format, and a transformation T having a compact representation, choosing blocking parameters MB and NB based on the cache size such that MB*NB lies between the L1 cache size and the L2 cache size;

determining a size M 1 ×N 1 for blocking matrix A into a plurality of sub-matrices Ai, and values m and n, such that M 1 =m*MB and N 1 =n*NB;

determining whether any residual exists in said matrix A data if matrix A is blocked into submatrices Ai by determining whether either r or q is greater than zero, where M=m*MB+r and N=n*NB+q, and, if so, allocating at least one buffer area in memory and moving any said residuals r and/or q, respectively, into said at least one buffer area;

executing a contraction processing on data of matrix A 1 =A(0:M 1 −1,0:N 1 −1) to convert said data in-place to an array space A(0:M 1 *N 1 −1);

converting said array space A(0:M 1 *N 1 −1) into a New Data Structure (NDS) matrix A 1 wherein said data is stored in memory as contiguous data in increments of blocks of said size MB×NB;

transforming, in-place, said matrix A 1 in NDS format by sequentially reading into cache, transforming, and storing each MB×NB block;

executing an expansion processing to convert said transformed matrix A 1 in NDS format back into said one of column major format or row major format, leaving a hole or holes to replace the residual data of said at least one buffer area; and

executing an out-of-place transformation of contents of said at least one buffer area and storing the out-of-place transformed data into said hole or holes.

15. The machine-readable storage medium of claim 14 , wherein said matrix A is stored as said standard full format and said NDS comprises a rectangular block (RB) format.

16. The machine-readable storage medium of claim 14 , wherein said matrix A is stored as said packed format and said NDS comprises a Square Block Packed (SBP) format.

17. The machine-readable storage medium of claim 14 , wherein said data transformation comprises a matrix transposition.

18. The machine-readable storage medium of claim 14 as comprising one of:

a hard drive memory on a computer;

a RAM memory on a computer;

a storage device associated with a server; and

a standalone diskette of instructions to be inserted into a computer.