Optimisation de la compilation de déparseurs pour processeurs réseau implémentés sur FPGA

Les réseaux de télécommunication ont vu leur taille, leur complexité et leur débit augmenter de façon très importante ces dernières années. Pour suivre cette évolution, les commutateurs, responsables d'aiguiller les paquets, ont perdu en flexibilité ce qui a rendu l'intégration de nouveaux protocoles plus compliquée. Afin de redonner de la flexibilité aux réseaux, le paradigme du réseau défini par logiciel — Software Defined Networking (SDN) a été introduit. Avec le SDN, le plan des données et le plan de contrôle sont séparés et peuvent donc être modifiés de manière indépendante. Récemment, afin de rendre le plan des données programmables, l'architecture de commutateur indépendante des protocoles — Protocol Independent Switch Architecture (PISA) a été introduite avec le langage P4 permettant de la programmer. Dans cette thèse, nous nous intéressons à l'optimisation de la compilation d'applications décrites dans le langage P4 en vue de leur implémentation sur des réseaux prédiffusés programmables — Field Programmable Gate Array (FPGA). Tout d'abord, nous cherchons à définir les limites des FPGA pour l'implémentation d'applications décrites avec le langage P4. Pour cela, nous proposons une évaluation des différents éléments composant l'architecture PISA, et des pistes de travail afin d'améliorer l'implémentation de plans des données sur FPGA. Les résultats de notre évaluation montrent que la microarchitecture actuelle des FPGA limite l'implémentation de certains types de comparaisons ainsi que le débit maximum qui peut être atteint. Également, nos résultats montrent que l'implémentation du déparseur, responsable de générer le paquet à émettre, peut être améliorée. À la suite de notre analyse de l'implémentation de programmes P4 sur FPGA, nous avons identifié deux éléments limitant les implémentations actuelles du déparseur. D'une part, le graphe de déparsage généré depuis P4 est trop séquentiel. D'autre part, les architectures de déparseurs ne tirent pas suffisamment avantage de la structure interne des FPGA. Pour augmenter le parallélisme exprimé par le graphe de déparsage, nous proposons d'effectuer une fermeture transitive du graphe. Cette transformation permet d'exposer le parallélisme pour l'évaluation des conditions de transition entre les sommets du graphe. Avec la transformation du graphe de déparsage, nous proposons une nouvelle architecture de déparseur générée depuis le graphe. L'architecture proposée maximise l'utilisation de connexions fixes afin de tirer avantage de la capacité de reconfiguration du FPGA. Notre approche permet ainsi de générer des déparseurs depuis des programmes P4 utilisant de 4× à 10× moins de ressources que les travaux précédents. Afin de réduire le coût d'implémentation de notre nouvelle architecture, nous proposons d'élaguer le graphe de déparsage en effectuant la spécialisation de programmes P4. La spécialisation est effectuée à l'aide de l'évaluation symbolique de certaines variables du programme P4. L'élagage du graphe de déparsage permet de réduire de 50 % l'utilisation de ressources par le déparseur comparé à la première approche proposée.

Abstract

Computer networks have, in recent years, significantly increased in size, complexity and throughput. To keep up with this evolution, switches, which route network packets, have lost in flexibility, hence making the integration of new protocols more complex. To restore flexibility into the network, the Software Defined Networking (SDN) paradigm has been introduced. With SDN, the data and control planes are separated and can therefore evolve independently. Recently, to bring programmability to the data plane, the Protocol Independent Switch Architecture (PISA) has been proposed alongside the P4 language to program it. In this thesis, we focus on the optimization of the compilation of applications described using the P4 language with regards to their implementation on Field Programmable Gate Arrays (FPGAs). First of all, we seek to determine the limits of FPGAs concerning the implementation of applications described with the P4 language. For this purpose, we propose an evaluation of the different elements composing the PISA architecture, and avenues to improve implementation of network data planes on FPGA. Our evaluation results demonstrate that the current microarchitecture of FPGAs limits the implementation of certain types of comparisons as well as the maximum achievable throughput. Also, our results indicate that the implementation of the deparser, which generates the packet to be emitted, can be improved. Resulting from our analysis of the implementation of P4 programs on FPGAs, we have identified two elements limiting current deparser implementations. Firstly, the deparser graph generated from the P4 code is too sequential. Secondly, deparser architectures do not take sufficient advantage of the internal structure of FPGAs. To increase the parallelism expressed in the deparser graph, we propose to perform a transitive closure on the graph. With this transformation it is possible to expose the parallelism of the transition conditions evaluation between the vertices of the graph. Along with the transformation of the deparser graph, we propose a new deparser architecture generated from the graph. The proposed architecture maximizes the use of fixed connections in order to take advantage of the reconfiguration capability of the FPGA. Our approach makes it possible to generate deparsers from P4 programs using 4× to 10× fewer resources compared to previous work. In order to reduce the cost of our new architecture, we propose to prune the deparsing graph by performing P4 program specialization. The specialization is carried out by applying viii symbolic evaluation on certain variables of the P4 program. Pruning the deparsing graph reduces the deparser resource usage by 50 % compared to the first approach we proposed.