# A Novel Low-Complexity and Parallel Algorithm for DCT IV Transform and Its GPU Implementation
## Appendix B  
In the following, the pseudocode of the implemented algorithm is presented. The implemented algorithm is the one with four sections running in parallel. The values for all matrices and vectors (e.g., A, B, C, cos1, cos2, XA1, XA2, XA3, XA4, XA5, and XA6) are those presented in relations (12), (15), (18) and (21).  
//main program  
main()  
N = 17;  
...  
//host system (CPU) vector declaration  
double in_cpu[N], out_cpu[N];  
//GPU system pointer declaration  
double in_gpu, out_gpu;  
//CUDA events declaration  
cudaEvent_t start, stop;  
//creates CUDA event objects  
cudaEventCreate (&start);  
cudaEventCreate (&stop);  
//allocate the memory on GPU: input data vector and output data vector  
cudaMalloc(&in_gpu, N * sizeof(double));  
cudaMalloc(&out_gpu, N * sizeof(double));  
in_cpu[] \(\LeftLeft\) generateNrandomValues()  
cudaEventRecord (start);  
//*start\" CUDA event recording  
//copy input data from CPU to GPU  
cudaMemcpy(in_gpu, in_cpu, N * sizeof(double), cudaMemcpyHostToDevice)  
//run kernels in paralleldctIV_pp <<<<4,1>>> (in_gpu, out_gpu);  
cudaEventRecord (stop); //\"stop\" CUDA event recording  
//copy DCT IV results from GPU to CPU  
cudaMemcpy (out_cpu, out_gpu, N * sizeof(double), cudaMemcpyDeviceToHost)  
//get and display the number of milliseconds time elapsed  
//between the recording of \"start\" and \"stop\" events  
cudaEventSynchronize(stop);  
milliseconds = 0;  
cudaEventElapsedTime (&milliseconds, start, stop);  
printf (\"Processing time on GPU--paral alg. executed paralel [ms] = %f\
\", milliseconds);  
...  
dctIV_pp (double *in, double *out)  
tid \(\Leftarrow\) getGlobalThreadIdentifier();  
myPI = 3.1415926; \(\mathrm{alfa}\) = myPI/(2*N);  
//initialization of vectors and matrices are according to relations (8)--(15)  
A, B, C, cos1, cos2, XA1, XA2, XA3, XA4, XA5, XA6 \(\Leftarrow\) initialization();  
for (i = 0; i < N; i++)  
Xc[i] = in[i] * cos ((2*I + 1)*alfa/2);  
Xa[N - 1] = Xc[N-1];  
for (i = N-2; i >= 0; i--)  
Xa[i] = Xc[i] - Xa[i + 1];  
If (tid == 0)  
tmp0_1 = A \(\times\) diag (C \(\times\) XA1) \(\times\) B \(\times\) cos2;  
tmp0_2 = A \(\times\) diag (C \(\times\) XA2) \(\times\) B \(\times\) cos1;  
\(\left[\begin{array}{c}T6\\ T14\\ T10\\ T12\end{array}\right]\) = tmp0_1 + tmp0_2 ;  
out [6] = 2 * (Xa[0] + T6) * cos (6* alfa);  
out [14] = 2 * (Xa[0] + T14) * cos (14* alfa);  
out [10] = 2 * (Xa[0] + T10) * cos (10* alfa);  
out [12] = 2 * (Xa[0] + T12) * cos (12* alfa);  
If (tid == 1)  
tmp1_1 = A \(\times\) diag (C \(\times\) XA1) \(\times\) B \(\times\) cos1;  
tmp1_2 = A \(\times\) diag (C \(\times\) XA3) \(\times\) B \(\times\) cos2;  
\(\left[\begin{array}{c}T16\\ T8\\ T4\\ T2\end{array}\right]\) = tmp1_1 + tmp1_2 ;  
out [16] = 2 * (Xa[0] + T16) * cos (16* alfa);  
out [8] = 2 * (Xa[0] + T8) * cos (8* alfa);  
out [4] = 2 * (Xa[0] + T4) * cos (4* alfa);  
out [2] = 2 * (Xa[0] + T2) * cos (2* alfa);  
If (tid == 2)  
tmp2_1 = A \(\times\) diag (C \(\times\) XA4) \(\times\) B \(\times\) cos2;  
tmp2_2 = A \(\times\) diag (C \(\times\) XA5) \(\times\) B \(\times\) cos1;\[\begin{bmatrix}T11\\ T3\\ T7\\ T5\end{bmatrix}=\text{tmp2\_1}+\text{tmp2\_2}\,;\]  
out [11] = 2 * (Xa[0] + T11) * cos (11 * alfa); out [3] = 2 * (Xa[0] + T3) * cos (3 * alfa); out [7] = 2 * (Xa[0] + T7) * cos (7 * alfa); out [5] = 2 * (Xa[0] + T5) * cos (5 * alfa); } If (tid == 3) { tmp3_1 = A \(\times\) diag (C \(\times\) XA4) \(\times\) B \(\times\) cos1; tmp3_2 = A \(\times\) diag (C \(\times\) XA6) \(\times\) B \(\times\) cos2; \(\begin{bmatrix}T1\\ T9\\ T13\\ T15\end{bmatrix}=\text{tmp3\_1}+\text{tmp3\_2}\,;\)  
out [1] = 2 * (Xa[0] + T1) * cos (1 * alfa); out [9] = 2 * (Xa[0] + T9) * cos (9 * alfa); out [13] = 2 * (Xa[0] + T13) * cos (13 * alfa); out [15] = 2 * (Xa[0] + T15) * cos (15 * alfa); } }