# US 2008/0313441 A1 · Method and structure for producing high performance linear algebra routines using register block data format routines

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0313441 A1
- Document ID: US20080313441A1
- Status: Published application
- Kind: A1
- Application number: 12/196,095
- Filed: 2008-08-21
- Published: 2008-12-18
- Earliest claimed: 2003-09-29
- Assignees: International Business Machines Corporation
- Inventors: Fred Gehrung Gustavson; John A. Gunnels; James C. Sexton
- Web page: https://patentgrep.com/patent/US20080313441A1

## CPC

- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method (and structure) of executing a matrix operation, includes, for a matrix A, separating the matrix A into blocks, each block having a size p-by-q. The blocks of size p-by-q are then stored in a cache or memory in at least one of the two following ways. The elements in at least one of the blocks is stored in a format in which elements of the block occupy a location different from an original location in the block, and/or the blocks of size p-by-q are stored in a format in which at least one block occupies a position different relative to its original position in the matrix A.

## Claims

### Claim 1

A computer, comprising:
a processor;
a memory system; and
a co-processing unit with an associated plurality of data registers for data exchange and used as working registers by said co-processing unit,
wherein said computer is controlled to implement a method of increasing efficiency in executing a processing by said co-processing unit that uses data stored in said memory system in a standard format, said standard format comprising one of a column major format and a row major format, said method comprising:
for said data stored in said standard format in said memory system, using said processor to separate said data into blocks of data, each data block having a size p-by-q, where p and q are small integers such that said data will be loaded into said data registers in increments of said data blocks; and
using said processor to rearrange and store said data blocks, thereby said data is stored in said memory system in a format different from said standard format.

### Claim 2 (depends on 1)

The computer of claim 1, wherein said processor rearranges and stores said data blocks so that said data blocks are stored contiguously in said memory system in a manner that said data will be consumed by said co-processor processing of said data.

### Claim 3 (depends on 1)

The computer of claim 1, wherein said data blocks are repetitively retrieved from said memory system during said co-processor processing of said data.

### Claim 4 (depends on 1)

The computer of claim 1, wherein said co-processor processing comprises a matrix operation.

### Claim 5 (depends on 1)

The computer of claim 1, wherein said data registers each comprises storage for an even number of 32-bit words.

### Claim 6 (depends on 5)

The computer of claim 5, said blocks of data stored in said memory system comprise blocks of four 32-bit words, so that p=q=2, said data registers comprise storage for two 32-bit words, and said four 32-bit words of a data block are loaded into said data registers using a quad-loading format wherein said four 32-bit words of said data block are accessible in units of four single-word lengths, as appropriate for two of said data registers.

### Claim 7 (depends on 6)

The computer of claim 6, wherein said quad-loading format selectively permits said an ordering of said four single-words to be reversed.

### Claim 8 (depends on 1)

The computer of claim 1, wherein said selective reversing of single-words in combination with said rearranging of data blocks together comprises a method of overcoming a hardware disadvantage on said computer relative to a specific processing on a specific computer architecture/set of instructions using said co-processing unit, said hardware disadvantage reducing an efficiency of said specific processing, said method thereby comprising:
using first software instructions to preliminarily process input data by said processor in a manner to generate a first error relative to said specific processing, said first error comprising a conversion of said input data into a predetermined new format of said input data; and
using second software instructions to subsequently process said input data in said new format in a manner to generate a correcting error relative to said specific processing, said correcting error comprising a loading said input data into said plurality of data registers in a new word order of said input data,
wherein said first software instructions in combination with said second software instructions overcome said disadvantage and provides a correct result for said processing of said data.

### Claim 9 (depends on 1)

The computer of claim 1, wherein said rearranging of data blocks permits said data to be loaded from said memory system into said co-processor data registers more efficiently than if said data were loaded as stored in said standard format.

### Claim 10

A method of improving at least one of a processing speed and a processing efficiency on a digital processing apparatus, said method comprising:
for data stored in a memory in a standard format, said standard format comprising one of a column major format and a row major format, separating said data into blocks of data, each data block having a size p-by-q, where p and q are small integers such that said data will be loaded into data registers in increments of said data blocks; and
rearranging and storing said data blocks in said memory, thereby said data is stored in said memory in a register block format that is different from said standard format.

### Claim 11 (depends on 10)

The method of claim 10, further comprising: repetitively retrieving said data blocks from said memory for consumption in a processing being executed on said digital processing apparatus.

### Claim 12 (depends on 10)

A computer-readable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of storing data in register block data format, as described in claim 10.
