Breaking serialization in lock-free multicore synchronization

Gangwani, Tanmay

Permalink

https://hdl.handle.net/2142/92858 Copy

Description

Title

Breaking serialization in lock-free multicore synchronization

Author(s)

Gangwani, Tanmay

Issue Date

2016-07-18

Director of Research (if dissertation) or Advisor (if thesis)

Torrellas, Josep

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• lock-free synchronization
• serialization
• parallel programming

Abstract

In multicores, performance-critical synchronization is increasingly performed in a lock-free manner using atomic instructions such as CAS or LL/SC. However, when many processors synchronize on the same variable, performance can still degrade significantly. Contending writes get serialized, creating a non-scalable condition. Past proposals that build hardware queues of synchronizing processors do not fundamentally solve this problem. At best, they help to efficiently serialize the contending writes. We propose a novel architecture that breaks the serialization of hardware queues and enables the queued processors to perform lock-free synchronization in parallel. The architecture, called Caspar, is able to (1) execute the CASes in the queued-up processors in parallel through eager forwarding of expected values, and (2) validate the CASes in parallel and dequeue groups of processors at a time. The result is highly scalable synchronization. We evaluate Caspar with simulations of a 64-core chip. Compared to existing proposals with hardware queues, Caspar improves the throughput of kernels by 32% on average and reduces the execution time of the sections considered in lock-free versions of applications by 47% on average. This makes these sections 2.5x faster than in the original applications.

Graduation Semester

2016-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/92858

Copyright and License Information

Copyright 2016 Tanmay Gangwani

Owning Collections