Bandit-Based Optimization on Graphs with Application to Library Performance Tuning
Identifieur interne : 000102 ( Hal/Curation ); précédent : 000101; suivant : 000103Bandit-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 :
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...)
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000102
Links to Exploration step
Hal:inria-00379523Le 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 }}
![]() | This area was generated with Dilib version V0.6.38. | ![]() |