First two Solutions of O(N2) Computational Complexity
1) Ignore it and implement straightforwardly on a conventional computer
2) Note that one can build special purpose parallel machines as need less communication bandwidth (and just one dimensional pipeline) and much less memory per CPU power than for general purpose (parallel) computer
- parallel algorithm described in course incredibly efficient and can use inexpensive low bandwidth communication channels
- This is approach of GRAPE (Gravity Pipeline) machine which could be about a factor of 100 more cost effective for astrophysics on large problems
- Note memory is a major cost on most general purpose machines and needed ratio of memory to CPU much smaller for GRAPE than general purpose machine.
- GRAPE uses same parallel algorithm we described in course