Brevet FR2937762A1 — publié le 20100430

Procédé pour la conception d'accélérateurs L'invention concerne les applications embarquées et, plus particulièrement, la conception d'accélérateurs adaptés à de telles applications. Les besoins de l'industrie militaire et civile en terme de calcul n'ont cessé de croître durant ces dernières années. Ces besoins se sont surtout exprimés dans le domaine des systèmes embarqués notamment en matière de traitement de signal et d'image. Ils se caractérisent aussi par de fortes contraintes, parfois contradictoires, de consommation d'énergie, de haute performance et de traitement temps réel. io Afin de répondre à ces fortes contraintes, aussi bien dans les systèmes embarqués que dans les systèmes haute-performance, et suite à la montée en fréquence des nouvelles technologies d'intégration, deux voies de recherche complémentaires se sont dégagées : le parallélisme et la spécialisation. Le parallélisme a permis de répondre partiellement au 15 problème lié à la montée en fréquence des technologies actuelle et de la montée en complexité des architectures des processeurs (superscalaire, ordonnancement dynamique des instructions, ...). Cependant, l'exécution efficace de certaines tâches nécessite des accélérateurs spéciaux, et ceci pour des raisons de contraintes de consommation ou des besoins en 20 performances. Les processeurs des cartes graphiques sont un exemple d'accélérateur spécialisé pour le traitement graphique. Selon l'art connu, il est possible de concevoir des accélérateurs ou des circuits adaptés et optimisés pour une boucle ou une procédure particulière dans une application. Le problème est plus complexe lorsqu'on 25 cherche à produire un accélérateur qui permet d'optimiser l'exécution de boucles ou procédures différentes dans une ou plusieurs applications. Les éléments de calculs spécialisés de type ASIC offrent des avantages en terme de performance et consommation d'énergie. Cependant le développement de telles unités reste une opération très coûteuse et 3o nécessite beaucoup d'efforts de développement et d'ingénierie pour la conception de ces circuits à partir des boucles de programme ou des algorithmes à accélérer. Une autre solution consiste à utiliser des accélérateurs programmables à mi-chemin entre les processeurs généralistes et les accélérateurs spécialisés. Par exemple, plusieurs accélérateurs SIMD (Single Instruction Multiple Data) ont été proposés par Intel (MMX, SSE), Motorola (Alitvec), ARM (Neon) et par d'autres acteurs de l'industrie. Les accélérateurs SIMD permettent l'exécution simultanée d'une instruction sur plusieurs données. D'autres accélérateurs programmables portant sur des portions d'application plus importantes ont aussi été proposés, par exemple ARM OptimoDETM propose une suite logicielle ainsi qu'une plateforme VLIW (Very long instruction Word) qui permet une exécution efficace des boucles. io Ces solutions ont pour inconvénients de ne pas offrir d'aussi bonnes performances et une aussi bonne consommation en énergie que des circuits spécialisés pour chacune des boucles que l'on souhaite exécuter. L'invention vise à pallier les problèmes cités précédemment en proposant un procédé pour la conception et la génération d'accélérateurs 15 optimisés selon les demandes d'une ou plusieurs applications. Une application spécifique peut contenir plusieurs boucles différentes à accélérer. Le procédé selon l'invention prend en compte une fonction de coût qui reflète les contraintes de l'application par exemple : une contrainte de temps réel ou une contrainte de consommation d'énergie. 20 En utilisant l'invention, on peut minimiser les coûts de conception et de fabrication des accélérateurs spécialisés en cherchant des accélérateurs adéquats et optimisés pour une gamme d'applications plutôt qu'une seule application spécifique. L'invention a donc pour avantage de produire des circuits optimisés pour une gamme d'applications tout en 25 conservant les avantages de performance et de consommation d'énergie acquis lors de la conception de chaque circuit correspondant à chaque application individuellement. A cet effet, l'invention a pour objet un procédé pour la conception d'accélérateurs, dits accélérateurs agrégats, chacun d'eux étant adapté à au 30 moins deux procédures d'un programme, un accélérateur agrégat comprenant des noeuds, correspondant à des éléments architecturaux, et des liens entre ces noeuds, ledit procédé de conception étant caractérisé en ce qu'il comporte les étapes suivantes : - la génération d'accélérateurs spécialisés adaptés auxdites procédures, la création d'au moins un accélérateur agrégat à partir desdits accélérateurs spécialisés et d'une base de données d'éléments architecturaux prédéfinis, le calcul d'un coût pour chacun des accélérateurs agrégats créés à 5 partir d'une fonction de coût prédéfinie, la sélection, en fonction du coût, d'un d'accélérateur agrégat parmi les accélérateurs créés. Selon une caractéristique de l'invention, l'étape de création d'au moins un accélérateur agrégat comprend : ~o - le choix d'un premier accélérateur spécialisé, nommé accélérateur agrégat, - la sélection d'un deuxième accélérateur parmi les accélérateurs non agrégés, nommé accélérateur à agréger, - l'agrégation du deuxième accélérateur au premier accélérateur, 15 - tant qu'il existe des accélérateurs non agrégés, la répétition de l'étape de sélection du deuxième accélérateur et de l'étape d'agrégation. Selon une caractéristique de l'invention, un lien définissant une relation parent enfant entre deux noeuds, l'étape d'agrégation de 20 l'accélérateur à agréger à l'accélérateur agrégat comprend : l'ajout de noeuds à l'accélérateur agrégat tant que tous les noeuds de l'accélérateur à agréger ne sont pas inclus dans un ensemble formé par les noeuds de l'accélérateur agrégat, le choix d'un premier noeud N1 appartenant à l'accélérateur à agréger, 25 - le choix d'un deuxième noeud N2 appartenant à l'accélérateur agrégat, l'association du premier noeud N1 au deuxième noeud N2, le premier noeud N1 et le deuxième noeud N2 étant associé : o si le deuxième noeud N2 est apte à exécuter les mêmes opérations arithmétiques et logiques que le premier noeud N1, et 30 o si chaque noeud parent du premier noeud N1 est associé à un noeud parent du deuxième noeud N2, o sinon, si un noeud parent du premier noeud N1 est associé à un troisième noeud S de l'accélérateur agrégat qui n'est pas un noeud parent du deuxième noeud N2 alors, la connexion du deuxième noeud N2 au troisième noeud S en ajoutant des liens et des multiplexeurs. si l'association a réussi et que le premier noeud N1 était le dernier noeud non-associé alors l'agrégation de l'accélérateur à agréger à l'accélérateur agrégat est terminée, sinon s'il existe encore un noeud non associé dans l'accélérateur à agréger, le retour à l'étape de choix du premier noeud N1, si l'association a échoué le retrait des liens et des multiplexeurs créés à l'étape précédente et le retour à l'étape de choix du deuxième noeud ~o N2. Selon une caractéristique de l'invention, les procédures sont des boucles d'un programme. L'invention sera mieux comprise et d'autres avantages 15 apparaîtront à la lecture de la description détaillée faite à titre d'exemple non limitatif et à l'aide des figures parmi lesquelles : La figure 1 représente un exemple d'une architecture matérielle utilisant un accélérateur. La figure 2 représente un exemple d'accélérateur adapté à une 20 boucle. l'invention. l'invention. 25 La figure 5 représente un organigramme illustrant une étape d'agrégation d'un accélérateur à un autre. L'invention concerne un procédé pour la conception d'accélérateurs, dits accélérateurs agrégats, chacun d'eux étant adapté à au moins deux boucles. De façon générale, un accélérateur peut être adapté à 30 une procédure ou même une application entière. La figure 1 représente un exemple d'une architecture matérielle utilisant un accélérateur. L'architecture matérielle comprend un microprocesseur 11 relié à une mémoire centrale 12 via une mémoire cache 13 et un bus de données 14. Le microprocesseur 11 est aussi relié à un 35 accélérateur 15. L'accélérateur dispose d'une première interface 16 pour La figure 3 représente un organigramme illustrant le procédé selon La figure 4 représente un exemple d'application du procédé selon communiquer avec le microprocesseur via une liaison particulière 17 et d'une seconde interface 18 pour communiquer avec la mémoire centrale 12 via le bus de données 14. Un accélérateur est un circuit électronique spécialisé dans certains calculs tels que des opérations sur des matrices ou des transformées de Fourier. Un tel circuit prend en charge les calculs pour lesquels il est spécialisé de façon à alléger la charge de calcul du microprocesseur auquel il est relié. Une telle architecture présente une puissance de calcul supérieure à une architecture simple ne présentant pas d'accélérateur. La figure 2 montre un exemple d'accélérateur 22 adapté à une boucle 21. La boucle 21 décrit le produit scalaire d'un premier vecteur A et d'un second vecteur B. L'accélérateur agrégat 22 comprend des noeuds, correspondant à des éléments architecturaux 23,24,25,26,27, et des liens entre ces noeuds. Ces éléments architecturaux sont aptes à exécuter des opérations arithmétiques et logiques. L'accélérateur comprend un premier 23 et un second 24 flux de données (appelé � stream � selon l'expression anglo-saxonne) pour stocker les valeurs du premier vecteur A et du second vecteur B. Les flux de données 23,24 permettent : - de découpler les accès mémoire des calculs même en les présentant 20 sous formes de flux continus, et, - d'exprimer des accès mémoire particuliers comme un accès par pas dans le cas d'accès non continu des matrices. De façon générale, les éléments architecturaux sont des composants électroniques qui peuvent être, par exemple : des registres, des 25 unités de calcul, des flux d'accès mémoires, des multiplieurs, des unités de calcul flottantes, des multiplexeurs. Cette liste n'est pas exhaustive. Les données du premier et du second flux de données sont communiquées à un multiplieur 25 réalisant la multiplication des deux valeurs qui lui sont communiquées. Le résultat du multiplieur est communiqué à un 30 additionneur 27 réalisant l'addition de cette valeur et de la valeur contenue dans un registre 26. Le résultat de l'additionneur est communiqué au registre 26. Le rôle du registre 26 correspond ainsi à celui de la variable sum dans la boucle 21. La figure 3 représente un organigramme illustrant le procédé selon 35 l'invention. La figure 4 représente un exemple d'application du procédé selon l'invention. Le procédé de conception selon l'invention comporte les étapes décrites ci-après. Ce procédé est destiné à être mis en oeuvre sur un calculateur. La première étape du procédé selon l'invention est la génération 31 d'accélérateurs spécialisés 43,44 adaptés à des boucles. Une boucle est décrite sous la forme d'un langage d'instructions informatiques. L'exemple comporte une première boucle 41 et une seconde boucle 42. La première étape génère un premier accélérateur spécialisé Al 43 adapté à la première application 41 et un second accélérateur spécialisé A2 44 adapté à la io deuxième application 42. Le premier accélérateur 43 comprend un premier registre 43.1 et un premier flux de données 43.2 reliés à un premier multiplieur 43.3. Le premier multiplieur est relié en sortie à un deuxième flux de données 43.4. Le deuxième accélérateur 44 comprend un deuxième registre 44.1 et un troisième registre 44.2 reliés à un premier additionneur 15 44.3. Le premier additionneur est relié en sortie à un troisième flux de données 44.4. La deuxième étape du procédé selon l'invention est la création 32 d'au moins un accélérateur agrégat 45 à partir des accélérateurs spécialisés 43,44 et d'une base de données 49 d'éléments architecturaux prédéfinis 20 49.1. Cette étape de création d'au moins un accélérateur agrégat 45 comprend : le choix 32.1 d'un accélérateur spécialisé, nommé accélérateur agrégat, on choisit, par exemple, le premier accélérateur spécialisé Al 43. la sélection 32.2 d'un accélérateur parmi les accélérateurs non 25 agrégés, nommé accélérateur à agréger, on choisit le premier accélérateur A2 44. l'agrégation 32.3 de l'accélérateur à agréger A2 à l'accélérateur agrégat Al tant 32.4 qu'il existe des accélérateurs non agrégés 32.3, la répétition 30 des étapes de sélection 32.2 accélérateur à agréger et d'agrégation 32.3. L'exemple comportant uniquement deux accélérateurs 43,44, il n'y a pas de répétition des étapes de sélection 32.2 accélérateur à agréger et d'agrégation 32.3. La figure 5 représente un organigramme illustrant le procédé de l'agrégation d'un accélérateur à un autre. L'étape d'agrégation 32.3 de l'accélérateur à agréger 44 à l'accélérateur agrégat 45 comprend : l'ajout 57 de noeuds à l'accélérateur agrégat 45 tant que tous les noeuds de l'accélérateur à agréger A2 ne sont pas inclus dans l'ensemble formé par les noeuds de l'accélérateur agrégat, on ajoute par exemple un premier additionneur 45.1 et un quatrième registre 45.3 à l'accélérateur agrégat 45. le choix d'un premier noeud N1 51 appartenant à l'accélérateur à 1 o agréger 44, le noeud choisi est, par exemple, le troisième flux de données 44.4. le choix d'un deuxième noeud N2 52 appartenant à l'accélérateur agrégat 45, le noeud choisi est, par exemple, le deuxième flux de données 43.4. 15 l'association du premier noeud N1 au deuxième noeud N2, les noeuds N1 et N2 pouvant être associés : o si le deuxième noeud N2 est apte à exécuter les mêmes opérations arithmétiques et logiques que le premier noeud N1, et o si chaque noeud parent du premier noeud N1 est associé à un 20 noeud parent du deuxième noeud N2, ou si le premier noeud N1 et le deuxième noeuds N2 n'ont pas de parents, o sinon, si un noeud parent du premier noeud N1 est associé à un troisième noeud S de A2 qui n'est pas un noeud parent du deuxième noeud N2 alors, la connexion du deuxième noeud N2 25 au troisième noeud S en ajoutant des liens et des multiplexeurs. Le deuxième flux de données 43.4 et le troisième flux de données 44.4 sont aptes à exécuter les mêmes opérations arithmétiques et logiques. L'étape suivante consiste donc à vérifier, de façon récursive, si le noeud parent du deuxième flux de données 43.4 peut être associé au noeud parent 30 du troisième flux de données 44.4. Le noeud parent du deuxième flux de données 43.4 est le premier multiplieur 43.3 alors que noeud parent du troisième flux de données 44.4 est le premier additionneur 44.3. Ces deux noeuds ne sont pas aptes à exécuter les mêmes opérations arithmétiques et logiques. Mais le premier accélérateur agrégat 45 comprend le deuxième 35 additionneur 45.1 pouvant être associé au premier additionneur 44.3. On ajoute donc un premier multiplexeur relié, d'une part, au troisième flux de données et, d'autre part, au deuxième additionneur 45.1 et au premier multiplieur 43.3. Toujours de façon récursive, on vérifie que les parents du premier additionneur peuvent être associés aux parents du deuxième additionneur 45.1. Le deuxième additionneur 44.3 n'a pas de noeud parent, mais le premier registre 43.1 et le quatrième registre 45.3 peuvent être associés au deuxième 44.1 et le troisième 44.2 registres. Des liens sont ajoutés pour connecter le premier registre 43.1 et le quatrième registres 45.3 au deuxième additionneur 45.1. ~o L'association 54 ayant réussi et le premier noeud N1 étant le dernier noeud non-associé alors l'agrégation de l'accélérateur à agréger 43 à l'accélérateur agrégat 45 est terminée 56. Dans le cas où il existe encore un noeud non associé dans l'accélérateur à agréger, le procédé selon l'invention prévoit le retour à 15 l'étape de choix 51 du premier noeud N1. Enfin si l'association 54 a échoué, le procédé selon l'invention comprend une étape de retrait 59 des liens et des multiplexeurs crées à l'étape précédente et le retour à l'étape de choix du deuxième noeud N2 52. Selon une variante de l'invention, l'étape de création 32 d'au 20 moins un accélérateur agrégat comprend la substitution d'au moins un noeud de l'accélérateur agrégat par un élément architectural issu de la base de données d'éléments architecturaux 39. La substitution peut intervenir, par exemple, lorsqu'on vérifie que le deuxième noeud N2 est apte à exécuter les mêmes opérations arithmétiques et logiques que le premier noeud N1. S'il 25 n'est pas apte à exécuter les mêmes opérations, il est remplacé par un noeud apte à exécuter l'ensemble des opérations exécutables par les deux noeuds. Un deuxième accélérateur agrégat 46, créé selon cette variante du procédé selon l'invention, comprend le premier registre 43.1, un cinquième registre 46.4 et le premier flux de données 43.2 relié à l'entrée 30 d'un deuxième multiplexeur 46.2. Le deuxième multiplexeur 46.2 est relié en sortie à une première unité arithmétique et logique (aussi appelé ALU) 46.1. Le deuxième multiplexeur 46.4 est contrôlé par un deuxième registre de configuration 46.3. Le deuxième registre de configuration 46.3 permet de sélectionner l'entrée du multiplexeur qui sera transmise à la sortie. La quatrième étape du procédé selon l'invention est le calcul 33 du coût de chacun des accélérateurs agrégats 46 créés à partir d'une fonction de coût prédéfinie. Selon une caractéristique de l'invention, l'accélérateur agrégat étant un composant électronique présentant une surface, la fonction coût comprend la surface de l'accélérateur agrégat. La surface d'un accélérateur peut être mesurée en nombre de transistors ou en millimètres carrés. Dans ce dernier cas, la surface dépend alors de la technologie de gravure utilisée. Selon une caractéristique de l'invention, la fonction coût comprend io la longueur maximale, mesurée en nombre de noeuds, d'un chemin entre un noeud en entrée et un noeud en sortie de l'accélérateur agrégat. Selon une caractéristique de l'invention, la fonction coût comprend la consommation électrique de l'accélérateur agrégat. Le calcul des fonctions de coûts ci-avant nécessite l'utilisation d'un 15 synthétiseur, synthétisant un accélérateur à partir de sa description sous la forme de noeuds et de liens. Ceci a pour inconvénient de nécessiter beaucoup de ressources de calcul. Un multiplexeur comprend plusieurs liens entrants. Chacun de ces liens est notamment caractérisé par un nombre de bits. Selon une variante 20 du procédé selon l'invention, la fonction de coût comprend le nombre de multiplexeurs pondéré par le nombre de bits sur les liens entrants des multiplexeurs (dit � bit width �) de l'accélérateur agrégat. Cette fonction coût a pour avantage de pouvoir être facilement calculée et de bien représenter le surcoût entraîné par l'agrégation des différents accélérateurs. 25 La sixième étape du procédé selon l'invention est la sélection 34, en fonction du coût, d'un d'accélérateur agrégat parmi les accélérateurs créés. Pour chaque accélérateur agrégat créé, on peut calculer une valeur grâce à la fonction coût. Par exemple, si on suppose que le nombre d'éléments architecturaux à une incidence directe sur la surface d'un 30 accélérateur agrégat le second accélérateur agrégat 46 aura une surface inférieure au premier 45. Ainsi, le second accélérateur agrégat 46 sera préféré au premier 45. Selon une caractéristique de l'invention, le procédé comprend, en outre, une étape de création d'un registre de configuration pour les 35 accélérateurs agrégats sélectionnés. Le registre de configuration 46.3 permet de configurer un accélérateur agrégat en contrôlant notamment ces multiplexeurs. Les différentes configurations du registre de configuration permettent de retrouver les fonctionnalités de chacun des accélérateurs spécifiques 43, 44. Dans l'accélérateur 46, dans une première configuration, c'est le résultat du cinquième registre 46.4 qui est transmis à la première ALU 46.1, la première ALU 46.1 étant configurée pour effectuer des additions. Dans une seconde configuration, c'est le résultat du premier flux de données 43.2 qui est transmis à la première ALU 46.1, la première ALU 46.1 étant configurée pour effectuer des multiplications. Selon une caractéristique de l'invention, l'étape de création de nouveaux accélérateurs agrégats est réalisée à partir d'une bibliothèque d'opérateurs correspondant à des sous-parties de circuits. L'étape de création de nouveaux accélérateurs agrégats permet alors d'alterner entre, d'une part, l'utilisation d'éléments architecturaux et, d'autre part, l'utilisation des opérateurs issus de la base de données d'opérateurs. REVENDICATIONS1. Procédé pour la conception d'accélérateurs, dits accélérateurs agrégats, chacun d'eux étant adapté à au moins deux procédures (41,42) d'un programme, un accélérateur agrégat (22) comprenant des noeuds, correspondant à des éléments architecturaux (23,24,25,26,27), et des liens entre ces noeuds, ledit procédé de conception étant caractérisé en ce qu'il comporte les étapes suivantes : la génération (31) d'accélérateurs spécialisés (43,44) adaptés auxdites procédures (41,42), la création (32) d'au moins un accélérateur agrégat (45) à partir desdits 10 accélérateurs spécialisés (43,44) et d'une base de données (49) d'éléments architecturaux prédéfinis (49.1), le calcul (33) d'un coût pour chacun des accélérateurs agrégats (46) créés à partir d'une fonction de coût prédéfinie, la sélection (34), en fonction du coût, d'un d'accélérateur agrégat parmi 15 les accélérateurs créés. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape de création (32) d'au moins un accélérateur agrégat (45) comprend : le choix d'un premier accélérateur spécialisé (32.1), nommé 20 accélérateur agrégat, la sélection (32.2) d'un deuxième accélérateur parmi les accélérateurs non agrégés, nommé accélérateur à agréger, l'agrégation (32.3) du deuxième accélérateur au premier accélérateur, tant qu'il existe des accélérateurs non agrégés, la répétition de l'étape 25 de sélection (32.2) du deuxième accélérateur et de l'étape d'agrégation (32.3). 3. Procédé selon la revendication 2, caractérisé en ce que, un lien définissant une relation parent enfant entre deux noeuds, l'étape d'agrégation 30 (32.3) de l'accélérateur à agréger à l'accélérateur agrégat comprend : - l'ajout (57) de noeuds à l'accélérateur agrégat tant que tous les noeuds de l'accélérateur à agréger ne sont pas inclus dans un ensemble formé par les noeuds de l'accélérateur agrégat,le choix d'un premier noeud N1 (51) appartenant à l'accélérateur à agréger, le choix d'un deuxième noeud N2 (52) appartenant à l'accélérateur agrégat, l'association (53) du premier noeud N1 au deuxième noeud N2, le premier noeud N1 et le deuxième noeud N2 étant associé : o si le deuxième noeud N2 est apte à exécuter les mêmes opérations arithmétiques et logiques que le premier noeud N1, et o si chaque noeud parent du premier noeud N1 est associé à un io noeud parent du deuxième noeud N2, o sinon, si un noeud parent du premier noeud N1 est associé à un troisième noeud S de l'accélérateur agrégat qui n'est pas un noeud parent du deuxième noeud N2 alors, la connexion du deuxième noeud N2 au troisième noeud S en ajoutant des liens et 15 des multiplexeurs. si l'association (54) a réussi et que le premier noeud N1 était le dernier noeud non-associé alors l'agrégation de l'accélérateur à agréger à l'accélérateur agrégat est terminée (56), sinon s'il existe encore un noeud non associé dans l'accélérateur à 20 agréger, le retour à l'étape de choix du premier noeud N1 (51), si l'association (54) a échoué le retrait (59) des liens et des multiplexeurs créés à l'étape précédente et le retour à l'étape de choix du deuxième noeud N2 (52). 25 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que, l'accélérateur agrégat étant un composant électronique présentant une surface, la fonction coût comprend la surface de l'accélérateur agrégat. 30 5. Procédé selon l'une des revendications précédentes, caractérisé en ce que la fonction coût comprend la fonction coût comprend la longueur maximale, mesurée en nombre de noeuds, d'un chemin entre un noeud en entrée et un noeud en sortie de l'accélérateur agrégat. 6. Procédé selon l'une des revendications précédentes, caractérisé en ce que la fonction coût comprend la consommation électrique de l'accélérateur agrégat. 7. Procédé selon l'une des revendications précédentes, caractérisé en ce que la fonction coût comprend le nombre de multiplexeurs de l'accélérateur agrégat pondéré par le nombre de bits sur les liens entrants des multiplexeurs. 8. Procédé selon l'une des revendications précédentes, caractérisé en ce qu'il comprend en outre une étape de création d'une table de configuration (47) pour les accélérateurs agrégats sélectionnés. 9. Procédé selon l'une des revendications précédentes, 15 caractérisé en ce que l'étape de création (32) d'au moins un accélérateur agrégat comprend la substitution d'au moins un noeud de l'accélérateur agrégat par un élément architectural issu de la base de données d'éléments architecturaux (39). 20 10. Procédé selon l'une des revendications précédentes, caractérisé en ce que les procédures sont des boucles d'un programme.