Delegation Systems for Efficient and Safe Multi-Core Programming

Highly parallel hardware is common in many contemporary computing platforms, making multi-threaded design key to high application performance. Today, the dominant paradigm for multi-threaded programming is synchronized access to shared memory, or locking for short. In this thesis, we revisit the question of delegation vs. synchronized access to shared memory, and show through analysis and demonstration that delegation can be much faster than locking under a range of common circumstances, even in highly concurrent, uncontended scenarios. Starting from first principles, we propose fast, fly-weight delegation (ffwd). The highly optimized design of ffwd allows it to significantly outperform prior work on delegation, while retaining the scalability advantage. Next, we introduce gepard, that adopts light-weight user threads (fibers), designed for delegation, on both the client and server sides of the delegation system. In addition to improved performance, gepard adds support for common software requirements such as nested delegation and lock acquisition in delegated functions. In our evaluation, we use 7 benchmark applications, and 6 shared data structures, and compare our delegation system to a selection of lock, combining, lock-free, software transactional memory and delegation designs. We port memcached to delegation, and show a 4.3 X improvement over stock memcached on YCSB workloads, and a modest improvement over sharded stock memcached. We also demonstrate multi-redis, a multi-threaded version of redis, which delegates the single-threaded database to one thread. Multi-redis yields 17 X throughput increase vs single-threaded stock redis, on standard workloads, using 32 hardware threads. It also improves modestly on 32-way sharded stock redis. Using gepard, performance is improved up to 4 X with respect to locking methods on splash2.