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

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.

Please use the citation below to reference SFMalloc.

• [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.

• 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)

If you would like to download the SFMalloc, please email us. 

• Getting started with the SNU-SAMSUNG OpenCL framework
• OpenCL API functions supported by the SNU-SAMSUNG OpenCL framework

• Sangmin Seo, Junghyun Kim, and Jaejin Lee

• sfmalloc@aces.snu.ac.kr

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
    
    https://thunder.snu.ac.kr
    
    Contributors:
     Sangmin Seo, Junghyun Kim, and Jaejin Lee