This case study examines leveraging both the CPU and the GPU to implement a mixed-sized particle simulation. Without a loss of generality, this example is restricted to two dimensions to keep the kernels easily understandable. In addition, this case study leverages OpenCL's ability to share data between the CPU and the GPU, which is beneficial on highly integrated devices such as AMD's APUs.

Implementing a simple simulation with uniform particle sizes on data-parallel devices such as GPUs is relatively straightforward in OpenCL. Unfortunately, the efficiency of the simulation decreases if the assumption breaks (i.e., the particle size varies). The inefficiency results from the non-uniform granularity of the computation, especially for the collision detection, which is the most expensive part in a particle simulation. If there is a single large particle and many small particles, the number of collisions detected on the large particle can be significantly more than the number detected on the small particles. This difference can cause inefficiency because most GPUs execute in SIMD manner over wide vectors. If a GPU SIMD engine executes small particles for most SIMD lanes and in a single lane computes the result for a large particle, the “large” lane runs for longer than the “small” lanes. This means that the lanes computing collisions for small particles have to wait for the large lane to finish. This results in load imbalance and poor utilization of the hardware as the vector width increases. However, the CPU has no problem dealing with this variation in the granularity of computation. Accordingly, the approach we present here is to use the CPU for the collision of large particles, whereas the GPU is used only for the collision of the uniformly sized small particles. This chapter discusses how to realize the collaboration of the GPU and the CPU for a mixed-sized particle simulation using OpenCL.

Figure 10.1 is a screen shot from the simulation. You can see a large number of small particles rendered in blue interacting with varying-sized particles rendered in green and red. The green and the red colors represent dynamic and static particles, respectively. The collisions between the particles are classified into three types: small–small, large–small, and large–large. The granularity of the small–small collision is uniform, so the work is dispatched to the GPU. However, as discussed previously, the granularity of large–small and large–large is varying, so the CPU is better suited for performing these computations. If there are no large–small interactions, the two simulations are completely disjoint, so the GPU simulates the small particles and the CPU simulates the large particles. The mixed-sized particle simulation is implemented as an extension of the two disjoint computations. The challenge is to efficiently realize the interaction between the simulations because the physical properties of small particles live in GPU memory, whereas those of large particles live in CPU memory. If the memories are allocated without care, the data on the GPU has to be read back to the host every time it calculates the interaction. By using OpenCL buffers that are shared between and accessed by both the CPU and the GPU, the read back is no longer necessary.

Figure 10.2 shows an overview of the algorithm and the interaction between the GPU manager thread and the CPU work thread, both of which run on the host CPU. There are three major phases of computation per iteration: (1) data structure construction (2) computation of forces resulting from (3) collisions and force integration.

First, the GPU kernel data structure is built. Then the GPU and CPU are synchronized to guarantee that the computation of the new data structure is complete and we can share the updated data and physical properties of the small particles with the CPU thread. After the first synchronization, threads start processing collisions. The GPU performs the small–small collisions, and the CPU performs the large–small and large–large collisions. To accelerate the collision detection of small particles against large particles, the data structure built on the GPU is also used on the CPU. The output from the collisions is a set of forces on particles. Two force buffers are prepared for the small particles: One is filled with small–small forces, resulting from the small–small collisions, and the other is shared with the CPU, which fills the buffer with the forces resulting from the large–small collisions. After the collisions are completed, the GPU and CPU threads are synchronized again so that the CPU is known to have finished writing to the force buffer, which is going to be used in the integration stage. Then, the GPU integrates forces on small particles, and the CPU integrates forces on large particles. Note that there are no write conflicts between the CPU and the GPU for the shared buffer. The CPU only writes to the shared buffer during the large–small collision phase. The buffer is only accessed by the GPU during the integration after the synchronization.

The CPU implementation does not differ much from the GPU version, but it runs in scalar rather than vector fashion. The collisions of particles are serialized so that we do not have to worry about the granularity. The collision of a large particle with small particles is performed using the uniform grid that was built on the GPU and shared with the CPU. It first calculates the extent of the large particle in the grid space and looks up all the cells in the extent. Figure 10.3 illustrates overlapping cells for a large particle. As the reader can see from this figure, the large particle overlaps many cells, whereas a small particle does not. If this code were to be executed on the GPU, it would waste many cycles as SIMD lanes were masked out.

Although we have shown the flow of the simulation using two threads in Figure 10.2, our implementation suffers from pool imbalance in terms of computation between the workloads. This imbalance results in low utilization of CPU threads. Of course, the degree of imbalance depends on the numbers of small and large particles present. Looking at the CPU work thread, it is easy to see that the large–small and large–large collisions are more expensive than the integration. Thus, the time between the first and the second synchronization is the largest amount of time. On the other hand, the most expensive part of the GPU execution is the small–small collision computation, followed by the construction of the uniform grid. Although the GPU is a powerful processor, the cost of building the uniform grid is not negligible. If the simulation is executed as shown in Figure 10.2, a thread has to wait before the first synchronization and the other has to wait before the second synchronization, which we can see more clearly in Figure 10.4A.

The computations can be reordered to improve load imbalance. Figure 10.2 shows the flow of a single iteration, but it is not necessary for grid creation to be the first step if we assume that particles do not move between the end of the previous iteration and the start of the current iteration. This is generally true unless a particle is directly moved, likely through user interaction, which is relatively rare. From this observation, grid creation can be moved to the end of the previous iteration. This modification makes two big blocks for the GPU thread, but the CPU's thread workload only involves the integration of particles (which is inexpensive). If we can move some computation to the CPU thread from the first half to the second half, then this should also ease load imbalance. Careful observation of the data flow of the pipeline shows that the second synchronization is necessary only for the buffer containing forces for the small particles that were filled by the CPU. As a result, the large–large collision does not have to be performed during the first half given the removal of any data dependencies with the next GPU computation. This means that the large–large collision can be moved to the second half of the computation (as shown in Figure 10.4B). In this way, we improve the load balance on the CPU threads, which results in a reduction in total simulation time.

Figure 10.1 is a screen shot from the mixed particle simulation with approximately 8200 small particles and 150 large particles running on an AMD A-series Fusion APU, on which the CPU and GPU are integrated on-chip. The bar at the right of the figure shows the computation times on two threads (one column per thread). The full height of the column is equal to 1/60 of a second. The blue and green blocks correspond to the time spent on the GPU and the CPU, respectively. Because there are four iterations per time step, one iteration takes approximately 4 ms in this simulation. The first four blocks are for the first iterations. As can be seen, the threads synchronize after the first GPU computation. The CPU work thread is waiting for the GPU thread to finish, producing the gap between the first green block and the synchronization.

If a buffer is created without the CL_MEM_ALLOC_HOST_PTR flag, the data has to be copied when the buffer is mapped and unmapped. The effect of the map operation is quantitatively compared between a simulation with a normal buffer and a simulation with a shared buffer. Figure 10.5 is the breakdown of the times. Although the simulation itself is the same, one can see a clear difference between the two versions with and without data sharing. The comparison shows a clear advantage of using a shared buffer. However, notice the extra execution time for the GPU-side small–small collision phase when using data sharing: This is due to the extra latency of accesses over the shared memory interface.

In this chapter, we discussed an implementation of a particle simulation that handles variably sized particles by leveraging the best features of both the CPU and the GPU. In addition, by sharing memory between the CPU and the GPU on tightly integrated devices such as AMD's Fusion APU architecture, the efficiency of the computation improved by eliminating wasteful memory copies. Although this example is designed to be simple to understand, the same technique can be applicable to more complicated applications.