PittsburghV1, Main, Merge, bibRecord, 00AD52

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

Identifieur interne : 00AD52 ( Main/Merge ); précédent : 00AD51; suivant : 00AD53

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:

https://hal.inria.fr/inria-00379523

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

to stream Hal, to step Corpus: 000102
to stream Hal, to step Curation: 000102
to stream Hal, to step Checkpoint: 000512

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>
<idno type="wicri:Area/Hal/Checkpoint">000512</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000512</idno>
<idno type="wicri:Area/Main/Merge">00AD52</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>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00AD52 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00AD52 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Main
   |étape=   Merge
   |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.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	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.

Serveur d'exploration sur Pittsburgh

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

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

Source :

Abstract

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

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

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