# A Novel Low-Complexity and Parallel Algorithm for DCT IV Transform and Its GPU Implementation
## 4 Implementation
### Program Implementation, Testing, and Analysis Approaches  
To highlight and analyze the algorithm's performance, introduced in this study, the parallel DCT versions (with four and eight sections) were implemented in the C language, and each section of the algorithm was executed on a different CUDA processor. At the end of this study, we will present a comparison with two other algorithms for parallel calculation of the DCT IV transform. All of these algorithms were implemented and tested on the same development systems as the novel algorithm, so a reference is necessary. Even in these conditions, where the testing is carried out under identical conditions for all algorithms, a correct comparative evaluation of these algorithms is difficult. For example, these algorithms use data sequences of 13 elements [21; 40], while our algorithm works on 17 values. For this reason, we will compare all of them with a reference algorithm that will work on the same number of elements, 13 and 17, and, in the end, the comparison will be made based on the speed improvements obtained by these algorithms as compared with the reference algorithm. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Volta** & **Ampere** \\ \hline Supported CUDA & INT8, FP16, & INT8, FP16, \\ core precisions & FP32, FP64 & Bfloat16, FP32, FP64 \\ \hline Supported Tensor & FP16 & INT1, INT4, INT8, FP16, \\ Core precisions & & Bfloat16, TF32, FP64 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Supported CUDA and Tensor Core precisions for all NVIDIA-used architectures. As a reference, the C implementation of the classical DCT-IV algorithm was used, given by the following relation [44]:  
\[X_{k}=\frac{2}{N}{\sum_{n=0}^{N-1}x_{n}cos\left[\frac{\pi}{N}\left(n+\frac{1}{2} \right)\left(k+\frac{1}{2}\right)\right]}\text{ for }k=0,\ldots,N-1 \tag{23}\]  
In the previous relation, the \(x_{n}\) sequence, composed of \(N\) real numbers, is transformed into another output sequence, \(X_{k}\), of real numbers with the same length as the input one through the DCT-IV transform. This classical implementation was also executed on a CUDA core when performances were analyzed. CUDA units can work with numbers in different representations, such as INT8, FP16, Bfloat16, FP32, or FP64, Table 3. This study presents almost all results on the double (FP64) data type only. This research mainly aims to show the performance improvements in the new algorithm compared to other algorithms implemented with the exact data representation and operating under similar conditions. When algorithms use data representation with fewer bits, they also achieve lower accuracy. This balance of execution speed/accuracy depends on the requirements of each practical application. To have a deeper understanding of the performance increase that can be achieved based on the use of a lower resolution, an analysis based on a Bfloat16 representation was also performed. Also, the DCT IV performance can be increased even more by using intrinsic-type trigonometric functions in the algorithm implementation. The intrinsic implementation for the trigonometric functions is faster but has domain restrictions and lower accuracy. The less accurate trigonometric functions are fine for some applications, but the intrinsic may not be sufficient for others. For this reason, we have avoided using these functions. In what follows, a measurement cycle involves (1) copying data from CPU to GPU, (2) the execution of a DCT IV transform (given by relation (1) or one of the novel DCT transform implementation proposed in this study--with 4 sections or with 8 sections), followed by (3) copying data from GPU to CPU. Appendix B depicts a short presentation of how the novel algorithm with four sections was implemented. Based on this cycle, one determination is the average value of 1000 sequential measurement cycles. For the statistical values of the performances obtained on each architecture supported by each development system, 30 such determinations were executed.