Programmer Le Parallelisme Avec Des Futures En Heptagon Un Langage Synchrone Flot De Donnees Et Etude Des Reseaux De Kahn En Vue D Une Compilation Synchrone
Download Programmer Le Parallelisme Avec Des Futures En Heptagon Un Langage Synchrone Flot De Donnees Et Etude Des Reseaux De Kahn En Vue D Une Compilation Synchrone PDF/ePub or read online books in Mobi eBooks. Click Download or Read Online button to get Programmer Le Parallelisme Avec Des Futures En Heptagon Un Langage Synchrone Flot De Donnees Et Etude Des Reseaux De Kahn En Vue D Une Compilation Synchrone book now. This website allows unlimited access to, at the time of writing, more than 1.5 million titles, including hundreds of thousands of titles in various foreign languages.
Programmer le parallélisme avec des futures en Heptagon un langage synchrone flot de données et étude des réseaux de Kahn en vue d'une compilation synchrone
Les langages synchrones ont été fondés pour modéliser et implémenter les systèmes réactifs temps-réels critiques. Avec la complexité toujours croissante des systèmes contrôlés, la vitesse d'exécution devient un critère important. Nous sommes donc à la recherche d'une exécution parallèle, combinant efficacité et sûreté.Les langages synchrones ont toujours intégré la notion de parallélisme, mais ce, pour l'expressivité de la modélisation. Leurs compilations visent principalement les circuits ou la génération de code séquentiel. Tous ont une sémantique formelle, qui rend possible la distribution correcte du code. Mais la préservation de cette sémantique peut être un obstacle à l'efficacité du code généré, particulièrement s'il est nécessaire de préserver une notion d'instant global au système.Le modèle sémantique qui nous intéresse est celui des réseaux de Kahn. Ces réseaux modélisent des calculateurs distribués, communiquant au travers de files de taille non bornée. Dans ce cadre, la distribution ne demande aucune communication ni synchronisation supplémentaire. En considérant l'histoire des files de communication, la sémantique de Kahn permet de s'abstraire de l'exécution effective, tout en garantissant le déterminisme du calcul. Pour cela, chaque nœud du réseau doit avoir une sémantique fonctionnelle continue.Le langage que nous développons est Heptagon, un langage synchrone fonctionnel du premier ordre, déscendant de Lustre. Son compilateur est un prototype universitaire, apparenté à l'outil industriel Scade. Grâce à sa sémantique de Kahn, la distribution d'un programme Heptagon ne pose pas de question, son efficacité beaucoup plus.L'efficacité requiert de minimiser les synchronisations. Cela revêt deux aspects non indépendants. Avoir un découplage suffisant des calculs : il y a des délais dans les dépendances entre calculs. Avoir une granularité importante des calculs : un fort ratio temps de calcul sur fréquence de communication. Or la sémantique synchrone et les horloges d'un programme Heptagon reflètent exactement l'inverse. Elles permettent au programmeur de se contenter d'un découplage d'un instant et à chaque instant, au maximum une valeur est calculée. De plus, les instants sont typiquement courts, pour assurer que le système réagit rapidement.Des précédents travaux sur le sujet, nous tirons deux constats.Le premier est que nous souhaitons le contrôle du parallélisme par le programmeur, directement dans le code source. Il doit pouvoir maîtriser à quels instants il y a communication ou synchronisation. La solution que nous proposons dans ce manuscrit est l'utilisation des futures dans Heptagon. Ils fournissent ce pouvoir au programmeur, tout en restant des annotations qui peuvent être supprimées sans changer la sémantique dénotationnelle du programme.Le deuxième constat est que la question de la granularité des calculs est une question profonde, touchant en particulier aux questions de dépendance de données, de choix des horloges et de compilation modulaire. Heptagon, comme ses parents, restreint les réseaux de Kahn qui peuvent être écrits, de telle sorte que ces trois questions se traitent séparément. Pour mieux comprendre le lien entre ces éléments, nous revenons aux réseaux de Kahn. Notre principal résultat est la définition de la sous-classe des réseaux ordonnés réactifs. Ceux-ci sont les seuls pour lesquels nous pouvons décrire modulairement le comportement avec des horloges, sans restreindre les contextes d'appels. Ces réseaux ont une signature d'horloge en forme normale, qui maximise la granularité. Pour l'exprimer, nous introduisons les horloges entières, décrivant la communication de plusieurs valeurs en un seul instant. Nous appliquons ensuite nos résultats pour voir sous un nouveau jour Heptagon, Signal, les politiques des objets de Lucid Synchrone, mais aussi proposer une analyse pleinement modulaire de Lucy-n langage synchrone le plus fidèle aux réseaux de Kahn.
Modèle n-synchrone pour la programmation de réseaux de Kahn à mémoire bornée
Dans cette thèse, nous nous intéressons aux modèles et aux langages pour la programmation d'applications de traitement de flux ayant des contraintes de temps-réel, comme les applications multimédias. Elles manipulent des flots de données infinis, auxquels sont appliquées des opérations successives. Ces systèmes peuvent être représentés par des réseaux de Kahn. Dans ce modèle, des noeuds de calcul s'exécutent de manière concurrente et communiquent à travers des buffers infinis. Son intérêt est d'être déterministe tout en permettant d'exprimer le parallélisme intrinsèque aux applications. Néanmoins, il présente l'inconvénient de ne pas donner de garanties sur l'absence d'interblocage et sur le caractère borné des buffers. Les langages synchrones flot de données fournissent un cadre simple pour la programmation de réseaux de Kahn sans buffers. Ils offrent des garanties fortes comme l'absence de blocage et un besoin en mémoire bornée. La contrepartie de ces garanties est un manque de souplesse dans la composition des flots : celle-ci doit être réalisée sans buffers. Le modèle n-synchrone est une extension du modèle synchrone qui relâche cette contrainte de manière contrôlée. Il permet une composition plus souple, tout en conservant les garanties statiques offertes par les langages synchrones. Nous présentons un langage qui met en oeuvre le modèle n-synchrone. En particulier, nous détaillons les analyses permettant de vérifier statiquement qu'un programme est exécutable avec des buffers bornés et de calculer automatiquement leur taille.
COMPILATION DES LANGAGES A PARALLELISME DE DONNEES
LES LANGAGES A PARALLELISME DE DONNEES OFFRENT UNE OPPORTUNITE D'ECRIRE DES PROGRAMMES PARALLELES NE DEPENDANT PAS D'UN MODELE PARTICULIER D'ARCHITECTURES. ILS PERMETTENT AINSI UNE MEILLEURS PORTABILITE DES APPLICATIONS. CEPENDANT, ILS OFFRENT PEU DE SUPPORT POUR LES PROBLEMES D'EQUILIBRAGE DE CHARGE. DANS LE LANGAGE HIGH PERFORMANCE FORTRAN, L'UTILISATEUR DOIT EXPLICITEMENT UTILISER DES REDISTRIBUTIONS DE DONNEES. CES REDISTRIBUTION SONT DES OPERATIONS COUTEUSES ET IL N'A PAS DE MOYEN STANDARD DE PRENDRE EN COMPTE L'HETEROGENEITE DES MACHINES ET DES RESEAUX. LA CONTRIBUTION DE CETTE THESE EST DE PROPOSER ET DE METTRE EN UVRE UNE SOLUTION QUI PERMETTE D'INTEGRER LES POLITIQUES D'EQUILIBRAGE DE CHARGE GENERIQUES A L'EXECUTION DE PROGRAMME A PARALLELISME DE DONNEES. L'INTERFACE EST REALISEE EN CONSIDERANT LES PROGRAMMES A PARALLELISME DE DONNEES COMME UN ENSEMBLE D'ACTIVITES COMMUNICANTES DE GRAIN MOYEN. L'INTEGRATION EST REALISEE SANS INTERFERENCE AVEC LE CODE UTILISATEUR GRACE AUX POLITIQUES D'EQUILIBRAGE DE CHARGE NON INTRUSIVES. POUR NOTRE PART, NOUS DEVONS PERMETTRE AUX ACTIVITES D'ETRE DEPLACEES PREEMPTIVEMENT. NOTRE CHOIX A ETE D'IMPLANTER LES ACTIVITES PAR DES PROCESSUS LEGERS. LES RAISONS ONT ETE LA POSSIBILITE D'UNE MISE EN UVRE RAPIDE ET LES PERFORMANCES QUE PERMETTENT LES PROCESSUS LEGERS. LA DERNIERE RAISON A ETE L'EXISTENCE D'ENVIRONNEMENTS FOURNISSANT LA MIGRATION DE PROCESSUS LEGERS COMME PM2. NOUS AVONS IMPLANTE LA PROPOSITION DANS UN COMPILATEUR HPF (ADAPTOR) ET UN COMPILATEUR CSTAR (UNH-CSTAR). CES DEUX IMPLANTATIONS ONT NECESSITE ESSENTIELLEMENT DES MODIFICATIONS DE L'EXECUTIF MAIS AUSSI DU COMPILATEUR SOURCE A SOURCE POUR CSTAR. ENFIN, NOUS AVONS VALIDE LA PROPOSITION AINSI QUE LA CHAINE DE COMPILATION SUR QUATRE NOYAUX APPLICATIONS : LE PIVOT PARTIEL DE GAUSS, L'APPLICATION DE MANDELBROT, UNE SIMULATION DE COMBUSTION ET UNE APPLICATION D'IMAGERIE (LES DIVIDING CUBES). LES MESURES REALISEES MONTRENT LA PERTINENCE DE LA PROPOSITION.