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

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 N9659c0e734be49ceafa13909d9240772
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 N033f42ab518a4626acfec02de94c9fce
32 N0ffba744bcf14a4ebfdad15cdc03b299
33 N5525624825f24894a1ebdc99c25e219b
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 Nb0ccf5960752454483fe5b1176e23550
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 N033f42ab518a4626acfec02de94c9fce schema:name readcube_id
44 schema:value 7fadea7b93c51950b0f7d52891ea2a8c164875b4ef8df1b6b17deaa717bac056
45 rdf:type schema:PropertyValue
46 N0ffba744bcf14a4ebfdad15cdc03b299 schema:name dimensions_id
47 schema:value pub.1112986986
48 rdf:type schema:PropertyValue
49 N4b997c8655894e03aedcb1b9c9bba56c rdf:first Nd07918a8ac364d9f9859914549502326
50 rdf:rest rdf:nil
51 N5525624825f24894a1ebdc99c25e219b schema:name doi
52 schema:value 10.1007/s11227-019-02820-x
53 rdf:type schema:PropertyValue
54 N9659c0e734be49ceafa13909d9240772 rdf:first Nbb458d32a14844b4abcf1b447f2b7e7e
55 rdf:rest N4b997c8655894e03aedcb1b9c9bba56c
56 Nb0ccf5960752454483fe5b1176e23550 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 Nbb458d32a14844b4abcf1b447f2b7e7e schema:affiliation https://www.grid.ac/institutes/grid.7399.4
59 schema:familyName Niculescu
60 schema:givenName Virginia
61 rdf:type schema:Person
62 Nd07918a8ac364d9f9859914549502326 schema:affiliation https://www.grid.ac/institutes/grid.261120.6
63 schema:familyName Loulergue
64 schema:givenName Frédéric
65 rdf:type schema:Person
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)


...