BACKGROUND

Description of the Related Art

[0001] Performing matrix operations in parallel processing units involves loading large amounts of data from memory which results in high memory bandwidth utilization. Loading matrix elements typically requires calculating offsets for stepping through the matrix data elements stored in memory in a linear format. However, this requires a complicated formula for each load instruction to calculate the offset used to move through the elements of the matrix in the correct order to perform the matrix operation. As used herein, the term“linear format” is defined as a format where consecutive matrix elements are stored in a sequential fashion in adjacent memory locations until the end of a physical row or column of memory is reached. Examples of linear formats for storing matrix elements include row-major order and column- major order. In a row-major order, consecutive elements of a matrix row reside next to each other in memory. In a column-major order, consecutive elements of a matrix column reside next to each other in memory. Processing matrix elements in a linear format results in an inefficient usage of memory bandwidth and matrix operation units.

BRIEF DESCRIPTION OF THE DRAWINGS

[0002] The advantages of the methods and mechanisms described herein may be better understood by referring to the following description in conjunction with the accompanying drawings, in which:

[0003] FIG. l is a block diagram of one implementation of a computing system.

[0004] FIG. 2 is a block diagram of another implementation of a computing system.

[0005] FIG. 3 is a block diagram of one implementation of a matrix operations unit.

[0006] FIG. 4 is a diagram of one implementation of a data layout for a source A matrix being operated on by a SIMD unit.

[0007] FIG. 5 is a diagram of one implementation of a data layout for a source B matrix being operated on by a SIMD unit.

[0008] FIG. 6 is a diagram of one implementation of a tiling layout for a tiling block.

[0009] FIG. 7 is a diagram of one implementation of the format of a 32x32 block within a source A matrix. [0010] FIG. 8 is a diagram of one implementation of the format of a 128x128 block within a source A matrix.

[0011] FIG. 9 is a diagram of one implementation of the format of an image constructed of 128x128 blocks.

[0012] FIG. 10 is a diagram of one implementation of a source B matrix.

[0013] FIG. 11 is a diagram of one implementation of the format of a 32x32 block within a source B matrix.

[0014] FIG. 12 is a diagram of one implementation of the format of a 128x128 block within a source B matrix.

[0015] FIG. 13 is a diagram of one implementation of the format of an image constructed of 128x128 blocks.

[0016] FIG. 14 is a diagram of one implementation of a result C matrix.

[0017] FIG. 15 illustrates an example of pseudocode for converting a source A matrix from linear format to tiling format in accordance with one implementation.

[0018] FIG. 16 illustrates an example of pseudocode for converting a source B matrix from linear format to tiling format in accordance with one implementation.

[0019] FIG. 17 is a generalized flow diagram illustrating one implementation of a method for converting matrix data from a linear format to a tiling format for performing a matrix operation.

PET ATT, ED DESCRIPTION OF IMPLEMENTATIONS

[0020] In the following description, numerous specific details are set forth to provide a thorough understanding of the methods and mechanisms presented herein. However, one having ordinary skill in the art should recognize that the various implementations may be practiced without these specific details. In some instances, well-known structures, components, signals, computer program instructions, and techniques have not been shown in detail to avoid obscuring the approaches described herein. It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements.

[0021] Various systems, apparatuses, and methods for converting matrix data from a linear format to a tiling format for performing matrix operations are disclosed herein. A system includes at least a memory, a cache, a processor, and a plurality of compute units. The memory stores a plurality of matrix elements in a linear format, and the processor converts the plurality of matrix elements from the linear format to a tiling format. In one implementation, the term“tile format” or“tiling format” is defined as a format for storing matrix elements in memory locations such that matrix elements for performing a given matrix operation are stored in adjacent memory locations. In one implementation, the given matrix operation is a matrix multiplication operation.

In another implementation, the term“tiling format” is defined as a format where matrix elements that constitute a column of a tile are stored in adjacent memory locations. The term“tile” is defined as an NxM block of elements, where N and M are positive integers, and where at least one of N or M is greater than one. A“tile” can also be referred to herein as a“block”. In one implementation, the number“M” of columns of a tile of a first source matrix is equal to a number of lanes of a matrix operations unit. In one implementation, for a matrix multiplication operation, a first source matrix is partitioned into tiles of NxM elements, while a second source matrix is partitioned into tiles of MxN elements.

[0022] The tiling format results in the matrix data being ordered with a specific layout which allows data to be loaded successively without performing an offset calculation. Each compute unit retrieves a row and/or column of matrix elements of one or more tiles from the memory into the cache. Each compute unit includes a matrix operations unit which retrieves the plurality of matrix elements of the corresponding tile(s) from the cache and performs a matrix operation on the plurality of matrix elements to generate a result in the tiling format. In one implementation, the system performs a plurality of matrix operations on the plurality of compute units as part of a machine learning engine to generate a classification of a first dataset. For example, in one implementation, the system performs the plurality of matrix operations while implementing a neural network to classify an image into one or more categories. The neural network can be a convolutional neural network, recurrent neural network, or other type. Various tasks such as hand-written digit classification and face detection can be performed by the neural network. Additionally, neural networks can perform other, more challenging, visual classification tasks. Other applications for neural networks include speech recognition, language modeling, sentiment analysis, text prediction, and others. In other implementations, the system performs a plurality of matrix operations on the plurality of compute units as part of other types of software applications.

[0023] In various implementations, the cache has P channels, where P is a positive integer greater than one. In one implementation, P is equal to 32 In other implementations, P is equal to other numbers. Requests are mapped to different channels of the cache based on a portion of the physical address bits. For example, in one implementation, each channel is mapped with bits 12-8 of the physical address. In other implementations, the channel mapping is based on other bits of the physical address. In one implementation, storing the matrix elements in the tiling format increases the cache hit efficiency. In a typical application, each compute unit processes different matrix tiles but the tiles may map to the same cache channel. This can impact the cache efficiency because different compute units will end up requesting data via the same cache channel. Accordingly, the compute units will be waiting for the data to be returned from the cache, and the cache will be processing the requests one by one in the same channel. However, when the matrix elements are stored in the tiling format, different compute units are mapped to different channels. When the compute units are executing the same kernel in parallel, the requests are sent to the cache on different channels, which helps to increase the cache access efficiency.

[0024] Referring now to FIG. 1, a block diagram of one implementation of a computing system 100 is shown. In one implementation, computing system 100 includes at least processors 105A-N, input/output (I/O) interfaces 120, bus 125, memory controller(s) 130, network interface 135, memory device(s) 140, display controller 150, and display 155. In other implementations, computing system 100 includes other components and/or computing system 100 is arranged differently. Processors 105A-N are representative of any number of processors which are included in system 100.

[0025] In one implementation, processor 105 A is a general purpose processor, such as a central processing unit (CPU). In one implementation, processor 105N is a data parallel processor with a highly parallel architecture. Data parallel processors include graphics processing units (GPUs), digital signal processors (DSPs), field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and so forth. In some implementations, processors 105A-N include multiple data parallel processors. In one implementation, processor 105N is a GPU which provides pixels to display controller 150 to be driven to display 155.

[0026] Memory controller(s) 130 are representative of any number and type of memory controllers accessible by processors 105A-N. Memory controlled s) 130 are coupled to any number and type of memory devices(s) 140. Memory device(s) 140 are representative of any number and type of memory devices. For example, the type of memory in memory device(s) 140 includes Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), NAND Flash memory, NOR flash memory, Ferroelectric Random Access Memory (FeRAM), or others.

[0027] I/O interfaces 120 are representative of any number and type of I/O interfaces (e.g., peripheral component interconnect (PCI) bus, PCI-Extended (PCI-X), PCIE (PCI Express) bus, gigabit Ethernet (GBE) bus, universal serial bus (USB)). Various types of peripheral devices (not shown) are coupled to I/O interfaces 120. Such peripheral devices include (but are not limited to) displays, keyboards, mice, printers, scanners, joysticks or other types of game controllers, media recording devices, external storage devices, network interface cards, and so forth. Network interface 135 is used to receive and send network messages across a network.

[0028] In various implementations, computing system 100 is a computer, laptop, mobile device, game console, server, streaming device, wearable device, or any of various other types of computing systems or devices. It is noted that the number of components of computing system

100 varies from implementation to implementation. For example, in other implementations, there are more or fewer of each component than the number shown in FIG. 1. It is also noted that in other implementations, computing system 100 includes other components not shown in FIG. 1.

Additionally, in other implementations, computing system 100 is structured in other ways than shown in FIG. 1.

[0029] Turning now to FIG. 2, a block diagram of another implementation of a computing system 200 is shown. In one implementation, system 200 includes GPU 205, system memory 225, and local memory 230. System 200 also includes other components which are not shown to avoid obscuring the figure. GPU 205 includes at least command processor 235, control logic 240, dispatch unit 250, compute units 255A-N, memory controller 220, global data share 270, level one (LI) cache 265, and level two (L2) cache 260. In other implementations, GPU 205 includes other components, omits one or more of the illustrated components, has multiple instances of a component even if only one instance is shown in FIG. 2, and/or is organized in other suitable manners. In one implementation, the circuitry of GPU 205 is included in processor 105N (of FIG. 1).

[0030] In various implementations, computing system 200 executes any of various types of software applications. As part of executing a given software application, a host CPU (not shown) of computing system 200 launches kernels to be performed on GPU 205. Command processor 235 receives kernels from the host CPU and uses dispatch unit 250 to issue corresponding wavefronts to compute units 255A-N. In one implementation, each compute unit 255A-N includes a matrix operations unit. For example, the matrix operations unit performs matrix multiplication operations. Additionally, in various implementations, the matrix operations unit performs other types of matrix operations. Wavefronts executing on compute units 255A-N read and write data to global data share 270, LI cache 265, and L2 cache 260 within GPU 205. Although not shown in FIG. 2, in one implementation, compute units 255A-N also include one or more caches and/or local memories within each compute unit 255A-N.

[0031] In one implementation, matrix data is stored in a linear format in system memory 225 and/or local memory 230. Prior to loading the matrix data into L2 cache 260, the matrix data is converted from the linear format to a tiling format. In one implementation, the term“tiling format” is defined as storing matrix elements together into units of tiles, with each tile storing an

NxM block of matrix elements, where N and M are positive integers. The“tiling format” results in consecutive tiles being stored in a sequential fashion in memory.

[0032] In one implementation, command processor 235 converts the matrix data from the linear format to the tiling format. In another implementation, a host processor (e.g., processor 105 A of FIG. 1) converts the matrix data from the linear format to the tiling format. Then, during execution of wavefronts on compute units 255A-N, the matrix data is loaded from L2 cache 260 in an efficient manner due to the matrix data being stored in the tiling format. In one implementation, when the matrix elements are stored in the tiling format, the matrix data elements are read on multiple channels from L2 cache 260 into compute units 255A-N in parallel. This is a more efficient approach than having the matrix data elements stored in linear format, which would result in matrix data elements being read on a single channel from L2 cache 260 in serial fashion.

[0033] Referring now to FIG. 3, a block diagram of one implementation of a matrix operations unit 300 is shown. In one implementation, each compute unit 255A-N includes the circuitry of matrix operations unit 300. In one implementation, matrix operations unit 300 includes at least architecture vector general purpose register (VGPR) file 305, export unit 310, accumulation VGPR file 315, single instruction, multiple data (SIMD) unit 320, and SIMD unit 325. It should be understood that matrix operations unit 300 includes any number of other components which are not shown to avoid obscuring the figure. Additionally, in other implementations, matrix operations unit 300 is organized in other suitable manners.

[0034] In one implementation, SIMD unit 320 is a floating point unit for performing various floating point operations and SIMD unit 325 is a matrix unit for performing various matrix operations (e.g., dot product operations, matrix multiplication operations). In one implementation, each separate input shown connected to architecture VGPR file 305and accumulation VGPR file 315 has 16 lanes of 32 bits each. In other implementations, the inputs have other numbers of lanes of other bit-widths. In one implementation, SIMD unit 325 operates on input matrix elements more efficiently when the matrix elements are stored in a tiling format. Accordingly, in this implementation, the matrix elements are converted from a linear format to the tiling format prior to being read into architecture VGPR file 305 and/or accumulation VGPR file 315. This enables the operations to be performed by SIMD unit 325 in a more efficient manner.

[0035] Turning now to FIG. 4, a diagram of one implementation of the data layout 400 of a source A matrix being operated on by a SIMD unit is shown. In one implementation, SIMD unit 325 (of FIG. 3) is organized according to the data layout 400 illustrated in FIG. 4 for reading in a source A matrix to perform a matrix multiplication operation of a source A matrix multiplied by a source B matrix. For example, in this implementation, there are 64 threads in data layout 400 per SIMD unit. In other implementations, the SIMD unit includes other numbers (e.g., 32, 128) of threads in the data layout. Each thread of data layout 400 corresponds to a lane of the SIMD unit.

[0036] Depending on the size of a block being processed, different numbers of blocks can be mapped according to data layout 400. For example, if each block is of size 32x2, then two blocks (BlkO and Blkl) are mapped from the VGPR file to the SIMD unit. If each block is of size 16x2, then four blocks (BlkO, Blkl, Blk2, and Blk3) are mapped from the VGPR file to the SIMD unit. If each block is of size 4x2, then sixteen blocks (BlkO, Blkl, Blk2, Blk3, Blk4, Blk5, Blk6, Blk7, Blk8, Blk9, BlklO, Blkl l, Blkl2, Blkl3, Blkl4, and Blkl5) are mapped from the VGPR file to the SIMD unit.

[0037] Referring now to FIG. 5, a diagram of one implementation of a data layout 500 for a source B matrix for a SIMD unit is shown. In one implementation, the connections between a VGPR file and a SIMD unit (e.g., SIMD unit 325 (of FIG. 3)) are organized according to the data layout 500. For example, in one implementation, data layout 500 defines the connections for loading a source B matrix so as to perform a matrix multiplication operation between a source A matrix and a source B matrix. In one implementation, data layout 500 is organized for 64 threads. In other implementations, data layout 500 includes other numbers of threads. Each thread of data layout 500 corresponds to a lane of the SIMD unit. Depending on the size (e.g., 2x32, 2x16, 2x4) of a block being processed, different numbers (e.g., 2, 4, 16) of blocks can be mapped according to data layout 500.

[0038] Turning now to FIG. 6, a diagram of one implementation of a tiling layout for a block 600 of a source A matrix is shown. In one implementation, a matrix is partitioned into multiple blocks, with each block organized according to block 600. The organization of elements in block 600 illustrates the mapping relationship between the linear data and the tiling data. For example, the matrix element 65 is indicated by circle 605. The original position of this element is (x=3, y=0). Accordingly, the position is (y*stride + x) = 0*4+3 = 3 in the linear format and position 65 in the tiling format. In one implementation, the basic tiling block is 32x4 for the source A matrix and 4x32 for the source B matrix to implement a matrix multiplication operation. In other implementations, the basic tiling block for a matrix operation can be other sizes. In one implementation, for the next level in the matrix hierarchy, 8 basic blocks of size 32x4 are combined into a 32x32 middle block. Additionally, moving up the matrix hierarchy, 16 middle blocks are combined into a 128x128 large block. It is assumed for the purposes of the remaining discussion that the matrix size being processed is aligned with the 128x128 large block.

However, it should be understood that in other implementations, the matrix size can be aligned with other sizes of blocks.

[0039] Referring now to FIG. 7, a diagram of one implementation of a 32x32 block 700 within a source A matrix is shown. Each 4x32 block is arranged from block 0 to block 7 from left to right as shown to form a 32x32 block 700. In other implementations, other sizes of blocks can be combined together to form a block higher up in the matrix block hierarchy.

[0040] Turning now to FIG. 8, a diagram of one implementation of a 128x128 block 800 within a source A matrix is shown. The first column of 128x128 block 800 is constructed from 32x32 blocks 0-3 as shown in block 800. The second column of 128x128 block 800 is constructed from 32x32 blocks 4-7, the third column of 128x128 block 800 is constructed from 32x32 blocks 8-11, and the fourth column (i.e., the right-most column) of 128x128 block 800 is constructed from 32x32 blocks 12-15. In one implementation, each 32x32 block is constructed according to block 700 (of FIG. 7).

[0041] Referring now to FIG. 9, a diagram of one implementation of an image 900 constructed of 128x128 blocks is shown. It should be understood that in other implementations, an image can be constructed of other sizes of blocks which can be organized in other suitable manners. For example, in other implementations, an image can be constructed of 64x64 blocks, 256x256 blocks, or other sizes of blocks. For these implementations, the mechanisms and methods described herein for image 900 can be adapted to apply to other images made up of other sizes of blocks.

[0042] Turning now to FIG. 10, a diagram of one implementation of a tiling layout of a block 1000 of a source B matrix is shown. In one implementation, a matrix operations unit multiplies a source A matrix by a source B matrix. The organization of block 1000 of a source B matrix is one example of the organization of the elements of source B matrix block 1000 in accordance with one implementation for implementing a matrix multiplication operation.

[0043] Referring now to FIG. 11, a diagram of one implementation of a 32x32 block 1100 of a source B matrix is shown. In one implementation, 32x32 block 1100 of a source B matrix is constructed using eight different 32x4 blocks. As shown in FIG. 11, each 32x4 block is arranged from block 0 to block 7 from top to bottom as shown in block 1100. In other implementations, 32x32 block 1100 can be constructed with other numbers, sizes, and/or arrangements of smaller blocks. [0044] Turning now to FIG. 12, a diagram of one implementation of a 128x128 block 1200 of a source B matrix is shown. The first row of 128x128 block 1200 is constructed from 32x32 blocks 0-3 moving from left to right. The second row of 128x128 block 1200 is constructed from

32x32 blocks 4-7 moving from left to right, the third row of 128x128 block 1200 is constructed from 32x32 blocks 8-11 moving from left to right, and the fourth row (i.e., the bottom row) of

128x128 block 1200 is constructed from 32x32 blocks 12-15 moving from left to right. In one implementation, each 32x32 block is constructed according to the layout of block 1100 (of FIG.

11).

[0045] Referring now to FIG. 13, a diagram of one implementation of an image 1300 constructed of 128x128 blocks is shown. The first row of image 1300 includes 128x128 blocks 0-7 moving from left to right. Similarly, the second row of image 1300 includes 128x128 blocks 8-15 moving from left to right. The other rows of image 1300 are organized in the same manner, with the bottom row including 128x128 blocks 56-63 moving from left to right. In one implementation, each 128x128 block 0-63 is constructed according to block 1200 (of FIG. 12).

[0046] Turning now to FIG. 14, a diagram of one implementation of a block 1400 of a result C matrix is shown. In one implementation, a matrix operations unit multiplies a source A matrix by a source B matrix to generate a result C matrix. The organization of the elements of block 1400 is one example of the organization of the elements of a block within a result C matrix after a matrix multiplication operation has been performed in accordance with one implementation. The first column of block 1400 includes element 0 followed by element 1, element 2, and then element 3. The second column of block 1400 includes element 4 on top of element 5 on top of element 6 on top of element 7. This pattern of element layout continues in the columns moving to the right of matrix C 1400 until the last, right-most column includes element 60, element 61, element 62, and element 63.

[0047] Referring now to FIG. 15, an example of pseudocode 1500 for converting a source A matrix from linear format to tiling format in accordance with one implementation is shown. Pseudocode 1500 includes definitions of variables with specific values that are used for one particular implementation. In other implementations, the values of these variables can vary depending on the sizes of tiles, number of lanes and bit-widths of matrix multiplication units, number of cache channels, and so on.

[0048] It is assumed for the purposes of the discussion of pseudocode 1500 and pseudocode 1600 (of FIG. 16) that there are two input matrices: a source A matrix and a source B matrix. It is also assumed that the size of the source A matrix is MxK, the size of the source B matrix is KxN, and the size of the result C matrix is MxN, where M, N, and K are positive integers. In one implementation, M, N, and K are equal to 1024. In other implementations, the values of M, N, and K can vary.

[0049] In one implementation, there are two sets of buffers in memory. A_outbuffer[] and B_outbuffer[] store the matrix elements of the source A matrix and the source B matrix, respectively, in memory in the linear format. A_package_outbuffer[] and B_package_outbuffer[] store the matrix elements of the source A matrix and the source B matrix, respectively, in memory in the tiling format. Based on the instructions in pseudocode 1500, elements of the source A matrix that are stored in consecutive memory locations in the linear format are stored in memory locations which are separated by a tile height in the tiling format. In other words, values are read from sequential locations of a first buffer (i.e., A_outbuffer[]) and written to locations in a second buffer (i.e., A_package_outbuffer[]) while stepping through the second buffer with a stride equal to a tile height. After the source A matrix and the source B matrix are converted from the linear format to the tiling format, the kernel code executing on the compute units will load the data from memory into the cache (e.g., L2 cache).

[0050] Turning now to FIG. 16, one example of pseudocode 1600 for converting a source B matrix from a linear format to a tiling format is shown. The discussion of pseudocode 1600 is intended to be a continuation of the discussion of pseudocode 1500 (of FIG. 15). In one implementation, pseudocode 1600 is used to convert the source B matrix from a linear format to a tiling format. Once the source B matrix is converted from the linear format to the tiling format, the kernel code will load the data from memory into the cache.

[0051] Referring now to FIG. 17, one implementation of a method 1700 for converting matrix data from a linear format to a tiling format for performing a matrix operation is shown. For purposes of discussion, the steps in this implementation are shown in sequential order. However, it is noted that in various implementations of the described methods, one or more of the elements described are performed concurrently, in a different order than shown, or are omitted entirely. Other additional elements are also performed as desired. Any of the various systems or apparatuses described herein are configured to implement method 1700.

[0052] A host processor (e.g., CPU) detects a request to perform a matrix operation on matrix data stored in a linear format (block 1705). In one implementation, the matrix operation is a matrix multiplication operation. In other implementations, other types of matrix operations are requested. Next, in response to detecting the request, the host processor converts the matrix data from the linear format to a tiling format (block 1710). Examples of pseudocode 1500 and 1600 for converting a source A matrix and a source B matrix from a linear format to a tiling format are shown in FIG. 15 and FIG. 16, respectively. In other implementations, other techniques for converting a source A matrix and a source B matrix from a linear format to a tiling format can be utilized.

[0053] Next, a plurality of matrix operations units load the matrix data in the tiling format from memory into all N channels of a cache (block 1715). In one implementation, the cache is a L2 cache. In one implementation, the cache has N channels, where N is a positive integer greater than one. Then, the plurality of matrix operations units perform, in parallel, matrix operations on the matrix data to generate a result (block 1720). Next, the processor uses the result to complete a first action associated with a given software application (block 1725). In one implementation, the first action is the classification of a first dataset and the given software application is a machine learning application. In one implementation, the first dataset is an image, and the classification identifies a given category to which the image belongs. In another implementation, the first dataset is a video, and the classification assigns the video to a given category. In other implementations, the first dataset includes other types of data which are classified in other ways. In other implementations, other types of actions associated with other types of software applications are performed. After block 1725, method 1700 ends.

[0054] In various implementations, program instructions of a software application are used to implement the methods and/or mechanisms described herein. For example, program instructions executable by a general or special purpose processor are contemplated. In various implementations, such program instructions are represented by a high level programming language. In other implementations, the program instructions are compiled from a high level programming language to a binary, intermediate, or other form. Alternatively, program instructions are written that describe the behavior or design of hardware. Such program instructions are represented by a high-level programming language, such as C Alternatively, a hardware design language (HDL) such as Verilog is used. In various implementations, the program instructions are stored on any of a variety of non-transitory computer readable storage mediums. The storage medium is accessible by a computing system during use to provide the program instructions to the computing system for program execution. Generally speaking, such a computing system includes at least one or more memories and one or more processors configured to execute program instructions.

[0055] It should be emphasized that the above-described implementations are only non limiting examples of implementations. Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.