Transforming powerlist-based divide-and-conquer programs for an improved execution model View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-25

AUTHORS

Virginia Niculescu, Frédéric Loulergue

ABSTRACT

Powerlists are data structures that can be successfully used for defining parallel programs based on divide-and-conquer paradigm. These parallel recursive data structures and their algebraic theories offer both a methodology to design parallel algorithms and parallel programming abstractions to ease the development of parallel applications. The paper presents a technique for speeding up the parallel recursive programs defined based on powerlists. The improvements are achieved by applying transformation rules that introduce tuple functions and prefix operators, for which a more efficient execution model is defined. Together with the execution model, a cost model is also defined in order to allow a proper evaluation. The treated examples emphasise the fact that the transformation leads to important improvements of the programs. The speeding up is achieved by reducing the number of recursive calls, and also by enable the fusion of splitting/combining operations on different data structures. In addition, enhancing the function that has to be computed to other useful functions using a tuple, could improved the cost reduction even more. More... »

PAGES

1-22

References to SciGraph publications

  • 1987. An Introduction to the Theory of Lists in LOGIC OF PROGRAMMING AND CALCULI OF DISCRETE DESIGN
  • 1995. Architecture independent massive parallelization of divide-and-conquer algorithms in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 2004. Interactive Theorem Proving and Program Development, Coq’Art: The Calculus of Inductive Constructions in NONE
  • 1996. Construction of list homomorphisms by tupling and fusion in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1996
  • 2007. Data-Distributions in PowerList Theory in THEORETICAL ASPECTS OF COMPUTING – ICTAC 2007
  • 2003. SAT: A Programming Methodology with Skeletons and Collective Operations in PATTERNS AND SKELETONS FOR PARALLEL AND DISTRIBUTED COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11227-019-02820-x

    DOI

    http://dx.doi.org/10.1007/s11227-019-02820-x

    DIMENSIONS

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


    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": "Babe\u0219-Bolyai University", 
              "id": "https://www.grid.ac/institutes/grid.7399.4", 
              "name": [
                "Faculty of Mathematics and Computer Science, Babe\u015f-Bolyai University, Cluj-Napoca, Romania"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Niculescu", 
            "givenName": "Virginia", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Northern Arizona University", 
              "id": "https://www.grid.ac/institutes/grid.261120.6", 
              "name": [
                "School of Informatics Computing and Cyber Systems, Northern Arizona University, Flagstaff, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Loulergue", 
            "givenName": "Fr\u00e9d\u00e9ric", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-60117-1_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000350993", 
              "https://doi.org/10.1007/3-540-60117-1_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1965-0178586-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000912574"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/197320.197356", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007737646"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(90)90147-a", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019824477"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1023848190", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-07964-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023848190", 
              "https://doi.org/10.1007/978-3-662-07964-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-07964-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023848190", 
              "https://doi.org/10.1007/978-3-662-07964-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-87374-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024345342", 
              "https://doi.org/10.1007/978-3-642-87374-4_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-0097-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025959239", 
              "https://doi.org/10.1007/978-1-4471-0097-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-0097-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025959239", 
              "https://doi.org/10.1007/978-1-4471-0097-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/154630.154643", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026830871"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.future.2009.05.021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034521585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/141471.141494", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035391141"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61550-4_166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039676537", 
              "https://doi.org/10.1007/3-540-61550-4_166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75292-9_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045899214", 
              "https://doi.org/10.1007/978-3-540-75292-9_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75292-9_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045899214", 
              "https://doi.org/10.1007/978-3-540-75292-9_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/79173.79181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049385325"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/candar.2013.17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093426451"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/synasc.2014.51", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095341631"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139173018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098775702"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/pdcat.2017.00049", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1101866459"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-25", 
        "datePublishedReg": "2019-03-25", 
        "description": "Powerlists are data structures that can be successfully used for defining parallel programs based on divide-and-conquer paradigm. These parallel recursive data structures and their algebraic theories offer both a methodology to design parallel algorithms and parallel programming abstractions to ease the development of parallel applications. The paper presents a technique for speeding up the parallel recursive programs defined based on powerlists. The improvements are achieved by applying transformation rules that introduce tuple functions and prefix operators, for which a more efficient execution model is defined. Together with the execution model, a cost model is also defined in order to allow a proper evaluation. The treated examples emphasise the fact that the transformation leads to important improvements of the programs. The speeding up is achieved by reducing the number of recursive calls, and also by enable the fusion of splitting/combining operations on different data structures. In addition, enhancing the function that has to be computed to other useful functions using a tuple, could improved the cost reduction even more.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s11227-019-02820-x", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133522", 
            "issn": [
              "0920-8542", 
              "1573-0484"
            ], 
            "name": "The Journal of Supercomputing", 
            "type": "Periodical"
          }
        ], 
        "name": "Transforming powerlist-based divide-and-conquer programs for an improved execution model", 
        "pagination": "1-22", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "7fadea7b93c51950b0f7d52891ea2a8c164875b4ef8df1b6b17deaa717bac056"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11227-019-02820-x"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112986986"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11227-019-02820-x", 
          "https://app.dimensions.ai/details/publication/pub.1112986986"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:05", 
        "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/0000000366_0000000366/records_112063_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs11227-019-02820-x"
      }
    ]
     

    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/s11227-019-02820-x'

    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/s11227-019-02820-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11227-019-02820-x'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11227-019-02820-x'


     

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

    122 TRIPLES      21 PREDICATES      42 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11227-019-02820-x schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nb3b750d03fa54f569ad8646271bebf70
    4 schema:citation sg:pub.10.1007/3-540-60117-1_7
    5 sg:pub.10.1007/3-540-61550-4_166
    6 sg:pub.10.1007/978-1-4471-0097-3_2
    7 sg:pub.10.1007/978-3-540-75292-9_27
    8 sg:pub.10.1007/978-3-642-87374-4_1
    9 sg:pub.10.1007/978-3-662-07964-5
    10 https://app.dimensions.ai/details/publication/pub.1023848190
    11 https://doi.org/10.1016/0304-3975(90)90147-a
    12 https://doi.org/10.1016/j.future.2009.05.021
    13 https://doi.org/10.1017/cbo9781139173018
    14 https://doi.org/10.1090/s0025-5718-1965-0178586-1
    15 https://doi.org/10.1109/candar.2013.17
    16 https://doi.org/10.1109/pdcat.2017.00049
    17 https://doi.org/10.1109/synasc.2014.51
    18 https://doi.org/10.1145/141471.141494
    19 https://doi.org/10.1145/154630.154643
    20 https://doi.org/10.1145/197320.197356
    21 https://doi.org/10.1145/79173.79181
    22 schema:datePublished 2019-03-25
    23 schema:datePublishedReg 2019-03-25
    24 schema:description Powerlists are data structures that can be successfully used for defining parallel programs based on divide-and-conquer paradigm. These parallel recursive data structures and their algebraic theories offer both a methodology to design parallel algorithms and parallel programming abstractions to ease the development of parallel applications. The paper presents a technique for speeding up the parallel recursive programs defined based on powerlists. The improvements are achieved by applying transformation rules that introduce tuple functions and prefix operators, for which a more efficient execution model is defined. Together with the execution model, a cost model is also defined in order to allow a proper evaluation. The treated examples emphasise the fact that the transformation leads to important improvements of the programs. The speeding up is achieved by reducing the number of recursive calls, and also by enable the fusion of splitting/combining operations on different data structures. In addition, enhancing the function that has to be computed to other useful functions using a tuple, could improved the cost reduction even more.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf sg:journal.1133522
    29 schema:name Transforming powerlist-based divide-and-conquer programs for an improved execution model
    30 schema:pagination 1-22
    31 schema:productId N27a55de815df43a38f046f967069e231
    32 N3e7194a8b3544fd8ab7e0c9529efc9bb
    33 N75061d9a08d04b2e94f7e5c99867c34d
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112986986
    35 https://doi.org/10.1007/s11227-019-02820-x
    36 schema:sdDatePublished 2019-04-11T13:05
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher Nfbc5bbcde9d54d5cbd052e192f2a4134
    39 schema:url https://link.springer.com/10.1007%2Fs11227-019-02820-x
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset articles
    42 rdf:type schema:ScholarlyArticle
    43 N0d2b000c16b14c5fbc6faed1a05f722c schema:affiliation https://www.grid.ac/institutes/grid.261120.6
    44 schema:familyName Loulergue
    45 schema:givenName Frédéric
    46 rdf:type schema:Person
    47 N27a55de815df43a38f046f967069e231 schema:name doi
    48 schema:value 10.1007/s11227-019-02820-x
    49 rdf:type schema:PropertyValue
    50 N3e7194a8b3544fd8ab7e0c9529efc9bb schema:name dimensions_id
    51 schema:value pub.1112986986
    52 rdf:type schema:PropertyValue
    53 N75061d9a08d04b2e94f7e5c99867c34d schema:name readcube_id
    54 schema:value 7fadea7b93c51950b0f7d52891ea2a8c164875b4ef8df1b6b17deaa717bac056
    55 rdf:type schema:PropertyValue
    56 Nb3b750d03fa54f569ad8646271bebf70 rdf:first Nb66ba3b784294db5b91be3bb6cc4333e
    57 rdf:rest Nd683e3829b1448f6863ff8ff6a13ca58
    58 Nb66ba3b784294db5b91be3bb6cc4333e schema:affiliation https://www.grid.ac/institutes/grid.7399.4
    59 schema:familyName Niculescu
    60 schema:givenName Virginia
    61 rdf:type schema:Person
    62 Nd683e3829b1448f6863ff8ff6a13ca58 rdf:first N0d2b000c16b14c5fbc6faed1a05f722c
    63 rdf:rest rdf:nil
    64 Nfbc5bbcde9d54d5cbd052e192f2a4134 schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Information and Computing Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Computation Theory and Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1133522 schema:issn 0920-8542
    73 1573-0484
    74 schema:name The Journal of Supercomputing
    75 rdf:type schema:Periodical
    76 sg:pub.10.1007/3-540-60117-1_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000350993
    77 https://doi.org/10.1007/3-540-60117-1_7
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/3-540-61550-4_166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039676537
    80 https://doi.org/10.1007/3-540-61550-4_166
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-1-4471-0097-3_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025959239
    83 https://doi.org/10.1007/978-1-4471-0097-3_2
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/978-3-540-75292-9_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045899214
    86 https://doi.org/10.1007/978-3-540-75292-9_27
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/978-3-642-87374-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024345342
    89 https://doi.org/10.1007/978-3-642-87374-4_1
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/978-3-662-07964-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023848190
    92 https://doi.org/10.1007/978-3-662-07964-5
    93 rdf:type schema:CreativeWork
    94 https://app.dimensions.ai/details/publication/pub.1023848190 schema:CreativeWork
    95 https://doi.org/10.1016/0304-3975(90)90147-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1019824477
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/j.future.2009.05.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034521585
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1017/cbo9781139173018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098775702
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1090/s0025-5718-1965-0178586-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000912574
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1109/candar.2013.17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093426451
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1109/pdcat.2017.00049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101866459
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/synasc.2014.51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095341631
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/141471.141494 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035391141
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1145/154630.154643 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026830871
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/197320.197356 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007737646
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/79173.79181 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049385325
    116 rdf:type schema:CreativeWork
    117 https://www.grid.ac/institutes/grid.261120.6 schema:alternateName Northern Arizona University
    118 schema:name School of Informatics Computing and Cyber Systems, Northern Arizona University, Flagstaff, USA
    119 rdf:type schema:Organization
    120 https://www.grid.ac/institutes/grid.7399.4 schema:alternateName Babeș-Bolyai University
    121 schema:name Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania
    122 rdf:type schema:Organization
     




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


    ...