Brevet FR2834574A1 — publié le 20030711

revendication 10 ou 11, caractérisé en ce qu'il constitue un appareil dit "PDA". - 1 - 2834574 CHAMP DE L' INVENTION La présente invention se rapporte d'une manière générale aux systèmes de traitement et de manière plus particulière à la compression de lignes de données dans des mémoires cache d'un système de traitement. ARRIÈRE PLAN DE L' INVENTION De manière typique les mémoires cache sont utilisées dans des systèmes de traitement pour accélérer l'accès du processeur à des données stockées dans une mémoire principale. Une mémoire cache est plus petite, plus rapide et de manière typique plus coûteuse qu'une mémoire principale. Lorsqu'un processeur demande une donnée qui réside en mémoire principale, le système de traitement transmet la donnée demandée au processeur et peut aussi stocker la donnée dans une mémoire cache, dont il peut y avoir une pluralité de niveaux. Lorsque le processeur place par la suite une requête pour la même donnée, le système de traitement vérifie la mémoire cache en premier lieu. Si la donnce demandée réside dans le cache, le système "fait mouche" dans le cache et fournit la donnée au processeur à partir du cache. Si la donnée n'est pas résidente dans le cache, un "manqué" de cache a lieu et le système récupère la donnée depuis la mémoire principale. Une donnée utilisée de manière fréquente est par conséquent récupérée de manière plus rapide qu'une donnée demandée de manière moins fréquente et la latence d'accès globale aux données, c'est- à-dire le temps séparant la requête et la fourniture des données, est réduite. Des niveaux intermédiaires de cache peuvent être utilisés entre un cache primaire et une mémoire principale et sont, de manière typique, plus lents et moins coûteux, que le cache primaire. Des caches de 2 - 2834574 niveau supérieur dans une telle hiérarchie de caches sont arrangés d'une manière générale en ordre de vitesse décroissante et sont utilisés de manière typique pour tenir des données qui font l'objet d'accès moins fréquemment que des données gardées dans le cache primaire. Lorsqu'un manqué de cache se produit au niveau du cache primaire, le système de traitement vérifie la donnée dans le ou les niveaux de cache supérieurs avant d'accéder à la donnée depuis la mémoire principale. Par conséquent, bien que le fait d'utiliser des niveaux supérieurs de cache tende à améliorer la performance globale du système, il reste néanmoins souhaitable de rendre le plus bas niveau de cache aussi grand que possible, pour augmenter les chances de faire mouche dans le cache dans le niveau de cache le plus faible. Lorsqu'une adresse de donnée est présentée à un cache, une recherche de correspondance dans un arrangement d'étiquettes de cache est effectuée pour déterminer si la donnée demandée est couramment dans l' arrangement de données du cache. Si c'est le cas, alors l' arrangement de données est lu. La donnée est stockée dans un arrangement de donnces de cache sous forme de "lignes", toutes les lignes de l' arrangement contenant un nombre égal d'octets. La taille de ligne de cache est en général la méme pour tous les niveaux de cache dans un système. Fréquemment les tailles de ligne courantes sont fixées à 64 ou 128 octets. Un cache d'un mégaoctet (ayant 220 octets), par exemple, stockerait 8192 lignes de 128 octets, et une structure d'étiquettes en correspondance contiendrait 8192 entrées. Augmenter une taille de cache dans un système de traitement peut non seulement être coûteux, mais peut aussi augmenter la latence, puisqu'il serait possible de demander au système de traitement de 3 2834574 chercher dans un plus grand arrangement d'étiquettes, puis de chercher dans un arrangement de donnces plus grand pour localiser la donnée dans le cache. Des techniques sont connues, dont le but est de réduire la latence des recherches dans un cache. Par exemple, la recherche de correspondance entre donnée et étiquette peut être effectuée en parallèle pour réduire le nombre de cycles d'horloge nécessaires pour chercher dans un cache. Il serait aussi souhaitable, cependant, d' augmenter la capacité de stockage d'un cache sans avoir à augmenter sa taille physique. Par conséquent, il serait souhaitable de fournir une compression de données dans un cache. Une telle compression serait particulièrement convenable pour des niveaux inférieurs d'une hiérarchie de cache, o la capacité, plus que la latence, peut affecter la performance du système. RÉSUMÉ DE L' INVENTION Selon un premier aspect, l' invention propose un procédé pour stocker des lignes de données dans un arrangement de donnces d'une mémoire cache cartographiée à une mémoire principale d'un système de traitement, l' arrangement de donnces comprenant une pluralité de lignes pour stocker des donnces ayant des longueurs égales, le procédé comprenant les étapes consistant à: prédéfinir une pluralité de longueurs possibles de soussections disponibles pour stocker des lignes de données, dans chacune des lignes pour stocker des données; compresser au moins une des lignes de données; ajuster la ligne de données compressce dans une sous section de l'une des lignes pour stocker des données, la sous-section ayant une des longueurs prédéfinies; et pointer vers la sous-section en utilisant un arrangement d'étiquettes. Dans une variante de réalisation du procédé 4 2834574 proposé par l' invention, il est prévu, dans l'étape consistant à pointer vers la sous-section en utilisant un arrangement d'étiquettes d'inclure l' allocation d'un élément dans l' arrangement d'étiquettes à chacune des sous-sections. Dans cette variante de réalisation du procédé proposé par l' invention, il est prévu, dans l'étape consistant à allouer un élément dans l' arrangement d' étiquettes, de procéder au rejet du cache d' une ligne "victime" sur la base d'un indicateur de compression. Dans une autre variante de réalisation du procédé, proposé par l' invention, il est prévu, dans l'étape consistant à aguster la ligne de données compressée dans une sous-section de l'une des lignes pour stocker des données d'inclure les étapes consistant à: prédéfinir une longueur possible pour la sous-section comme l'intégralité d'une ligne pour stocker des données; et stocker la ligne de données compressée sous forme non compressée dans une sous-section définie comme celle qui est entière parmi les lignes pour stocker des données lorsqu'un rapport de compression de la ligne de données compressée dépasse une limite prédéterminée du rapport de compression. Selon un deuxième aspect, l' invention fournit un cache, dans un système de traitement, pour tenir des lignes de données réaupérées d'une mémoire principale du système de traitement, ledit cache comprenant: un arrangement de données cartographié à la mémoire principale, l' arrangement de donnéss comprenant une pluralité de lignes pour stocker des données pour stocker les lignes de donnces, chaque ligne pour stocker des données étant configurée pour tenir une pluralité de lignes compressée de données; et un arrangement d'étiquettes configuré pour pointer vers des lignes de données stockées dans l' arrangement de _ 5 - 2834574 données, l'arrangement d'étiquettes comprenant un élément pour chaque ligne de données qui peut être stockée dans l' arrangement de données. Dans une variante de réalisation de ce deuxième aspect de l' invention, il est prévu que chaque ligne pour stocher des données comprenne une pluralité de sous-sections possibles dans lesquelles une ligne de donnces peut être stockée, chacun des éléments formant une étiquette correspondant à une sous-section possible en correspondance. Dans une autre variante de réalisation de ce deuxième aspect de l' invention, il est prévu que l' arrangement d'étiquettes comprenne un élément pour chaque sous-sect ion de ligne s pour stocker de s données dans lequel une ligne de données peut être stockée. Dans une autre variante de réalisation de ce deuxTème aspect de l' invention, il est prévu que chacun des éléments formant une étiquette comprenne un indicateur de compression configuré pour indiquer un état de compression pour une ligne de donnces en correspondance. Dans une autre variante de réalisation de ce deuxième aspect de l' invention, il est prévu que chacun des éléments formant une étiquette comprenne un indicateur disponibilité configuré pour indiquer si une sous-section d'une ligne pour stocker des données est disponible pour tenir une ligne de données. Enfin, dans une autre variante de réalisation de ce deuxième aspect de l' invention, il est prévu que chacune des lignes pour stocker des données soit configurée pour tenir une ligne de données non compressée dans plus d'une sous-section. Lorsque des lignes de données sont compressées lors d'écritures vers le cache puis décompressées lors de lectures depuis un cache, il est possible d'ajuster 6- 2834574 un plus grand nombre de lignes dans le cache. Par conséquent, la probabilité de faire mouche dans un cache augnente et la performance du système de traitement est améliorée. D'autres zones d'applicabilité de la présente invention deviendront apparentes à partir de la description détaillée fournie ci-dessous. On comprendra que la description détaillée et les exemples spécifiques, tout en indiquant le mode de réalisation préférentiel de l' invention, ne sont donnés qu'à des fins d' illustration et ne sont pas destinés à limiter la portée de l' invention. BRÈVE DESCRIPTION DES DESSINS La présente invention pourra être mieux comprise à partir de la description détaillée et des dessins qui l'accompagnent, dans lesquels: La figure 1 est un diagramme simplifié d'un cache bidirectionnel associatif par jeu de la technique ancienne; La figure 2 est un diagramme simplifié d'un cache bidirectionnel associatif par jeu conformément à un mode de réalisation de la présente invention; et La figure 3 est un organigramme d'un procédé pour stocker des données dans une mémoire cache conformément à un mode de réalisation de la présente invention. DESCRIPTION DÉTAILLÉE DU MODE DE RÉALISATION PRÉFÉRENTIEL La description de modes de réalisation préférentiels qui fait suite constitue uniquement donnée à titre d'exemples et n'est en aucune manière destince à limiter l' invention, son application ou usages. Bien que la présente invention soit décrite ici en référence à un cache associatif par jeu, l' invention 7 2834574 n'est pas ainsi limitée. Des modes de réalisation de l' invention peuvent être pratiqués en liaison avec d'autres formes de cartographies de cache, qui incluent sans toutefois limiter, une cartographie directe et associative de cache. En outre, bien que des modes de réal i sat ion soient décrits i ci en relation avec un cache bidirectionnel associatif par jeu, l' invention peut être pratiquée avec des niveaux plus élevés d'associativité par jeu. Un cache bidirectionnel associatif par jeu de la technique ancienne est indiqué d'une manière générale par une référence numérique 10 à la figure 1. Le cache comprend un arrangement d'étiquettes 14 qui cartographie un arrangement de données 18 sur une mémoire principale 22. Des lignes 26 de données sont stockées dans la mémoire principale 22 et sont alignces sur des frontières de ligne de cache 30, de telle sorte que les lignes de donnces 26 soient égales en longueur aux lignes pour stocker des données 38 dans l' arrangement de données de cache 18. Pour beaucoup de systèmes de traitement, une ligne de données possède communément 64 ou 128 octets. Comme on le montre à la figure 1, les lignes de données 26 et les lignes pour stocker des données 38 ont des longueurs de 128 octets. Chaque adresse d'une ligne de données 26 dans la mémoire principale 22 comprend une référence d'étiquette 46. En outre, la mémoire principale 22 peut être considérée comme étant divisée en une pluralité de groupes 42, chacun d'eux étant associé à un jeu 44 de deux lignes pour stocker des données 38 dans l' arrangement de données 18. Pour chaque ligne pour stocLer des données 38 dans l' arrangement de données de cache 18, l' arrangement d'étiquettes 14 comprend un élément en correspondance 54. Lorsqu'il est utilisé ici, le terme "élément" est défini comme un emplacement - 8 - 2834574 (qui peut être occupé ou non par des données valables) à l'intérieur d'un arrangement. Chaque élément 54 de l' arrangement d'étiquettes 14 comprend une entrée d'étiquette 58 et un bit "valable" 62. Lorsqu'une ligne de donnces 26 est écrite dans le cache 10, elle est écrite dans l'une des lignes pour stocker des données 38 dans le jeu 44 associé au groupe 42 de la mémoire principale 22 à partir de laquelle la ligne de données 26 est en cours d'écriture. Une ligne particulière pour stocker des données 38 peut être sélectionnée sur la base (parmi d'autres critères possibles) du fait que les bits "valable" des deux lignes pour stocker des donnces 38 dans le jeu associé 44 indiquent la présence d'une donnce valable, c'est-à dire une autre ligne de données 26 du groupe associé 42 dans la mémoire principale 22. Lorsqu'une ligne de données 26 est écrite dans une ligne pour stocker des données 38, l'étiquette 46 qui référence la ligne de données 26 dans la mémoire principale 22 est écrite dans l'entrce d'étiquette en correspondance 58 de l' arrangement d'étiquettes 14. Le bit "valable" en correspondance 62 est mis à j our aussi pour indiquer que la ligne pour stocker des données 38 dans laquelle la ligne de données 26 est écrite contient une donnée valable. Les caches conventionnels incluent de manière typique une étiquette pour chaque ligne pour stocker des données, et par conséquent pour chaque ligne de données, dans le cache. En se référant au cache simplifié 10 montré à la figure 1, on peut voir que là o le cache 10 est un cache d'un mégaactet, l' arrangement de données 18 peut contenir 8192 lignes de 128 octets. Pour chaque ligne pour stocker des données 38 de l' arrangement de données 18, un élément formant un arrangement d'étiquettes en correspondance 9 2834574 54 est nécessaire. L' arrangement d'étiquettes en correspondance 14 aurait donc 8192 éléments formant un arrangement d'étiquettes 54. Il serait souhaitable d'augnenter la capacité de stockage d'un arrangement de cache de donnces pour stocker des lignes de donnces compressées dans l' arrangement. Lorsqu'il est utilisé ici, le terme "rapport de compression" est défini comme un rapport de la taille compressée d'une ligne de données à la taille non compressée de la ligne de données. Ainsi par exemple, là o une ligne de 128 octets de données est compressée en 64 octets, le rapport de compression vaut 0,5. La compression des données a tendance à dépendre du motif des donnces. Lorsqu'une compression de données est effectuée, on ne connaît pas à l'avance, de manière typique, quel rapport de compression sera obtenu. Par contre, dans un cache, une entrée d'étiquette est fournie pour chaque ligne de données en cours de stockage dans le cache, et les entrces d'étiquette sont en nombre fixé. Ceci signifie que le nombre d'étiquettes disponibles est prédéterminé par une taille de l' arrangement d'étiquettes utilisé pour référencer l' arrangement de données du cache. Si les données devaient être stockées sous une forme compressée dans un arrangement de données de cache, la structure d'étiquettes pour un tel cache inclurait suffisamment d'entrées pour représenter toutes les lignes de données qui pourraient être présentes dans l' arrangement de données. Par exemple, si deux lignes ou moins de données pouvaient être entassoes dans une ligne pour stocker des données et s'ajuster dans une ligne non compressée de données, la structure d'étiquettes pourrait avoir besoin de deux fois plus d'entrces qu'il ne serait nécessaire pour un cache sans - 10 - 2834574 aucune compression. Par conséquent, si un total de deux mégaoctets de lignes de données était stocké sous forme de lignes compressées, 16384 étiquettes seraient utilisées pour garder une trace des lignes de données. Un mode de réalisation de la présente invention s'adresse à un procédé pour stocker des lignes de données dans un arrangement de donnces formant un cache. Ce procédé comprend une compression d' au moins une des lignes de données, un ajustement de la ligne de données compressée à l'intérieur d'une sous-section de l'une des lignes pour stocker des données dans l' arrangement, et le pointage vers la sous-section en utilisant un arrangement d'étiquettes. Si une ligne de données est compressée selon un rapport de compression supérieur à une limite prédéterminée, alors la ligne non compressée de données est insérce dans le cache. Par exemple, et comme cela sera décrit plus loin en rapport à la figure 2, si un rapport de compression est inférieur ou égal à 0,5 pour une ligne de donnces compressée, la ligne de données compressée est écrite dans une moitié d'une ligne pour stocker des données. L'autre moitié de la ligne pour stocker des données remplie à demi est disponible pour une autre ligne de données compressée. Lorsqu'une ligne non compressée de données est écrite dans le cache, une parmi deux entrées d'étiquette pour cette ligne particulière pour stocker des donnces est utilisée pour référencer la ligne de donnces. L'autre entrce n'est pas utilisée et par conséquent est non valable lorsque des données non compressées sont contenues dans la ligne pour stocker des données. Un cache bidirectionnel associatif par jeu conforme à un mode de réalisation de la présente invention est indiqué d'une manière générale par une référence numérique 200 à la figure 2. Le cache 200 - 11 - 2834574 comprend un arrangement d'étiquettes 214 qui cartographie un arrangement de données 218, par exemple, sur une mémoire principale 222. Des lignes 226 de données sont stockées dans la mémoire principale 222 et sont alignées sur des frontières 230 de lignes de cache de telle sorte que les lignes de données 226 soient égales en longueur aux lignes pour stocker des donnces 238 dans l' arrangement de donnces de cache 218. Comme cela est montré à la figure 2, les lignes de données 226 et les lignes pour stocker des donnces 238 ont une longueur de 128 octets. Bien que le présent mode de réalisation soit décrit en relation avec des lignes de données longues de 128 octets, on considère que l' invention peut étre pratiquce en relation avec d'autres longueurs de ligne. Chaque adresse pour une ligne de données 226 en mémoire principale 222 comprend une référence d'étiquette 246. En outre, la mémoire principale 222 peut étre considérce comme étant divisée en une pluralité de groupes 242, chacun d'eux étant associé à un jeu 244 de deux lignes pour stocker des données 238 dans l' arrangement de données 218. Par exemple, le groupe 248 de la mémoire principale est associé au jeu 250 dans l' arrangement de données 218. Un jeu de longueurs possibles pour la sous-section de ligne pour stocker des données disponible pour stocker des lignes de données est prédéfini pour l' arrangement de données 218. De manière spécifique, il est prédéLini qu'une ligne de données 226 pourrait être stockée soit dans une moitié d'une ligne pour stocker des données 238 soit dans une ligne entière pour stocker des données 238. L' arrangement d'étiquettes 214 comprend un élément 254 pour chacune des plus petites sous-sections possibles, c'est-à-dire pour chaque demi ligne pour stocker des données 278. Par conséquent, - 12 - 2834574 pour chaque ligne pour stocker des donnces 238 dans l' arrangement de données de cache 218, l' arrangement d'étiquettes 214 comprend deux éléments en correspondance 254a et 254b. On notera que des prédéfinit ions de sous-sect ion en variante ou en supplément sont possibles. Par exemple, on pourrait aussi prédéfinir des sections d'un quart ou de trois quarts de ligne pour stocker des données 238. Dans un tel cas, l' arrangement d'étiquettes 214 inclurait quatre éléments 254 en correspondance pour chaque ligne pour stocker des données 238. En se reportant à nouveau à la figure 2, chaque élément 254 comprend une entrée d'étiquette 258, un bit "valable" 262, un indicateur de compression 270 et un champ "disponible" 274. Le bit valable 262 est mis à un pour chaque sous-section 278 de ligne pour stocker des données 238 qui peut contenir une ligne valable de donnces 226. Le champ "disponible" 274 est utilisé pour indiquer si une sous-section d'une ligne pour stocker des données en correspondance 278 contient une ligne de données compressée 226 ou au contraire si elle est occupée par une ligne non compressoe des données 226 qui occupe plus d'une sous-section 278. En outre, le champ "disponible" 274 est utilisé pour indiquer si la sous- section en correspondance 278 est actuellement disponible ou en cours d'utilisation par une autre entrée d'étiquette. L'indicateur de compression 270 est utilisé pour indiquer un état de compression pour une ligne de données 226 stockée dans la sous-section en correspondance 278. Par exemple, l'indicateur 270 est utilisé pour indiquer si la ligne de données en correspondance 226 est compressée ou non, et, dans un mode de réalisation dans lequel une pluralité de rapports de compression sont acceptés, un rapport de - 13 - 2834574 compression pour la ligne de données stockée 226. L'indicateur de compression 270 est aussi utilisé par un matériel de décompression (non montré) lorsque la ligne de donnces est lue depuis le cache 200. Des lignes de données peuvent être stockées dans le cache 200 en utilisant un procédé indiqué d'une manière générale à la figure 3 par la référence numérique 400 Une ligne de données 226 à écrire est compressée dans une étape 404. Le rapport de compression pour la ligne de donnces compressée 226 est vérifié à l'étape 408. Si le rapport de compression est supérieur à 0,5, une recherche est effectuée, à l'étape 412, pour trouver une ligne pour stocker des données 238 entière dans laquelle stocker la ligne de données 226 sous forme non compressée. Un élément de l' arrangement d'étiquettes 254 est alors recherché pour cela et marqué "non valable" et "disponible" par des indicateurs 262 et 274. Si un tel élément 254 n'est pas trouvé, une ligne de données "victime" 226 est sélectionnée pour un remplacement, à l'étape 416. La ligne victime 226 est copiée dans la mémoire principale 222. Copier toutes les lignes de données en qualité de victimes 226 à l'intérieur d'une ligne pour stocker des données 238 sert à récupérer tous les éléments d' arrangement d'étiquettes 254 associés avec cette ligne particulière pour stocker des données 238, en créant ainsi deux éléments d'étiquettes non valable et disponible 254 dans le jeu 244. La nouvelle ligne 226 est insérée à la place de la victime. La ligne non compressée 226 est écrite, à l'étape 420, dans la sous-section sélectionnce, c'est-à-dire l'intégralité de la ligne pour stocker des données 238. A l'étape 424, l'intégralité de la ligne pour stocker des données 238 est marquée comme "valable" et "indisponible" par des - 14 - 2834574 indicateurs 262 et 274. Le facteur de compression est 270 et est écrit pour indiquer que la ligne de données n'est pas compressée et l'entrce d'étiquette 258 est mise à j our pour pointer vers la ligne écrite pour stocker des données. Si le rapport de compression est inférieur ou égal à 0,5, une recherche est effectuée, dans une étape 430 pour trouver un élément de l' arrangement d'étiquettes 254 pointant vers une sous-section d'une ligne pour stocker des données 238 de demi-longueur, dans le jeu associé 244, qui soit à la fois non valable et disponible. Si aucun élément de l' arrangement d'étiquettes 254 n'est trouvé, une ligne de données 226 victime est sélectionnée dans une étape 434 et écrite vers la mémoire 222. La ligne compressce 226 est écrite, dans une étape 438, dans la sous-section de demi-longueur sélectionnée 278. Dans une étape 442, la sous-section de demi-longueur 278 est marquée comme "valable" et "indisponible" par des indicateurs 262 et 274. L'indicateur de compression est 270 et est écrit pour indiquer que la ligne de données 226 est compressée, et l'entrée d'étiquette 258 est mise à jour pour pointer vers la sous-section de demi-longueur écrite 278. On notera qu'il est possible de faire des comparaisons avec des rapports de compression en variantes ou supplémentaires, en particulier dans des modes de réalisation dans lesquels d'autres jeux de sous-sections 278 sont prédéfinis comme cela a été décrit plus haut. Les lignes de données 226 peuvent être compressoes en utilisant des algorithmes de compression connus dans la technique. De tels algorithmes, de manière typique mais non nocessaire, sont exécutés dans un matériel. Des algorithmes et un matériel pour compresser/ décompresser possibles comprennent, sans toutefois être - 15 limités à, des procédés pour coder par longueur de course, dans lesquels des bits répétés sont compressés, et le codage par le procédé de Huffman. Plusieurs procédés pour compresser sont décrits dans les brevets américains N 5,389,922 et 5,488, 365 accordés à Serrousi et col. et attribués au présent demandeur. Des procédés pour compresser basés sur des dictionnaires de symbole peuvent être utilisés, dans lesquels un dictionnaire et un résultat compressés sont stockés dans une entrce d'un arrangement de données. En variante, un stockage séparé est utilisé pour le dictionnaire. Si un stockage séparé pour le dictionnaire est utilisé, un algorithme est établi pour les mises à j our du dictionnaire, par exemple sur la base de l'observation d'un niveau de performance de compression obtenu et en mettant le dictionnaire à j our lorsque la performance tombe en dessous d'un seuil. Pour changer une table de symboles, toutes les lignes compressées dans une ancienne table sont lues puis écrites en retour après compression avec la nouvelle table. La performance d'une compression peut être surveillée de la manière suivante. Si la performance tombe en dessous d'un seuil, le cache peut être vidangé dans la mémoire principale. Le dictionnaire est ensuite considéré comme non valable. Le cache est ensuite rempli à nouveau de demandes de lectures issues de la mémoire. Un algorithme de compression peut être utilisé pour construire de manière automatique un nouveau dictionnaire à mesure que des données passent par lui. En se reportant à la figure 2, le nombre d'éléments de l' arrangement d'étiquettes 254 est relié à une compression maximum permise dans le cache 200. - 16 - 2834574 Par exemple, si un rapport de compression de 0,5 ou de 0,25 est permis, quatre fois autant d'éléments 254 seraient utilisés que pour stocker un arrangement de données non compressées dans le cache 200. Dans des modes de réalisation dans lesquels jusqu'à quatre lignes de données compressées pourraient être compressées en une ligne pour stocker des données 238, des lignes de données 226 pourraient occuper 0,25, 0,5 ou 0,75 de la ligne pour stocker des données 238. Par conséquent quand une ligne de données226 compressée à 0,75 de la taille non compressée est stochée dans une ligne pour stocker des données 238, si une ligne 226 compressée à 0,25 fois la taille non compressée doit par la suite être insérée dans le même jeu 244 du cache 200, elle peut être placée dans les octets disponibles restants de la ligne pour stocker des données 238. Bien que les procédés pour stocker des lignes de données dans un cache exposés ci-dessus ne soient pas limités à utiliser des caches associatifs par jeu, ils sont extrêmement efficaces lorsqu'ils sont exécutés dans des caches ayant un degré élevé d'associativité par jeu. Lorsqu'un cache est structuré et que des lignes de données sont compressées comme cela est décrit plus haut, un espace de stockage supplémentaire peut être rendu disponible à l'intérieur d'un arrangement de donnses de cache, ce qui accroît ainsi les probabilités pour faire mouche dans le cache et améliore la performance du système de traitement. La description de l' invention est uniquement exemplaire par nature et, par conséquent, l' intention est que des variations qui ne dévient pas de l' esprit de l' invention soient dans la portée de l' invention. De telles variations ne doivent pas être considérées comme un départ de l' esprit et de la portée de l' invention. - 17 - 2834574 REVENDICAT IONS 1. Procédé pour stocker des lignes de donnces (226) dans un arrangement de données (218) d'une mémoire cache (222) cartographice à une mémoire princi- pale (222) d'un système de traitement, l' arrangement de données comprenant une pluralité de lignes pour stocker des données (238) ayant des longueurs égales, le procédé comprenant les étapes consistant à: prédéfinir une pluralité de longueurs possibles de sous-sections (278) disponibles pour stocker des lignes de donnces (226), dans chacune des lignes pour stocker des données (238); compresser (404) au moins une des lignes de données; ajuster la ligne de données compressce (226) dans une sous section (278) de l'une des lignes pour stocker des données (238), la sous-section (278) ayant une des longueurs prédéfinies; et pointer (424, 442) vers la sous-section en utilisant un arrangement d'étiquettes (214). 2. Procédé de la revendication 1, dans lequel l'étape consistant à pointer vers la sous-section (278) en utilisant un arrangement d'étiquettes (214) comprend une allocation d'un élément (254) dans l' arrangement d'étiquettes à chacune des sous-sections (278). 3. Procédé de la revendication 2, dans lequel l'étape consistant à allouer un élément (254) dans l' arrangement d'étiquettes (214) comprend le rejet du cache (200) d'une ligne victime (226) sur la base d'un indicateur de compression (270). 4. Procédé de la revendication 1, dans lequel l'étape consistant à ajuster la ligne de donnces compressée (226) dans une sous-section (278) de l'une - 18 - 2834574 des lignes pour stocker des données (238) comprend les étapes consistant à:. prédéfinir une longueur possible pour la sous- section (278) comme l'intégralité d'une ligne pour stocker des données (238); et stocker la ligne de données compressée (226) sous forme non compressée dans une sous-section (278) définie comme celle qui est entière parmi les lignes pour stocker des données (238) lorsqu'un rapport de compression de la ligne de données compressée (226) dépasse une limite prédéterminée du rapport de compression. 5. Cache (200), dans un système de traitement, pour tenir des lignes de données (226) réaupérées d'une mémoire principale (222) du système de traitement, le cache comprenant: un arrangement de données (218) cartographié à la mémoire principale, l' arrangement de données comprenant une pluralité de lignes pour stocker des données (238) pour stocker les lignes de données (226), chaque ligne pour stocker des données étant configurée pour tenir une pluralité de lignes compressée de données (226); et un arrangement d'étiquettes (214) configuré pour pointer vers des lignes de données (226) stockées dans l' arrangement de données (218), l' arrangement d'étiquettes comprenant un élément (254) pour chaque ligne de données (226) qui peut être stockée dans l' arrangement de donnéss. 6. Cache (200) de la revendication 5, dans lequel chaque ligne pour stocker des données (238) comprend une pluralité de sous-sections possibles (278) dans lesquelles une ligne de données (226) peut être stockée, chacun des éléments formant une étiquette (254) correspondant à une sous-section possible en - 19 - 2834574 correspondance (278). 7. Cache (200) de la revendication 5, dans lequel l' arrangement d'étiquettes (214) comprend un élément (254) pour chaque sous-section (278) de lignes pour stocker des donnéss (238) dans lequel une ligne de données (226) peut être stockée. 8. Cache (200) de la revendication 5, dans lequel chacun des éléments formant une étiquette (254) comprend un indicateur de compression (270) configuré pour indiquer un état de compression pour une ligne de données en correspondance (226). 9. Cache (200) de la revendication 5, dans lequel chacun des éléments formant une étiquette (254) comprend un indicateur disponibilité (274) configuré pour indiquer si une sous-section (278) d'une ligne pour stocker des données est disponible pour tenir une ligne de données (226). 10. Cache (200) de la revendication 5, dans lequel chacune des lignes pour stocker des données (238) est configurce pour tenir une ligne de données non compressce (226) dans plus d'une sous-section