PROCEDE DE GESTION DE REQUETES D'ACCES A DES MEMOIRES ET SYSTEME DE STOCKAGE DE DONNEES

La présente invention concerne un procédé de gestion de requêtes d'accès à des mémoires et un système de stockage de données.

Il existe des processeurs travaillant sur plusieurs données en parallèle, comme par exemple les processeurs de signaux numériques (« Digital Signal Processor » ou DSP en anglais), les processeurs à une seule instruction sur des données multiples (« Single Instructions on Multiple Data » ou SIMD en anglais), les processeurs à instructions longues (« Long Instruction Word » ou LIW en anglais), ou les processeurs vectoriels, c'est-à- dire conçus pour effectuer des opérations sur plusieurs nombres (représentant des vecteurs ou des matrices) pendant un unique cycle d'horloge.

De tels processeurs ont besoin de pouvoir lire et écrire un ensemble de données au même moment le plus rapidement possible.

Ces données peuvent être stockées dans différentes mémoires qui doivent être utilisées au mieux afin de bénéficier d'un maximum d'accès haut débit.

Il est ainsi connu d'utiliser un système de stockage destiné à être cadencé par un signal d'horloge et comportant plusieurs mémoires.

Chaque mémoire comporte un certain nombre de ports d'entrée et de sortie. Chaque port d'entrée est destiné à recevoir une requête d'accès à l'un des emplacements de la mémoire, repéré par son adresse, appelée adresse locale, dans la mémoire. La mémoire est destiné à recevoir des requêtes locales à chaque cycle d'horloge et à y répondre en un nombre prédéterminé de cycles d'horloge. La mémoire est en outre destinée à présenter, à la fin de ce ou ces cycles d'horloge, les réponses éventuelles sur ses ports de sortie. Ainsi, une mémoire ne peut recevoir par cycle d'horloge qu'un nombre de requêtes locales limité, au plus égal au nombre de ports d'entrée de cette mémoire. Un type de mémoire classique est par exemple une mémoire à accès direct (appelée « Random Access Memory » ou RAM en anglais) simple port (un port d'entrée et un port de sortie associé) ou double ports (deux ports d'entrée et deux ports de sortie associés).

Le système de stockage comporte par ailleurs des ports d'entrée et un ou plusieurs ports de sortie. Chaque port d'entrée est destiné à recevoir, à chaque cycle d'horloge, une requête d'accès à un emplacement de l'une des mémoires. Cette requête indique une adresse globale structurée comme si le système de stockage constituait une seule mémoire. Il est ainsi connu d'utiliser une fonction de correspondance qui associe chaque adresse globale à une des mémoires et à une adresse locale dans cette mémoire.

Il est possible qu'au cours d'un même cycle d'horloge, le système de stockage reçoive sur ses ports d'entrée un nombre de requêtes d'accès vers la même mémoire supérieur à ce que cette mémoire peut recevoir sur ses ports d'entrée. Il y a donc un conflit car la mémoire ne pourra pas recevoir toutes ces requêtes dans un même cycle d'horloge.

Il est donc nécessaire de mettre en œuvre un procédé de gestion des requêtes efficaces pour diminuer la fréquence des conflits.

Il existe plusieurs publications décrivant des procédés de gestion de requêtes d'accès à des mémoires, parmi lesquelles :

- la thèse de Eero Aho intitulée « Design and Implementation of Parallel Memory Architectures », et publiée en 2006 dans Tampere University of Technology, Publication 641 ,

- l'article de Kimmo Kuusilinna et al. intitulé « Configurable parallel memory architecture for multimédia computers », et publié en 2002 dans

Journal of Systems Architecture 47 (2002) 1089-1115, et

- l'article de Dionysios Reisis et al. intitulé « Conflict-Free Parallel Memory Accessing Techniques for FFT Architectures », et publié en 2008 dans IEEE Transactions on circuits and Systems,! - Regular papers, vol. 55, n ° 11 , décembre 2008.

Ces procédés proposent tous d'optimiser la fonction de correspondance en fonction de la répartition prévisible des accès aux mémoires. Ces procédés de gestion de requêtes présentent comme problème de ne pas être très efficaces pour les applications les plus complexes, telles que les transformées de Fourier rapides (« Fast Fourier Transform » ou FFT en anglais) avec un radix changeant dans le temps en fonction de la taille des vecteurs sur lesquels la FFT est calculée, ou bien les applications où les accès se font à des emplacements aléatoires ou presque aléatoires. Ainsi, les accès aux mémoires sont difficilement prévisibles de sorte qu'il n'est pas possible d'optimiser la fonction de correspondance.

Ainsi, il peut être souhaité de disposer d'un procédé de gestion de requêtes permettant de diminuer la fréquence des conflits même dans le cas d'applications où les accès aux mémoires sont difficilement prévisibles.

A cet effet, il est proposé un procédé de gestion de requêtes reçues par un système de stockage comportant des mémoires, une entrée destinée à recevoir un signal d'horloge définissant des cycles d'horloge successifs, et un étage de traitement, le système de stockage étant destiné recevoir des requêtes requérant chacune un accès à un emplacement de l'une des mémoires, le procédé comportant, à un premier cycle d'horloge : - l'obtention de nouvelles requêtes par l'étage de traitement ; - la fourniture par l'étage de traitement d'au moins une des nouvelles requêtes ; - la mise en attente par l'étage de traitement d'au moins une autre des nouvelles requêtes, appelée par la suite requête en attente ;

le procédé étant caractérisé en ce qu'il comporte, à un second cycle d'horloge succédant au premier cycle d'horloge : - l'obtention par l'étage de traitement d'au moins une nouvelle requête ; - la sélection par l'étage de traitement, parmi la ou les requêtes en attente et la ou les nouvelles requêtes, d'au moins une requête ; - la fourniture par l'étage de traitement de la ou des requêtes sélectionnées.

De façon optionnelle, les requêtes sont fournies par l'étage de traitement à un étage de traitement suivant dans le système de stockage.

De façon optionnelle, l'étage de traitement suivant comporte les mémoires.

De façon optionnelle, la sélection par l'étage de traitement d'au moins une requête comporte la sélection d'une requête en attente. De façon optionnelle, la sélection par l'étage de traitement d'au moins une requête comporte la sélection d'une nouvelle requête obtenue au second cycle d'horloge.

De façon optionnelle, le procédé comporte en outre : - la détermination de l'existence ou non d'une requête mise en attente à chacun des L cycles d'horloge précédant le cycle d'horloge en cours, L étant un nombre prédéterminé supérieur ou égal à deux, une telle requête étant appelée requête prioritaire ; et l'obtention par l'étage de traitement d'au moins une nouvelle requête est réalisée lorsque l'existence d'aucune requête prioritaire est déterminée.

De façon optionnelle, le procédé comporte en outre : - la détermination de l'existence ou non d'une requête mise en attente à chacun des L cycles d'horloge précédant le cycle d'horloge en cours, L étant un nombre prédéterminé supérieur ou égal à deux, une telle requête étant appelée requête prioritaire ; - lorsque l'existence d'au moins une requête prioritaire est déterminée, la suspension d'obtention de nouvelles requêtes par l'étage de traitement pour le cycle d'horloge en cours.

De façon optionnelle, pour au moins une mémoire, la sélection d'au moins une requête destinée à être fournie à cette mémoire est réalisée de manière à sélectionner le plus grand nombre possible de requêtes que la mémoire sera apte à recevoir au cycle d'horloge suivant.

De façon optionnelle, pour au moins une mémoire, la sélection d'au moins une requête destinée à être fournie à cette mémoire est réalisée en donnant la priorité aux requêtes mises en attente depuis le plus grand nombre de cycles d'horloge.

Il est également proposé un système de stockage de données comportant : - des mémoires, le système de stockage étant destiné recevoir des requêtes requérant chacune un accès à un emplacement de l'une des mémoires ; - une entrée destinée à recevoir un signal d'horloge définissant des cycles d'horloge successifs ; - un étage de traitement destiné, à un premier cycle d'horloge, à : - obtenir de nouvelles requêtes ; - fournir au moins une des nouvelles requêtes ; - mettre en attente au moins une autre des nouvelles requêtes, appelée par la suite requête en attente ; le système de stockage étant caractérisé en ce que l'étage de traitement est en outre destiné, à un second cycle d'horloge succédant au premier cycle d'horloge, à : - obtenir au moins une nouvelle requête ; - sélectionner, parmi la ou les requêtes en attente et la ou les nouvelles requêtes, au moins une requête destinée à être fournie ; - fournir la ou les requêtes sélectionnées.

Des exemples de mise en œuvre de l'invention vont à présent être décrits en référence aux figures suivantes :

- la figure 1 est une vue simplifiée d'un système de stockage conforme à l'invention, et

- la figure 2 est un schéma-blocs illustrant le déroulement des étapes d'un procédé de gestion de requêtes conforme à l'invention.

En référence à la figure 1 , un système de stockage de données 100 conforme à l'invention va être à présent décrit.

Le système de stockage 100 comporte tout d'abord une entrée de signal d'horloge CLK destinée à recevoir un signal d'horloge de cadencement du système de stockage 100. Le signal d'horloge définit des cycles d'horloges successifs.

Le système de stockage 100 comporte en outre des mémoires 102 _n (n = 1 ...N).

Chaque mémoire 102 _n comporte un ou plusieurs ports d'entrée désignés globalement par la référence 104 _n et un ou plusieurs ports de sortie désignés globalement par la référence 106 _n .

Chaque port d'entrée 104 _n de chaque mémoire 102 _n est destiné à recevoir, à chaque cycle d'horloge, au plus une requête d'accès à la mémoire 102 _n . Cette requête est sous la forme d'une requête locale indiquant en particulier une adresse de la mémoire 102 _n où l'accès est destiné à être réalisé. Chaque port d'entrée 104 _n est destiné à recevoir des requêtes d'accès en lecture et en écriture, ou bien spécialisé pour ne recevoir que des requêtes d'accès en lecture ou bien que des requêtes d'accès en écriture.

Chaque port de sortie 106 _n de chaque mémoire 102 _n est associé à un seul port d'entrée 104 _n et est destiné à présenter, à chaque cycle d'horloge, au plus une réponse à une requête obtenue auprès du port d'entrée 104 _n associé. Dans l'exemple décrit, seules les requêtes en lecture sont destinées à donner lieu à une réponse, mais pas les requêtes en écriture. Ainsi, un port de sortie 106 _n est associé à chaque port d'entrée 104 _n destiné à recevoir au moins des requêtes d'accès en lecture, mais il n'y a pas de port de sortie associé aux ports d'entrée 104 _n spécialisés en écriture.

Chaque mémoire 102 _n est ainsi destinée, à chaque cycle d'horloge, à obtenir des requêtes auprès de ses ports d'entrée 104 _n , à les réaliser, et à fournir à ses ports de sortie 106 _n les réponses éventuelles. Comme les ports d'entrée 104 _n sont en nombre limité, chaque mémoire 102 _n n'est apte à obtenir qu'un nombre limité de requêtes à chaque cycle d'horloge, ce qui sera appelé par la suite « capacité » de la mémoire.

En variante, la réalisation des requêtes prend plusieurs cycles d'horloge.

Le système de stockage 100 comporte en outre au moins deux ports d'entrée désignés globalement par le référence 108 et un ou plusieurs ports de sortie désignés globalement par la référence 110.

Chaque port d'entrée 108 est destiné à recevoir, à chaque cycle d'horloge, au plus une requête d'accès à une des mémoires 102 _n . Cette requête est sous la forme d'une requête globale indiquant en particulier une adresse globale structurée comme si le système de stockage 100 était une seule mémoire. Chaque port d'entrée 108 est destiné à recevoir des requêtes d'accès en lecture et en écriture, ou bien spécialisé pour ne recevoir que des requêtes d'accès en lecture ou bien que des requêtes d'accès en écriture.

Chaque port de sortie 110 est associé à un seul port d'entrée 108 et est destiné à présenter, à chaque cycle d'horloge, au plus une réponse à une requête obtenue auprès du port d'entrée 108 associé. Dans l'exemple décrit, seules les requêtes en lecture sont destinées à donner lieu à une réponse, mais pas les requêtes en écriture. Ainsi, un port de sortie 110 est associé à chaque port d'entrée 108 destiné à recevoir au moins des requêtes d'accès en lecture, mais il n'y a pas de port de sortie associé aux ports d'entrée 108 spécialisés en écriture. Le système de stockage 100 comporte en outre un ou plusieurs étages de traitement destinés à traiter successivement les requêtes obtenues auprès des ports d'entrée 108, à les réaliser et, le cas échéant, à fournir une réponse. Le ou les étages de traitement sont destinés à être successivement traversés de manière à former une ligne de traitement (traduction de l'anglais « pipeline »). De préférence, chaque étage de traitement est destiné à traiter les données qu'il reçoit en un cycle d'horloge. Ainsi, il est destiné à recevoir, à chaque cycle d'horloge, des données d'entrée et à fournir les données de sorties correspondant aux données d'entrée avant le cycle d'horloge suivant.

Dans l'exemple décrit, le système de stockage 100 comporte trois étages de traitement : un étage d'entrée 112 de traitement des requêtes, un étage intermédiaire 114 regroupant les mémoires 102 _n et un étage de sortie 116 de traitement des réponses.

L'étage d'entrée 112 est destiné, à chaque cycle d'horloge, à réaliser les étapes qui seront détaillées en référence à la figure 2. En résumé, l'étage d'entrée 112 est destinée à obtenir des requêtes auprès des ports d'entrée 108, à en sélectionner certaines, et à fournir les requêtes sélectionnées à l'étage intermédiaire 114, c'est-à-dire aux ports d'entrée 104 _n des mémoires 102 _n . Les requêtes sont fournies sous la forme de requêtes locales indiquant une adresse locale dans la mémoire 102 _n où la lecture ou l'écriture est destinée à être réalisée. L'étage d'entrée 112 comporte une fonction de correspondance F associant chaque adresse globale possible à une des mémoires 102 _n et à une adresse locale dans cette mémoire 102 _n .

L'étage de sortie 116 est destiné, à chaque cycle d'horloge, à réaliser les étapes qui seront détaillées en référence à la figure 2. En résumé, l'étage de sortie 116 est destiné à obtenir auprès des ports de sortie 106 _n des mémoires 102 _n les réponses éventuelles fournies par les mémoires 102 _n , à déterminer, pour chaque réponse éventuelle, le port de sortie 110 sur lequel la réponse est destinée à être fournie, et à fournir cette réponse sur ce port de sortie 110.

De préférence, le système de stockage 100 est réalisé uniquement avec des composants matériels, et non avec des composants logiciels tels que des processeurs exécutant des instructions enregistrées sur un support de mémorisation.

En référence à la figure 2, un procédé de gestion de requêtes 200 conforme à l'invention et mis en œuvre par le système de stockage 100 de la figure 1 , va à présent être décrit.

À chaque cycle d'horloge, les étapes suivantes sont réalisées dans l'étage d'entrée 112.

Au cours d'une étape 202, s'il n'existait pas de requête prioritaire au cycle d'horloge précédent, l'étage d'entrée 112 obtient de nouvelles requêtes auprès des ports d'entrée 108. Comme cela sera expliqué par la suite, une requête prioritaire est une requête mise en attente à chacun des L derniers cycles d'horloge en partant du cycle d'horloge précédent, L étant un nombre prédéterminé supérieur ou égal à deux.

Au cours d'une étape 204, pour chaque nouvelle requête obtenue, l'étage d'entrée 112 détermine, au moyen de la fonction d'adressage F, la mémoire 102 _n et l'adresse locale dans cette mémoire visées par la nouvelle requête.

Au cours d'une étape 206, s'il existait une ou plusieurs requêtes prioritaires au cycle d'horloge précédent, l'étage d'entrée 112 s'abstient d'obtenir de nouvelles requêtes.

Au cours d'une étape 208, l'étage d'entrée 112 sélectionne, parmi la ou les requêtes en attente éventuelles et la ou les nouvelles requêtes éventuelles, au moins une requête destinée à être fournie à l'étage intermédiaire 114. De préférence, la sélection d'au moins une requête est réalisée en fonction de la capacité de chaque mémoire 102 _n à obtenir des requêtes. En particulier, pour chaque mémoire 102 _n , un nombre de requêtes inférieur ou égal au nombre de port d'entrée 104 _n de la mémoire 102 _n est sélectionné. De préférence, la sélection est réalisée de manière à sélectionner le plus grand nombre possible de requêtes que la mémoire sera apte à recevoir au cycle d'horloge suivant. De préférence, la sélection d'au moins une requête est réalisée en donnant la priorité aux requêtes en attente les plus anciennes, c'est-à-dire aux requêtes mises en attente depuis le plus grand nombre de cycles d'horloge. Dans le cas où il n'y a pas de requête en attente, l'étage d'entrée 112 sélectionne donc au moins une nouvelle requête.

Dans le cas où il y avait des requêtes prioritaires au cycle d'horloge précédent, l'étage d'entrée 112 sélectionne donc au moins une requête en attente et aucune nouvelle requête (puisqu'aucune nouvelle requête n'a été reçue au cycle d'horloge en cours).

Au cours d'une étape 210, l'étage d'entrée 112 fournit chaque requête sélectionnée à un port d'entrée 104 _n de la mémoire 102 _n visée par cette requête. La requête est fournie sous la forme d'une requête locale indiquant en particulier l'adresse locale visée.

Au cours d'une étape 212, l'étage d'entrée 112 met en attente la ou les requêtes non sélectionnées.

En particulier, dans le cas où une nouvelle requête n'a pas été sélectionnée, cette nouvelle requête est mise en attente.

Au cours d'une étape 214, l'étage d'entrée 112 détermine l'existence ou non d'au moins une requête mise en attente depuis au moins L cycles d'horloge, y compris le cycle d'horloge en cours, c'est-à-dire mise en attente à chacun des L derniers cycles d'horloge, y compris le cycle d'horloge en cours. L est un nombre prédéterminé supérieur ou égal à deux. Une telle requête est qualifiée de prioritaire. Le système de stockage 100 se trouve alors dans une situation dite de conflit. Dans ce cas, l'étage d'entrée 112 suspend l'obtention de nouvelles requêtes pour le cycle d'horloge suivant. De préférence, l'étage d'entrée 112 prévient en outre le dispositif informatique (non représenté) fournissant les requêtes au système de stockage 100 de cette situation de conflit, afin que ce dernier, par exemple, suspende l'envoi de requêtes au système de stockage 100 pour le cycle d'horloge suivant.

Parallèlement, les étapes suivantes sont réalisées dans l'étage intermédiaire 114.

Au cours d'une étape 216, chaque mémoire 102 _n obtient sur ses ports d'entrée 104 _n les requêtes qui lui ont été fournies au cycle précédent sous forme de requête locale par l'étage d'entrée 112.

Au cours d'une étape 218, chaque mémoire 102 _n traite les requêtes qu'elle a obtenues. En particulier, dans le cas d'une requête d'accès en écriture indiquant des données à écrire, la mémoire 102 _n écrit ces données à l'adresse locale. Dans le cas d'une requête en lecture, la mémoire 102 _n lit les données se trouvant à l'adresse locale.

Au cours d'une étape 220, chaque mémoire 102 _n fournit les réponses éventuelles sur ses ports de sortie 106 _n . En particulier, dans le cas d'une requête d'accès en lecture, la mémoire 102 _n fournit les données lues sur son port de sortie 106 _n associé au port d'entrée 104 _n sur lequel la requête a été obtenue.

Parallèlement, les étapes suivantes sont réalisées dans l'étage de sortie 116.

Au cours d'une étape 222, l'étage de sortie 116 obtient, auprès des ports de sortie 106 _n des mémoires 102 _n , les réponses éventuelles fournies par les mémoires 102 _n .

Au cours d'une étape 224, l'étage de sortie 116 détermine, pour chaque réponse éventuelle, le port de sortie 110 sur lequel la réponse est destinée à être fournie.

Au cours d'une étape 226, l'étage de sortie 116 fournit chaque réponse sur le port de sortie 110 associé au port d'entrée 108 sur lequel la requête correspondant à cette réponse a été reçue.

Un exemple de fonctionnement du système de stockage 100 mettant en œuvre le procédé de gestion 200 va à présent être décrit.

Dans cet exemple, le système de stockage 100 comporte trois ports d'entrée 108 (destinés à recevoir des requête d'accès en lecture et en écriture).

Le système de stockage 100 comporte en outre trois mémoires 102 _n

(N = 3) simple port, c'est-à-dire présentant chacune un seul port d'entrée 104 _n et un seul port de sortie 106 _n associé.

En outre, le nombre prédéterminé L vaut deux, de sorte qu'une requête mise en attente deux cycles d'horloge de suite devient prioritaire et entraîne l'arrêt de l'obtention de nouvelles requêtes.

Pour décrire cet exemple, un tableau récapitulatif sera présenté pour chaque cycle d'horloge. La case de gauche de la première ligne du tableau indique les nouvelles requêtes obtenues sur les ports d'entrée 108 au cycle d'horloge en cours.

La case de droite de la première ligne du tableau indique les requêtes restant en attente, c'est-à-dire mises en attente au cycle d'horloge précédent le cycle d'horloge en cours.

La case de droite de la seconde ligne du tableau indique les requêtes sélectionnées au cycle d'horloge en cours pour être fournies à l'étage intermédiaire 114.

La case de gauche de la seconde ligne du tableau indique les requêtes mises en attente au cycle d'horloge en cours. Une requête déterminée comme prioritaire à la fin du cycle d'horloge en cours est indiquée par un soulignement.

Les requêtes sont notées sous la forme : Xy(n) où X est une lettre correspondant au port d'entrée (A pour le premier port, B pour le second et C pour le troisième), y est le numéro de la requête et n est l'indice de la référence de la mémoire 102 _n visée par la requête.

Premier cycle d'horloge

Ainsi, au premier cycle d'horloge, l'étage d'entrée 112 obtient de nouvelles requêtes, en fournit deux nouvelles requêtes à l'étage intermédiaire et met en attente une nouvelle requête.

Deuxième cycle d'horloge

Ainsi, au deuxième cycle d'horloge, l'étage d'entrée 112 obtient de nouvelles requêtes, sélectionne deux requêtes parmi les nouvelles requêtes et la requête en attente et fournit ces deux requêtes. L'une des deux requêtes sélectionnées est une nouvelle requête obtenue au deuxième cycle d'horloge.

Troisième cycle d'horloge A3(2), B3(3), C3(3) A2(1 ), B2(1 )

A2(1 ), A3(2), B3(3) B2(1 ), C3(3)

Ainsi, au troisième cycle d'horloge, l'étage d'entrée 112 détermine l'existence d'une requête prioritaire.

Quatrième cycle d'horloqe

Ainsi, au quatrième cycle d'horloge, l'étage d'entrée suspend l'obtention de nouvelles requêtes, et fournit la requête prioritaire ainsi qu'une requête non prioritaire.

Cinquième cycle d'horloqe

Pour illustrer encore les résultats qui peuvent être obtenus par le système de stockage 100 et le procédé de gestion 200, il a été calculé le ratio entre, d'une part, le nombre de cycles d'horloge où aucune nouvelle requête n'est obtenue à cause de la présence d'au moins requête prioritaire au cycle d'horloge précédent et, d'autre part, le nombre de cycles d'horloge où des nouvelles requêtes sont obtenues à cause de l'absence de requête prioritaire au cycle d'horloge précédent. Le ratio a été calculé pour plusieurs valeurs du nombre prédéterminé L, dans le cas où les requêtes ciblent de manière aléatoires les mémoires 106 _n , et où le système de stockage 100 comporte trente-deux ports d'entrée 108 et quarante-huit mémoires 102 _n (N = 48) simple port.

Les résultats obtenus sont résumés dans le tableau suivant.

L ratio

1 1 ,78

2 1 ,14

3 0,62

4 0,3

L'invention n'est pas limitée aux exemples de mise en œuvre décrits précédemment, mais au contraire définie par les revendications qui suivent.

Il apparaîtra en effet à l'homme de l'art que diverses modifications peuvent être apportées aux exemples de mise en œuvre décrits ci-dessus, à la lumière de l'enseignement qui vient de lui être divulgué.

Par ailleurs, dans les revendications qui suivent, les termes utilisés ne doivent pas être interprétés comme limitant les revendications aux éléments des exemples de mise en œuvre décrits précédemment, mais doivent être interprétés pour y inclure tous les équivalents dont la prévision est à la portée de l'homme de l'art en appliquant ses connaissances générales.