Towards Automatic Lock Removal for Scalable Synchronization View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-11-05

AUTHORS

Maya Arbel , Guy Golan-Gueta , Eshcar Hillel , Idit Keidar

ABSTRACT

We present a code transformation for concurrent data structures, which increases their scalability without sacrificing correctness. Our transformation takes lock-based code and replaces some of the locking steps therein with optimistic synchronization in order to reduce contention. The main idea is to have each operation perform an optimistic traversal of the data structure as long as no shared memory locations are updated, and then proceed with pessimistic code. The transformed code inherits essential properties of the original one, including linearizability, serializability, and deadlock freedom.Our work complements existing pessimistic transformations that make sequential code thread-safe by adding locks. In essence, we provide a way to optimize such transformations by reducing synchronization bottlenecks (for example, locking the root of a tree). The resulting code scales well and significantly outperforms pessimistic approaches. We further compare our synthesized code to state-of-the-art data structures implemented by experts. We find that its performance is comparable to that achieved by the custom-tailored implementations. Our work thus shows the promise that automated approaches bear for overcoming the difficulty involved in manually hand-crafting concurrent data structures. More... »

PAGES

170-184

Book

TITLE

Distributed Computing

ISBN

978-3-662-48652-8
978-3-662-48653-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48653-5_12

DOI

http://dx.doi.org/10.1007/978-3-662-48653-5_12

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1002431597


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "The Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Yahoo Labs, Haifa, Israel", 
            "The Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arbel", 
        "givenName": "Maya", 
        "id": "sg:person.012531575477.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012531575477.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Yahoo Labs, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Yahoo Labs, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Golan-Gueta", 
        "givenName": "Guy", 
        "id": "sg:person.013051666705.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013051666705.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Yahoo Labs, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Yahoo Labs, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hillel", 
        "givenName": "Eshcar", 
        "id": "sg:person.07576456004.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07576456004.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Yahoo Labs, Haifa, Israel", 
            "The Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Keidar", 
        "givenName": "Idit", 
        "id": "sg:person.07674464077.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-11-05", 
    "datePublishedReg": "2015-11-05", 
    "description": "We present a code transformation for concurrent data structures, which increases their scalability without sacrificing correctness. Our transformation takes lock-based code and replaces some of the locking steps therein with optimistic synchronization in order to reduce contention. The main idea is to have each operation perform an optimistic traversal of the data structure as long as no shared memory locations are updated, and then proceed with pessimistic code. The transformed code inherits essential properties of the original one, including linearizability, serializability, and deadlock freedom.Our work complements existing pessimistic transformations that make sequential code thread-safe by adding locks. In essence, we provide a way to optimize such transformations by reducing synchronization bottlenecks (for example, locking the root of a tree). The resulting code scales well and significantly outperforms pessimistic approaches. We further compare our synthesized code to state-of-the-art data structures implemented by experts. We find that its performance is comparable to that achieved by the custom-tailored implementations. Our work thus shows the promise that automated approaches bear for overcoming the difficulty involved in manually hand-crafting concurrent data structures.", 
    "editor": [
      {
        "familyName": "Moses", 
        "givenName": "Yoram", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48653-5_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48652-8", 
        "978-3-662-48653-5"
      ], 
      "name": "Distributed Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "concurrent data structures", 
      "data structure", 
      "lock-based code", 
      "code transformations", 
      "optimistic synchronization", 
      "art data structure", 
      "memory locations", 
      "deadlock freedom", 
      "sequential code", 
      "synchronization bottlenecks", 
      "scalable synchronization", 
      "main idea", 
      "pessimistic approach", 
      "code", 
      "synchronization", 
      "scalability", 
      "serializability", 
      "correctness", 
      "traversal", 
      "such transformations", 
      "essential properties", 
      "bottleneck", 
      "implementation", 
      "linearizability", 
      "work", 
      "experts", 
      "performance", 
      "transformation", 
      "idea", 
      "operation", 
      "lock", 
      "contention", 
      "way", 
      "step", 
      "order", 
      "essence", 
      "structure", 
      "location", 
      "difficulties", 
      "freedom", 
      "state", 
      "promise", 
      "properties", 
      "removal", 
      "approach", 
      "optimistic traversal", 
      "shared memory locations", 
      "pessimistic code", 
      "pessimistic transformations", 
      "hand-crafting concurrent data structures", 
      "Automatic Lock Removal", 
      "Lock Removal"
    ], 
    "name": "Towards Automatic Lock Removal for Scalable Synchronization", 
    "pagination": "170-184", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002431597"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48653-5_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48653-5_12", 
      "https://app.dimensions.ai/details/publication/pub.1002431597"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_235.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48653-5_12"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48653-5_12'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48653-5_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48653-5_12'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48653-5_12'


 

This table displays all metadata directly associated to this object as RDF triples.

137 TRIPLES      23 PREDICATES      77 URIs      70 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48653-5_12 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N293f97ae7daf4acbbdde740023a32f3d
4 schema:datePublished 2015-11-05
5 schema:datePublishedReg 2015-11-05
6 schema:description We present a code transformation for concurrent data structures, which increases their scalability without sacrificing correctness. Our transformation takes lock-based code and replaces some of the locking steps therein with optimistic synchronization in order to reduce contention. The main idea is to have each operation perform an optimistic traversal of the data structure as long as no shared memory locations are updated, and then proceed with pessimistic code. The transformed code inherits essential properties of the original one, including linearizability, serializability, and deadlock freedom.Our work complements existing pessimistic transformations that make sequential code thread-safe by adding locks. In essence, we provide a way to optimize such transformations by reducing synchronization bottlenecks (for example, locking the root of a tree). The resulting code scales well and significantly outperforms pessimistic approaches. We further compare our synthesized code to state-of-the-art data structures implemented by experts. We find that its performance is comparable to that achieved by the custom-tailored implementations. Our work thus shows the promise that automated approaches bear for overcoming the difficulty involved in manually hand-crafting concurrent data structures.
7 schema:editor N50adb2be0c374b2a8f4cc7dd39d152dc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7a58c696fac245a7b025a273a240d8c9
12 schema:keywords Automatic Lock Removal
13 Lock Removal
14 approach
15 art data structure
16 bottleneck
17 code
18 code transformations
19 concurrent data structures
20 contention
21 correctness
22 data structure
23 deadlock freedom
24 difficulties
25 essence
26 essential properties
27 experts
28 freedom
29 hand-crafting concurrent data structures
30 idea
31 implementation
32 linearizability
33 location
34 lock
35 lock-based code
36 main idea
37 memory locations
38 operation
39 optimistic synchronization
40 optimistic traversal
41 order
42 performance
43 pessimistic approach
44 pessimistic code
45 pessimistic transformations
46 promise
47 properties
48 removal
49 scalability
50 scalable synchronization
51 sequential code
52 serializability
53 shared memory locations
54 state
55 step
56 structure
57 such transformations
58 synchronization
59 synchronization bottlenecks
60 transformation
61 traversal
62 way
63 work
64 schema:name Towards Automatic Lock Removal for Scalable Synchronization
65 schema:pagination 170-184
66 schema:productId N90c4d53ba9e0440b9a5a9755dc397aff
67 Ne96ea6ef1dca4bb8a2d2f4607864af0a
68 schema:publisher N6370917a58324fd3a2dee35ef512f07b
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002431597
70 https://doi.org/10.1007/978-3-662-48653-5_12
71 schema:sdDatePublished 2022-01-01T19:14
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher N0eeaaa99077b480a9a4e1ddcaca7f75f
74 schema:url https://doi.org/10.1007/978-3-662-48653-5_12
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N0eeaaa99077b480a9a4e1ddcaca7f75f schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N1ce1242f42ce4c82a086c28e3b3cd202 rdf:first sg:person.07576456004.08
81 rdf:rest N2c7f53a7bd87414d8e97a1b1042a55ff
82 N2659b1529e114c26a6c9d39e4a66704a schema:familyName Moses
83 schema:givenName Yoram
84 rdf:type schema:Person
85 N293f97ae7daf4acbbdde740023a32f3d rdf:first sg:person.012531575477.87
86 rdf:rest N9e7fb4e803f64e89bf61d6ba8519a64c
87 N2c7f53a7bd87414d8e97a1b1042a55ff rdf:first sg:person.07674464077.03
88 rdf:rest rdf:nil
89 N50adb2be0c374b2a8f4cc7dd39d152dc rdf:first N2659b1529e114c26a6c9d39e4a66704a
90 rdf:rest rdf:nil
91 N6370917a58324fd3a2dee35ef512f07b schema:name Springer Nature
92 rdf:type schema:Organisation
93 N7a58c696fac245a7b025a273a240d8c9 schema:isbn 978-3-662-48652-8
94 978-3-662-48653-5
95 schema:name Distributed Computing
96 rdf:type schema:Book
97 N90c4d53ba9e0440b9a5a9755dc397aff schema:name doi
98 schema:value 10.1007/978-3-662-48653-5_12
99 rdf:type schema:PropertyValue
100 N9e7fb4e803f64e89bf61d6ba8519a64c rdf:first sg:person.013051666705.78
101 rdf:rest N1ce1242f42ce4c82a086c28e3b3cd202
102 Ne96ea6ef1dca4bb8a2d2f4607864af0a schema:name dimensions_id
103 schema:value pub.1002431597
104 rdf:type schema:PropertyValue
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
109 schema:name Computer Software
110 rdf:type schema:DefinedTerm
111 sg:person.012531575477.87 schema:affiliation grid-institutes:grid.6451.6
112 schema:familyName Arbel
113 schema:givenName Maya
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012531575477.87
115 rdf:type schema:Person
116 sg:person.013051666705.78 schema:affiliation grid-institutes:None
117 schema:familyName Golan-Gueta
118 schema:givenName Guy
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013051666705.78
120 rdf:type schema:Person
121 sg:person.07576456004.08 schema:affiliation grid-institutes:None
122 schema:familyName Hillel
123 schema:givenName Eshcar
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07576456004.08
125 rdf:type schema:Person
126 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
127 schema:familyName Keidar
128 schema:givenName Idit
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
130 rdf:type schema:Person
131 grid-institutes:None schema:alternateName Yahoo Labs, Haifa, Israel
132 schema:name Yahoo Labs, Haifa, Israel
133 rdf:type schema:Organization
134 grid-institutes:grid.6451.6 schema:alternateName The Technion, Haifa, Israel
135 schema:name The Technion, Haifa, Israel
136 Yahoo Labs, Haifa, Israel
137 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...