Pervasive Theory of Memory

Ulan Degenbaev and Wolfgang J. Paul and Norbert Schirmer

Article in Festschrift, 2009


For many aspects of memory theoretical treatment already exists, in particular for: simple cache construction, store buffers and store buffer forwarding, cache coherence protocols, out of order access to memory, segmentation and paging, shared memory data structures (e.g. for locks) as well as for memory models of multi-threaded programming languages. It turns out that we have to unite all of these theories into a single theory if we wish to understand why parallel C compiled by an optimizing compiler runs correctly on a contemporary multi core processor. This pervasive theory of memory is outlined here.

 Online Copy

Available as PDF-File

 BibTeX Entry

  author =       "Ulan Degenbaev and Wolfgang J. Paul and Norbert
  title =        "Pervasive Theory of Memory",
  booktitle =    "Efficient Algorithms -- Essays Dedicated to Kurt
                 Mehlhorn on the Occasion of His 60th Birthday",
  ee =           "",
  pages =        "74--98",
  publisher =    "Springer",
  year =         "2009",
  editor =       "Susanne Albers and Helmut Alt and Stefan N{\"a}her",
  volume =       "5760",
  series =       "Lecture Notes in Computer Science",

Norbert Schirmer