Palloc: parallel dynamic memory allocation

In this thesis, we describe two related memory allocators, each with novel properties. PALLOC1 contributes a unique strategy based on the traversal of a parallel tree data structure for allowing concurrent allocations and frees to proceed within a single thread's heap. PALLOC1 also provides a novel, provable guarantee limiting the allocator's requests for more memory from the operating system to only those situations where no contiguous block is available to satisfy the allocation request, and a pure bitmap allocation strategy speed-competitive even for sequential codes with the boundary-tag / binning strategy used in dlmalloc. We find that, for larger allocation patterns, our implementation exhibits competitive base performance relative to other parallel allocators, superior scaling, and better resistance in practice to fragmentation. PALLOC2 contributes a second unique strategy for memory allocation based on bitmap allocation into variable-sized superpages. Our system provides the runtime with the useful ability to, given an arbitrary heap address, find both the start of the heap allocation and the size of the object allocated. Thus, PALLOC2 provide the capabilities of baggy bounds checking with no performance impact. In fact, we find that, for both sequential and parallel programs, PALLOC2's performance is superior to PALLOC1 and to other state-of-the-art allocators including Hoard, DLMalloc, and Streamflow for allocations of all sizes.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Simmons, Patrick A.

Contributors dc:contributor

• Adve, Vikram S.

• malloc
• memory allocation
• palloc
• palloc1
• palloc2
• dynamic memory allocation

Statement dc:rights

• Copyright 2011 Patrick A. Simmons

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24135

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24135