CROSS REFERENCE TO RELATED APPLICATIONS [0001] This application claims the benefit of pending U.S. Non-Provisional Patent Application Number 17/214,784, entitled “APPROXIMATION OF MATRICES FOR MATRIX MULTIPLY OPERATIONS,” filed on March 26, 2021, the entirety of which is hereby incorporated herein by reference. This application is related to non-provisional application No. 17/214,779 entitled “DATA COMPRESSOR FOR APPROXIMATION OF MATRICES FOR MATRIX MULTIPLY OPERATIONS,” filed on March 26, 2021 which is incorporated herein by reference as if fully set forth.

BACKGROUND

[0002] Matrix multiplication is a key building block across a number of application domains, including use in high performance computing (HPC) and machine learning. Matrix multiplication is also used in convolutional neural networks, recurrent neural networks and other forms of artificial neural networks. [0003] Matrix multiplication techniques employ parallelization to increase the efficiency of matrix multiplication. For example, two matrices are typically divided into smaller portions (e.g., columns, rows, and portions of columns and rows) and a matrix multiplication operation of the two matrices is performed by executing a plurality of matrix multiplication computations each including the multiplication of a portion of one matrix with a portion of another matrix. The matrix multiplication computations are mapped to and executed by different processor cores of a processor network to perform the matrix multiplication operation.

BRIEF DESCRIPTION OF THE DRAWINGS [0004] A more detailed understanding can be had from the following description, given by way of example in conjunction with the accompanying drawings wherein: [0005] FIG. 1 is a block diagram of an example device in which one or more features of the disclosure can be implemented;

[0006] FIG. 2 is a block diagram illustrating exemplary components of a processor in which one or more features of the disclosure can be implemented; [0007] FIG. 3 is a flow diagram illustrating an example method of selecting data for matrix multiplication according to features of the disclosure;

[0008] FIG. 4A shows a first example of an array of approximated product exponent values according to features of the disclosure;

[0009] FIG. 4B shows a second example of an array of approximated product exponent values according to features of the disclosure;

[0010] FIG. 4C shows a third example of an array of approximated product exponent values according to features of the disclosure;

[0011] FIG. 4D shows a fourth example of an array of approximated product exponent values according to features of the disclosure; and [0012] FIG. 5 is a diagram illustrating an example of partial matrix multiplication of two matrices, A and B, and an output matrix C according to features of the disclosure.

DETAILED DESCRIPTION

[0013] As used herein, programs include sequences of instructions to be executed using one or more processors to perform procedures or routines (e.g., operations, computations, functions, processes, jobs). Processing of programmed instructions and data includes one or more of a plurality of processing stages, such as but not limited to fetching, decoding, scheduling for execution, executing and decoding the programmed instructions and data. Programmed instructions include, for example, applications and control programs, such as operating systems. Processors include, for example, multiple processing cores (e.g., compute units (CUs)) each of which are configured to read and execute program instructions, such as instructions to perform matrix multiplications.

[0014] Matrix multiplication includes calculating dot products of sub portions of data of a first matrix and a second matrix. A matrix multiplication operation includes the calculation C = A x B, where A, B, C are matrices of sizes M x K, K x N, and M x N, respectively. Each element in matrix C is a dot product of a row of matrix A and a column of matrix B. For example, a multiply accumulate operation calculates the product of a pair of values, each value corresponding to an element of a portion (e.g., row, column, part of a row or column, or multiple rows or columns) of a matrix, and adds the product to an accumulator using hardware components known as a multiplier accumulator (MAC). For example, a 64 x 64 product can be implemented as four 16 x 16 MACs or eight 8 x 8 MACs. Matrix multiplication typically involves many calculations, which is time consuming and expensive.

[0015] The present application provides devices and methods for efficiently performing an approximation of matrix multiplication. Features of the present disclosure include devices and methods of dynamically determining an output matrix by dropping a number of products (i.e., products of pairs of elements of two input matrices), along the common dimension K of the two matrices, from the products to be used for the dot product calculations of the matrix multiplication of input matrices. The dropped products are the products approximated as having the smallest exponent sums among the products to be used for the dot product calculations. As described in more detail below, a target number of elements, to be kept (i.e., not dropped) and provided to the MACs, is determined based on sums of bit values of the approximated product values (referred to herein as product exponent values, starting with a sum of the most significant bits (MSBs) of the product exponent values and continuing through sets of each set of corresponding next significant bits, until the target number of product exponent values is determined to be kept and, in turn, indicating which corresponding elements of matrices A and B are provided to MACs for matrix multiplication.

[0016] Features of the present disclosure reduce the number of products without first sorting the elements of the input arrays according to their values, which would otherwise be expensive to implement in hardware.

[0017] For example, a 64 x 64 product is reduced to a 48 x 48 product by keeping the largest approximated 48 product values (i.e., dropping the lowest 16 approximated values) among the 64 x 64 product values. By way of example, if a 64 x 64 product is implemented as a 16 x 16 MAC, four 16 x 16 MACs are reduced to three 16 x 16 MACs, resulting in a 25% reduction time to execute the task and a reduction in energy cost to execute the task. Likewise, if the 64 x 64 product is implemented as an 8 x 8 MAC, eight 8 x 8 MACs are reduced to 68 x 8 MACs, also resulting in a 25% reduction time. A target number of product values to be kept and provided to the MACs to execute the matrix multiplication, or a target number of product values to be dropped (i.e., dropped product values) from the product values to be provided to the MACs, can be any number and is determined based on various factors during runtime, such as an amount of result error that can be tolerated by the approximations for a particular task or application. For example, when used for machine learning training, a target number of products determined to be dropped is based on the effect the approximations will have on the accuracy of a resulting network. The target number of products values to be dropped can also be determined based the size of the common dimension K. For example, based on heuristics, additional product values can be dropped for larger values of K and additional product values can kept and provided to the MACs for lower values of K.

[0018] Features of the present disclosure include performing matrix multiplication for a variety of different data types, such as float data types (e.g., FP32, FP16 and BF16 formats) and integer data types (e.g., int8 format).

[0019] A processing device is provided which comprises memory configured to store data and a processor configured to receive a portion of data of a first matrix comprising a first plurality of elements and receive a portion of data of a second matrix comprising a second plurality of elements. The processor is also configured to determine values for a third matrix by dropping a number of products from products of pairs of elements of the first and second matrices based on approximating the products of the pairs of elements as a sum of exponents of the pairs of elements and performing matrix multiplication on remaining products of the pairs of elements of the first and second matrices.

[0020] A matrix multiplication data selection method is provided which comprises receiving a portion of data of a first matrix comprising a first plurality of elements and receiving a portion of data of a second matrix comprising a second plurality of elements. The method also comprises determining values for a third matrix by dropping a number of products from products of pairs of elements of the first and second matrices based on approximating the products of the pairs of elements as a sum of exponents of the pairs of elements and performing matrix multiplication on remaining products of the pairs of elements of the first and second matrices.

[0021] A non-transitory computer readable medium is provided which comprises instructions for causing a computer to execute a matrix multiplication data selection method, comprising receiving a portion of data of a first matrix comprising a first plurality of elements, receiving a portion of data of a second matrix comprising a second plurality of elements, and determining values for a third matrix by dropping a number of products from products of pairs of elements of the first and second matrices based on approximating the products of the pairs of elements as a sum of exponents of the pairs of elements and performing matrix multiplication on remaining products of the pairs of elements of the first and second matrices.

[0022] FIG. 1 is a block diagram of an example device 100 in which one or more features of the disclosure can be implemented. The device 100 includes, for example, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device 100 includes a processor 102, a memory 104, a storage 106, one or more input devices 108, and one or more output devices 110. The device 100 also optionally includes an input driver 112 and an output driver 114. It is understood that the device 100 can include additional components not shown in FIG. 1.

[0023] In various alternatives, the processor 102 includes a central processing unit (CPU), a graphics processing unit (GPU), a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core can be a CPU or a GPU. In various alternatives, the memory 104 is located on the same die as the processor 102, or is located separately from the processor 102. The memory 104 includes a volatile or non-volatile memory, for example, random access memory (RAM), including dynamic RAM (DRAM) and static RAM (SRAM). The RAM includes for example, cache memory, scratchpad memory and registers. [0024] The storage 106 includes a fixed or removable storage, for example, a hard disk drive, a solid state drive, an optical disk, or a flash drive. The input devices 108 include, without limitation, a keyboard, a keypad, a touch screen, a touch pad, a detector, a microphone, an accelerometer, a gyroscope, a biometric scanner, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE 802 signals). The output devices 110 include, without limitation, a display, a speaker, a printer, a haptic feedback device, one or more lights, an antenna, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE 802 signals).

[0025] The input driver 112 communicates with the processor 102 and the input devices 108, and permits the processor 102 to receive input from the input devices 108. The output driver 114 communicates with the processor 102 and the output devices 110, and permits the processor 102 to send output to the output devices 110. It is noted that the input driver 112 and the output driver 114 are optional components, and that the device 100 will operate in the same manner if the input driver 112 and the output driver 114 are not present.

[0026] Features of the present disclosure are described herein using CUs as an example of processor cores. CUs include one or more single instruction, multiple data (SIMD) units that are configured to perform operations at the request of the processor 102 in a parallel manner according to a SIMD paradigm. The SIMD paradigm is one in which multiple processing elements share a single program control flow unit and program counter and thus execute the same program but are able to execute that program with different data. In one example, each SIMD unit includes sixteen lanes, where each lane executes the same instruction at the same time as the other lanes in a SIMD unit but can execute that instruction with different data. Lanes can be switched off with predication if not all lanes need to execute a given instruction. Predication can also be used to execute programs with divergent control flow. More specifically, for programs with conditional branches or other instructions where control flow is based on calculations performed by an individual lane, predication of lanes corresponding to control flow paths not currently being executed, and serial execution of different control flow paths allows for arbitrary control flow. The parallelism afforded by CUs is suitable for matrix multiplication, such as for example, matrix multiplication used in graphics related operations such as pixel value calculations, vertex transformations, and other graphics operations.

[0027] FIG. 2 is a block diagram illustrating an example of processor 102 shown in FIG. 1 in which one or more features of the disclosure can be implemented. As shown in FIG. 2, processor 102 includes a plurality of CUs 202. Each CU 202 includes a level N (e.g., level 1) cache controller 208 in communication with a corresponding level N cache 204 and is configured to process data using the corresponding level N cache 204. Alternatively, a plurality of level N cache controllers 208 (e.g., a cache controller 208 for each CU 202 or a plurality of cache controllers 208 each in communication with a group of CUs 202) is used to process data.

[0028] As shown in FIG. 2, processor 102 also includes a level N+l (e.g., level 2) cache controller 210 in communication with level N+l cache 206 and is configured to process data using a level N+l cache 206. Alternatively, a plurality of level N+l cache controllers, in communication with one or more corresponding level N+l caches, is used to process data. As shown in FIG. 2, cache controller 210 is also in communication with a next cache level (e.g., level 3) and each level N cache controller 208. Additionally, or alternatively, each CU 202 is in communication with different types of memory 104, such as registers and scratchpad memory.

[0029] As shown in FIG. 2, each CU 202 also includes MACs 212 and data compressor 214 in communication with the MACs 212. The MACs 212 are configured to calculate products of element pairs of portions of matrices (e.g., approximated products exponent values) and accumulate (e.g., store) the products to execute matrix multiplication operations. A target number of products, which are approximated as the products having the smallest exponent sums, are dropped from the products to be used by the MACs 212 to execute the dot product calculations of the matrix multiplication.

[0030] Data compressor 214 includes hardware circuitry configured to determine, from the exponent values (i.e., exponent sums), which of the exponent values are to be kept (i.e., not dropped) and provided to the MACs 212 based on their bit values, starting from their most significant bits and continuing through sets of corresponding next significant bits, until the target number of exponent values is determined. Data compressor 214 is also configured to provide the kept exponent values to the MACs 212 to execute the matrix multiplication.

[0031] FIG. 3 is a flow diagram illustrating an example method 300 of selecting data for matrix multiplication according to features of the disclosure. [0032] As shown at block 302, the method 300 includes receiving a portion of data of a first matrix A and a portion of data of a second matrix B. FIG. 5 is a diagram illustrating an example of partial matrix multiplication of two matrices, A and B, and an output matrix C according to features of the disclosure. As described above, a matrix multiplication operation includes the calculation C = A x B, where A, B, C are matrices of sizes M x K, K x N, and M x N, respectively. Each element in matrix C is a dot product of a row of matrix A and a column of matrix B. For example, a part of the matrix multiplication of matrices A and B is performed, according to features of the present disclosure, by approximating product values of the 4 elements 502(l)-502(4) of element array 502 of matrix B and 4 corresponding elements 504(l)-504(4) of array 504 of matrix B to produce the result in portion 1 (PI) of matrix C.

[0033] Although the sizes of matrix A and matrix B in FIG. 5 are different from each other, matrix multiplication operation can be performed for matrices if the number of columns in one matrix is equal to the number of rows in the other matrix. In the example shown in FIG. 5, matrix A includes eight columns and matrix B includes 8 rows. The number of columns and rows in matrices A and B are merely an example. Matrix multiplication is performed, according to features of the present disclosure, for matrices of any size meeting the general rules for matrix multiplication (e.g., number of columns in matrix A is equal to the number of rows in matrix B.

[0034] The portions of data of the first matrix and the second matrix can include any number of elements of different data types, such as for example, integer data types (e.g., int8 format) and float data types (e.g., BF16 format). The number of bits representing each element depends on the float format (e.g., FP32, FP16, BF16) and integer format being used (e.g., int8, intl6, int32). For example, for float format BF16, each element is represented 16 bits while each exponent is represented by 8 bits.

[0035] As shown at block 304, the method 300 includes approximating the values of products of element pairs of the portions of the first and second matrices as a sum of the exponents of the element pairs.

[0036] If the elements of the portions of data of the first and second matrices are float data types, then the exponent values can be just extracted from the exponent bits of each element. For example, if the element is in BF16 format, the first bit is a sign bit, bits 2 to 9 are the exponent bits and bits 10-16 are the mantissa bits. Accordingly, the exponent values can be extracted from the values of bits 2 to 9.

[0037] If the sub-portions of data of the first matrix A and the second matrix

B include 8 elements of int data type format (int8), the exponents are extracted by determining the absolute values for the elements of each sub-portion of data (A _a [8], Ba[8]), determining the number of leading zeros to be dropped for each element, representing each element as l.M * 2 ^e (where M is the mantissa of the element value and e is the exponent of the element value) and approximating the exponent value for each element as [the number of bits -1] - LA (where LA is the number of leading zeros of the element).

[0038] By way of example, if the absolute value of the first element of the first matrix (A _a [l]) is 00001011, four leading zeroes are determined to be dropped. The element is represented as 1.011 * 2 ^e and the exponent value (e) for A[l] is calculated as [the number of bits -1] - LA = 7 - 4 = 3. If the absolute value of the first element of the second matrix (B _a [l]) is 00101111, two leading zeroes are determined to be dropped. The element is represented as 1.01111 * 2 ^e and the exponent value (e) for A[l] is calculated as [the number of bits -1] - LB = 7 - 2 = 5. Accordingly, the approximate product (P) of A[l] and B[l] is determined to be 14 - (LA + LB) = 14 - 8 = 6.

[0039] The same process is performed to determine the approximate product of the remaining 7 elements (A[2-8]) of the sub-portion of the first matrix A and the corresponding remaining 7 elements (B[2-8]) of the sub-portion of the second matrix B. That is, the products of corresponding pairs of elements of the first matrix A and the second matrix B are approximated based on 2, raised to the sum of exponents of the elements of the first matrix A and the second matrix B.

[0040] As shown at block 306, the method 300 includes dropping a number of products and determining which products to keep for the matrix multiplication of the first and second portions of matrices A and B. That is, the products are essentially dropped (i.e., not kept for the matrix multiplication) by dropping pairs of elements from the first and second matrices whose corresponding products are approximated, based on a sum of their exponents, as resulting in the smallest products among the products of the element pairs. The remaining products, which are not dropped, are kept for performing matrix multiplication.

[0041] FIGS. 4A through 4D show examples of different arrays of approximated product values (referred to herein as product exponent values), which are approximated based on a sum of the exponents of corresponding element pairs, as described above at block 304. A process of determining which product exponent values to be kept and, in turn, indicating which corresponding elements of matrices A and B are provided to MACs 212 in FIG. 2, is now described for each of the arrays of product exponent values shown in FIGS. 4A through 4D. For simplification purposes, the arrays of product exponent values illustrated in FIGS. 4A through 4D are 4 bit values. Features of the present disclosure can be implemented, however, for any number of bits used to show the product values. In addition, for simplification purposes, arrays of 8 product exponent values (corresponding to 8 element pairs) are used and a target number of 6, out of each of the 8 elements, is used as the number of product exponent values to be kept for the arrays of product exponent values shown in FIGS. 4A through 4D. Features of the present disclosure can be implemented, however, for any target number of product exponent values.

[0042] For each of the arrays shown in FIGS. 4A through 4D, the determination of which product exponent values to be kept includes summing the values of the bits of corresponding significance of the product exponent values, starting with the most significant bits for the product exponent values, and comparing each of the sums to the target number (e.g., 6) of product exponent values until the target number of product exponent values is determined. For example, for the array of 8 product exponent values shown in FIG. 4A, the MSBs of the 8 product exponent values are summed. In this case, the sum of MSBs of the 8 product exponent values is 6, which is equal to the target number of 6 product exponent values to be kept. Accordingly, the 6 product exponent values, in which the MSB is 1, are determined as the product exponent values to be kept (i.e., indicating which corresponding elements of matrices A and B are to be kept and provided to MACs 212) and the 2 product exponent values, in which the MSB is 0, are determined as the product exponent values to be dropped (i.e., indicating which corresponding elements of matrices A and B are to be dropped and not provided to MACs 212).

[0043] For the array of 8 product exponent values shown in FIG. 4B, the sum of MSBs of the 8 product exponent values is 8, which is greater than the target number of 6 product exponent values to be kept. When the sum of the MSBs is greater than 6, the bits of the next lower significance of the 8 product exponent values are summed. In this case, the sum of the bits of the next lower significance (i.e., the 2 ^nd bits) of the 8 product exponent values is equal to 4. Accordingly, the product exponent values, starting with “11” are identified as the 4 largest product exponent values and are kept (i.e., indicating 4 corresponding elements of matrix A and 4 corresponding elements of matrix B which are to be kept and provided to MACs 212). Because the 4 largest product exponent values are 2 less than the target number of 6, however, the product exponent values starting with “10” are identified and the next least significant bits (i.e., 3 ^rd bits) of the product exponent values starting with “10” are summed and the result is added to the previous sum. In this case, the sum of the 3rd bits of the product exponent values starting with “ 10” is equal to 2, which when added to the previous sum of 4, is equal to the target number of 6. Accordingly, the 2 product exponent values, starting with “101” are also identified as product exponent values to be kept (i.e., indicating 2 corresponding elements of matrix A and 2 corresponding elements of matrix B which are to be kept and provided to MACs 212).

[0044] For the array of 8 product exponent values shown in FIG. 4C, the sum of the MSBs of the 8 product exponent values is 8, which is greater than the target number of 6 product exponent values to be kept. As described above, when the sum of the MSBs is greater than 6, the bits of the next lower significance of the 8 product exponent values are summed. In this case (which is the same as the case described above for product exponent values shown in FIG. 4B), the sum of the bits of the next lower significance (i.e., the 2 ^nd bits) of the 8 product exponent values is equal to 4. Accordingly, the product exponent values starting with “11” are identified as the 4 largest product exponent values and are kept, but because the 4 largest product exponent values are 2 less than the target number of 6, the product exponent values starting with “10” are identified and the next least significant bits (i.e., 3 ^rd bits) of the product exponent values starting with “ 10” are summed and added to the previous sum of 4. In this case, the sum of the 3rd bits of the product exponent values starting with “ 10” is equal to 3, which when added to the previous sum of 4 is equal to 7, which is greater than the target number of 6. Therefore, the least significant bits (i.e. the 4th bits) of the 8 product exponent values starting with “10” are summed, which is again equal to 3, and when added to the previous sum of 4, is again greater than the target number of 6. When there are no more bits to be summed and the total of the previous sums is greater than the target number, the first 2 product exponent values in the array starting with “10” are also kept.

[0045] For the array of 8 product exponent values shown in FIG. 4D, the sum of the MSBs of the 8 product exponent values is 8, which is greater than the target number of 6 product exponent values to be kept (which is the same as the cases described above for the product exponent values shown in FIGS. 4B and 4C). In this case, however, each of the remaining bits are zero. In this case, the first 6 product exponent values in the array are kept.

[0046] The process described above with regard to FIGS 4A through 4D does not include any sorting (i.e., ordering) of the product values, which would otherwise be expensive to implement in hardware.

[0047] As shown at blocks 308, the method 300 includes selecting the data (i.e., the products) which are not determined to be dropped, and instead determined to be kept, as described above at block 306. As shown at block 310, the method 300 includes determining the dot products from the products determined to be kept.

[0048] In addition, the information generated by the matrix multiplication operations can be displayed, on a display device (e.g., output device 110 in FIG. 1). [0049] It should be understood that many variations are possible based on the disclosure herein. Although features and elements are described above in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements.

[0050] The methods provided can be implemented in a general purpose computer, a processor, or a processor core. Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine. Such processors can be manufactured by configuring a manufacturing process using the results of processed hardware description language (HDL) instructions and other intermediary data including netlists (such instructions capable of being stored on a computer readable media). The results of such processing can be maskworks that are then used in a semiconductor manufacturing process to manufacture a processor which implements features of the disclosure.

[0051] The methods or flow charts provided herein can be implemented in a computer program, software, or firmware incorporated in a non-transitory computer-readable storage medium for execution by a general purpose computer or a processor. Examples of non-transitory computer-readable storage mediums include a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs).