US 5,099,447 AGrant
Blocked Matrix Multiplication for Computers With Hierarchical Memory
Issue Date:1992-03-24
•21 Claims
•23 Drawing Sheets
Abstract
A matrix multiplication method that is particularly well suited for use with a computer having hierarchical memory. The A and B term matrices are broken down into blocks and a sum of a series of outer products is computed in order to generate product matrix blocks. Reads to cache or other faster, high-level storage and writes to main memory are interleaved with the calculations in order to reduce or elimiante processor stalling. Individual blocks may be computed by separate processors without requiring communication of intermediate results.
Metadata
Assignee
- Alliant Computer Systems Corporation
Inventor
- Mathew Myszewski
Application Information
Application Number:US 4679628
Filing Date:1990-01-22
Priority Date:1990-01-22
Art Unit:231
Classifications
IPC:
G06F 15347
Field of Search:
364754;736
Patent Drawings (23 sheets)
Description
Background of the Invention
This invention relates to methods for multiplying matrices using computers with hierarchical memory.
The multiplication of matrices is an important operation for computers. It is useful for a wide variety of operations, one of them being the solution of simultaneous equations. In the interest of efficiency, it is highly desirable to perform these operations quickly. For example, a simulation for the purpose of research and/or development that can run more quickly will enhance the productivity of the scientist or engineer without added hardware costs.
In the solution of large matrix multiplications in large or real time problems, scientists and engineers have turned to supercomputers which include high speeds of operation, pipelined architectures and/or parallel processing. A series of libraries of subroutines has been developed for matrix multiplication, among other operations, on these machines. These subroutine libraries provide the high-level function of matrix multiplication, and are available on a variety of supercomputers. The subroutine is usually written for a specific machine, taking that machine's architecture into consideration. In this way, the programmer may make calls to a simple matrix algebra subroutine and expect rapid performance from the system. Commonly used subroutine libraries of this kind are the BLAS subroutine libraries (Basic Linear Algebra Subprograms). The BLAS3 subroutine library contains matrix operation subroutines and in particular a subroutine called DGEMM which performs matrix multiplications. For more information on BLAS, see C. Lawson, R. Hanson, D. Kincaid and F. Krogh, "Basic Linear Algebra Subprograms for FORTRAN Usage", ACM Trans. on Math. Soft., 5 (1979), 308-325, or J. J. Dongarra, J. DuCroz, S. Hammarling and R. Hanson, "An Extended Set of Linear Algebra Subprograms", ACM Trans on Math. Soft., 14,1 (1988) 1-32. For more information on BLAS3, see J. J. Dongarra, J. DuCroz, I. Duff, and S. Hammarling, "Set of Level 3 Basic Linear Algebra Subprograms", ACM Trans on Math. Soft. (Dec. 1989).
In designing these subroutines, speed is important. For any given architecture, there are several limiting parameters that affect matrix multiplication speed. A first limiting parameter is the number of computations needed to perform the operation. Upon first consideration, it would seem that the order of the number of operations needed to perform a matrix multiplication would be n.sup.3, where n.sup.2 is the number of elements in each of the term matrices.
It has been shown, however, that this order can be reduced to n.sup.2.49, by using asymptotic complexity reduction methods of the type of Strassen's. This can lead to greater computational efficiency for large matrices, although there may be some accuracy tradeoffs. Strassen's method, and an implementation thereof, are discussed in "Gaussian Elimination is Not Optimal", Numerische Mathematik, Vol. 13, 1969, pp. 354-356 by V. Strassen, and "Extra High Speed Matrix Multiplication on the Cray-2", SIAM J. Sci. Stat. Comput., Vol. 9, No. 3, May 1988, by D. H. Bailey. Other asymptotic complexity reduction methods are discussed in V. Pan, "New Fast Algorithms for Matrix Operations", SIAM J. Comp., 9 (1980), 321-342.
A second parameter in speeding up matrix multiplication is system power. The clock speed, word size and number of processors limit the number of operations that may be performed in any given amount of time, and thus the speed at which matrix multiplications may be performed. Improvements along this line have included using faster processors with larger word sizes and using parallel processors. The use of parallel processors has allowed programmers to break the problem up into separate sub-problems and allocate these sub-problems to different processors. These so-called "blocked" methods allow speed improvements by performing more than one operation in parallel.
Another, more elusive, limiting parameter is memory performance. Two components of memory performance of interest are memory bandwidth and memory latency. Memory bandwidth is indicative of the overall available throughput rate of data from the memory to the processor. Memory latency is a measure of the time taken to retrieve the contents of a memory location, measured from the time at which it is requested to the time at which it is delivered to the requesting processor. Both latency and bandwidth may be degraded from the point of view of a processor if it must share its memory resources with other processors or peripheral devices. Computational methods may be affected by one or both of these limiting parameters, as the processor may be forced to stall while waiting for data from memory.
These problems have been addressed by computer designers in different ways. Memory bandwidth has been increased by using memories that cycle faster, and by using larger word sizes. Latency has been addressed by using memories with faster access times and by making computers more hierarchical. This involves adding small areas of expensive high speed memory that are local to a processor. Examples of hierarchical memory include cache memories, virtual memory, and large register sets.
If one ignores latency and bandwidth issues in implementing a method of matrix multiplication, one may have a method that is theoretically efficient, as it reduces the order of the number of operations to be performed or it splits the operations into blocked operations that may be performed by several processors, but still falls short of good performance. This may happen because the processing rate is slower than optimal as the processor spends a lot of time waiting for slow memory fetches or because it is competing for access to a shared memory resource.
This problem has become more pronounced as computers tend to include more hierarchical elements, as memory elements tend be shared more often, and as processors are getting faster and more complex, while large semiconductor memories, disks and other mechanical storage systems have not increased in speed at the same pace.
Blocked methods for matrix multiplication have been used for computers with hierarchical memories (K. Gallivan, W. Jalby, U. Meier and A. Sameh, "Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design", The International Journal of Supercomputer Applications, 2,1 Spring 1988, 12-48).
Summary of the Invention
In general the invention features a matrix multiplication method that is particularly well suited for use with a computer having hierarchical memory. The A and B term matrices are broken down into blocks (except in the case of small matrices where each matrix constitutes one block) and a sum of a series of outer products is computed to generate blocks of the result matrix C. Fetching of elements of the A and B matrices into cache or other high-level storage is performed during (e.g., by being interleaved with) multiplication and/or addition operations in order to reduce or eliminate processor stalling.
In preferred embodiments, store operations for storing elements of the result matrix into main memory are also done by interleaving the operations with multiplication and/or addition operations. A matrix update operation (C=A.times.B+C) is performed, with elements of the initial values of matrix C being fetched during multiplication and/or addition operations. Elements of the matrices are double buffered (e.g., a newly fetched element of matrix A is placed in one side of a two element buffer and swapped with the previously used element). Elements of the A matrix are double buffered element-by-element, elements of the B matrix B are double buffered row-by-row, and elements of the C matrix are double buffered block-by-block. Individual blocks of the result matrix may be computed by separate processors without requiring communication of intermediate results; distribution of blocks among the processors is based on a size dependent sequencing method to reduce differences in completion times between processors. The method may operate on transposed A or B matrices.
This matrix multiplication method has the advantage of improving speed of execution by reducing the impact of both memory bandwidth and memory latency. The impact of memory latency is reduced by fetching operands in advance, while multiplications of the previous operands take place. The impact of memory bandwidth is reduced as the method of the invention actually requires fewer fetches overall than would a conventional technique. The combination of these two effects will cause the speed of the matrix multiplication to be increased.
The fact that this is a blocked method allows multiple processors to work on a single matrix multiplication at the same time, in any combination, and without any need to communicate intermediate results between processors.
Furthermore, the method is advantageous in that it may be used in conjunction with Strassen's method or other similar techniques for further savings in computation time.
Other features and advantages of the invention will be apparent from the following description of a preferred embodiment and from the claims.
Description of the Preferred Embodiment
FIG. 1 is a diagram of a first step in conceptually partitioning the task of multiplying two matrices according to the invention.
FIG. 2 is a diagram of a second step in this conceptual partitioning process.
FIG. 3 is a diagram of a third step in this conceptual partitioning process.
FIG. 4 illustrates the computation of outer products on the matrix blocks.
FIG. 5 illustrates the individual scalar-scalar products which make up one of the outer products.
FIG. 6 illustrates the double buffering of the first term matrix block elements.
FIG. 7 illustrates the double buffering of the second term matrix block rows.
FIG. 8 illustrates the double buffering of the result matrix blocks.
FIG. 9 is a diagram showing a possible allocation of matrix blocks to two processors.
FIG. 10 is a diagram showing the status of selected blocks during the operation of the method of the invention.
FIG. 11 is a state diagram illustrating the overlap of operations different situations.
FIGS. 12a and 12b are execution time diagrams comparing the times taken to compute the results of the matrix multiplication of FIG. 9 using two different processing sequences.
FIGS. 13-27 are a flowchart for an implementation of the method of the invention, corresponding to the FORTRAN and assembly language program of appendix A.
The method of matrix multiplication of the invention performs computations on blocks of the term matrices and assembles the results into a result matrix. The size of the blocks depends on the particular implementation. To understand the rationale for operating on blocks of the matrix, the matrices may be broken down conceptually as follows.
The first conceptual partitioning of the matrices is simple, and can be understood in connection with FIG. 1. In multiplying two matrices (A.times.B=C), the elements of the result matrix C are each a sum of the products of individual elements of a row of the first term matrix A and the corresponding elements in the corresponding column of the second term matrix B. Thus, referring to FIG. 1, the elements in the shaded block 14 of result matrix C 17 depend only on the elements in the shaded blocks 10, 12 of term matrices A and B.
The second conceptual partitioning is shown in FIG. 2. Again, it may be appreciated that the elements in the shaded block 18 of result matrix C 17 depend only on the elements in the shaded blocks 10, 16 of term matrices A and B. The elements of this shaded block 18 may thus be generated independently from other like blocks.
The third step of the breakdown, shown in FIG. 3, is a little more complicated, and leads to the blocks that the method actually uses. Here, the shaded block 18 of the result matrix 17 is a result of the sum of a complete series of outer products of each of the pairs of term matrix blocks associated with an arrow 20 & 30, 22 & 32, 24 & 34, 26 & 36. The problem has now been reduced to a sum of a series of outer products. The meaning of a "complete series of outer products" will be clarified further on.
It should be noted that the decision to divide the shaded areas 10, 16 into four blocks is for the purposes of illustration, and that the matrix could be divided into a number of block sizes. In practice, the optimum size of the matrix blocks will depend on computer system parameters such as cache size, and tradeoffs to be discussed later on. It should also be noted that the width of the blocks in the first term matrix should be the same as the height of the corresponding blocks in the second term matrix.
An outer product of a column vector and a row vector is defined as the matrix product of the column vector and the row vector, in that order. Thus, in FIG. 4, the outer product of the first column 40 of the first term matrix block 30 and the corresponding row 42 of the second term matrix block 20 will yield resulting elements for all locations of the result matrix block 18.
This operation is repeated in part II of FIG. 4 on the second column 46 and corresponding row 48 of the term matrix blocks to form a second outer product which will also have elements for all locations of the result matrix block 18. These elements are added to the results already stored in result matrix block 18 to form an updated result matrix block 18. This process is repeated until there are no corresponding pairs of rows and columns left in the pair of term matrix blocks. In this case, there are three columns in the first term matrix block 30 and three corresponding rows in the second term matrix block 20, and thus part III of FIG. 4 completes the series of outer products. The size of these blocks, as was implied earlier, can be other than three-by-three.
Performing these operations constitutes summing a complete series of outer products for a pair of corresponding term matrix blocks. It bears noting that this series of outer products amounts to a matrix multiplication operation for the first pair of term matrix blocks 20, 30 in the computation of result matrix block 18. The final value of the result matrix block 18, however, will be obtained by computing the sum of the complete series of outer products for all of the corresponding pairs of term matrix blocks. The results obtained in computing the outer products for the rest of the pairs of term matrix blocks 22 & 32, 24 & 34, 26 & 36 are each added to the result matrix block 18 as they are evaluated in a running sum, and thus the matrix products of these pairs are not explicitly computed.
In fact, it is useful to write a subroutine that performs a matrix update operation: C=A.times.B+C, and in this case, the outer products of the first pair of term matrix blocks 20, 30 are simply added to the current C matrix elements as they are computed. Subsequently computed outer products are added to the result matrix, as before. Providing a zero C matrix allows the user to compute the simple matrix product C=A.times.B with this matrix update subroutine.
When the outer products for all of the pairs of corresponding first and second term matrix blocks have been accumulated to form a final result matrix block 18 (i.e. when the sum of a complete series of outer products for each block has been formed), the result matrix block 18 will contain result elements of the overall matrix product or matrix update. The preceding operation may then be performed on further sets of term matrix blocks to obtain the complete solution of the matrix multiplication.
Referring now to FIG. 5, the computation of the outer products is discussed in more detail. Each outer product will be broken down into a succession of scalar-scalar multiplications which the processor executes. The whole of FIG. 5 shows the operations performed in a single outer product; that of the first column 40 of the first term matrix block a 30 and the first row 42 of second term matrix block b 20. This product is computed in the following sequence.
First, the first element 50 of the column 40 of the first term matrix block 30 is multiplied successively by the elements 52, 54, 56 of the first row 42 of the second term matrix block 20 to form the elements 62, 64, 66 of the first row of the result matrix block 18.
This process is repeated (part ii of FIG. 5) for the next element 70 of the first column, and the same elements 52, 54, 56 of the same row to form the elements 72, 74, 76 of the second row of the result matrix block 18. This process is repeated until there are no more elements in the row and column operand vectors.
It should be mentioned that the outer products could be evaluated in different orders, and the final result would be the same.
The method achieves its speed advantages by fetching the operands from their locations in memory into the cache (or other faster memory in a hierarchal system) before they are needed. In this way, every element is ready to be operated on before the operation takes place and little time is spent waiting for operands. This is possible because modern processors are usually pipelined and a fetch from memory can take place while other operations are being performed on data in the cache. The block size can be chosen to be large enough to compensate for the latency of these fetches.
The fetching of the operands is interleaved with the matrix outer product computations. Before or while each element of a column of a first term matrix block is multiplied by the corresponding row of elements of the corresponding second term matrix block (e.g., during or just before the scalar-vector multiplication of part i of FIG. 5), the element that will be used in the next computation (i.e., the next element 70 of the column 40 of the first term matrix block 30) is fetched into the cache or other high level storage. In this way, the element will be available before the multiplications of part i are finished and the operations of part ii of FIG. 5 are ready to be started.
When a first matrix element (e.g., 70) is fetched into the cache, it is stored in a storage area allocated for that purpose. Since the current first term matrix block element (e.g., 50) is being used for computation, the storage area allocated for the fetched element is different from that used for the current element. When the next operation is to take place and the next element is needed, a swap of these two storage areas takes place.
This swap can be performed by changing pointers, as illustrated in FIG. 6. A pointer 80 points to the value to be used for computations, which is stored in a first cache storage location 86. While the computations are being performed, the next element is fetched into a second cache storage location 84 pointed to by a second pointer 82. When the computations on the current element are finished, the computation pointer 80 is updated to point to the second storage location and the pointer 82 is updated to point to the first storage location. The cycle is then repeated. The updating of these pointers will take place between the scalar-vector products of the outer products (e.g., after part i of FIG. 5, and before part ii of FIG. 5). This technique is commonly known as double buffering.
Also fetched between scalar-vector products is an element of the next row of the matrix block which is to be used in the next series of computations (i.e., element b.sub.22 -68). If one element of this row is fetched when each element of the column is multiplied by its corresponding row and the matrix blocks are square, the elements of the row will also be readily available in the cache when it comes time to perform the computations for the next row. Again referring to FIG. 5, the above operation would proceed as follows. Before or during the multiplication in part i, the processor would initiate a fetch of the corresponding element in the next row (i.e., b.sub.21 - 58). Before or during part ii, element 68 would be fetched. In this way, after all of the multiplications and corresponding fetches (i-iii for the exemplary three-by-three matrix blocks), the next whole row will be ready for processing.
These elements are also double-buffered, this time into a row-sized buffer instead of a single-element buffer. This level of double buffering is illustrated in FIG. 7. The operation of this double buffering is similar to the earlier described double buffering. The swaps occur after completion of a row of fetched elements (e.g., between parts I and II of FIG. 4), instead of after retrieval of a single element as is the case for elements of the first term matrix block.
Elements of the result matrix blocks are also double-buffered. In this case, however, the double buffering takes place for reading and writing. As the outer products are being computed, elements of the next result matrix block are being retrieved into an allocated storage area in the cache. These elements are elements of the initial C matrix that is to be updated in a matrix update operation. Once a result matrix block is computed, the next result matrix block may be swapped in using a pointer, as was done for the elements of the first and second term matrices, respectively.
It is noted that while this next result matrix block is being retrieved from memory, the previous result matrix block is being stored in memory. These operations are performed in a manner that is interleaved with the computations as was the case for rest of the double buffering operations.
FIG. 8 shows this double buffering. The elements of the next and previous result matrix blocks are retrieved and written respectively at the same intervals as the first and second term matrices are retrieved (e.g., before or during operation i, ii and iii of FIG. 5). In this way, the next whole result matrix block will be retrieved once the current block has been operated upon, and pointer 89 may then be updated in order to start operating on this next whole result matrix block. If writes of this result buffer are performed before reads, the same buffer may be used to store both the elements fetched in and those to be written out.
The double buffering of the result matrix blocks may be further understood in conjunction with FIGS. 9, 10 and 11. In FIG. 9, an exemplary choice of matrix block allocations to processors is shown. Blocks marked with P1 are to be processed by one processor and blocks marked with P2 are to be processed by another processor. There could be more processors, of course.
The first operation performed by processor P1 will be to generate the result matrix block 128 from the top row (blocks 120, 122) of matrix A and the first column (blocks 124, 126) of matrix B, using the sum of outer products as described earlier. The second and third operations for processor Pl will be to generate result matrix blocks 130 and 132, respectively.
The situation illustrated in FIG. 9 is of the status of the method while it is computing the outer products for result matrix block 130. A pointer C1 points to result matrix block 130, and is used to access that block. Similar pointers are used to point to other blocks in the first term, second term and result matrices. Not only do the pointers that indicate the locations in the cache of the operands and results have to be updated, but the pointers (A1, B1, C0, etc.) that are used to determine where the contents of these cache storage locations are to be loaded from or written to must also be updated. This pointer update is performed when a processor starts to perform computations on a new matrix block.
The elements of result matrix block 130 were read into cache storage during the computation of result elements of block 128, in an interleaved manner as described earlier. The result elements 128 are now being transferred from the cache into their final destination in memory, as a second block of result elements 130 is being computed. Also taking place during the computation of this second block of result elements, are reads of the next result matrix block 132.
The resulting sequence of operations includes computations interleaved with reads and writes as follows:
1. Read one b element.
2. Write one c element.
3. Read one c element.
4. Read one a element.
5. Compute one vector of outer product.
This overall sequence is illustrated in more detail in FIG. 10.
It should also be apparent that all of the forms of interleaving are not always happening. This is true at the end and beginning of the computations. If only one result matrix block is being processed by an individual processor, there will be no reason to fetch any further operands, for example. FIG. 11 is a state diagram which illustrates this.
Upon startup of the method, only reading takes place, as no values are available for computation. This state is represented by the box 100. If no further result matrix blocks are to be processed, computations are performed on the read values, as represented by box 102. The results are then written out as represented by box 104.
If consecutive blocks are processed, reading and computations will take place at the same time, as represented by box 106. If only two blocks are processed, the results of the first computations will be written out at the same time that the computations on the second block take place. This situation corresponds to box 108. If more than two blocks are being processed consecutively, writing, reading and computations will all take place simultaneously corresponding to box 110. This situation may continue for as long as there are matrix blocks to process.
From the above discussion it might seem that smaller block sizes would make the method more efficient, as more time would be spent in the situation of box 110, where three operations are being performed at once. This advantage is offset by the latency involved with the fetch of each block, and hence a compromise block size needs to be found. This block size will be also be constrained by the amount of cache or other high-level storage available to the processor. On an Alliant FX/2800, it was found that a block size of about 20.times.20 elements was efficient for 64 bit precision.
It will be remarked that the end matrix blocks 140, 142, 144 and the bottom matrix blocks 146, 148, 150 of the result matrix of FIGS. 9 and 10 are not square. This is necessary if arbitrary matrix sizes are to be accommodated, as not all matrices will divide evenly into square blocks. Similar methods with fetch overlapping may be used for these blocks, but the full benefit will not be obtained. However, since these remainder blocks will typically represent small percentages of the matrix, the savings will not represent a large portion of the overall time taken to compute the matrix product, and hence it may be acceptable to use conventional methods on these blocks.
It is useful to schedule these remainder blocks after the regular blocks so that the largest ones are computed first, as the subroutine will tend to finish earlier. This may be seen in connection with FIG. 12. FIG. 12a is an example of a well sequenced scheduling of result matrix blocks for the matrix of FIG. 9. The larger bars 160 represent the time taken to compute the regular matrix result matrix blocks (e.g., 128, 130 of FIG. 9). The smaller bars 162, 164 and 166 represent the time taken to compute the remainder matrix blocks (e.g., 142, 146 and 150 respectively). It can be seen that if the blocks are processed in order of size, the blocks will be well distributed between processors P1 and P2.
FIG. 12b illustrates what might happen if this size-dependent sequencing was not used. From this diagram, it can be seen that some orderings exist that lead to less even distribution of the tasks between processors, and that resulting execution times may be longer (T.sub.2 >T.sub.1)
The matrices described herein have tended to be quite small, to simplify the explanation of the invention efficiently. However, real applications where this technique is of most value involve much larger matrices than those described in detail herein. Matrices with thousands of rows and columns are not uncommon.
For the purpose of describing the invention more fully, two computer programs have been included in this document. The first is an illustrative program written in the style of the well-known C programming language. This incomplete program is not intended to be directly compiled and run, only to be used as an aid in understanding the invention. An actual implementation of the method of the invention in the form of a program primarily written in assembly language (with some FORTRAN) for an Alliant FX/2800 computer is included in Appendix A. Assembly language was chosen for the final implementation as it permits the programmer to implement the method in a manner that will lead to the most efficient operation on a specific machine.
The illustrative C language program is now described. This program is a matrix update procedure which performs the matrix update operation C=A.times.B+C. It accepts as parameters matrices in the form of arrays of floating point elements (A, B and C), their leading offset dimensions (lda, ldb, ldc), and their dimensions (N1, N2, N3). The leading offset dimensions are included to allow for offset in the case where one or more of the matrices operated upon are to be sub-matrices of larger matrices. This feature is useful in performing operations on parts of matrices, such as Gaussian elimination. The program needs these leading dimensions in order to manipulate the matrix array indices. The matrix dimension N- is the number of rows in the A and C matrices, N2 is the number of columns in the B and C matrices, and N3 is the number of columns in the A matrix which is the same as the number of rows in the B matrix.
The first portion of the C program includes variable initialization statements (see below). I, J, i, j, and k are loop counters. n1 is the block size to be used for forming the matrix blocks. m1, m2, m3 represent the number of blocks in the dimensions N1, N2, N3 respectively. ac, ar, bc, br, cc, cr are pointers to the cache buffers used in double buffering the elements from matrix A, the rows from matrix B and the blocks from matrix C. The variables A0, A1, B0, B1, C0, C1 and C2 are pointers which are used to point to blocks to be operated upon in the A, B and C matrices which will remain in main memory. This initialization section follows.
The rest of the program performs the multiplication operations on the matrices. It consists of five nested loops. Each iteration of the innermost loop (index j) computes one scalar-scalar product within an outer product and adds the result to the current result matrix block's cache calculation storage buffer cc. The cumulative effect of this loop is to compute a scalar-vector product, like that of part i, ii or iii of FIG. 5.
While performing this function, the fetch of an element of the next row of the term matrix block b is initiated. This element is stored in the retrieval storage buffer br. The storage of an element of the previous c matrix from retrieval buffer cr into main memory is also initiated. An element of the next c matrix block may now be retrieved into retrieval buffer cr, and the next c element may also be retrieved into retrieval buffer ar.
Once the scalar-vector product of the j loop has been computed, the pointers to the a buffers are swapped in order to point to the next element, and a further iteration of the surrounding i loop is started. The cumulative result of the i loop is to compute a complete outer product.
When a complete outer product is formed, the pointers to the row-sized b buffers are swapped in order to point to the next row using the exchange function (not shown), and the next outer product is computed. The k loop repeats these outer products until a complete series of outer products have been computed for the first pair of term matrix blocks (e.g., the operations on term matrix blocks 152 and 156 in the generation of result matrix block 130 in FIG. 9). This portion of the program is reproduced below.
A second k loop is then entered. This loop performs the same operations as the previous loop, with the exception of the fetches and writes to the c blocks, as these have already been performed. This second k loop finishes the outer products for the rest of the pairs of term matrix blocks (e.g., the operations on term matrix blocks 154 and 158 in the generation of result matrix block 130 in FIG. 9). The pointers to the matrix blocks cr, cc are now switched, so that the next matrix blocks may be processed.
In this simple illustrative example, the result matrix blocks are simply evaluated consecutively, by the same processor, and the above operation will be executed by the I and J loops until there is but one more block to process. At that point, the following code will execute. This code is similar to the above code except that it does not fetch elements of the next c block, since there is none.
The above program is not complete, for lack of a number of functions. It does not schedule the different blocks to different processors and it does not handle the remainder blocks, for example. For more extensive details of the operation of these missing functions, the assembly language program of appendix A and/or the following description of its associated flowchart may be consulted.
The flowchart generally outlining the assembly language program of appendix A is to be found in FIGS. 13-27. Some parts of the flowchart are continuous across pages, and where this is the case, a numbered pentagonal symbol indicates that the flowchart is to be continued on the next page.
The first figure of the flowchart, FIG. 13, is the overall body of the subroutine dmm (Double precision Matrix Multiply). The portion of the subroutine on this page distributes the work to several processors. As may be seen from flowchart item 200, this subroutine takes the same arguments as the above illustrative C language-style program. These parameters are passed on to separate processors, by calling the subroutine domine in item 204 for a different processor in each iteration of the loop. The loop counter iproc is included in the call and is indicative of the number of the processor to which the call is being made. When each processor is called, it also receives an argument indicating the number of processors that are being used for the matrix multiplication, nproc.
FIGS. 14-18 illustrate the subroutine domine. Each call to domine is executed on a different processor. Therefore, the domine subroutine must be reentrant. The Alliant FX/2800 does not distinguish reentrant and recursive subroutines, and thus the subroutine domine is declared as being recursive. Referring to FIG. 14, the subroutine first initializes variables which includes calling a subroutine initinfo, a subroutine that initializes a general-purpose data storage block, info. This data block contains a variety of variables to be used throughout the program.
The subroutine domine continues in FIG. 15, where it determines which blocks the current processor is to work on. This information is derived from the processor's own processor number iproc, the number of processors nproc, and the block size iblock, (20 in this program). If the number of processors does not divide into the number of blocks evenly, then the first processors will work on the extra remaining blocks. Each processor determines whether it is to work on remainder blocks using the variables left and num. From the above information, the subroutine derives the variables myvov which is the starting block for that processor, and myvnv which is the number of blocks that processor is to process. If the myvnv is zero, which would happen in the case where there were fewer blocks than processors, the subroutine returns as shown in items 2-0 and 212.
The next operation that the subroutine domine performs is to compute the index offsets into the matrices of the blocks that the processor it is to operate on. This is shown in FIG. 16, in items 220 and 222.
Referring now to FIG. 17, the processor now enters a loop. In this loop, the pointers to the blocks in the arrays to be operated on are found in item 230. The subroutine then calls a further subroutine mu8blk to perform the actual computations on each of the blocks. After each call to mu8blk, new index offsets are computed for the next matrix and the process is repeated. The loop is repeated once for each block. This is not sufficient to finish all of the operations to be performed on all of the blocks, as there will still be one iteration including computations and writing, and one final iteration for writing the last results. The subroutine must thus call mu8blk twice more, as shown in FIG. 18, items 240, 242. This time, new indices do not need to be calculated for storing the results. The subroutine domine then returns to its calling subroutine dmm.
FIG. 19 shows the initinfo routine which initializes the info block. This info block contains several variables. The meanings of these variables are apparent from the beginning of the mu8blk subroutine where they are accessed successively. This is shown in FIG. 20. In this figure, a0, a1 are the pointers to the matrix blocks in the matrix arrays. ainc1 and ainc21 are offset values which allow the program to step through the matrices. Similar values exist for the B and C matrices also. cr, cp, br and bp are pointers to cache blocks. These correspond to the cache blocks of cr, cc, br, bc of the illustrative C-language style program.
Referring now to FIG. 21, the subroutine sets up the pointers into the matrix for retrieving and storing elements in the next call to mu8blk.
Upon starting operations on the blocks, the first elements are simply fetched, as there are no multiplications to interleave these fetches with. This is shown in FIG. 22. the pointer Cl is checked for a value of zero in item 280. A zero value, which cannot be a valid pointer, indicates that there are not yet any values to calculate and that the initial fetch cycle should start. If, however, there is a computation, as signaled by C1 not equal to zero, the fetch of the first a element is performed in item 282, and the fetching of the first b row is performed in an unrolled loop, 284. Now that the first fetch has been performed, fetches of one element of each of A, B and C are initiated in preparation for computation.
FIG. 23 shows a decision tree which determines which type of block operation to perform on the block. This determination is made based on zero values of the pointers C0, C1, C2. A zero C2 value indicates that no writes are to be performed, a zero C1 value indicates that no computations are to be performed, and a zero C0 value indicated that no fetch is to be performed. Depending on the permutations of the above pointer values, the corresponding operations are performed by one of three macros, readblock, writeblock, or block. Some values are illegal (e.g., block 290--"do nothing"), and lead to an error condition.
The first of the above three macros, readblock, (FIG. 24) fetches data from the area in the matrix pointed to by pointer C0, and puts it into the cache. This macro reads the first block in, before computations are performed.
The second of the above macros, writeblock, (FIG. 25) writes data from the cache block pointed to by cr into the area in the matrix pointed to by C2. This macro is responsible for writing out the last block, when there are no more computations to perform.
The third of the above macros, block, (FIG. 26) performs the actual multiplications and the reads and/or writes as applicable, depending on the parameter it was called with, in FIG. 25. Since this is really a macro and not a subroutine, the parameter will not be passed on to it, but rather it will determine which version of that macro is executed. All of these versions are condensed in FIG. 26, where the only difference between versions is indicated by the condition statements 320.
The inner item 322 of the macro performs the multiplications and the parallel fetching and/or writing that takes place while the multiplications are executing. Each pass computes one scalar-vector product, and fetches
the operands for the next one. These operations actually share instructions, as the Alliant FX/2800 is capable of embedding certain categories of instruction within other types of instructions.
This scalar-vector operation is performed within a loop, the icount loop. The overall effect of the complete execution of this loop is the formation of an outer product.
This outer product loop is also embedded in a loop, the kcount loop. The overall effect of this loop is to perform all of the outer products necessary for a pair of term matrix blocks. This done, the pointers are updated to operate on the next pair of term matrix blocks, as shown in item 324.
Now that the c matrix block has been read into the cache, there is no need to read it again, so the rest of the term matrix block pairs are computed in the loop of FIG. 27, which is similar to that of FIG. 26, except that it does not fetch or store the c elements into or from cache memory. The block macro now returns to the calling subroutine mu8blk, which also returns to its calling subroutine which returns to the main domine routine for that processor.
The assembly language program presented in appendix A generally follows the above-described flowchart, and it may be consulted for additional implementational details.
It is noted that, while the subroutine domine performs a deterministic, static allocation of blocks to processors, other allocations are possible, for example, dynamic self-scheduling, in which a processor completing a block selects the next block to be completed.
It is also noted that the flowchart and code for mu8blk allow for either or both of the term matrices A and B to be transposed. This is accomplished by performing a different initialization for the info parameter block. The increments found at elements 3, 4, 7, 8, 14 and 15 of the info block are adjusted accordingly.
It is further noted that this method can be used in conjunction with Strassen's technique or another asymptotic complexity reduction method, for multiplying large matrices. In this case, the technique would be applied to the matrix recursively until it was no longer efficient to do so. The resulting sub-matrices could then be tackled using the above-described procedure.
Other embodiments are within the scope of the following claims. ##SPC1##
Claims
I claim:
1. A method of reducing the effects of memory latency in the multiplication of two matrices by a hierarchical memory computer system, said method comprising the steps of: generating by a processor, in a first series of generating operations, scalar-vector products of scalars from a vector of one of said matrices, and a vector of the other of said matrices, for successive ones of said scalars, accumulating said products as they are generated, generating, in a next series of said generating operations, further scalar-vector products of scalars from a next vector of said one of said matrices, and a next vector of said other of said matrices, for successive ones of said scalars from said next vector of said one of said matrices, accumulating said further products as they are generated, fetching from slower memory into faster memory of a memory hierarchy of said computer system, during a time period overlapping the currently executing one of said generating operations, the next said scalar to be operated upon, so that said fetched next scalar is available for the next of said generating operations sooner than if it were to be retrieved directly from said slower memory at the onset of said next operation, and fetching from said slower memory into said faster memory, during a time period overlapping the currently executing one of said first series of generating operations, a scalar in said next vector of said other of said matrices, so that said fetched next vector is available for said next series of generating operations sooner than if it were to be retrieved directly from said slower at the onset of said next series of generating operations.
2. The method of claim 1, further including the steps of: generating, in a plurality of further series of said generating operations, yet further scalar-vector products of scalars from further vectors of said one of said matrices, and further vectors of said other of said matrices, for successive ones of said further scalars in each of said further vectors of said one of said matrices, until said further vectors of said matrices are exhausted, accumulating said yet further products as they are generated, and in a time period overlapping with said further series of generating operations, continuing to fetch scalars from said matrices, until said scalars from said vectors are exhausted.
3. The method of claim 1 or 2 further including the steps of: maintaining a pair of scalar storage locations in said faster memory for scalars from said one of said matrices, maintaining a scalar fetching pointer and a scalar operating pointer, during the current said step of fetching a scalar from said one of said matrices, storing said fetched scalar in the location pointed to by said scalar fetching pointer, during the current said generating operation, operating on the scalar pointed to by said scalar operating pointer, and swapping said scalar pointers to prepare said stored fetched scalar for the next generating operation to be performed, and to allow the next fetched scalar to over write the scalar that has just been operated upon.
4. The method of claim 1 or 2, further including the steps of: maintaining a pair of vector storage locations in said faster memory for vectors from said outer of said matrices, maintaining a vector fetching pointer and a vector operating pointer, during the current said step of fetching scalars from a vector of said other of said matrices, storing said fetched scalars of said other of said matrices in the location pointed to by said vector fetching pointer, during the current said series of generating operations, operating on the vector pointed to by said vector operating pointer, and swapping said vector pointers to prepare said stored fetched vector for the next series of generating operations to be performed, and to allow the next fetched vector to over-write the vector that has just been operated upon.
5. The method of claim 1 or 2, wherein said method is a blocked method, said matrices being divided into blocks, said vectors being operated upon being vectors of said blocks, and said generating, accumulating, and fetching operations being performed for said vectors of said blocks.
6. The method of claim 5, wherein said steps of accumulating said further products generate a result block, and further including the step of storing from said faster memory into said slower memory, during a time period overlapping the currently executing one of said generating operations, a scalar from a previous result block.
7. The method of claim 6, wherein said method is applied to a matrix update operation, further including the step of fetching from said slower memory into said faster memory, during a time period overlapping the currently executing one of said generating operations, a scalar from a next result block to use as a starting value for accumulating steps in said next result block, so that said fetched next block is available for operations on the next block sooner than if it were to be retrieved directly from said slower memory at the onset of said operations on said next block.
8. The method of claim 6, further including the steps of: maintaining a pair of block storage locations in said faster memory for said result blocks, maintaining a block storing pointer and a block operating pointer, during the current said step of storing scalars from said faster memory into said slower memory, storing said scalars from the location pointed to by said block storing pointer, during the current said series of accumulating operations, accumulating into the block pointed to by said operating pointer, and swapping said block pointers to prepare for the next lock storing steps to be performed, and to allow the next accumulating steps to over-write the block that has just been stored.
9. The method of claim 5, wherein said method is applied to a matrix update operation, further including the step of fetching from said slower memory into said faster memory, during a time period overlapping the currently executing one of said generating operations, a scalar from a next result block to use as a starting value for accumulating steps in said next result block, so that said fetched next block is available for operations on the next block sooner than if it were to be retrieved directly from said slower memory at the onset of said operations on said next block.
10. The method of claim 9, further including the steps of: maintaining a pair of block storage locations in said faster memory for said result blocks, maintaining a block storing pointer and a block operating pointer, during the current said step of storing scalars from said faster memory into said slower memory, storing said scalars from the location pointed to by said block storing pointer, during the current said series of accumulating operations, accumulating into the block pointed to by said operating pointer, and swapping said block pointers to prepare for the next block storing steps to be performed, and to allow the next accumulating steps to over-write the block that has just been stored.
11. The method of claim 5, further including the steps of: maintaining a pair of block storage locations in said faster memory for said result blocks, maintaining a block storing pointer and a block operating pointer, during the current said step of storing scalars from said faster memory into said slower memory, storing said scalars from the location pointed to by said block storing pointer, during the current said series of accumulating operations, accumulating into the block pointed to by said operating pointer, and swapping said block pointers to prepare for the next block storing steps to be performed, and to allow the next accumulating steps to over-write the block that has just been stored.
12. The method of claim 1 or 2, wherein said one of said matrices is a first term matrix, and said other of said matrices is a second term matrix, and said vectors of said first matrix are column vectors, and said vectors of said second matrix are row vectors.
13. The method of claim 1 or 2, wherein said steps of generating and fetching are distributed among a plurality of processors each of which operates on the elements of different blocks of the matrices.
14. The method of claim 13, wherein the distribution of blocks among said processors is based on a size dependent sequencing method to reduce differences in completion times between processors.
15. The method of claim 1 or 2, further including the step of first applying an asymptotic complexity reduction method to said matrices to reduce the order of the number of overall operations to be performed on said matrices.
16. The method of claim 1 or 2, further including the step of operating with one of said matrices transposed.
17. The method of claim 1, wherein said method is applied to a matrix update operation, and wherein said method is a blocked method, said matrices being divided into blocks, said vectors being operated upon being block vectors of said blocks, and said generating, accumulating, and fetching operations being performed for said block vectors, and wherein said one of said matrices in a first term matrix, and said other of said matrices is a second term matrix, and said block vectors of said first matrix are column vectors, and said block vectors of said second matrix are row vectors, and further including the steps of: generating, in a plurality of further series of said generating operations, yet further scalar-vector products of scalars from further block vectors of said first of said matrices, and further block vectors of said second of said matrices, for successive ones of said further scalars in each of said further block vectors of said first of said matrices, until said further scalars are exhausted, accumulating said yet further products as they are generated, to update a result block in said faster memory, in a time period overlapping with said further series of generating operations, continuing to fetch scalars from said matrices, until said block vectors from said matrices are exhausted, and fetching from said slower memory into said faster memory, during a time period overlapping the currently executing one of said generating operations, a scalar from a next block to use as a starting value for said updating, so that said fetched next block is available for operations on the next block sooner than if it were to be retrieved directly from said slower memory at the onset of said operations on said next block, maintaining a pair of scalar storage locations in said faster memory for scalars from said first of said matrices, a pair of vector storage locations in said faster memory for vectors from said second of said matrices, and a pair of block storage locations in said faster memory for result blocks, maintaining a scalar fetching pointer, a scalar operating pointer, a vector fetching pointer, a vector operating pointer, a block storing pointer, and a block operating pointer, during the current said step of fetching a scalar from said first of said matrices, storing said fetched scalar in the location pointed to by said scalar fetching pointer, during the current said generating operation, operating on the scalar pointed to by said scalar operating pointer, swapping said scalar pointers to prepare said stored fetched scalar for the next generating operation to be performed, and to allow the next fetched scalar to over-write the scalar that has just been operated upon, during the current said step of fetching scalars from a vector of said second of said matrices, storing said fetched scalars of said second of said matrices in the location pointed to by said vector fetching pointer, during the current said series of generating operations, operating on the vector pointed to by said vector operating pointer, swapping said vector pointers to prepare said stored fetched vector for the next series of generating operations to be performed, and to allow the next fetched vector to over-write the vector that has just been operated upon, storing from said faster memory into said slower memory, during a time period overlapping the currently executing one of said generating operations, a scalar from a previous result block, during the current said step of storing scalars from said faster memory into said slower memory, storing said scalars from the location pointed to by said block storing pointer, during the current said series of accumulating operations, updating the block pointed to by said operating pointer, and swapping said block pointers to prepare for the next block storing steps to be performed, and to allow the next accumulating steps to over-write the block that has just been stored.
18. The method of claim 17, wherein said steps of generating and fetching are distributed among a plurality of processors each of which operates on the elements of different blocks of the matrices.
19. The method of claim 19, wherein the distribution of blocks among said processors is based on a size dependent sequencing method to reduce differences in completion times between processors.
20. The method of claim 17, further including the step of first applying an asymptotic complexity reduction method to said matrices to reduce the order of the number of overall operations to be performed on said matrices.
21. The method of claim 17, further including the step of operating with one of said matrices transposed.
Patent Citations (6)
Non-Patent Literature (15)
- Dangarra, Gustavson and Karp; Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine; SIAM Review vol. 26, No. 1 pp. 91-112, Jan. 1984.
- Bailey; Extra High Speed Matrix Multiplication on the Cray-2; pp.: 603-607, SIAM J. Sci. Stat,. Comput. vol. 9, No. 3 May 1988.
- Jalby, Meier; Optimizing Matrix Operations on a Parallel Muliprocessor with a Hierarchical Memory System: pp.: 429-432, Proceedings 1986 Intl. Conf. on Parallel Processing Aug. 1986.
- Gallivan, Jalby, Meier and Sameh; Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design; pp.: 12-48, The Intl. J. of Supercomputer Applications vol. 2, No. 1, 1988.
- Gallivan, Jalby, Meier; The Use of BLAS3 in Linear Algebra on a Parallel Processor with a Hierarchical Memory; pp.: 1079-1084 SIAM J. Sci. Stat. Comput. vol. 8, No. 6, Nov. 1987.
- Dongarra and Sorensan; Linear Algebra on High Perforance Computers; pp.: 57-88, Applied Mathematics & Computation vol. 20, Nos. 1 & 2, 1986.
- Geist, Heath and E. Ng; Parallel Algorithms for Matrix Computations; pp.: 233-250, Mathematical Sci. Sec., Oak Ridge National Lab.
- Lamagna; Fast Computer Algebra; pp.: 43-56, Computer Sep. 1982.
- Jagadish and Kailath; A Family of New Efficiency Arrays for Matrix Multiplications; pp.: 149-155, IEEE Trans. on Computers vol. 38, No. 1, Jan. 1989.
- Pan; How to Multiply Matrices Faster; pp.: 250-251, 1984, Book Reviews.
- Evans; Designing Efficient Systolic Algorithms for VLSI Parallel Processor Arrays; pp.: 261-281, Parallel Architecture & Computer Vision, 1988.
- Aggarwal, Alpern, Chandra and Snir; A Model for Hierarchical Memory; pp.: 305-314, Proceedings of the 19th Annual ACM Symposium on Theory of Computing 1987.
- Johnson; Communication Efficient Basic Linear Algebra Computations on Hypercube Architecture; pp.: 133-172, J. of Parallel & Distributed Computing vol. 4, 1987.
- Varman, Ramakrishnan; A Fault-Tolerant VLSI Matrix Multiplier; pp.: 351-357, Proceedings 1986 Intl. Conf. on Parallel Processing.
- Carnevali, Radicati, Robert, Sguazzero; Block Algorithms for Gaussian Elimination and Householder Reduction on the IBM 3090 Vector Multiprocessor; pp.: 297-302, Proceeding of the Intl. Conf. on Parallel Processing & Applications, Italy Sep. 23-25, 1987.