No Hot-Spot Data Structures

Summary

The goal of this project is to design and implement novel data structure algorithms especially suited for many-core architectures.

Supervisor(s)

Dr Vincent Gramoli

Research Location

Computer Science

Program Type

PHD

Synopsis

The many-core era is changing the way we write programs. In fact, by multiplying the number of cores and no longer their clock frequency to provide higher performance capabilities without increasing energy consumption, many-cores make concurrency a de facto principle that programmers must take into account. Hitherto, concurrency was only considered an optional source of performance improvement, especially appealing for high-performance computing experts or for embarrassingly parallel applications that could be easily ported to parallel machines without much effort. Today, concurrency is the only way to make any application run faster on our cell phone than on our 10 year old desktop computers. Now that multi-cores are everywhere, the main challenge to reach high performance is to reduce the contention bottleneck at the heart of these applications, their data structures.

The goal of this research project is to design and implement data structures with low contention. Most applications, like key-value store, differ from regular scientific ones where data could be easily segregated among threads (or processes). This concurrency has severe drawbacks when concurrent threads have to exchange information or aggregate results as the corresponding synchronization induces contention. Designing appropriate data structures for synchronization is thus crucial to minimize the effect of contention. While we used to design algorithms with minimal asymptotic complexity in their number of steps, it is now crucial to design algorithms that produce as little contention as possible.

Keywords

Data Structure, NoSQL, Database, Concurrency, Multicore, algorithm, Contention, Synchronisation

Opportunity ID

The opportunity ID for this research opportunity is: 1789

Other opportunities with Dr Vincent Gramoli

• What Theory for Concurrency?
• Reusable Concurrent Data Types
• Reconfiguring Data Centers
• Evaluating Blockchain Systems