Brevet FR3020230A1 — publié le 20151023

Domaine de l'invention La présente invention se rapporte à un procédé de sélec- tion d'une file d'attente parmi plusieurs files d'attente pour prélever un ou plusieurs segments de données dans la file d'attente sélectionnée pour l'émission par une interface de sortie. Etat de la technique On connaît des procédés de sélection de l'une de plu- sieurs files d'attente pour prélever un ou plusieurs segments de données dans la file d'attente sélectionnée. Exposé et avantages de l'invention La présente invention a pour objet un procédé du type défini ci-dessus caractérisé en ce qu' à l'aide d'un premier ordonnanceur, on sélectionne l'interface de sortie, à l'aide d'un second ordonnanceur, on sélectionne un nombre de files d'attente, à l'aide d'un troisième ordonnanceur, on sélectionne une file d'attente dans le nombre de files d'attente, et on transmet un ou plusieurs segments de données de la file d'attente sélectionnée vers l'interface de sortie. En d'autres termes, grâce à un premier, un second et un troisième ordonnanceurs, on sélectionne une file d'attente pour transmettre à l'interface de sortie un ou plusieurs segments de données de la file d'attente sélectionnée. Cet ordonnanceur à trois étapes ou trois ni- veaux permet de traiter les données de priorité maximale pour les- quelles on a une interface de sortie déterminée, comme étant des données de priorité maximale pour l'envoi. Grâce à cette opération d'ordonnancement à trois niveaux, le procédé peut être réalisé de manière simple sous la forme d'un circuit. Dessins La présente invention sera décrite ci-après de manière plus détaillée à l'aide d'un procédé de sélection d'une parmi plusieurs files d'attente pour le prélèvement de segments de données, représenté dans les dessins annexés dans lesquels : la figure 1 montre un schéma de communication, la figure 2 montre un procédé d'échéance à trois niveaux sous une forme schématique, et - la figure 3 montre un ordinogramme schématique. Description de modes de réalisation de l'invention La figure 1 montre un schéma de communication 2 selon lequel plusieurs files d'attente 4 (4a-4c) sont chargées de données. Pour les files d'attente 4, on a une seule unité de traitement 6. A cause de cette unique unité de traitement 6, il faut déterminer à l'aide de l'unité de sélection 8, l'ordre et la durée pendant laquelle les données sont ex- traites par l'unité de traitement 6 des différentes files d'attente 4. L'unité de traitement 6 est reliée à différentes interfaces de sortie 10a-10c auxquelles sont envoyées les données des files d'attente. La figure 2 montre un procédé d'ordonnancement à trois niveaux ou trois étapes selon une représentation schématique 12. Une première liste en anneau active, 14 qui peut également être appelée ca- lendrier circulaire actif, comporte une succession d'étapes de procédé prévues chaque fois pour une fenêtre de temps ; une étape de traitement est associée à chaque interface de sortie 10. La liste en anneau 14 est traitée par son enregistrement dans une fenêtre de temps selon la flèche 16. Après le traitement du dernier élément ou élément le plus bas de la liste en anneau 14, ici l'interface 10c, on revient au premier élément de la liste en anneau 14, ici l'interface 10a, pour recommencer. C'est ainsi que dans une fenêtre de temps, une interface de sortie 10 est associée à chaque liste en anneau 14. Dans le premier élément de la liste en anneau 14, on traite une file d'attente 4 pour l'interface de sor- tie 10a. Pour le second et le troisième enregistrement, on traite chaque fois une file d'attente 4 pour l'interface de sortie 10b. Pour le dernier enregistrement, on traite une file d'attente 4 pour l'interface de sortie 10c. On enlève seulement un ou plusieurs segments de don- nées dans la file d'attente 4 sélectionnée si dans la fenêtre de temps actuelle, l'interface de sortie 10 est prête à recevoir. Selon un autre mode de réalisation, on ne sélectionne une file d'attente que si dans la fenêtre de temps actuel, l'interface de sortie respective 10 choisie selon la liste en anneau actif 14 est prête à recevoir. En outre, à côté de la liste en anneau active 14, on a une liste en anneau passive 18 en arrière plan et qui est configurée au cours du traitement de la liste en anneau active 14. Après configuration, la liste en anneau passive 18, peut remplacer la liste en anneau active 14. La liste en anneau passive 18 tient compte des interfaces de sortie 10 qui s'ajoutent ou des interfaces de sortie 10 désactivées au cours du fonctionnement de l'unité de traitement 6. En outre, on peut tenir compte de la pondération pour le service des interfaces 10 de la liste en anneau passif 18. La gestion et le traitement des listes en anneau 14 et 18 se font à l'aide d'un premier ordonnanceur 20 qui sélectionne l'interface de sortie 10. A titre d'exemple, à l'aide du second enregistrement dans la liste en anneau 14, on associe à l'interface de sortie 10b un certain nombre de priorités 22a et 22b ; le nombre de deux priorités 22 ne constitue qu'un exemple. Le nombre de priorités et l'ordonnanceur des priorités concernant les priorités 22, garantissent que les données fortement prioritaires des files d'attente 4 sélectionnées se verront attribuer une priorité élevée 22 pour être traitées de manière préférentielle et être envoyées. Un second ordonnanceur 24, à partir de priorités fixes, effectue une mise à jour des priorités 22 et sélectionne ainsi un nombre de files d'attente 4. La priorité 22 est associée au nombre de files d'attente 4. Ainsi, la priorité 22a est associée à un premier nombre de files d'attente 4d-4i. La seconde priorité 22b est associée à un second nombre de files d'attente 4k et 4m. A titre d'exemple, à l'aide du premier nombre de files d'attente 4d-4i, on décrira le fonctionnement d'un troisième ordonnanceur 26. Le troisième ordonnanceur 26 comporte un registre FIFO Ready (registre FIFO prêt) 30 et un registre FIFO Wait (registre FIFO d'attente) 32. Pour appliquer le procédé Weighted Round Robin, à l'aide du troisième ordonnanceur 23, on attribue un poids à chacune des files d'attente 4d-4i et en fonction du traitement, on décrémente un compteur pour chaque étape de traitement de la file d'attente 4. Ce compteur, initialement à l'entrée de la file d'attente 4 dans le registre FIFO 30, est mis à la valeur du poids. Selon la flèche 34, on établit une nou- velle file d'attente 4 selon un premier mode de réalisation dans le registre FIFO 30 ; le compteur de la file d'attente 4 est fixé au produit du poids de la file d'attente 4 et du nombre de files d'attente 4 de la priorité 22, divisé par X. Selon une variante de réalisation, on met une nouvelle file d'attente 4 selon la flèche 36 dans le registre FIFO 32. A la sélection de la file d'attente 4, on sélectionne la première file d'attente 4g dans le registre FIFO Ready 30 pour le traitement. Si la file d'attente 4g est vide, c'est-à-dire si elle ne contient plus aucun segment de données, on enlève la file d'attente 4g selon la flèche 38 de l'ordonnanceur et on élimine la file d'attente 4g. Après une étape de traitement de la file d'attente 4g, c'est-à-dire après l'extraction d'un segment de données ou d'un bloc de données comportant plusieurs segments, on décrémente le compteur de la file d'attente 4g. Lorsque le compteur de la file d'attente 4g atteint la valeur zéro, selon la flèche 40, on met la file d'attente 4g à l'extrémité du registre FIFO 32 en attente, et on met le compteur de la file d'attente 4g à la valeur du poids de la Ofile d'attente 4g. Si après décrémentation du compteur de la file d'attente 4g, celui-ci est supérieur à zéro, alors selon la flèche 42, on applique la file d'attente 4g à l'extrémité du re- gistre FIFO 30. A la fin d'une étape de traitement de la file d'attente 4g, on met la file d'attente 4g au début du registre FIFO 30. On distingue entre un ordonnanceur rapporté à un seg- ment de données et un ordonnanceur rapporté à un bloc de données. Dans le cas de l'ordonnanceur rapporté à un segment de données, en fonction de l'interface de sortie 10, on extrait un segment de données de la file d'attente sélectionnée 4 avant de passer à une autre file d'attente 4. L'ordonnancement rapporté au segment de données est par exemple possible pour des interfaces de sortie à plusieurs registres tampons d'entrée et qui permettent de reclasser les segments de données reçus car dans le cas d'un ordonnancement rapporté à des segments de don- nées, les segments de données d'un bloc de données peuvent être dépassés de sorte que l'ordre initial des segments de données, par exemple dans un bloc de données, ne sera plus respecté. L'ordonnancement rapporté au bloc de données, est fon- dé sur un bloc de données a plusieurs segments de données de base. En fonction de l'interface de sortie 10, on prélève un bloc de données en entier de la file d'attente 4 sélectionnée avant de passer à une autre file d'attente 4. L'ordonnancement rapporté au bloc de données est par exemple nécessaire pour des interfaces de sortie qui, n'ont qu'un re- gistre tampon d'entrée pour le bloc de données, et dont les données re- çues ne peuvent être reclassées simplement car par l'ordonnancement rapporté aux segments de données des segments de données peuvent être sautés dans le bloc de données de sorte que l'ordre initial des segments de données dans le bloc de données ne sera plus respecté. Si le registre FIFO actif 30 ne comporte plus de files d'attente, alors on active le registre FIFO 32 et on neutralise le registre FIFO 30 ; le registre FIFO 32 est traité exactement comme le registre FIFO 30 décrit ci-dessus. Le premier ordonnanceur 20 lance l'organisation chrono- logique du second et du troisième ordonnanceur 24, 26 si dans la fe- nêtre de temps établie par l'ordonnanceur 20, l'interface de sortie 10 n'est plus prête à recevoir des données. En particulier, des données pourraient être perdues, si le procédé ou le système sont réalisés sous la forme de circuit Pipeline et si le second et le troisième ordonnanceur 24, 26 ainsi que d'autres unités de traitement en direction de l'interface de sortie, ont déjà traité ou traitent des données pour les interfaces de données 10, respectives, qui ne sont plus prêtes à la réception. De façon avantageuse, les mémoires intermédiaires sont des interfaces d'entrée qui évitent la perte de segments de données à cause d'une interface de sortie 10 qui n'était pas prête à recevoir. La perte de données est signa- lée à l'interface d'entrée respective pour que les données puissent de nouveau être mises dans la file d'attente 4. La figure 3 montre schématiquement trois procédés se déroulant en parallèle dans une fenêtre de temps 60. Un premier procé- dé 62 enregistre les nouvelles données arrivées dans la file d'attente 4 et vérifie si la file d'attente correspondante a déjà un ordonnanceur 26. Si la file d'attente 4 qui comporte de nouvelles données n'a pas encore reçu l'attribution d'un troisième ordonnanceur 26, elle est enregistrée dans le registre FIFO 30 ou 32 selon la flèche 34 ou la flèche 36 de la figure 2. Un second procédé 64 vérifie si l'interface de sortie 10 correspondante, à traiter dans la fenêtre de temps actuelle a déjà un troisième ordonnanceur 26. Si l'interface de sortie respective 10 n'est pas encore attribuée à un ordonnanceur 26, le procédé 64 continue dans sa liste passive 18 au moins jusqu'à l'enregistrement de l'interface de sortie 10 respective. Si en revanche, un troisième ordonnanceur 26 est déjà activé pour l'interface de sortie respective, alors le troisième ordonnanceur 26 sélectionne pour passer à la file d'attente suivante 4. Le second procédé 64 active le registre FIFO 32 dès que le registre FIFO 30 ne comporte plus de file d'attente 4. Le troisième procédé 66 exécute les étapes selon les flèches 38, 40, 42. Dans le cas d'un ordonnanceur attribué à un bloc de données, le troisième procédé 66 sélectionne seulement une autre file d'attente après réception du dernier segment de données d'un bloc de données provenant de la file d'attente. Le premier procédé 62 marque une file d'attente, comme n'étant pas vide, seulement lorsque le dernier segment de données d'un bloc de données s'est rangé dans la file d'attente puis la file d'attente est attribuée à un ordonnanceur 26.20 NOMENCLATURE DES ELEMENTS PRINCIPAUX 2 Schéma de communication 4 File d'attente 4a-4i Files d'attente 6 Unité de traitement 8 Unité de sélection Interface de sortie 10a,b,c Interfaces 10 12 Vue schématique 14 Liste en anneau active 16 Flèche 18 Liste en anneau passive 20 Premier ordonnanceur 22 Priorité maximale 22a,b Priorités 24 Second ordonnanceur 26 Troisième ordonnanceur 30 Registre FIFO 32 Registre FIFO 34 Flèche 40 Flèche 60 Fenêtre de temps 62 Premier procédé 64 Deuxième procédé REVENDICATIONS1°) Procédé de sélection d'une file d'attente parmi plusieurs files d'attente (4) pour prélever un ou plusieurs segments de données dans la file d'attente (4) sélectionnée pour l'émission par une interface de sortie (10), procédé caractérisé en ce qu' - à l'aide d'un premier ordonnanceur (20), on sélectionne l'interface de sortie (10), à l'aide d'un second ordonnanceur (24), on sélectionne un nombre de files d'attente (4), à l'aide d'un troisième ordonnanceur (26), on sélectionne une file d'attente (4) dans le nombre de files d'attente (4), et on transmet un ou plusieurs segments de données de la file d'attente sélectionnée (4) vers l'interface de sortie (10). 2°) Procédé selon la revendication 1, caractérisé en ce que le premier ordonnanceur a une liste en anneau, active (14), comportant un ou plusieurs enregistrements pour une interface de sor- tie (10), et un ou plusieurs segments de données ne sont extraits de la file d'attente sélectionnée (4) que lorsque dans une fenêtre de temps actuelle (60), l'interface de sortie (10) est prête à recevoir. 3°) Procédé selon la revendication 2, caractérisé en ce que le premier ordonnanceur (20) comporte une liste en anneau passive (18), qui est configurée pendant le traitement de la liste en anneau active, et la liste en anneau passive (18) remplace la liste en anneau active (14) lorsque la configuration de la liste en anneau passive (18) est terminée. 4°) Procédé selon la revendication 1, caractérisé en ce qu'une priorité fixe (22) est attribuée pour le second ordonnanceur (24) à chacune des files d'attente (4), et le second ordonnanceur (20) effectue un échelonnement selon la priorité. 5°) Procédé selon la revendication 4, caractérisé en ce que le second ordonnanceur (20) sélectionne l'une des files d'attente (4) si au moins l'une des files d'attente (4) contient des segments de données à traiter. 6°) Procédé selon la revendication 1, caractérisé en ce que le troisième ordonnanceur (26) sélectionne selon le procédé Weighted Round Robin, l'une des files d'attente (4) dans le nombre de files d'attente (4). 7°) Procédé selon la revendication 1, caractérisé en ce qu' en fonction de l'interface de sortie (10), avant un changement de file d'attente (4), on extrait un segment de données de la file d'attente (4). 8°) Procédé selon la revendication 1, caractérisé en ce qu' en fonction de l'interface de sortie (10), avant le changement de la file d'attente (4), on prélève un bloc de données comportant plusieurs segments de données dans la file d'attente (4) sélectionnée. 9°) Circuit intégré pour la mise en oeuvre du procédé selon l'une quel- conque des revendications 1 à 8.