Parallélisme des métaheuristique : vue générale et classification

Parallélisme des métaheuristique : vue générale et classification

Dans un domaine comme l’informatique, les besoins de performance sont toujours croissants. Les programmes informatiques doivent gérer de plus en plus de données et ce, de plus en plus rapidement. Il est toutefois possible de rendre un programme plus performant en améliorant l’algorithme ou la machine sur laquelle il s’exécute. Une autre approche consiste à combiner les deux options et ainsi adapter un programme à une architecture matérielle plus performante. C’est pour répondre à une demande de plus en plus pressante qu’est apparu le parallélisme[Noe07]. Dans la plus parts des cas le calcul parallèle est considéré comme un moyen d’augmanter la performance (réduire le temps d’exécution) des applications qui nécessitent une grande quantité de calcul. Le parallélisme de métaheuristiques est la technique généralement utilisée pour traiter les grandes instances des problèmes difficiles ; le but était d’utiliser le calcul parallèle pour réduire le temps d’exucution afin de traiter des grandes instance des problèmes difficils, mais on va voire que l’apparition des modèles basés sur la notion de multi-cherche coopérative a conduit non seulement à réduire le temps de calcul mais aussi à trouver des solutions de qualité supérieure. Dans ce chapitre on va donner un aperçu sur les stratégies et les modèles du parallélisme des métaheuristiques.

Le parallélisme

On peut définir le calcul parallèle comme l’utilisation simultanée des ressources multiples de calcul (un ordinateur simple avec les processeurs multiples, un nombre arbitraire d’ordinateurs s’est relié par un réseau ou nombre arbitraire d’ordinateurs s’est relié par un réseau) pour résoudre un problème informatique, et on peut imaginer un programme qui s’exécute à l’aide des unités centrales de traitement multiples. Un problème décomposé en parties discrètes qui peuvent être résolues concurremment chaque partie est une série d’instructions. Ces instructions s’exécutent simultanément sur différentes unités centrales de traitement. 

Motivations

  La vitesse des processeurs ne continuera pas augmenter à cause des contraintes physiques (vitesse de transfert des donneés ne peut pas depasse la vitesse de la lumiere).  Le calcul parallèle peut être :  la seule solution pour traiter certains gros calculs en un temps donné.  la solution la plus simple ou la moins onéreuse pour traiter certains calculs en un temps donné.  Le calcul parallèle apporte une solution pour des problèmes nécessitant une haute tolérance aux fautes.  L’univers est hautement parallèle. 

Modèles de programmations parallèles 

Il y a plusieurs modèles de programmation parallèle d’usage courant citant :  Le modèle de Données parallèles.  Le modèle de programmation a mémoire partagée.  Le modèle de passage de message. 

Parallélisme De Données

 Ce modèle de parallélisme est utilisé pour l’exploitation de la simultanéité qui se produite de l’application du même flux d’instructions aux différents éléments d’une structure de données. Par exemple, l’addition de 2 à tous les éléments d’une rangée, ou l’incrémentation du salaire de tous les employés avec 5 ans de service. Les programmes de parallélisme de données sont caractérisés par les caractéristiques suivantes :  chaque opération sur chaque élément d’informations peut être considérée comme une tâche indépendante.  La granularité normale d’un calcul donnée-parallèle est petite.  Le concept de localité des données ne manifeste pas naturellement. Noté que les compilateurs de parallélisme de données exigent souvent du programmeur de fournir des informations au sujet de la façon dont les données doivent être réparties sur les processeurs, c.-à-d. de la façon dont les données doivent être divisées sur les tâches. Après le compilateur peut traduire le programme de données parallèles sous forme de SIMD, et produire un code de communication automatiquement. 

Mémoire Partagée

 Dans le modèle de programmation a Mémoire Partagée les tâches partagent un espace d’adressage commun. Chaque tache (processus) peut exécuter les opérations de lecture ou d’écriture d’une manière asynchrone. Le control d’accès à la mémoire partagée est assuré avec les mécanismes d’exclusion mutuelle tels que les verrous et les sémaphores. L’avantage de ce modèle est que pour le programmeur il n’y a aucun besoin d’indiquer explicitement comment faire communiquer les données des producteurs aux consommateurs, ceci est à cause de l’absence de la notion de l’ownership de données. Cependant la compréhension et le maintien de la localité des données est plus difficile, par conséquent il est plus difficile d’écrire des programmes déterministes. Dans un environnement avec mémoire distribuée on trouve une autre variété c’est le modèle de la mémoire virtuelle partagée (Virtual Shared Memory VSM). La mémoire distribuée partagée (DSM) est une extension du modèle de programmation à mémoire partagée sur les systèmes qu’ils n’ont pas une mémoire physiquement partagée. L’accès se fait à l’aide des opérations de lecture et écriture habituelles. Contrairement au passage de message, dans un système de DSM un processus qui veut effectuer des opérations sur quelques données n’a pas besoin de connaître son endroit ; le système les cherchera et trouvera automatiquement. Dans la plupart des systèmes de DSM, des données partagées peuvent être repliées pour augmenter le parallélisme et l’efficacité des applications. Tandis que les machines parallèles scalable sont la plupart du temps basées sur la mémoire distribuée, beaucoup d’utilisateurs trouvent que plus facile d’écrire des programmes parallèles en utilisant un modèle de programmation de shared-mémoire. Ceci fait à DSM un modèle très prometteur, s’il est mis en application avec efficacité[Fos95]