Parallel Visualization Frameworks 19
FIGURE 2.3: A contract summarizes the possible constraints and optimiza-
tions for the pipeline execution. Each filter has a chance to modify this con-
tract. The initial version of the contract, V 1, has default values. The final
filter, F 3, is the first to modify the contract, making a new version, V 2. The
next filter, F 2, then modifies V 2, to make a new version, V 3. The first filter
to execute, F 1, is the last to modify V 3, making the final version, V 4. This
version reflects the constraints and optimizations from all of the filters.
and another filter eliminates a different portion, then the final contract will
prescribe processing only the data at the intersection of their remainders.
2.5.2 Data Subsetting
Data subsetting refers to only processing the portion of a data set that
will affect the final result. Consider the example of slicing a 3D data set by
a plane (see Fig. 2.4). Many of the pieces will not intersect the plane and
reading them in would be a wasted effort. In fact, if P is the total number of
pieces, then the number of pieces intersected by the slice is typically O(P
2/3
).
It is possible to eliminate pieces from processing before ever reading them,
if metadata is available. By accessing the spatial extents for each piece, the
slice filter can calculate which pieces have bounding boxes that intersect the
slice and only process those pieces. Note that false positives can potentially
be generated by considering only the bounding box. In terms of the contracts
described in 2.5.1, each piece would have its own Boolean field in the contract,
indicating whether or not that piece should be processed. The Boolean for each
piece would be true by default, but the slice filter would set it to false during
its contract modification if the spatial metadata indicated it did not intersect
the slice.
2.5.3 Parallelization Artifacts
As mentioned earlier, the approach of independently operating on pieces
of a larger data set can introduce artifacts at the exteriors of the pieces. Even
20 High Performance Visualization
FIGURE 2.4: A data set decomposed into 36 pieces. Each piece is outlined
with black lines and is colored light or dark gray. To create the data set sliced
by the transparent plane, only the dark gray pieces need to be processed.
though the cause of these artifacts can differ, parallel visualization frameworks
can be adapted to detect their causes and prevent them.
Some visualizations render the external faces of a volume—possibly after
clipping away a region and giving the user a look inside a volume. However,
calculating these external faces is difficult when operating on one piece at
a time; faces that are external to a piece can be internal to the whole data
set. And, if these faces are not eliminated, they can have multiple negative
impacts. One negative impact is that the number of triangles being drawn can
increase by an order of magnitude. Another negative impact is that these extra
faces will be visible when the surface is transparent and result in an incorrect
image. The solution to this problem is straightforward: identify faces that are
external to a piece but internal to the data set. These faces are called ghost
faces. In some cases, especially with unstructured grids, this identification
requires significant additional memory, possibly in the form of a Boolean array
for every face in the piece.
Interpolation is another cause of artifacts. If the data must be interpolated
from cell centers to node centers—in anticipation of applying a Marching
Cubes isosurface algorithm, which depends on nodal data, for example—then
inconsistent values will get assigned to the nodes that are duplicated at the
boundary of two pieces. These inconsistent values can ultimately in broken
isosurfaces. The common solution to this problem is to introduce ghost cells.
Ghost cells are an extra layer of cells around each piece that are used for
interpolation, but discarded before rendering. The cost for this approach is
even more significant. The piece’s size is increased (more cells and more values)
Parallel Visualization Frameworks 21
and additional memory must be allocated for understanding which cells are
ghost and which are not, so the ghost cells can be removed before rendering.
Once again, contracts can be used to solve this problem. Each filter can
modify the contract to identify their constraints, i.e., whether ultimately they
will be calculating external faces or whether they will be performing inter-
polation. If they do, filters can be inserted to mark ghost faces or add ghost
cells. If not, then no additional action is taken. In this case, this coordination
allows the parallel visualization framework to prevent the conservative policy
of always generating unnecessary ghost data; the correct picture can always
be calculated at minimum cost.
2.5.4 Scheduling
Parallel visualization frameworks accommodate multiple strategies for
scheduling the processing of pieces. Further, for a given execution, they can
dynamically choose a strategy based on pipeline properties.
Dynamic load balancing is a scheduling strategy that assigns one task
to play the role of master and the rest to be slaves. Any time a slave is
idle, the master assigns it a piece for processing, until there is no more work
to do. This strategy is particularly effective when the pieces take a different
amount of time to process, as it naturally adapts to balance load. Further, the
approach typically uses streaming (see Chap. 10), meaning that the memory
requirements are lessened because only one piece at a time is processed by a
task. But it does not work for all algorithms: some algorithms require all of
the data to be immediately available and this strategy does not make some
pieces available until later in the execution.
Static load balancing is a scheduling strategy that partitions the pieces over
the tasks before execution. This strategy is prone to load imbalance when the
time to process pieces is variable, impacting performance because the overall
execution time is only as fast as the slowest task. However, this strategy has
all of the data in memory at one time (spread out over the tasks), enabling
certain classes of algorithms.
Again, contracts enable choosing the optimal strategy. Consider the two
scheduling strategies just described. If an algorithm needs to have all of the
data available to proceed, it can indicate this by setting a Boolean in the
contract. Then, prior to execution, the parallel visualization framework can
decide which strategy to employ. If any algorithm needs the entire data set
available (and hence, set the Boolean in the contract), then the contract would
select static load balancing. If not, it could choose the faster, dynamic load
balancing.
22 High Performance Visualization
2.6 Conclusion
Parallel visualization frameworks address the large data problem by en-
abling the usage of additional parallel resources, which increases available
memory, compute power, and I/O bandwidth. Their parallelization strategies
divide the data into pieces over their tasks, with individual algorithms exe-
cuting in either embarrassingly or non-embarrassingly parallel manners. These
frameworks are then used to build applications with sophisticated architec-
tures, such as a client–server model with parallel visualization frameworks
built into the server. Finally, these frameworks serve as the foundation for
richly featured visualization tools, since they are flexible in usage, enabling
optimizations for scheduling strategies, data subsetting, and many more.
Parallel Visualization Frameworks 23
References
[1] Greg Abram and Lloyd A. Treinish. An Extended Data-Flow Architec-
ture for Data Analysis and Visualization. Research report RC 20001
(88338), IBM T. J. Watson Research Center, Yorktown Heights, NY,
USA, February 1995.
[2] Barbara Chapman, Gabriele Jost, and Ruud van der Pas. Using OpenMP:
Portable Shared Memory Parallel Programming (Scientific and Engineer-
ing Computation). The MIT Press, 2007.
[3] Hank Childs, Eric S. Brugger, Kathleen S. Bonnell, Jeremy S Meredith,
Mark Miller, Brad J Whitlock, and Nelson Max. A Contract-Based Sys-
tem for Large Data Visualization. In Proceedings of IEEE Visualization
2005, pages 190–198, 2005.
[4] Cyrus Harrison, Hank Childs, and Kelly P. Gaither. Data-Parallel Mesh
Connected Components Labeling and Analysis. In Proceedings of Euro-
Graphics Symposium on Parallel Graphics and Visualization, pages 131–
140, April 2011.
[5] C.R. Johnson, S. Parker, and D. Weinstein. Large-Scale Computational
Science Applications Using the SCIRun Problem Solving Environment.
In Proceedings of the 2000 ACM/IEEE Conference on Supercomputing,
2000.
[6] Wesley Kendall, Jian Huang, Tom Peterka, Rob Latham, and Robert
Ross. Visualization Viewpoint: Towards a General I/O Layer for Parallel
Visualization Applications. IEEE Computer Graphics and Applications,
31(6), 2011.
[7] Konstantinos Konstantinides and John R. Rasure. The Khoros Soft-
ware Development Environment for Image and Signal Processing. IEEE
Transactions on Image Processing, 3:243–252, 1994.
[8] Bradford Nichols, Dick Buttlar, and Jacqueline Proulx Farrell. Pthreads
Programming. O’Reilly & Associates, Inc., Sebastopol, CA, USA, 1996.
[9] William J. Schroeder, Kenneth M. Martin, and William E. Lorensen.
The Design and Implementation of an Object-Oriented Toolkit for 3D
Graphics and Visualization. In VIS ’96: Proceedings of the Conference
on Visualization ’96, pages 93–ff. IEEE Computer Society Press, 1996.
[10] Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack
Dongarra. MPI-The Complete Reference, Volume 1: The MPI Core.MIT
Press, Cambridge, MA, USA, 2nd. (revised) edition, 1998.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.