Game Development Reference
In-Depth Information
We chose to use domain decomposition, which is often used in grid-based
simulation, for particle-based simulation instead of splitting the particles by their
indices. A processor assigned to a subdomain simulates the particles in the sub-
domain. At first, particle motions are ignored for simplicity. Their motion will be
taken into account in the next section.
We first have to consider how to store the particle data. The simplest way
would be by employing server-client-type management, in which a server pro-
cessor containing all the data distributes jobs with data to client processors and
retrieves the results in each step. Although this is easy to implement, it requires a
large data transfer. This is not efficient when the data transfer between processors
is expensive, as with GPUs. Moreover, the clients have to wait while the server
is preparing the data to be sent. Therefore, we used another strategy to manage
the data that is better suited for parallelizing on multiple processors, and in which
each processor manages its own data: peer-to-peer-type management.
To calculate the physical values of a particle, the values of neighboring parti-
cles are used: positions of neighbors are used to calculate forces using a distinct
element method (DEM) simulation [Mishra 03]; physical values of neighbors are
integrated in a smoothed particle hydrodynamics (SPH) simulation (see Chap-
ter 6). Neighbors can be in the adjacent subdomain computed by another proces-
sor. In this case, the processor has to ask for the data from the adjacent processor.
Accessing the memory of another processor whenever it is necessary, is ineffi-
cient because it lowers the granularity of the memory transfer when it is smaller
and more frequent. Therefore, we introduce ghost regions to the simulation—the
entire computation domain is
C =
{
x
|
s<x
e
}
,
and two processors p 0 and p 1 are used for the simulation. The domain is decom-
posed at x by a plane perpendicular to the x -axis, so the subdomains for p 0 and
p 1 are
C 0 =
{
x
|
s<x
m
}
,
C 1 =
{
x
|
m<x
e
}
,
where m =( s + e ) / 2 is the midpoint of the computation domain in the x -
direction. Then, the ghost region for p 0 is the area in C 1 adjacent to C 0 ,so
G 1 0 =
{
x
|
m<x
m + g
}
,