-The issue of creating high-performance computing systems based on heterogeneous computer systems is topical, since the volumes of processed information, calculations and studies with large data sets are constantly increasing. The aim of the work is an experimental study of previously developed models for predicting the performance of heterogeneous computer systems in telecommunications. As a result, the study showed that the developed models allow us to obtain an adequate estimate of the possible time of the algorithm for various parameters of the GPU with some limitations.
INTRODUCTION
One of the most dynamically developing areas in parallel programming at the moment is the use of computer systems with a heterogeneous architecture, in which there are computing devices with different architectures and, accordingly, with different methods of using parallel computing. The most common approach in the design of such systems was the use of graphic video cards or devices based on them as the main parallel calculator. This growing need for solving big problems stimulates research and innovation in the field of parallel computing in general and in the development of methods for graphic processors in particular.
II. RESEARCH AND DEVELOPMENT OF MODELS OF HETEROGENEOUS COMPUTING SYSTEMS BASED ON GRAPHICS
PROCESSORS
Modern graphic processors (GPUs) are parallel processors. More precisely, they are known as stream processors because they are capable of performing various functions in the incoming data stream. They represent advanced architectures that are designed for parallel processing of data (primarily graphic). They are currently extremely powerful programmable processors, MIMD architecture capabilities with some limitations.
As technology, languages, and hardware evolved,
researchers were able to leverage the added flexibility of
GPUs when deploying non-graphical applications to the GPU
(GPGPU), especially when processing images. A more
detailed history of the development of GPGPU is presented in
[
A further development momentum was the emergence of CUDA, the NVIDIA C-based development environment for GPGPUs. CUDA allows developers unfamiliar with graphical programming to write code that can be executed on the GPU. CUDA provides the necessary abstractions for the developer to write multi-threaded programs with little or no knowledge of the graphics APIs. Since then, many implementations of parallelized applications have been developed for GPUs, Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) many of which offer significant acceleration compared to sequential implementations on the processor.
A model of the upper bound for the running time of an
algorithm on a graphics processor in a CPU-GPU environment
is presented in [
T GPU ( N )
N HD ( N )
S HD
B ( N ) T i G ( N ) i 1
N DH ( N )
S DH
This model does not account for certain features of the
graphics processor, such as the size of a warp-to GPU memory
access time, etc., however, the GPGPU performance
prediction model, which is a combination of known parallel
computing models, was given in [
T ( K )
N B ( K ) N w ( K ) N t ( K ) C T ( K )
N C D R All parameters of this model are shown in table 1.
THE LIST OF DEVELOPED MODEL PARAMETERS Parameter
D Nc
R Ct(K)
Description
The kernel pipeline depth The number of cores per SM
GPU Clock The maximum number of ticks consumed by
any thread in the kernel K Number of threads in warp = 32 The number of warps per block The number of blocks per kernel i-th kernel on the GPU Time spent by kernel K
Time spent by program P
The performance of the CUDA kernel can vary greatly
with slight changes depending on memory access strategies.
Using shared memory can provide up to 20 times better
performance than using global memory, and using shared
global memory access can lead to 5 times better performance
compared to non-coalesced access. Arithmetic operations also
require a different number of cycles to perform, for example,
operations such as integer summation require 4 cycles, while
calculating an integer module takes 48 cycles [
USING GPU MEMORY ACCESS PATTERNS TO IMPROVE HETEROGENEOUS COMPUTING SYSTEM PERFORMANCE Since the access delay when reading data from the global memory of the GPU is up to 200 times higher, than reading data from the registers, providing the most efficient way to access the GPU RAM is crucial to improve the performance of the GPU in particular and the heterogeneous system as a whole. Therefore, optimizing global memory access is becoming the single most important programming factor for the GPGPU architecture.
The GPU global memory reads and writes data in half warp threads (16 threads), which are optimized by the device in just one global memory transaction if certain access requirements are met. For the GTX 280 video card, the following protocol is used to determine the number of transactions used by the halfwarp:
1) Implemented search memory segment, which contains the address inquiry from the active thread with the lowest number. The segment size is 32 bytes for 8-bit data, 64 bytes for 16-bit data, and 128 bytes for 32-, 64- and 128-bit data.
a) if the transaction size is 128 bytes and only the upper or lower half of the segment is used, the transaction size is reduced to 64 bytes;
b) if the transaction size is 64 bytes and only the lower or upper half is used, the transaction size is reduced to 32 bytes.
2) A transaction is in progress, serviced threads are marked as inactive.
3) Repeated until all threads in the halfwarp are serviced.
When more than one thread requests data from addresses, that fall into the same segment, one transaction can satisfy all such threads. This service of multiple requests in a single transaction is called coalescing. Thus, it is obvious that certain GPU memory access patterns will necessarily have a positive effect, while others will gradually increase the delay as the memory addresses requested by the halfwarp threads diverge.
The shared memory of the GPU is divided into memory modules of the same size, called banks, which can be accessed simultaneously by several threads. Thus, any request to read or write to the memory, consisting of n addresses, that fall into n separate memory banks, can be carried out simultaneously, which gives an effective throughput that is n times higher than the throughput of one module. However, if two memory request addresses fall into the same memory bank, a bank conflict occurs and access must be serialized. The GPU divides memory access requests with bank conflicts into as many individual requests without conflicts as necessary, reducing the effective bandwidth by a factor equal to the number of individual memory requests. For GTX280, the size of the warp is 32, and the number of banks is 16. Access to shared memory for warp is divided into one request for the first half of warp and one request for the second half of warp. As a result, there can be no conflict of the bank between a thread belonging to the first half of the warp and a thread belonging to the second half of the same warp.
Shared memory also has a broadcast mechanism that allows you to read a 32-bit word and broadcast it to multiple threads at the same time with one transaction to read from memory. This reduces the number of conflicts in the bank when several threads of the halfwarp are read from the address within the same 32-bit word. More precisely, a memory read request made to several addresses are served in several stages over time – one step every two cycles, serving one conflictfree subset of these addresses per step, until all addresses are served. At each step, a subset is constructed from the remaining addresses that have yet to be served using the following procedure:
1) Select one of the words indicated by the remaining addresses as the translated word.
2) Include in a subset: a) all addresses that are within the broadcast word; b) one address for each bank indicated in the remaining addresses.
The space of constant memory is cached, so reading from constant memory is delayed as in the case of reading from global memory only if there is no cache, otherwise a transaction from constant cache is performed. For all threads, halfwarp reads from the constant cache as fast as reads from registers if all threads read the same address. Access time scales linearly depending on the number of different addresses read by all threads.
Texture memory allows to cache data present in global memory. If a cached item is requested, then it is served in a single request. The lack of a cache results in a global memory read operation, which takes much longer.
To compare the access time to different types of memory, 1,000,000 read operations from each type of memory were performed. Access was performed both sequentially and randomly. Tests were performed using the NVIDIA GTX280 GPU. The results are presented in Table 2. As you can see, shared memory provides the best performance, followed by a constant cache, and then a texture cache. Global memory shows the highest latency.
For most parallel computing platforms, modeling memory access patterns and their associated costs is the most complex and most important part. The following algorithm is used to experimentally verify statements about the process of accessing memory on the GPU:
Algorithm 1 Global Memory Access Benchmark
Input data: number of elements N, step stride, offset offset, array A in global memory.
1: Calculate the number of elements in the thread, Nthread;
2: Calculate the data range of this thread, using stride and offset; model presented above adequately describes the performance of GPGPU.
Using the above algorithm, the experiment was simulated, that shows how much gain from sharing depends on the number of threads in the warp. This is controlled by the stride variable. Stride denotes the gap between elements, that are accessed sequentially by a single thread. Consequently, threads in halfwarp can take advantage of coalesced access, if the stride value is large. For example, when stride = 32, each warp thread receives consecutive elements, which ensures complete union. When stride is 1, each thread reads one element that is offset by 32, so they are not completely merged and require 16 memory transactions that will be serviced for halfwarp. To ensure a fair comparison, in the above code the number of hits on the stream does not depend on stride.
In the code shown in algorithm 1, the number of
calculations per iteration is very small compared to the
memory access delay for stride = 1. However, as the stride
value increases, memory access and calculations take
approximately the same number of clock cycles. Using the
MAX model, we can assume the runtime of this kernel and
compare it with the actual one in Figure 1. The program
execution graph is shown for various stride values. It should
be noted that the basic access code only for memory, that is,
with a small number of calculations, differs from the model,
due to limited information about the hardware [
EXPERIMENTAL VERIFICATION OF THE IMPACT OF ACCESS CONFLICTS WHEN USING SHARED MEMORY
In this experiment, while maintaining the general structure of global memory accesses, as in the previous experiment, each thread writes an element to the shared memory. The shared memory access pattern is controlled by the bank variable, which can be set to a value from 0 to 16. With a larger bank value, we can thus increase the number of access conflicts.
Algorithm 2 Shared Memory Access Benchmark
Input data: number of elements N, step stride, offset offset, control variable bank, array A in global memory, array B in shared memory.
1: Calculate the number of elements in the thread, Nthread; 2: Calculate the data range of this thread, using stride and offset; 3: while index is in the range do
for i = 0 to 10000 do 4: 5: 6: 7:
end for
B [IDthread × bank (mod sizeblock)];
The kernel in this algorithm has about 16 cycles of
calculation per iteration, and there are 64,000 iterations. The
number of clock cycles required to access the memory is about
bank × 4 per iteration [
As can be seen from Figure 1, the value of stride significantly affects the execution time of the algorithm. Because the amount of operations of the actual calculations in the algorithm is very small, then from the graph you can see that to increase the performance of the parallel algorithm it is necessary to read the array elements located at a distance from each other by no less than the value of warp to take advantage of the combined access to memory. It can also be seen from Figure 1 that although the graph of the predicted lead time does not coincide with the graph of the actual time, it also allows the predicted lead time to obtain enough information about the decrease in performance while decreasing the distance between the read elements. This suggests that the
As can be seen from Figure 2, there is a linear dependence
of the number of conflicts on the execution time of the
program. Thus, to increase the performance of parallel
algorithms, it is necessary to exclude the intersection of the
read data for different threads [
CONCLUSIONS
This paper presents an experimental study of previously developed models for predicting the performance of a heterogeneous computer system in telecommunications. The study showed that the developed models allow us to obtain an adequate estimate of the possible time of the algorithm for various parameters of the GPU. However, it is worth noting that the estimate obtained using the developed models is not accurate, because average access time is used for all levels of the memory hierarchy. In the future, it is planned to finalize the models taking into account the use of the amount of memory access time, obeying a rank distribution, for example, Pareto or Zipf.
ACKNOWLEDGMENT
The work was carried out under a grant from the president of the Russian Federation for state support of young Russian scientists № МК-2378.2020.9.