research-article

Simplified parallel domain traversal

Authors:

Wesley Kendall,

David EricksonAuthors Info & Claims

SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 10, Pages 1 - 11

https://doi.org/10.1145/2063384.2063397

Published: 12 November 2011 Publication History

Abstract

Many data-intensive scientific analysis techniques require global domain traversal, which over the years has been a bottleneck for efficient parallelization across distributed-memory architectures. Inspired by MapReduce and other simplified parallel programming approaches, we have designed DStep, a flexible system that greatly simplifies efficient parallelization of domain traversal techniques at scale. In order to deliver both simplicity to users as well as scalability on HPC platforms, we introduce a novel two-tiered communication architecture for managing and exploiting asynchronous communication loads. We also integrate our design with advanced parallel I/O techniques that operate directly on native simulation output. We demonstrate DStep by performing teleconnection analysis across ensemble runs of terascale atmospheric CO₂ and climate data, and we show scalability results on up to 65,536 IBM BlueGene/P cores.

References

[1]

Boost C++ libraries. http://www.boost.org.

[2]

IDL: Interactive data language. http://www.ittvis.com/idl.

[3]

IOR benchmark. http://www.cs.sandia.gov/Scalable_IO/ior.html.

[4]

NCL: NCAR command language. http://www.ncl.ucar.edu.

[5]

Protocol Buffers: Google's data interchange format. http://code.google.com/p/protobuf.

[6]

Visit: Software that delivers parallel interactive visualization. https://wci.llnl.gov/codes/visit.

[7]

Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI '04: Sixth Symposium on Operating System Design and Implementation, 2004.

Digital Library

[8]

Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Communications of the ACM, 51:107--113, January 2008.

Digital Library

[9]

D. J. Erickson, R. T. Mills, J. Gregg, T. J. Blasing, F. M. Hoffman, R. J. Andres, M. Devries, Z. Zhu, and S. R. Kawa. An estimate of monthly global emissions of anthropogenic CO2: The impact on the seasonal cycle of atmospheric CO2. Journal of Geophysical Research, 113, 2007.

[10]

D. Galbally, K. Fidkowski, K. Willcox, and O. Ghattas. Non-linear model reduction for uncertainty quantification in large-scale inverse problems. International Journal for Numerical Methods in Engineering, 81(12):1581--1608, 2010.

[11]

Kui Gao, Wei keng Liao, Arifa Nisar, Alok Choudhary, Robert Ross, and Robert Latham. Using subfiling to improve programming flexibility and performance of parallel shared-file i/o. International Conference on Parallel Processing, pages 470--477, 2009.

Digital Library

[12]

A. Hannachi, I. T. Jolliffe, and D. B. Stephenson. Empirical orthoghonal functions and related techniques in atmospheric science: A review. International Journal of Climatology, 27:1119--1152, 2007.

[13]

T. Hoefler, A. Lumsdaine, and J. Dongarra. Towards efficient mapreduce using MPI. In Recent Advances in Parallel Virtual Machine and Message Passing Interface, 16th European PVM/MPI Users' Group Meeting. Springer, Sep. 2009.

Digital Library

[14]

Wesley Kendall, Markus Glatter, Jian Huang, Tom Peterka, Robert Latham, and Robert Ross. Terascale data organization for discovering multivariate climatic trends. In SC '09: Proceedings of ACM/IEEE Supercomputing 2009, Nov. 2009.

Digital Library

[15]

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), Nov./Dec. 2011.

Digital Library

[16]

Samuel Lang, Philip Carns, Robert Latham, Robert Ross, Kevin Harms, and William Allcock. I/O performance challenges at leadership scale. In SC '09: Proceedings of ACM/IEEE Supercomputing 2009, 2009.

Digital Library

[17]

S-J Lin. A "vertically lagrangian" finite-volume dynamical core for global models. Monthly Weather Review, 132:2293--2307.

[18]

Jay Lofstead, Fang Zheng, Qing Liu, Scott Klasky, Ron Oldfield, Todd Kordenbrock, Karsten Schwan, and Matthew Wolf. Managing variability in the I/O performance of petascale storage systems. In SC '10: Proceedings of ACM/IEEE Supercomputing 2010, 2010.

Digital Library

[19]

Grzegorz Malewicz, Matthew H. Austern, Aart J. C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 International Conference on Management of Data, SIGMOD '10, pages 135--146, 2010.

Digital Library

[20]

L. Ott, B. Duncan, S. Pawson, P. Colarco, M. Chin, C. Randles, T. Diehl, and E. Nielsen. Influence of the 2006 Indonesian biomass burning aerosols on tropical dynamics studied with the GEOS-5 AGCM. Journal of Geophysical Research, 115, 2010.

[21]

Tom Peterka, Robert Ross, B. Nouanesengsey, Teng-Yok Lee, Han-Wei Shen, Wesley Kendall, and Jian Huang. A study of parallel particle tracing for steady-state and time-varying flow fields. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2011.

Digital Library

[22]

Steven J. Plimpton and Karen D. Devine. Mapreduce in mpi for large-scale graph algorithms. 2011.

[23]

Dave Pugmire, Hank Childs, Christoph Garth, Sean Ahern, and Gunther H. Weber. Scalable computation of streamlines on very large datasets. In Proceedings of the 2009 ACM/IEEE conference on Supercomputing, 2009.

Digital Library

[24]

Kurt Stockinger, John Shalf, Kesheng Wu, and E. Wes Bethel. Query-Driven Visualization of Large Data Sets. In Proceedings of IEEE Visualization 2005, pages 167--174. IEEE Computer Society Press, October 2005. LBNL-57511.

[25]

Jeff Stuart and John Owens. Multi-GPU MapReduce on GPU clusters. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2011.

Digital Library

[26]

Tiankai Tu, Charles A. Rendleman, David W. Borhani, Ron O. Dror, Justin Gullingsrud, Morten Ø. Jensen, John L. Klepeis, Paul Maragakis, Patrick Miller, Kate A. Stafford, and David E. Shaw. A scalable parallel framework for analyzing terascale molecular dynamics simulation trajectories. In Proceedings of the 2008 ACM/IEEE conference on Supercomputing, SC '08, 2008.

Digital Library

[27]

Hongfeng Yu, Chaoli Wang, and Kwan-Liu Ma. Parallel hierarchical visualization of large time-varying 3d vector fields. In Proceedings of the 2007 ACM/IEEE conference on Supercomputing, SC '07, pages 1--24, 2007.

Digital Library

Cited By

Xu JGuo HShen HRaj MWurster SPeterka T(2023)Reinforcement Learning for Load-Balanced Parallel Particle TracingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.314874529:6(3052-3066)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TVCG.2022.3148745
Hobson THammer JProvins PHuang J(2023)Interactive Visualization of Large Turbulent Flow as a Cloud ServiceIEEE Transactions on Cloud Computing10.1109/TCC.2021.309138711:1(263-277)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3091387
Binyahib RPugmire DChilds HMoreland KGarth CBethel ERaffin B(2019)In situ particle advection via parallelizing over particlesProceedings of the Workshop on In Situ Infrastructures for Enabling Extreme-Scale Analysis and Visualization10.1145/3364228.3364235(29-33)Online publication date: 18-Nov-2019
https://dl.acm.org/doi/10.1145/3364228.3364235
Show More Cited By

Recommendations

The NYU Ultracomputer Designing an MIMD Shared Memory Parallel Computer

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate ...
Parallel asynchronous protocols on parallel and distributed systems
Composable Parallel Patterns with Intel Cilk Plus

Intel Cilk Plus extends C and C++ to enable writing composable deterministic parallel software that can exploit both the thread and vector parallelism commonly available in modern hardware.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

November 2011

866 pages

ISBN:9781450307710

DOI:10.1145/2063384

Conference Chair:
Scott Lathrop
University of Chicago
,
Program Chairs:
Jim Costa
Sandia National Laboratories
,
William Kramer
National Center for Supercomputing Applications

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC '11

Sponsor:

SIGARCH
IEEE-CS

SC '11: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 18, 2011

Washington, Seattle

Acceptance Rates

SC '11 Paper Acceptance Rate 74 of 352 submissions, 21%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
432
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu JGuo HShen HRaj MWurster SPeterka T(2023)Reinforcement Learning for Load-Balanced Parallel Particle TracingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.314874529:6(3052-3066)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TVCG.2022.3148745
Hobson THammer JProvins PHuang J(2023)Interactive Visualization of Large Turbulent Flow as a Cloud ServiceIEEE Transactions on Cloud Computing10.1109/TCC.2021.309138711:1(263-277)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3091387
Binyahib RPugmire DChilds HMoreland KGarth CBethel ERaffin B(2019)In situ particle advection via parallelizing over particlesProceedings of the Workshop on In Situ Infrastructures for Enabling Extreme-Scale Analysis and Visualization10.1145/3364228.3364235(29-33)Online publication date: 18-Nov-2019
https://dl.acm.org/doi/10.1145/3364228.3364235
Guo HHe WSeo SShen HConstantinescu ELiu CPeterka T(2019)Extreme-Scale Stochastic Particle Tracing for Uncertain Unsteady Flow Visualization and AnalysisIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.285677225:9(2710-2724)Online publication date: 1-Sep-2019
https://doi.org/10.1109/TVCG.2018.2856772
Binyahib RPugmire DNorris BChilds H(2019)A Lifeline-Based Approach for Work Requesting and Parallel Particle Advection2019 IEEE 9th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV48142.2019.8944355(52-61)Online publication date: Oct-2019
https://doi.org/10.1109/LDAV48142.2019.8944355
Pugmire DYenpure AKim MKress JMaynard RChilds HHentschel BHentschel BChilds HCucchietti F(2018)Performance-portable particle advection with VTK-mProceedings of the Symposium on Parallel Graphics and Visualization10.5555/3293524.3293528(45-55)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.5555/3293524.3293528
Zhang JGuo HHong FYuan XPeterka T(2018)Dynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle TracingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2017.274405924:1(954-963)Online publication date: Jan-2018
https://doi.org/10.1109/TVCG.2017.2744059
Zhang JGuo HYuan XPeterka T(2018)Dynamic Data Repartitioning for Load-Balanced Parallel Particle Tracing2018 IEEE Pacific Visualization Symposium (PacificVis)10.1109/PacificVis.2018.00019(86-95)Online publication date: Apr-2018
https://doi.org/10.1109/PacificVis.2018.00019
Hong FZhang JYuan X(2018)Access Pattern Learning with Long Short-Term Memory for Parallel Particle Tracing2018 IEEE Pacific Visualization Symposium (PacificVis)10.1109/PacificVis.2018.00018(76-85)Online publication date: Apr-2018
https://doi.org/10.1109/PacificVis.2018.00018
He WGuo HPeterka TDi SCappello FShen H(2018)Parallel Partial Reduction for Large-Scale Data Analysis and Visualization2018 IEEE 8th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV.2018.8739165(45-55)Online publication date: Oct-2018
https://doi.org/10.1109/LDAV.2018.8739165
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents