2016
Carr, Hamish; Weber, Gunther H.; Sewell, Christopher; Ahrens, James
Parallel Peak Pruning for Scalable SMP Contour Tree Computation Proceedings Article
In: 2016 IEEE 6th Symposium on Large Data Analysis and Visualization (LDAV) , IEEE 2016, (LA-UR-16-24454).
Abstract | Links | BibTeX | Tags: contour tree
@inproceedings{Carr2016,
title = {Parallel Peak Pruning for Scalable SMP Contour Tree Computation},
author = {Hamish Carr and Gunther H. Weber and Christopher Sewell and James Ahrens},
url = {http://datascience.dsscale.org/wp-content/uploads/2016/11/ParallelPeakPruningForScalableSMPContourTreeComputation2.pdf},
year = {2016},
date = {2016-10-23},
booktitle = {2016 IEEE 6th Symposium on Large Data Analysis and Visualization (LDAV) },
organization = {IEEE},
abstract = {As data sets grow to exascale, automated data analysis and visu- alisation are increasingly important, to intermediate human under- standing and to reduce demands on disk storage via in situ anal- ysis. Trends in architecture of high performance computing sys- tems necessitate analysis algorithms to make effective use of com- binations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses rela- tionships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for com- puting the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analy- sis. While there is some work on distributed contour tree computa- tion, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with for- mal guarantees of O(lgnlgt) parallel steps and O(nlgn) work, and implementations with up to 10⇥ parallel speed up in OpenMP and up to 50⇥ speed up in NVIDIA Thrust.},
note = {LA-UR-16-24454},
keywords = {contour tree},
pubstate = {published},
tppubtype = {inproceedings}
}
As data sets grow to exascale, automated data analysis and visu- alisation are increasingly important, to intermediate human under- standing and to reduce demands on disk storage via in situ anal- ysis. Trends in architecture of high performance computing sys- tems necessitate analysis algorithms to make effective use of com- binations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses rela- tionships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for com- puting the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analy- sis. While there is some work on distributed contour tree computa- tion, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with for- mal guarantees of O(lgnlgt) parallel steps and O(nlgn) work, and implementations with up to 10⇥ parallel speed up in OpenMP and up to 50⇥ speed up in NVIDIA Thrust.
2015
Carr, Hamish; Sewell, Christopher; Lo, Li-Ta; james Ahrens,
Hybrid Data-Parallel Contour Tree Computation Proceedings Article
In: 2015, (LA-UR-15-24759).
Abstract | Links | BibTeX | Tags: and object reppresentations, computational geometry and object modeling, contour tree, data-parallel, gpu, multi-core, nvidia thrust, simulation output analysis, solid, surface, topological analysis
@inproceedings{Carr2015,
title = {Hybrid Data-Parallel Contour Tree Computation},
author = {Hamish Carr and Christopher Sewell and Li-Ta Lo and james Ahrens},
url = {http://datascience.dsscale.org/wp-content/uploads/2016/06/HybridData-ParallelContourTreeComputaion.pdf},
year = {2015},
date = {2015-01-01},
number = {LA-UR-15-24759},
institution = {Los Alamos National Laboratory},
abstract = {As data sets increase in size beyond the petabyte, it is increasingly important to have automated methods for data analysis and visualization. While topological analysis tools such as the contour tree and Morse-Smale complex are now well established, there is still a shortage of efficient parallel algorithms for their computation, in particular for massively data-parallel computation on a SIMD model. We report the first data-parallel algorithm for computing the fully augmented contour tree, using a quantized computation model. We then extend this to provide a hybrid data-parallel / distributed algorithm allowing scaling beyond a single GPU or CPU, and provide results for its computation. Our implementation uses the portable data-parallel primitives provided by Nvidia’s Thrust library, allowing us to compile our same code for both GPUs and multi-core CPUs.},
note = {LA-UR-15-24759},
keywords = {and object reppresentations, computational geometry and object modeling, contour tree, data-parallel, gpu, multi-core, nvidia thrust, simulation output analysis, solid, surface, topological analysis},
pubstate = {published},
tppubtype = {inproceedings}
}
As data sets increase in size beyond the petabyte, it is increasingly important to have automated methods for data analysis and visualization. While topological analysis tools such as the contour tree and Morse-Smale complex are now well established, there is still a shortage of efficient parallel algorithms for their computation, in particular for massively data-parallel computation on a SIMD model. We report the first data-parallel algorithm for computing the fully augmented contour tree, using a quantized computation model. We then extend this to provide a hybrid data-parallel / distributed algorithm allowing scaling beyond a single GPU or CPU, and provide results for its computation. Our implementation uses the portable data-parallel primitives provided by Nvidia’s Thrust library, allowing us to compile our same code for both GPUs and multi-core CPUs.
: . .
1.
Carr, Hamish; Weber, Gunther H.; Sewell, Christopher; Ahrens, James
Parallel Peak Pruning for Scalable SMP Contour Tree Computation Proceedings Article
In: 2016 IEEE 6th Symposium on Large Data Analysis and Visualization (LDAV) , IEEE 2016, (LA-UR-16-24454).
@inproceedings{Carr2016,
title = {Parallel Peak Pruning for Scalable SMP Contour Tree Computation},
author = {Hamish Carr and Gunther H. Weber and Christopher Sewell and James Ahrens},
url = {http://datascience.dsscale.org/wp-content/uploads/2016/11/ParallelPeakPruningForScalableSMPContourTreeComputation2.pdf},
year = {2016},
date = {2016-10-23},
booktitle = {2016 IEEE 6th Symposium on Large Data Analysis and Visualization (LDAV) },
organization = {IEEE},
abstract = {As data sets grow to exascale, automated data analysis and visu- alisation are increasingly important, to intermediate human under- standing and to reduce demands on disk storage via in situ anal- ysis. Trends in architecture of high performance computing sys- tems necessitate analysis algorithms to make effective use of com- binations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses rela- tionships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for com- puting the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analy- sis. While there is some work on distributed contour tree computa- tion, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with for- mal guarantees of O(lgnlgt) parallel steps and O(nlgn) work, and implementations with up to 10⇥ parallel speed up in OpenMP and up to 50⇥ speed up in NVIDIA Thrust.},
note = {LA-UR-16-24454},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
As data sets grow to exascale, automated data analysis and visu- alisation are increasingly important, to intermediate human under- standing and to reduce demands on disk storage via in situ anal- ysis. Trends in architecture of high performance computing sys- tems necessitate analysis algorithms to make effective use of com- binations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses rela- tionships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for com- puting the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analy- sis. While there is some work on distributed contour tree computa- tion, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with for- mal guarantees of O(lgnlgt) parallel steps and O(nlgn) work, and implementations with up to 10⇥ parallel speed up in OpenMP and up to 50⇥ speed up in NVIDIA Thrust.
2.
Carr, Hamish; Sewell, Christopher; Lo, Li-Ta; james Ahrens,
Hybrid Data-Parallel Contour Tree Computation Proceedings Article
In: 2015, (LA-UR-15-24759).
@inproceedings{Carr2015,
title = {Hybrid Data-Parallel Contour Tree Computation},
author = {Hamish Carr and Christopher Sewell and Li-Ta Lo and james Ahrens},
url = {http://datascience.dsscale.org/wp-content/uploads/2016/06/HybridData-ParallelContourTreeComputaion.pdf},
year = {2015},
date = {2015-01-01},
number = {LA-UR-15-24759},
institution = {Los Alamos National Laboratory},
abstract = {As data sets increase in size beyond the petabyte, it is increasingly important to have automated methods for data analysis and visualization. While topological analysis tools such as the contour tree and Morse-Smale complex are now well established, there is still a shortage of efficient parallel algorithms for their computation, in particular for massively data-parallel computation on a SIMD model. We report the first data-parallel algorithm for computing the fully augmented contour tree, using a quantized computation model. We then extend this to provide a hybrid data-parallel / distributed algorithm allowing scaling beyond a single GPU or CPU, and provide results for its computation. Our implementation uses the portable data-parallel primitives provided by Nvidia’s Thrust library, allowing us to compile our same code for both GPUs and multi-core CPUs.},
note = {LA-UR-15-24759},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
As data sets increase in size beyond the petabyte, it is increasingly important to have automated methods for data analysis and visualization. While topological analysis tools such as the contour tree and Morse-Smale complex are now well established, there is still a shortage of efficient parallel algorithms for their computation, in particular for massively data-parallel computation on a SIMD model. We report the first data-parallel algorithm for computing the fully augmented contour tree, using a quantized computation model. We then extend this to provide a hybrid data-parallel / distributed algorithm allowing scaling beyond a single GPU or CPU, and provide results for its computation. Our implementation uses the portable data-parallel primitives provided by Nvidia’s Thrust library, allowing us to compile our same code for both GPUs and multi-core CPUs.