Algorithme de minimisation de variable.

La question :

Salut.

j'ai 275 équations (qui ne sont que des additions, mais bon a aurait pu
être autre chose), lesquels sont dépendantes les unes des autres

voila une portion du tableau

R066=R209+R210
R007=R030+R033
R008=R029+R036
R011=R028+R043
R012=R050+R053
R013=R039+R054
R015=R037+R057
R016=R048+R056
R019=R046+R059
R020=R041+R060
R023=R038+R064
R024=R044+R063
R026=R027+R066
R001=R008+R011
R002=R016+R019
R003=R015+R020
R004=R013+R023
R005=R012+R024
R006=R007+R026
R000=R001+R006

On voit que la dernière ligne R000=R001+R006 dépend d'autres additions
faites précédemment.

J'aimerai trouver l'algorithme que va utiliser un nombre minimum de
variable temporaire (Vxxx)

L'idée est de remplacer les Rxxx par une nouvelle numérotation en
utilisant un minimum d'indice.

Pour cela on considère que si l'équation n'est plus utilisée par la
suite, on peut recycler son ID
Exemple:
R066 est utilisée pour le calcul de R026 donc R066 devient V0=R209+R210
R077 est utilisée pour le calcul de R006 donc R077 devient V1=R030+R033
R008 est utilisée pour le calcul de R001 donc R008 devient V2=R029+R036
R011 est utilisée pour le calcul de R001 donc R011 devient V3=R028+R043
R012 est utilisée pour le calcul de R005 donc R012 devient V4=R050+R053
R013 est utilisée pour le calcul de R004 donc R013 devient V5=R039+R054
R016 ... V6
R019 ... V7
R020 ... V8
R023 ... V9
R024 ... V10
R026 est utilisée pour le calcul de R006 mais !!! R066 ne sera plus
utilisé donc nous pouvons recycler V0 et donc R026 devient V0=R027+V0

R001 est utilisée pour le calcul de R000 mais !!! R008 et R011 ne seront
plus utilisé donc nous pouvons recycler V2 et V3 et donc R001 devient
V2=V2+V3

En laissant V3 libre d'être utilisé par la suite.
....

Alors là ou ça se complique, c'est qu'on peut évidement réordonner les
équations tant qu'on respecte l'ordre des dépendances.

Ce qu'il faut c'est utiliser le minimum de variable temporaire.

Alors je suis sur l'affaire depuis une semaine, mais j'ai un peu de mal.
C'est surtout le réordonnancement qui me pose problème.

Merci.
Etienne

Poser votre question sur le forum Programmation

Les 7 réponses :

Etienne a écrit :


Alors je suis sur l'affaire depuis une semaine, mais j'ai un peu de
mal. C'est surtout le réordonnancement qui me pose problème.


Il faut appliquer les algorithmes d'analyse de flot de donnée (data flow
analysis), et d'allocation de registres (register allocation).


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Le 15/11/2010 16:32, Pascal J. Bourguignon a écrit :


Etiennea écrit :



Il faut appliquer les algorithmes d'analyse de flot de donnée (data flow
analysis), et d'allocation de registres (register allocation).


Ca semble pas mal ca, vu qu'effectivement, l'idée est de limiter les
accès mémoire en utilisant des registres...

Je vais voir ce que je trouve.

Merci.
Etienne

Le 15/11/2010 16:32, Pascal J. Bourguignon a écrit :


Il faut appliquer les algorithmes d'analyse de flot de donnée (data flow
analysis), et d'allocation de registres (register allocation).


Bon j'ai pas mal regardé (surtout la partie flux de données) Mais si je
trouve pas mal d'explications sur ce qu'est l'analyse des flux de
données, il est plus difficile de trouver un exemple concret de
l'utilisation de celui-ci.

J'ai reformulé mon besoin, et envisager une piste (qui ne mènera peut
etre pas bien loin).

Soit le code suivant.
0: a=10
1: b=9
2: k=71
3: n=k*2+a
4: c=2*b
5: d=c+b
6: d=d+k
7: f=d*2*b
8: a=d*a

on souhaite réordonner ces instructions afin de limiter le nombre de
variable utilisée en même temps (c'est à dire entre l'initialisation et
la dernière utilisation).

On remarque que:
- Les instructions 0, 3, et 8 peuvent être regroupée
- Les instruction 1 et 4 devrait être rapprochée pour bloquer un
registre pdt 2 instructions de moins
- L'instruction 7 peut être réaliser avant ou apres le bloc 0, 3, 8.

j'ai crée un graphe de dépendance pour indiquer quelles instructions
sont dépendantes les unes des autres.

0 1 2 3 4 5 6 7 8
0 - - - - - - - - -
1 - - - - - - - - -
2 - - - - - - - - -
3 1 - 1 - - - - - -
4 - 1 - - - - - - -
5 - 1 - - 1 - - - -
6 - - 1 - - 1 - - -
7 - - 1 - - - 1 - -
8 1 - - - - - 1 - -

Le code que je cherche à obtenir est sans doute:

1: b=9 b
4: c=2*b b,c
5: d=c+b b,c,d c n'est plus utilisée
2: k=71 b,d,k
6: d=d+k b,d,k
7: f=d*2*b b,d,f,k b et f ne sont plus utilisées
0: a=10 a,d,k
3: n=k*2+a a,d,k,n n et k ne sont plus utilisées
8: a=d*a a,d a et d ne sont plus utilisées

bon ben voila.
Il n'y a plus qu'a trouver comment passer de ma matrice à cet ordre (ou
un autre équivalent)...

Etienne

WebShaker a écrit :


Le 15/11/2010 16:32, Pascal J. Bourguignon a écrit :


Il faut appliquer les algorithmes d'analyse de flot de donnée (data flow
analysis), et d'allocation de registres (register allocation).


Bon j'ai pas mal regardé (surtout la partie flux de données) Mais si
je trouve pas mal d'explications sur ce qu'est l'analyse des flux de
données, il est plus difficile de trouver un exemple concret de
l'utilisation de celui-ci.

J'ai reformulé mon besoin, et envisager une piste (qui ne mènera peut
etre pas bien loin).

Soit le code suivant.
0: a=10
1: b=9
2: k=71
3: n=k*2+a
4: c=2*b
5: d=c+b
6: d=d+k
7: f=d*2*b
8: a=d*a

on souhaite réordonner ces instructions afin de limiter le nombre de
variable utilisée en même temps (c'est à dire entre l'initialisation
et la dernière utilisation).

On remarque que:
- Les instructions 0, 3, et 8 peuvent être regroupée
- Les instruction 1 et 4 devrait être rapprochée pour bloquer un
registre pdt 2 instructions de moins
- L'instruction 7 peut être réaliser avant ou apres le bloc 0, 3, 8.

j'ai crée un graphe de dépendance pour indiquer quelles instructions
sont dépendantes les unes des autres.

0 1 2 3 4 5 6 7 8
0 - - - - - - - - -
1 - - - - - - - - -
2 - - - - - - - - -
3 1 - 1 - - - - - -
4 - 1 - - - - - - -
5 - 1 - - 1 - - - -
6 - - 1 - - 1 - - -
7 - - 1 - - - 1 - -
8 1 - - - - - 1 - -

Le code que je cherche à obtenir est sans doute:

1: b=9 b
4: c=2*b b,c
5: d=c+b b,c,d c n'est plus utilisée
2: k=71 b,d,k
6: d=d+k b,d,k
7: f=d*2*b b,d,f,k b et f ne sont plus utilisées
0: a=10 a,d,k
3: n=k*2+a a,d,k,n n et k ne sont plus utilisées
8: a=d*a a,d a et d ne sont plus utilisées

bon ben voila.
Il n'y a plus qu'a trouver comment passer de ma matrice à cet ordre
(ou un autre équivalent)...


C'est expliqué dans les algorithmes sur l'allocation des registres. Par
exemple, tu as là un graphe. À partir de ce graphe, on peut calculer un
graphe d'interférence (où chaque noeud représente une variable, mais
chaque arc représente le fait que deux variables sont vivantes en même
temps. Alors allouer les régistres est équivalent à colorer ce graphe
d'interférence (chaque couleur représentant un régistre).

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Le 16/11/2010 00:07, Pascal J. Bourguignon a écrit :


C'est expliqué dans les algorithmes sur l'allocation des registres. Par
exemple, tu as là un graphe. À partir de ce graphe, on peut calculer un
graphe d'interférence (où chaque noeud représente une variable, mais
chaque arc représente le fait que deux variables sont vivantes en même
temps. Alors allouer les régistres est équivalent à colorer ce graphe
d'interférence (chaque couleur représentant un régistre).


Pour être honnête, j'ai bien regardé (ce que j'ai trouvé) sur les
algorithme d'allocation de registres.
Je suis resté un peu sur ma faim.
La plupart (tous en fait) des algo ou thèses que j'ai trouvé, font
l'impasse sur le ré ordonnancement des instructions.
Hors d'après moi c'est tout de même le plus important. Et surtout ca
doit arriver en amont de l'allocation de registres.

Bon je vais continuer a chercher ou tenter un algo maison...
Apres tout faut bien faire des essais pour avoir une chance de trouver
une méthode encore inconnue et repousser les frontières de l'impossible
(les fans de star trek comprendrons )

Etienne

Ps: si tu es des piste pour le réordonnancent, je suis preneur.

Poser votre question sur le forum Programmation

Questions similaires :

Algorithme rapide de permutation

ast écrivit : Tout dépend des outils utilisés ! Nous ne sommes pas ici dans le cadre de l'étude d'une rapidité de convergence vers une solution, à laquelle on peut mathématiquement répondre, mais d'une recherche de la performance. Tous les algos de tri, Bubble sort, Quicksort,...

algorithme de la fonction pow

[Copie et suivi vers fr.comp.algorithmes] Le 13/09/2011 10:24, Etienne a écrit dans fr.sci.maths : Dans quelle implémentation sur quelle machine ? Sans cette précision, je ne vois pas bien qui pourrait deviner de quel algorithme il s'agit exactement ! À tout hasard, un algorithme est exposé ici...

algorithme itératif de calcul de distance

Salut. l'algorithme de Bresenham http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d'arc_de_cercle_de_Bresenham permet de tracer un cercle en utilisant des opération simple. existe t-il un algorithme pour remplir le disque avec la valeur de la distance des points par rapport à leur centre...

Algo pour générer tous les couples, triplets, ... n-uplet d'une liste, n étant une variable

Bonjour, Je dispose d'une liste de nombre stockés dans un tableau Tab[1000]. Comment faire pour générer tous les couples possibles, triplets, ... n-uplet, n étant une variable ? (L'ordre des éléments dans le couple, triplet ... est sans importance) Générer tous les couples: for (i=0; i<999; i++)...

Algorithme de simulation

Bonjour , Je suis à la recherche d'un algorithme de simulation discrete informatique et l'algorithme ou le code source colonie de fourmie j'ai fais boucoup de recherche mais j'ai pas trouvé l'algorithme .Please Bonne année et Merci . All the best .