Palloc: parallel dynamic memory allocation

Simmons, Patrick A.

Permalink

https://hdl.handle.net/2142/24135 Copy

Description

Title

Palloc: parallel dynamic memory allocation

Author(s)

Simmons, Patrick A.

Issue Date

2011-05-25T15:07:09Z

Director of Research (if dissertation) or Advisor (if thesis)

Adve, Vikram S.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

Abstract

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.

Graduation Semester

2011-05

Permalink

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

Copyright and License Information

Copyright 2011 Patrick A. Simmons

Owning Collections