SFMalloc A Lock-Free and Mostly Synchronization-Free Dynamic Memory Allocator for Manycores

Overview

As parallel programming becomes the mainstream due to multicore processors, dynamic memory management routines (malloc/free) used in C and C++ can suppress the performance of multi-threaded applications if they are not scalable.

SFMalloc (Synchronization-Free Malloc) is a new dynamic memory allocator for multi-threaded applications. SFMalloc never uses any synchronization for common cases. It uses only lock-free synchronization mechanisms for uncommon cases.

SFMalloc provides each thread with a private heap and each thread handles memory requests on the heap. SFMalloc is completely synchronization-free when a thread allocates a memory block and deallocates it by itself. Synchronization-free means that threads do not communicate with each other at all. On the other hand, if a thread allocates a block and another thread frees it, we use a lock-free stack to atomically add it to the owner thread's heap to avoid the memory blowup problem. SFMalloc also exploits various memory block caching mechanisms to reduce the latency of memory management. Freed blocks or intermediate memory chunks are cached hierarchically in each thread's heap and they are used for future memory allocation.

Publications

  • [PACT] Sangmin Seo, Junghyun Kim, and Jaejin Lee. SFMalloc: A Lock-Free and Mostly Synchronization-Free Dynamic Memory Allocator for Manycores, PACT '11: Proceedings of the 20th ACM/IEEE/IFIP International Conference on Parallel Architectures and Compilation Techniques, Galveston Island, Texas, USA, October 2011.

Tested Platforms

SFMalloc supports x86-64 CPUs. It builds on 64-bit flavors of Linux.

  • AMD Opteron 6714, Intel Xeon X5660 CPU
  • Ubuntu 10.04 (64-bit), Red Hat Enterprise Linux Server release 5.5 (64-bit)

Download

If you would like to download the SFMalloc, please fill out the following form and click the download button. An email containing the download URL will be sent to the email address.

Contributors

Sangmin Seo, Junghyun Kim, and Jaejin Lee

Contact and Bug Report

E-mail: sfmalloc@aces.snu.ac.kr

License

Copyright (c) 2011, Seoul National University.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
 1. Redistributions of source code must retain the above copyright
 notice, this list of conditions and the following disclaimer.
 2. Redistributions in binary form must reproduce the above copyright
 notice, this list of conditions and the following disclaimer in the
 documentation and/or other materials provided with the distribution.
 3. Neither the name of Seoul National University nor the names of its
 contributors may be used to endorse or promote products derived
 from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY SEOUL NATIONAL UNIVERSITY "AS IS" AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL SEOUL NATIONAL UNIVERSITY BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

Contact information:
 Center for Manycore Programming
 School of Computer Science and Engineering
 Seoul National University, Seoul 151-744, Korea

http://aces.snu.ac.kr

Contributors:
 Sangmin Seo, Junghyun Kim, and Jaejin Lee