Performance Prediction Model and Analysis for
Compute-Intensive Tasks on GPUs

Khondker S. Hasan, Amlan Chatterjee, Sridhar Radhakrishnan, John K.

Antonio

► To cite this version:

Khondker S. Hasan, Amlan Chatterjee, Sridhar Radhakrishnan, John K. Antonio. Performance Pre-diction Model and Analysis for Compute-Intensive Tasks on GPUs. 11th IFIP International Confer-ence on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. pp.612-617, 10.1007/978-3-662-44917-2_65 . hal-01403164

HAL Id: hal-01403164

https://inria.hal.science/hal-01403164

Submitted on 25 Nov 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Performance Prediction Model and Analysis for Compute-intensive Tasks on GPUs

Khondker S. Hasan¹, Amlan Chatterjee¹, Sridhar Radhakrishnan¹, and John K. Antonio¹

¹School of Computer Science
University of Oklahoma
110 W. Boyd St., Norman
OK 73019, USA
{shajadul, amlan, sridhar, antonio}@ou.edu

**Abstract.** Using Graphics Processing Units (GPUs) to solve general purpose problems has received significant attention both in academia and industry. Harnessing the power of these devices however requires knowledge of the underlying architecture and the programming model. In this paper, we develop analytical models to predict the performance of GPUs for computationally intensive tasks. Our models are based on varying the relevant parameters - including total number of threads, number of blocks, and number of streaming multi-processors - and predicting the performance of a program for a specified instance of these parameters. The approach can be used in the context of heterogeneous environments where distinct types of GPU devices with different hardware configurations are employed.

**Keywords:** Compute-Intense Kernels; CUDA; GPU; Modeling and prediction

## 1 Introduction

The availability of GPUs as commodity hardware and co-processors to CPUs, and the relative low cost-to-performance ratio has propelled these devices to the forefront or research in both academia and the industry. Compute Unified Device Architecture (CUDA), an extension to the C programming language, allows general-purpose problems to be solved using Nvidia GPUs. However, this paradigm shift has left developers striving for better performance from the available hardware. The general trend has been focusing on transferring compute intensive portions of tasks to the GPUs and exploiting parallelism in the existing code. Therefore, most of the research and studies relevant to GPUs focus on transferring the data from the CPU to the GPU and back, designing efficient data structures for the GPU, and utilizing available primitives to decrease memory latency [2, 4]. In reality, to exploit the full potential of these devices,
understanding the underlying architecture and the basics of the programming model are required.

In this paper, we focus our research on optimally using the device at hand. We concentrate on deriving analytical models that can predict the *execution efficiency* of GPU programs i.e., GPU *kernels* based on certain parameters like the total number of resident blocks, number of threads in each block, the total number of blocks spawned in the device, the total number of streaming multi-processors available in the device, and others. The importance of our models are in the fact that it will help developers to unleash the full potential of the available hardware by predicting execution efficiency of thread blocks before placing them in the GPU run queue and also by providing suggestions to improve the efficiency by making arrangements for optimal execution time. The benchmark programs used for empirical analysis of our analytical model are professionally developed programs from the Nvidia CUDA GPU Computing SDK [8] for demonstrating the reliability and accuracy of our proposed model. The benchmark programs are tested in both Tesla C1060 and Kepler 20 devices, respectively and achieved very low prediction error with an error bound of 0.13-5.69%.

## 2 Analytical Models

An analytical framework for estimating the overall execution efficiency for batches of thread blocks is derived for GPU systems. The introduced prediction model incorporates the following three major observed categories while GPU executes several blocks of threads:

- When the number of blocks to be executed is more than the aggregate number of resident blocks for the GPU.

- When the number of warps to be executed is more than the aggregate number of resident warps for the GPU.

- When the total number of threads to be executed is more than the aggregate number of resident threads for the GPU.

Table 1 contains the notation and definitions of required parameters of the model. The execution time is ideal, denoted by $\tau$, when the number of blocks and threads in each block is less than the aggregate resident blocks and threads for the GPU (this number varies by GPU architecture). The following model incorporates the effect for the case when the number of thread blocks spawned for execution is more than the aggregate resident blocks for all multi-core processors of the GPU; for measuring the execution time ($\xi_{rb}$):

$$ \xi_{rb} = \begin{cases} \tau & \text{if } \beta \le (\rho_b \times \rho_{sm}), \\ \text{Max} \left( 1, \left[ \frac{\beta}{\rho_b \times \rho_{sm}} \right] \right) \times \tau & \text{else} \end{cases} \quad (1) $$

A higher occupancy reduces processor idle time (SM may stall due to unavailability of data or busy functional units) and improves overall performance [9], [10].
<table><caption>**Table 1.** Terms and definitions of GPU efficiency prediction model parameters.</caption><thead><tr><td>Terms</td><td>Definition</td></tr></thead><tbody><tr><td>ρ<sub>sm</sub></td><td>Number of Streaming Multi-core processors (SM) in the device.</td></tr><tr><td>ρ<sub>w</sub></td><td>Maximum number of resident warps in a streaming multi-core processor.</td></tr><tr><td>ρ<sub>b</sub></td><td>Maximum number of resident blocks in a streaming multi-core processor.</td></tr><tr><td>ρ<sub>t</sub></td><td>Maximum number of resident threads in a streaming multi-core processor.</td></tr><tr><td>σ<sub>w</sub></td><td>Size of warp. Size for both Tesla C1060 and Kepler 20 is 32.</td></tr><tr><td>σ<sub>b</sub></td><td>Maximum size (number of threads) of a block.</td></tr><tr><td>β</td><td>Number of blocks spawned in the GPU device.</td></tr><tr><td>ϑ</td><td>Number of threads per block (block size).</td></tr></tbody></table>

The estimated execution time model can be derived as:

$$ \xi_{rw} = \left\{ \frac{\beta \times \vartheta}{(\rho_w \times \sigma_w \times \rho_{sm})} \right\} \times \tau \quad (2) $$

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Surface diagrams by deploying the introduced prediction model when $\vartheta$ is increased from 32 to 1024, $\beta$ increased from 16 to 1248, and $\tau = 14.5$ (a) shows measured total execution time surface (b) shows measured efficiency surface diagram (associated with Eq. 3)</figcaption></figure>

The composite prediction model which incorporates all major specified effects includes the input parameters: ideal thread execution time, execution efficiency when $\beta > (\rho_b \times \rho_{sm})$, and execution efficiency when threads in a SM > $(\rho_w \times \sigma_w)$. The model equation is derived from Eqs. 1 and 2 to reflect the observed effect in total thread execution time ($\kappa$).

$$ \kappa = \begin{cases} \frac{\tau}{(\tau + \xi_{rw})}, & \text{when } (\beta \times \vartheta) \le (\rho_w \times \sigma_w \times \rho_{sm}) \\ \frac{\tau}{(\xi_{rb} + \xi_{rw})}, & \text{when } (\beta \times \vartheta) > (\rho_w \times \sigma_w \times \rho_{sm}) \end{cases} \quad (3) $$
When the value of $(\beta \times \vartheta) \le (\rho_w \times \sigma_w \times \rho_{sm})$, the $\tau$ is divided by an expression which incorporates the overhead of warp occupancy. Next, when $(\beta \times \vartheta) > (\rho_w \times \sigma_w \times \rho_{sm})$, the $\tau$ is divided by an expression which contains the overhead of both $\beta > \rho_b$ and $\vartheta > \rho_t$ expressed in Eqs. 1 and 2.

Figure 1 (a) shows the composite effect of increased blocks and threads in a block on total execution time of the GPU kernel. In this figure, two horizontal axes represents $\vartheta$ and $\beta$ respectively and the vertical axis represents the total execution time in milliseconds. With careful observation, it can be seen that for each case when $\beta > (\rho_b \times \rho_{sm})$, the execution time jumps by the value of $\tau$. Similarly, when $(\beta \times \vartheta) > (\rho_w \times \sigma_w \times \rho_{sm})$, for each $(\rho_w \times \sigma_w \times \rho_{sm})$, the execution time increases utilizing Eq. 2. The total execution time increases sharply for large number of blocks and its sizes. Figure 1 (b) depicts the execution efficiency surface measured by Eq. 3. The efficiency surface diagram clearly visualizes the composite effect of increased number of $\beta$ and $\vartheta$. The model depicts a sharp performance degradation as soon as the $\beta > \rho_b$.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Surface diagrams for the Sum of Binomial Series benchmark program (a) shows increasing run-time while $\vartheta$ increased from 32 to 1248 and $\beta$ increased from 16 to 1024 (b) shows measured efficiency surface diagram with respect to $\tau$.</figcaption></figure>

# 3 Empirical Studies

The purpose of this experimental study is to empirically measure the execution efficiency of kernels in GPUs as a function of aggregate blocks and threads in each block. The *Sum of binomial series* benchmark program is utilized from Nvidia CUDA SDK to conduct the empirical work to ensure real-world applications adaptability and accuracy. Two different GPU devices are used for evaluating the proposed efficiency prediction models for parallel thread execution. We have used Kepler 20 and Tesla C1060 GPU cards for empirical studies in heterogeneous environments.
<table><caption>**Table 2.** Empirical results using Kepler 20 GPU device for the Sum of Binomial Series benchmark program.</caption><thead><tr><th rowspan="2">β</th><th colspan="10">Number of Threads per Block (ϑ)</th></tr><tr><th>32</th><th>64</th><th>96</th><th>128</th><th>160</th><th>192</th><th>224</th><th>256</th><th>288</th><th>320</th></tr></thead><tbody><tr><td>16</td><td>14.61</td><td>14.61</td><td>14.62</td><td>14.63</td><td>14.62</td><td>14.62</td><td>14.62</td><td>14.62</td><td>14.63</td><td>14.64</td></tr><tr><td>64</td><td>14.61</td><td>14.60</td><td>14.63</td><td>14.62</td><td>15.42</td><td>15.91</td><td>16.90</td><td>17.73</td><td>21.34</td><td>22.57</td></tr><tr><td>112</td><td>14.60</td><td>14.53</td><td>15.20</td><td>16.69</td><td>21.38</td><td>24.35</td><td>27.93</td><td>42.31</td><td>42.74</td><td>41.72</td></tr><tr><td>160</td><td>14.54</td><td>15.19</td><td>17.84</td><td>22.47</td><td>40.29</td><td>40.58</td><td>44.35</td><td>45.28</td><td>52.16</td><td>65.71</td></tr><tr><td>208</td><td>14.55</td><td>15.83</td><td>20.80</td><td>27.64</td><td>43.00</td><td>45.12</td><td>52.69</td><td>55.23</td><td>70.21</td><td>77.90</td></tr><tr><td>224</td><td>29.02</td><td>30.36</td><td>35.30</td><td>42.16</td><td>42.97</td><td>46.65</td><td>56.08</td><td>69.69</td><td>75.50</td><td>78.63</td></tr><tr><td>272</td><td>29.05</td><td>30.37</td><td>35.47</td><td>43.40</td><td>50.60</td><td>66.41</td><td>70.39</td><td>79.28</td><td>84.12</td><td>95.45</td></tr><tr><td>320</td><td>29.07</td><td>30.54</td><td>36.56</td><td>45.43</td><td>67.23</td><td>71.02</td><td>80.39</td><td>98.46</td><td>102.9</td><td>117.3</td></tr><tr><td>368</td><td>29.08</td><td>31.60</td><td>39.95</td><td>51.77</td><td>69.03</td><td>78.60</td><td>96.55</td><td>103.4</td><td>123.5</td><td>127.1</td></tr><tr><td>416</td><td>29.02</td><td>31.63</td><td>41.58</td><td>55.38</td><td>75.08</td><td>93.54</td><td>102.2</td><td>110.4</td><td>129.7</td><td>147.5</td></tr><tr><td>432</td><td>43.45</td><td>46.13</td><td>56.03</td><td>69.73</td><td>78.60</td><td>94.69</td><td>105.3</td><td>124.9</td><td>134.9</td><td>147.9</td></tr><tr><td>480</td><td>43.50</td><td>46.15</td><td>56.19</td><td>70.99</td><td>93.14</td><td>99.24</td><td>124.6</td><td>134.3</td><td>153.7</td><td>170.8</td></tr><tr><td>528</td><td>43.51</td><td>46.32</td><td>58.16</td><td>74.42</td><td>94.91</td><td>117.8</td><td>132.6</td><td>152.3</td><td>164.8</td><td>178.4</td></tr><tr><td>576</td><td>43.50</td><td>46.75</td><td>60.69</td><td>79.36</td><td>101.6</td><td>120.7</td><td>139.1</td><td>161.9</td><td>181.4</td><td>199.4</td></tr><tr><td>624</td><td>43.51</td><td>47.41</td><td>62.39</td><td>83.10</td><td>105.8</td><td>130.2</td><td>152.4</td><td>165.5</td><td>192.9</td><td>209.2</td></tr><tr><td>640</td><td>57.87</td><td>61.91</td><td>76.75</td><td>97.30</td><td>118.9</td><td>131.1</td><td>156.4</td><td>180.1</td><td>203.4</td><td>222.6</td></tr></tbody></table>

It can be observed from Table 2 that for $β = 64$ and $ϑ$ ranging from 32 to 320, as the $(β × ϑ) > ρ_t$, the execution time increases around $(2 × τ)$ depending on the number of warps. This behavior is modeled using Eq. 2. Next, when the total number of threads spawned $(β × ϑ)$ is more than the occupancy, $(ρ_w × σ_w × ρ_{sm} = 64 × 32 × 13 = 26,624$ for the Kepler 20 device), the specified series in Section 2 can be observed in the Table 2. For $β = 208$ and $ϑ = 128$, the number of threads spawned in the device is $208 × 128 = 26,624$ (i.e., maximum occupancy reached)$^1$. As soon as the $ϑ$ or $β$ increases, the execution time increases depending on the number of execution cycle. This observed behavior is modeled using Eq. 3.

Figure 2 (a) and (b) shows the complete measured *run time surface* and *efficiency surface* (using Eq. 3) diagram for the sum of binomial series benchmark program. Both surfaces depict the complete 2496 independent test run results to capture all possible scenarios by varying the values of $β$ and $ϑ$. It can be observed from Figure 2 (a) that each time when $β × ϑ$ crosses $(ρ_w × σ_w × ρ_{sm})$, the execution time increases for new scheduling cycles. Similarly, when $β$ crosses $(ρ_b × ρ_{sm})$, the execution time increases by $τ$. It can be observed from Figure 2 (b) that the efficiency value decreases significantly when $β$ and $ϑ$ increases beyond the capacity of scheduling cycle. Both surface diagrams clearly depicts same behavior and shape as compared to the models' run-time and efficiency surfaces in Figure 1 respectively.

<footnote n="1">¹ Maximum number of resident threads in a Kepler 20 SM is 2048 though a thread block can contain a maximum of 1024 threads.</footnote>
## 4 Conclusion

This paper has introduced prediction models to forecast the execution efficiency of GPUs for computationally intensive kernels. The key challenge was to determine the arrangement of blocks and threads in a block prior to placement of threads into the run queue. The model has been validated with Nvidia CUDA GPU SDK benchmark program for accuracy. The provided surface diagrams depict clear visualization of measured efficiency based on variable number of blocks and size of blocks. The empirical studies performed on the prediction model show that the model surface follows the same shape and pattern of the real-world benchmark programs with only 0.13 – 5.69% prediction error. The conducted study is highly useful for understanding and optimizing performance on GPUs and useful in the context of heterogeneous environment to choose the device with a better performance potential.

## References

1. Sim, Jaewoong and Dasgupta, Aniruddha and Kim, Hyesoon and Vuduc, Richard, "A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications", 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '12), pp. 11-22, New Orleans, Louisiana, 2012.

2. Khondker S. Hasan, John K. Antonio, and Sridhar Radhakrishnan, "A New Composite CPU/Memory Model for Predicting Efficiency of Multi-core Processing", The 20th IEEE International Symposium on High Performance Computer Architecture (HPCA-2014) workshop, Orlando, FL, February 15-19, 2014.

3. John K. Holmen and David L. Foster, "Accelerating Single Iteration Performance of CUDA-Based 3D ReactionDiffusion Simulations", International Journal of Parallel Programming, Springer, Volume 42, Issue 2, pp. 343-363, DOI 10.1007/s10766-013-0251-z, April 2014.

4. Chatterjee, Amlan and Radhakrishnan, Sridhar and Antonio, John K, "Data Structures and Algorithms for Counting Problems on Graphs using GPU", International Journal of Networking and Computing, vol. 3, num. 2, pp. 264-288, 2013.

5. Khondker S. Hasan, Sridhar Radhakrishnan, and John K. Antonio, "Composite Prediction Model and Task Distribution on a Cloud of Multi-core Processors", IEEE International Conference on High Performance Computing (HiPC-14) workshop, Bangalore, India, Dec. 2013.

6. "Kepler Compute Architecture Technology in a Brief", http://www.nvidia.com/content/PDF/kepler/NV_DS_Tesla_KCompute_Arch_May_2012_LR.pdf, 2012.

7. Yao Zhang and Owens, J.D., "A quantitative performance analysis model for GPU architectures", High Performance Computer Architecture (HPCA), 2011 IEEE 17th International Symposium on, pp. 382-393, 2011.

8. Nvidia CUDA GPU SDK, Sample CUDA Toolkits, http://docs.nvidia.com/cuda/cuda-samples/

9. CUDA Warps and Occupancy, "GPU Computing Webinar", Available from: http://on-demand.gputechconf.com/gtc-express/2011/presentations/cuda_webinars_WarpsAndOccupancy.pdf, July 2011.

10. Siu Kwan Lam, "CUDA Performance: Maximizing Instruction-Level Parallelism", Available from: http://continuum.io/blog/cudapy_ilp_opt, September, 2013.