International Business Machines Corporation

Fred Gehrung Gustavson

John A Gunnels

Brett Olsson

Ramesh Chandra Agarwal

Mark A Johnson

Randall Dean Groves

James C Sexton

Bruce Martin Fleischer

James Bergheim Shearer

Robert Daniel Engle

Michael K Gschwind

Jose Eduardo Moreira

Alexandre E Eichenberger

Terry L Lyon

Robert F Enenkel

Siddhartha Chatterjee

John Joseph Forrest

A method and structure for an in-place transformation of matrix data. For a matrix A stored in one of a standard full format or a packed format and a transformation T having a compact representation, blocking parameters MB and NB are chosen, based on a cache size. A sub-matrix Aof A, Ahaving size M=m*MB by N=n*NB, is worked on, and any of a residual remainder of A is saved in a buffer B. Sub-matrix Ais worked on by contiguously moving and contiguously transforming Ain-place into a New Data Structure (NDS), applying the transformation T in units of MB*NB contiguous double words to the NDS format of A, thereby replacing Awith the contents of T(A), and moving and transforming NDS T(A) to standard data format T(A) with holes for the remainder of A in buffer B. The contents of buffer B is contiguously copied into the holes of A, thereby providing in-place transformed matrix T(A).

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

A method and structure for transposing a rectangular matrix A in a computer includes subdividing the rectangular matrix A into one or more square submatrices and executing an in-place transposition for each of the square submatrices A.

Method and structure for cache aware transposition via rectangular subsections

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.

Method and structure for producing high performance linear algebra routines using composite blocking based on L1 cache size

A structure (and method) including a plurality of coprocessing units and a controller that selectively loads data for processing on the plurality of coprocessing units, using a compound loading instruction. The compound loading instruction includes a plurality of low-level software instructions that preliminarily processes input data in a manner predetermined to simulate an effect of a single hardware loading instruction that would provide optimal loading of complex matrix data by loading input data in accordance with the effect of multiplying i&#xb7;i=&#x2212;1.

Method and structure of using SIMD vector architectures to implement matrix multiplication

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.

Method and structure for producing high performance linear algebra routines using register block data format routines

A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method to at least one of reduce a memory space requirement and to increase a processing efficiency in a computerized method of linear algebra processing. A hybrid full-packed data structure is generated for processing data of a triangular matrix by one or more dense linear algebra (DLA) matrix subroutines designed to process matrix data in a full format, as modified to process matrix data using said hybrid full-packed data structure into a hybrid full-packed data structure, as follows. A portion of the triangular matrix data is determined that would comprise a square portion having a dimension approximately one half a dimension of the triangular matrix data. A first triangular portion of the triangular matrix data is fitted into a first location relative to data of the square portion, and a second triangular portion of the triangular matrix data is fitted into a second location relative to data of the square portion, such that the first triangular portion, the second triangular portion, and the square portion fit together to form the rectangular data structure. The hybrid full-packed data structure provides a substantially rectangular full format data structure for an entirety of the triangular matrix data and the triangular matrix comprises a triangular or symmetric/Hermitian matrix.

Method and structure for producing high performance linear algebra routines using a hybrid full-packed storage format

A method (and structure) for executing a linear algebra subroutine on a computer having a cache, includes streaming data for matrices involved in processing the linear algebra subroutine such that data is processed using data for a first matrix stored in the cache as a matrix format and data from a second matrix and a third matrix is stored in a memory device at a higher level than the cache, the streaming providing data from the higher level as the streaming data is required for the processing.

Method and structure for producing high performance linear algebra routines using streaming

A method (and system) for detecting at least one faulty object in a system including a plurality of objects in communication with each other in an n-dimensional architecture, includes probing a first plane of objects in the n-dimensional architecture and probing at least one other plane of objects in the n-dimensional architecture which would result in identifying a faulty object in the system.

System and method for detecting a faulty object in a system

A computerized method provides for an in-place transformation of matrix A data including a New Data Structure (NDS) format and a transformation T having a compact representation. The NDS represents data of the matrix A in a format other than a row major format or a column major format, such that the data for the matrix A is stored as contiguous sub matrices of size MB by NB in an order predetermined to provide the data for a matrix processing. The transformation T is applied to the MB by NB blocks, using an in-place transformation processing, thereby replacing data of the block Awith the contents of T(A).

A method (and structure) for executing linear algebra subroutines, includes, for an execution code controlling operation of a floating point unit (FPU) performing the linear algebra subroutine execution, unrolling instructions to preload data into a floating point register (FReg) of the FPU. The unrolling generates an instruction to load data into the FReg and the instruction is inserted into a sequence of instructions that execute the linear algebra subroutine on the FPU.

Method and structure for producing high performance linear algebra routines using preloading of floating point registers

A method (and structure) of managing memory in which a low-level mechanism is executed to signal, in a sequence of instructions generated at a higher level, that at least a portion of a contiguous area of memory is permitted to be overwritten.

Method and structure for an improved data reformatting procedure

A method (and structure) for improving at least one of speed and efficiency when executing level 3 dense linear algebra subroutines on a computer. An optimal matrix subroutine is selected from among a plurality of matrix subroutines stored in a memory that could alternatively perform a level 3 matrix multiplication or factorization processing.

Method and structure for producing high performance linear algebra routines using a selectable one of six possible level 3 L1 kernel routines

A method (and structure) of improving at least one of speed and efficiency when executing a linear algebra subroutine on a computer having a memory hierarchical structure including at least one cache, the computer having M levels of caches and a main memory. Based on sizes, it is determined, for a level 3 matrix multiplication processing, which matrix will have data for a submatrix block residing in a lower level cache of the computer and which two matrices will have data for submatrix blocks residing in at least one higher level cache or a memory. From a plurality of six kernels, two kernels are selected as optimal to use for executing the level 3 matrix multiplication processing as data streams from different levels of the M levels of cache, such that the processor will switch back and forth between the two selected kernels as streaming data traverses the different levels of cache. Data from the selected two matrices is streamed, for executing the level 3 matrix multiplication processing, so that the submatrix block residing in the lower level cache remains resident in the lower level cache.

Growing community of inventors

Briarcliff Manor, NY, United States of America

Fred Gehrung Gustavson