License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SNAPL.2015.1
URN: urn:nbn:de:0030-drops-50121
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5012/
Go to the corresponding LIPIcs Volume Portal

Acar, Umut A. ; Blelloch, Guy ; Fluet, Matthew ; Muller, Stefan K. ; Raghunathan, Ram

Coupling Memory and Computation for Locality Management

pdf-format:
2.pdf (0.5 MB)

Abstract

We articulate the need for managing (data) locality automatically rather than leaving it to the programmer, especially in parallel programming systems. To this end, we propose techniques for coupling tightly the computation (including the thread scheduler) and the memory manager so that data and computation can be positioned closely in hardware. Such tight coupling of computation and memory management is in sharp contrast with the prevailing practice of considering each in isolation. For example, memory-management techniques usually abstract the computation as an unknown "mutator", which is treated as a "black box". As an example of the approach, in this paper we consider a specific class of parallel computations, nested-parallel computations. Such computations dynamically create a nesting of parallel tasks. We propose a method for organizing memory as a tree of heaps reflecting the structure of the nesting. More specifically, our approach creates a heap for a task if it is separately scheduled on a processor. This allows us to couple garbage collection with the structure of the computation and the way in which it is dynamically scheduled on the processors. This coupling enables taking advantage of locality in the program by mapping it to the locality of the hardware. For example for improved locality a heap can be garbage collected immediately after its task finishes when the heap contents is likely in cache.

BibTeX - Entry

@InProceedings{acar_et_al:LIPIcs:2015:5012,
  author =	{Umut A. Acar and Guy Blelloch and Matthew Fluet and Stefan K. Muller and Ram Raghunathan},
  title =	{{Coupling Memory and Computation for Locality Management}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{1--14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Thomas Ball and Rastislav Bodik and Shriram Krishnamurthi and Benjamin S. Lerner and Greg Morrisett},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5012},
  URN =		{urn:nbn:de:0030-drops-50121},
  doi =		{10.4230/LIPIcs.SNAPL.2015.1},
  annote =	{Keywords: Parallel computing, locality, memory management, parallel garbage collection, functional programming, nested parallelism, thread scheduling}
}

Keywords: Parallel computing, locality, memory management, parallel garbage collection, functional programming, nested parallelism, thread scheduling
Collection: 1st Summit on Advances in Programming Languages (SNAPL 2015)
Issue Date: 2015
Date of publication: 30.04.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI