Datenlokale Iterationsverfahren zur effizienten Lösung partieller Differentialgleichungen

• Applicant: Professor Dr. Ulrich Rüde
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: from 1997 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5302800

• Final Report Year: 2008

Final Report Abstract

Im vorhergehenden ,,DiME" wurden verschiedene Cache- und Speicherlayout-Optimierungen zur effizienten Lösung partieller Differentialgleichungen mit Hilfe datenlokaler Iterationsverfahren untersucht. Dabei wurden v. a. RISC-Architekturen (wie Alpha-Prozessoren) als Grundlage benutzt, und es stand die Suche nach möglichen Optimierungsstrategien im Vordergrund. Im vorliegenden Projekt ,,DiME-2" wurde erkannt, dass eine naive Nutzung dieser Strategien auf heutigen Prozessoren, insbesondere der x86-Architektur, häufig nicht erfolgreich ist, da komplexe Architektureigenschaften, die zu der enormen Leistungsfähigkeit wesentlich beitragen, nicht berücksichtigt werden. Dazu zählen automatische Vorauslademechanismen und die dabei verwendeten Heuristiken, die Abhängigkeit der verfügbaren Speicherleistung von Zugriffsmustern und die Erweiterung um Vektoreinheiten (SIMD). Cache- und Speicherlayout-Optimierungen - so wie sie bereits in DiME empfohlen werden - können aber zu teils großen Leistungssteigerungen führen, wenn sie unter stärkerer Berücksichtigung der jeweiligen Zielarchitektur angewandt werden, was mitunter zeitaufwendig handoptimierten Assemblercode erfordert. Neben Blocking- Techniken, die eine möglichst häufige Nutzung von in den Cache geladenen Daten ermöglichen, ist die Maximierung der effektiven Speicherbandbreite entscheidend. Je nach Architektur und Anwendung sind hier ein günstiges Speicherlayout, die Einstreuung von Vorausladeoperationen oder sogar die Verwendung dedizierter Threads sinnvoll, die den effizienten Speicherzugriff übernehmen. Eine zweischneidige Entwicklung wurde bei den Compilern festgestellt, die viele Optimierungstechniken zunehmend automatisch ausführen können, aber dabei eingesetzte Optimierungsstrategien zum Schlechteren verändern können. Entwicklungen in der Prozessortechnik und Compiler-Technik stellen zudem oft widersprüchliche Anforderungen, zwischen denen ein guter Kompromiss gefunden werden muss; häufig sollte ein Speicherlayout z.B. die Anforderungen der immer wichtigeren SIMD-Rechenwerke bezüglich Ausrichtung genauso erfüllen wie die Anzahl der Datenströme entsprechend der Fähigkeiten der automatischen Prefetch-Einheiten begrenzen, zugleich aber eine effiziente Adressberechnung durch den Compiler ermöglichen. Experimente mit der Cell Broadband Engine haben zudem gezeigt, dass viele der untersuchten oder entwickelten Optimierungsverfahren auch bei einschneidenden architekturellen Änderungen übertragen und somit auf zukünftigen Plattformen eingesetzt werden können. Nachdem immer weniger eine Standardstrategie zur Optimierung einer Anwendung angegeben werden kann, ist eine genaue vorherige Analyse von Algorithmus und Zielplattform unverzichtbar. Dabei muss bei Optimierungsschritten regelmäßig überprüft werden, ob die implementierten Techniken den gewünschten Erfolg bringen. Um die Ursache eines Leistungsengpasses feststellen zu können, sind detailierte Analysen des Laufzeitverhaltens mit entsprechenden Werkzeugen unverzichtbar. Neben klassischen Techniken wie manueller oder Compiler-gestützter Instrumentierung oder der Nutzung von „Performance Countern" erweist sich hier die Verwendung von Simulatoren als besonders sinnvoll, um Vermutung zu überprüfen oder neue Hinweise zu erhalten. Neben der Simulation verschiedener Architekturen oder Prozessorversionen können hier auch komplexere Zusammenhänge erfasst oder ausgewertet werden — zum Beispiel, welcher Anteil an Daten in den Cache geladen wurde, ohne jemals genutzt zu werden, und welcher Anteil vor einer Verdrängung mehrfach genutzt wurde. Die in diesem Projekt entwickelten Werkzeuge (Cachesimulator, Visualisierung) wurden als Open-Source veröffentlicht, und werden dabei nicht nur in verschiedenen Open-Source-Entwicklungskreisen (wie KDE, OpenOffice) oder Software-Unternehmen eingesetzt, wie verschiedene Anfragen dazu gezeigt haben, sondern auch in anderen Forschungsvorhaben und in der Lehre.

Publications

• Cache Performance Optimizations for Parallel Lattice Boltzmann Codes. In: Proc. of the EuroPar-03 Conf., Band 2790 der Reihe Lecture Notes in Computer Science (LNCS), Seiten 441-450. Springer, 2003
  Wilke, J., T. Pohl, M. Kowarschik und U. Rüde
  
• Optimization and Profiling of the Cache Performance of Parallel Lattice Boltzmann Codes in 2D and 3D. Technischer Bericht 03-8, Lehrstuhl für Informatik 10 (Systemsimulation), University of Erlangen-Nuremberg, Germany, Juli 2003
  Pohl, T., M. Kowarschik, J. Wilke, K. Iglberger und U. Rüde
  
• Optimization and Profiling of the Cache Performance of Parallel Lattice Boltzmann Codes. Parallel Processing Letters, 13(4):549- 560, 2003
  Pohl, T., M. Kowarschik, J. Wilke, K. Iglberger und U. Rüde
  
• A Tool Suite for Simulation Based Analysis of Memory Access Behavior. In: Proc. of the 2004 Int. Conf. on Computational Science (ICCS2Q04), Part III, Band 3038 der Reihe Lecture Notes in Computer Science (LNCS), Seiten 440-447, Krakov, Poland, Juni 2004. Springer
  Weidendorfer, J., M. Kowarschik und C. Trinitis
  
• Data Locality Optimizations for Iterative Numerical Algorithms and Cellular Automata on Hierarchical Memory Architectures. Cauerstrasse 6, 91058 Erlangen, Germany, Juli 2004. SCS Publishing House, ISBN 3-936150-39-7
  Kowarschik, M.
  
• erformance Evaluation of Parallel Large-Scale Lattice Bolizmann Applications on Three, Supercomputing Architectures. November 2004. Supercomputing Conference 04
  Pohl, T., N. Thürey, P. Deserno, U. Rüde, P. Lammers, G. Wellein und T. Zeiser
  
• Towards Cache-Optimized Multigrid Using Patch-Adaptive Relaxation. Technischer Bericht 04-8, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander-Universität Erlangen-Nürnberg, 2004
  Kowarschik, M., I. Christadler und U. Rüde
  
• Collecting and Exploiting Cache-Reuse Metrics. In: ICCS 2005: 5th International Conference on Computational Science, Band 3515 der Reihe LNCS, Seiten 191-198. Springer, Mai 2005.
  Weidendorfer, Josef und Carsten Trinitis
  
• Hierarchical Hybrid Grids: Data Structures and Core Algorithms for Efficient Finite Element Simulations on Supercomputers. Doktorarbeit, FAU Erlangen, 2005
  Bergen,B.
  
• Is 1.7 x 1010 Unknowns the Largest Finite Element System that Can Be Solved Today? In: SC '05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing, Seite 5, Washington, DC, USA, 2005. IEEE Computer Society, Preprint version as Technical Report 05-3
  Ergen, B., F. Hülsemann und U. Rüde
  
• Optimizing Performance of the Lattice Boltzmann Method for Complex Structures on Cache-based Architectures. In: HÜLSEMANN, F., M. Kowarschik und U. Rüde (Herausgeber): I8th Symposium Simulationstechnique ASIM 2005 Proceedings, Band 15 der Reihe Frontiers in Simulation, Seiten 728-735. ASIM, SCS Publishing House, September 2005.
  Donath, S., T. Zeiser, G. Hager, J. Habich Und G. Wellein
  
• Optimizing Performance on Modern HPC Systems: Learning From Simple Kernel Benchmarks. Conference Paper, März 2005. 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing, German-Russian Center for Computational Technologies and High Performance Computing, Stuttgart, 16.03.2005
  Ager, G., T. Zeiser, J. Treibig und G. Wellein
  
• Performance Analysis of the Lattice Boltzmann Method on x-86-64 Architectures. In: Hülsemann, F., M. Kowarschik und U. Rüde (Herausgeber): 18th Symposium Simulationstechnique ASIM 2005 Proceedings, Band 15 der Reihe Frontiers in Simulation, Seiten 736-741. ASIM, SCS Publishing House, September 2005.
  Treibig, J., S. Hausmann und U. Rüde
  
• Towards Cache- Optimized Multigrid Using Patch-Adaptive Relaxation. In: Dongarra, J., K. Madsen Und J. Wasniewski (Herausgeber): PARA 2004 Proceedings, Band 3732 der Reihe Lecture Notes in Computer Science, Seiten 901-910. Springer Verlag, Dezember 2005
  Kowarschik, M., I. Christadler und U. Rüde
  
• A Massively Parallel Multigrid Method for Finite Elements. Computing in Science and Engineering, 8(6):56-62, Dezember 2006
  Bergen, B., T. Gradl, F. Hülsemann und U. Rüde
  
• Block Prefetching for Numerical Codes. In: Proc. of the ASIM-06 Conf., Frontiers in Simulation. SCS, 2006.
  Weidendorfer, Josef und Carsten Trinitis
  
• Blocking Techniques with Fast Expression Templates. Technischer Bericht 06-8, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander-Universität Erlangen-Nürnberg, November 2006
  Härdtlein, J., A. Linke und C. Pflaum
  
• Cache Optimizations for Iterative Numerical Codes Aware of Hardware Prefetching. Band 3732 der Reihe Lecture Notes in Computer Science, Seiten 921- 927. Springer, 2006
  Weidendorfer, Josef und Carsten Trinitis
  
• On the single processor performance of simple Lattice Boltzmann kernels, computers & fluids, 35(8-9):910-919, November 2006. ISSN 0045-7930
  Wellein, G., T, Zeiser, G. Hager und S. Donath
  
• Optimization of Cache Oblivious Lattice Boltzmann Method in 2D and 3D. In: BECKER, M. und H. SzczERBlCKA (Herausgeber): Simulationstechnique - 19th Symposium in Hannover, September 2006, Band 16 der Reihe Frontiers in Simulation, Seiten 265-270. ASIM, SCS Publishing House, September 2006
  Nitsure, A., K. Iglberger, U. Rüde, C. Feichtinger, G. Wellein und G. Hager
  
• Optimizing a 3D Multigrid Algorithm for the IA-64 Architecture. In: Becker, M. und H. Szczerbicka (Herausgeber): Simulationstechnique - 19th Symposium in Hannover, September 2006, Band 16 der Reihe Frontiers in Simulation, Seiten 271-276. ASIM, SCS Publishing House, September 2006
  Stürmer, M., J. Treibig und U. Rüde
  
• Simulation of bloodflow in aneurysms using the Lattice Boltzmann method and an adapted data structure. Technischer Bericht 06-6, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander-Universität Erlangen-Nürnberg, 2006.
  Götz, J.
  
• A fast multigrid solver for applications in image processing. Technischer Bericht 07-6, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander- Universität Erlangen-Nürnberg, Mai 2007. in Numerical Linear Algebra with Applications.
  Stürmer, M., H. Köstler und U. Rüde
  
• A Guide to Designing Cache Aware Multigrid Algorithms. Technischer Bericht 07-3, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander-Universität Erlangen-Nürnberg, April 2007
  Douglas, C. C., U. Rüde, J. Hu und M. L. Bittencourt
  
• Blood Flow Simulation on the Cell Broadband Engine using the Lattice Boltzmann Method. Technischer Bericht 07-9, Lehrstuhl für Informatik 10 (Systemsimulation) , Friedrich-Alexander-Universität Erlangen-Nürnberg, September 2007
  Stürmer, M., J. Götz, G. Richter und U. Rüde
  
• Massively Parallel Multilevel Finite Element Solvers on the Altix 4700. inSiDE, 5(2):24-29, 2007
  Gradl, Tobias und Ulrich Rüde
  
• PDE based Video Compression in Real Time. Technischer Bericht 07-11, Lehrstuhl für Informatik 10 (Systemsimulation), Friedrich-Alexander-Universität Erlangen-Nürnberg, August 2007
  Köstler, H., M. Stürmer, C. Freundl und U. Rüde
  
• Petascale Computing: Algorithms and Applications, Kapitel Towards Petascale Multilevel Finite Element Solvers. Chapman & Hall/CRC, Dezember 2007.
  Freundl, C., T. Gradl, U. Rüde und B. Bergen
  
• Off-loading Application controlled Data Prefetching in Numerical Codes for Multi-Core Processors. Int. J. High Performance Computing and Networking, 2008
  Weidendorfer, Josef und Carsten Trinitis
  
• Optimizing a 3D Multigrid Algorithm for the IA-64 Architecture. International Journal of Computational Science and Engineering (IJCSE), 2008
  Stürmer, M., J. Treibig und U. Rüde