R. Boudour ; M.T. Laskri - Outil de partitionnement hw/sw basé sur l’algorithme Kernighan/Lin amélioré

arima:1882 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 26 novembre 2007, Volume 7, 2007 - https://doi.org/10.46298/arima.1882
Outil de partitionnement hw/sw basé sur l’algorithme Kernighan/Lin amélioréArticle

Auteurs : R. Boudour 1; M.T. Laskri 1

  • 1 Département d’informatique Université Badji-Mokhtar

[en]
Partitioning of system functionality for implementation among multiple system components, such as among hardware and software components in codesign, is becoming an increasingly important topic. Various heuristics are used in automatic partitioning. In this paper, we present our tool, called AutoDec, implemented in Visual C++ 6.0. We verified that hierarchical clustering algorithm, based on closeness metrics, can be used to merge pieces of functionality before applying Kernighan/Lin algorithm, resulting in reduced execution time with often improvements in quality. In addition, we show that our approach, when used in partitioning, fills the gap between fast algorithms and highly-optimizing ones.

[fr]
Le partitionnement fonctionnel d’un système, en composants matériels et logiciels, acquiert de plus en plus de l’importance en conception conjointe. Plusieurs heuristiques et algorithmes sont utilisés en partitionnement. Dans ce papier, nous présentons l'outil, appelé AutoDec, implémenté en Visual C++ 6.0. Nous vérifions que l’algorithme hierarchical clustering, basé sur des métriques de rapprochement, peut être utilisé pour fusionner des parties fonctionnelles avant l’application de l’algorithme Kernihgan/Lin, entraînant ainsi une réduction notable du temps d’exécution avec souvent une amélioration accrue en qualité. En somme, nous montrons que notre approche, utilisée en partitionnement, permet de réduire le fossé entre les algorithmes rapides et hautement optimaux


Volume : Volume 7, 2007
Publié le : 26 novembre 2007
Soumis le : 15 mai 2007
Mots-clés : [INFO]Computer Science [cs], [MATH]Mathematics [math], [en] Codesign, automatic partitioning, closeness metrics, hierarchical clustering algorithm, Kernighan/Lin algorithm; [fr] Conception conjointe, partitionnement automatique, métriques de rapprochement, algorithme hierarchical clustering, algorithme Kernighan/Lin

Statistiques de consultation

Cette page a été consultée 519 fois.
Le PDF de cet article a été téléchargé 933 fois.