{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/24135"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/24135","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Palloc: parallel 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Simmons, Patrick A."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Adve, Vikram S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-25T15:07:09Z","date_published":"2011-05-25T15:07:09Z","updated_at":"2026-07-22T22:25:24Z","subjects":["malloc","memory allocation","palloc","palloc1","palloc2","dynamic memory allocation"],"languages":["en"],"rights":["Copyright 2011 Patrick A. Simmons"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/24135","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Adve, Vikram S."]},{"key":"dc:creator","label":"Author","values":["Simmons, Patrick A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-25T15:07:09Z","2011-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["malloc","memory allocation","palloc","palloc1","palloc2","dynamic memory allocation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Patrick A. Simmons"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/24135"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-25T18:33:41Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 palloc.tex: 50769 bytes, checksum: 5fd62b9b663bccf1483e73b23cd4d1c8 (MD5) Simmons_Patrick.pdf: 736938 bytes, checksum: f878b483a98c6102e99871f04c9fa721 (MD5)","Made available in DSpace on 2011-05-25T15:07:09Z (GMT). No. of bitstreams: 3 Simmons_Patrick.pdf: 736938 bytes, checksum: f878b483a98c6102e99871f04c9fa721 (MD5) license.txt: 4065 bytes, checksum: c3969c6afb327dae1d5cae5dd1f14630 (MD5) palloc.tex: 50769 bytes, checksum: 5fd62b9b663bccf1483e73b23cd4d1c8 (MD5)"]},{"key":"dc:title","label":"Title","values":["Palloc: parallel dynamic memory allocation"]}]}],"canonical_facts":{"dc:contributor":["Adve, Vikram S."],"dc:creator":["Simmons, Patrick A."],"dc:date":["2011-05-25T15:07:09Z","2011-05"],"dc:description":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-25T18:33:41Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 palloc.tex: 50769 bytes, checksum: 5fd62b9b663bccf1483e73b23cd4d1c8 (MD5) Simmons_Patrick.pdf: 736938 bytes, checksum: f878b483a98c6102e99871f04c9fa721 (MD5)","Made available in DSpace on 2011-05-25T15:07:09Z (GMT). No. of bitstreams: 3 Simmons_Patrick.pdf: 736938 bytes, checksum: f878b483a98c6102e99871f04c9fa721 (MD5) license.txt: 4065 bytes, checksum: c3969c6afb327dae1d5cae5dd1f14630 (MD5) palloc.tex: 50769 bytes, checksum: 5fd62b9b663bccf1483e73b23cd4d1c8 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/24135"],"dc:language":["en"],"dc:rights":["Copyright 2011 Patrick A. Simmons"],"dc:subject":["malloc","memory allocation","palloc","palloc1","palloc2","dynamic memory allocation"],"dc:title":["Palloc: parallel dynamic memory allocation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:24Z"}