Brevet FR2845177A1 — publié le 20040402

t -, Cette invention concerne d'une manière générale les systèmes informatiques. Il est courant dans les systèmes informatiques d'avoir de multiples dispositifs ou processus logiciels partageant une ressource, comme un bus, un port d'entréesortie, une mémoire, ou un périphérique. Il y a de nombreux procédés pour contrôler 5 l'accès, ou d'arbitrage pour l'accès, à une ressource partagée. Par exemple, l'accès peut être accordé dans l'ordre temporel de demande (premier entré, premier sorti), ou un schéma "à tour de rôle " peut être utilisé pour appeler séquentiellement chaque utilisateur potentiel. En variante, certains dispositifs ou procédés peuvent se voir attribuer des priorités relatives, de sorte que les demandes ne sont pas accordées dans 10 l'ordre. Si des priorités sont fixées, il est possible qu'un dispositif ou un procédé à faible priorité soit forcé d'être " suspendu " ou de patienter. Il existe des procédés pour changer les priorités afin de s'assurer que chaque dispositif ou procédé finisse par avoir un accès. Par exemple, un algorithme d'ancienneté peut être utilisé dans lequel un arbitre accorde la demande qui a été accordée le moins récemment. 15 Certaines demandes peuvent être par nature plus urgentes que d'autres, et certaines demandes peuvent nécessiter un temps de réponse minimum garanti. Il y a un besoin continuel d'algorithmes améliorés pour accorder l'accès à une ressource partagée. Lorsqu'une demande d'accès à une ressource partagée est refusée, un compteur est initialisé. Chaque transaction subséquente pour la ressource partagée est 20 comptée. Lorsque le compteur atteint un seuil, la priorité de la demande d'accès est augmentée. Le seuil peut être programmable. Les demandes peuvent être triées en files d'attente, chaque file d'attente ayant un seuil programmable séparément. De multiples demandes d'une file d'attente peuvent ensuite être accordées sans interruption. Dans exemple de mode de réalisation, une mémoire cache a de 25 multiples files d'attente, et chaque file d'attente a un compteur associé avec un seuil programmable. La figure l est un schéma de principe d'un exemple de système informatique. La figure 2 est un organigramme d'un exemple de procédé utilisé avec le système de la figure l. La figure 3 est un schéma de principe d'un exemple de système informatique avec une mémoire cache. La figure 4 est un diagramme d'état pour l'exemple de système de la figure 3. La figure 1 illustre un système dans lequel deux agents (100, 102) partagent une ressource 112. Un agent correspond à tout ce qui peut demander l'accès à la ressource 112, y compris par exemple, les processeurs d'ordinateur, les contrôleurs de mémoire, les contrôleurs de bus, les périphériques, et les processus logiciels. La 5 ressource partagée peut être, par exemple, une mémoire, un bus, un port d'entrée/sortie, ou un périphérique. En général, une ressource partagée peut ne pas être en mesure de répondre à toutes les demandes d'accès en temps réel, et par conséquent des files d'attente (104, 106) peuvent être utilisées optionnellement pour stocker des demandes d'accès en attente. Chaque demande d'accès (à la sortie d'une 10 file d'attente, s'il y a des files d'attente) a une priorité associée. Lorsqu'il y a de multiples demandes d'accès simultanées, la demande ayant la priorité la plus haute se voit accorder l'accès. En cas de priorité égale, divers algorithmes peuvent être utilisés pour déterminer quelle demande est accordée, par exemple, de permutation circulaire ou d'ancienneté. Le système comprend au moins un compteur, représenté 15 dans l'exemple de la figure 1 comme compteurs 108 et 110 associés aux files d'attente 104 et 106. Les compteurs peuvent être situés dans les files d'attente ou autre part, et peuvent être implémentés dans le logiciel, dans un processeur, ou en tant que champs dans un registre, o les champs peuvent être incrémentés ou décrémentés et initialisés individuellement. La figure 2 illustre un exemple de procédé utilisé avec le système de la figure 1. A la référence 200, il y a une demande d'accès à la ressource partagée. S'il y a une file d'attente, la demande d'accès représentée par la référence 200 est à la sortie de la file d'attente. A savoir, la demande est celle qui est présentée à la ressource partagée, pas une demande qui est en attente dans la file d'attente. A la référence 202, si la 25 demande est refusée, un compteur est initialisé. Le terme initialisé comprend "réinitialisé" ou "préréglé"; à savoir, le compteur peut démarrer à zéro et effectuer un comptage progressif ou régressif jusqu'à un seuil, ou peut démarrer à un autre nombre et effectuer un comptage progressif ou régressif jusqu'à un seuil. Le seuil du compteur peut, optionnellement, être programmable. Pour chaque 30 transaction subséquente (référence 206), le compteur progresse (est incrémenté ou décrémenté en fonction de l'implémentation, et la progression n'est pas limitée à un) (référence 208). Lorsque le compteur atteint un seuil prédéterminé (référence 210), la priorité est augmentée pour la demande d'accès en attente de la référence 200. Par exemple, dans le système de la figure 1, supposons que des demandes de l'agent 102 ont à l'origine une priorité supérieure aux demandes de l'agent 100, et supposons que pour l'agent 100, le comptage de seuil est quatre. Si une demande d'accès par l'agent 5 100 est refusée en raison de demandes en attente de l'agent 102, le système permettra jusqu'à quatre transactions par la ressource partagée (par exemple, quatre accès par l'agent 102) avant d'accroître la priorité de l'agent 100. Les figures 3 et 4 illustrent un exemple de système spécifique dans lequel de multiples processeurs partagent un cache. Sur la figure 3, deux processeurs 300 et 10 302, avec des mémoires caches de premier niveau (LI) , partagent une mémoire cache de second niveau (L2) 304. Il peut y avoir plus de deux processeurs, et il peut y avoir plus de deux niveaux de cache. La figure 3 peut représenter un noeud à l'intérieur d'un système plus important, et il peut y avoir de multiples noeuds, chacun avec de multiples processeurs, et chacun avec un cache L2. Tous les processeurs et 15 les caches peuvent partager une mémoire principale commune (non représentée). A l'intérieur du cache L2 (304), il y a des files d'attente de demandes (306, 308, 310, et 312) d'accès à la mémoire vive (RAM) cache 326. Une file d'attente de lecture 306 contient les demandes de lecture dans la RAM cache 326, pour fournir des données aux processeurs 300 et 302, en cas d'absence d'informations dans le cache LI et de 20 présence d'informations dans le cache L2. Une file d'attente d'écriture 308 contient les demandes d'écriture dans la RAM cache 326 d'un des processeurs (300, 302) ou d'un bus système (non représenté). Si de nouvelles données doivent être écrites dans la RAM cache, et qu'il n'y a pas d'espace vide, une entrée existante dans la RAM cache doit être expulsée. Une file d'attente d'expulsion 310 contient les données qui 25 sont expulsées de la RAM cache 326, qui seront écrites ultérieurement dans la RAM système principale (non représentée). Des copies d'un élément de données particulier peuvent exister simultanément dans la mémoire principale et dans les hiérarchies de cache pour de multiples processeurs. Si la copie d'un élément de données dans un cache est différente de la copie présente dans la mémoire principale, l'élément de 30 données dans le cache est dit " sale ". Sur la figure 3, une file d'attente de cohérence 312 contient les demandes, d'agents distants (par exemple, d'autres noeuds), pour les éléments de données dans la RAM cache 326 qui sont sales. Un contrôleur de files d'attente 314 détermine quelle demande de quelle file d'attente se voit accorder l'accès à la RAM cache 326. Chaque file d'attente a un compteur associé (316, 318, 320, 322) (ou registre, ou champ dans un registre), qui sera présenté de manière plus détaillée ci-dessous. La figure 4 illustre un diagramme d'état implémenté par le contrôleur de files d'attente de la figure 3. Il y a sept états, Inactif, Lecture, Lecture-Attente, Ecriture, Ecriture-Attente, Cohérence, et Expulsion. Les petits cercles avec des numéros indiquent la priorité, " 1 " étant la plus haute priorité, et " 8 " étant la plus basse priorité. Par exemple, dans l'état Inactif, une demande de cohérence urgente a la plus 10 haute priorité. Pour lire ou écrire dans la RAM cache 326, une adresse est transférée, et ensuite un temps additionnel est nécessaire pour achever le transfert de données. Les données sont lues pendant l'état Lecture-Attente, et les données sont écrites pendant l'état Ecriture-Attente. Pour chacun des quatre états illustrés au-dessus de l'état Inactif sur la figure 4, le bus 324 de la RAM cache 326 est commuté dans une 15 direction pour la lecture dans la RAM cache. Dans les états Cohérence, Lecture, et Expulsion, une adresse est transférée est certaines données sont lues, et la partie restante des données correspondant à l'adresse est lue pendant l'état Lecture-Attente. Pour chacun des deux états sous l'état Inactif sur la figure 4, le bus 324 de la RAM cache 326 est commuté dans une direction pour l'Ecriture. Une adresse est 20 transférée, et certaines données sont écrites, pendant l'état Ecriture, et la partie restante des données correspondant à l'adresse est écrite pendant l'état EcritureAttente. Quelques cycles d'horloge sont nécessaires pour commuter un bus mémoire de la lecture à l'écriture, et de l'écriture à la lecture, et donc, le fait de regrouper les transactions qui concernent la lecture dans la mémoire (par exemple, les lectures 25 d'une mémoire cache à un processeur, les transactions de cohérence, et les transactions d'expulsion), et de regrouper les écritures dans la mémoire, peut améliorer les performances en réduisant le nombre de fois qu'un bus doit être commuté de la lecture à l'écriture. Une écriture d'un processeur à la mémoire peut généralement être retardée sans affecter les performances, mais tout retard dans 30 l'exécution d'une lecture de la mémoire à un processeur, ou tout retard dans l'exécution d'une transaction de cohérence, peut diminuer les performances. Dans la discussion suivante, un protocole de priorité d'accès, comme décrit conjointement avec les figures 1 et 2, est implémenté dans l'exemple de système des figures 3 et 4 pour améliorer les performances. En particulier, les transactions concernant la lecture dans la mémoire sont regroupées, et les écritures dans la mémoire sont regroupées, et les transactions concernant la lecture dans la mémoire se voient donner la priorité par rapport aux écritures dans la mémoire. Sur la figure 3, lorsque chaque file d'attente (306, 308, 310, et 312) fournit pour la première fois une demande d'accès à la RAM cache, la demande a une priorité normale. Il convient de noter que sur la figure 4 les demandes de cohérence normales ont une priorité de 5, les demandes de lecture normales ont une priorité de 10 6, les demandes d'expulsion normales ont une priorité de 7. Les demandes d'écriture normales (à l'état Inactif) ont une priorité de 8 (la priorité des demandes d'écriture normales dépend de l'état). Sur la figure 3, chaque file d'attente a un compteur (316, 318, 320, 322), par micrologiciel, utilisé pour contrôler le nombre de transactions de RAM cache qui peuvent avoir lieu avant que la demande d'accès de la file d'attente 15 soit changée en priorité urgente. Il convient de noter sur la figure 4 que les demandes de cohérence urgentes ont une priorité de 1, les demandes de lecture urgentes ont une priorité de 2, les demandes d'expulsion urgentes ont une priorité de 3, et les demandes d'écriture urgentes ont une priorité de 4. Prenons un exemple spécifique avec des seuils de comptage maximum 20 supposés. Supposons que la file d'attente de Lecture et la file d'attente de Cohérence ont chacune des compteurs à deux bits (ou des champs à deux bits dans un registre), et que la file d'attente d'Ecriture et la file d'attente d'Expulsion ont chacune des compteurs à cinq bits (ou des champs à cinq bits dans un registre). Par conséquent, les files d'attente de Lecture et de Cohérence peuvent permettre que zéro à trois 25 transactions de RAM cache aient lieu avant d'affirmer une demande urgente. Les files d'attente d'Ecriture et d'Expulsion peuvent permettre que zéro à 31 transactions de RAM cache aient lieu avant d'affirmer une demande urgente. Par exemple, un groupe de 31 demandes de lecture peuvent être accordées avant qu'une demande d'écriture soit accordée, et une fois que la demande d'écriture et accordée, trois 30 demandes d'écriture peuvent être accordées avant qu'un autre groupe de demandes de lecture soit accordé. Ce regroupement de lectures et d'écritures améliore les performances en réduisant le nombre de fois que le bus mémoire 324 doit passer de la lecture à l'écriture ou de l'écriture à la lecture. Sur la figure 4, il convient de noter par exemple, à l'état LectureAttente, qu'une demande d'écriture normale n'interrompra jamais une série de lectures, mais 5 une demande d'écriture urgente (priorité 4) aura la priorité sur une demande de lecture normale (priorité 6). Il convient de noter aussi que le fait de changer une priorité sur urgent ne garantit pas l'accès. Par exemple, à l'état Lecture-Attente, une demande de cohérence urgente (priorité 1), une demande de lecture urgente (priorité 2), et une demande d'expulsion urgente (priorité 3), ont toutes une priorité plus haute 10 qu'une demande d'écriture urgente (priorité 4). Par conséquent, le système de priorité facilite les groupes de transactions qui concernent la lecture depuis la mémoire, et facilite les groupes d'écritures dans la mémoire, mais assure toujours l'interruption par des demandes d'accès de haute priorité. La description précédente de la présente invention a été présentée à des fins 1 5 d'illustration et de description. Elle n'a pas pour objet d'être exhaustive ou de limiter l'invention à la forme précise décrite, et d'autres modifications et variations peuvent être possibles à la lumière des enseignements précités. Le mode de réalisation a été choisi et décrit de manière à expliquer au mieux les principes de l'invention et son application pratique, pour ainsi permettre à d'autres hommes du métier d'utiliser au 20 mieux l'invention dans divers modes de réalisation et diverses modifications appropriées à l'utilisation particulière envisagée. Il est prévu que les revendications annexées soient interprétées pour inclure d'autres modes de réalisation alternatifs de l'invention dans la mesure o ils ne sortent pas du cadre de l'art antérieur. REVENDICATIONS 1. Système informatique, comprenant: une ressource partagée (112); et un compteur (108, 110), le compteur déterminant un nombre maximum de transactions qui peuvent avoir lieu pour la ressource partagée avant qu'une priorité pour une demande d'accès particulière soit rendue supérieure. 2. Système informatique selon la revendication 1 o le nombre maximum de transactions est programmable. 3. Système informatique selon la revendication 1 o la ressource partagée est un cache (326). 4. Système informatique selon la revendication 1, comprenant en outre: une pluralité de files d'attente (306, 308, 310, 312), chaque file d'attente étant capable de contenir une pluralité de demandes d'accès à la ressource 15 partagée; et chaque file d'attente ayant un compteur associé (316, 318, 320, 322), o pour chaque file d'attente, le compteur associé détermine un nombre maximum de transactions qui peuvent avoir lieu pour la ressource partagée avant qu'une priorité pour une demande d'accès, à la sortie de la file d'attente, soit rendue supérieure. 20 5. Procédé, consistant à: demander (200), par un agent, l'accès à une ressource qui est partagée, la demande ayant une priorité; compter (208) les transactions par la ressource; et augmenter (212) la priorité de la demande par l'agent, lorsque les 25 transactions par la ressource sont égales à un seuil prédéterminé. 6. Procédé selon la revendication 5, consistant en outre à: stocker les demande d'accès en attente par l'agent dans une file d'attente.