Files in this item

FilesDescriptionFormat

application/pdf

application/pdfGANGWANI-THESIS-2016.pdf (645kB)
(no description provided)PDF

Description

Title:Breaking serialization in lock-free multicore synchronization
Author(s):Gangwani, Tanmay
Advisor(s):Torrellas, Josep
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2016-07-18
Type:Thesis
URI:http://hdl.handle.net/2142/92858
Rights Information:Copyright 2016 Tanmay Gangwani
Date Available in IDEALS:2016-11-10
Date Deposited:2016-08


This item appears in the following Collection(s)

Item Statistics