Serveur d'exploration sur Pittsburgh

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Bandit-Based Optimization on Graphs with Application to Library Performance Tuning

Identifieur interne : 000102 ( Hal/Curation ); précédent : 000101; suivant : 000103

Bandit-Based Optimization on Graphs with Application to Library Performance Tuning

Auteurs : Frédéric De Mesmay [États-Unis] ; Arpad Rimmel [France] ; Yevgen Voronenko [États-Unis] ; Markus Püschel [États-Unis]

Source :

RBID : Hal:inria-00379523

Abstract

The problem of choosing fast implementations for a class of recursive algorithms such as the fast Fourier transforms can be formulated as an optimization problem over the language generated by a suitably defined grammar. We propose a novel algorithm that solves this problem by reducing it to maximizing an objective function over the sinks of a directed acyclic graph. This algorithm valuates nodes using Monte-Carlo and grows a subgraph in the most promising directions by considering local maximum k-armed bandits. When used inside an adaptive linear transform library, it cuts down the search time by an order of magnitude compared to the existing algorithm. In some cases, the performance of the implementations found is also increased by up to 10% which is of considerable practical importance since it consequently improves the performance of all applications using the library.

Url:

Links toward previous steps (curation, corpus...)


Links to Exploration step

Hal:inria-00379523

Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Bandit-Based Optimization on Graphs with Application to Library Performance Tuning</title>
<author>
<name sortKey="De Mesmay, Frederic" sort="De Mesmay, Frederic" uniqKey="De Mesmay F" first="Frédéric" last="De Mesmay">Frédéric De Mesmay</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author>
<name sortKey="Rimmel, Arpad" sort="Rimmel, Arpad" uniqKey="Rimmel A" first="Arpad" last="Rimmel">Arpad Rimmel</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID">
<idno type="RNSR">199812948M</idno>
<orgName>Laboratoire de Recherche en Informatique</orgName>
<orgName type="acronym">LRI</orgName>
<desc>
<address>
<addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lri.fr/</ref>
</desc>
<listRelation>
<relation active="#struct-92966" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-411575" type="direct"></relation>
<relation name="UMR8623" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-92966" type="direct">
<org type="institution" xml:id="struct-92966" status="VALID">
<orgName>Université Paris-Sud - Paris 11</orgName>
<orgName type="acronym">UP11</orgName>
<desc>
<address>
<addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.u-psud.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-411575" type="direct">
<org type="institution" xml:id="struct-411575" status="VALID">
<orgName>CentraleSupélec</orgName>
<desc>
<address>
<addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8623" active="#struct-441569" type="direct">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Voronenko, Yevgen" sort="Voronenko, Yevgen" uniqKey="Voronenko Y" first="Yevgen" last="Voronenko">Yevgen Voronenko</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author>
<name sortKey="Puschel, Markus" sort="Puschel, Markus" uniqKey="Puschel M" first="Markus" last="Püschel">Markus Püschel</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00379523</idno>
<idno type="halId">inria-00379523</idno>
<idno type="halUri">https://hal.inria.fr/inria-00379523</idno>
<idno type="url">https://hal.inria.fr/inria-00379523</idno>
<date when="2009-06">2009-06</date>
<idno type="wicri:Area/Hal/Corpus">000102</idno>
<idno type="wicri:Area/Hal/Curation">000102</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en">Bandit-Based Optimization on Graphs with Application to Library Performance Tuning</title>
<author>
<name sortKey="De Mesmay, Frederic" sort="De Mesmay, Frederic" uniqKey="De Mesmay F" first="Frédéric" last="De Mesmay">Frédéric De Mesmay</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author>
<name sortKey="Rimmel, Arpad" sort="Rimmel, Arpad" uniqKey="Rimmel A" first="Arpad" last="Rimmel">Arpad Rimmel</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID">
<idno type="RNSR">199812948M</idno>
<orgName>Laboratoire de Recherche en Informatique</orgName>
<orgName type="acronym">LRI</orgName>
<desc>
<address>
<addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lri.fr/</ref>
</desc>
<listRelation>
<relation active="#struct-92966" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-411575" type="direct"></relation>
<relation name="UMR8623" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-92966" type="direct">
<org type="institution" xml:id="struct-92966" status="VALID">
<orgName>Université Paris-Sud - Paris 11</orgName>
<orgName type="acronym">UP11</orgName>
<desc>
<address>
<addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.u-psud.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-411575" type="direct">
<org type="institution" xml:id="struct-411575" status="VALID">
<orgName>CentraleSupélec</orgName>
<desc>
<address>
<addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8623" active="#struct-441569" type="direct">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Voronenko, Yevgen" sort="Voronenko, Yevgen" uniqKey="Voronenko Y" first="Yevgen" last="Voronenko">Yevgen Voronenko</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author>
<name sortKey="Puschel, Markus" sort="Puschel, Markus" uniqKey="Puschel M" first="Markus" last="Püschel">Markus Püschel</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-15735" status="VALID">
<orgName>Department of Electrical and Computer Engineering - Carnegie Mellon University</orgName>
<desc>
<address>
<addrLine>Pittsburgh, Pennsylvania 15213-3890</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.ece.cmu.edu/</ref>
</desc>
<listRelation>
<relation active="#struct-67135" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-67135" type="direct">
<org type="institution" xml:id="struct-67135" status="VALID">
<orgName>Carnegie Mellon University [Pittsburgh]</orgName>
<orgName type="acronym">CMU</orgName>
<desc>
<address>
<addrLine>5000 Forbes Ave, Pittsburgh, PA 15213</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cmu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc>
<textClass></textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">The problem of choosing fast implementations for a class of recursive algorithms such as the fast Fourier transforms can be formulated as an optimization problem over the language generated by a suitably defined grammar. We propose a novel algorithm that solves this problem by reducing it to maximizing an objective function over the sinks of a directed acyclic graph. This algorithm valuates nodes using Monte-Carlo and grows a subgraph in the most promising directions by considering local maximum k-armed bandits. When used inside an adaptive linear transform library, it cuts down the search time by an order of magnitude compared to the existing algorithm. In some cases, the performance of the implementations found is also increased by up to 10% which is of considerable practical importance since it consequently improves the performance of all applications using the library.</div>
</front>
</TEI>
<hal api="V3">
<titleStmt>
<title xml:lang="en">Bandit-Based Optimization on Graphs with Application to Library Performance Tuning</title>
<author role="aut">
<persName>
<forename type="first">Frédéric</forename>
<surname>De Mesmay</surname>
</persName>
<idno type="halauthorid">400635</idno>
<orgName ref="#struct-67135"></orgName>
<affiliation ref="#struct-15735"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Arpad</forename>
<surname>Rimmel</surname>
</persName>
<email type="md5">f816e5743d6d73670416045dcfebb116</email>
<email type="domain">lri.fr</email>
<idno type="halauthorid">400636</idno>
<affiliation ref="#struct-2544"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Yevgen</forename>
<surname>Voronenko</surname>
</persName>
<idno type="halauthorid">400637</idno>
<orgName ref="#struct-67135"></orgName>
<affiliation ref="#struct-15735"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Markus</forename>
<surname>Püschel</surname>
</persName>
<email type="md5">cb580d015109a59f4e6280d92c019d28</email>
<email type="domain">ece.cmu.edu</email>
<idno type="halauthorid">391984</idno>
<affiliation ref="#struct-15735"></affiliation>
</author>
<editor role="depositor">
<persName>
<forename>Arpad</forename>
<surname>Rimmel</surname>
</persName>
<email type="md5">e682007e97ebc320e25ce8f5e4b634be</email>
<email type="domain">lri.fr</email>
</editor>
</titleStmt>
<editionStmt>
<edition n="v1" type="current">
<date type="whenSubmitted">2009-04-28 20:20:37</date>
<date type="whenModified">2017-02-09 15:55:00</date>
<date type="whenReleased">2009-04-28 20:57:08</date>
<date type="whenProduced">2009-06</date>
<date type="whenEndEmbargoed">2009-04-28</date>
<ref type="file" target="https://hal.inria.fr/inria-00379523/document">
<date notBefore="2009-04-28"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.inria.fr/inria-00379523/file/icmlspiral.pdf">
<date notBefore="2009-04-28"></date>
</ref>
</edition>
<respStmt>
<resp>contributor</resp>
<name key="140507">
<persName>
<forename>Arpad</forename>
<surname>Rimmel</surname>
</persName>
<email type="md5">e682007e97ebc320e25ce8f5e4b634be</email>
<email type="domain">lri.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt>
<distributor>CCSD</distributor>
<idno type="halId">inria-00379523</idno>
<idno type="halUri">https://hal.inria.fr/inria-00379523</idno>
<idno type="halBibtex">demesmay:inria-00379523</idno>
<idno type="halRefHtml">ICML, Jun 2009, Montréal, Canada. 2009</idno>
<idno type="halRef">ICML, Jun 2009, Montréal, Canada. 2009</idno>
</publicationStmt>
<seriesStmt>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="UNIV-PSUD">Université Paris Sud - Paris XI</idno>
<idno type="stamp" n="UMR8623">Laboratoire de Recherche en Informatique</idno>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CENTRALESUPELEC">Ecole CentraleSupélec</idno>
</seriesStmt>
<notesStmt>
<note type="audience" n="2">International</note>
<note type="invited" n="0">No</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
<note type="proceedings" n="1">Yes</note>
</notesStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en">Bandit-Based Optimization on Graphs with Application to Library Performance Tuning</title>
<author role="aut">
<persName>
<forename type="first">Frédéric</forename>
<surname>De Mesmay</surname>
</persName>
<idno type="halauthorid">400635</idno>
<orgName ref="#struct-67135"></orgName>
<affiliation ref="#struct-15735"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Arpad</forename>
<surname>Rimmel</surname>
</persName>
<email type="md5">f816e5743d6d73670416045dcfebb116</email>
<email type="domain">lri.fr</email>
<idno type="halauthorid">400636</idno>
<affiliation ref="#struct-2544"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Yevgen</forename>
<surname>Voronenko</surname>
</persName>
<idno type="halauthorid">400637</idno>
<orgName ref="#struct-67135"></orgName>
<affiliation ref="#struct-15735"></affiliation>
</author>
<author role="aut">
<persName>
<forename type="first">Markus</forename>
<surname>Püschel</surname>
</persName>
<email type="md5">cb580d015109a59f4e6280d92c019d28</email>
<email type="domain">ece.cmu.edu</email>
<idno type="halauthorid">391984</idno>
<affiliation ref="#struct-15735"></affiliation>
</author>
</analytic>
<monogr>
<meeting>
<title>ICML</title>
<date type="start">2009-06</date>
<settlement>Montréal</settlement>
<country key="CA">Canada</country>
</meeting>
<imprint>
<date type="datePub">2009</date>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc>
<langUsage>
<language ident="en">English</language>
</langUsage>
<textClass>
<classCode scheme="halDomain" n="info.info-ai">Computer Science [cs]/Artificial Intelligence [cs.AI]</classCode>
<classCode scheme="halTypology" n="COMM">Conference papers</classCode>
</textClass>
<abstract xml:lang="en">The problem of choosing fast implementations for a class of recursive algorithms such as the fast Fourier transforms can be formulated as an optimization problem over the language generated by a suitably defined grammar. We propose a novel algorithm that solves this problem by reducing it to maximizing an objective function over the sinks of a directed acyclic graph. This algorithm valuates nodes using Monte-Carlo and grows a subgraph in the most promising directions by considering local maximum k-armed bandits. When used inside an adaptive linear transform library, it cuts down the search time by an order of magnitude compared to the existing algorithm. In some cases, the performance of the implementations found is also increased by up to 10% which is of considerable practical importance since it consequently improves the performance of all applications using the library.</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Hal/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000102 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 000102 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Hal
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:inria-00379523
   |texte=   Bandit-Based Optimization on Graphs with Application to Library Performance Tuning
}}

Wicri

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021