Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Thom Frühwirth

ABSTRACT

Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons: - Up to now, no parallel computation model for CHR was defined. - Tarjan’s optimal union-find is known to be hard to parallelize. - The parallel code should be as close as possible to the sequential one. It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR. More... »

PAGES

113-127

References to SciGraph publications

  • 2004. The Refined Operational Semantics of Constraint Handling Rules in LOGIC PROGRAMMING
  • 2005-06-10. Operational semantics and confluence of constraint propagation rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP97
  • 2003. Essentials of Constraint Programming in NONE
  • Book

    TITLE

    Logic Programming

    ISBN

    978-3-540-29208-1
    978-3-540-31947-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11562931_11

    DOI

    http://dx.doi.org/10.1007/11562931_11

    DIMENSIONS

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


    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/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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Ulm", 
              "id": "https://www.grid.ac/institutes/grid.6582.9", 
              "name": [
                "Faculty of Computer Science, University of Ulm, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fr\u00fchwirth", 
            "givenName": "Thom", 
            "id": "sg:person.013750414271.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0743-1066(98)10005-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000275719"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/96709.96733", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003265233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/62.2160", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006789528"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0017444", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010989701", 
              "https://doi.org/10.1007/bfb0017444"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0017444", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010989701", 
              "https://doi.org/10.1007/bfb0017444"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/195613.195617", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015103074"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1023426236", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-05138-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023426236", 
              "https://doi.org/10.1007/978-3-662-05138-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-05138-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023426236", 
              "https://doi.org/10.1007/978-3-662-05138-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27775-0_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043968221", 
              "https://doi.org/10.1007/978-3-540-27775-0_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27775-0_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043968221", 
              "https://doi.org/10.1007/978-3-540-27775-0_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/116873.116878", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048960048"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/99583.99627", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051898893"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s1471068405002541", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053824991"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s1471068405002541", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053824991"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons: - Up to now, no parallel computation model for CHR was defined. - Tarjan\u2019s optimal union-find is known to be hard to parallelize. - The parallel code should be as close as possible to the sequential one. It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR.", 
        "editor": [
          {
            "familyName": "Gabbrielli", 
            "givenName": "Maurizio", 
            "type": "Person"
          }, 
          {
            "familyName": "Gupta", 
            "givenName": "Gopal", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11562931_11", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-29208-1", 
            "978-3-540-31947-4"
          ], 
          "name": "Logic Programming", 
          "type": "Book"
        }, 
        "name": "Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis", 
        "pagination": "113-127", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11562931_11"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "8f2ba8bd3c19aab02e417f9288009a9b91e6a0a924bccf65ab223bcdc3808ec6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030053121"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11562931_11", 
          "https://app.dimensions.ai/details/publication/pub.1030053121"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T17:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000261.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/11562931_11"
      }
    ]
     

    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/11562931_11'

    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/11562931_11'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11562931_11'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11562931_11'


     

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

    105 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11562931_11 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N31ef0ce32bc4410c80302dadabc8d3c0
    4 schema:citation sg:pub.10.1007/978-3-540-27775-0_7
    5 sg:pub.10.1007/978-3-662-05138-2
    6 sg:pub.10.1007/bfb0017444
    7 https://app.dimensions.ai/details/publication/pub.1023426236
    8 https://doi.org/10.1016/s0743-1066(98)10005-5
    9 https://doi.org/10.1017/s1471068405002541
    10 https://doi.org/10.1145/116873.116878
    11 https://doi.org/10.1145/195613.195617
    12 https://doi.org/10.1145/62.2160
    13 https://doi.org/10.1145/96709.96733
    14 https://doi.org/10.1145/99583.99627
    15 schema:datePublished 2005
    16 schema:datePublishedReg 2005-01-01
    17 schema:description Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons: - Up to now, no parallel computation model for CHR was defined. - Tarjan’s optimal union-find is known to be hard to parallelize. - The parallel code should be as close as possible to the sequential one. It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR.
    18 schema:editor Na0e88b50e368442094ac3e422b608d6f
    19 schema:genre chapter
    20 schema:inLanguage en
    21 schema:isAccessibleForFree true
    22 schema:isPartOf N8d1c6c47a8ce4fe0a3d47797c48c2428
    23 schema:name Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis
    24 schema:pagination 113-127
    25 schema:productId N4107f0b943c44fde94170af4b976f7e1
    26 N41d99eaf9f41420cb38e7e3c191a6993
    27 N4801f5697f19463d9cfe03a297589d46
    28 schema:publisher N1fad19b7f13c41f39f2aef370f730fb3
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030053121
    30 https://doi.org/10.1007/11562931_11
    31 schema:sdDatePublished 2019-04-15T17:14
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher N285b3727a1314151950117d047daaec7
    34 schema:url http://link.springer.com/10.1007/11562931_11
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset chapters
    37 rdf:type schema:Chapter
    38 N045d260e71a1422fa0477bb44a517035 schema:familyName Gupta
    39 schema:givenName Gopal
    40 rdf:type schema:Person
    41 N09f127e0e0274d998ecca1fb04cac881 schema:familyName Gabbrielli
    42 schema:givenName Maurizio
    43 rdf:type schema:Person
    44 N1fad19b7f13c41f39f2aef370f730fb3 schema:location Berlin, Heidelberg
    45 schema:name Springer Berlin Heidelberg
    46 rdf:type schema:Organisation
    47 N285b3727a1314151950117d047daaec7 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N31ef0ce32bc4410c80302dadabc8d3c0 rdf:first sg:person.013750414271.15
    50 rdf:rest rdf:nil
    51 N4107f0b943c44fde94170af4b976f7e1 schema:name readcube_id
    52 schema:value 8f2ba8bd3c19aab02e417f9288009a9b91e6a0a924bccf65ab223bcdc3808ec6
    53 rdf:type schema:PropertyValue
    54 N41d99eaf9f41420cb38e7e3c191a6993 schema:name doi
    55 schema:value 10.1007/11562931_11
    56 rdf:type schema:PropertyValue
    57 N4801f5697f19463d9cfe03a297589d46 schema:name dimensions_id
    58 schema:value pub.1030053121
    59 rdf:type schema:PropertyValue
    60 N501638c2413f4ebdb7d17a9ad2ed2dbf rdf:first N045d260e71a1422fa0477bb44a517035
    61 rdf:rest rdf:nil
    62 N8d1c6c47a8ce4fe0a3d47797c48c2428 schema:isbn 978-3-540-29208-1
    63 978-3-540-31947-4
    64 schema:name Logic Programming
    65 rdf:type schema:Book
    66 Na0e88b50e368442094ac3e422b608d6f rdf:first N09f127e0e0274d998ecca1fb04cac881
    67 rdf:rest N501638c2413f4ebdb7d17a9ad2ed2dbf
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Computation Theory and Mathematics
    73 rdf:type schema:DefinedTerm
    74 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
    75 schema:familyName Frühwirth
    76 schema:givenName Thom
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
    78 rdf:type schema:Person
    79 sg:pub.10.1007/978-3-540-27775-0_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043968221
    80 https://doi.org/10.1007/978-3-540-27775-0_7
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-662-05138-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023426236
    83 https://doi.org/10.1007/978-3-662-05138-2
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/bfb0017444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010989701
    86 https://doi.org/10.1007/bfb0017444
    87 rdf:type schema:CreativeWork
    88 https://app.dimensions.ai/details/publication/pub.1023426236 schema:CreativeWork
    89 https://doi.org/10.1016/s0743-1066(98)10005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000275719
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1017/s1471068405002541 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053824991
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1145/116873.116878 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048960048
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1145/195613.195617 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015103074
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/62.2160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006789528
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/96709.96733 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003265233
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/99583.99627 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051898893
    102 rdf:type schema:CreativeWork
    103 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
    104 schema:name Faculty of Computer Science, University of Ulm, Germany
    105 rdf:type schema:Organization
     




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


    ...