TY - GEN
T1 - Parallel Partial Reduction for Large-Scale Data Analysis and Visualization
AU - He, Wenbin
AU - Guo, Hanqi
AU - Peterka, Tom
AU - Di, Sheng
AU - Cappello, Franck
AU - Shen, Han Wei
N1 - Funding Information:
This work is supported by the U.S. Department of Energy, Office of Advanced Scientific Computing Research, Scientific Discovery through Advanced Computing (SciDAC) program. This material is also based upon work supported by the U.S. Department of Energy, Office of Science, under contract number DE-AC02-06CH11357. This research used resources of the Argonne Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC02-06CH11357.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/10
Y1 - 2018/10
N2 - We present a novel partial reduction algorithm to aggregate sparsely distributed intermediate results that are generated by data-parallel analysis and visualization algorithms. Applications of partial reduction include flow trajectory analysis, big data online analytical processing, and volume rendering. Unlike traditional full parallel reduction that exchanges dense data across all processes, the purpose of partial reduction is to exchange only intermediate results that correspond to the same query, such as line segments of the same flow trajectory. To this end, we design a three-stage algorithm that minimizes the communication cost: (1) partitioning the result space into groups; (2) constructing and optimizing the reduction partners for each group; and (3) initiating collective reduction operations for all groups concurrently. Both theoretical and empirical analyses show that our algorithm outperforms the traditional methods when the intermediate results are sparsely distributed. We also demonstrate the effectiveness of our algorithm for flow visualization, big log data analysis, and volume rendering.
AB - We present a novel partial reduction algorithm to aggregate sparsely distributed intermediate results that are generated by data-parallel analysis and visualization algorithms. Applications of partial reduction include flow trajectory analysis, big data online analytical processing, and volume rendering. Unlike traditional full parallel reduction that exchanges dense data across all processes, the purpose of partial reduction is to exchange only intermediate results that correspond to the same query, such as line segments of the same flow trajectory. To this end, we design a three-stage algorithm that minimizes the communication cost: (1) partitioning the result space into groups; (2) constructing and optimizing the reduction partners for each group; and (3) initiating collective reduction operations for all groups concurrently. Both theoretical and empirical analyses show that our algorithm outperforms the traditional methods when the intermediate results are sparsely distributed. We also demonstrate the effectiveness of our algorithm for flow visualization, big log data analysis, and volume rendering.
KW - I.3.1 [COMPUTER GRAPHICS]: Hardware Architecture-Parallel processing
KW - I.3.2 [COMPUTER GRAPHICS]: Graphics Systems-Distributed/network graphics
UR - http://www.scopus.com/inward/record.url?scp=85068827896&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068827896&partnerID=8YFLogxK
U2 - 10.1109/LDAV.2018.8739165
DO - 10.1109/LDAV.2018.8739165
M3 - Conference contribution
AN - SCOPUS:85068827896
T3 - 2018 IEEE 8th Symposium on Large Data Analysis and Visualization, LDAV 2018
SP - 45
EP - 55
BT - 2018 IEEE 8th Symposium on Large Data Analysis and Visualization, LDAV 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 8th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2018
Y2 - 21 October 2018
ER -