Contention Bounds for Locking Computations

This thesis quantifies lock contention in multithreaded programs by expanding the theoretical model of task-parallel execution traces to account for mutual exclusion locks. While lock profiling and contention detection tools abound in software, empirical measurements of contention suffer from wide fluctuations across different executions of the same code due to scheduling variation and processor availability. In this work we present analytical bounds on the maximum possible contention incurred by a given program over all possible execution schedules, even when running alongside other programs in a busy environment or when scheduled by an adversary. Although we show that computing the exact optimum is NP-hard for general task graphs, in the restricted case of fork-join (series-parallel) computations with 𝑛 strands and a single lock we offer a Θ(𝑛²) exact algorithm as well as a Θ(𝑛) 2-approximation for worst case contention. In proving these bounds linking maximum contention to the antichain sizes of a program’s parallel trace, we establish graph-based properties of worst case execution schedules that also apply directly to the related single processor scheduling problem of average response time under task precedence constraints. In addition, our analysis of worst case contention offers improved estimates for the completion time of locking computations under the execution trace model.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Li, Wanlin

Advisors dc:contributor.advisor

• Leiserson, Charles E.
• Kuszmaul, William

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/145079

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/145079