# mHLogGP: A Parallel Computation Model for CPU/GPU Heterogeneous Computing Cluster

Gangfeng Liu, Yunlan Wang, Tianhai Zhao, Jianhua Gu, Dongyang Li

► To cite this version:

Gangfeng Liu, Yunlan Wang, Tianhai Zhao, Jianhua Gu, Dongyang Li. mHLogGP: A Parallel Computation Model for CPU/GPU Heterogeneous Computing Cluster. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. pp.217-224, 10.1007/978-3-642-35606-3_25 . hal-01551314

HAL Id: hal-01551314

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

Submitted on 30 Jun 2017

**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>
mHLogGP: a Parallel Computation Model for CPU/GPU
Heterogeneous Computing Cluster

Gangfeng Liu, Yunlan Wang, Tianhai Zhao, Jianhua Gu, Dongyang Li

Center for High Performance Computing, Northwestern Polytechnical University, Xi'an, China

wangyl@nwpu.edu.cn

**Abstract.** CPU/GPU heterogeneous computing has become a tendency in scientific and engineering computing. The conventional computation models cannot be used to estimate the application running time under the CPU/GPU heterogeneous computing environment. In this paper, a new model named mHLogGP is presented on the basis of mPlogP, LogGP and LogP. In mHLogGP, the communication and memory access is abstracted based on the characteristic of CPU/GPU hybrid computing cluster. This model can be used to study the behavior of application, estimate the execution time and guide the optimization of parallel programs. The results show that the predicted running time approaches to the actual execution of program.

**Keywords:** CPU/GPU Heterogeneous computing; Parallel Computation Mod-
el; Parallel Computing

# 1 Introduction

The compute-capable graphics processing units (GPUs) are attractive as accelerators for high-performance parallel computing. According to the top500 supercomputer sites, three out of the top five fastest supercomputers in November 2011, employ GPUs. CPU and GPU have their own advantages respectively. CPU is suitable for complex arithmetical, logical, and input/output operations. GPU consists of hundreds of smaller cores which gives high compute performance. Therefore, heterogeneous CPU/GPU computing provides new and powerful computing architecture.

The conventional parallel computation models are not suitable for the new emerg-
ing heterogeneous computing environment. The PRAM [1] is unrealistic because it
assumes that all processors work synchronously. The bulk-synchronous parallel mod-
el (BSP) [2] models asynchronously processors, communication latency and limited
bandwidth. The LogP model [3] is capable of predicting the communication time for
short messages but cannot accurately predict the communication time for long mes-
sages. The LogGP [4] extends it and adds an additional parameter for long messages,
which captures the bandwidth constraints for long messages. The PlogP [5] considers
the varying communication overheads for different message sizes. The memory LogP
[6], log<sub>3</sub>P and log<sub>n</sub>P [7] models draw characteristics of data movement in the tradi-
tional parallel computer. However, all the models mentioned above ignore the new characteristics of communication and memory access in the heterogeneous computing system. MMGP [8] is a multi-dimensional parallel computation model for steering the parallelization process on heterogeneous multi-core processors. However, it ignores the influence of data movement across computational cores. mPlogP [9] is also a model for heterogeneous multi-core computer. It extends PLogP and adds another level on top of the conventional level to model behaviors of computational cores. However, the characteristics of CPU/GPU hybrid computing environment is not considered in this model.

In this paper, a new model named mHLogGP is proposed, which is on the basis of mPlogP, LogGP and LogP. In order to analyze the characteristics of CPU/GPU heterogeneous computing cluster, some related parameters are defined to estimate the time performance of the parallel program.

# 2 mHLogGP model

## 2.1 abstract hardware architecture of GPU and CPU

Fig.1(a) shows GPU abstract architecture [10]. Each thread processors has private memory and parallel data cache. The thread processors visit each other through the parallel data cache and global memory. Fig.1 (b) shows CPU abstract architecture, the CPU cores exchange message via the bus and the host memory.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Hardware Abstraction of Processor Architecture</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Hardware Abstraction of a node(a) and cluster(b)</figcaption></figure>

The hardware abstraction of computer node which includes GPU and CPU is showed in Fig.2(a). The host memory is shared by GPU and CPU. GPU exchanges information with CPU by accessing host memory.
The hardware abstraction of the widely used CPU/GPU computer cluster is shown in Fig.2(b). A computer cluster consists of dozens to thousands computers that are connected by high performance network such as Infiniband, 10-Gigabit Ethernet, etc.

## 2.2 The parameters of the model

$o$(Overhead): the time needed by processor to send or receive a message, $o \in \{o_s, o_r\}$. $o_s \in \{o_{sg}, o_{sc}\}$, $o_{sg}$ is the time that GPU sends messages to host memory. $o_{sc}$ is the time that CPU sending messages. $o_{sc} \in \{o_{scd}, o_{scn}\}$, $o_{scd}$ defined as the time that CPU sends messages to global memory. $o_{scn}$ is the time that CPU sending messages to another computer node. $o_r \in \{o_{rgb}, o_{rn}, o_{rd}\}$, $o_r$ is the time that a processor receive a message. $o_{rgb}$ is the time of initializing the GPU. $o_{rn}$ ($o_{rd}$) is defined as the time that CPU (GPU) engaged reception of each message.

$l$: latency, or delay, incurred in communicating a message from its sender to receiver. $l \in \{l_g, l_c, l_{dm}, l_{nn}\}$, $l_g$ denotes the latency between the parallel data cache and the global memory. $l_c$ denotes the latency from the core of CPU to the host memory of another node. $l_{dm}$ denotes the latency between the global memory and the host memory. $l_{nn}$ is defined as the delay from one node to another.

$G$: the Gap per byte for long messages, which is defined as the time per byte for a long message. The reciprocal of $G$ characterizes the available communication bandwidth per processor for long messages.

$g$: the gap, defined as the time interval between consecutive message transmission or reception. The reciprocal of $g$ corresponds to the available communication bandwidth per-processor and the speed of accessing the memory. $g \in \{g_g, g_c\}$, $g_g$ means the time interval between consecutive message transmission or reception in the global memory of GPU. $g_c$ denotes the time interval for sending a message from the host memory to network cache.

$P$: the number of computer nodes. $P$ is mostly used to model the collective communication.

# 3 Usage of the Model

## 3.1 Point-to-Point Communication

In this section, the performance of point-to-point communications is predicted. In the CPU/GPU hybrid computing environment, the cost of sending short message between two nodes can be predicted as $o_{s1}+l+o_{r1}(\text{LogP})$, where $l$ is the latency of communicating a message from its sender to receiver, $o_{s1}$, $o_{r1}$ is the time of sending or receiving the first message, where $G$ is the Gap per byte. For long message, the Point-to-Point Communication time can be predicted as follows:

$$T = o_{s1} + (k_1 - 1)G + l + o_{r1} \quad (\text{LogGP}) \quad (1)$$

As shown in Fig.3, if the non-blocking communication is used to send ‘m’ consecutive messages, the transmission time is as follows:
$$T = o_{s1} + (k_1 - 1)G + \sum_{i=1}^{m-1} \max(((k_{i+1} - 1)G + g_{c(i+1)} + o_{s(i+1)}), l_{nmi}) + l_{nmn} + o_{rm} \quad (2)$$

Where $k_{i+1}$ is the size of the (i+1)-th message. $o_{si}$, $o_{ri}$ is the time of sending or receiving the i-th message. It is obvious that network bandwidth and the speed of accessing the memory have a great influence on inter-node communication time.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Sending and receiving messages</figcaption></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 4. Half-round trip sender/receiver communication cost</figcaption></figure>

The communication cost varies with different sender and receiver. If messages are send from CPU of one node to CPU of another node (Fig.4A), the communication cost can be expressed by (2) where $o_s = o_{scn}$ and $o_r = o_m$. If messages are send from CPU of one node to GPU of another node (Fig.4B), $o_s = o_{scn}$, for the first message, $o_r = o_{rgb} + o_m + o_{rd}$, for other messages, $o_r = o_m + o_{rd}$. If messages are sent from GPU of one node to CPU of another node (Fig.4C), $o_s = o_{sg} + o_{scn}$, $o_r = o_m$. If messages are send from GPU of one node to GPU of another node (Fig.4D), $o_s = o_{sg} + o_{scn}$, for the first message $o_r = o_{rgb} + o_m + o_{rd}$, for other messages $o_r = o_m + o_{rd}$.
## 3.2 Broadcast Communication

We take the MPICH2 as example. For the short message or the number of nodes less than 8, the broadcast communication is taken by the short message algorithm, namely, binomial tree. If the number of nodes is P and the size of the message is k. it needs lgP steps in broadcast communication. Each byte travels through the network for $l_{nn}$. Under the CPU/GPU heterogeneous computing environment, the broadcast communication cost can be predicted as follows:

$$T_{\text{broP}} = \text{lgP} * o + \text{lgP} * k * (G + l_{nn}). \quad (3)$$

For medium-size messages and power-of-two number of nodes, the broadcast communication uses a recursive doubling algorithm. This costs approximately $T_{\text{broP}} = 2*\text{lgP} * o + 2*\text{k}*(P-1)/P*(G+l_{nn})$. For long messages or medium-size messages and non-power-of-two node situations the broadcast communication use a ring algorithm, which takes P-1 steps, so the total cost is $T_{\text{broP}} = (\text{lgP} + P - 1) * o + 2 * \text{k} * (P - 1) / P * (G + l_{nn})$.

# 4 Validating the Model

Our experimental platform is the Dawning TC3600 Blade system with Intel X5650 processors and NVIDIA Tesla C2050 GPUs at the National Super Computer Center in Shenzhen, China. The computing network is 40Gb InfiniBand.

<table><caption>**Table 1.** Sender and receiver overheads between Global memory and host memory</caption><thead><tr><th>Message Size</th><th>1B</th><th>4KB</th><th>16KB</th><th>64KB</th><th>256KB</th><th>1MB</th><th>4MB</th><th>16MB</th><th>256MB</th></tr></thead><tbody><tr><td>o<sub>scd</sub>,o<sub>id</sub>(µs)</td><td>3</td><td>45</td><td>52</td><td>64</td><td>173</td><td>381</td><td>1243</td><td>4754</td><td>71799</td></tr><tr><td>O<sub>rg</sub>(µs)</td><td>20</td><td>22</td><td>26</td><td>50</td><td>174</td><td>824</td><td>1329</td><td>4803</td><td>70209</td></tr><tr><td>O<sub>scn</sub>(µs)</td><td>4</td><td>4</td><td>8</td><td>17</td><td>32</td><td>65</td><td>128</td><td>904</td><td>20426</td></tr><tr><td>O<sub>rgb</sub>(µs)</td><td>102055</td><td>103537</td><td>109984</td><td>109455</td><td>114427</td><td>111911</td><td>101656</td><td>101410</td><td>103542</td></tr><tr><td>o<sub>m</sub>(µs)</td><td>3</td><td>5</td><td>8</td><td>15</td><td>32</td><td>67</td><td>129</td><td>1002</td><td>21527</td></tr><tr><td>l<sub>m</sub>(µs)</td><td>141</td><td>149</td><td>225</td><td>268</td><td>339</td><td>755</td><td>2589</td><td>10461</td><td>161469</td></tr></tbody></table>

It can be shown in Table 1 that $o_{scd}$ remains unchanged when the message size is less than 256 KB. It increases linearly when the message size is larger than 256 KB. So does $o_{rg}$, $o_{scn}$ and $o_{m}$ when the size is larger than 64KB. Since the GPU must be initialized, no matter the size of message short or large, the value of $o_{rgb}$ has no large variation. Because the speed of intra-node communication is very high, the value of $l_g$, $l_c$ and $l_{dm}$ can be ignored. $l_{nn}$ denotes the intra-node delay. The experiments show that $l_{nn}$ is random from 100 µs to 700 µs when the size of a message is less than 1MB. It increases linearly when the message size is larger than the 1MB.

As shown in Table 2, G is not stable when the size of a message is less than 1MB. When the message size larger than 1MB, it approaches a constant. $g_g$ and $g_c$ has changed little when the size of the data varies.

As shown in Table 3, for the messages size larger than 64KB, the total cost of broadcast communication is accord with ring algorithm. There may be errors of the
test function, and other factors deviating from the principle of broadcast communica-
tion when the messages size less than 64KB.

<table><caption>**Table 2.** Overheads per byte for a long message</caption>
  <thead>
    <tr>
      <th>Message Size</th>
      <th>1B</th>
      <th>256B</th>
      <th>1KB</th>
      <th>16 kB</th>
      <th>64kB</th>
      <th>256kB</th>
      <th>1MB</th>
      <th>16MB</th>
      <th>64MB</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>G(µs/B)</th>
      <td>141</td>
      <td>0.578125</td>
      <td>0.145508</td>
      <td>0.014710</td>
      <td>0.004577</td>
      <td>0.001537</td>
      <td>0.000845</td>
      <td>0.000737</td>
      <td>0.000749</td>
    </tr>
    <tr>
      <th>g<sub>g</sub>(µs)</th>
      <td>4</td>
      <td>4</td>
      <td>4</td>
      <td>4</td>
      <td>4</td>
      <td>7</td>
      <td>68</td>
      <td>104</td>
      <td>249</td>
    </tr>
    <tr>
      <th>g<sub>g</sub>(µs)</th>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>42</td>
      <td>39</td>
      <td>40</td>
      <td>41</td>
      <td>55</td>
      <td>35</td>
    </tr>
  </tbody>
</table>

<table><caption>**Table 3.** Overheads of broadcast communication</caption>
  <thead>
    <tr>
      <th>size<br>time(µs)<br>nodes</th>
      <th>1B</th>
      <th>256B</th>
      <th>16KB</th>
      <th>64KB</th>
      <th>256KB</th>
      <th>1MB</th>
      <th>4MB</th>
      <th>16MB</th>
      <th>64MB</th>
      <th>256MB</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>2</th>
      <td>83667</td>
      <td>85284</td>
      <td>97732</td>
      <td>106578</td>
      <td>106578</td>
      <td>95334</td>
      <td>101449</td>
      <td>140239</td>
      <td>211425</td>
      <td>417945</td>
    </tr>
    <tr>
      <th>4</th>
      <td>132472</td>
      <td>142002</td>
      <td>140794</td>
      <td>188769</td>
      <td>213175</td>
      <td>197967</td>
      <td>234129</td>
      <td>284768</td>
      <td>392290</td>
      <td>805469</td>
    </tr>
    <tr>
      <th>8</th>
      <td>207340</td>
      <td>203330</td>
      <td>291777</td>
      <td>294295</td>
      <td>299879</td>
      <td>300807</td>
      <td>472381</td>
      <td>599026</td>
      <td>822744</td>
      <td>1804826</td>
    </tr>
  </tbody>
</table>

5 Experiments Validation

The matrix multiply [11] is adopted to validate mHLogGP. The implementation of
algorithm mainly adopts the point-to-point communication and broadcast communica-
tion. Let A and B be two matrices, n represents the number of lines in matrices A.
Matrices A is divided into p parts. The master process sends every part and broadcast
matrices B to p slave processes. The slave processes receive the data and do the calcu-
lation by GPU and send the results to the master process. The master process receives
the results and save the information. The overhead of program can be estimated based
on the formulas in Section 3.

<table><caption>**Table 4.** The comparison between computing cost and total cost</caption>
  <tr>
    <td>Matrix size</td>
    <td>64*64</td>
    <td>128*128</td>
    <td>256*256</td>
    <td>512*512</td>
    <td>1024*1024</td>
    <td>2048*2048</td>
    <td>4192*4192</td>
    <td>8192*8192</td>
  </tr>
  <tr>
    <td>Total cost( µs )</td>
    <td>110268</td>
    <td>109819</td>
    <td>115474</td>
    <td>115553</td>
    <td>119466</td>
    <td>219825</td>
    <td>964722</td>
    <td>6999979</td>
  </tr>
  <tr>
    <td>Computing cost( µs )</td>
    <td>164</td>
    <td>166</td>
    <td>241</td>
    <td>300</td>
    <td>423</td>
    <td>1042</td>
    <td>2854</td>
    <td>11284</td>
  </tr>
</table>

The cost of sending messages (for the master process) is:

$$
T_{\text{ptop1}} = o_{\text{scnl}} + (k_1 - 1)G + \sum_{i=1}^{p-1} \max(((k_{i+1} - 1)G + g_{c(i+1)} + o_{\text{scnt(i+1)}}), l_{\text{nni}}) + l_{\text{nnp}} + o_{\text{rnp}} + o_{\text{rgbp}} + o_{\text{rdp}}
$$

The cost of receiving messages (for the master process) is:

$$
T_{\text{ptop2}} = \sum_{i=1}^{p} (o_{\text{sgi}} + o_{\text{scni}} + (k_i - 1)G + l_{\text{nni}} + o_{\text{rni}})
$$
The cost of the broadcast Communication (for the master process) is:

$$T_{\text{broP}} = (\lg P + P - 1) * o + 2 * k * (P - 1) / P * (G + l_m)$$

The value of parameters is based on the experiments data in section 4. For single GPU, the computing cost and total cost is shown in Table 4. The computing time in matrix multiply is very short compared to communication time, so it is ignored.

<figure><img src="image_9.png" /><figcaption>Fig. 5. The comparison of the predicted and actual execution time</figcaption></figure>

The experiments are done on a cluster with 8 nodes including GPU. The comparison of the predicted and actual running time is shown in Fig.5. It is shown that our model could get competitive accuracy. With the increase of computation scale, the errors of the predicted running time increases. But, at worst, when matrix size becomes 8192*8192 on 8 nodes, the error of our model is 15-25%.

## 6 Conclusion And Future Work

Nowadays, CPU/GPU heterogeneous computing is a tendency. The conventional computation models do not fit in with the emerging CPU/GPU heterogeneous computing environment. In this paper, a new model named mHLogGP is presented. In mHLogGP, communication and memory access is abstracted by considering the characteristic of the CPU/GPU heterogeneous computing environment. This parallel computation model can be used to estimate the communication time and running time of
parallel program, to find the bottleneck and guide the optimization of parallel programs in heterogeneous computing environment. The evaluation experiments show that this computation model is valid. In the future, the computing time of parallel program will be concerned. We will also study the execution time of concurrent parallel programs under the heterogeneous computing environment with dynamic load.

## Acknowledgment

This research was partially supported by the National High-Tech Research and Development Plan of China (Grant No. 2009AA01Z142).

## References

1. Steven F., James W.: Parallelism in Random Access Machines. In: Proceedings of the 10th Annual Symposium on Theory of Computing, 1978:114-118 (1978)

2. Leslie G. V.: A bridging model for parallel computation. In: Commun. of the ACM, vol. 33, p. 103-111, 1990 (1990)

3. David C., Richard K., David P., Abhijit S., Klaus E. S., Eunice S., Ramesh S., Thorsten v. E.: Logp: Towards a realistic model of parallel computation. In: Proc. of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1993)

4. Albert A., Mihai F. I., Klaus E. S., and Chris S.: LogGP: incorporating long messages into the logp model—one step closer towards a realistic model for parallel computation. In: Proc. of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures (1995)

5. Thilo K., Henri E. B., and Kees V.: Fast measurement of logp parameters for message passing platforms. In: Proc. of the 4th Workshop on Runtime Systems for Parallel Programming (RTSPP) (2000)

6. Qasim A., Samuel P. M., and Vijay S. P.: Modeling advanced collective communication algorithms on cell-based systems. In: Proc. of the 15th ACM SIGPLAN symposium on Principles and practice of parallel computing (2010)

7. Kirk W. C., Rong G., Xian-HeSun: log<sub>n</sub>P and log<sub>3</sub>P: accurate analytical models of point-to-point communication. In: distributed systems. In: IEEE Trans. Computers, MARCH 2007,56(3):314-32 (2007)

8. Filip B., Xizhou F., Kirk W. C., and Dimitrios S. N.: Modeling multi-grain parallelism on heterogeneous multicore processors: A case study of the cell be. In: Proc. of the 2008 International Conference on High-Performance Embedded Architectures and Compilers, Goteborg, Sweden (2008)

9. Liang L., Xingjun Z., Jinghua F., and Xiaoshe D.: mPlogP: a Parallel Computation Model for Heterogeneous Multi-core Computer. In: Proc. of 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (2010)

10. Sunpyo H., Hyesoon K.: An Analytical Model for a GPU Architecture with Memory-level and Thread-level Parallelism Awareness. In: ISCA'09, Proceedings of the 36th annual international symposium on Computer architecture, 2009: 152-163 (2009)

11. N. P. Karunadasa and D. N. Ranasinghe: Accelerating High Performance Applications with CUDA and MPI. In: Proc. Of Fourth International Conference on Industrial and Information Systems, ICIIS 2009, 28 - 31 December 2009, Sri Lanka (2009)