UnivTrevesV1, PascalFrancis, Corpus, bibRecord, 001422

Scheduling expression DAGs for minimal register need

Identifieur interne : 001422 ( PascalFrancis/Corpus ); précédent : 001421; suivant : 001423

Scheduling expression DAGs for minimal register need

Auteurs : C. W. Kessler

Source :

Lecture notes in computer science [ 0302-9743 ] ; 1996.

RBID : Pascal:97-0022170

Descripteurs français

Pascal (Inist)
- Ordonnancement, Optimisation, Problème NP complet, Complexité algorithme, Programmation dynamique, Programme application, Algorithme optimal, Algorithme rapide.

English descriptors

KwdEn :
- Algorithm complexity, Application program, Dynamic programming, Fast algorithm, NP complete problem, Optimal algorithm, Optimization, Scheduling.

Abstract

Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2²ⁿ) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0302-9743`
A05				`@2 1140`
A08	`01`	`1`	`ENG`	`@1 Scheduling expression DAGs for minimal register need`
A09	`01`	`1`	`ENG`	`@1 PLILP '96 : programming languages : implementations, logics, and programs : Aachen, September 24-27, 1996`
A11	`01`	`1`		`@1 KESSLER (C. W.)`
A12	`01`	`1`		`@1 KUCHEN (Herbert) @9 ed.`
A12	`02`	`1`		`@1 SWIERSTRA (S. Doaitse) @9 ed.`
A14	`01`			`@1 Universität Trier, FB 4 - Informatik @2 54286 Trier @3 DEU @Z 1 aut.`
A20				`@1 228-242`
A21				`@1 1996`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16343 @5 354000063989040160`
A44				`@0 0000 @1 © 1997 INIST-CNRS. All rights reserved.`
A45				`@0 31 ref.`
A47	`01`	`1`		`@0 97-0022170`
A60				`@1 P @2 C`
A61				`@0 A`
A64	`01`	`1`		`@0 Lecture notes in computer science`
A66	`01`			`@0 DEU`
A66	`02`			`@0 USA`
C01	`01`		`ENG`	@0 Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2²ⁿ) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.
C02	`01`	`X`		`@0 001D02A05`
C02	`02`	`X`		`@0 001D02B04`
C03	`01`	`X`	`FRE`	`@0 Ordonnancement @5 01`
C03	`01`	`X`	`ENG`	`@0 Scheduling @5 01`
C03	`01`	`X`	`GER`	`@0 Netzplantechnik @5 01`
C03	`01`	`X`	`SPA`	`@0 Ordonamiento @5 01`
C03	`02`	`X`	`FRE`	`@0 Optimisation @5 02`
C03	`02`	`X`	`ENG`	`@0 Optimization @5 02`
C03	`02`	`X`	`GER`	`@0 Optimierung @5 02`
C03	`02`	`X`	`SPA`	`@0 Optimización @5 02`
C03	`03`	`X`	`FRE`	`@0 Problème NP complet @5 03`
C03	`03`	`X`	`ENG`	`@0 NP complete problem @5 03`
C03	`03`	`X`	`SPA`	`@0 Problema NP completo @5 03`
C03	`04`	`X`	`FRE`	`@0 Complexité algorithme @5 04`
C03	`04`	`X`	`ENG`	`@0 Algorithm complexity @5 04`
C03	`04`	`X`	`SPA`	`@0 Complejidad algoritmo @5 04`
C03	`05`	`X`	`FRE`	`@0 Programmation dynamique @5 05`
C03	`05`	`X`	`ENG`	`@0 Dynamic programming @5 05`
C03	`05`	`X`	`SPA`	`@0 Programación dinámica @5 05`
C03	`06`	`X`	`FRE`	`@0 Programme application @5 06`
C03	`06`	`X`	`ENG`	`@0 Application program @5 06`
C03	`06`	`X`	`SPA`	`@0 Programa aplicación @5 06`
C03	`07`	`X`	`FRE`	`@0 Algorithme optimal @5 07`
C03	`07`	`X`	`ENG`	`@0 Optimal algorithm @5 07`
C03	`07`	`X`	`SPA`	`@0 Algoritmo óptimo @5 07`
C03	`08`	`X`	`FRE`	`@0 Algorithme rapide @5 08`
C03	`08`	`X`	`ENG`	`@0 Fast algorithm @5 08`
C03	`08`	`X`	`SPA`	`@0 Algoritmo rápido @5 08`
N21				`@1 006`

A30	`01`	`1`	`ENG`	`@1 Programming languages : implementations, logics, and programs. International symposium @2 8 @3 Aachen DEU @4 1996-09-24`

Format Inist (serveur)

NO :	PASCAL 97-0022170 INIST
ET :	Scheduling expression DAGs for minimal register need
AU :	KESSLER (C. W.); KUCHEN (Herbert); SWIERSTRA (S. Doaitse)
AF :	Universität Trier, FB 4 - Informatik/54286 Trier/Allemagne (1 aut.)
DT :	Publication en série; Congrès; Niveau analytique
SO :	Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1996; Vol. 1140; Pp. 228-242; Bibl. 31 ref.
LA :	Anglais
EA :	Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2²ⁿ) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.
CC :	001D02A05; 001D02B04
FD :	Ordonnancement; Optimisation; Problème NP complet; Complexité algorithme; Programmation dynamique; Programme application; Algorithme optimal; Algorithme rapide
ED :	Scheduling; Optimization; NP complete problem; Algorithm complexity; Dynamic programming; Application program; Optimal algorithm; Fast algorithm
GD :	Netzplantechnik; Optimierung
SD :	Ordonamiento; Optimización; Problema NP completo; Complejidad algoritmo; Programación dinámica; Programa aplicación; Algoritmo óptimo; Algoritmo rápido
LO :	INIST-16343.354000063989040160
ID :	97-0022170

Links to Exploration step

Pascal:97-0022170

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Scheduling expression DAGs for minimal register need</title>
<author><name sortKey="Kessler, C W" sort="Kessler, C W" uniqKey="Kessler C" first="C. W." last="Kessler">C. W. Kessler</name>
<affiliation><inist:fA14 i1="01"><s1>Universität Trier, FB 4 - Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">97-0022170</idno>
<date when="1996">1996</date>
<idno type="stanalyst">PASCAL 97-0022170 INIST</idno>
<idno type="RBID">Pascal:97-0022170</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">001422</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Scheduling expression DAGs for minimal register need</title>
<author><name sortKey="Kessler, C W" sort="Kessler, C W" uniqKey="Kessler C" first="C. W." last="Kessler">C. W. Kessler</name>
<affiliation><inist:fA14 i1="01"><s1>Universität Trier, FB 4 - Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="1996">1996</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>Algorithm complexity</term>
<term>Application program</term>
<term>Dynamic programming</term>
<term>Fast algorithm</term>
<term>NP complete problem</term>
<term>Optimal algorithm</term>
<term>Optimization</term>
<term>Scheduling</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Ordonnancement</term>
<term>Optimisation</term>
<term>Problème NP complet</term>
<term>Complexité algorithme</term>
<term>Programmation dynamique</term>
<term>Programme application</term>
<term>Algorithme optimal</term>
<term>Algorithme rapide</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2<sup>2n</sup>
) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>1140</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>Scheduling expression DAGs for minimal register need</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>PLILP '96 : programming languages : implementations, logics, and programs : Aachen, September 24-27, 1996</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>KESSLER (C. W.)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>KUCHEN (Herbert)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1"><s1>SWIERSTRA (S. Doaitse)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>Universität Trier, FB 4 - Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA20><s1>228-242</s1>
</fA20>
<fA21><s1>1996</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000063989040160</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 1997 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>31 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>97-0022170</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fA66 i1="02"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2<sup>2n</sup>
) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02B04</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Ordonnancement</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Scheduling</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="GER"><s0>Netzplantechnik</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Ordonamiento</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Optimisation</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Optimization</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="GER"><s0>Optimierung</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Optimización</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Problème NP complet</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>NP complete problem</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Problema NP completo</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Complexité algorithme</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Algorithm complexity</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Complejidad algoritmo</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Programmation dynamique</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Dynamic programming</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Programación dinámica</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Programme application</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Application program</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Programa aplicación</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Algorithme optimal</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Optimal algorithm</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Algoritmo óptimo</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Algorithme rapide</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Fast algorithm</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA"><s0>Algoritmo rápido</s0>
<s5>08</s5>
</fC03>
<fN21><s1>006</s1>
</fN21>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>Programming languages : implementations, logics, and programs. International symposium</s1>
<s2>8</s2>
<s3>Aachen DEU</s3>
<s4>1996-09-24</s4>
</fA30>
</pR>
</standard>
<server><NO>PASCAL 97-0022170 INIST</NO>
<ET>Scheduling expression DAGs for minimal register need</ET>
<AU>KESSLER (C. W.); KUCHEN (Herbert); SWIERSTRA (S. Doaitse)</AU>
<AF>Universität Trier, FB 4 - Informatik/54286 Trier/Allemagne (1 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1996; Vol. 1140; Pp. 228-242; Bibl. 31 ref.</SO>
<LA>Anglais</LA>
<EA>Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n !) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2<sup>2n</sup>
) and very good average behaviour. Applying a dynamic programming scheme and reordering techniques, it is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.</EA>
<CC>001D02A05; 001D02B04</CC>
<FD>Ordonnancement; Optimisation; Problème NP complet; Complexité algorithme; Programmation dynamique; Programme application; Algorithme optimal; Algorithme rapide</FD>
<ED>Scheduling; Optimization; NP complete problem; Algorithm complexity; Dynamic programming; Application program; Optimal algorithm; Fast algorithm</ED>
<GD>Netzplantechnik; Optimierung</GD>
<SD>Ordonamiento; Optimización; Problema NP completo; Complejidad algoritmo; Programación dinámica; Programa aplicación; Algoritmo óptimo; Algoritmo rápido</SD>
<LO>INIST-16343.354000063989040160</LO>
<ID>97-0022170</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Corpus

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

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 001422 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:97-0022170
   |texte=   Scheduling expression DAGs for minimal register need
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	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 l'Université de Trèves

Scheduling expression DAGs for minimal register need

Scheduling expression DAGs for minimal register need

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

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