2.3 Complexité algorithmique du problème:
Soit Mi le nombre d`instances du composant i requis pour
concevoir le système. Pour un type de composant donné, Il y'a
alors trois cas possibles:
- il y'a autant d'instances de ce composant dans ce
système que dans la bibliothèque (Mi = Ni)
- le nombre d'instances de ce composant dans le système
est inférieur au
nombre d'instances de ce même composant dans la
bibliothèque (Mi < Ni)
- le nombre d'instances de ce composant dans le système
est supérieur au
nombre d'instances de ce même composant dans la
bibliothèque (Mi > Ni)
Pour les trois cas, et en tenant compte de l'ordre de la position
de chacune des instances dans le système, le nombre de
possibilités est alors :
(2 . 1)
c N Mi
i =
i
En considérant tous les types des
composants implémentant le système, le nombre de
possibilités serait alors :
|
c =
|
Nb Types Systm
_ _
?
i=1
|
N i
M
i
|
(2 .2)
|
Nb_Types_Systm est le nombre de types différents
de composants dans le système à concevoir.
La complexité algorithmique du problème posé
est alors :
CPbm = O( c ) (2 . 3)
L'équation (2.3) montre clairement que la
complexité algorithmique du problème posé n'est pas
polynomiale (noter que Mi n'est pas une constante). De ce fait, une
méthode à base d'une heuristique ou d'une méta-heuristique
est nécessaire afin de faire face à n'importe quelle taille de ce
problème. Néanmoins, et comme il a été dit
auparavant, en absence de benchmarks pour le problème concerné,
une méthode exhaustive est nécessaire pour servir de
référence ou de repère au développement de la
méthode approchée. Les détails techniques de la
méthode exacte que nous avons développée seront
abordés dans le prochain chapitre. Dans ce qui suit, nous allons
décrire quelques aspects de la surface d'un circuit, sa vitesse et sa
consommation de puissance. Ces trois paramètres constituent l'essentiel
des contraintes de notre problème d'optimisation.
2.4 Définition des contraintes du problème:
2.4.1 Surface
Nous avons auparavant dit que la conception d'un circuit
nécessite plusieurs étapes. Ce n'est qu'à la
dernière étape qui consiste à générer le
fichier des masques (appelé GDS2) et destiné à la fonderie
pour la fabrication du circuit (ou système) où tous les
paramètres électriques sont précis. En d'autres termes,
plus le niveau d'abstraction est élevé, et moins sont
précis les paramètres électriques. Néanmoins, une
estimation de ces paramètres à chaque niveau de conception peut
être faite pour sélectionner, à ce niveau de conception,
une entité parmi d'autres, et ce, sans fausser le choix pour les niveaux
d'abstraction inférieurs.
En ce qui concerne notre problème, les interconnexions
(matérialisées par des lignes de métal - aluminium,
cuivre, ..-) ne sont pas exactement définies à ce niveau de
conception. Quoique ces interconnexions ont un impact non négligeable
sur la surface, la vitesse et la consommation de la puissance, nous
supposerons, sans fausser le problème, que leur impact est sensiblement
le même, quelle que soit la configuration (combinaison des instances des
composants utilisés par le système). De ce fait, afin de
sélectionner une combinaison d'instances parmi d'autres,
l'estimation de la surface requise par les instances
implémentant le système est suffisante. Or, du fait que toute
instance incluse dans la bibliothèque est caractérisée par
sa surface, sa vitesse et sa consommation de puissance, la surface induite par
une combinaison donnée s'obtient simplement par l'équation
suivante :
N
S comb = S I i (2.4)
( )
i = 1
N est le nombre total d'instances utilisées dans le
système ; Ii est une instance puisée de la bibliothèque et
existant dans la combinaison étudiée, S(Ii) est sa surface.
Rappelons que si Scomb > SF, alors cette combinaison serait
écartée.
| 
