Implications of Hierarchical N-Body Methods for Multiprocessor Architectures

Jaswinder Pal Singh, John L. Hennessy, Anoop Gupta

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


To design effective large-scale multiprocessors, designers need to understand the characteristics of the applications that will use the machines. Application characteristics of particular interest include the amount of communication relative to computation, the structure of the communication, and the local cache and memory requirements, as well as how these characteristics scale with larger problems and machines. One important class of applications is based on hierarchical N-body methods, which are used to solve a wide range of scientific and engineering problems efficiently. Important characteristics of these methods include the nonuniform and dynamically changing nature of the domains to which they are applied, and their use of long-range, irregular communication. This article examines the key architectural implications of representative applications that use the two dominant hierarchical N-body methods: the Barnes-Hut Method and the Fast Multipole Method. We first show that exploiting temporal locality on accesses to communicated data is critical to obtaining good performance on these applications and then argue that coherent caches on shared-address-space machines exploit this locality both automatically and very effectively. Next, we examine the implications of scaling the applications to run on larger machines. We use scaling methods that reflect the concerns of the application scientist and find that this leads to different conclusions about how communication traffic and local cache and memory usage scale than scaling based only on data set size. In particular, we show that under the most realistic form of scaling, both the communication-to-computation ratio as well as the working-set size 1995 grow slowly as larger problems are run on larger machines. Finally, we examine the effects of using the two dominant abstractions for interprocessor communication: a shared address space and explicit message passing between private address spaces. We show that the lack of an efficiently supported shared address space will substantially increase the programming complexity and performance overheads for these applications.

Original languageEnglish (US)
Pages (from-to)141-202
Number of pages62
JournalACM Transactions on Computer Systems (TOCS)
Issue number2
StatePublished - Jan 5 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • N-body methods
  • communication abstractions
  • locality
  • message passing
  • parallel applications
  • parallel computer architecture
  • scaling
  • shared address space
  • shared memory


Dive into the research topics of 'Implications of Hierarchical N-Body Methods for Multiprocessor Architectures'. Together they form a unique fingerprint.

Cite this