Efficient implementation of arrays of structures on SIMT and SIMD architectures
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).
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.
2. 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.
3. 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.
4. The method of claim 3 , wherein computing the third partial offset comprises multiplying the field offset by the number of thread/data lanes.
5. 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.
6. 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.
7. 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.
8. The method of claim 1 , wherein the number of thread/data lanes is a power of two.
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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. The computer readable medium of claim 9 , wherein the number of thread/data lanes is a power of two.
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.
18. 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.
19. 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.
20. 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.