moteur de recherche

Séminaire Algo - Serghei Verlan
Séminaire Algo - Serghei Verlan
3-Mar-2020 14:00
Age: 200 days





Serghei Verlan

Implémentations matérielles efficaces des modèles de calcul non-conventionnel

Salle de séminaire (4B125) - Bâtiment Copernic

Abstract: Les modèles de calcul non-conventionnel permettent d'avoir une approche différente pour la résolution des différents problèmes, plus particulièrement des problèmes d'optimisation et d'algorithmique parallèle. Dans la plupart des cas, les modèles sous-jacents sont massivement parallèles et ne peuvent pas être implémentés efficacement en logiciel sur des architectures courantes.

Nous nous sommes intéressés récemment par le développement des architectures matérielles spécialisés (en circuits logiques matériels à l'aide des FPGA) ce que permettrait d'avoir une exécution réellement parallèle des modèles correspondants. Afin d'obtenir des implémentations efficaces nous avons analysé les opérations possibles en FPGA et nous avons proposé des restrictions théoriques sur les modèles considérés ce que nous a permis d'obtenir des implémentations très efficaces (speed-up de l'ordre 105 par rapport aux réalisations logicielles et une vitesse de calcul à 108 étapes/s).

Ce qui est particulier dans notre démarche, c'est l'utilisation des résultats théoriques de la théorie des langages formels afin d'obtenir les résultats d'accélération cités ci-dessus. Nous allons montrer des exemples (concernant l'implémentation des différentes versions des systèmes à membranes) où l'efficacité de l'implémentation est une conséquence de la réduction du problème de simulation au problème du nombre des mots dans un langage rationnel. Nous allons également donner l'exemple de l'implémentation efficace des systèmes à membranes numériques où le point clef est la possibilité d'expression du problème en arithmétique de Presburger. Nous avons également montré que dans ce cas le modèle correspond à un système d'équations non-linéaires en différences finies et nous avons appliqué cette correspondance pour la création des contrôleurs matériels (extrêmement rapides - environs 10ns de temps de réponse) pour le problème du déplacement des robots à roues.








<- Back to: Accueil