Separate HTML for Basic Foil 42 Why isn't GRAPE a Perfect Solution?

Basic HTML version of Foils prepared 10 Sept 1996

Foil 42 Why isn't GRAPE a Perfect Solution?

From New CPS615Master Foils-- 26 August 96 Basic Simulation Track for Computational Science CPS615 -- Fall Semester 96. by Geoffrey C. Fox

GRAPE will execute the classic O(N^2) (parallel) N body algorithm BUT this is not the algorithm used in most such computations

Rather there is the O(N) or O(N)logN so called "fast-multipole" algorithm which uses hierarchical approach

On one million stars, fast multipole is a factor of 100-1000 faster than GRAPE algorithm
fast multipole works in most but not all N-body problems (in globular clusters, extreme heterogenity makes direct O(N^2) method most attractive)

So special purpose devices cannot usually take advantage of new nifty algorithms!