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
1 GRAPE will execute the classic O(N^2) (parallel) N body algorithm BUT this is not the algorithm used in most such computations
2 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)
3 So special purpose devices cannot usually take advantage of new nifty algorithms!
in Table To:

© on Tue Oct 7 1997