Method and structure for producing high performance linear algebra routines using composite blocking based on L1 cache size
AssigneeInternational Business Machines Corporation
InventorsFred Gehrung Gustavson, John A. Gunnels
Life of this patent
Estimating the term…
Abstract
A method (and structure) for performing a matrix subroutine, includes storing data for a matrix subroutine call in a computer memory in an increment block size that is based on a cache size.
Claims17
A method of increasing at least one of efficiency and speed in executing a matrix subroutine on a computer, said method comprising:
- for a cache on said computer having a working area size defined by dimensions k and m, k and m being integers greater than 1, with k>m, determining an integer a and, for data of a matrix to be processed by said matrix subroutine, a square block of matrix data having a size (a*m)×(a*m), such that k≧(a*m);
- and
- preliminarily storing data contiguously for a matrix subroutine call in a computer memory in an increment block size that is based on said cache working area size, a first dimension of said block size being (a*m) and a second dimension of said block size being m, thereby a of said increment blocks constitute said square block of matrix data of size (a*m)×(a*m), and each said increment block fits into said cache working area having said dimensions defined by k and m.
An apparatus, comprising:
- a processor for processing a matrix subroutine;
- a cache associated with said processor, said cache having a working area size defined by dimensions k and m, k and m being integers greater than 1;
- and a memory, wherein said memory stores data for memory calls of said matrix subroutine as contiguous data in an increment block size that is based on dimensions of said cache working area size and loads said blocks of data into said cache for said matrix subroutine processing;
- wherein said processor determines an integer a and, for data of a matrix to be processed by said matrix subroutine, a square block of matrix data having a size (a*m)×(a*m), such that k≧(a*m), and a first dimension of said increment block size is (a*m) and a second dimension of said block is m, thereby a of said increment blocks constitute said square block of matrix data of size (a*m)×(a*m) and each said increment block of size (a*m)×m fits into said cache working area defined by k and m.
A non-transitory signal-bearing storage device comprising a machine-readable medium tangibly embodying-a program of machine-readable instructions executable by a digital processing apparatus, said instructions including a method of storing data for a matrix subroutine call in a computer memory in an increment block size that is based on a cache size of said computer, said cache having a working area size defined by dimensions k and m, where k and m are integers greater than 1 and k>m, said method comprising:
- determining an integer a and, for data of a matrix to be processed by said matrix subroutine, a square block of matrix data having a size (a*m)×(a*m), such that k≧(a*m);
- and
- preliminarily storing data contiguously for a matrix subroutine call in a computer memory in an increment block size that is based on said cache working area size, a first dimension of said block size being (a*m) and a second dimension of said block size being m, thereby a of said increment blocks constitute a square block of matrix data and each said increment block of size (a*m)×m fits into said cache working area defined by k and m.
Dependencies are inferred from the claim text.