Allocating device buffer on GPGPU for an object with metadata using access boundary alignment

A method is provided for buffer allocation on a graphics processing unit. The method includes analyzing, by the graphics processing unit, a program to be executed on the graphics processing unit to determine, for an object in the program, a set of elements in the object that are designated to be accessed during an execution of the program. The method further includes allocating, by the graphics processing unit, a placement of the object in a device buffer on the graphics processing unit based on the set of elements to minimize a number of memory accesses during the execution of the program.

BACKGROUND

Technical Field

The present invention relates generally to graphics processing and, in particular, to allocating a device buffer on a General Purpose Graphics Processing Unit (GPGPU) for an object with metadata using access boundary alignment.

Description of the Related Art

An object for languages running on a managed runtime (e.g. Java®/Python/Ruby) has metadata that is used for efficient implementation of language features. For example, in the implementation of IBM® Java® for 64-bit platforms, an array object for a primitive type (e.g. int) has a 16-byte header that includes its array length. The array length is used for checking array index bound exceptions.

It is important to reduce the number of accesses from/to L2 cache/global memory to achieve high performance on a General Purpose Graphics Processing Unit (GPGPU). The access from/to global memory takes several hundred cycles. One approach to reduce the number of accesses is to align a starting address of memory accesses within a warp with a memory transaction boundary (e.g. 128-byte granularity). However, such an alignment still does not result in an efficient solution as described below.

That is, an object with metadata is copied from the host processor to a GPU so that a program written in the language running on the managed runtime can be executed while following its language specification. At that time, its execution time may be slower since an unappropriated memory allocation of the object increases the number of memory transactions. For example, in the implementation of IBM® Java® for 64-bit platforms, when a float array is transferred from the host to the GPU using an alignment with a 128-byte boundary, offset 0-15 is used for metadata. In this case, when load instructions in a warp of the program read data from elements 0 to 31 of the array, these loads perform accesses at offset 16 to 143. These accesses are coalesced into two memory transactions. One memory transaction is for offset 0-127. The other memory transaction is for offset 128-255. While we expected one transaction for one 128-byte memory access, it is slower than what we expected.

Thus, there is a need to allocate a device buffer on a GPU for an object with metadata using better access boundary alignment.

SUMMARY

According to an aspect of the present principles, a method is provided for buffer allocation on a graphics processing unit. The method includes analyzing, by the graphics processing unit, a program to be executed on the graphics processing unit to determine, for an object in the program, a set of elements in the object that are designated to be accessed during an execution of the program. The method further includes allocating, by the graphics processing unit, a placement of the object in a device buffer on the graphics processing unit based on the set of elements to minimize a number of memory accesses during the execution of the program.

According to another aspect of the present principles, a computer program product is provided for device buffer allocation on a graphics processing unit. The computer program product includes a non-transitory computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a computer to cause the computer to perform a method. The method includes analyzing, by the graphics processing unit, a program to be executed on the graphics processing unit to determine, for an object in the program, a set of elements in the object that are designated to be accessed during an execution of the program. The method further includes allocating, by the graphics processing unit, a placement of the object in a device buffer on the graphics processing unit based on the set of elements to minimize a number of memory accesses during the execution of the program.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

The present principles are directed to allocating a device buffer on a General Purpose Graphics Processing Unit (GPGPU) for an object with metadata using access boundary alignment. The present principles advantageously reduce the number of accesses from/to L2 cache/global memory to achieve a high performance on the GPGPU.

FIG. 1shows an exemplary processing system100to which the present principles may be applied, in accordance with an embodiment of the present principles. The processing system100includes at least one processor (CPU)104and a GPGPU103operatively coupled to other components via a system bus102. A cache106, a Read Only Memory (ROM)108, a Random Access Memory (RAM)110, an input/output (I/O) adapter120, a sound adapter130, a network adapter140, a user interface adapter150, and a display adapter160, are operatively coupled to the system bus102. While cache106is intended to represent an off-chip cache, CPU104can have one or more on-chip caches (e.g., L1, L2, etc., collectively denoted by the reference numeral104A). Moreover, GPGPU103includes at least one buffer103A.

Further, it is to be appreciated that processing system100may perform at least part of the method described herein including, for example, at least part of method300ofFIGS. 2-3.

FIGS. 2-3show an exemplary method300for allocating a device buffer on a General Purpose Graphics Processing Unit (GPGPU) for an object with metadata using access boundary alignment, in accordance with an embodiment of the present principles. Advantageously, method300reduces the number of access from/to L2 cache/global memory to achieve high performance on the GPGPU. The method300can be considered to include a first portion301that relates to allocating a buffer on the GPGPU and a second portion351that relates to accessing the metadata of the object once the buffer has been allocated by the first portion301. The first portion301includes steps310,320, and330. In an embodiment, the first portion can further include step340. The second portion351includes steps350,360, and370.

At step310, analyze a program to be executed on the GPGPU to determine, for a given object in the program:

R: a set of elements in the object to be read;

W: a set of elements in the object to be written;

Mr: the number of read accesses to metadata of the object; and

Mw: the number of write accesses to metadata of the object.

At step320, identify access patterns of the object without metadata. This step refers to identifying accesses to elements in the object other than metadata. In an embodiment, step320includes step320A.

At step320A, calculate the following:
G=R∪W,
where G denotes the set of all elements in the object to be read or written, and ∪ denotes a union function applied to set R and set W.

At step330, identify a placement of the object on GPU memory (e.g., a particular location in a buffer from among a set of possible (available) locations and/or a particular buffer from among a set of possible (available) buffers) that reduces the number of global memory accesses and place the object accordingly. In an embodiment, step330involves steps330A-D.

At step330A, calculate the lowest address in G.

At step330B, calculate a starting address S (which, in an embodiment, can simply be the next available address in the memory) of the buffer on GPU memory, which can include metadata and (all) other parts (elements) of the object, and allocate a buffer on the GPGPU memory for the object by aligning the lowest address in G with a memory transaction boundary imposed on the buffer. The memory transaction boundary can be, for example, but is not limited to, 128. Thus, a region with the starting address S includes the entirety of the object starting therefrom, that is, the metadata parts and the non-metadata parts, where the non-metadata parts include sets R and W and as well as any elements that are not to be read or written during the execution of the program that includes the object therein).

At step330C, calculate an offset O, as follows:
offsetO=(starting address of the object on GPU)−S.

At step330D, copy metadata and elements in G of the object from a host processor to the GPU.

At step340, generate load and store instructions using S for the object with the offset O.

At step350, determine if Mr>0 and Mw=0. If so, then the method proceeds to step360. Otherwise, the method proceeds to step370.

At step360, generate load instructions for loading the metadata of the object through a read-only cache. Then, the method for code generation is terminated.

At step370, generate load instructions for loading the metadata of the object without a read-only cache. Then, the method is terminated.

FIG. 4shows an exemplary application400of the present principles, in accordance with an embodiment of the present principles.

In the exemplary application400, a source program410is analyzed according to method300. The source program410includes an object a[ ] and an object b[ ].

The allocated device buffers for object a[ ] and object b[ ] using method300are411and412, respectively. For object a[ ], addresses 0-127 includes the object header for object a[ ], with the Java array body of a[ ] starting at address 128. For object b[ ], addresses 10240-10367 include the object header for object b[ ], with the Java array body of b[ ] starting at 10368.

FIG. 5shows another exemplary application500of the present principles, in accordance with an embodiment of the present principles.

In the exemplary application500, the source program410(the same one fromFIG. 4) is further analyzed according to method300. Pseudocode520is then generated for accessing b. length, as shown in source program410, using method300. The pseudocode520includes a portion520A for loading the array length through a read-only cache, and a portion520B that forms a bound check. Further regarding the bound check, the following applies:

Set true to P1 if R8>=R6. If P1 is true, “BRA 0x4d0” is executed. Thus, a process for array bound exception will be executed.

While the exemplary application500generates pseudocode520for accessing b. length, it is to be appreciated that the present principles can be applied so as to generate pseudocode for accessing a length. These and other variations in applying the present principles are readily determined by one of ordinary skill in the art, given the teachings of the present principles provided herein, while maintaining the spirit of the present principles.

It is to be appreciated that the present principles provide a significant reduction in execution time. For example, when we built a binary for the matrix multiplication program by using a Java® Just-In-Time compiler with Method1and measured the execution time of GPU code on NVIDIA K40m, we measured reduction of execution time by 32.9%