Sanidhya Kashyap

Ph.D. Candidate

School of Computer Science

College of Computing

Georgia Institute of Technology

Date: Thursday, June 11th

Time: 1:00 PM-3:00 PM (EST)

Location: https://bluejeans.com/209362103 (remote)

Committee:

Dr. Taesoo Kim (Advisor), School of Computer Science, Georgia Institute of Technology

Dr. Changwoo Min (Co-advisor), Virginia Tech

Dr. Ada Gavrilovska, School of Computer Science, Georgia Institute of Technology

Dr. Irina Calciu, VMware Research

Dr. Joy Arulraj, School of Computer Science, Georgia Institute of Technology

Abstract:

Over the past decade, multicore machines have become the norm. A single machine is

capable of having thousands of hardware threads or cores. Even cloud providers offer such

large multicore machines for data processing engines and databases. Thus, a fundamental

question arises is how efficient are existing synchronization primitives—timestamping and

locking—that developers use for designing concurrent, scalable, and performant applications.

Hence, this dissertation focuses on understanding the scalability aspect of these primitives,

and presents new algorithms and approaches, that either leverage the hardware or the

application domain knowledge, to scale up to hundreds of cores.

First, the thesis presents Ordo, a scalable ordering or timestamping primitive, that forms

the basis of designing scalable timestamp-based concurrency control mechanisms. Ordo

relies on invariant hardware clocks and provides a notion of a globally synchronized clock

within a machine. We use the Ordo primitive to redesign a synchronization mechanism and

concurrency control mechanisms in databases and software transactional memory.

Later, this thesis focuses on the scalability aspect of locks in both virtualized and

non-virtualized scenarios. We identify that synchronization primitives suffer from various

preemption problems that happen because of the double scheduling problem. We then

leverage the hypervisor’s scheduler to address this problem by bridging the semantic gap in

the form of scheduling information between the hypervisor and VMs.

Finally, we focus on the design of lock algorithms in general. We find that locks in

practice have discrepancies from locks in design. For example, popular spinlocks suffer

from excessive cache-line bouncing in multicore (NUMA) systems, while scalable,

NUMA-aware locks exhibit sub-par single-thread performance. We classify several

dominating factors that impact the performance of lock algorithms. We then propose

a new technique, shuffling, that can dynamically accommodate all these factors, without

slowing down the critical path of the lock. The key idea of shuffling is to re-order the queue

of threads waiting to acquire the lock with some pre-established policy. Using shuffling, we

propose a family of locking algorithms, called ShflLocks that respect all factors, efficiently

utilize waiters, and achieve the best performance.