# US 8,751,771 B2 · Efficient implementation of arrays of structures on SIMT and SIMD architectures > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,771 B2 - Document ID: US8751771B2 - Status: Granted - Kind: B2 - Application number: 13/247,855 - Filed: 2011-09-28 - Published: 2012-04-12 - Granted: 2014-06-10 - Earliest claimed: 2010-09-29 - Assignees: NVIDIA Corporation - Applicants: Brian Fahs; Henry Packard Moreton; Brett W. Coon; Kathleen Elliott Nickolls - Inventors: Brian Fahs; John R. Nickolls; Henry Packard Moreton; Brett W. Coon - Web page: https://patentgrep.com/patent/US8751771B2 ## CPC - G06F 9/3885: {using a plurality of independent parallel functional units} - G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations} - G06F 9/3009: {Thread control instructions} - G06F 9/30123: {according to context, e.g. thread buffers} - G06F 9/345: of multiple operands or results {(addressing multiple banks G06F12/06)} - G06F 9/3824: {Operand accessing} - G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]} - G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel} - G06F 9/38885: {Divergence aspects} - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 12/0207: {with multidimensional access, e.g. row/column, matrix} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract One embodiment of the present invention sets forth a technique providing an optimized way to allocate and access memory across a plurality of thread/data lanes. Specifically, the device driver receives an instruction targeted to a memory set up as an array of structures of arrays. The device driver computes an address within the memory using information about the number of thread/data lanes and parameters from the instruction itself. The result is a memory allocation and access approach where the device driver properly computes the target address in the memory. Advantageously, processing efficiency is improved where memory in a parallel processing subsystem is internally stored and accessed as an array of structures of arrays, proportional to the SIMT/SIMD group width (the number of threads or lanes per execution group). ## Claims ### Claim 1 A computer-implemented method for accessing data in a data structure stored in a memory, the method comprising: receiving a memory access instruction that includes a base address of the data structure that corresponds to a first memory location within the memory; computing a first partial offset relative to the base address that is proportional to a position of a target structure of arrays within the data structure; computing a second partial offset by adding to the first partial offset a position of a target structure within the target structure of arrays; computing a third partial offset by adding to the second partial offset a position of a target field within the target structure; and accessing a location within the memory corresponding to the base address plus the third partial offset. ### Claim 2 (depends on 1) The method of claim 1, wherein the memory access instruction further includes a structure size associated with each structure in the target structure of arrays, a structure index, and a field offset, and computing the first partial offset comprises: performing an integer division operation that divides the structure index by a number of thread/data lanes associated with a processing core coupled to the memory to produce a first intermediate value; multiplying the first intermediate by the structure size to produce a second intermediate value; and multiplying the second intermediate value by the number of thread/data lanes to produce the first partial offset. ### Claim 3 (depends on 2) The method of claim 2, wherein computing the second partial offset comprises multiplying a remainder value produced from the integer division operation by a field size associated with each structure within the target structure of arrays. ### Claim 4 (depends on 3) The method of claim 3, wherein computing the third partial offset comprises multiplying the field offset by the number of thread/data lanes. ### Claim 5 (depends on 1) The method of claim 1, wherein the structure size associated with each structure in the target structure of arrays is increased based on a memory access byte granularity associated with the memory. ### Claim 6 (depends on 1) The method of claim 1, wherein the target structure of arrays includes a first number of structures in each row and a second number of structure in each column, and further comprising: allocating space in the memory corresponding to a first data field for every structure in a first row of the target structure of arrays; and allocating space in the memory corresponding to a second data field for every structure in a second row of the target structure of arrays. ### Claim 7 (depends on 6) The method of claim 6, wherein a second target structure of arrays includes the first number of structures in each row and the second number of structures in each column, and further comprising: allocating space in the memory corresponding to the first data field for every structure in a first row of the second target structure of arrays; and allocating space in the memory corresponding to the second data field for every structure in a second row of the second target structure of arrays. ### Claim 8 (depends on 1) The method of claim 1, wherein the number of thread/data lanes is a power of two. ### Claim 9 A computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to access data in a data structure stored in a memory, by performing the steps of: receiving a memory access instruction that includes a base address of the data structure that corresponds to a first memory location within the memory; computing a first partial offset relative to the base address that is proportional to a position of a target structure of arrays within the data structure; computing a second partial offset by adding to the first partial offset a position of a target structure within the target structure of arrays; computing a third partial offset by adding to the second partial offset a position of a target field within the target structure; and accessing a location within the memory corresponding to the base address plus the third partial offset. ### Claim 10 (depends on 9) The computer readable medium of claim 9, wherein the memory access instruction further includes a structure size associated with each structure in the target structure of arrays, a structure index, and a field offset, and computing the first partial offset comprises: performing an integer division operation that divides the structure index by a number of thread/data lanes associated with a processing core coupled to the memory to produce a first intermediate value; multiplying the first intermediate by the structure size to produce a second intermediate value; and multiplying the second intermediate value by the number of thread/data lanes to produce the first partial offset. ### Claim 11 (depends on 10) The computer readable medium of claim 10, wherein computing the second partial offset comprises multiplying a remainder value produced from the integer division operation by a field size associated with each structure within the target structure of arrays. ### Claim 12 (depends on 11) The computer readable medium of claim 11, wherein computing the third partial offset comprises multiplying the field offset by the number of thread/data lanes. ### Claim 13 (depends on 9) The computer readable medium of claim 9, wherein the structure size associated with each structure in the target structure of arrays is increased based on a memory access byte granularity associated with the memory. ### Claim 14 (depends on 9) The computer readable medium of claim 9, wherein the target structure of arrays includes a first number of structures in each row and a second number of structure in each column, and further comprising: allocating space in the memory corresponding to a first data field for every structure in a first row of the target structure of arrays; and allocating space in the memory corresponding to a second data field for every structure in a second row of the target structure of arrays. ### Claim 15 (depends on 14) The computer readable medium of claim 14, wherein a second target structure of arrays includes the first number of structures in each row and the second number of structures in each column, and further comprising: allocating space in the memory corresponding to the first data field for every structure in a first row of the second target structure of arrays; and allocating space in the memory corresponding to the second data field for every structure in a second row of the second target structure of arrays. ### Claim 16 (depends on 9) The computer readable medium of claim 9, wherein the number of thread/data lanes is a power of two. ### Claim 17 A computing device comprising: a processing unit; a first memory coupled to the processing unit and storing a software driver that is configured to allow data stored in a data structure in a second memory to be accessed by: receiving a memory access instruction that includes a base address of the data structure that corresponds to a first memory location within the memory; computing a first partial offset relative to the base address that is proportional to a position of a target structure of arrays within the data structure; computing a second partial offset by adding to the first partial offset a position of a target structure within the target structure of arrays; computing a third partial offset by adding to the second partial offset a position of a target field within the target structure; and accessing a location within the memory corresponding to the base address plus the third partial offset. ### Claim 18 (depends on 17) The method of claim 17, wherein the structure size associated with each structure in the target structure of arrays is increased based on a memory access byte granularity associated with the memory. ### Claim 19 (depends on 17) The computing device of claim 17 wherein the target structure of arrays includes a first number of structures in each row and a second number of structure in each column, and further comprising: allocating space in the memory corresponding to a first data field for every structure in a first row of the target structure of arrays; and allocating space in the memory corresponding to a second data field for every structure in a second row of the target structure of arrays. ### Claim 20 (depends on 19) The computing device of claim 19 wherein a second target structure of arrays includes the first number of structures in each row and the second number of structures in each column, and further comprising: allocating space in the memory corresponding to the first data field for every structure in a first row of the second target structure of arrays; and allocating space in the memory corresponding to the second data field for every structure in a second row of the second target structure of arrays.