On Avoiding Spare Aborts in Transactional Memory View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-02-15

AUTHORS

Idit Keidar, Dmitri Perelman

ABSTRACT

This paper takes a step toward developing a theory for understanding aborts in transactional memory systems (TMs). Existing TMs may abort many transactions that could, in fact, commit without violating correctness. We call such unnecessary aborts spare aborts. We classify what kinds of spare aborts can be eliminated, and which cannot. We further study what kinds of spare aborts can be avoided efficiently. Specifically, we show that some spare aborts cannot be avoided, and that there is an inherent tradeoff between the overhead of a TM and the extent to which it reduces the number of spare aborts. We also present an efficient example TM algorithm that avoids certain kinds of spare aborts, and analyze its properties and performance. More... »

PAGES

261-285

References to SciGraph publications

  • 2008. Toward a Theory of Input Acceptance for Transactional Memories in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2008-01-01. Permissiveness in Transactional Memories in DISTRIBUTED COMPUTING
  • 2006. Transactional Locking II in DISTRIBUTED COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-015-9607-7

    DOI

    http://dx.doi.org/10.1007/s00224-015-9607-7

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0805", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Distributed Computing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Electrical Engineering, Technion, 32000, Haifa, Israel", 
              "id": "http://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Electrical Engineering, Technion, 32000, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Electrical Engineering, Technion, 32000, Haifa, Israel", 
              "id": "http://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Electrical Engineering, Technion, 32000, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Perelman", 
            "givenName": "Dmitri", 
            "id": "sg:person.015440102124.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015440102124.28"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11864219_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014890882", 
              "https://doi.org/10.1007/11864219_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92221-6_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006789727", 
              "https://doi.org/10.1007/978-3-540-92221-6_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-87779-0_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052578105", 
              "https://doi.org/10.1007/978-3-540-87779-0_21"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-02-15", 
        "datePublishedReg": "2015-02-15", 
        "description": "This paper takes a step toward developing a theory for understanding aborts in transactional memory systems (TMs). Existing TMs may abort many transactions that could, in fact, commit without violating correctness. We call such unnecessary aborts spare aborts. We classify what kinds of spare aborts can be eliminated, and which cannot. We further study what kinds of spare aborts can be avoided efficiently. Specifically, we show that some spare aborts cannot be avoided, and that there is an inherent tradeoff between the overhead of a TM and the extent to which it reduces the number of spare aborts. We also present an efficient example TM algorithm that avoids certain kinds of spare aborts, and analyze its properties and performance.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-015-9607-7", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "57"
          }
        ], 
        "keywords": [
          "memory system", 
          "certain kinds", 
          "memory", 
          "theory", 
          "kind", 
          "performance", 
          "extent", 
          "fact", 
          "paper", 
          "transactions", 
          "step", 
          "system", 
          "correctness", 
          "tradeoff", 
          "number", 
          "inherent tradeoff", 
          "abort", 
          "transactional memory systems", 
          "algorithm", 
          "properties", 
          "transactional memory", 
          "overhead", 
          "such unnecessary aborts spare aborts", 
          "unnecessary aborts spare aborts", 
          "aborts spare aborts", 
          "spare aborts", 
          "efficient example TM algorithm", 
          "example TM algorithm", 
          "TM algorithm"
        ], 
        "name": "On Avoiding Spare Aborts in Transactional Memory", 
        "pagination": "261-285", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1034835971"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-015-9607-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-015-9607-7", 
          "https://app.dimensions.ai/details/publication/pub.1034835971"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:36", 
        "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/article/article_667.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-015-9607-7"
      }
    ]
     

    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/s00224-015-9607-7'

    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/s00224-015-9607-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9607-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9607-7'


     

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

    118 TRIPLES      22 PREDICATES      60 URIs      46 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-015-9607-7 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author Na8ce10f4792a4a35a4548b4c6196372e
    7 schema:citation sg:pub.10.1007/11864219_14
    8 sg:pub.10.1007/978-3-540-87779-0_21
    9 sg:pub.10.1007/978-3-540-92221-6_33
    10 schema:datePublished 2015-02-15
    11 schema:datePublishedReg 2015-02-15
    12 schema:description This paper takes a step toward developing a theory for understanding aborts in transactional memory systems (TMs). Existing TMs may abort many transactions that could, in fact, commit without violating correctness. We call such unnecessary aborts spare aborts. We classify what kinds of spare aborts can be eliminated, and which cannot. We further study what kinds of spare aborts can be avoided efficiently. Specifically, we show that some spare aborts cannot be avoided, and that there is an inherent tradeoff between the overhead of a TM and the extent to which it reduces the number of spare aborts. We also present an efficient example TM algorithm that avoids certain kinds of spare aborts, and analyze its properties and performance.
    13 schema:genre article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree true
    16 schema:isPartOf Na8490ae614684e0c9dcd2ed634a740e9
    17 Nf70c85dee29b4484b6f45d678bf4db81
    18 sg:journal.1052098
    19 schema:keywords TM algorithm
    20 abort
    21 aborts spare aborts
    22 algorithm
    23 certain kinds
    24 correctness
    25 efficient example TM algorithm
    26 example TM algorithm
    27 extent
    28 fact
    29 inherent tradeoff
    30 kind
    31 memory
    32 memory system
    33 number
    34 overhead
    35 paper
    36 performance
    37 properties
    38 spare aborts
    39 step
    40 such unnecessary aborts spare aborts
    41 system
    42 theory
    43 tradeoff
    44 transactional memory
    45 transactional memory systems
    46 transactions
    47 unnecessary aborts spare aborts
    48 schema:name On Avoiding Spare Aborts in Transactional Memory
    49 schema:pagination 261-285
    50 schema:productId N155ab9975fc54dfca773d0f08ba63203
    51 N175e327bc94f4ff491c7a68f3155b210
    52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034835971
    53 https://doi.org/10.1007/s00224-015-9607-7
    54 schema:sdDatePublished 2022-01-01T18:36
    55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    56 schema:sdPublisher N6b2aa430c7654cefadd9bcbf2645c9f3
    57 schema:url https://doi.org/10.1007/s00224-015-9607-7
    58 sgo:license sg:explorer/license/
    59 sgo:sdDataset articles
    60 rdf:type schema:ScholarlyArticle
    61 N155ab9975fc54dfca773d0f08ba63203 schema:name doi
    62 schema:value 10.1007/s00224-015-9607-7
    63 rdf:type schema:PropertyValue
    64 N175e327bc94f4ff491c7a68f3155b210 schema:name dimensions_id
    65 schema:value pub.1034835971
    66 rdf:type schema:PropertyValue
    67 N22160fed7f8a4c3fab128f5f568e8aa5 rdf:first sg:person.015440102124.28
    68 rdf:rest rdf:nil
    69 N6b2aa430c7654cefadd9bcbf2645c9f3 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 Na8490ae614684e0c9dcd2ed634a740e9 schema:issueNumber 1
    72 rdf:type schema:PublicationIssue
    73 Na8ce10f4792a4a35a4548b4c6196372e rdf:first sg:person.07674464077.03
    74 rdf:rest N22160fed7f8a4c3fab128f5f568e8aa5
    75 Nf70c85dee29b4484b6f45d678bf4db81 schema:volumeNumber 57
    76 rdf:type schema:PublicationVolume
    77 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Mathematical Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Applied Mathematics
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Information and Computing Sciences
    85 rdf:type schema:DefinedTerm
    86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Computation Theory and Mathematics
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Distributed Computing
    91 rdf:type schema:DefinedTerm
    92 sg:journal.1052098 schema:issn 1432-4350
    93 1433-0490
    94 schema:name Theory of Computing Systems
    95 schema:publisher Springer Nature
    96 rdf:type schema:Periodical
    97 sg:person.015440102124.28 schema:affiliation grid-institutes:grid.6451.6
    98 schema:familyName Perelman
    99 schema:givenName Dmitri
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015440102124.28
    101 rdf:type schema:Person
    102 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
    103 schema:familyName Keidar
    104 schema:givenName Idit
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
    106 rdf:type schema:Person
    107 sg:pub.10.1007/11864219_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014890882
    108 https://doi.org/10.1007/11864219_14
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-3-540-87779-0_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052578105
    111 https://doi.org/10.1007/978-3-540-87779-0_21
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/978-3-540-92221-6_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006789727
    114 https://doi.org/10.1007/978-3-540-92221-6_33
    115 rdf:type schema:CreativeWork
    116 grid-institutes:grid.6451.6 schema:alternateName Department of Electrical Engineering, Technion, 32000, Haifa, Israel
    117 schema:name Department of Electrical Engineering, Technion, 32000, Haifa, Israel
    118 rdf:type schema:Organization
     




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


    ...