Distributed Computing LPD

Software projects developed at LPD

LPD has a github page where most new software projects are published: https://github.com/LPD-EPFL/


Designed for the EuroSys '17 paper: “FloDB: Unlocking Memory in Persistent Key-Value Stores.”

FloDB is a LSM memory component architecture which allows throughput to scale on modern multicore machines with ample memory sizes. The main idea underlying FloDB is essentially to bootstrap the traditional LSM architecture by adding a small in-memory buffer layer on top of the memory component. This buffer offers low-latency operations, masking the write latency of the sorted memory component. Integrating this buffer in the classic LSM memory component to obtain FloDB is not trivial and requires revisiting the algorithms of the user-facing LSM operations (search, update, scan). FloDB's two layers can be implemented with state-of-the-art, highly-concurrent data structures. This way, as we show in the paper, FloDB eliminates significant synchronization bottlenecks in classic LSM designs, while offering a rich LSM API.

Details & Code


Designed for the EuroSys '17 paper: “Abstracting Multi-Core Topologies with MCTOP.”

MCTOP is an abstraction of multi-core topologies augmented with important low-level hardware information, such as memory bandwidths and communication latencies. We automatically generate MCTOP using libmctop, our library that leverages the determinism of cache-coherence protocols to infer the topology of multi-cores using only latency measurements. MCTOP enables developers to accurately define performance policies, expressing high-level semantics that utilize the low-level performance details of multi-cores. This way, MCTOP enables the design of easy, portable, and efficient optimizations.

Details & Code


Designed for the Middleware '16 paper: “Locking Made Easy.”

GLS is a middleware that makes lock-based programming simple and effective. GLS offers the classic lock-unlock interface of locks. However, in contrast to classic lock libraries, GLS does not require any effort from the programmer for allocating and initializing locks, nor for selecting the appropriate locking strategy. With GLS, all these intricacies of locking are hidden from the programmer. GLS is based on GLK, a generic lock algorithm that dynamically adapts to the contention level on the lock object. GLK is able to deliver the best performance among simple spinlocks, scalable queue-based locks, and blocking locks. Furthermore, GLS offers several debugging options for easily detecting various lock-related issues, such as deadlocks.

Details & Code


Designed for the ATC '16 paper: “Unlocking Energy.”

LOCKIN is a new locking library that includes more than 10 state-of-the-art lock algorithms. For simplicity, LOCKIN offers these algorithms in C header files, so that selecting the algorithm to use can be as simple as setting one configuration flag. LOCKIN can be also set to overload the default pthread mutex lock interface, in order to allow for easily modifying locks in pthread-based systems. Most importantly, LOCKIN includes MUTEXEE, our optimized version of pthread mutex algorithm. MUTEXEE delivers significant performance and energy efficiency benefits over mutex.

Details & Code


Designed for the PPoPP '16 paper: “Optimistic concurrency with OPTIK.”

OPTIK is a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We implement the OPTIK pattern using the novel concept of OPTIK locks. We publish the code for OPTIK locks and several data structure implementations using OPTIK in ASCYLIB (see below). Using OPTIK, we have designed one array-map, two linked lists, three hash tables that use the array-map and the linked lists, a skip list, and a binary search tree.

Details & Code


Designed for the PPoPP '16 paper: “ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications.”

ESTIMA is an easy-to-use tool for extrapolating the scalability of in-memory applications. It is designed to perform a simple, yet important task: given an application on a small machine with a handful of cores, it extrapolates its performance to a larger machine with more cores. ESTIMA uses stalled cycles, both from hardware and software, reported by the application and runtime libraries. It automates the measurement and extrapolation process, requiring minimum input from the user.

Details & Code


Designed for the ASPLOS '15 paper: “Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures.”

ASCYLIB is a concurrent-search data-structure (CSDS) library. It contains over 30 implementations of linked lists, hash tables, skip lists, and binary search trees (BST). ASCYLIB contains sequential, lock-based, and lock-free implementations for each data structure. ASCYLIB works on x86, SPARC, and Tilera architectures and contains tests to evaluate the throughput, latency, latency distribution, and energy efficiency of the included data structures.

Details & Code


Designed for the SOSP '13 paper: “Everything You Always Wanted to Know About Synchronization but Were Afraid to Ask.”

SSYNC is a cross-platform synchronization suite; it works on x86_64, SPARC, and Tilera processors. SSYNC contains libslock, a library that abstracts lock algorithms behind a common interface and libssmp, a library with fine-tuned implementations of message passing for each of the supported platforms. SSYNC also includes microbenchmarks for measuring the latencies of the cache coherence, the locks, and the message passing, as well as ssht, i.e., a cache efficient hash table.

Details & Code


Designed for the EuroSys '12 paper: “TM2C: a Software Transactional Memory for Many-Cores.”

TM2C, is the first software transactional memory protocol for many-core systems. TM2C exploits network-on-chip communications to get granted accesses to shared data through efficient message passing. In particular, it allows visible read accesses and hence effective distributed contention management with eager conflict detection. TM2C comes with FairCM, a companion contention manager that ensures starvation-freedom, i.e., the eventual termination of every transactions. TM2C has been ported to Intel’s SCC, i386, x86_64, SPARC, and Tilera processors.

Details & Code

STMs and STM benchmarks

LPD has designed various state-of-the-art STM systems (SwissTM, eSTM) and STM benchmarks (STMBench7, Synchrobench, LeeTM).

Details & Code