2026-09-19T17:12:39Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/92858 2023-07-11 col_2142_5131 com_2142_5130

Torrellas, Josep Gangwani, Tanmay 2016-11-10T17:55:16Z 2016-11-10T17:55:16Z 2016-07-18 2016-08 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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-11-09 without embargo terms The student, Tanmay Gangwani, accepted the attached license on 2016-07-18 at 14:05. The student, Tanmay Gangwani, submitted this Thesis for approval on 2016-07-18 at 14:25. This Thesis was approved for publication on 2016-07-18 at 15:13. DSpace SAF Submission Ingestion Package generated from Vireo submission #9975 on 2016-11-09 at 10:25:18 Made available in DSpace on 2016-11-10T17:55:16Z (GMT). No. of bitstreams: 2 GANGWANI-THESIS-2016.pdf: 645222 bytes, checksum: 8d88d90984ee511ebc9d7720dd30c2fc (MD5) LICENSE.txt: 4212 bytes, checksum: 3fad0c180e8fc58bf9d82976ab8aac56 (MD5) Previous issue date: 2016-07-18 application/pdf http://hdl.handle.net/2142/92858 en Copyright 2016 Tanmay Gangwani lock-free synchronization serialization parallel programming Breaking serialization in lock-free multicore synchronization text text Electrical & Computer Eng Electrical & Computer Engr University of Illinois at Urbana-Champaign Thesis M.S.