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

@InCollection{Degenbaev:PTM2009, author = "Ulan Degenbaev and Wolfgang J. Paul and Norbert Schirmer", title = "Pervasive Theory of Memory", booktitle = "Efficient Algorithms -- Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday", ee = "http://dx.doi.org/10.1007/978-3-642-03456-5_5", 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", }