214 High Performance Visualization
data parallelism wherein the same operations are performed simultaneously
on different data items. Examples of functional parallelism include overlap-
ping asynchronous requests for data with rendering, as occurs in out-of-core
rendering systems [8, 29], and causing modules along a visualization pipeline
to operate on different portions simultaneously [34]. This is called pipeline
parallelism.
Vo et al. [36] added streamed, pipelined parallel processing to VTK by
scheduling module execution in a push pipeline. They found that a push
pipeline can have less overhead than a pull pipeline, because a pull pipeline
must stall the entire pipeline to obtain an up-to-date result. In a push pipeline,
the end-to-end delay is lower, because filters can process data portions as soon
as they become ready. In general, asynchrony allows the pipeline to overcome
serial bottlenecks. Ideally, an N element long pipeline will yield an N times
speedup when run on N pipelined processors. In a test, Vo’s asynchronous
VTK approach achieved 77% parallel efficiency on eight threads where the
standard VTK achieved only 41.8%.
10.4.5 Lazy Evaluation
Lazy evaluation is a variation on streamed visualization in which compu-
tations are aggregated and performed on demand so that unimportant data
is not considered. For example, with the Demand Driven Visualizer [23, 24]
system, when the user computes derived quantities for data values that lie on
a slicing plane, only the data values on the plane are fed into the expression.
No time is wasted in evaluating the expression for the majority of the values
in the data, which do not happen to lie on the plane.
The Demand Driven Visualizer makes sparse traversal part of its core data
access architecture. Paged modules and time dependent modules service re-
quests for data in space and time by loading the requested pages from external
memory on demand and managing the removal of unused pages transparently.
Data accessors are layered so that arbitrarily derived expressions can be com-
puted without requiring the expression to be evaluated over the entire domain.
A cached accessor class ensures that results can be reused many times with-
out an additional I/O, once they are computed initially. A set of visualization
modules, built on top of the sparse memory access API, produce images par-
simoniously.
Duke et al. [12, 11] implement a lazily evaluated streamed visualization
system within Haskell, a functional language with built-in support for a lazy
evaluation. The key insight is that demand-driven pipelines and streaming are
naturally expressed within lazy evaluated functional languages. In an object-
oriented language, visualization modules may be implemented as a class with
methods to connect the modules together, to compute a result, and to commu-
nicate results across the module connections. Important optimizations, such
as reusing completed results and working in a streaming fashion, add consid-
erable code complexity. In a lazy evaluated functional language, a pipeline is
Streaming and Out-of-Core Methods 215
expressed simply as: render(contour(readfile())). The implementation of
each function or processing module is restricted to the specific algorithm while
the language handles the details of connecting modules together, evaluating
and passing results between modules.
In the evaluation of their visualization system in Haskell, the result was a
fine-grained streaming visualization system that scaled to large data sizes by
minimizing memory consumption. In the comparison of isocontouring perfor-
mance and VTK, the study results show that although isocontouring perfor-
mance for small data suffered, with large enough data the streaming approach
was faster, and it had a smaller memory footprint because both the input
and output data sizes were constrained. A 128MB volume that produced a
199 million-vertex isosurface took 517 seconds in the functional approach and
consumed 8.35MB of RAM, while the VTK implementation took 755 seconds
and consumed 1.27GB of RAM because of the complex output surface.
In terms of the streaming taxonomy, these operate on a finite stream and
partition, both in the geometric and temporal domains, at a fine level of
granularity. They stream data from external memory to the processing pipeline
asynchronously.
10.5 Conclusion
This chapter has given an overview of streaming, including hazards and a
potential optimization. By surveying multiple works, this chapter recognizes
the effectiveness of the streaming technique in a variety of settings. In entering
the era of exascale computing, the streaming technique is likely to become
more widespread. The generation of supercomputers that will come online
soon will produce even larger data sets than today’s generation, and they will
have less random access memory (RAM) associated with and tied more tightly
to each processing element. In this setting the streaming concepts of piecemeal
processing, with parsimonious data traversal and remote delivery become even
more appealing. One might envision a complete solution consisting of a true
asynchronous data flow system, where the modules operate simultaneously on
fine-grained data streams, which allow for arbitrary processing of arbitrary
scientific data of an unlimited size.
216 High Performance Visualization
References
[1] J. Ahrens, K. Brislawn, K. Martin, B. Geveci, C. Law, and M. Papka.
Large-Scale Data Visualization Using Parallel Data Streaming. IEEE
Computer Graphics and Applications, 21:34–41, August 2001.
[2] J. Ahrens, N. Desai, P. McCormick, K. Martin, and J. Woodring. A Mod-
ular Extensible Visualization System Architecture for Culled Prioritized
Data Streaming. In Society of Photo-Optical Instrumentation Engineers
(SPIE) Conference Series, volume 6495, January 2007.
[3] J. Ahrens, J. Woodring, D. DeMarle, J. Patchett, and M. Maltrud. In-
teractive Remote Large-Scale Data Visualization Via Prioritized Multi-
Resolution Streaming. In Proceedings of the 2009 Workshop on Ultrascale
Visualization (UltraVis ’09), pages 1–10. ACM, 2009.
[4] J. Biddiscombe, B. Geveci, K. Martin, K. Moreland, and D. Thomp-
son. Time Dependent Processing in a Parallel Pipeline Architecture.
IEEE Transactions on Visualization and Computer Graphics, 13:1376–
1383, November 2007.
[5] Yi-Jen Chiang, C. Silva, and W. Schroeder. Interactive Out-Of-Core
Isosurface Extraction. Proceedings of IEEE Conference on Visualization
(Vis’98), pages 167–174, 1998.
[6] Yi-Jen Chiang and C.T. Silva. I/O Optimal Isosurface Extraction. Pro-
ceedings of IEEE Conference on Visualization (Vis97), pages 293–300,
1997.
[7] Hank Childs, Eric S. Brugger, Kathleen S. Bonnell, Jeremy S. Meredith,
Mark Miller, Brad J. Whitlock, and Nelson Max. A Contract Based
System For Large Data Visualization. Proceedings of IEEE Conference
on Visualization 2005 (Vis05), pages 190–198, 2005.
[8] W. Corrˆea, J. Klosowski, and C. Silva. iWalk: Interactive Out-of-Core
Rendering of Large Models. Technical report, University of Utah, 2002.
[9] Michael Cox and David Ellsworth. Application-Controlled Demand Pag-
ing for Out-of-Core Visualization. In Proceedings of the IEEE Conference
on Visualization (Vis’97), pages 235–244, Los Alamitos, CA, USA, 1997.
IEEE Computer Society Press.
[10] D. DeMarle, J. Woodring, and J. Ahrens. Multi-Resolution Streaming in
VTK and ParaView. The Kitware Source, 1(15):13–15, Oct. 2010.
[11] D. Duke, R. Borgo, M. Wallace, and C. Runciman. Huge Data But
Small Programs: Visualization Design via Multiple Embedded DSLs. In
Streaming and Out-of-Core Methods 217
Proceedings of the 11th International Symposium on Practical Aspects of
Declarative Languages (PADL ’09), pages 31–45, 2009.
[12] D. Duke, M. Wallace, R. Borgo, and C. Runciman. Fine-Grained Visu-
alization Pipelines and Lazy Functional Languages. IEEE Transactions
on Visualization and Computer Graphics, 12:973–980, 2006.
[13] Enrico Gobbetti and Fabio Marton. Far Voxels: a Multiresolution Frame-
work for Interactive Rendering of Huge Complex 3D Models on Commod-
ity Graphics Platforms. In ACM SIGGRAPH ASIA 2008 Courses, pages
32:1–32:8, 2008.
[14] Robert B. Haber, David A. McNabb, and Robert A. Ellis. Eliminating
Distance in Scientific Computing: An Experiment in Televisualization.
International Journal of Supercomputing Applications and High Perfor-
mance Engineering, 4(4):71–89, December 1990.
[15] L. Ib´a˜nez, W. Schroeder, L. Ng, and J. Cates. Streaming Large Data. In
The ITK Software Guide, pages 743–748. Kitware, 2nd edition, 2005.
[16] M. Isenburg, P. Lindstrom, and H. Childs. Parallel and Streaming Gen-
eration of Ghost Data for Structured Grids. IEEE Computer Graphics
and Applications, 30:32–44, May 2010.
[17] M. Isenburg, P. Lindstrom, and J. Snoeyink. Streaming Compression
of Triangle Meshes. In Proceedings of the EuroGraphics Symposium on
Geometry Processing, pages 111–118, July 2005.
[18] M. Isenburg, Y. Liu, J. Shewchuk, and J. Snoeyink. Streaming Compu-
tation of Delaunay Triangulations. In ACM SIGGRAPH 2006 Papers,
SIGGRAPH ’06, pages 1049–1056, 2006.
[19] Martin Isenburg and Peter Lindstrom. Streaming Meshes. Proceedings
of IEEE Conference on Visualization (Vis05), pages 231–238, 2005.
[20] J. Kim, S. Lee, and L. Kobbelt. View-Dependent Streaming of Progressive
Meshes. In Proceedings of the Shape Modeling International 2004, pages
209–220, 2004.
[21] C. Charles Law, W. Schroeder, K. Martin, and J. Temkin. A Multi-
Threaded Streaming Pipeline Architecture for Large Structured Data
Sets. In Proceedings of the IEEE Conference on Visualization (Vis’99),
pages 225–232, 1999.
[22] D. Lipsa, R. Laramee, R. Bergeron, and T. Sparr. Techniques for Large
Data Visualization. International Journal of Research and Reviews in
Computer Science, 2:315–322, 2011.
218 High Performance Visualization
[23] P. Moran and C. Henze. Large Field Visualization with Demand-Driven
Calculation. In Proceedings of the IEEE Conference on Visualization
(Vis’99), pages 27–33, 1999.
[24] Patrick J Moran. Field Model: An Object-Oriented Data Model for
Fields. Technical report, NASA Ames Research Center, 2001.
[25] Renato Pajarola. Stream Processing Points. Proceedings of IEEE Con-
ference on Visualization (Vis05), pages 239–246, 2005.
[26] V. Pascucci and R. Frank. Hierarchical Indexing for Out-of-Core Access
to Multi-Resolution Data. Technical report, LLNL, 2001.
[27] S. Prohaska, A. Hutanu, R. Kahler, and H. Hege. Interactive Exploration
of Large Remote Micro-CT Scans. In Proceedings of the IEEE Conference
on Visualization (Vis’04), pages 345–352, 2004.
[28] Szymon Rusinkiewicz and Marc Levoy. QSplat: a Multiresolution Point
Rendering System for Large Meshes. In Proceedings of SIGGRAPH, pages
343–352, 2000.
[29] Szymon Rusinkiewicz and Marc Levoy. Streaming QSplat: a Viewer for
Networked Visualization of Large, Dense Models. In Proceedings of the
Symposium on Interactive 3D Graphics (I3D’01), pages 63–68, 2001.
[30] W. Schroeder, H. Martin, and B. Lorensen. The Visualization Toolkit.
Kitware, 1996.
[31] C. Silva, Y. Chiang, J. El-sana, and P. Lindstrom. Out-of-Core Algo-
rithms for Scientific Visualization and Computer Graphics. In IEEE
Visualization Course Notes, 2002.
[32] Deyang Song and Eric Golin. Fine-Grain Visualization Algorithms in
Dataflow Environments. In Proceedings of the IEEE Conference on Vi-
sualization (Vis93), pages 126–133, 1993.
[33] Robert Stephens. A Survey of Stream Processing. Acta Informatica,
34:491–541, 1997. 10.1007/s002360050095.
[34] A. Varchola, A. Vaˇsko, V. Solˇc´any, L. Dimitrov, and M
ˇ
Sr´amek. Pro-
cessing of Volumetric Data by Slice- and Process-Based Streaming. In
Proceedings of the 5th International Conference on Computer Graphics,
Virtual Reality, Visualisation and Interaction in Africa, AFRIGRAPH
’07, pages 101–110, 2007.
[35] Jeffrey Scott Vitter. External Memory Algorithms and Data Structures:
Dealing with Massive Data. ACM Computing Surveys, 33:209–271, June
2001.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.