Image Processing Reference
In-Depth Information
Fig. 26.2 An illustration of
basic parallelization strategies
for integral curves. Left
Parallelize-over-blocks
distributes data, and
integration is performed on
the processor owning
required blocks. Right
Parallelize-over-seeds
statically assigns curves to
processors; data needed for
integration must be loaded
on-demand
Parallelize-over-blocks
Parallelize-over-seeds
Processor 0
Processor 1
Processor 2
A much simpler strategy for the latter case was pointed out by Lane [ 10 ]. Here,
prefetching is achieved by limiting integration to short time intervals; while com-
putation is running, blocks for future time steps are loaded. However, his method
loads all blocks corresponding to the next time step, and is thus not truly a POS-type
method.
Overall, POS is a robust strategy. While it is generally found to be I/O intensive,
it does not possess limitations with respect to data size, and given enough parallel
resources, can in principle treat problems of arbitrary size.
26.3.2 Parallelization Over Blocks
The parallelize-over-blocks (POB) approach distributes data blocks across processors
using a fixed assignment. Integral curves are communicated between the tasks to
migrate them to the task owning the block required to continue integration. This
algorithm performs minimal I/O; before integration commences, every task loads all
blocks assigned to it, leveraging maximal parallel I/O capacity.
An early implementation of this algorithm for streamlines was described by Su-
judi and Haimes [ 19 ], who made use of distributed computation by splitting the
block in consideration into several sub-blocks and assigning each processor one such
sub-block. A streamline is communicated among processors as it traverses different
sub-blocks. Their design is a client/server architecture, in which the clients perform
integration and the server manages routes trajectories between clients.
A systematic investigation of the performance and scalability of the POB
approach, applied to streamline problems and spanning a wide range of integra-
tion problems, was given by Pugmire et al. [ 16 ]. In their implementation, processors
directly communicate solver state to each other when integration traverses block
boundaries. Curve geometry generated during the integration remains with the
processor that generated it, and is merged in a post-processing step; thus, their bench-
marks reflect only the curve propagation portion of a visualization pipeline.
 
Search WWH ::




Custom Search