Relaxed concurrent ordering structures

Efficient implementations of concurrent ordering structures, including stacks, queues, and priority queues, have long been elusive due to an inherent bottleneck on the 'head' element. We argue that classical semantics which are easy to support in sequential settings are stronger than necessary for concurrent applications, and instead define new semantics for implementing relaxed ordering structures: relaxed structures need only return elements which are probabilistically near the head element. This thesis demonstrates the effectiveness of relaxed semantics by formally defining a notion of k-relaxation which imposes behavior 'similar' to that of a structure which returns one of the k elements nearest the head uniformly at random. This behavior is encapsulated by two probabilistic criteria: error boundedness-a bound on the distance of a returned element from the head--and fairness--a bound on the number of operations an element has to wait before being returned by some thread. We design, analyze, and implement k-relaxed algorithms in this model, showing both that they achieve good values of k in theory and that they exhibit empirically good performance on applications such as Single-Source Shortest Paths. Finally, we introduce a general framework for using relaxed structures to schedule and execute a wide class of problems which can be formulated as a series of task executions with dependencies between tasks. Our framework provides a case study demonstrating that applications can use our model of relaxed data structures to prove that the extra work induced by reordering tasks is low in the settings that we consider. Empirically, our benchmarks show that the low overhead is more than offset by increased throughput, resulting in improved performance on tasks such as Maximal Independent Set compared to an exact scheduler.

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

2018

Author dc:creator

• Kopinsky, Justin

Advisor dc:contributor.advisor

• Nir Shavit.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/118089

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/118089