Brevet FR3063358A1 — publié le 20180831

DOMAINE TECHNIQUE AUQUEL SE RAPPORTE L'INVENTION La présente invention concerne de manière générale un procédé d'estimation d'un temps d'exécution d'une partie de code d'un algorithme, par un processeur d'une architecture de calcul. Elle concerne en particulier un procédé d'estimation d'un temps d'exécution d'une pluralité d'opérations constituant une partie de code d'un algorithme, par une pluralité d'unités élémentaires de calcul d'un processeur et/ou par une unité de mémoire dudit processeur, dans lequel il est prévu des étapes de : a) détermination d'un temps global de calcul associé au processeur en fonction d'un temps individuel de calcul associé à chacune des unités élémentaires de calcul du processeur, et/ou b) détermination d'un temps global d'accès à la mémoire en fonction de la quantité de données contenue dans les opérations de ladite partie de code, à lire et/ou à écrire par l'unité de mémoire, et c) estimation du temps d'exécution en fonction dudit temps global de calcul et/ou dudit temps global d'accès à la mémoire. L'invention est particulièrement utile pour sélectionner une architecture de calcul parmi plusieurs architectures de calcul, voire un mode de répartition de l'algorithme sur cette architecture de calcul, en vue de son implantation dans un véhicule automobile pour la mise en oeuvre d'un algorithme de traitement d'images « en temps réel ». ARRIERE-PLAN TECHNOLOGIQUE De plus en plus de véhicules automobiles sont équipés de dispositifs d'aide à la conduite embarqués comprenant un dispositif de capture d'images ainsi qu'une architecture de calcul configurée pour mettre en oeuvre un algorithme de traitement d'images qui traite les images capturées et extrait de ces images des informations utiles à la conduite (telles que la position d'un obstacle par rapport au véhicule automobile). Ces informations peuvent ensuite être communiquées au conducteur du véhicule automobile et/ou prises en compte directement pour commander des actionneurs du véhicule automobile tels qu'un dispositif de freinage d'urgence. 3063358 2 Pour que les informations déduites des images traitées soient effectivement utiles à la conduite, il est primordial que l'algorithme de traitement d'images soit exécuté « en temps réel », c'est-à-dire que l'algorithme puisse traiter l'ensemble des images en respectant la période d'arrivée des images imposée par 5 la caméra. Par exemple, dans certains cas, une exécution en « temps réel » signifie l'algorithme traite chaque image avant l'arrivée d'une nouvelle image à traiter.. Il existe sur le marché plusieurs architectures de calcul et il est par conséquent utile de pouvoir identifier l'architecture de calcul la plus adaptée à la 10 mise en oeuvre de l'algorithme de traitement d'images. En outre, les architectures de calcul comportant chacune une pluralité de processeurs, il est intéressant de répartir au mieux les différentes opérations de l'algorithme sur ces processeurs, c'est-à-dire d'optimiser le mode de répartition de l'algorithme sur l'architecture de calcul, de sorte que l'algorithme soit exécuté « en temps réel ». 15 A ce jour, il est connu de répartir les opérations de l'algorithme de traitement d'images entre plusieurs processeurs de l'architecture de calcul, de sorte que ces opérations soient effectuées en parallèle les unes des autres, c'est-à-dire simultanément mais sur différents processeurs. Cependant, ce type de répartition nécessite des processeurs particulièrement puissants. 20 Il est également connu de tenter de répartir d'autres manières les opérations entre les différents processeurs, mais il est alors indispensable de s'assurer, par expérience sur banc d'essai, que l'algorithme est bien réalisé « en temps réel ». Cela implique que pour chaque modification de la répartition, pour chaque modification de l'algorithme, et pour chaque nouvelle architecture de 25 calcul, il faut recommencer les expériences sur banc d'essai, ce qui est long et fastidieux. Il est enfin connu d'estimer le temps d'exécution de l'algorithme par l'architecture de calcul. Pour ce faire, il est possible de mettre au point des simulateurs, ou de faire des modélisations analytiques reposant sur un ensemble 30 d'équations représentatives à la fois de l'architecture de calcul utilisé et de l'algorithme mis en oeuvre. Cependant, les simulateurs comme les modélisations analytiques sont spécifiques de chaque algorithme et de chaque architecture de calcul utilisée, ce qui est contraignant lorsqu'un constructeur veut implémenter un autre algorithme sur l'architecture de calcul, et/ou lorsqu'il souhaite l'implémenter 3063358 3 sur une autre architecture de calcul. En outre, la fiabilité des modélisations analytiques reste limitée, notamment parce que le temps d'exécution de chaque élément de code par chaque processeur de l'architecture de calcul n'est pas connu avec une parfaite précision, et parce que sa valeur peut fluctuer autour 5 d'une valeur moyenne. OBJET DE L'INVENTION Afin de remédier à l'inconvénient précité de l'état de la technique, la présente invention propose un procédé d'estimation d'un temps d'exécution d'une partie de code d'un algorithme, qui soit fiable quels que soient l'algorithme et 10 l'architecture de calcul utilisés. Plus particulièrement, on propose selon l'invention un procédé d'estimation du type précité, selon lequel à l'étape a) et/ou à l'étape b) chacun desdits temps globaux de calcul et/ou d'accès à la mémoire est déterminé sous la forme d'un intervalle de valeurs possibles. 15 Ainsi, le procédé selon l'invention garantit que les temps globaux de calcul et d'accès à la mémoire appartiennent à des intervalles donnés, ce qui permet d'obtenir un résultat très fiable. Selon une caractéristique avantageuse de l'invention, à l'étape c), le temps d'exécution est estimé sous la forme d'un intervalle de valeurs possibles 20 dont les bornes sont déterminées en fonction des bornes des intervalles de valeurs du temps global de calcul et du temps global d'accès à la mémoire. Ainsi, le procédé selon l'invention permet aussi de garantir que le temps d'exécution appartienne à un intervalle donné. A partir du temps d'exécution déterminé sous forme d'un intervalle, il est possible de déterminer de manière 25 fiable la performance temporelle globale d'une architecture de calcul comprenant le processeur, à mettre en oeuvre l'algorithme dans son ensemble. D'autres caractéristiques non limitatives et avantageuses du procédé conforme à l'invention sont les suivantes : - postérieurement à la mise en oeuvre des deux étapes a) et b), il est 30 prévu une étape de comparaison du temps global de calcul et du temps global d'accès à la mémoire, et l'estimation du temps d'exécution à l'étape c) dépend de ladite comparaison entre le temps global de calcul et le temps global d'accès à la mémoire ; - à l'étape c), le temps d'exécution est estimé sous la forme d'un 3063358 4 intervalle de valeurs possibles dont les bornes sont déterminées en fonction des bornes des intervalles de valeurs du temps global de calcul et/ou du temps global d'accès à la mémoire ; - lorsque l'étape a) est exécutée, la borne inférieure de l'intervalle 5 formant le temps global de calcul est déterminée comme étant égale au plus grand desdits temps individuels de calcul, et la borne supérieure dudit intervalle formant le temps global de calcul est déterminée comme étant égale à la somme desdits temps individuels de calcul ; - chacune desdites unités élémentaires de calcul étant adaptée à 10 exécuter une catégorie d'opérations de calcul, à l'étape a), le temps individuel de calcul d'une unité élémentaire de calcul est déterminé en fonction, d'une part, du nombre d'opérations de calcul, dans ladite partie de code, appartenant à la catégorie d'opérations associée à ladite unité élémentaire de calcul et, d'autre part, d'une cadence de traitement de ladite unité élémentaire de calcul ; 15 - la cadence de traitement de chaque unité élémentaire de calcul du processeur, associé à un type particulier de donnée, est déterminée en fonction d'une cadence de traitement de base prédéterminée sur banc d'essai ; - ledit processeur étant en outre associé à un compilateur adapté à optimiser l'exécution de ladite partie de code par le processeur, la cadence de 20 traitement de chaque unité élémentaire de calcul du processeur et/ou le nombre d'opérations à traiter par chacune desdites unités élémentaires de calcul sont déterminés en fonction d'un coefficient d'optimisation dudit compilateur ; - lorsque l'étape b) est exécutée, la borne inférieure de l'intervalle formant le temps global d'accès à la mémoire est déterminée comme étant égale 25 à un temps total de lecture qui dépend d'au moins un temps élémentaire de lecture associé à l'unité de mémoire du processeur, et la borne supérieure dudit intervalle formant le temps global d'accès à la mémoire est déterminée comme étant égale à la somme dudit temps total de lecture et d'un temps total d'écriture qui dépend d'au moins un temps élémentaire d'écriture associé à ladite unité de 30 mémoire ; - les temps élémentaires de lecture et d'écriture de l'unité de mémoire du processeur sont prédéterminés sur banc d'essai, pour chaque type et quantité de données ; - ledit processeur étant adapté à exécuter au moins une autre partie de 3063358 5 code dudit algorithme, la cadence de traitement de chaque unité élémentaire de calcul et/ou les temps élémentaires de lecture et d'écriture de l'unité de mémoire sont déterminés en fonction d'un paramètre dont la valeur varie selon que les parties de code sont exécutées simultanément ou successivement ; 5 - ledit processeur comportant au moins deux coeurs de processeur, chaque coeur comportant une pluralité d'unités élémentaires de calcul et/ou une unité de mémoire propre, et un desdits coeurs du processeur étant adapté à exécuter la partie de code successivement ou au moins en partie simultanément avec l'exécution d'une autre partie de code par l'autre coeur du processeur, la 10 cadence de traitement de chaque unité élémentaire de calcul et/ou les temps élémentaires de lecture et d'écriture de chaque unité de mémoire du processeur sont déterminés en fonction d'un paramètre dont la valeur varie selon que lesdites parties de code sont exécutées simultanément ou successivement par lesdits coeurs du processeur. 15 DESCRIPTION DETAILLEE D'UN EXEMPLE DE REALISATION La description qui va suivre en regard des dessins annexés, donnés à titre d'exemples non limitatifs, fera bien comprendre en quoi consiste l'invention et comment elle peut être réalisée. Sur les dessins annexés : 20 - la figure 1 représente schématiquement une architecture de calcul ; - la figure 2 est un organigramme des étapes principales d'un procédé d'estimation selon l'invention. Dispositif Sur la figure 1, on a représenté schématiquement une architecture de 25 calcul 1 adaptée à mettre en oeuvre un algorithme, notamment un algorithme de traitement d'images pour un dispositif d'aide à la conduite embarqué dans un véhicule automobile. L'architecture de calcul 1 comprend plusieurs processeurs al, a2, ax, chacun adapté à opérer certaines opérations de l'algorithme. L'architecture de 30 calcul peut en outre comprendre une ou plusieurs mémoires électroniques adaptées à stocker et restituer des données numériques, et un ou plusieurs périphériques d'interface adaptés à communiquer avec d'autres éléments du dispositif d'aide à la conduite, tel qu'un dispositif de capture d'images et un dispositif de communication d'informations aux actionneurs et/ou au conducteur 3063358 6 du véhicule automobile. Telle que représentée sur la figure 1, l'architecture de calcul 1 comprend trois processeurs al, a2, a3 adaptés à exécuter des opérations portant sur des données numériques et un périphérique d'interface I. 5 L'architecture de calcul 1 est ici intégrée sur une puce électronique ; on parle alors de système sur puce (ou SoC, selon l'acronyme anglo-saxon de « System-on-Chip »). L'algorithme de traitement d'images mis en oeuvre par l'architecture de calcul 1 est formé d'une suite de processus élémentaires, qu'il est prévu de faire 10 exécuter en série, c'est-à-dire successivement, et/ou en parallèle, c'est-à-dire simultanément, par les différents processeurs ax de ladite architecture de calcul 1. Par exemple, un processus élémentaire peut correspondre à une correction de distorsion de l'image, à un calcul de gradient vertical ou horizontal, à un calcul de gradient d'orientation, ou encore à une classification d'éléments remarquables 15 présents dans l'image, par exemple sur la base de résultats obtenus précédemment. Chacun des processus élémentaires est représenté, c'est-à-dire codé, par une partie de code kl, k2, ' REVENDICATIONS1. Procédé d'estimation d'un temps d'exécution (At) d'une pluralité d'opérations constituant une partie de code (K) d'un algorithme, par une pluralité d'unités élémentaires de calcul (Cy) d'un processeur (ax) et/ou par une unité de mémoire (M) dudit processeur (ax), dans lequel il est prévu des étapes de : a) détermination d'un temps global de calcul (ta) associé au processeur (ax) en fonction d'un temps individuel de calcul (tc,a) associé à chacune des unités élémentaires de calcul (Cy) du processeur (ax), et/ou b) détermination d'un temps global d'accès à la mémoire (4) en fonction de la quantité de données contenue dans les opérations de ladite partie de code (k1), à lire et/ou à écrire par l'unité de mémoire (M), et c) estimation du temps d'exécution (At) en fonction dudit temps global de calcul (ta) et/ou dudit temps global d'accès à la mémoire (4), caractérisé en ce que, à l'étape a) et/ou à l'étape b) chacun desdits temps globaux de calcul (ta) et/ou d'accès à la mémoire (4) est déterminé sous la forme d'un intervalle de valeurs possibles. 2. Procédé d'estimation selon la revendication 1, selon lequel : - postérieurement à la mise en oeuvre des deux étapes a) et b), il est 20 prévu une étape de comparaison du temps global de calcul (ta) et du temps global d'accès à la mémoire (4), et - l'estimation du temps d'exécution (At) à l'étape c) dépend de ladite comparaison entre le temps global de calcul (ta) et le temps global d'accès à la mémoire (4). 25 3. Procédé d'estimation selon la revendication 1 ou 2, selon lequel, à l'étape c), le temps d'exécution (At) est estimé sous la forme d'un intervalle de valeurs possibles dont les bornes sont déterminées en fonction des bornes des intervalles de valeurs du temps global de calcul (ta) et/ou du temps global d'accès à la mémoire (4). 30 4. Procédé d'estimation selon l'une des revendications 1 à 3, selon lequel, lorsque l'étape a) est exécutée, la borne inférieure de l'intervalle formant le temps global de calcul (ta) est déterminée comme étant égale au plus grand desdits temps individuels de calcul (tc,a), et la borne supérieure dudit intervalle 3063358 formant le temps global de calcul (ta) est déterminée comme étant égale à la somme desdits temps individuels de calcul (tc,a). 5. Procédé d'estimation selon l'une des revendications 1 à 4, selon lequel, chacune desdites unités élémentaires de calcul (Cy) étant adaptée à 5 exécuter une catégorie d'opérations de calcul, à l'étape a), le temps individuel de calcul (tca) d'une unité élémentaire de calcul (Cy) est déterminé en fonction, d'une part, du nombre d'opérations de calcul (N0), dans ladite partie de code (k1), appartenant à la catégorie d'opérations associée à ladite unité élémentaire de calcul (Cy) et, d'autre part, d'une cadence de traitement (pc,a) de ladite unité 10 élémentaire de calcul (Cy). 6. Procédé d'estimation selon la revendication 5, selon lequel, la cadence de traitement (pc,a) de chaque unité élémentaire de calcul (Cy) du processeur (ax), associé à un type particulier de donnée (s), est déterminée en fonction d'une cadence de traitement de base prédéterminée sur banc d'essai. 15 7. Procédé d'estimation selon l'une des revendications 5 et 6, selon lequel, ledit processeur (ax) étant en outre associé à un compilateur (CO) adapté à optimiser l'exécution de ladite partie de code (K) par le processeur (ax), la cadence de traitement (pc,a) de chaque unité élémentaire de calcul (Cy) du processeur (ax) et/ou le nombre d'opérations de calcul (N0) à traiter par chacune desdites unités 20 élémentaires de calcul (Cy) sont déterminés en fonction d'un coefficient d'optimisation dudit compilateur (CO). 8. Procédé d'estimation selon l'une des revendications 1 à 7, selon lequel, lorsque l'étape b) est exécutée, la borne inférieure de l'intervalle formant le temps global d'accès à la mémoire (tm) est déterminée comme étant égale à un temps total de lecture (tL) qui dépend d'au moins un temps élémentaire de lecture associé à l'unité de mémoire (M) du processeur (ax), et la borne supérieure dudit intervalle formant le temps global d'accès à la mémoire (tm) est déterminée comme étant égale à la somme dudit temps total de lecture (tL) et d'un temps total d'écriture (tE) qui dépend d'au moins un temps élémentaire d'écriture associé à ladite unité de mémoire (M). 9. Procédé d'estimation selon la revendication 8, selon lequel les temps élémentaires de lecture et d'écriture de l'unité de mémoire (M) du processeur (ax) sont prédéterminés sur banc d'essai, pour chaque type et quantité de données. 10. Procédé d'estimation selon l'une des revendications 5 à 9, selon 3063358 21 lequel, ledit processeur (ax) étant adapté à exécuter au moins une autre partie de code (kj) dudit algorithme, la cadence de traitement (pc,a) de chaque unité élémentaire de calcul (Cy) et/ou les temps élémentaires de lecture et d'écriture de l'unité de mémoire (M) sont déterminés en fonction d'un paramètre dont la valeur 5 varie selon que les parties de code (ki, kj) sont exécutées simultanément ou successivement. 11. Procédé d'estimation selon l'une des revendications 5 à 10, selon lequel, ledit processeur (ax) comportant au moins deux coeurs (C)1,02) de processeur (ax), chaque coeur (01,02) comportant une pluralité d'unités 10 élémentaires de calcul (Cy) et/ou une unité de mémoire (M) propre, et un desdits coeurs (01,02) du processeur (ax) étant adapté à exécuter la partie de code (k1) successivement ou au moins en partie simultanément avec l'exécution d'une autre partie de code (1