Load balancing and data locality in adaptive hierarchical \(N\)-body methods: Barnes-Hut, fast multipole, and radiosity (Q1898222)

Partitioning and scheduling issues in representative applications that use three important hierarchical \(N\)-body methods are studied. Two of these methods, the Barnes-Hut method and the fast multipole method, have been used for galactic simulation studying the evolution of a system of particles. The third method is a recent hierarchical method for radiosity calculations in computer graphics, which applies the hierarchical \(N\)-body approach to a problem with very different characteristics. The focus of the study is on partitioning/scheduling techniques that simultaneously give load balancing and exploit data locality.