XMalloc: A scalable lock-free dynamic memory allocator for many-core machines

Xiaohuang Huang, Christopher I. Rodrigues, Stephen Jones, Ian Buck, Wen Mei Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

There are two avenues for many-core machines to gain higher performance: increasing the number of processors, and increasing the number of vector units in one SIMD processor. A truly scalable algorithm should take advantage of both. However, most past research on scalable memory allocators scales well with the number of processors, but poorly with the number of vector units in one SIMD processor. As a result, they are not truly scalable on many-core architectures. In this work, we introduce our proposed solution through the design of XMalloc, a truly scalable, efficient lock-free memory allocator. We will present (1) our solution for transforming traditional atomic compare-and-swap based lock-free algorithm to scale on SIMD architectures, and (2) a hierarchical cache-like buffer solution to reduce the average latency of accesses to non-scalable or slow resources such as main memory in a many-core machine. We implemented XMalloc as a memory allocator on an NVIDIA Tesla C1060 GPU with 240 processing units. Our experimental results show that XMalloc scales very well with growth in both the number of processors and the number of vector units in each SIMD processor. Our truly scalable lock-free solution achieves 211 times speedup compared to the common lock-free solution.

Original languageEnglish (US)
Title of host publicationProceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010
Pages1134-1139
Number of pages6
DOIs
StatePublished - Nov 19 2010
Event10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010 - Bradford, United Kingdom
Duration: Jun 29 2010Jul 1 2010

Publication series

NameProceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010

Other

Other10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010
CountryUnited Kingdom
CityBradford
Period6/29/107/1/10

Fingerprint

Data storage equipment
Processing
Graphics processing unit

Keywords

  • Async-signal-safe
  • Availability
  • CUDA
  • GPGPU
  • Lock-free
  • Malloc
  • Scalability

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Software

Cite this

Huang, X., Rodrigues, C. I., Jones, S., Buck, I., & Hwu, W. M. (2010). XMalloc: A scalable lock-free dynamic memory allocator for many-core machines. In Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010 (pp. 1134-1139). [5577907] (Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010). https://doi.org/10.1109/CIT.2010.206

XMalloc : A scalable lock-free dynamic memory allocator for many-core machines. / Huang, Xiaohuang; Rodrigues, Christopher I.; Jones, Stephen; Buck, Ian; Hwu, Wen Mei.

Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010. 2010. p. 1134-1139 5577907 (Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, X, Rodrigues, CI, Jones, S, Buck, I & Hwu, WM 2010, XMalloc: A scalable lock-free dynamic memory allocator for many-core machines. in Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010., 5577907, Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010, pp. 1134-1139, 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010, Bradford, United Kingdom, 6/29/10. https://doi.org/10.1109/CIT.2010.206
Huang X, Rodrigues CI, Jones S, Buck I, Hwu WM. XMalloc: A scalable lock-free dynamic memory allocator for many-core machines. In Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010. 2010. p. 1134-1139. 5577907. (Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010). https://doi.org/10.1109/CIT.2010.206
Huang, Xiaohuang ; Rodrigues, Christopher I. ; Jones, Stephen ; Buck, Ian ; Hwu, Wen Mei. / XMalloc : A scalable lock-free dynamic memory allocator for many-core machines. Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010. 2010. pp. 1134-1139 (Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010).
@inproceedings{82de7871ac6d48329418ae1f76332846,
title = "XMalloc: A scalable lock-free dynamic memory allocator for many-core machines",
abstract = "There are two avenues for many-core machines to gain higher performance: increasing the number of processors, and increasing the number of vector units in one SIMD processor. A truly scalable algorithm should take advantage of both. However, most past research on scalable memory allocators scales well with the number of processors, but poorly with the number of vector units in one SIMD processor. As a result, they are not truly scalable on many-core architectures. In this work, we introduce our proposed solution through the design of XMalloc, a truly scalable, efficient lock-free memory allocator. We will present (1) our solution for transforming traditional atomic compare-and-swap based lock-free algorithm to scale on SIMD architectures, and (2) a hierarchical cache-like buffer solution to reduce the average latency of accesses to non-scalable or slow resources such as main memory in a many-core machine. We implemented XMalloc as a memory allocator on an NVIDIA Tesla C1060 GPU with 240 processing units. Our experimental results show that XMalloc scales very well with growth in both the number of processors and the number of vector units in each SIMD processor. Our truly scalable lock-free solution achieves 211 times speedup compared to the common lock-free solution.",
keywords = "Async-signal-safe, Availability, CUDA, GPGPU, Lock-free, Malloc, Scalability",
author = "Xiaohuang Huang and Rodrigues, {Christopher I.} and Stephen Jones and Ian Buck and Hwu, {Wen Mei}",
year = "2010",
month = "11",
day = "19",
doi = "10.1109/CIT.2010.206",
language = "English (US)",
isbn = "9780769541082",
series = "Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010",
pages = "1134--1139",
booktitle = "Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010",

}

TY - GEN

T1 - XMalloc

T2 - A scalable lock-free dynamic memory allocator for many-core machines

AU - Huang, Xiaohuang

AU - Rodrigues, Christopher I.

AU - Jones, Stephen

AU - Buck, Ian

AU - Hwu, Wen Mei

PY - 2010/11/19

Y1 - 2010/11/19

N2 - There are two avenues for many-core machines to gain higher performance: increasing the number of processors, and increasing the number of vector units in one SIMD processor. A truly scalable algorithm should take advantage of both. However, most past research on scalable memory allocators scales well with the number of processors, but poorly with the number of vector units in one SIMD processor. As a result, they are not truly scalable on many-core architectures. In this work, we introduce our proposed solution through the design of XMalloc, a truly scalable, efficient lock-free memory allocator. We will present (1) our solution for transforming traditional atomic compare-and-swap based lock-free algorithm to scale on SIMD architectures, and (2) a hierarchical cache-like buffer solution to reduce the average latency of accesses to non-scalable or slow resources such as main memory in a many-core machine. We implemented XMalloc as a memory allocator on an NVIDIA Tesla C1060 GPU with 240 processing units. Our experimental results show that XMalloc scales very well with growth in both the number of processors and the number of vector units in each SIMD processor. Our truly scalable lock-free solution achieves 211 times speedup compared to the common lock-free solution.

AB - There are two avenues for many-core machines to gain higher performance: increasing the number of processors, and increasing the number of vector units in one SIMD processor. A truly scalable algorithm should take advantage of both. However, most past research on scalable memory allocators scales well with the number of processors, but poorly with the number of vector units in one SIMD processor. As a result, they are not truly scalable on many-core architectures. In this work, we introduce our proposed solution through the design of XMalloc, a truly scalable, efficient lock-free memory allocator. We will present (1) our solution for transforming traditional atomic compare-and-swap based lock-free algorithm to scale on SIMD architectures, and (2) a hierarchical cache-like buffer solution to reduce the average latency of accesses to non-scalable or slow resources such as main memory in a many-core machine. We implemented XMalloc as a memory allocator on an NVIDIA Tesla C1060 GPU with 240 processing units. Our experimental results show that XMalloc scales very well with growth in both the number of processors and the number of vector units in each SIMD processor. Our truly scalable lock-free solution achieves 211 times speedup compared to the common lock-free solution.

KW - Async-signal-safe

KW - Availability

KW - CUDA

KW - GPGPU

KW - Lock-free

KW - Malloc

KW - Scalability

UR - http://www.scopus.com/inward/record.url?scp=78249288442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78249288442&partnerID=8YFLogxK

U2 - 10.1109/CIT.2010.206

DO - 10.1109/CIT.2010.206

M3 - Conference contribution

AN - SCOPUS:78249288442

SN - 9780769541082

T3 - Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010

SP - 1134

EP - 1139

BT - Proceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010

ER -