To calculate long-range potentials in a molecular dynamics simulation, a naive approach using direct particle interactions needs a computational work of order O(N2). This is infeasible for larger simulations. In order to reduce this complexity and thus allow to increase the size of the simulation, several algorithms have been proposed in the last decades. This thesis first gives an overview over these algorithms and examines the advantages and disadvantages of these methods with respect to high performance computing, i.e., how well they are suited for a good scalability on a many-processor system. Two algorithms that seem well suited for this task, the Multilevel Summation Method and the Meshed Continuum Method, both of which are based on a hierarchy of multiple grids, are implemented and optimized for a massively parallel environment. The mathematical foundation as well as the implementation steps to improve the performance and scalability of the algorithms are explained in detail. Finally the algorithms were tested with up to 8192 processors at PDC. The results of these runs are presented together with an explanation of possible performance bottlenecks and a final comparison of both algorithms / Ett naivt sätt att beräkna potentialer med lång räckvidd i molekylärdynamiska simulationer vore att använda direkta partikelinteraktioner som behöver ett beräkningsarbete av ordo O(N2). Det är inte genomförbart i större simulationer. Flera algoritmer föreslogs under de förra decennierna för att reducera komplexitäten och tillåta större beräkningar. I rapporten ges en översyn över dessa algoritmer och utredas för- och nackdelar med hänsyn till högprestandaberäkningar, d.v.s. skalerbarhet på system med flärkärnprocessorer. Två algoritmer, den s.k. Multilevel Summation Metod och den s.k. Meshed Continuum Method, tycks passa bra. Både metoder baseras på en hierarki av flera rutnät. Både kan implementeras och optimeras för massiv parallella system. De matematiska fundamenten och implementeringsstegen för att förbättra algoritmernas prestanda och skalerbarhet förklaras detaljerat. Algoritmerna testades med upp till 8192 processorer at PDC. Resultaten av dessa tester, förklaringar av möjliga orsaker för prestandaproblem samt en slutlig jämförelse av algoritmerna presenteras.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-124321 |
| Date | January 2013 |
| Creators | Rachinger, Christoph |
| Publisher | KTH, Numerisk analys, NA |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-MAT-E ; 2013:38 |
Page generated in 0.0017 seconds