Logotyp: till Uppsala universitets webbplats

uu.sePublikationer från Uppsala universitet
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Iterative and Adaptive PDE Solvers for Shared Memory Architectures
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för teknisk databehandling. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Numerisk analys. (Software Aspects of High-Performance Computing)
2006 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)Alternativ titel
Iterativa och adaptiva PDE-lösare för parallelldatorer med gemensam minnesorganisation (Svenska)
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.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis , 2006. , s. 49
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 218
Nyckelord [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
Nationell ämneskategori
Programvaruteknik Beräkningsmatematik
Forskningsämne
Beräkningsvetenskap
Identifikatorer
URN: urn:nbn:se:uu:diva-7136ISBN: 91-554-6648-6 (tryckt)OAI: oai:DiVA.org:uu-7136DiVA, id: diva2:168842
Disputation
2006-10-07, Auditorium Minus, Museum Gustavianum, Akademigatan 3, Uppsala, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2006-09-15 Skapad: 2006-09-15 Senast uppdaterad: 2022-03-11Bibliografiskt granskad
Delarbeten
1. Improving Geographical Locality of Data for Shared Memory Implementations of PDE Solvers
Öppna denna publikation i ny flik eller fönster >>Improving Geographical Locality of Data for Shared Memory Implementations of PDE Solvers
2004 (Engelska)Ingår i: Computational Science – ICCS 2004, Berlin: Springer-Verlag , 2004, s. 9-16Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Berlin: Springer-Verlag, 2004
Serie
Lecture Notes in Computer Science ; 3037
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-71098 (URN)10.1007/b97988 (DOI)
Tillgänglig från: 2007-03-11 Skapad: 2007-03-11 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
2. affinity-on-next-touch: Increasing the Performance of an Industrial PDE Solver on a cc-NUMA System
Öppna denna publikation i ny flik eller fönster >>affinity-on-next-touch: Increasing the Performance of an Industrial PDE Solver on a cc-NUMA System
2005 (Engelska)Ingår i: Proc. 19th ACM International Conference on Supercomputing, New York: ACM Press , 2005, s. 387-392Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
New York: ACM Press, 2005
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-80041 (URN)10.1145/1088149.1088201 (DOI)1-59593-167-8 (ISBN)
Tillgänglig från: 2006-05-19 Skapad: 2009-01-19 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
3. Algorithmic optimizations of a conjugate gradient solver on shared memory architectures
Öppna denna publikation i ny flik eller fönster >>Algorithmic optimizations of a conjugate gradient solver on shared memory architectures
2006 (Engelska)Ingår i: International Journal of Parallel, Emergent and Distributed Systems, ISSN 1744-5760, E-ISSN 1744-5779, Vol. 21, s. 345-363Artikel i tidskrift (Refereegranskat) Published
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-80937 (URN)10.1080/17445760600568139 (DOI)
Tillgänglig från: 2006-06-29 Skapad: 2006-06-29 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
4. Multigrid and Gauss-Seidel smoothers revisited: Parallelization on chip multiprocessors
Öppna denna publikation i ny flik eller fönster >>Multigrid and Gauss-Seidel smoothers revisited: Parallelization on chip multiprocessors
2006 (Engelska)Ingår i: Proc. 20th ACM International Conference on Supercomputing, New York: ACM Press , 2006, s. 145-155Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
New York: ACM Press, 2006
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-19810 (URN)10.1145/1183401.1183423 (DOI)1-59593-282-8 (ISBN)
Tillgänglig från: 2008-02-08 Skapad: 2008-02-08 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
5. Geographical locality and dynamic data migration for OpenMP implementations of adaptive PDE solvers
Öppna denna publikation i ny flik eller fönster >>Geographical locality and dynamic data migration for OpenMP implementations of adaptive PDE solvers
2008 (Engelska)Ingår i: OpenMP Shared Memory Parallel Programming, Berlin: Springer-Verlag , 2008, s. 382-393Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Berlin: Springer-Verlag, 2008
Serie
Lecture Notes in Computer Science ; 4315
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-17844 (URN)10.1007/978-3-540-68555-5_31 (DOI)000256573200031 ()978-3-540-68554-8 (ISBN)
Projekt
UPMARC
Tillgänglig från: 2008-09-05 Skapad: 2008-09-05 Senast uppdaterad: 2022-01-28Bibliografiskt granskad

Open Access i DiVA

fulltext(469 kB)1440 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 469 kBChecksumma MD5
7be402a5f8f4cec172a00873d605e0df613dbf7962d8fa7644abd6731bbe1a7e10d793f1
Typ fulltextMimetyp application/pdf

Person

Löf, Henrik

Sök vidare i DiVA

Av författaren/redaktören
Löf, Henrik
Av organisationen
Avdelningen för teknisk databehandlingNumerisk analys
ProgramvaruteknikBeräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 1440 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 1834 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf