What Theory for Concurrency?

Summary

The goal of this project is to measure theoretically the concurrency one can expect out of a concurrent program for multicore. 

Supervisor(s)

Dr Vincent Gramoli

Research Location

Information Technologies

Program Type

PHD

Synopsis

The devices we use on a daily basis do not compute faster than the desktop computers we used 10 years ago. Manufacturers have just started multiplying the CPU cores in handheld phones, adding multi-cores and concurrent capabilities to almost all computing devices. Writing concurrent software is the only way to improve performance: making graphics of video games more fluid, internet browsers faster, or smartphone applications more responsive. Concurrent programming is however a very difficult task often reserved to experts. In an attempt to simplify concurrent programming, hardware manufacturers propose transactional instructions to complement the more traditional but deadlock-prone locks.

The goal of this research project is to define formal concurrency metrics and to design shared-memory algorithms that are optimal with respect to these metrics. More precisely, the core idea is to compare theoretically speculative (transaction-based) synchronization techniques against non-speculative ones (lock). The former allows concurrent executions to the same memory locations and resolve a decision lazily whereas the latter requires to avoid conflicts ahead of time. While the latter seems more conservative than the former, to our knowledge there is no known lower bound on the concurrency cost of using locks.

Additional Information

Want to find out more?

Contact us to find out what’s involved in applying for a PhD. Domestic students and International students

Contact Research Expert to find out more about participating in this opportunity.

Browse for other opportunities within the Information Technologies .

Keywords

Concurrency, Data Structure, Impossibility Result, Multicore, Mutual Exclusion, Transaction, Synchronisation, algorithm, parallelism

Opportunity ID

The opportunity ID for this research opportunity is: 1788

Other opportunities with Dr Vincent Gramoli