Binding-time analysis applied to mathematical algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1996

AUTHORS

Robert Glück , Ryo Nakashige , Robert Zöchling

ABSTRACT

Our goal is to incorporate state-of-the-art partial evaluation in a library of general-purpose algorithms — in particular, mathematical algorithms — in order to allow the automatic creation of efficient, special-purpose programs. The main goal is efficiency: a specialized program often runs significantly faster than its generic version. This paper shows how a binding-time analysis can be used to identify potential sources for specialization in mathematical algorithms. The method is surprisingly simple and effective. To demonstrate the effectiveness of this approach we used an automatic partial evaluator for Fortran that we developed. Results for five well-known algorithms show that some remarkable speedup factors can be obtained on a uniprocessor architecture. More... »

PAGES

137-146

References to SciGraph publications

  • 1982. Automatic construction of special purpose programs in 6TH CONFERENCE ON AUTOMATED DEDUCTION
  • Book

    TITLE

    System Modelling and Optimization

    ISBN

    978-1-4757-6671-4
    978-0-387-34897-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-0-387-34897-1_14

    DOI

    http://dx.doi.org/10.1007/978-0-387-34897-1_14

    DIMENSIONS

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


    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/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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Dept. of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100\u00a0Copenhagen \u00d8, Denmark"
              ], 
              "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": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Dept. of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100\u00a0Copenhagen \u00d8, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nakashige", 
            "givenName": "Ryo", 
            "id": "sg:person.013130736031.99", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013130736031.99"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "TU Wien", 
              "id": "https://www.grid.ac/institutes/grid.5329.d", 
              "name": [
                "Inst. f\u00fcr Computersprachen, Vienna University of Technology, Argentinierstr. 8, A-1040\u00a0Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Z\u00f6chling", 
            "givenName": "Robert", 
            "id": "sg:person.011127047767.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011127047767.55"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/202176.202184", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009460962"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0000060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009613871", 
              "https://doi.org/10.1007/bfb0000060"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/176454.176526", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038531823"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/2.62091", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061105865"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996", 
        "datePublishedReg": "1996-01-01", 
        "description": "Our goal is to incorporate state-of-the-art partial evaluation in a library of general-purpose algorithms \u2014 in particular, mathematical algorithms \u2014 in order to allow the automatic creation of efficient, special-purpose programs. The main goal is efficiency: a specialized program often runs significantly faster than its generic version. This paper shows how a binding-time analysis can be used to identify potential sources for specialization in mathematical algorithms. The method is surprisingly simple and effective. To demonstrate the effectiveness of this approach we used an automatic partial evaluator for Fortran that we developed. Results for five well-known algorithms show that some remarkable speedup factors can be obtained on a uniprocessor architecture.", 
        "editor": [
          {
            "familyName": "Dole\u017eal", 
            "givenName": "Jaroslav", 
            "type": "Person"
          }, 
          {
            "familyName": "Fidler", 
            "givenName": "Ji\u0159\u00ed", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-0-387-34897-1_14", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-1-4757-6671-4", 
            "978-0-387-34897-1"
          ], 
          "name": "System Modelling and Optimization", 
          "type": "Book"
        }, 
        "name": "Binding-time analysis applied to mathematical algorithms", 
        "pagination": "137-146", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-0-387-34897-1_14"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "2f0d566548509edce8a3a94fdbfe7a758358c8f3181d4460cc1ce342009d8505"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1009876868"
            ]
          }
        ], 
        "publisher": {
          "location": "Boston, MA", 
          "name": "Springer US", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-0-387-34897-1_14", 
          "https://app.dimensions.ai/details/publication/pub.1009876868"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T10:31", 
        "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_8659_00000249.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-0-387-34897-1_14"
      }
    ]
     

    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/978-0-387-34897-1_14'

    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/978-0-387-34897-1_14'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-0-387-34897-1_14'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-0-387-34897-1_14'


     

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

    100 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-0-387-34897-1_14 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author N2f9290db4f924fe695349565dfc42bc6
    4 schema:citation sg:pub.10.1007/bfb0000060
    5 https://doi.org/10.1109/2.62091
    6 https://doi.org/10.1145/176454.176526
    7 https://doi.org/10.1145/202176.202184
    8 schema:datePublished 1996
    9 schema:datePublishedReg 1996-01-01
    10 schema:description Our goal is to incorporate state-of-the-art partial evaluation in a library of general-purpose algorithms — in particular, mathematical algorithms — in order to allow the automatic creation of efficient, special-purpose programs. The main goal is efficiency: a specialized program often runs significantly faster than its generic version. This paper shows how a binding-time analysis can be used to identify potential sources for specialization in mathematical algorithms. The method is surprisingly simple and effective. To demonstrate the effectiveness of this approach we used an automatic partial evaluator for Fortran that we developed. Results for five well-known algorithms show that some remarkable speedup factors can be obtained on a uniprocessor architecture.
    11 schema:editor N1a34ee33986148cbb74183dbbc8d266f
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N937dccbbeb3b473c88b49b185d282ea7
    16 schema:name Binding-time analysis applied to mathematical algorithms
    17 schema:pagination 137-146
    18 schema:productId N0ab6fd6d2f204838865072e56b97e692
    19 N35cbc9d44e9648d0b564462d1d21163c
    20 Nd09131e291b14a92b61d170720a5e7bb
    21 schema:publisher Na62717a2168b47f991a49b6cb02f5483
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009876868
    23 https://doi.org/10.1007/978-0-387-34897-1_14
    24 schema:sdDatePublished 2019-04-15T10:31
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher N95986d8b436d48768483e21027ffb287
    27 schema:url http://link.springer.com/10.1007/978-0-387-34897-1_14
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N0ab6fd6d2f204838865072e56b97e692 schema:name dimensions_id
    32 schema:value pub.1009876868
    33 rdf:type schema:PropertyValue
    34 N1a34ee33986148cbb74183dbbc8d266f rdf:first Nc5cd0f3ad3234465b34b56fc40ce77e2
    35 rdf:rest N6f854806d18142a9a4208459c229c6d1
    36 N2f9290db4f924fe695349565dfc42bc6 rdf:first sg:person.010754010217.31
    37 rdf:rest N517163c19e384408bc9012df79043f67
    38 N35cbc9d44e9648d0b564462d1d21163c schema:name readcube_id
    39 schema:value 2f0d566548509edce8a3a94fdbfe7a758358c8f3181d4460cc1ce342009d8505
    40 rdf:type schema:PropertyValue
    41 N517163c19e384408bc9012df79043f67 rdf:first sg:person.013130736031.99
    42 rdf:rest Nab3b6770a43842b8926782959332c616
    43 N5d6bf49accc24ea1ba529b351a6300a6 schema:familyName Fidler
    44 schema:givenName Jiří
    45 rdf:type schema:Person
    46 N6f854806d18142a9a4208459c229c6d1 rdf:first N5d6bf49accc24ea1ba529b351a6300a6
    47 rdf:rest rdf:nil
    48 N937dccbbeb3b473c88b49b185d282ea7 schema:isbn 978-0-387-34897-1
    49 978-1-4757-6671-4
    50 schema:name System Modelling and Optimization
    51 rdf:type schema:Book
    52 N95986d8b436d48768483e21027ffb287 schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 Na62717a2168b47f991a49b6cb02f5483 schema:location Boston, MA
    55 schema:name Springer US
    56 rdf:type schema:Organisation
    57 Nab3b6770a43842b8926782959332c616 rdf:first sg:person.011127047767.55
    58 rdf:rest rdf:nil
    59 Nc5cd0f3ad3234465b34b56fc40ce77e2 schema:familyName Doležal
    60 schema:givenName Jaroslav
    61 rdf:type schema:Person
    62 Nd09131e291b14a92b61d170720a5e7bb schema:name doi
    63 schema:value 10.1007/978-0-387-34897-1_14
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Mathematical Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Applied Mathematics
    70 rdf:type schema:DefinedTerm
    71 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    72 schema:familyName Glück
    73 schema:givenName Robert
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    75 rdf:type schema:Person
    76 sg:person.011127047767.55 schema:affiliation https://www.grid.ac/institutes/grid.5329.d
    77 schema:familyName Zöchling
    78 schema:givenName Robert
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011127047767.55
    80 rdf:type schema:Person
    81 sg:person.013130736031.99 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    82 schema:familyName Nakashige
    83 schema:givenName Ryo
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013130736031.99
    85 rdf:type schema:Person
    86 sg:pub.10.1007/bfb0000060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009613871
    87 https://doi.org/10.1007/bfb0000060
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1109/2.62091 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061105865
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1145/176454.176526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038531823
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1145/202176.202184 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009460962
    94 rdf:type schema:CreativeWork
    95 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    96 schema:name DIKU, Dept. of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø, Denmark
    97 rdf:type schema:Organization
    98 https://www.grid.ac/institutes/grid.5329.d schema:alternateName TU Wien
    99 schema:name Inst. für Computersprachen, Vienna University of Technology, Argentinierstr. 8, A-1040 Vienna, Austria
    100 rdf:type schema:Organization
     




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


    ...