Loop peeling based on quasi-invariance/induction variables View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-03

AUTHORS

Litong Song, Robert Glück, Yoshihiko Futamura

ABSTRACT

Loop optimization plays an important role in compiler optimization and program transformation. Many sophisticated techniques such as loop-invariance code motion have been developed. Loop peeling is a technique to assist parallelization of loops by unfolding loops a few times. This paper introduces a novel technique called loop peeling based on quasi-invariance/induction variables. It aims at finding a general and automatic method to derive how many times a given loop should be peeled. Our technique allows for a number of iterations before some variables assigned inside a given loop become invariance or induction variables. In this paper we define the notion of quasi-invariance/induction variables, present an algorithm for statically computing the optimal peeling length of a given loop. Our technique can increase the accuracy of program analyses, improve the effectiveness of loop peeling and is well-suited as supporting other optimization techniques in the context of supercomputers. More... »

PAGES

362-367

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf03160270

DOI

http://dx.doi.org/10.1007/bf03160270

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Waseda University", 
          "id": "https://www.grid.ac/institutes/grid.5290.e", 
          "name": [
            "Institute for Software Production Technology, Waseda University, Okubo 3-4-1, Shinjuku-ku, 169-8555, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Song", 
        "givenName": "Litong", 
        "id": "sg:person.014174302727.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014174302727.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Waseda University", 
          "id": "https://www.grid.ac/institutes/grid.5290.e", 
          "name": [
            "Institute for Software Production Technology, Waseda University, Okubo 3-4-1, Shinjuku-ku, 169-8555, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gl\u00fcck", 
        "givenName": "Robert", 
        "id": "sg:person.010754010217.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Waseda University", 
          "id": "https://www.grid.ac/institutes/grid.5290.e", 
          "name": [
            "Institute for Software Production Technology, Waseda University, Okubo 3-4-1, Shinjuku-ku, 169-8555, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Futamura", 
        "givenName": "Yoshihiko", 
        "id": "sg:person.016641004255.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641004255.43"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/367766.368168", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000891687"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/73560.73562", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004049074"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321105.321107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006574609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/197405.197406", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018107335"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/7902.7904", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027666846"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/115372.115320", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041304454"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001-03", 
    "datePublishedReg": "2001-03-01", 
    "description": "Loop optimization plays an important role in compiler optimization and program transformation. Many sophisticated techniques such as loop-invariance code motion have been developed. Loop peeling is a technique to assist parallelization of loops by unfolding loops a few times. This paper introduces a novel technique called loop peeling based on quasi-invariance/induction variables. It aims at finding a general and automatic method to derive how many times a given loop should be peeled. Our technique allows for a number of iterations before some variables assigned inside a given loop become invariance or induction variables. In this paper we define the notion of quasi-invariance/induction variables, present an algorithm for statically computing the optimal peeling length of a given loop. Our technique can increase the accuracy of program analyses, improve the effectiveness of loop peeling and is well-suited as supporting other optimization techniques in the context of supercomputers.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf03160270", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1135877", 
        "issn": [
          "1007-1202", 
          "1993-4998"
        ], 
        "name": "Wuhan University Journal of Natural Sciences", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "name": "Loop peeling based on quasi-invariance/induction variables", 
    "pagination": "362-367", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1892bd469c40867d1c9bf94d48846fc49f351564fbd7c4e5c550644f5a96dbfc"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf03160270"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005157673"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf03160270", 
      "https://app.dimensions.ai/details/publication/pub.1005157673"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:28", 
    "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/0000000373_0000000373/records_13081_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF03160270"
  }
]
 

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/bf03160270'

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/bf03160270'

Turtle is a human-readable linked data format.

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

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

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


 

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

93 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf03160270 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N93792fdae3224c60bad8dc333fd7cb89
4 schema:citation https://doi.org/10.1145/115372.115320
5 https://doi.org/10.1145/197405.197406
6 https://doi.org/10.1145/321105.321107
7 https://doi.org/10.1145/367766.368168
8 https://doi.org/10.1145/73560.73562
9 https://doi.org/10.1145/7902.7904
10 schema:datePublished 2001-03
11 schema:datePublishedReg 2001-03-01
12 schema:description Loop optimization plays an important role in compiler optimization and program transformation. Many sophisticated techniques such as loop-invariance code motion have been developed. Loop peeling is a technique to assist parallelization of loops by unfolding loops a few times. This paper introduces a novel technique called loop peeling based on quasi-invariance/induction variables. It aims at finding a general and automatic method to derive how many times a given loop should be peeled. Our technique allows for a number of iterations before some variables assigned inside a given loop become invariance or induction variables. In this paper we define the notion of quasi-invariance/induction variables, present an algorithm for statically computing the optimal peeling length of a given loop. Our technique can increase the accuracy of program analyses, improve the effectiveness of loop peeling and is well-suited as supporting other optimization techniques in the context of supercomputers.
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N44efb64352844c008bdfeb44ae838b59
17 N8b645fa9f0dd4432b3545ddbf415760d
18 sg:journal.1135877
19 schema:name Loop peeling based on quasi-invariance/induction variables
20 schema:pagination 362-367
21 schema:productId N03c579147fc14a20bb5ae4f5e60614dc
22 N2260d6da0c3b4344be62764c4b14e957
23 Ncb684d4ded75476cad87554241f4bf7d
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005157673
25 https://doi.org/10.1007/bf03160270
26 schema:sdDatePublished 2019-04-11T14:28
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N161614f0017d4b9cb354d3fff8bfae7c
29 schema:url http://link.springer.com/10.1007%2FBF03160270
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N03c579147fc14a20bb5ae4f5e60614dc schema:name readcube_id
34 schema:value 1892bd469c40867d1c9bf94d48846fc49f351564fbd7c4e5c550644f5a96dbfc
35 rdf:type schema:PropertyValue
36 N161614f0017d4b9cb354d3fff8bfae7c schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 N2260d6da0c3b4344be62764c4b14e957 schema:name doi
39 schema:value 10.1007/bf03160270
40 rdf:type schema:PropertyValue
41 N44efb64352844c008bdfeb44ae838b59 schema:issueNumber 1-2
42 rdf:type schema:PublicationIssue
43 N6441338c6023413297eb96a3429f26ed rdf:first sg:person.016641004255.43
44 rdf:rest rdf:nil
45 N8b645fa9f0dd4432b3545ddbf415760d schema:volumeNumber 6
46 rdf:type schema:PublicationVolume
47 N93792fdae3224c60bad8dc333fd7cb89 rdf:first sg:person.014174302727.03
48 rdf:rest N9f36db67c74d48e9907122f3a901ab41
49 N9f36db67c74d48e9907122f3a901ab41 rdf:first sg:person.010754010217.31
50 rdf:rest N6441338c6023413297eb96a3429f26ed
51 Ncb684d4ded75476cad87554241f4bf7d schema:name dimensions_id
52 schema:value pub.1005157673
53 rdf:type schema:PropertyValue
54 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
55 schema:name Mathematical Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
58 schema:name Numerical and Computational Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1135877 schema:issn 1007-1202
61 1993-4998
62 schema:name Wuhan University Journal of Natural Sciences
63 rdf:type schema:Periodical
64 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
65 schema:familyName Glück
66 schema:givenName Robert
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
68 rdf:type schema:Person
69 sg:person.014174302727.03 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
70 schema:familyName Song
71 schema:givenName Litong
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014174302727.03
73 rdf:type schema:Person
74 sg:person.016641004255.43 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
75 schema:familyName Futamura
76 schema:givenName Yoshihiko
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641004255.43
78 rdf:type schema:Person
79 https://doi.org/10.1145/115372.115320 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041304454
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1145/197405.197406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018107335
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1145/321105.321107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006574609
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1145/367766.368168 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000891687
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/73560.73562 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004049074
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1145/7902.7904 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027666846
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
92 schema:name Institute for Software Production Technology, Waseda University, Okubo 3-4-1, Shinjuku-ku, 169-8555, Tokyo, Japan
93 rdf:type schema:Organization
 




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


...