Divide-Conquer-Recombine: An Algorithmic Pathway toward Metascalability. Nakano, A., Hattori, S., Kalia, R. K., Mou, W., Nomura, K., Rajak, P., Vashishta, P., Shimamura, K., Shimojo, F., Kunaseth, M., Ohmura, S., Messina, P. C., & Romero, N. A. In PROCEEDINGS FROM THE 20 YEARS OF BEOWULF WORKSHOP, pages 17-26, 2015. 20 Years of Beowulf Workshop, Annapolis, MD, OCT 13-14, 2014doi abstract bibtex We propose an extension of the divide-and-conquer (DC) algorithmic paradigm called divide-conquer-recombine (DCR) in order to develop O(N) applications that will continue to scale on future parallel supercomputing, i.e., making them metascalable (or ``design once, scale on new architectures''). In DCR, the DC phase constructs globally informed local solutions, which in the recombine phase are synthesized into a global solution. Innovative recombination algorithms allow the synthesis of a variety of global properties in broad applications. To enable large spatial-scale molecular dynamics (MD) simulations, DCR-in-space is empowered by globally scalable and locally fast (GSLF) hybrid solvers based on spatial locality. In addition, DCR-in-time is used to predict long-time dynamics based on temporal locality, while utilizing space-time-ensemble parallelism (STEP). We have used DCR to perform quantum molecular dynamics (QMD) and reactive molecular dynamics (RMD) simulations that encompass unprecedented spatiotemporal scales. Our 50.3 million-atom QMD benchmark achieved a parallel efficiency of 0.984 and 50.5% of the peak floating-point performance on 786,432 IBM Blue Gene/Q cores. Production QMD simulation involving 16,661 atoms for 21,140 time steps (or 129,208 self-consistent-field iterations) revealed a novel nanostructural design for on-demand hydrogen production from water, advancing renewable energy technologies. Nonadiabatic QMD simulation of photoexcitation dynamics involving 6,400 atoms reached the experimental time scales, elucidating molecular mechanisms of a novel singlet-fission phenomenon to realize low-cost, high-efficiency solar cells. Our billion-atom RMD simulation revealed the role of focused nanojet for the damage of solid surface caused by shock-induced collapse of nanobubbles in water, and suggested how to mitigate the damage by filling the bubble with inert gas.
@inproceedings{ ISI:000455386500003,
Author = {Nakano, Aiichiro and Hattori, Shinnosuke and Kalia, Rajiv K. and Mou,
Weiwei and Nomura, Ken-ichi and Rajak, Pankaj and Vashishta, Priya and
Shimamura, Kohei and Shimojo, Fuyuki and Kunaseth, Manaschai and Ohmura,
Satoshi and Messina, Paul C. and Romero, Nichols A.},
Book-Group-Author = {{ACM}},
Title = {{Divide-Conquer-Recombine: An Algorithmic Pathway toward Metascalability}},
Booktitle = {{PROCEEDINGS FROM THE 20 YEARS OF BEOWULF WORKSHOP}},
Year = {{2015}},
Pages = {{17-26}},
Note = {{20 Years of Beowulf Workshop, Annapolis, MD, OCT 13-14, 2014}},
Abstract = {{We propose an extension of the divide-and-conquer (DC) algorithmic
paradigm called divide-conquer-recombine (DCR) in order to develop O(N)
applications that will continue to scale on future parallel
supercomputing, i.e., making them metascalable (or ``design once, scale
on new architectures{''}). In DCR, the DC phase constructs globally
informed local solutions, which in the recombine phase are synthesized
into a global solution. Innovative recombination algorithms allow the
synthesis of a variety of global properties in broad applications. To
enable large spatial-scale molecular dynamics (MD) simulations,
DCR-in-space is empowered by globally scalable and locally fast (GSLF)
hybrid solvers based on spatial locality. In addition, DCR-in-time is
used to predict long-time dynamics based on temporal locality, while
utilizing space-time-ensemble parallelism (STEP). We have used DCR to
perform quantum molecular dynamics (QMD) and reactive molecular dynamics
(RMD) simulations that encompass unprecedented spatiotemporal scales.
Our 50.3 million-atom QMD benchmark achieved a parallel efficiency of
0.984 and 50.5\% of the peak floating-point performance on 786,432 IBM
Blue Gene/Q cores. Production QMD simulation involving 16,661 atoms for
21,140 time steps (or 129,208 self-consistent-field iterations) revealed
a novel nanostructural design for on-demand hydrogen production from
water, advancing renewable energy technologies. Nonadiabatic QMD
simulation of photoexcitation dynamics involving 6,400 atoms reached the
experimental time scales, elucidating molecular mechanisms of a novel
singlet-fission phenomenon to realize low-cost, high-efficiency solar
cells. Our billion-atom RMD simulation revealed the role of focused
nanojet for the damage of solid surface caused by shock-induced collapse
of nanobubbles in water, and suggested how to mitigate the damage by
filling the bubble with inert gas.}},
DOI = {{10.1145/2737909.2737911}},
ISBN = {{978-1-4503-3031-2}},
Unique-ID = {{ISI:000455386500003}},
}
Downloads: 0
{"_id":"m2Rs3ZgN5oRL3X4xW","bibbaseid":"nakano-hattori-kalia-mou-nomura-rajak-vashishta-shimamura-etal-divideconquerrecombineanalgorithmicpathwaytowardmetascalability-2015","authorIDs":[],"author_short":["Nakano, A.","Hattori, S.","Kalia, R. K.","Mou, W.","Nomura, K.","Rajak, P.","Vashishta, P.","Shimamura, K.","Shimojo, F.","Kunaseth, M.","Ohmura, S.","Messina, P. C.","Romero, N. A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Nakano"],"firstnames":["Aiichiro"],"suffixes":[]},{"propositions":[],"lastnames":["Hattori"],"firstnames":["Shinnosuke"],"suffixes":[]},{"propositions":[],"lastnames":["Kalia"],"firstnames":["Rajiv","K."],"suffixes":[]},{"propositions":[],"lastnames":["Mou"],"firstnames":["Weiwei"],"suffixes":[]},{"propositions":[],"lastnames":["Nomura"],"firstnames":["Ken-ichi"],"suffixes":[]},{"propositions":[],"lastnames":["Rajak"],"firstnames":["Pankaj"],"suffixes":[]},{"propositions":[],"lastnames":["Vashishta"],"firstnames":["Priya"],"suffixes":[]},{"propositions":[],"lastnames":["Shimamura"],"firstnames":["Kohei"],"suffixes":[]},{"propositions":[],"lastnames":["Shimojo"],"firstnames":["Fuyuki"],"suffixes":[]},{"propositions":[],"lastnames":["Kunaseth"],"firstnames":["Manaschai"],"suffixes":[]},{"propositions":[],"lastnames":["Ohmura"],"firstnames":["Satoshi"],"suffixes":[]},{"propositions":[],"lastnames":["Messina"],"firstnames":["Paul","C."],"suffixes":[]},{"propositions":[],"lastnames":["Romero"],"firstnames":["Nichols","A."],"suffixes":[]}],"book-group-author":"ACM","title":"Divide-Conquer-Recombine: An Algorithmic Pathway toward Metascalability","booktitle":"PROCEEDINGS FROM THE 20 YEARS OF BEOWULF WORKSHOP","year":"2015","pages":"17-26","note":"20 Years of Beowulf Workshop, Annapolis, MD, OCT 13-14, 2014","abstract":"We propose an extension of the divide-and-conquer (DC) algorithmic paradigm called divide-conquer-recombine (DCR) in order to develop O(N) applications that will continue to scale on future parallel supercomputing, i.e., making them metascalable (or ``design once, scale on new architectures''). In DCR, the DC phase constructs globally informed local solutions, which in the recombine phase are synthesized into a global solution. Innovative recombination algorithms allow the synthesis of a variety of global properties in broad applications. To enable large spatial-scale molecular dynamics (MD) simulations, DCR-in-space is empowered by globally scalable and locally fast (GSLF) hybrid solvers based on spatial locality. In addition, DCR-in-time is used to predict long-time dynamics based on temporal locality, while utilizing space-time-ensemble parallelism (STEP). We have used DCR to perform quantum molecular dynamics (QMD) and reactive molecular dynamics (RMD) simulations that encompass unprecedented spatiotemporal scales. Our 50.3 million-atom QMD benchmark achieved a parallel efficiency of 0.984 and 50.5% of the peak floating-point performance on 786,432 IBM Blue Gene/Q cores. Production QMD simulation involving 16,661 atoms for 21,140 time steps (or 129,208 self-consistent-field iterations) revealed a novel nanostructural design for on-demand hydrogen production from water, advancing renewable energy technologies. Nonadiabatic QMD simulation of photoexcitation dynamics involving 6,400 atoms reached the experimental time scales, elucidating molecular mechanisms of a novel singlet-fission phenomenon to realize low-cost, high-efficiency solar cells. Our billion-atom RMD simulation revealed the role of focused nanojet for the damage of solid surface caused by shock-induced collapse of nanobubbles in water, and suggested how to mitigate the damage by filling the bubble with inert gas.","doi":"10.1145/2737909.2737911","isbn":"978-1-4503-3031-2","unique-id":"ISI:000455386500003","bibtex":"@inproceedings{ ISI:000455386500003,\nAuthor = {Nakano, Aiichiro and Hattori, Shinnosuke and Kalia, Rajiv K. and Mou,\n Weiwei and Nomura, Ken-ichi and Rajak, Pankaj and Vashishta, Priya and\n Shimamura, Kohei and Shimojo, Fuyuki and Kunaseth, Manaschai and Ohmura,\n Satoshi and Messina, Paul C. and Romero, Nichols A.},\nBook-Group-Author = {{ACM}},\nTitle = {{Divide-Conquer-Recombine: An Algorithmic Pathway toward Metascalability}},\nBooktitle = {{PROCEEDINGS FROM THE 20 YEARS OF BEOWULF WORKSHOP}},\nYear = {{2015}},\nPages = {{17-26}},\nNote = {{20 Years of Beowulf Workshop, Annapolis, MD, OCT 13-14, 2014}},\nAbstract = {{We propose an extension of the divide-and-conquer (DC) algorithmic\n paradigm called divide-conquer-recombine (DCR) in order to develop O(N)\n applications that will continue to scale on future parallel\n supercomputing, i.e., making them metascalable (or ``design once, scale\n on new architectures{''}). In DCR, the DC phase constructs globally\n informed local solutions, which in the recombine phase are synthesized\n into a global solution. Innovative recombination algorithms allow the\n synthesis of a variety of global properties in broad applications. To\n enable large spatial-scale molecular dynamics (MD) simulations,\n DCR-in-space is empowered by globally scalable and locally fast (GSLF)\n hybrid solvers based on spatial locality. In addition, DCR-in-time is\n used to predict long-time dynamics based on temporal locality, while\n utilizing space-time-ensemble parallelism (STEP). We have used DCR to\n perform quantum molecular dynamics (QMD) and reactive molecular dynamics\n (RMD) simulations that encompass unprecedented spatiotemporal scales.\n Our 50.3 million-atom QMD benchmark achieved a parallel efficiency of\n 0.984 and 50.5\\% of the peak floating-point performance on 786,432 IBM\n Blue Gene/Q cores. Production QMD simulation involving 16,661 atoms for\n 21,140 time steps (or 129,208 self-consistent-field iterations) revealed\n a novel nanostructural design for on-demand hydrogen production from\n water, advancing renewable energy technologies. Nonadiabatic QMD\n simulation of photoexcitation dynamics involving 6,400 atoms reached the\n experimental time scales, elucidating molecular mechanisms of a novel\n singlet-fission phenomenon to realize low-cost, high-efficiency solar\n cells. Our billion-atom RMD simulation revealed the role of focused\n nanojet for the damage of solid surface caused by shock-induced collapse\n of nanobubbles in water, and suggested how to mitigate the damage by\n filling the bubble with inert gas.}},\nDOI = {{10.1145/2737909.2737911}},\nISBN = {{978-1-4503-3031-2}},\nUnique-ID = {{ISI:000455386500003}},\n}\n\n","author_short":["Nakano, A.","Hattori, S.","Kalia, R. K.","Mou, W.","Nomura, K.","Rajak, P.","Vashishta, P.","Shimamura, K.","Shimojo, F.","Kunaseth, M.","Ohmura, S.","Messina, P. C.","Romero, N. A."],"key":"ISI:000455386500003","id":"ISI:000455386500003","bibbaseid":"nakano-hattori-kalia-mou-nomura-rajak-vashishta-shimamura-etal-divideconquerrecombineanalgorithmicpathwaytowardmetascalability-2015","role":"author","urls":{},"downloads":0},"bibtype":"inproceedings","biburl":"http://nanotec.cnr.it/data/nanotec/nanotec-full.bib","creationDate":"2020-04-22T21:25:44.045Z","downloads":0,"keywords":[],"search_terms":["divide","conquer","recombine","algorithmic","pathway","toward","metascalability","nakano","hattori","kalia","mou","nomura","rajak","vashishta","shimamura","shimojo","kunaseth","ohmura","messina","romero"],"title":"Divide-Conquer-Recombine: An Algorithmic Pathway toward Metascalability","year":2015,"dataSources":["ZTEbWc6bW5f9DTsjF"]}