L'outil de partitionnement de circuits est basé sur un algorithme de partitionnement de graphes Metis [] ou d'hypergraphes, HMetis [].
Il a été implanté dans SIS par la commande part. La
commande s'applique sur le circuit courant (obtenu par exemple par la
commande read_blif). La syntaxe est la suivante :
sis> part nb out
où nb est le nombre de parties désirées et
out est le nom de sortie des fichiers résultants.
La commande partitionne le graphe représentant le circuit
sans toucher à la logique interne des sommets. Chaque sommet
interne (autre que les entrées/sorties) est affecté à l'une
des parties out.part-0, ... out.part-;SPMlt;nb-1;SPMgt;. Des
entrées/sorties sont générées automatiquement pour les E/S
initiales du circuit et les signaux internes utilisés par des
sommets se situant dans des parties distinctes. Les parties sont
écrites au format BLIF dans les fichiers résultants. Ceux-ci
sont situés dans le répertoire courant.
Le partitionnement est réalisé en essayant d'équilibrer le
nombre de sommets (internes) par partie. Par défaut, chaque
sommet a le même poids, mais il est possible d'affecter un poids
différent aux différent sommets pour refléter la complexité de
leur logique interne. Cela permet d'équilibrer la taille des
parties non plus en nombre de sommets, mais avec une métrique
plus fine reflétant la complexité des parties. La complexité
d'une partie est alors mesurée par la somme des complexités des
sommets qui y sont inclus. Avoir une mesure, même approximative de
la complexité d'une partie, permet d'estimer le temps de
synthèse qui sera nécessaire à l'optimisation par un algorithme
de synthèse logique de cette partie. Equilibrer la complexité
des parties entraîne un équilibrage de la charge de calcul lors
de la synthèse simultanée par des processeurs distincts de
l'ensemble des parties.
La notion de complexité est intéressante pour évaluer le temps de synthèse correspondant à l'optimisation logique d'un sommet. Or l'optimisation dépend du type d'algorithme employé : il n'est par exemple pas possible d'évaluer a priori le nombre de noyaux qui seront extrait d'une équation logique pour sa factorisation.
Une mesure générale de complexité peut être le nombre le
litéraux de la forme SOP d'une équation. Certains algorithmes
d'optimisation se basent sur le voisinage d'un sommet pour l'optimiser
(méthodes de réinjection). Une autre métrique consiste à
calculer le nombre d'entrées que comporte une équation.
Lorsque l'on partitionne les sommets dans différentes parties,
des informations de dépendances entre sommets sont perdues. Comme il
a été dit plus haut, des signaux d'E/S sont générés
automatiquement pour des sommets partageant le même signal, mais
situés dans des parties différentes. Supposons que un sommet
interne A produise en sortie le signal a. Si a est utilisé en
entrée par le sommet B, et que A et B sont placés dans des
parties et respectivement lors du partitionnement, une
sortie primaire a sera générée pour le circuit et une
entrée primaire a sera générée pour le circuit . Lors
de l'optimisation du circuit , le signal a sera considéré
comme un signal d'entrée/sortie, et non pas comme le résultat de
la fonction logique A. Aucune optimisation basée sur les
propriétés de A ne sera donc possible. Par exemple, si
l'équation du sommet A est a = 1 (fonction constante) et que
celle de B est b = a + ce, B peut se simplifier en b = ce en
considérant le réseau globalement. Si A et B sont dans des
parties séparées, la constante a ne peut être propagée
pour simplifier B.
Un réseau optimisé globalement permet d'obtenir de meilleurs
résultats en terme de qualité, en exploitant les dépendances
entre sommets, comme montré dans l'exemple de réinjection
ci-dessus. De nombreux algorithmes exploitent ces informations de
dépendance. Le problème réside dans le fait que les algorithmes
de synthèse exigent des ressources de calcul et des temps
d'exécution exponentiels par rapport au nombre d'équations que
comporte le circuit (algorithmes NP-complets).
Une première solution consiste à employer des heuristiques.
Celles-ci fournissent des solutions approchées, parfois de bonne
qualité. Mais même si ces heuristiques sont moins coûteuses en
ressources que des algorithmes exacts, elles atteignent elles-aussi
des temps d'exécution prohibitifs pour des circuits de grande
taille.
L'avènement de circuits intégrés ASIC ou FPGA de
taille de plus en plus importantes autorise aujourd'hui la
réalisation dans le matériel de circuits de taille très
importante. Ces progrès technologiques s'accompagnent de
l'apparition de logiciels et de langages de spécification de
circuits de haut niveau pour maitriser la complexité des circuits
réalisables dans ces nouvelles technologies.
Tant l'évolution de la capacité des circuits que celle des
possibilités de spécification de fonctionnalités complexes
induisent des besoins très importants en capacité de traitement
lors de l'étape intermédiaire entre la spécification et la
réalisation physique que constitue la synthèse logique. La
méthode de synthèse par partitionnement offre l'avantage de
réduire la taille des circuits traités. Par contre, elle induit
une perte au niveau de la qualité finale du circuit, reconstitué,
après optimisations de ses différentes parties.
Pour minimiser cette perte, il faut minimiser le nombre de signaux
partagés par différentes parties, tout en préservant
l'équilibre en terme de complexité de celles-ci. Ce problème
revient à réaliser un partitonnement multi-partie de graphe (
k-way partitioning problem). Le graphe traité est celui associé
au réseau booléen définissant le circuit, en affectant aux
différents sommets un poids reflétant leur complexité. Le but
de l'algorithme est de partitionner le graphe en équilibrant les
poids entre parties et en minimisant la coupe. La coupe est définie
comme le nombre d'arêtes du graphe connectant des sommets situés
dans des parties distinctes. C'est ce que réalise les algorithmes
Metis et HMetis interfacés par la commande part dans SIS.
Sa syntaxe complète est la suivante :
part [options] [-f out]
les options sont les suivantes :
Le réassemblage, après optimisation par un logiciel de synthèse
des différentes parties est réalisé par la commande
merge, elle aussi intégrée dans SIS. Sa syntaxe est la
suivante :
merge [-f in] [-p nb]
in est le nom des nb fichiers à réassembler, décrivant les sous-circuits au format BLIF (défauts : partition et 4).