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
Methods for Creating and Exploiting Data Locality
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Avdelningen för datorteknik. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Uppsala Architecture Research Team)
2006 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

The gap between processor speed and memory latency has led to the use of caches in the memory systems of modern computers. Programs must use the caches efficiently and exploit data locality for maximum performance. Multiprocessors, built from many processing units, are becoming commonplace not only in large servers but also in smaller systems such as personal computers. Multiprocessors require careful data locality optimizations since accesses from other processors can lead to invalidations and false sharing cache misses. This thesis explores hardware and software approaches for creating and exploiting temporal and spatial locality in multiprocessors.

We propose the capacity prefetching technique, which efficiently reduces the number of cache misses but avoids false sharing by distinguishing between cache lines involved in communication from non-communicating cache lines at run-time. Prefetching techniques often lead to increased coherence and data traffic. The new bundling technique avoids one of these drawbacks and reduces the coherence traffic in multiprocessor prefetchers. This is especially important in snoop-based systems where the coherence bandwidth is a scarce resource.

Most of the studies have been performed on advanced scientific algorithms. This thesis demonstrates that a cc-NUMA multiprocessor, with hardware data migration and replication optimizations, efficiently exploits the temporal locality in such codes. We further present a method of parallelizing a multigrid Gauss-Seidel partial differential equation solver, which creates temporal locality at the expense of increased communication. Our conclusion is that on modern chip multiprocessors, it is more important to optimize algorithms for data locality than to avoid communication, since communication can take place using a shared cache.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis , 2006. , s. 37
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 176
Nyckelord [en]
data locality, temporal locality, spatial locality, prefetching, cache, cache behavior, cache coherence, snooping protocols, partial differential equation, shared-memory multiprocessor, chip multiprocessor, simulation
Nationell ämneskategori
Datorteknik
Identifikatorer
URN: urn:nbn:se:uu:diva-6837ISBN: 91-554-6555-2 (tryckt)OAI: oai:DiVA.org:uu-6837DiVA, id: diva2:168291
Disputation
2006-05-24, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2006-04-28 Skapad: 2006-04-28 Senast uppdaterad: 2022-03-11Bibliografiskt granskad
Delarbeten
1. Miss Penalty Reduction Using Bundled Capacity Prefetching in Multiprocessors
Öppna denna publikation i ny flik eller fönster >>Miss Penalty Reduction Using Bundled Capacity Prefetching in Multiprocessors
2003 Ingår i: Proceedings of the International Parallel and Distributed Processing SymposiumArtikel i tidskrift (Refereegranskat) Published
Identifikatorer
urn:nbn:se:uu:diva-94442 (URN)
Tillgänglig från: 2006-04-28 Skapad: 2006-04-28Bibliografiskt granskad
2. Bundling: Reducing the Overhead of Multiprocessor Prefetchers
Öppna denna publikation i ny flik eller fönster >>Bundling: Reducing the Overhead of Multiprocessor Prefetchers
2004 Ingår i: Proceedings of the International Parallel and Distributed Processing SymposiumArtikel i tidskrift (Refereegranskat) Published
Identifikatorer
urn:nbn:se:uu:diva-94443 (URN)
Tillgänglig från: 2006-04-28 Skapad: 2006-04-28Bibliografiskt granskad
3. Cache memory behavior of advanced PDE solvers
Öppna denna publikation i ny flik eller fönster >>Cache memory behavior of advanced PDE solvers
2004 (Engelska)Ingår i: Parallel Computing: Software Technology, Algorithms, Architectures and Applications, Amsterdam, The Netherlands: Elsevier , 2004, s. 475-482Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Amsterdam, The Netherlands: Elsevier, 2004
Serie
Advances in Parallel Computing ; 13
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-67857 (URN)0-444-51689-1 (ISBN)
Tillgänglig från: 2006-05-17 Skapad: 2006-05-17 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
4. Performance of PDE solvers on a self-optimizing NUMA architecture
Öppna denna publikation i ny flik eller fönster >>Performance of PDE solvers on a self-optimizing NUMA architecture
2002 (Engelska)Ingår i: Parallel Algorithms and Applications, ISSN 1063-7192, E-ISSN 1029-032X, Vol. 17, s. 285-299Artikel i tidskrift (Refereegranskat) Published
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
urn:nbn:se:uu:diva-66909 (URN)10.1080/01495730208941445 (DOI)
Tillgänglig från: 2006-05-22 Skapad: 2006-05-22 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
5. 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
6. Vasa: A Simulator Infrastructure with Adjustable Fidelity
Öppna denna publikation i ny flik eller fönster >>Vasa: A Simulator Infrastructure with Adjustable Fidelity
2005 Ingår i: Proceedings of the International Conference on Parallel and Distibuted Computing and SystemsArtikel i tidskrift (Refereegranskat) Published
Identifikatorer
urn:nbn:se:uu:diva-94447 (URN)
Tillgänglig från: 2006-04-28 Skapad: 2006-04-28Bibliografiskt granskad

Open Access i DiVA

fulltext(256 kB)1401 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 256 kBChecksumma SHA-1
7e484336121b919bfd885e5e7cb410512e22490e6991631a14ac135c603dbafcbfc97ef4
Typ fulltextMimetyp application/pdf

Av organisationen
Avdelningen för datorteknikDatorteknik
Datorteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 1401 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: 1916 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