A new approximation algorithm for the register allocation problem
Identifieur interne : 002A69 ( Main/Merge ); précédent : 002A68; suivant : 002A70A new approximation algorithm for the register allocation problem
Auteurs : K. Jansen [Allemagne] ; J. Reiter [Allemagne]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 1997.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
In this paper we study the problem of register allocation in the presence of parallel conditional branches with a given branching depth d. We start from a scheduled flow graph and the goal is to find an assignment of the variables in the flow graph to a minimum number of registers. This problem can be solved by coloring the corresponding conflict graph G = (V, E). We describe a new approximation algorithm with constant worst case rate for flow graphs with constant branching depth. The algorithm works in two steps. In the first step, the lifetimes are enlarged such that the lifetimes form one unique interval across the different possible execution paths for each variable. We prove that the conflict graph G with enlarged lifetimes satisfies ω(G) ≤ (2d +1)ω(G) where ω(G) is the cardinality of a maximum clique in G. In the second step, we propose an algorithm with approximation bound (d +1)X(G) for G, using its specific structure.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 001368
- to stream PascalFrancis, to step Curation: 001624
- to stream PascalFrancis, to step Checkpoint: 001087
Links to Exploration step
Pascal:97-0443246Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A new approximation algorithm for the register allocation problem</title><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Fachbereich IV, Mathematik, Universität Trier</s1><s2>54 286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54 286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54 286 Trier</wicri:noRegion></affiliation></author><author><name sortKey="Reiter, J" sort="Reiter, J" uniqKey="Reiter J" first="J." last="Reiter">J. Reiter</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Fachbereich IV, Wirtschaftsinformatik, Universität Trier</s1><s2>54 286 Trier</s2><s3>DEU</s3><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54 286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54 286 Trier</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">97-0443246</idno><date when="1997">1997</date><idno type="stanalyst">PASCAL 97-0443246 INIST</idno><idno type="RBID">Pascal:97-0443246</idno><idno type="wicri:Area/PascalFrancis/Corpus">001368</idno><idno type="wicri:Area/PascalFrancis/Curation">001624</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">001087</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">001087</idno><idno type="wicri:doubleKey">0302-9743:1997:Jansen K:a:new:approximation</idno><idno type="wicri:Area/Main/Merge">002A69</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A new approximation algorithm for the register allocation problem</title><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Fachbereich IV, Mathematik, Universität Trier</s1><s2>54 286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54 286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54 286 Trier</wicri:noRegion></affiliation></author><author><name sortKey="Reiter, J" sort="Reiter, J" uniqKey="Reiter J" first="J." last="Reiter">J. Reiter</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Fachbereich IV, Wirtschaftsinformatik, Universität Trier</s1><s2>54 286 Trier</s2><s3>DEU</s3><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54 286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54 286 Trier</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="1997">1997</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Acyclic graph</term><term>Chromatic graph</term><term>Computer theory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Graphe acyclique</term><term>Graphe chromatique</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper we study the problem of register allocation in the presence of parallel conditional branches with a given branching depth d. We start from a scheduled flow graph and the goal is to find an assignment of the variables in the flow graph to a minimum number of registers. This problem can be solved by coloring the corresponding conflict graph G = (V, E). We describe a new approximation algorithm with constant worst case rate for flow graphs with constant branching depth. The algorithm works in two steps. In the first step, the lifetimes are enlarged such that the lifetimes form one unique interval across the different possible execution paths for each variable. We prove that the conflict graph G with enlarged lifetimes satisfies ω(G) ≤ (2d +1)ω(G) where ω(G) is the cardinality of a maximum clique in G. In the second step, we propose an algorithm with approximation bound (d +1)X(G) for G, using its specific structure.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name></noRegion><name sortKey="Reiter, J" sort="Reiter, J" uniqKey="Reiter J" first="J." last="Reiter">J. Reiter</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002A69 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002A69 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:97-0443246
|texte= A new approximation algorithm for the register allocation problem
}}
| This area was generated with Dilib version V0.6.31. |  |