NDLI: Communication-Optimal Parallel N-body Solvers

Content Provider	IEEE Xplore Digital Library
Author	Chandramowlishwaran, A. Vuduc, R.W.
Copyright Year	2012
Abstract	We present new analysis, algorithmic techniques, and implementations of the Fast Multipole Method (FMM) for solving N-body problems. Our research specifically addresses two key challenges. The first challenge is how to engineer fast code for today's platforms. We present the first in-depth study of multicore optimizations and tuning for FMM, along with a systematic approach for transforming a conventionally parallelized FMM into a highly-tuned one. We introduce novel optimizations that significantly improve the within-node scalability of the FMM, thereby enabling high-performance in the face of multicore and many core systems. The second challenge is how to understand scalability on future systems. We present a new algorithmic complexity analysis of the FMM that considers both intra- and inter-node communication costs. This analysis yields the surprising prediction that although the FMM is largely compute-bound today, and therefore highly scalable on current systems, the trajectory of processor architecture designs -- if there are no significant changes -- could cause it to become communication-bound as early as the year 2020. This prediction suggests the utility of our analysis approach, which directly relates algorithmic and architectural characteristics, for enabling a new kind of high-level algorithm-architecture co-design.
Starting Page	2462
Ending Page	2465
File Size	383586
Page Count	4
File Format	PDF
ISBN	9781467309745
DOI	10.1109/IPDPSW.2012.303
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Multicore processing Computational modeling Scalability Predictive models Tuning Optimization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Performance Tuning on Multicore Systems for Feature Matching within Image Collections

Performance Analysis of a Multithreaded PDES Simulator on Multicore Clusters

POSTER: “Analysis of scalability: A parallel application model approach”

Parallel program performance modeling for runtime optimization of multi-algorithm circuit simulation

Design and Performance of a Scalable, Parallel Statistics Toolkit

A Parallel Implementation of Multiobjective Particle Swarm Optimization Algorithm Based on Decomposition

Parallel simulations of optical communication systems

Product recommendations using linear predictive modeling

Communication-Optimal Parallel N-body Solvers

Communication-Optimal Parallel N-body Solvers

Similar Documents

Performance Tuning on Multicore Systems for Feature Matching within Image Collections

Performance Analysis of a Multithreaded PDES Simulator on Multicore Clusters

POSTER: “Analysis of scalability: A parallel application model approach”

Parallel program performance modeling for runtime optimization of multi-algorithm circuit simulation

Design and Performance of a Scalable, Parallel Statistics Toolkit

A Parallel Implementation of Multiobjective Particle Swarm Optimization Algorithm Based on Decomposition

Parallel simulations of optical communication systems

Product recommendations using linear predictive modeling

Communication-Optimal Parallel N-body Solvers

Communication-Optimal Parallel N-body Solvers