Relaxed concurrent ordering structures
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
| Auteur principal: | |
|---|---|
| Autres auteurs: | |
| Format: | Thèse |
| Langue: | eng |
| Publié: |
Massachusetts Institute of Technology
2018
|
| Sujets: | |
| Accès en ligne: | http://hdl.handle.net/1721.1/118089 |
| _version_ | 1826198067007717376 |
|---|---|
| author | Kopinsky, Justin |
| author2 | Nir Shavit. |
| author_facet | Nir Shavit. Kopinsky, Justin |
| author_sort | Kopinsky, Justin |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. |
| first_indexed | 2024-09-23T10:58:20Z |
| format | Thesis |
| id | mit-1721.1/118089 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:58:20Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1180892019-04-11T12:19:53Z Relaxed concurrent ordering structures Kopinsky, Justin Nir Shavit. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 131-137). 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. by Justin Kopinsky. Ph. D. 2018-09-17T15:57:02Z 2018-09-17T15:57:02Z 2018 2018 Thesis http://hdl.handle.net/1721.1/118089 1052124049 eng 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. http://dspace.mit.edu/handle/1721.1/7582 137 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kopinsky, Justin Relaxed concurrent ordering structures |
| title | Relaxed concurrent ordering structures |
| title_full | Relaxed concurrent ordering structures |
| title_fullStr | Relaxed concurrent ordering structures |
| title_full_unstemmed | Relaxed concurrent ordering structures |
| title_short | Relaxed concurrent ordering structures |
| title_sort | relaxed concurrent ordering structures |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/118089 |
| work_keys_str_mv | AT kopinskyjustin relaxedconcurrentorderingstructures |