Prix EPFL de Doctorat - 2022 - Lana Josipović

Pour le développement d'une approche radicalement nouvelle pour générer des circuits numériques efficaces à partir de programmes informatiques.

Des outils de Synthèse de haut-niveau (HLS) peuvent générer des circuits électroniques à partir d'un langage de programmation haut-niveau. Ces outils créent quasiment toujours un chemin de données contrôlé à partir d'un contrôleur centralisé utilisant un ordonnancement statique connu au temps de compilation pour déterminer le cycle pendant lequel chaque opération s'exécute. Une telle approche permet de créer des pipelines ayant une bande passante élevée dans les cas où les accès à la mémoire sont prouvablement indépendants et que des décisions de contrôle critiques sont déterministiques pendant la compilation du code. Malheureusement, quand ce n'est pas le cas, les outils doivent faire des hypothèses pessimistes, créant ainsi des ordonnancements de plus basse qualité et une performance réduite. Une solution HLS alternative est de créer des circuits dataflow à partir de code de haut niveau. Les circuits dataflow sont conçus à partir d'unités qui communiquent en utilisant des signaux d'établissement de liaison (handshake); les données se propagent d'unité à unité aussitôt que les dépendances de contrôle et de mémoire le permettent, et sont arrêtés par le mécanisme de handshake le cas échéant. Ce mécanisme de contrôle distribué implémente ainsi un ordonnancement dynamique où les décisions d'ordonnancement sont faites de façon local dans le circuit pendant qu'il s'exécute. De tels circuits peuvent ainsi atteindre des comportements qui dépassent les capacités de circuits ordonnancés de façon statique.

Bien que la traduction de code haut-niveau en circuits dataflow est relativement simple, une traduction naïve n'est pas suffisante pour atteindre un fonctionnement correct, une haute performance, ainsi qu'un bon rendement au niveau de la surface nécessaire pour concevoir le circuit. Premièrement, sans un bon placement et dimensionnement de mémoires tampon, les circuits dataflow n'auraient qu'une capacité limitée pour être pipeliné. Deuxièmement, en l'absence d'un ordonnancement statique, il est difficile de détecter des opportunités pour partager des ressources. De plus, un tel partage de ressources pourrait causer un interblocage et ainsi compromettre la fonctionnalité du circuit. Troisièmement, les accès à la mémoire dans un circuit dataflow peuvent s'exécuter dans un ordre différent que celui spécifié dans le programme original --- une interface mémoire naïve n'est parfois pas suffisante pour garantir que toutes les dépendances des accès à la mémoire sont honorées. Finalement, les circuits dataflow standards ne supportent pas de spéculation, c'est-à-dire la capacité d'exécuter certaines opérations avant qu'il ne soit certain qu'elles soient nécessaires, ce qui empêche le pipelining quand une dépendance de donnée ou de contrôle prend du temps à résoudre.

La contribution de cette thèse est de développer des techniques qui permettent aux circuits dataflow d'être véritablement compétitifs dans le contexte de la HLS. Nous présentons en premier un ensemble de règles et de transformations pour créer des circuits dataflow à partir de spécifications de haut-niveau telles que des programmes C/C++. Nous détaillons ensuite une méthodologie pour placer et dimensionner des mémoires tampons dans des circuits dataflow afin de créer des pipelines à bande passante élevée. Nous montrons comment identifier de façon automatique des opportunités de partage de ressources ayant des performances acceptables et décrivons un mécanisme de partage pour créer des circuits dataflow étant fonctionnellement corrects et sans interblocage. Nous détaillons la construction d'une interface mémoire (une load-store queue) pour des circuits dataflow qui peut traiter des accès à la mémoire arrivant dans le désordre et montrons comment adapter cette interface à une application spécifique. De plus, nous présentons un cadre générique pour traiter la spéculation dans les circuits dataflow. Finalement, nous montrons que ces techniques permettent de gagner significativement plus de performance et de rendement de surface dans des situations appropriées.

Toutes ces fonctionnalités permettent aux circuits dataflow d'exposer un comportement dynamique similaire à celui des processeurs superscalaires modernes. Nous pensons que ces nouvelles techniques sont la clé pour le succès de la HLS dans de nouveaux contextes ainsi que dans des domaines d'application plus large.