Indirectly accessing sample data to perform multi-convolution operations in a parallel processing system

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application claims benefit of the United States Provisional Patent Application having Ser. No. 62/087,681 (Attorney Docket Number 14-SC-0391-USL) and filed on Dec. 4, 2014. The subject matter of this related application is hereby incorporated herein by reference.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003Embodiments of the present invention relate generally to computer processing and, more specifically, to indirectly accessing sample data to perform multi-convolution operations in a parallel processing system.

00042. Description of the Related Art

0005Convolutional Neural Networks (CNNs) are oftentimes used to efficiently and reliably solve a wide range of inference problems. For example, CNNs are included in many image recognition, handwriting recognition, and speech translation algorithms. In operation, CNNs can substantially reduce error rates compared to many simpler machine learning techniques. However, the time required for CNNs to execute usually exceeds the time required for simpler machine learning techniques to execute. Consequently, time-sensitive applications may be structured to implement simpler machine learning techniques at the expense of producing inferior results.

0006As a general matter, the time required for a CNN to execute is dominated by the time required for the CNN to perform “multi-convolution” operations. A multi-convolution operation is a generalized form of a multi-dimension convolution operation between sample data, such as an image, and a filter. The multi-convolution operation is oftentimes implemented using a stencil-based technique or using Fast Fourier Transforms (FFTs). While stencil-based techniques and FFT-based techniques may enable some multi-convolution operations to be implemented more efficiently, such techniques are normally unable to allow multi-convolution operations to execute efficiently over the full range of dimensions and additional parameters typically associated with standard CNNs.

0007In this regard, a CNN typically includes multiple “convolution layers,” where each convolution layer performs convolution operations across multiple dimensions of a sample data batch and multiple dimensions of a filter stack. For example, for a four dimensional CNN involving image samples, the sample data batch is a batch of images, and the four dimensions of the image batch include the image width, the image height, the number of color planes per image, and the number of images in the image batch. The four dimensions of the filter stack include the filter width, the filter height, the number of feature planes per filter, and the number of filters in the filter stack. Additional parameters may further customize the multi-convolution operations. For example, a horizontal filter stride and a vertical filter stride may reduce the overall computational load by decreasing the size of the subset of pixels involved in the convolution operation. Notably, the dimensions of the image batch and the filter stack as well as the additional parameters often vary between convolution layers.

0008Stencil-based techniques are typically tuned to optimize multi-convolution operations across a relatively small subset of dimensions and parameters. However, the performance of stencil-based techniques across other dimensions and parameters usually exceeds the time required to execute simpler machine learning techniques. Consequently, as alluded to above, the time required to execute many CNNs using stencil-based techniques is typically unacceptably long. As also alluded to above, the time required to execute many CNNs using FFT-based approaches also varies dramatically based on the values of the parameters.

0009One approach to reducing the time required to execute CNNs across a wide range of parameter values incorporates the observation that convolution is a linear operator and therefore may be lowered onto matrix multiplication. Such an approach requires expanding the sample data into the required matrix form. More specifically, in such implementations, the convolution engine converts the image batch into a column-major image matrix and expresses the filter stack as a filter matrix. Subsequently, the convolution engine performs matrix multiplication operations between the image matrix and the filter stack. Notably, the dimensions of the image matrix and the filter matrix correspond to products of subsets of the independent parameters of the CNN instead of the individual parameters. As a result, matrix-based techniques exhibit relatively uniform performance characteristics across the different input dimensions and parameters. Further, because libraries of code written for each of many types of processing units include optimized matrix multiplication routines, the time required to execute a CNN via the foregoing approach may be significantly less than the time required to execute the CNN using stencil-based or FFT-based techniques.

0010One drawback to implementing such matrix-based operations in a convolution engine is that, as part of expanding the image batch to properly set up the matrix multiplication operations, the convolution engine has to copy the image data to multiple locations in the image matrix. Consequently, the size of the image matrix may increase to the point where the available memory is completely consumed. For example, suppose that the image width were W, the image height were H, the number of color planes per image were C, and the number of images in the image batch were N. Further, suppose that the dimensions of each of the output images were (P×Q). In such a scenario, the dimensions of the image matrix would be (N×P×Q)×(C×R×S). In many systems, the space needed to store image matrices of this size can exceed the available space in memory.

0011In an effort to reduce memory use while executing a multi-convolution via an optimized matrix multiplication routine, a tile-based convolution engine can be implemented that configures a parallel processing pipeline to independently expand and process individual tiles of the image matrix. In such an approach, the parallel processing pipeline performs address calculations to expand each tile of the image matrix in shared memory on an as-needed basis. The parallel processing pipeline then performs matrix multiplication operations between the image tile and the filter stack. Because the expanded image matrix is expanded directly into shared memory a tile at a time, the matrix is never stored in its entirety, and the amount of parallel processing memory used can be dramatically reduced compared to typical matrix-based convolution engines.

0012One drawback of tile-based convolution engines, however, is that calculating the address sequence needed to load the image data in the correct order to expand a tile of the expanded image matrix involves performing a sequence of dependent integer operations. This sequence of integer operations typically requires a relatively large number of clock cycles to execute. Oftentimes, the number of clock cycles required to perform the integer operations can exceed the number of clock cycles required to perform the matrix multiplication operations. As a result, the benefits of the optimized matrix multiplication routine are not fully realized and the overall time to execute CNNs may be unacceptably long.

0013More specifically, each loop iteration in a matrix multiplication is typically sized for a certain number of floating point math operations to cover the memory latency of the loads. For example, one implementation could have 100 math operations for 10 memory loads. Typically, those 10 memory loads execute relatively quickly and will return as the 100 math operations are finishing. However, if each such memory operation takes 10 extra integer operations, each dependent on the previous operation with a 10 cycle latency, then the cost to generate the 10 addresses is 100 cycles—matching the number of math operations before accounting for the memory latency to service those memory loads. If those memory loads take on average 10 cycles themselves, then we have now taken 200 cycles to load memory versus 100 cycles to calculate the floating point math operations, leading to 100 cycles in which no useful math is available to cover the memory latency, hurting overall efficiency.

0014As the foregoing illustrates, what is needed in the art is a more effective approach to performing multi-convolution operations.

SUMMARY OF THE INVENTION

0015One embodiment of the present invention sets forth a computer-implemented method for performing a multi-convolution operation. The method includes selecting a first start address based on a first destination address included in a first image tile that is stored in a first memory; identifying a first offset based on the first destination address; computing a first source address included in an image batch that is stored in a second memory based on the first start address and the first offset; copying data from the first source address to the first destination address; and after copying the data, performing one or more matrix multiplication operations between the first image tile and a first filter tile.

0016Further embodiments provide, among other things, a non-transitory computer-readable medium and a system configured to implement the method set forth above.

0017One advantage of the disclosed techniques is that applications may perform multi-convolution operations via an optimized matrix multiplication routinewhile optimizing parallel processing memory usage. In particular, precomputing offsets reduces the latency associated with calculating addresses while expanding each image tile of a virtual image matrix on the fly.

BRIEF DESCRIPTION OF THE DRAWINGS

0018So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

0019<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating a computer system configured to implement one or more aspects of the present invention;

0020<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a parallel processing unit included in the parallel processing subsystem of <figref idref="DRAWINGS">FIG. 1</figref>, according to various embodiments of the present invention;

0021<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of a general processing cluster included in the parallel processing unit of <figref idref="DRAWINGS">FIG. 2</figref>, according to various embodiments of the present invention;

0022<figref idref="DRAWINGS">FIG. 4</figref> illustrates an image batch, a filter stack, and an output batch associated with a multi-convolution operation, according to various embodiments of the present invention.

0023<figref idref="DRAWINGS">FIG. 5</figref> illustrates the relationship between the image batch of <figref idref="DRAWINGS">FIG. 4</figref> and a virtual image matrix, according to various embodiments of the present invention;

0024<figref idref="DRAWINGS">FIG. 6</figref> illustrates the relationships between the image batch of <figref idref="DRAWINGS">FIG. 4</figref>, an offset sequence, and the virtual image matrix of <figref idref="DRAWINGS">FIG. 5</figref>, according to various embodiments of the present invention;

0025<figref idref="DRAWINGS">FIG. 7</figref> illustrates the convolution preprocessor of <figref idref="DRAWINGS">FIG. 1</figref> configured to generate the offset sequence of <figref idref="DRAWINGS">FIG. 6</figref>, according to various embodiments of the present invention;

0026<figref idref="DRAWINGS">FIG. 8</figref> illustrates the convolution engine of <figref idref="DRAWINGS">FIG. 1</figref> configured to perform a multi-convolution operation, according to various embodiments of the present invention;

0027<figref idref="DRAWINGS">FIG. 9</figref> is a flow diagram of method steps for performing a multi-convolution operation in a parallel processing system, according to various embodiments of the present invention.

DETAILED DESCRIPTION

0028In the following description, numerous specific details are set forth to provide a more thorough understanding of the present invention. However, it will be apparent to one of skill in the art that the present invention may be practiced without one or more of these specific details.

System Overview

0029<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating a computer system <b>100</b> configured to implement one or more aspects of the present invention. As shown, computer system <b>100</b> includes, without limitation, a central processing unit (CPU) <b>102</b> and a system memory <b>104</b> coupled to a parallel processing subsystem <b>112</b> via a memory bridge <b>105</b> and a communication path <b>113</b>. Memory bridge <b>105</b> is further coupled to an I/O (input/output) bridge <b>107</b> via a communication path <b>106</b>, and I/O bridge <b>107</b> is, in turn, coupled to a switch <b>116</b>.

0030In operation, I/O bridge <b>107</b> is configured to receive user input information from input devices <b>108</b>, such as a keyboard or a mouse, and forward the input information to CPU <b>102</b> for processing via communication path <b>106</b> and memory bridge <b>105</b>. Switch <b>116</b> is configured to provide connections between I/O bridge <b>107</b> and other components of the computer system <b>100</b>, such as a network adapter <b>118</b> and various add-in cards <b>120</b> and <b>121</b>.

0031As also shown, I/O bridge <b>107</b> is coupled to a system disk <b>114</b> that may be configured to store content and applications and data for use by CPU <b>102</b> and parallel processing subsystem <b>112</b>. As a general matter, system disk <b>114</b> provides non-volatile storage for applications and data and may include fixed or removable hard disk drives, flash memory devices, and CD-ROM (compact disc read-only-memory), DVD-ROM (digital versatile disc-ROM), Blu-ray, HD-DVD (high definition DVD), or other magnetic, optical, or solid state storage devices. Finally, although not explicitly shown, other components, such as universal serial bus or other port connections, compact disc drives, digital versatile disc drives, film recording devices, and the like, may be connected to I/O bridge <b>107</b> as well.

0032In various embodiments, memory bridge <b>105</b> may be a Northbridge chip, and I/O bridge <b>107</b> may be a Southbridge chip. In addition, communication paths <b>106</b> and <b>113</b>, as well as other communication paths within computer system <b>100</b>, may be implemented using any technically suitable protocols, including, without limitation, AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol known in the art.

0033In some embodiments, parallel processing subsystem <b>112</b> comprises a graphics subsystem that delivers pixels to a display device <b>110</b> that may be any conventional cathode ray tube, liquid crystal display, light-emitting diode display, or the like. In such embodiments, the parallel processing subsystem <b>112</b> incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry. As described in greater detail below in <figref idref="DRAWINGS">FIG. 2</figref>, such circuitry may be incorporated across one or more parallel processing units (PPUs) included within parallel processing subsystem <b>112</b>. In other embodiments, the parallel processing subsystem <b>112</b> incorporates circuitry optimized for general purpose and/or compute processing. Again, such circuitry may be incorporated across one or more PPUs included within parallel processing subsystem <b>112</b> that are configured to perform such general purpose and/or compute operations. In yet other embodiments, the one or more PPUs included within parallel processing subsystem <b>112</b> may be configured to perform graphics processing, general purpose processing, and compute processing operations.

0034As shown, the system memory <b>104</b> includes at least one device driver <b>175</b> and a convolution subsystem <b>180</b>. The device driver <b>175</b> is configured to manage the processing operations of the one or more PPUs within parallel processing subsystem <b>112</b>. The convolution subsystem <b>180</b> includes, without limitation, a convolution preprocessor <b>182</b> and a convolution engine <b>184</b>. The convolution preprocessor <b>182</b> performs computations designed to increase the efficiency of the convolution engine <b>184</b> and the convolution engine <b>184</b> is configured to perform multi-convolution operations.

0035The convolution preprocessor <b>182</b> may execute on the CPU <b>120</b>, the parallel processing subsystem <b>112</b>, or any combination thereof. The convolution engine <b>184</b> executes on the parallel processing subsystem <b>112</b>, and the parallel processing subsystem <b>112</b> executes an optimized matrix multiplication routine included in a library. Notably, such multi-convolution operations dominate the time required to execute Convolutional Neural Networks (CNN). Although not shown, the system memory <b>104</b> also includes any number of software applications that execute on the CPU <b>102</b>, may issue commands that control the operation of the PPUs, and may leverage the convolution subsystem <b>180</b> to efficiently execute CNNs.

0036In various embodiments, the parallel processing subsystem <b>112</b> may be integrated with one or more other the other elements of <figref idref="DRAWINGS">FIG. 1</figref> to form a single system. For example, the parallel processing subsystem <b>112</b> may be integrated with the CPU <b>102</b> and other connection circuitry on a single chip to form a system on chip (SoC).

0037It will be appreciated that the system shown herein is illustrative and that variations and modifications are possible. The connection topology, including the number and arrangement of bridges, the number of CPUs <b>102</b>, and the number of parallel processing subsystems <b>112</b>, may be modified as desired. For example, in some embodiments, system memory <b>104</b> could be connected to CPU <b>102</b> directly rather than through memory bridge <b>105</b>, and other devices would communicate with system memory <b>104</b> via memory bridge <b>105</b> and CPU <b>102</b>. In other alternative topologies, parallel processing subsystem <b>112</b> may be connected to I/O bridge <b>107</b> or directly to CPU <b>102</b>, rather than to memory bridge <b>105</b>. In still other embodiments, I/O bridge <b>107</b> and memory bridge <b>105</b> may be integrated into a single chip instead of existing as one or more discrete devices. Lastly, in certain embodiments, one or more components shown in <figref idref="DRAWINGS">FIG. 1</figref> may not be present. For example, switch <b>116</b> could be eliminated, and network adapter <b>118</b> and add-in cards <b>120</b>, <b>121</b> would connect directly to I/O bridge <b>107</b>.

0038<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a parallel processing unit (PPU) <b>202</b> included in the parallel processing subsystem <b>112</b> of <figref idref="DRAWINGS">FIG. 1</figref>, according to various embodiments of the present invention. Although <figref idref="DRAWINGS">FIG. 2</figref> depicts one PPU <b>202</b>, as indicated above, parallel processing subsystem <b>112</b> may include any number of PPUs <b>202</b>. As shown, PPU <b>202</b> is coupled to a local parallel processing (PP) memory <b>204</b>. PPU <b>202</b> and PP memory <b>204</b> may be implemented using one or more integrated circuit devices, such as programmable processors, application specific integrated circuits (ASICs), or memory devices, or in any other technically feasible fashion.

0039In some embodiments, PPU <b>202</b> comprises a graphics processing unit (GPU) that may be configured to implement a graphics rendering pipeline to perform various operations related to generating pixel data based on graphics data supplied by CPU <b>102</b> and/or system memory <b>104</b>. When processing graphics data, PP memory <b>204</b> can be used as graphics memory that stores one or more conventional frame buffers and, if needed, one or more other render targets as well. Among other things, PP memory <b>204</b> may be used to store and update pixel data and deliver final pixel data or display frames to display device <b>110</b> for display. In some embodiments, PPU <b>202</b> also may be configured for general-purpose processing and compute operations.

0040In operation, CPU <b>102</b> is the master processor of computer system <b>100</b>, controlling and coordinating operations of other system components. In particular, CPU <b>102</b> issues commands that control the operation of PPU <b>202</b>. In some embodiments, CPU <b>102</b> writes a stream of commands for PPU <b>202</b> to a data structure (not explicitly shown in either <figref idref="DRAWINGS">FIG. 1</figref> or <figref idref="DRAWINGS">FIG. 2</figref>) that may be located in system memory <b>104</b>, PP memory <b>204</b>, or another storage location accessible to both CPU <b>102</b> and PPU <b>202</b>. A pointer to the data structure is written to a pushbuffer to initiate processing of the stream of commands in the data structure. The PPU <b>202</b> reads command streams from the pushbuffer and then executes commands asynchronously relative to the operation of CPU <b>102</b>. In embodiments where multiple pushbuffers are generated, execution priorities may be specified for each pushbuffer by an application program via device driver <b>175</b> to control scheduling of the different pushbuffers.

0041As also shown, PPU <b>202</b> includes an I/O (input/output) unit <b>205</b> that communicates with the rest of computer system <b>100</b> via the communication path <b>113</b> and memory bridge <b>105</b>. I/O unit <b>205</b> generates packets (or other signals) for transmission on communication path <b>113</b> and also receives all incoming packets (or other signals) from communication path <b>113</b>, directing the incoming packets to appropriate components of PPU <b>202</b>. For example, commands related to processing tasks may be directed to a host interface <b>206</b>, while commands related to memory operations (e.g., reading from or writing to PP memory <b>204</b>) may be directed to a crossbar unit <b>210</b>. Host interface <b>206</b> reads each pushbuffer and transmits the command stream stored in the pushbuffer to a front end <b>212</b>.

0042As mentioned above in conjunction with <figref idref="DRAWINGS">FIG. 1</figref>, the connection of PPU <b>202</b> to the rest of computer system <b>100</b> may be varied. In some embodiments, parallel processing subsystem <b>112</b>, which includes at least one PPU <b>202</b>, is implemented as an add-in card that can be inserted into an expansion slot of computer system <b>100</b>. In other embodiments, PPU <b>202</b> can be integrated on a single chip with a bus bridge, such as memory bridge <b>105</b> or I/O bridge <b>107</b>. Again, in still other embodiments, some or all of the elements of PPU <b>202</b> may be included along with CPU <b>102</b> in a single integrated circuit or system of chip (SoC).

0043In operation, front end <b>212</b> transmits processing tasks received from host interface <b>206</b> to a work distribution unit (not shown) within task/work unit <b>207</b>. The work distribution unit receives pointers to processing tasks that are encoded as task metadata (TMD) and stored in memory. The pointers to TMDs are included in a command stream that is stored as a pushbuffer and received by the front end unit <b>212</b> from the host interface <b>206</b>. Processing tasks that may be encoded as TMDs include indices associated with the data to be processed as well as state parameters and commands that define how the data is to be processed. For example, the state parameters and commands could define the program to be executed on the data. The task/work unit <b>207</b> receives tasks from the front end <b>212</b> and ensures that GPCs <b>208</b> are configured to a valid state before the processing task specified by each one of the TMDs is initiated. A priority may be specified for each TMD that is used to schedule the execution of the processing task. Processing tasks also may be received from the processing cluster array <b>230</b>. Optionally, the TMD may include a parameter that controls whether the TMD is added to the head or the tail of a list of processing tasks (or to a list of pointers to the processing tasks), thereby providing another level of control over execution priority.

0044PPU <b>202</b> advantageously implements a highly parallel processing architecture based on a processing cluster array <b>230</b> that includes a set of C general processing clusters (GPCs) <b>208</b>, where C≧1. Each GPC <b>208</b> is capable of executing a large number (e.g., hundreds or thousands) of threads concurrently, where each thread is an instance of a program. In various applications, different GPCs <b>208</b> may be allocated for processing different types of programs or for performing different types of computations. The allocation of GPCs <b>208</b> may vary depending on the workload arising for each type of program or computation.

0045Memory interface <b>214</b> includes a set of D of partition units <b>215</b>, where D≧1. Each partition unit <b>215</b> is coupled to one or more dynamic random access memories (DRAMs) <b>220</b> residing within PPM memory <b>204</b>. In one embodiment, the number of partition units <b>215</b> equals the number of DRAMs <b>220</b>, and each partition unit <b>215</b> is coupled to a different DRAM <b>220</b>. In other embodiments, the number of partition units <b>215</b> may be different than the number of DRAMs <b>220</b>. Persons of ordinary skill in the art will appreciate that a DRAM <b>220</b> may be replaced with any other technically suitable storage device. In operation, various render targets, such as texture maps and frame buffers, may be stored across DRAMs <b>220</b>, allowing partition units <b>215</b> to write portions of each render target in parallel to efficiently use the available bandwidth of PP memory <b>204</b>.

0046A given GPCs <b>208</b> may process data to be written to any of the DRAMs <b>220</b> within PP memory <b>204</b>. Crossbar unit <b>210</b> is configured to route the output of each GPC <b>208</b> to the input of any partition unit <b>215</b> or to any other GPC <b>208</b> for further processing. GPCs <b>208</b> communicate with memory interface <b>214</b> via crossbar unit <b>210</b> to read from or write to various DRAMs <b>220</b>. In one embodiment, crossbar unit <b>210</b> has a connection to I/O unit <b>205</b>, in addition to a connection to PP memory <b>204</b> via memory interface <b>214</b>, thereby enabling the processing cores within the different GPCs <b>208</b> to communicate with system memory <b>104</b> or other memory not local to PPU <b>202</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 2</figref>, crossbar unit <b>210</b> is directly connected with I/O unit <b>205</b>. In various embodiments, crossbar unit <b>210</b> may use virtual channels to separate traffic streams between the GPCs <b>208</b> and partition units <b>215</b>.

0047Again, GPCs <b>208</b> can be programmed to execute processing tasks relating to a wide variety of applications, including, without limitation, linear and nonlinear data transforms, filtering of video and/or audio data, modeling operations (e.g., applying laws of physics to determine position, velocity and other attributes of objects), image rendering operations (e.g., tessellation shader, vertex shader, geometry shader, and/or pixel/fragment shader programs), general compute operations, etc. In operation, PPU <b>202</b> is configured to transfer data from system memory <b>104</b> and/or PP memory <b>204</b> to one or more on-chip memory units, process the data, and write result data back to system memory <b>104</b> and/or PP memory <b>204</b>. The result data may then be accessed by other system components, including CPU <b>102</b>, another PPU <b>202</b> within parallel processing subsystem <b>112</b>, or another parallel processing subsystem <b>112</b> within computer system <b>100</b>.

0048As noted above, any number of PPUs <b>202</b> may be included in a parallel processing subsystem <b>112</b>. For example, multiple PPUs <b>202</b> may be provided on a single add-in card, or multiple add-in cards may be connected to communication path <b>113</b>, or one or more of PPUs <b>202</b> may be integrated into a bridge chip. PPUs <b>202</b> in a multi-PPU system may be identical to or different from one another. For example, different PPUs <b>202</b> might have different numbers of processing cores and/or different amounts of PP memory <b>204</b>. In implementations where multiple PPUs <b>202</b> are present, those PPUs may be operated in parallel to process data at a higher throughput than is possible with a single PPU <b>202</b>. Systems incorporating one or more PPUs <b>202</b> may be implemented in a variety of configurations and form factors, including, without limitation, desktops, laptops, handheld personal computers or other handheld devices, servers, workstations, game consoles, embedded systems, and the like.

0049<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of a GPC <b>208</b> included in PPU <b>202</b> of <figref idref="DRAWINGS">FIG. 2</figref>, according to various embodiments of the present invention. In operation, GPC <b>208</b> may be configured to execute a large number of threads in parallel to perform graphics, general processing and/or compute operations. As used herein, a “thread” refers to an instance of a particular program executing on a particular set of input data. In some embodiments, single-instruction, multiple-data (SIMD) instruction issue techniques are used to support parallel execution of a large number of threads without providing multiple independent instruction units. In other embodiments, single-instruction, multiple-thread (SIMT) techniques are used to support parallel execution of a large number of generally synchronized threads, using a common instruction unit configured to issue instructions to a set of processing engines within GPC <b>208</b>. Unlike a SIMD execution regime, where all processing engines typically execute identical instructions, SIMT execution allows different threads to more readily follow divergent execution paths through a given program. Persons of ordinary skill in the art will understand that a SIMD processing regime represents a functional subset of a SIMT processing regime.

0050Operation of GPC <b>208</b> is controlled via a pipeline manager <b>305</b> that distributes processing tasks received from a work distribution unit (not shown) within task/work unit <b>207</b> to one or more streaming multiprocessors (SMs) <b>310</b>. Pipeline manager <b>305</b> may also be configured to control a work distribution crossbar <b>330</b> by specifying destinations for processed data output by SMs <b>310</b>.

0051In one embodiment, GPC <b>208</b> includes a set of M of SMs <b>310</b>, where M≧1. Also, each SM <b>310</b> includes a set of functional execution units (not shown in <figref idref="DRAWINGS">FIG. 3</figref>), such as execution units and load-store units. Processing operations specific to any of the functional execution units may be pipelined, which enables a new instruction to be issued for execution before a previous instruction has completed execution. Any combination of functional execution units within a given SM <b>310</b> may be provided. In various embodiments, the functional execution units may be configured to support a variety of different operations including integer and floating-point arithmetic (e.g., addition and multiplication), comparison operations, Boolean operations (AND, OR, XOR), bit-shifting, and computation of various algebraic functions (e.g., planar interpolation and trigonometric, exponential, and logarithmic functions, etc.). Advantageously, the same functional execution unit can be configured to perform different operations.

0052In operation, each SM <b>310</b> is configured to process one or more thread groups. As used herein, a “thread group” or “warp” refers to a group of threads concurrently executing the same program on different input data, with one thread of the group being assigned to a different execution unit within an SM <b>310</b>. A thread group may include fewer threads than the number of execution units within the SM <b>310</b>, in which case some of the execution may be idle during cycles when that thread group is being processed. A thread group may also include more threads than the number of execution units within the SM <b>310</b>, in which case processing may occur over consecutive clock cycles. Since each SM <b>310</b> can support up to G thread groups concurrently, it follows that up to G*M thread groups can be executing in GPC <b>208</b> at any given time.

0053Additionally, a plurality of related thread groups may be active (in different phases of execution) at the same time within an SM <b>310</b>. This collection of thread groups is referred to herein as a “cooperative thread array” (“CTA”) or “thread array.” The size of a particular CTA is equal to m*k, where k is the number of concurrently executing threads in a thread group, which is typically an integer multiple of the number of execution units within the SM <b>310</b>, and m is the number of thread groups simultaneously active within the SM <b>310</b>.

0054As shown, each SM <b>310</b> includes, without limitation, a shared memory <b>382</b> and a level one (L1) cache <b>384</b>. The shared memory <b>382</b> is typically a relatively small section of static random-access memory (SRAM) that is local to the SM <b>310</b>. One or more portions of the shared memory <b>382</b> are shared amongst the threads in a CTA. The L1 cache <b>384</b> supports, among other things, load and store operations performed by the execution units.

0055Each SM <b>310</b> also has access to level two (L2) caches (not shown) that are shared among all GPCs <b>208</b> in PPU <b>202</b>. The L2 caches may be used to transfer data between threads. Finally, SMs <b>310</b> also have access to off-chip memory, which may include PP memory <b>204</b> (also known as “global” memory) and/or system memory <b>104</b>. Additionally, as shown in <figref idref="DRAWINGS">FIG. 3</figref>, a level one-point-five (L1.5) cache <b>335</b> may be included within GPC <b>208</b> and configured to receive and hold data requested from memory via memory interface <b>214</b> by SM <b>310</b>. Such data may include, without limitation, instructions, uniform data, and constant data. In embodiments having multiple SMs <b>310</b> within GPC <b>208</b>, the SMs <b>310</b> may beneficially share common instructions and data cached in L1.5 cache <b>335</b>.

0056Each GPC <b>208</b> may have an associated memory management unit (MMU) <b>320</b> that is configured to map virtual addresses into physical addresses. In various embodiments, MMU <b>320</b> may reside either within GPC <b>208</b> or within the memory interface <b>214</b>. The MMU <b>320</b> includes a set of page table entries (PTEs) used to map a virtual address to a physical address of a tile or memory page and optionally a cache line index. The MMU <b>320</b> may include address translation lookaside buffers (TLB) or caches that may reside within SMs <b>310</b>, within one or more L1 caches, or within GPC <b>208</b>.

0057In graphics and compute applications, GPC <b>208</b> may be configured such that each SM <b>310</b> is coupled to a texture unit <b>315</b> for performing texture mapping operations, such as determining texture sample positions, reading texture data, and filtering texture data.

0058In operation, each SM <b>310</b> transmits a processed task to work distribution crossbar <b>330</b> in order to provide the processed task to another GPC <b>208</b> for further processing or to store the processed task in an L2 cache (not shown), parallel processing memory <b>204</b>, or system memory <b>104</b> via crossbar unit <b>210</b>. In addition, a pre-raster operations (preROP) unit <b>325</b> is configured to receive data from SM <b>310</b>, direct data to one or more raster operations (ROP) units within partition units <b>215</b>, perform optimizations for color blending, organize pixel color data, and perform address translations.

0059It will be appreciated that the core architecture described herein is illustrative and that variations and modifications are possible. Among other things, any number of processing units, such as SMs <b>310</b>, texture units <b>315</b>, or preROP units <b>325</b>, may be included within GPC <b>208</b>. Further, as described above in conjunction with <figref idref="DRAWINGS">FIG. 2</figref>, PPU <b>202</b> may include any number of GPCs <b>208</b> that are configured to be functionally similar to one another so that execution behavior does not depend on which GPC <b>208</b> receives a particular processing task. Further, each GPC <b>208</b> operates independently of the other GPCs <b>208</b> in PPU <b>202</b> to execute tasks for one or more application programs. In view of the foregoing, persons of ordinary skill in the art will appreciate that the architecture described in <figref idref="DRAWINGS">FIGS. 1-3A</figref> in no way limits the scope of the present invention.

Generating Image Tiles

0060In general, the SM <b>310</b> may be configured to execute a large number of threads in parallel to perform graphics, general processing and/or compute operations. Notably, the concurrency and dedicated memory resources provided by the SM <b>310</b> typically allow the SM <b>310</b> to optimize the execution of computationally-intensive operations. One computationally-intensive operation that is particularly well-suited for execution by the SM <b>310</b> is the multi-convolution operation. Typically, in conventional techniques that leverage parallel processing subsystems to perform multi-convolution operations, the SMs <b>310</b> execute optimized matrix multiplication routines included in libraries.

0061One limitation of such matrix-based approaches to performing multi-convolution operations is that the memory required to set up efficient matrix multiplication operations may strain the available PP memory <b>204</b>. More specifically, the image matrix that is the input to the matrix multiplication is an expanded version—containing significant redundant data—of the image batch that is the input to the multi-convolution image. In operation, the SM <b>310</b> executes the matrix multiplication operations on sub-matrices, referred to herein as tiles, of the image batch. Accordingly, to exploit the optimized matrix multiplication routine without straining the PP memory <b>204</b>, for each “image tile,” the convolution subsystem <b>180</b> generates the image tile as-needed, processes the image tile, and then discards the image tile. Advantageously, only a portion of the image matrix is stored in the shared memory <b>382</b> at any given time. In alternate embodiments, the convolution subsystem <b>180</b> may operate on any type of input data, also referred to herein as “samples,” instead of image data.

0062<figref idref="DRAWINGS">FIG. 4</figref> illustrates an image batch <b>410</b>, a filter stack <b>440</b>, and an output batch <b>470</b> associated with a multi-convolution operation, according to various embodiments of the present invention. In the context of <figref idref="DRAWINGS">FIG. 4</figref>, the streaming multiprocessor (SM) <b>310</b> is configured to perform a multi-convolution operation between the image batch <b>410</b> and the filter stack <b>440</b> to produce the output batch <b>470</b>. The multi-convolution operation corresponds to the predominant calculation involved in executing a particular convolution layer included in a CNN.

0063As shown, the image batch <b>410</b> includes, without limitation, any number of input images <b>420</b>(0:N-1). For explanatory purposes, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed. Further, a range of “X” like objects are denoted with a parenthetical range (i.e., (0:X-1)). Each of the input images <b>420</b> includes, without limitation, any number of color planes <b>430</b>(0:C-1). For example, each of the input images <b>420</b> may include three color planes <b>430</b>: the color plane <b>430</b>(0) “red”,” the color plane <b>430</b>(1) “green,” and the color plane <b>430</b>(2) “blue.” Each of the input images <b>420</b> is associated with an image height, shown as “H,” and an image width, shown as “W.” Notably, the image height and the image width define the dimensions of each of the color planes <b>430</b>. Accordingly, the image batch <b>410</b> includes (N×C×H×W) unique values.

0064In a complementary fashion, the filter stack <b>440</b> includes, without limitation, any number of filters <b>450</b>(0:K-1). In some embodiments, each of the filters <b>450</b> may represent a triggering search item associated with the layer of the CNN. For example, the CNN may be included in a face recognition algorithm, and the filter <b>450</b>(0) may represent an ear. Each of the filters <b>450</b> includes, without limitation, features planes <b>460</b>(0:C-1), where the number of the feature planes <b>460</b> is equal to the number of the color planes <b>430</b>. Each of the filters <b>450</b> is associated with a filter height, shown as “R,” and an filter width, shown as “S.” The filter height and the filter width define the dimensions of each of the feature planes <b>460</b> and, therefore, the filter stack <b>440</b> includes (K×C×R×S) unique values.

0065As also shown, there are numerous parameters <b>465</b> associated with the multi-convolution operation. The dimensions of the image batch <b>410</b> and the filter stack <b>440</b> represent five independent parameters of the multi-convolution operation: N (the number of the input images <b>420</b> in the image batch <b>410</b>), C (the number of the color planes <b>430</b> in each of the input images <b>420</b> and the number of the feature planes <b>460</b> in each of the filters <b>450</b>), H (the image height), W (the image width), K (the number of the filters <b>450</b> in the filter stack <b>440</b>), R (the filter height), and S (the filter width). The parameters <b>465</b> also include, without limitation, V (a horizontal filter stride), and U (a vertical filter stride). The horizontal filter stride and the vertical filter stride reduce the computational load by decreasing the size of the subset of pixels involved in the multi-convolution operation. Notably, the horizontal filter stride and the vertical filter stride not only reduce the time required to perform the multi-convolution operation, but also reduce the size of the output batch <b>470</b> produced by the multi-convolution operation.

0066In alternate embodiments, additional parameters <b>465</b> may correspond to additional dimensions, strides, optimization, formatting, and/or other configuration options. For example, in some embodiments, the parameters <b>465</b> may include a padding height and a padding width. The padding height and the padding width append, respectively, rows of zeros and columns of zeros to output images <b>480</b> included in the output batch <b>470</b> for any technical reason, such as formatting for future operations.

0067The output batch <b>470</b> includes, without limitation, the output images <b>480</b>(0:N-1), where the number of the output images <b>480</b> equals the number of the input images <b>420</b>. Each of the output images <b>480</b> includes, without limitation, feature maps <b>490</b>(0:K-1), where the number of the feature maps <b>490</b> equals the number of the filters <b>450</b>. Each of the output images <b>480</b> is associated with an output height, shown as “P,” and an output width, shown as “Q.” The output height and the output width define the dimensions of the features maps <b>490</b>. Accordingly, the output batch <b>470</b> includes (N×K×P×Q) unique values.

0068As previously described herein, the convolution subsystem <b>180</b> leverages the optimized matrix multiplication capabilities of the SM <b>310</b> to efficiently perform the multi-convolution operation. As persons skilled in the art will recognize, the multi-convolution operation between the input batch <b>410</b> and the filter stack <b>440</b> may be converted to matrix multiplication operations between an image matrix and a filter matrix. The conversion operations are well-known in the art and result in deterministic relationships between the values included in the input batch <b>410</b> and the values included in the image matrix. In a complementary fashion, the conversion operations result in deterministic relationships between the values included in the filter stack <b>440</b> and the values included in the filter matrix. To optimize the use of the PP memory <b>204</b>, the convolution subsystem <b>180</b> does not store the image matrix in the PP memory <b>204</b>. Instead, the convolution subsystem <b>180</b> configures the SM <b>310</b> based on these deterministic relationships—expanding image tiles included in a “virtual” image matrix on the fly.

0069<figref idref="DRAWINGS">FIG. 5</figref> illustrates the relationship between the image batch <b>410</b> of <figref idref="DRAWINGS">FIG. 4</figref> and a virtual image matrix <b>510</b>, according to various embodiments of the present invention. <figref idref="DRAWINGS">FIG. 5</figref> also illustrates relationships between the filter stack <b>440</b> of <figref idref="DRAWINGS">FIG. 4</figref> and a virtual filter matrix <b>540</b>. For explanatory purposes, the parameters <b>465</b>, and consequently the dimensions of the image batch <b>410</b>, the virtual image matrix <b>510</b>, the filter stack <b>440</b>, and the virtual filter matrix <b>540</b>, are: N-1, C-2, H-3, W-3, K-2, R-2, S-2, U-1, and V-1. Further, in accordance with the memory footprint of the image batch <b>410</b>, image data strides <b>475</b> are: C stride=9, H stride=3, and W stride=1.

0070As part of the expansion of the image batch <b>410</b> into the virtual image matrix <b>510</b>, each of four columns in the virtual image matrix <b>510</b> is associated with the values included in the image batch <b>410</b> that are required to compute one column of values in an output matrix (not shown). Such an expansion includes duplication of some of the values included in the image batch <b>410</b>. For example, as depicted for the value “D4,” the center of each of the three-by-three color planes <b>410</b> is used four times to compute each of four columns in the output matrix and, consequently, each of the center values (e.g., the “D4” values) is associated with four separate columns of the virtual image matrix <b>510</b>. For explanatory purposes, values included in the image batch <b>410</b> are referred to as the data at “source” addresses. Similarly, values included in the virtual image matrix <b>510</b> are referred to herein as the data at corresponding “virtual” addresses. As a result, multiple virtual addresses in the virtual image matrix <b>510</b> are associated with a single source address included in the image batch <b>410</b>. In a complementary manner, each of the rows of the virtual filter matrix <b>540</b> contains the values included in the filter stack <b>440</b> that are required to compute one or more of the tiles in an output matrix.

0071In general, if the dimensions of the input batch <b>410</b> are (N×C×H×W), the dimensions of the filter stack <b>440</b> are (K×C×R×S), and the dimensions of the output batch <b>470</b> are (N×K×P×Q), then the dimensions of the virtual image matrix <b>510</b> are (C×R×S)×(N×P×Q), the dimensions of the virtual filter matrix <b>540</b> are K×(C×R×S), and the dimensions of the output matrix are K×(N×P×Q). For the example shown, the dimensions of the input batch <b>410</b> are (1×3×3×3), the dimensions of the filter stack <b>440</b> are (2×3×2×2), and the dimensions of the output batch <b>470</b> are (1×2×2×2). Consequently, the dimensions of the virtual image matrix <b>510</b> are (12×4), the dimensions of the virtual filter matrix <b>540</b> are (2×12) and the dimensions of the output matrix are (2×4).

0072Notably, because the dimensions of the virtual image matrix <b>510</b> are products of the independent parameters associated with the multi-convolution operation, the matrix-based multi-convolution operation exhibits relatively uniform behavior across varying parameters. For example, although the parameters C, R, and S may individually vary dramatically across the multi-convolution operations associated with different layers of a particular CNN, the products of the parameters C, R, and S typically do not vary dramatically across the multi-convolution operations. Consequently, the optimized performance of the matrix-based multi-convolution operation is relatively consistent across changes in the values of individual parameters.

0073As the (C×R×S)×(N×P×Q) dimensions of the virtual image matrix <b>510</b> illustrate, simultaneously and redundantly storing the values associated with all the addresses included in the virtual image matrix <b>510</b> may strain the PP memory <b>204</b>. Consequently, the convolution subsystem <b>180</b> configures the SM <b>310</b> to manifest and process the virtual image matrix <b>510</b> in a “lazy” manner. More specifically, the convolution subsystem <b>180</b> partitions the virtual image matrix <b>510</b> into separate image tiles <b>542</b>, and then configures the SM <b>310</b> to process the image tiles <b>542</b>. Further, the convolution subsystem <b>180</b> associates each of the “destination” addresses in each of the image tiles <b>542</b> with a virtual address included in the virtual image matrix <b>510</b>. For example, as depicted in <figref idref="DRAWINGS">FIG. 5</figref>, the convolution engine <b>125</b> associates the sixteen destination addresses included in the image tile <b>542</b>(0) with the sixteen virtual addresses included in the first four rows of the virtual image matrix <b>510</b>.

0074Each of the virtual addresses in the virtual image matrix <b>510</b> is related deterministically to a source address included in the image batch <b>410</b>. Consequently, each of the destination addresses in the image tiles <b>542</b> is related deterministically to a source address included in the image batch <b>410</b>. Accordingly, the convolution subsystem <b>180</b> may perform addressing computations that enable the convolution subsystem <b>180</b> to copy the proper data from the image batch <b>410</b> directly to each destination address included in each of the image tiles <b>542</b> without creating the virtual input matrix <b>510</b>.

0075To avoid introducing integer latencies associated with performing addressing computations while generating the image tiles <b>542</b>, the convolution preprocessor <b>182</b> is configured to leverage a consistent pattern of source addresses that is inherent in the virtual image matrix <b>510</b>. More specifically, while each of the columns of the virtual image matrix <b>510</b> are associated with a different sequence of source addresses that follow a serpentine path through the image batch <b>410</b>, the sequences are affine (in a multi-dimensional sense).

0076For example, the first column of the virtual image matrix <b>510</b> is associated with the first source address sequence D0, D1, D3, and D4 for each of three color planes <b>430</b>. Adding 1 to each element in this first sequence yields D1, D2, D4, and D5 for each of the three colors planes <b>430</b>—corresponding to the source address sequence that is associated with the second column of the virtual image matrix <b>510</b>. Similarly, adding 3 to each element in the first sequence yields the source address sequence that is associated with the third column of the virtual image matrix <b>510</b>, and so forth. An example of how the convolution preprocessor <b>182</b> leverages this consistent pattern is described in greater detail in <figref idref="DRAWINGS">FIG. 6</figref>.

0077As part of processing each of the image tiles <b>542</b>, the SM <b>310</b> loads data from the image batch <b>410</b> to form the image tile <b>542</b>, and loads data from the filter stack <b>440</b> to form the corresponding filter tile <b>544</b>. The SM <b>310</b> then performs matrix multiplication operations between the image tile <b>542</b> and the filter tile <b>544</b>, stores the result as an output tile in the PP memory <b>204</b>, and then discards the data included in the image tile <b>542</b> and the filter tile <b>544</b>. Consequently, at any given point in time, the shared memory <b>382</b> includes the image tiles <b>542</b> that the SM <b>310</b> is currently processing, but does not necessarily include the image tiles <b>542</b> that the SM <b>310</b> has already processed or has not begun processing.

0078The convolution subsystem <b>180</b> may set the size of the image tile <b>542</b> in any technically feasible fashion that optimizes the capabilities of the SM <b>310</b>. For example, the convolution subsystem <b>180</b> may set the size of the image tile <b>542</b> based on any number and combination of the size of the shared memory <b>382</b>, the number of threads in each thread group, and so forth. In alternate embodiments, the convolution subsystem <b>180</b> may receive the size of the image tile <b>542</b> as an auxiliary input to the multi-convolution operation. The convolution subsystem <b>180</b> sets the size of the filter tile <b>544</b> based on the size of the image tile <b>542</b>. More specifically, the convolution subsystem <b>180</b> sets the size of the filter tile <b>545</b> such that the matrix multiplication between each the image tiles <b>542</b> and the corresponding filter tile <b>544</b> produces the data to properly populate an output tile.

0079In alternate embodiments, the convolution subsystem <b>180</b> may configure the SM <b>310</b> based on any technically feasible implementation of the virtual image matrix <b>510</b> and the virtual filter matrix <b>540</b> that facilitate performing the multi-convolution operation via matrix multiplication operations. Further, the convolution subsystem <b>180</b> may partition the data included in the virtual image matrix <b>510</b> and the virtual filter matrix <b>540</b> into image tiles <b>542</b> and filter tiles <b>544</b> in any technically feasible, consistent fashion.

Generating the Offset Sequence

0080<figref idref="DRAWINGS">FIG. 6</figref> illustrates the relationships between the image batch <b>410</b> of <figref idref="DRAWINGS">FIG. 4</figref>, an offset sequence <b>640</b>, and the virtual image matrix <b>510</b> of <figref idref="DRAWINGS">FIG. 5</figref>, according to various embodiments of the present invention. For explanatory purposes, the image batch <b>410</b> is depicted as image data <b>610</b> and as memory offsets <b>620</b>. As shown, the memory offset <b>620</b> for a particular value of image data <b>610</b> is a based on the color plane <b>430</b>, the vertical location within the image, the horizontal location within the image, and the data size associated with the value of the image data <b>610</b>. For example, the memory offset <b>620</b> for D4 is (1*2*2)*4 bytes=16.

0081As outlined in conjunction with <figref idref="DRAWINGS">FIG. 5</figref>, while the serpentine pattern of each column is offset from the serpentine pattern of the other columns, the serpentine pattern represents a uniform sequence of offsets for every row of the virtual image matrix <b>510</b>. For example, for each column of the virtual image matrix <b>510</b>, the source address associated with the second row is four greater than the source address associated with the first row. In operation, the convolution preprocessor <b>182</b> generates the offset sequence <b>640</b> based on this serpentine pattern. The offset sequence <b>640</b> includes an offset <b>642</b> for each row of the virtual image matrix <b>510</b>. The convolution preprocessor <b>182</b> may generate the offset sequence <b>640</b> in any technically feasible fashion that captures any pattern inherent in the virtual image matrix <b>510</b>.

0082Further, the serpentine pattern of each column is offset from the serpentine pattern of the other columns. For example, the first column of the virtual image matrix <b>510</b> is associated with the source address sequence 0, 4, 12, 16, 26, 40, 48, 52, 72, 76, 84, and 88. Adding 4 to each source address included in this sequence yields the source address sequence 4, 8, 16, 20, 40, 44, 52, 56, 76, 80, 88, and 92 that is associated with the second column of the virtual image matrix <b>510</b>. As persons skilled in the art will recognize, a column offset <b>632</b> that specifies a difference between the first column of the virtual image matrix <b>510</b> and a particular column of the virtual image matrix <b>510</b> equals the source address associated with the first row of the particular column.

0083<figref idref="DRAWINGS">FIG. 7</figref> illustrates the convolution preprocessor <b>182</b> of <figref idref="DRAWINGS">FIG. 1</figref> configured to generate the offset sequence <b>640</b> of <figref idref="DRAWINGS">FIG. 6</figref>, according to various embodiments of the present invention. As shown, <figref idref="DRAWINGS">FIG. 7</figref> depicts an offset sequence generator <b>720</b> as pseudocode that the convolution preprocessor <b>182</b> may implement. The offset sequence generator <b>720</b> creates the offset sequence <b>640</b> to offload time consuming address computations from the convolution engine <b>184</b>. Such offloading enables the SM <b>310</b> to efficiently execute an optimized matrix multiplication routine to perform the convolution operations.

0084In general, the offset sequence generator <b>720</b> may execute on any type and number of processing units and store the offset sequence <b>640</b> in any accessible memory. For example, in some embodiments, the offset sequence generator <b>720</b> may execute on the CPU <b>102</b> and store the offset sequence <b>640</b> in the system memory <b>104</b>. Subsequently, the device driver <b>175</b> may copy the offset sequence <b>640</b> to the PP memory <b>204</b>. When the convolution engine <b>184</b> accesses the offset sequence <b>640</b>, the offset sequence <b>640</b> may be loaded through the L1 cache <b>384</b>. In other embodiments, the offset sequence generator <b>720</b> may execute on the parallel processing subsystem <b>112</b>. In such embodiments, the offset sequence generator <b>720</b> may store the offset sequence <b>640</b> directly in the PP memory <b>204</b>.

0085As shown, the offset sequence generator <b>720</b> generates (C*R*S) offsets <b>642</b> based on the color plane (c) <b>430</b>, the filter height (r), the filter width (s), the image height stride (h stride), and the image width stride (w stride). In alternate embodiments, the pseudocode depicted in <figref idref="DRAWINGS">FIG. 7</figref> may be modified to represent any number of dimensions. Further, as shown in the pseudocode, the offset sequence generator <b>720</b> may be configured to generate an offset sequence <b>640</b> that represents a cross-correlation operation instead of a convolution operation.

0086As outlined above, the offset sequence <b>640</b> specifies a mapping from source addresses in the image batch <b>410</b> to virtual addresses in the virtual image matrix <b>510</b>. Since the convolution engine <b>125</b> associates each of the destination addresses in each of the image tiles <b>542</b> with virtual addresses in the virtual image matrix <b>510</b>, the convolution engine <b>125</b> may leverage the offset sequence <b>640</b> to properly populate the image tiles <b>542</b>. In general, the convolution preprocessor <b>182</b> and the convolution engine <b>125</b> may be configured to exploit any pattern inherent in the virtual image matrix <b>510</b> based on any number of offsets <b>642</b> and any number of offset sequences <b>640</b>.

Performing Matrix-Based Multi-Convolution Operations

0087<figref idref="DRAWINGS">FIG. 8</figref> illustrates the convolution engine <b>184</b> of <figref idref="DRAWINGS">FIG. 1</figref> configured to perform a multi-convolution operation, according to various embodiments of the present invention. In the context of <figref idref="DRAWINGS">FIG. 8</figref>, the convolution engine <b>184</b> configures functional units (e.g., execution units, load-store units, etc.) included in the streaming multiprocessor (SM) <b>310</b> to perform operations that implement multi-convolution operations. For explanatory purposes, operations performed by the SM <b>310</b>, including the functional execution units, that are configured by the convolution engine <b>184</b> are also referred to herein as operations performed by the convolution engine <b>184</b>.

0088In operation, to exploit the parallel processing capabilities of the SM <b>310</b>, the convolution engine <b>184</b> assigns the processing of each of the image tiles <b>542</b> to a thread group or a thread array. As persons skilled in the art will recognize, the convolution engine <b>184</b> may assign any number of image tiles <b>542</b> to a single thread group and/or may assign any number of operations or destination addresses in the image tiles <b>542</b> to a single thread. If a thread group is assigned to process multiple image tiles <b>542</b>, then the thread group may sequentially process the assigned image tiles <b>542</b> or may distribute the processing in any technically feasible fashion between the threads included in the thread group. If a thread is assigned to process multiple destination addresses in the image tile <b>542</b>, then the thread may sequentially process the assigned destination addresses.

0089Advantageously, the convolution engine <b>184</b> may configure the SM <b>310</b> to pipeline the processing of the image tiles <b>542</b> to minimize the latency associated with accessing the input data included in the PP memory <b>210</b>. More specifically, the convolution engine <b>184</b> may configure the SM <b>310</b> to copy data included in the image batch <b>410</b> and the filter stack <b>440</b> to, respectively, the image tile <b>542</b>(0) and the filter tile <b>544</b>(0). The convolution engine <b>184</b> may configure the SM <b>310</b> to then perform matrix multiplication operations between the image tile <b>542</b>(0) and the filter tile <b>544</b>(0) and, substantially in parallel, copy data included in the image batch <b>410</b> and the filter stack <b>440</b> to, respectively, the image tile <b>542</b>(1) and the filter tile <b>544</b>(1). In alternate embodiments, the convolution engine <b>184</b> may orchestrate any type of pipelining in any technically feasible fashion. For example, and without limitation, the convolution engine <b>184</b> may strategically assign the processing the image tiles <b>542</b> to thread groups to facilitate a two stage (loading data and performing matrix multiplication operations) pipeline.

0090As shown, the convolution engine <b>184</b> includes, without limitation, column offsets <b>632</b> and start addresses <b>634</b>. The PP memory <b>204</b> includes, without limitation, the filter stack <b>440</b>, the image batch <b>410</b>, the offset sequence <b>640</b>, and an output matrix <b>860</b>. As depicted using a dotted box, the convolution engine <b>184</b> typically accesses the offset sequence <b>640</b> through the L1 cache <b>384</b>. The shared memory <b>382</b> includes, without limitation, the image tile <b>542</b> and the filter tile <b>544</b>. For each thread group, the convolution engine <b>184</b> determines the source addresses in the image batch <b>410</b> corresponding to the destination addresses in the image tile <b>542</b> that is assigned to the thread group.

0091More specifically, for each image tile <b>542</b>, the threads in the assigned thread group collaboratively compute the column offsets <b>632</b> associated with the columns included in the image tile <b>542</b>. For example, for a four-by-four image tile <b>542</b>, the threads would calculate four column offsets <b>632</b> corresponding to four columns. More specifically, for each of the relevant columns, the assigned thread group sets the column offset <b>632</b> to the difference between the source address associated with the first row of the relevant column and the source address associated with the first row of the first column.

0092Subsequently, for each of the column offsets <b>632</b>, the assigned thread group sums the base address of the image batch <b>410</b> and the column offset <b>632</b> to generate the start address <b>634</b>. As persons skilled in the art will recognize, the start addresses <b>634</b> equal the source addresses in the image batch <b>410</b> that map to the first row of the virtual image matrix <b>510</b>. After computing the start addresses <b>634</b> for the image tile <b>542</b>, the threads in the assigned thread group perform image data addressing <b>850</b> to generate the image tile <b>542</b>.

0093First, the thread group accesses the portion of the offset sequence <b>640</b> associated with the rows of the virtual image matrix <b>510</b> that correspond to the image tile <b>542</b>. As previously described, each destination address included in the image tile <b>542</b> is associated with a virtual address included in the virtual image matrix <b>510</b>. Accordingly, the thread group populates the image tile <b>542</b> based on the mapping between the source address included in the image batch <b>410</b> and the virtual address included in the virtual image matrix <b>510</b>. In particular, the thread group computes the source address that corresponds to a column of the virtual image matrix <b>510</b> and a row of the virtual image matrix <b>510</b> as the sum of the start address <b>634</b> associated with the column and the offset <b>642</b> associated with the row. After computing each source address, the thread group copies the image data <b>610</b> stored at the source address (included in the image batch <b>410</b>) to the corresponding destination address included in the image tile <b>542</b>.

0094Because the convolution engine <b>184</b> generates the image tiles <b>542</b> as-needed, the convolution engine <b>184</b> stores only a portion of the virtual image matrix <b>510</b> in the shared memory <b>382</b> at any given time. The time required for the threads to execute the image data addressing <b>850</b> is significantly shorter than the time required to perform the numerous, dependent integer addressing operations implemented in some conventional tile-based convolution engines.

0095The thread group also generates the filter tile <b>544</b> associated with the image tile <b>542</b>. The thread group may copy data from the filter stack <b>440</b> included in the PP memory <b>204</b> to the filter tile <b>544</b> included in the shared memory <b>382</b> in any technically feasible fashion that is consistent with the data included in the image tile <b>542</b>. For example, the thread group may implement a linear mapping between the filter stack <b>440</b> and the filter tile <b>544</b> based on the source addresses associated with the image tile <b>542</b>.

0096After each thread group has finished generating the assigned image tile <b>542</b> and the corresponding filter tile <b>544</b>, the thread group executes within a floating-point unit included in the SM <b>310</b>, implementing the functionality of “per tile matrix multiplication” <b>855</b>. More specifically, each of the thread groups configures the floating-point unit to perform matrix multiplication operations between the assigned image tile <b>542</b> and the corresponding filter tile <b>544</b>. The thread group further configures the floating-point unit to update the output matrix <b>860</b> based on the results of the matrix multiplication.

0097After the thread groups have finished generating an output tile included in the output matrix <b>860</b>, the thread groups transpose the output matrix <b>860</b> into the output batch <b>470</b> (not shown in <figref idref="DRAWINGS">FIG. 8</figref>), also included in the PP memory <b>204</b>. The thread groups may implement any number formatting operations that generate the output batch <b>470</b> based on any organization or any subset or superset of the data included in the output matrix <b>860</b>. Typically, the output batch <b>470</b> implements a format that is consistent with the format of the image batch <b>410</b>, thereby enabling the output batch <b>470</b> to be used as the input batch <b>410</b> for the multi-convolution operation that implements the next convolution layer included in the CNN.

0098In general, components included in the computer system <b>100</b> may store any of the image batch <b>410</b>, the filter stack <b>440</b>, the offset sequence <b>640</b>, and/or the output matrix <b>860</b> in any type of memory structure included in the PP memory <b>204</b>. For example, any number, including zero, of the image batch <b>410</b>, the filter stack <b>440</b>, the offset sequence <b>640</b>, and/or the output matrix <b>860</b> may be included in a frame buffer. In other embodiments, components included in the computer system <b>100</b> may store the image batch <b>410</b>, the filter stack <b>440</b>, the offset sequence <b>640</b>, and/or the output matrix <b>860</b> in any type of memory instead of the PP memory <b>204</b>. Similarly, in alternate embodiments, the convolution engine <b>125</b> may store the image tiles <b>542</b> and the filter tiles <b>544</b> in any type of memory instead of the shared memory <b>382</b>.

0099In alternate embodiments, the convolution subsystem <b>180</b> may configure the offset sequence <b>640</b> to include any number of offsets <b>642</b> based on any number of parameters <b>465</b> and any number of image data strides <b>475</b> in any combination. For example, the number of dimensions associated with the image batch <b>410</b>, the number of dimensions associated with the filter stack <b>440</b>, the image data strides <b>475</b>, and the number of rows included in the virtual image matrix <b>510</b> could differ across various embodiments. Further, in some embodiments, the offset sequence <b>640</b> may include only a subset of dimensions. For example, the convolution preprocessor <b>182</b> could compute the offsets <b>642</b> for each of (R*S) rows of the virtual image matrix <b>510</b> based on the image height stride and image width stride. In a complementary fashion, the convolution engine <b>184</b> could be configured to apply the offsets <b>642</b> repeatedly—once for each of the C color planes <b>430</b>—across each of columns of the virtual image matrix <b>510</b> to determine the source addresses associated with each of the (C*R*S) rows of the virtual image matrix <b>510</b>.

0100<figref idref="DRAWINGS">FIG. 9</figref> is a flow diagram of method steps for performing a multi-convolution operation in a parallel processing system, according to various embodiments of the present invention. Although the method steps are described in conjunction with the systems of <figref idref="DRAWINGS">FIGS. 1-8</figref>, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the present invention.

0101As shown, a method <b>900</b> begins at step <b>902</b>, where the convolution subsystem <b>180</b> receives the image batch <b>410</b> and the filter stack <b>440</b>. At step <b>904</b>, the convolution preprocessor <b>182</b> computes the offset sequence <b>640</b> associated with the virtual image matrix <b>510</b> and then stores the offset sequence <b>640</b> in the PP memory <b>204</b>. The convolution preprocessor <b>182</b> may compute the offset sequence <b>640</b> in any technically feasible fashion that is representative of a pattern that maps a subset of source addresses in the image batch <b>410</b> to the corresponding virtual addresses along the image matrix columns <b>544</b> of the virtual image matrix <b>510</b> based on the row. For example, suppose that the dimensions of the dimensions of the input batch <b>410</b> are (N×C×H×W) and the dimensions of the filter stack <b>440</b> are (K×C×R×S). In such an example, the convolution preprocessor <b>182</b> could compute the offsets <b>642</b> for each of the (C*R*S) rows of the virtual image matrix <b>510</b> based on C stride, H stride, and W stride.

0102The convolution preprocessor <b>182</b> may execute on any processing unit (e.g., CPU <b>182</b>, SM <b>310</b>, etc.) and store the offset sequence <b>640</b> in the PP memory <b>204</b> in any technically feasible fashion. For example, in some embodiments, the convolution preprocessor <b>182</b> may execute on the CPU <b>182</b> and store the offset sequence <b>640</b> in the system memory <b>104</b>. Subsequently, the device driver <b>175</b> may copy the offset sequence <b>640</b> from the system memory <b>104</b> to the PP memory <b>204</b>. When the SM <b>310</b> initially accesses the offset sequence <b>640</b>, the SM <b>310</b> may load the offset sequence <b>640</b> into the L1 cache <b>384</b>.

0103At step <b>906</b>, the convolution subsystem <b>180</b> determines the size of the image tile <b>542</b> and then defines the image tiles <b>542</b>—associating destination addresses in each of the image tiles <b>542</b> with virtual addresses in the virtual image matrix <b>510</b>. At step <b>908</b>, the convolution engine <b>184</b> assigns the processing of each of the image tiles <b>542</b> to a thread group. The convolution engine <b>184</b> then configures the SM <b>310</b> to execute the thread groups.

0104At step <b>910</b>, for each of the image tiles <b>542</b>, the assigned thread group computes the start addresses <b>634</b> associated with the columns included in the image tile <b>542</b>. More specifically, for each of the columns, the assigned thread group sets the start address <b>634</b> to the source address included in the image batch <b>410</b> that is associated with the column of the virtual image matrix <b>510</b> and the first row of the virtual image matrix <b>510</b>. At step <b>912</b>, for each of the image tiles <b>542</b>, the thread group computes source addresses in the image batch <b>410</b> and copies the data stored at the source addresses to corresponding destination addresses in the assigned image tile <b>542</b> that is stored in the shared memory <b>382</b>. Notably, the threads in the assigned thread group compute the source address that corresponds to a particular column of the virtual image matrix <b>510</b> and a particular row of the virtual image matrix <b>510</b> as the sum of the start address <b>634</b> associated with the column and the offset <b>642</b> associated with the row.

0105At step <b>916</b>, for each of the image tiles <b>542</b>, the thread group performs matrix multiplication operations between the image tile <b>514</b> and the corresponding filter tile <b>544</b>. After all the threads groups have finished processing all the assigned image tiles <b>514</b>, the output matrix <b>860</b> is complete, and threads configured by the convolution subsystem <b>180</b> copy the data included in the output matrix <b>860</b> to the output batch <b>470</b> included in the PP memory <b>204</b>.

0106In sum, the disclosed techniques enable a convolution subsystem to efficiently perform multi-convolution operations in a parallel processing system. In general, the convolution subsystem implements a virtual image matrix conforming to a column major format that enables a matrix-based convolution operation. The convolution subsystem includes a convolution preprocessor that executes on the CPU and/or a streaming multiprocessor (SM) included in the parallel processing subsystem, and a convolution engine that executes on an SM included in the parallel processing subsystem.

0107In operation, an offset sequence generator included in the convolution preprocessor precomputes an offset sequence that reflects a serpentine pattern of source memory addresses associated with a column of the virtual image matrix. Notably, the pattern is consistent across columns relative to the first source memory address associated with each column. A driver then executes copy operations that store the offset sequence in the parallel processing memory. The convolution engine divides the virtual image matrix into separate image tiles and then assigns the processing of each image tile to a different thread group.

0108For each thread group, the threads included in each thread group collaboratively calculate start addresses, where each start address corresponds to the first source address associated with a column that is represented in the assigned image tile. Subsequently, to populate the image tile, the threads indirectly access the appropriate image data included in the image batch stored in parallel processing memory based on the start addresses and the offset sequence. The threads then perform matrix multiplication operations between the image tile and a corresponding filter tile to generate partial results for the output matrix. Notably, as each thread processes assigned image tiles, the thread steps through the offset sequence. After the thread groups have finished processing all the image tiles, the convolution engine configures the threads to copy the data included in the output matrix to an output batch.

0109At least one advantage of the disclosed approach is that the convolution subsystem fully exploits the benefits inherent in parallel processing systems to achieve the high accuracy provided by CNNs while optimizing execution speed and the amount of parallel processing memory used. More specifically, by configuring the CPU to precompute the offset sequence, the convolution engine decouples computationally-intensive addressing operations associated with populating the tiles of the virtual image matrix from the performance-critical matrix multiplication operations. Further, at any given only a portion of the virtual image matrix resides in shared memory and the entire image matrix is not stored in parallel processing memory. Consequently, the parallel processing pipeline realizes the benefits of an optimized matrix multiplication while minimizing the amount of parallel processing memory used.

0110The descriptions of the various embodiments have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments.

0111Aspects of the present embodiments may be embodied as a system, method or computer program product. Accordingly, aspects of the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present disclosure may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

0112Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

0113Aspects of the present disclosure are described above with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the disclosure. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, enable the implementation of the functions/acts specified in the flowchart and/or block diagram block or blocks. Such processors may be, without limitation, general purpose processors, special-purpose processors, application-specific processors, or field-programmable processors or gate arrays.

0114The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

0115While the preceding is directed to embodiments of the present disclosure, other and further embodiments of the disclosure may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.