Affectation de circuits d'une bibliothèque a des unités fonctionnelles d'une partie opérative avec des contraintes de surface, de vitesse et de consommation d'énergie.

CHAPITRE 2

Etude technique de

la problematique

2.1 Introduction :

Dans ce chapitre, nous montrerons que le travail accompli ne peut se faire manuellement par un concepteur de systèmes. La détermination de la complexité algorithmique du problème posé tranchera sur cette question. Même si la réponse est d'opter pour une méthode automatisée, cette complexité est à même de déterminer s'il faut développer une méthode exacte ou une méthode approchée. Ceci est très important dans la mesure où si la complexité est polynomiale, l'utilisation d'une heuristique ne se justifierait pas du fait qu'elle ne pourra produire, à chaque fois, la solution exacte. De ce fait, le développement d'une méthode exacte est doublement bénéfique :

- produire, pour n'importe quel cas, la solution exacte au problème si sa complexité est polynomiale,

- dans le cas contraire, cette méthode exhaustive pourrait servir de repère, en absence de benchmarks, pour le développement d'une méthode approchée fiable

La complexité du problème (consistant à trouver la combinaison d'instances de circuits qui vont constituer le système voulu tout en satisfaisant les contraintes qui lui sont liées) étant déterminée, nous aborderons dans ce même chapitre quelques aspects sur ces contraintes qui portent en général sur la surface, la vitesse et la consommation de la puissance. Ainsi, ce chapitre est entièrement consacré à une meilleure définition de la fonction objective et aux contraintes liées à ce problème qui, comme nous le verrons, est d'optimisation combinatoire.

2.2 Définition technique du problème:

Soit à concevoir un système S à partir d'une bibliothèque de cellules B={B1,1, B1,2, ...,B1,n1, , Bi,1, Bi,2, ...., Bi,ni, ...,BM,1, ...,BM,nM} en supposant que pour tout type de composant utilisé par S, il en existe au moins une instance dans la bibliothèque B.

Notons que _Bi,j est la j^ème instance du i^ème composant (1= j = Ni) ; Ni est le nombre maximal d'instances du composant i réalisant la même fonctionnalité que ce composant, mais les caractéristiques électriques de ces instances diffèrent.

Il s'agit alors de trouver la combinaison qui satisfait le mieux les contraintes imposées. En supposant que la surface, la vitesse et la consommation de la puissance induites par une combinaison combi sont respectivement Scomb,i, Vcomb,i et Pcomb,i, cette combinaison ne serait retenue que si :

Scomb,i = SF ET Vcomb,i = VF ET Pcomb,i = PF

SF, VF et PF sont respectivement les contraintes imposées sur la surface, la vitesse et la consommation de la puissance du système.

Ainsi, n'importe quelle combinaison satisfaisant les trois contraintes peut implémenter le système. Néanmoins, du fait que notre méthode étudie exhaustivement toutes les combinaisons, la meilleure parmi les combinaisons retenues sera candidate pour implémenter le système.