The Many Body Problem: Perspective on Performance

• Presentation by Sunil Sitaula and Amartey Pearson
• Halloween 1997

Contents

Source:

• Bentley, Jon Programming Pearls, Column 5
• Appel, Andrew SIAM Journal on Scientific and Statistical Computing 6, 1, pp. 85-103, January 1985

General Program Performance

• Importance of programmer time
• Efficiency of present day computers
• Microsoft example

Introduction of problem faced by Appel

• The many-body simulation
• Time requirement
• O(N²) to O(N LogN)

Design Levels

• Problem Definition
• System Structure
• Algorithms and Data Structures
• Code Tuning
• System Software
• Hardware

Implementation of Design Levels

• Reduction of algorithm to O(N LogN)
• Reduction of time steps taken
• Data structure reorganization
• Addition of hardware
• Hand optimization of code

Conclusion

• Speedup factors
• Comparison with todays computers
• Question & comments

Related Links

• Andrew Appel's Home Page
• Jon Bentley's Home Page
• Simulation Image (black and white)
• Simulation Image (color)