Computing 2-body statistics on graphics processing units (GPUs)
Disclosed are various embodiments for computing 2-body statistics on graphics processing units (GPUs). Various types of two-body statistics (2-BS) are regarded as essential components of data analysis in many scientific and computing domains. However, the quadratic complexity of these computations hinders timely processing of data. According, various embodiments of the present disclosure involve parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). Although the typical 2-BS problems can be summarized into a straightforward parallel computing pattern, traditional wisdom from (general) parallel computing often falls short in delivering the best possible performance. Therefore, various embodiments of the present disclosure involve techniques to decompose 2-BS problems and methods for effective use of computing resources on GPUs. We also develop analytical models that guide users towards the appropriate parameters of a GPU program. Although 2-BS problems share the same core computations, each 2-BS problem however carries its own characteristics that calls for different strategies in code optimization. Accordingly, various embodiments of the present disclosure involve a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code input.
1. A system for solving two-body statistics (2-BS) problems with a graphics processing unit (GPU), comprising:
a main memory and the GPU;
machine readable instructions stored in the main memory that, when executed by the GPU, cause the system to at least:
load a first input data block from the main memory into a first cache region of the GPU, the first input data block comprising a first array of values;
load a second input data block from the main memory into a second cache region of the GPU, the second input data block comprising a second array of values;
compute a first distance function between each value in the first data block and each value in the second data block;
load a third input data block from the main memory into a third cache region, the third input block comprising a third array of values; and
concurrently compute:
the first distance function between each value in the first data block and each value in the second data block;
a second distance function between each value in the first data block and each value in the third data block;
allocate a buffer in the memory;
divide the buffer into a plurality of pages;
assign a first one of the plurality of pages to a first thread that computes the first distance function;
assign a second one of the plurality of pages to a second thread that computes the second distance function;
initialize a global pointer that references a position of the first available page of the plurality of pages;
in response to the first thread filling the first one of the plurality of pages with output from the first distance function or in response to the second thread filling the second one of the plurality of pages with output from the second distance function, assign the first available page to a respective one of the first thread or the second thread; and
update the global pointer to reference a position of the second available page of the plurality of pages.
2. The system of claim 1 , wherein the machine readable instructions the compute first the distance function between each value in the first data block and each value in the second data block further cause the system to at least:
load a value from the first array of values into a register of the GPU; and
compute first distance function between the value in the register of the GPU and each value in the second data block.
3. The system of claim 1 , wherein the first distance function is provided as an input to the machine readable instructions.
4. The system of claim 1 , wherein the first input data block is selected from a first data set and the second input data block is selected from a second data set.
5. A method for solving two-body statistics (2-BS) problems with a graphics processing unit (GPU), comprising:
loading a first input data block from the main memory into a first cache region of the GPU, the first input data block comprising a first array of values;
loading a second input data block from the main memory into a second cache region of the GPU, the second input data block comprising a second array of values;
computing a first distance function between each value in the first data block and each value in the second data block,
loading a third input data block from the main memory into a third cache region, the third input block comprising a third array of values;
concurrently computing:
the first distance function between each value in the first data block and each value in the second data block;
a second distance function between each value in the first data block and each value in the third data block;
allocating a buffer in the memory;
dividing the buffer into a plurality of pages;
assigning a first one of the plurality of pages to a first thread that computes the first distance function;
assigning a second one of the plurality of pages to a second thread that computes the second distance function;
initializing a global pointer that references a position of the first available page of the plurality of pages;
in response to the first thread filling the first one of the plurality of pages with output from the first distance function or in response to the second thread filling the second one of the plurality of pages with output from the second distance function, assigning the first available page to a respective one of the first thread or the second thread; and
updating the global pointer to reference a position of the second available page of the plurality of pages.
6. The method of claim 5 , wherein computing the first distance function between each value in the first data block and each value in the second data block further comprises:
loading a value from the first array of values into a register of the GPU; and
computing the distance function between the value in the register of the GPU and each value in the second data block.
7. The method of claim 5 , further comprising receiving the first distance function as an input provided by a user.
8. The method of claim 5 , wherein the first input data block is selected from a first data set and the second input data block is selected from a second data set.
9. A non-transitory, computer-readable medium comprising a machine-readable instructions that, when executed by a processor of a computing device, cause the computing device to at least:
load a first input data block from the main memory into a first cache region of a Graphics Processing Unit (GPU), the first input data block comprising a first array of values;
load a second input data block from the main memory into a second cache region of the GPU, the second input data block comprising a second array of values;
compute a first distance function between each value in the first data block and each value in the second data block,
load a third input data block from the main memory into a third cache region, the third input block comprising a third array of values;
concurrently compute:
the first distance function between each value in the first data block and each value in the second data block;
a second distance function between each value in the first data block and each value in the third data block allocate a buffer in the memory;
divide the buffer into a plurality of pages;
assign a first one of the plurality of pages to a first thread that computes the first distance function;
assign a second one of the plurality of pages to a second thread that computes the second distance function;
initialize a global pointer that references a position of the first available page of the plurality of pages;
in response to the first thread filling the first one of the plurality of pages with output from the first distance function or in response to the second thread filling the second one of the plurality of pages with output from the second distance function, assign the first available page to a respective one of the first thread or the second thread; and
update the global pointer to reference a position of the second available page of the plurality of pages.
10. The non-transitory, computer-readable medium of claim 9 , wherein the machine-readable instructions that cause the computing device to compute the first distance function between each value in the first data block and each value in the second data block further cause the computing device to at least:
load a value from the first array of values into a register of the GPU; and
compute the first distance function between the value in the register of the GPU and each value in the second data block.
11. The non-transitory, computer-readable medium of claim 9 , wherein the machine-readable instructions further cause the computing device to receive the first distance function as an input provided by a user.
12. The non-transitory, computer-readable medium of claim 9 , wherein the first input data block is selected from a first data set and the second input data block is selected from a second data set.