uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Iterative and Adaptive PDE Solvers for Shared Memory Architectures
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Numerical Analysis. (Software Aspects of High-Performance Computing)
2006 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
Iterativa och adaptiva PDE-lösare för parallelldatorer med gemensam minnesorganisation (Swedish)
Abstract [en]

Scientific computing is used frequently in an increasing number of disciplines to accelerate scientific discovery. Many such computing problems involve the numerical solution of partial differential equations (PDE). In this thesis we explore and develop methodology for high-performance implementations of PDE solvers for shared-memory multiprocessor architectures.

We consider three realistic PDE settings: solution of the Maxwell equations in 3D using an unstructured grid and the method of conjugate gradients, solution of the Poisson equation in 3D using a geometric multigrid method, and solution of an advection equation in 2D using structured adaptive mesh refinement. We apply software optimization techniques to increase both parallel efficiency and the degree of data locality.

In our evaluation we use several different shared-memory architectures ranging from symmetric multiprocessors and distributed shared-memory architectures to chip-multiprocessors. For distributed shared-memory systems we explore methods of data distribution to increase the amount of geographical locality. We evaluate automatic and transparent page migration based on runtime sampling, user-initiated page migration using a directive with an affinity-on-next-touch semantic, and algorithmic optimizations for page-placement policies.

Our results show that page migration increases the amount of geographical locality and that the parallel overhead related to page migration can be amortized over the iterations needed to reach convergence. This is especially true for the affinity-on-next-touch methodology whereby page migration can be initiated at an early stage in the algorithms.

We also develop and explore methodology for other forms of data locality and conclude that the effect on performance is significant and that this effect will increase for future shared-memory architectures. Our overall conclusion is that, if the involved locality issues are addressed, the shared-memory programming model provides an efficient and productive environment for solving many important PDE problems.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2006. , p. 49
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 218
Keywords [en]
partial differential equations, iterative methods, finite elements, conjugate gradients, adaptive mesh refinement, multigrid, cc-NUMA, distributed shared memory, OpenMP, page migration, TLB shoot-down, bandwidth minimization, reverse Cuthill-McKee, migrate-on-next-touch, affinity, temporal locality, chip multiprocessors, CMP
National Category
Software Engineering Computational Mathematics
Research subject
Scientific Computing
Identifiers
URN: urn:nbn:se:uu:diva-7136ISBN: 91-554-6648-6 (print)OAI: oai:DiVA.org:uu-7136DiVA, id: diva2:168842
Public defence
2006-10-07, Auditorium Minus, Museum Gustavianum, Akademigatan 3, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2018-01-13Bibliographically approved
List of papers
1. Improving Geographical Locality of Data for Shared Memory Implementations of PDE Solvers
Open this publication in new window or tab >>Improving Geographical Locality of Data for Shared Memory Implementations of PDE Solvers
2004 (English)In: Computational Science – ICCS 2004, Berlin: Springer-Verlag , 2004, p. 9-16Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Berlin: Springer-Verlag, 2004
Series
Lecture Notes in Computer Science ; 3037
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-71098 (URN)10.1007/b97988 (DOI)
Available from: 2007-03-11 Created: 2007-03-11 Last updated: 2018-01-10Bibliographically approved
2. affinity-on-next-touch: Increasing the Performance of an Industrial PDE Solver on a cc-NUMA System
Open this publication in new window or tab >>affinity-on-next-touch: Increasing the Performance of an Industrial PDE Solver on a cc-NUMA System
2005 (English)In: Proc. 19th ACM International Conference on Supercomputing, New York: ACM Press , 2005, p. 387-392Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2005
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-80041 (URN)10.1145/1088149.1088201 (DOI)1-59593-167-8 (ISBN)
Available from: 2006-05-19 Created: 2009-01-19 Last updated: 2018-01-13Bibliographically approved
3. Algorithmic optimizations of a conjugate gradient solver on shared memory architectures
Open this publication in new window or tab >>Algorithmic optimizations of a conjugate gradient solver on shared memory architectures
2006 (English)In: International Journal of Parallel, Emergent and Distributed Systems, ISSN 1744-5760, E-ISSN 1744-5779, Vol. 21, p. 345-363Article in journal (Refereed) Published
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-80937 (URN)10.1080/17445760600568139 (DOI)
Available from: 2006-06-29 Created: 2006-06-29 Last updated: 2018-01-13Bibliographically approved
4. Multigrid and Gauss-Seidel smoothers revisited: Parallelization on chip multiprocessors
Open this publication in new window or tab >>Multigrid and Gauss-Seidel smoothers revisited: Parallelization on chip multiprocessors
2006 (English)In: Proc. 20th ACM International Conference on Supercomputing, New York: ACM Press , 2006, p. 145-155Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2006
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-19810 (URN)10.1145/1183401.1183423 (DOI)1-59593-282-8 (ISBN)
Available from: 2008-02-08 Created: 2008-02-08 Last updated: 2018-01-12Bibliographically approved
5. Geographical locality and dynamic data migration for OpenMP implementations of adaptive PDE solvers
Open this publication in new window or tab >>Geographical locality and dynamic data migration for OpenMP implementations of adaptive PDE solvers
2008 (English)In: OpenMP Shared Memory Parallel Programming, Berlin: Springer-Verlag , 2008, p. 382-393Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Berlin: Springer-Verlag, 2008
Series
Lecture Notes in Computer Science ; 4315
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:uu:diva-17844 (URN)10.1007/978-3-540-68555-5_31 (DOI)000256573200031 ()978-3-540-68554-8 (ISBN)
Projects
UPMARC
Available from: 2008-09-05 Created: 2008-09-05 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

fulltext(469 kB)1322 downloads
File information
File name FULLTEXT01.pdfFile size 469 kBChecksum MD5
7be402a5f8f4cec172a00873d605e0df613dbf7962d8fa7644abd6731bbe1a7e10d793f1
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Löf, Henrik

Search in DiVA

By author/editor
Löf, Henrik
By organisation
Division of Scientific ComputingNumerical Analysis
Software EngineeringComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1322 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1702 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf