538
G. Kotalczyk and F. E. Kruis
...
...
...
...
...
...
...
...
Fig. 10 Compartment-Stream merge pattern. Each double arrow represents one merge attempt. All
merge attempts which are executed in parallel with the destination offset o idx = 0 are shown in
comparison with all parallel merge attempts made for the offset o idx = 1
3.2.2 Parallel Merge Algorithm
The merging algorithm described in Fig. 4 could be used for the merging of MC
particles within stream and the destination compartment. However, such an approach
would be computationally not efficient due to the large number of MC particles
ranging in typical applications between 1000 and 10000. This would imply 1000
or 10000 sequential or parallel invocations of the algorithm presented in Fig. 4. In
order to accelerate the merging process, a novel parallel algorithm has been briefly
sketched in [57] and is discussed here in more detail. The GPU’s capability to process
a large amount of data in parallel can be exploited in a more efficient way, if not only
one (as in Fig. 4) but a large number of MC particles has to be merged together (as
in Fig. 9).
The merging scheme described by Eq. (6) and (7) can be thereby used in combination with the merging error described by Eq. (9). A maximal admittable merging error
ε can be formulated and all particle pairs (i, j) with a merging error E i, j (Eq. (9))
smaller than ε are merged together. A large number of parallel comparisons can
thereby be performed, forming potential pairs for the merging by calculation of the
merging errors of the pairs consisting of one particle in the destination compartment
and one particle in one of the streams, as shown as ‘Compartment-stream merge
pattern’ in Fig. 10. The destination offset, o idx , is thereby increased by one after
each comparison attempt, so that different pairs are formed for the calculation of the
merging error. After 512 steps, all possible pairs between each of the compartment
particle and another stream MC particle would have been checked in this way.
3 An
internal check between particles stored in the compartment (resp. streams) is also
3 In order to use the GPU efficiently, larger particle numbers (like e.g. 10000) have to be divided into
data blocks consisting of e.g. 512 particle numbers. In the here presented implementation, particle
numbers that are multiples of 512 are considered.
G. Kotalczyk and F. E. Kruis
...
...
...
...
...
...
...
...
Fig. 10 Compartment-Stream merge pattern. Each double arrow represents one merge attempt. All
merge attempts which are executed in parallel with the destination offset o idx = 0 are shown in
comparison with all parallel merge attempts made for the offset o idx = 1
3.2.2 Parallel Merge Algorithm
The merging algorithm described in Fig. 4 could be used for the merging of MC
particles within stream and the destination compartment. However, such an approach
would be computationally not efficient due to the large number of MC particles
ranging in typical applications between 1000 and 10000. This would imply 1000
or 10000 sequential or parallel invocations of the algorithm presented in Fig. 4. In
order to accelerate the merging process, a novel parallel algorithm has been briefly
sketched in [57] and is discussed here in more detail. The GPU’s capability to process
a large amount of data in parallel can be exploited in a more efficient way, if not only
one (as in Fig. 4) but a large number of MC particles has to be merged together (as
in Fig. 9).
The merging scheme described by Eq. (6) and (7) can be thereby used in combination with the merging error described by Eq. (9). A maximal admittable merging error
ε can be formulated and all particle pairs (i, j) with a merging error E i, j (Eq. (9))
smaller than ε are merged together. A large number of parallel comparisons can
thereby be performed, forming potential pairs for the merging by calculation of the
merging errors of the pairs consisting of one particle in the destination compartment
and one particle in one of the streams, as shown as ‘Compartment-stream merge
pattern’ in Fig. 10. The destination offset, o idx , is thereby increased by one after
each comparison attempt, so that different pairs are formed for the calculation of the
merging error. After 512 steps, all possible pairs between each of the compartment
particle and another stream MC particle would have been checked in this way.
3 An
internal check between particles stored in the compartment (resp. streams) is also
3 In order to use the GPU efficiently, larger particle numbers (like e.g. 10000) have to be divided into
data blocks consisting of e.g. 512 particle numbers. In the here presented implementation, particle
numbers that are multiples of 512 are considered.