Un algorithme hybride pour la résolution du problème de partitionnement matériel/logiciel

Abstract

Pour développer un système embarqué avec un rapport coût / performance  raisonnable, les concepteurs s’orientent vers la conception  conjointe matériel/logiciel (M/L) ou codesign. Cette méthodologie comporte une suite d’étapes dont les résultats de la première est une spécification exécutable et la dernière est un prototype virtuel du système. Le  partitionnement M/L, une étape cruciale du processus de Co design, a pour finalité de diviser le comportement d’un système en deux sous-ensembles de fonctions, l’un matériel et l’autre logiciel. Le problème de  partitionnement M/L étant NP-difficile, la littérature foisonne d’approches complémentaires pour remédier approximativement à ce problème. Dans ce papier, nous proposons un nouveau algorithme hybride et fiable de partitionnement M/L basé sur le principe de l’algorithme Late Acceptance Hill Climbing(LAHC) et de l'algorithme génétique (AG). LAHC est connue pour sa recherche locale efficace, conjuguée à la potentialité importante de recherche globale de l’AG. L'algorithme hybride, a été appliqué et a donné de meilleurs résultats, comparés à ceux de l’état de l’art.

Mots clés : Partitionnement M/L-Metaheuristique-Acceptation tardive de Hill Climbing- Algorithme génétique- Algorithme hybride

Hybrid algorithm for solving hardware/Software partitioning problem

To develop an embedded system with a reasonable cost / performance ratio, the designers were moving towards the hardware/software co-design. This methodology comprises a sequence of steps whose results from the first is an executable specification and the latter is a virtual prototype of the system. Hardware/software Partitioning, a crucial step in Co-design process, aims to divide the system’s behavior in two subsets of functions, one hardware and the other software. The Hw/Sw partitioning problem being NP-hard, the literature abounds with complementary approaches to remedy this problem roughly. In this paper, we propose a new hybrid and reliable Hw/Sw partitioning algorithm based on the principle of the Late Acceptance Hill Climbing (LAHC) technique and the Genetic Algorithm (GA). LAHC is known for its efficient local research, combined with the important potentiality of the AG total research. The hybrid algorithm has been applied and has given better results, compared to those of the state of Art.

Key words: Hw/Sw partitioning-Metaheuristic-Late Acceptance Hill Climbing- Genetic Algorithm- Hybrid Algorithm