EP0756729A1 - Cache-speichervorrichtung zum speichern von daten - Google Patents

Cache-speichervorrichtung zum speichern von daten

Info

Publication number
EP0756729A1
EP0756729A1 EP95916674A EP95916674A EP0756729A1 EP 0756729 A1 EP0756729 A1 EP 0756729A1 EP 95916674 A EP95916674 A EP 95916674A EP 95916674 A EP95916674 A EP 95916674A EP 0756729 A1 EP0756729 A1 EP 0756729A1
Authority
EP
European Patent Office
Prior art keywords
cache
cache memory
memory device
address
group information
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP95916674A
Other languages
English (en)
French (fr)
Inventor
Jochen Liedtke
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
GMD - FORSCHUNGSZENTRUM INFORMATIONSTECHNIK GmbH
GMD Forschungszentrum Informationstechnik GmbH
Original Assignee
GMD - FORSCHUNGSZENTRUM INFORMATIONSTECHNIK GmbH
GMD Forschungszentrum Informationstechnik GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from DE19504483A external-priority patent/DE19504483A1/de
Application filed by GMD - FORSCHUNGSZENTRUM INFORMATIONSTECHNIK GmbH, GMD Forschungszentrum Informationstechnik GmbH filed Critical GMD - FORSCHUNGSZENTRUM INFORMATIONSTECHNIK GmbH
Publication of EP0756729A1 publication Critical patent/EP0756729A1/de
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
    • G06F12/1045—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache
    • G06F12/1054—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache the data cache being concurrently physically addressed
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/65—Details of virtual memory and virtual address translation
    • G06F2212/653—Page colouring

Definitions

  • Cache memory device for storing data
  • the invention relates to a cache memory device with a virtually or real indexed and real marked cache memory.
  • Modern processors require cache memories in order to compensate for the gap between fast processors and slow main memories.
  • a cache index is calculated from the real or virtual address a with the aid of a map function and a row of the cache is thus selected. Then a is compared with the address of the memory area currently associated with this cache line (the marking of the cache entry). If there is a match, there is a hit (and the cache line is used instead of the main memory), otherwise a miss.
  • Direct-mapped caches are simpler, but lead to higher miss rates than n-way caches. In principle, these consist of n correspondingly smaller direct mapped cache blocks. This ensures that each main memory element is located in at most one block. Since the map function indexes n cache lines, up to n elements with map-equivalent addresses can be contained in the cache. This n-fold associativity reduces the likelihood of clashes and increases the hit rate accordingly.
  • Real and virtually indexed caches are known.
  • the virtual address supplied by the processor is first of all generated by the translation lookaside buffer (TLB) converted into a real address. Then the cache is addressed with this real address.
  • TLB translation lookaside buffer
  • a real indexed cache does not have these disadvantages, but requires a complete address conversion step (virtual ⁇ real) of the TLB before the cache access can be initiated.
  • the cache type favored today is virtually indexed and real (physically) marked. It is just as fast as a virtually indexed and virtually marked cache, but avoids most of its disadvantages, in particular problems with multiprocessor systems, synonyms, sharing and coherence.
  • a virtually indexed and real marked cache allows TLB and cache access to run in parallel (see Fig. 8).
  • the instruction pipeline of the processor is therefore shorter, so that the latency of an instruction usually decreases by one clock and the processor line increases accordingly.
  • the mechanism remains simple as long as the address bits (i) required for indexing the cache are all within the range of the address offset (address within a page). Since this address part is not changed by the conversion of the virtual address into the real address, the cache can also be addressed (indexed) before the conversion step of the TLB. Only at the end of the cache access and parallel TLB conversion step is it checked whether the real address associated with the cache entry (the marking) matches the real address provided by the TLB.
  • the high-value bits of the address following the index part (i) need to be compared, since the cache entry indexed by (i) can only be associated with addresses whose index bits have the value (i). Accordingly, only the high-value bits need to be stored in the cache as a marker (real address).
  • n-way associative cache of this type can only be up to nx 2 P , where 2 P is the page size.
  • the cache can be enlarged by larger pages or increased associativity.
  • a more interesting technique is page coloring.
  • This describes the method of always creating pages in the real memory in such a way that the low-order address bits of the virtual and real page address are identical (see FIG. 9).
  • the virtual page number (vpn) and cache index (i) overlap.
  • the overlapping part is in the. Fig. 9 shown in black.
  • the corresponding part of the virtual address is called virtual color c, that of the real address real color c '. If the allocation is true to color, ie if the virtual and real colors match, the size limitation nx 2 P mentioned above is removed.
  • the corresponding color bits can be dispensed with in the marking (real address) and only the high-value bits (r ') of the real ones are required Page number to be compared with the mark.
  • a cache should also work if the allocation is not perfectly true to color. If the first cache access therefore leads to a miss and the real color C supplied by the TLB differs from the virtual color c, a color-corrected cache access would have to be attempted (see FIG. 11). Incorrectly colored pages could therefore be used, but would require an additional step in cache access (see Fig. 12).
  • true-color allocation is not absolutely necessary, e.g. if two virtual pages of different colors have to be mapped onto the same real page. Color corrections occur again and again, which is time-consuming and delays cache access.
  • the invention is based on the object of constructing a cache which is virtually or actually indexed and marked in real terms and which also allows fast cache access or reduces the risk of clashes in the case of pages which are not color-correctly allocated.
  • each real address converted from a virtual address is assigned, in addition to first group information (referred to above as “real color”), second group information ("second color”).
  • first group information referred to above as "real color”
  • second group information second color
  • MMU Memory Management Unit
  • Page tables are derived and, if a translation lookaside buffer (TLB) is used, inscribed in them.
  • the color correction is carried out, namely when no marking of the addressed cache entry (s) matches the real address converted from the virtual address and the group information ("virtual color") of the virtual address does not match that of the converted real address assigned second group information (second color) matches, the cache memory is indexed again by means of the cache index part and the second group information and the Marking or markings of the cache entry (s) thus addressed is or are compared with the real address converted from the virtual address.
  • a number of cache entries corresponding to the associativity of the cache memory is addressed, specifically by indexing the cache memory using the cache index and the group information, both of which are part of the virtual address or from the virtual address or derived from parts thereof (Fig. 2).
  • the virtual address or more precisely its page number address part representing the virtual page number is converted into a real address or more precisely into a page number real address part representing the real page number.
  • This page number real address part contains part of the first group information.
  • the associated second group information is also provided during implementation.
  • a translation lookaside buffer (TLB) is normally used, which is indexed by a part of the virtual address - possibly modified according to a hash function - and then the part used for indexing compare the virtual address with the marking of the addressed TLB entry.
  • TLB translation lookaside buffer
  • the real address and the first and second group information are read from the TLB entry.
  • there is a TLB miss and the conversion of the virtual address into a real address is carried out, for example, using page tables from the MMU (FIG. 1).
  • the cache memory is indexed again, specifically by means of the cache index of the virtual address and the second group information. It is expedient to carry out this new indexing of the cache memory only when the virtual group information does not match the second group information assigned to the real address. Steps b) and c) are then repeated for the cache entry (s) addressed in this way (FIG. 4).
  • the second group information of the storage device according to the invention is any, but before the indexing of the cache memory, which is supplied in particular by the TLB and / or the MMU and which receives or derives the second group information from the page tables.
  • a modification of the above access (see claim 4) consists in that if the marking of the cache entry (s) addressed by means of the cache index part and the group information does not match the real address, then only access by indexing the cache memory by means of to try the second group information and the cache index part of the virtual address if the second group information is different from the group information. In any other case, the cache access is terminated and a cache miss is signaled. A group information comparison is provided for the necessary comparison of the second group information with the group information.
  • the cache memory is indexed again using the first group information (and the cache index part) following an access that results in a cache miss.
  • This indexing can be carried out either directly after the first indexing using the group information of the virtual address or after the indexing using the second group information.
  • first or second group information is used to investigate whether the second group information differs from the group information or is identical to the group information is. If the second group information is different from the group information, then the first renewed indexing (second indexing) is carried out using the second group information. If this second indexing has not in turn led to a cache hit, then one becomes Third-party indexing attempted using the first group information (normal case).
  • the indexing with the second group information which in fact has already been attempted with the first indexing and did not lead to success (group information and second group information are identical), are skipped , and the re-indexing of the cache memory (here also called third-party indexing analogously) is carried out using the first group information (special case).
  • the third-party indexing with the first group information is preferably only carried out if the first group information is different both from the group information and from the second group information.
  • the second indexing is always attempted with the first group information, in order to then carry out the third indexing using the second group information if the cache hit has not occurred. It is also possible, in the case of the first renewed indexing, to select, in particular, a random generator controlled between the two options, namely between the second indexing with the second group information and the third indexing with the first group information or the second indexing with the first group information and the third indexing with the second group information. Instead of a random generator or in addition to this, previous hits (cache hit) or non-hits (cache miss) can be taken into account when deciding between the two above possibilities.
  • index the cache memory by a combination of the cache index part of the (real or virtual) address and an additional index, the additional index the address assigned, but is not part of it.
  • the indexing of the cache memory can be influenced in a targeted manner by appropriate selection of the additional index, which provides a possibility for improved utilization of the occupancy.
  • the additional index is e.g. B. supplied by an MMU and / or a TLB, which also provide the real address or the part of the address required to access the cache memory.
  • the appended claims 12 to 15 relate to variants of a cache memory arrangement with first- and second-level cache memory devices of the types according to the invention specified above.
  • FIG. 1 schematically shows the structure of a TLB as it is used for the cache memory
  • FIG. 5 shows, as a block diagram, a second-color cache with a second-color bus for connecting a plurality of second-color cache memories
  • FIG. 10 shows the step of checking for color fidelity in a cache memory according to FIG. 9,
  • FIG. 11 shows the color correction step in a cache memory according to FIG. 9,
  • FIGS. 9 and 10 shows the access step in a cache memory according to FIGS. 9 and
  • FIG. 13 shows a real indexed cache with the address associated additional index.
  • the second-color TLB used to convert the virtual address into the real address differs from conventional TLBs in that it not only contains virtual page numbers, real page numbers and possibly status and access control information (access attributes) (not listed here) per entry ) contains, but also a two-color per virtual page (see also Fig. 1).
  • the TLB delivers the real address (r ', c') and the associated secondary color (c ").
  • TLB is a direct mapped, n-way associative or fully associative TLB.
  • n entries are selected at the same time, and their virtual addresses are compared in parallel with vpn.
  • the hash and selection function is completely eliminated and all TLB entries are checked against vpn at the same time.
  • a TLB entry is reloaded from the page table data structure in the event of a TLB miss. Not only the real address and access attribute, but also the secondary color is transferred from the page table. (ie at least every valid page table entry at the lowest level also contains the selected second color).
  • the second color can be freely selected by the operating system, in particular also in such a way that the above invariance condition is always maintained.
  • the statement applies that if two TLB entries refer to the same real page address, their secondary colors match (invariance condition).
  • v virtual address vpn virtual page number c virtual color group information of the virtual address rpn real page number c 'real color, also called first color (first group information) c "second color (second group information) r' higher part of rpn (without C) c index color (the one Part that is used in addition to the index part of the virtual address to index the cache) ⁇ low-order part of the cache entry number
  • Each Ca ' entry (line) contains a field as a marker. £ and c_, a data field d and other not listed
  • a current cache line is selected by an index i, the more significant bits of which are referred to as index color c become.
  • index color c the more significant bits of which are referred to as index color c become.
  • Virtual, first, second and index colors each have the same number of bits.
  • Step 1 At the beginning of a cache access, the index port (c, ⁇ ) is loaded from the virtual address (see Fig. 2). At the same time, the TLB starts address conversion with vpn as input.
  • Step 2 The CAche entry addressed by (c, ⁇ ) is read out.
  • Step 3 If there was no cache hit in step 2 (in all cases (r ', c') ⁇ (r_, c_)) and the index color differs from the second color (c ⁇ c "), a color correction is attempted ( 4): c is loaded with the secondary dye c "and step 2 is carried out again. Step 4. In any other case, the cache access is aborted and a miss signaled.
  • Step 2 The cache entry addressed by (c, ⁇ ) is read out.
  • Step 3 No cache hit occurred in step 2 (in all cases (r ', c') ⁇ (r ⁇ ) and occurred with this cache
  • Step 3 If there was no cache hit in step 2 (in all cases (r ', c') ⁇ (r_, c_)) and no redirection step occurred with this cache access and
  • Variant 2 If the virtual color is neither first nor second color, the order in which c 'and c "should be tried is rolled:
  • Step 3 No cache hit occurred in step 2 (in all cases (r ', c') ⁇ (r_, c)) and occurred with this cache
  • the decision mechanism in point 3c can function randomly or take previous hits and misses into account.
  • Another variant is that the TLB stores a strategy note in addition to the second color, which is evaluated by the decision mechanism.
  • Each processor's cache places not only the real address but also the secondary color on the bus when it is accessed. This is always possible because the secondary color is supplied by the TLB for read access and can be extracted from the cache index for write access.
  • the problem is therefore solved for multiprocessor systems, provided that the page table trees of all processors do not have contradicting second-color assignments, ie the above-mentioned invariance condition also applies to all processors.
  • bus masters that do not access via virtual addresses, for example DMA or screen processors, must also operate the two-color bus.
  • the TLB cannot supply any secondary color information. Such accesses can then be processed with real color as a secondary color.
  • Another possibility is to use a special secondary color for this, or to read the secondary color information from the page table entries together with the addresses for the table of the next level when the tree is parsed. Under certain circumstances, this can be used to control the allocation of the cache with page table information.
  • the second color bus is then expanded to offer a full set of second colors.
  • the secondary color set must then be saved in the cache. For write through caches, it is sufficient if the TLB saves the respective set.
  • An alternative, albeit very complex and poorly scalable method uses an RTB or a second MMU (with TLB), which derive the respective second color from the real address.
  • the additional index c '''used next to the address r for indexing can be designated with a third color in accordance with the terminology used above.
  • the third color can (but does not have to) be a wider bit field than the previously mentioned second color. It can also be identical to the second color or contain it as part (the whole of course also works exclusively with a third color, ie without a second color).
  • the MMU or the TLB supplies the real address r and the third color c '''(see FIG. 13).
  • the third color c ''' is linked (combined) in the map function with the cache index part of the real address r used for cache indexing. Simple links are e.g. B .:

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

Die Speichervorrichtung weist einen Cache-Speicher auf, der durch den Cache-Index und eine Gruppeninformation der virtuellen Adresse indiziert wird. Die aus der virtuellen Adresse umgesetzte Realadresse enthält eine Erst- und eine Zweitgruppeninformation. Stimmt die Markierung des gemäss obiger Vorschrift durch Indizierung des Cache-Speichers adressierten Cache-Eintrags nicht mit der Realadresse überein, so wird unter Zuhilfenahme der dieser Realadresse zugeordneten Zweitgruppeninformation (und des Cache-Indexes der virtuellen Adresse) erneut indiziert. Stimmt auch dann die Markierung des derart adressierten Cache-Eintrags nicht mit der Realadresse überein, wird ein Cache-Miss signalisiert.

Description

Cache-Speichervorrichtung zum Speichern von Daten
Die Erfindung betrifft eine Cache-Speichervorrichtung mit einem virtuell bzw. real indizierten und real markierten Cache-Spei¬ cher.
Moderne Prozessoren benötigen Cache-Speicher, um die Lücke zwi¬ schen schnellen Prozessoren und langsamen Hauptspeichern auszu¬ gleichen.
Bei direct-mapped Caches wird (wie in den Fign. 6 und 7 ge- zeigt) mit Hilfe einer map-Funktion aus der realen oder vir¬ tuellen Adresse a ein Cache-Index berechnet und damit eine Zeile des Caches angewählt. Dann wird a mit der Adresse des augenblicklich mit dieser Cache-Zeile assoziierten Speicherbe¬ reichs (der Markierung des Cache-Eintrags) verglichen. Bei Gleichheit liegt ein Treffer vor (und die Cache-Zeile wird an¬ stelle des Hauptspeichers benutzt), sonst ein Miss.
Meistens wird (a mod Cache-Größe)/Zeilengröße als map-Funktion benutzt. Dazu braucht im Cache nicht die vollständige virtuelle Adresse gespeichert zu werden, sondern es reicht a/Cache-Größe.
Direct-mapped Caches sind einfacher, führen aber zu höheren Miss-Raten als n-Wege Caches . Diese bestehen prinzipiell aus n entsprechend kleineren direct mapped Cache-Blöcken. Dabei wird sichergestellt, daß sich jedes Hauptspeicherelement in höch¬ stens einem Block befindet. Da die map-Funktion jeweils n Cache-Zeilen indiziert, können jeweils bis zu n Elemente mit map-äquivalenten Adressen im Cache enthalten sein. Diese n- fache Assoziativität verringert die Wahrscheinlichkeit von Clashes und vergrößert entsprechend die Trefferrate.
Bekannt sind real und virtuell indizierte Caches. Beim real indizierten Cache (Fig. 6) wird die vom Prozessor gelieferte virtuelle Adresse zuerst vom Translation Lookaside Buffer (TLB) in eine Realadresse umgesetzt. Danach wird der Cache mit dieser Realadresse angesprochen.
Beim virtuell indizierten Cache (Fig. 7) wird der Cache direkt mit der virtuellen Adresse angesprochen. Eine Umsetzung in die entsprechende Realadresse erfolgt nur bei einem Cache-Miss. Der Vorteil eines virtuell indizierten Caches ist die höhere Ge¬ schwindigkeit, da der Umsetzschritt durch den TLB entfällt. Nachteile treten bei Synonymen bzw. Aliasing und bei Multipro- zessor-Systemen auf.
Ein real indizierter Cache hat diese Nachteile zwar nicht, ver¬ langt aber einen vollständigenAdreßumsetzungsschritt (virtuell → real) des TLBs bevor der Cache-Zugriff eingeleitet werden kann.
Der heutzutage favorisierte Cache-Typ ist virtuell indiziert und real (physisch) markiert. Er ist genauso schnell wie ein virtuell indizierter und virtuell markierter Cache, vermeidet aber die meisten seiner Nachteile, insbesondere Probleme mit Multiprozessorsystemen, Synonymen, Sharing und Kohärenz.
Ein virtuell indizierter und real markierter Cache erlaubt es, TLB- und Cache-Zugriff parallel ablaufen zu lassen (siehe Fig. 8) . Die Befehls-Pipeline des Prozessors ist deshalb kürzer, so daß die Latenzzeit eines Befehls in der Regel um einen Takt sinkt und die Prozessorleitung entsprechend ansteigt.
Der Mechanismus bleibt einfach, solange die für die Indizierung des Caches benötigten Adreßbits (i) alle im Bereich des Adreß- offsets (Adresse innerhalb einer Seite) liegen. Da dieser Adreßteil durch die Umsetzung der virtuellen in die Realadresse nicht verändert wird, kann der Cache damit auch schon vor dem Umsetzschritt des TLBs adressiert (indiziert) werden. Erst am Ende von Cache-Zugriff und parallelem TLB-Umsetzschritt wird geprüft, ob die mit dem Cache-Eintrag assoziierte Realadresse (die Markierung) mit der vom TLB gelieferten Realadresse über¬ einstimmt. Hierbei brauchen nur die an den Indexteil (i) an¬ schließenden hoherwertigen Bits der Adresse verglichen zu wer¬ den, da der durch (i) indizierte Cache-Eintrag nur mit Adressen assoziiert werden kann, deren Indexbits den Wert (i) haben. Dementsprechend brauchen im Cache auch nur die hoherwertigen Bits als Markierung (reale Adresse) gespeichert zu sein.
Ein n-Wege assoziativer Cache dieses Typs kann lediglich bis zu n x 2P groß sein, wobei 2P die Seitengröße ist. Eine Vergröße¬ rung des Caches kann durch größere Seiten oder erhöhte Assozia- tivität erreicht werden.
Eine interessantere Technik ist allerdings Page Coloring. Damit wird das Verfahren bezeichnet, Seiten stets derart im Realspei¬ cher anzulegen, daß die niederwertigen Adreßbits von virtueller und realer Seitenadresse identisch sind (siehe Fig. 9) . Vir¬ tuelle Seitennummer (vpn) und Cache-Index (i) überschneiden sich hierbei. Der überlappende Teil ist in der. Fig. 9 schwarz dargestellt. Der entsprechende Teil der virtuellen Adresse wird virtuelle FarJbe c, der der realen Adresse reale Farbe c ' ge¬ nannt. Bei farbtreuer Allokation, d.h. wenn virtuelle und reale Farbe übereinstimmen, wird die oben erwähnte Größenbegrenzung n x 2P aufgehoben.
Wenn, wie in Fig. 10 gezeigt, virtuelle und reale Farbe zusätz¬ lich verglichen werden, kann bei der Markierung (reale Adresse) auf die Speicherung der entsprechenden Farb-Bits verzichtet werden und es brauchen nur die hoherwertigen Bits (r') der realen Seitennummer mit der Markierung verglichen zu werden.
Natürlich sollte ein Cache auch bei nicht perfekt farbtreuer Allokation funktionieren. Wenn deshalb der erste Cache-Zugriff zu einem Miss führt und die vom TLB gelieferte reale Farbe C sich von der virtuellen Farbe c unterscheidet, müßte ein farb¬ korrigierter Cache-Zugriff versucht werden (siehe Fig. 11) . Falsch kolorierte Seiten könnten also benutzt werden, würden aber einen zusätzlichen Schritt beim Cache-Zugriff benötigen (siehe Fig. 12) .
Man beachte, daß unter gewissen Umständen nicht farbtreue Allo¬ kation zwingend notwendig ist, z.B. wenn zwei virtuelle Seiten unterschiedlicher Farbe auf dieselbe Realseite abgebildet wer¬ den müssen. Damit kommt es immer wieder zu Farbkorrekturen, was zeitaufwendig ist und den Cache-Zugriff verzögert.
Der Erfindung liegt die Aufgabe zugrunde, einen Cache zu kon¬ struieren, der virtμell bzw. real indiziert und real markiert ist und auch bei nicht farbtreu allokierten Seiten einen schnellen Cache-Zugriff erlaubt bzw. die Gefahr von Clashes reduziert.
Zur Lösung dieser Aufgabe wird eine Speichervorrichtung mit den Merkmalen des Anspruchs 1 vorgeschlagen; die Merkmale vorteil¬ hafter Weiterbildungen sind jeweils in den Unteransprüchen aufgeführt.
Bei der erfindungsgemäßen Speichervorrichtung ist jeder aus einer virtuellen Adresse umgesetzten Realadresse neben einer Erstgruppeninformation (oben als "Realfarbe" bezeichnet) eine Zweitgruppeninformation ("Zweitfarbe") zugeordnet. Diese beiden Informationen werden insbesondere von der MMU (Memory Manage¬ ment Unit) aus den. Page Tables abgeleitet und im Falle der Verwendung eines Translation-Lookaside-Buffers (TLB) in diesen eingeschrieben. Die Farbkorrektur wird durchgeführt, und zwar indem dann, wenn keine Markierung des bzw. der adressierten Cache-Einträge mit der aus der virtuellen Adresse umgesetzten Realadresse übereinstimmt und die Gruppeninformation ("virtuel¬ le Farbe") der virtuellen Adresse nicht mit der der umgesetzten Realadresse zugeordneten Zweitgruppeninformation (Zweitfärbe) übereinstimmt, der Cache-Speicher mittels des Cache-Indexteils und der Zweitgruppeninformation erneut indiziert wird und die Markierung bzw. Markierungen des bzw. der so adressierten Cache-Einträge mit der aus der virtuellen Adresse umgesetzten Realadresse verglichen wird bzw. werden.
Bei der erfindungsgemäßen Speichervorrichtung wird ein Zugriff auf den Cache-Speicher mittels einer virtuellen Adresse wie folgt versucht:
a) Zunächst werden eine der Assoziativität des Cache-Speichers entsprechende Anzahl von Cache-Einträgen adressiert, und zwar durch Indizierung des Cache-Speichers mittels des Cache-Index und der Gruppeninformation, die beide Bestand¬ teil der virtuellen Adresse sind oder aus der virtuellen Adresse bzw. aus Teilen derselben abgeleitet werden (Fig. 2) .
Dann wird die virtuelle Adresse bzw. genauer gesagt deren die virtuelle Seitennummer repräsentierender Seitennummer- Adreßteil in eine Realadresse bzw. genauer gesagt in einen die reale Seitennummer repräsentierenden Seitennummer-Real- adreßteil umgesetzt. Dieser Seitennummer-Realadreßteil bein¬ haltet als einen Teil die Erstgruppeninformation. Bei der Umsetzung wird auch die zugehörige Zweitgruppeninformation geliefert.
b) Die sich durch Umsetzen der virtuellen Adresse ergebende Realadresse wird mit der Markierung jedes adressierten Cache-Eintrags verglichen.
Für die Umsetzung der virtuellen Adresse in die Realadresse wird normalerweise ein Translation Lookaside Buffer (TLB) verwendet, der durch einen Teil der virtuellen Adresse - ge¬ gebenenfalls gemäß einer Hash-Funktion modifiziert - indi¬ ziert wird, um dann den zur Indizierung verwendeten Teil der virtuellen Adresse mit der Markierung des adressierten TLB- Eintrags zu vergleichen. Bei Gleichheit werden die Real- adresse und die Erst- sowie die Zweitgruppeninformation aus dem TLB-Eintrag ausgelesen. Bei Ungleichheit liegt ein TLB- Miss vor, und die Umsetzung der virtuellen Adresse in eine Realadresse wird z.B. mit Hilfe von Page Tables von der MMU durchgeführt (Fig. 1) .
c) Stimmt die umgesetzte Realadresse mit der Markierung des adressierten Cache-Eintrags bzw. einer der Markierungen der adressierten Cache-Einträge überein, so liegt ein Cache-Hit vor und es wird -aus dem Datenfeld des betreffenden Cache- Eintrags gelesen bzw. in das Datenfeld geschrieben, was von hier nicht näher erläuterten und an sich bekannten Statusin¬ formationen und Zugriffskontrollvariablen abhängt.
d) Andernfalls wird der Cache-Speicher erneut indiziert, und zwar mittels des Cache-Indexes der virtuellen Adresse und der Zweitgruppeninformation. Zweckmäßig ist es, diese er¬ neute Indizierung des Cache-Speichers nur dann durchzufüh¬ ren, wenn die virtuelle Gruppeninformation mit der der Real- adresse zugeordneten Zweitgruppeninformation nicht überein¬ stimmt. Für den bzw. die derart adressierten Cache-Einträge wird bzw. werden dann die Schritte b) und c) wiederholt (Fig. 4) .
e) Liegt nach erneuter Indizierung wiederum keine Übereinstim¬ mung der Realadresse mit der Markierung bzw. einer der Mar¬ kierungen vor, so wird ein Cache-Miss signalisiert und der Zugriff abgebrochen.
Mit der Erfindung lassen sich Hauptspeicher bei großen Cache- Speichern besser auslasten, ohne daß die Cache-Zugriffszeiten vergrößert werden. Dies liegt daran, daß nicht mehr nur farb¬ treue, sondern auch andere definierte nicht-farbtreue Alloka- tionen (über die Zweitgruppeninformation) effizient behandelt werden. Die Zweitgruppeninformation der erfindungsgemäßen Spei- chervorrichtung ist eine beliebige, aber vor der Indizierung des Cache-Speichers festgelegte Information, die insbesondere vom TLB und/oder der MMU geliefert wird, welche die Zweitgrup¬ peninformation aus den Page Tables erhält bzw. ableitet.
Eine Modifikation des obigen Zugriffs (siehe Anspruch 4) be¬ steht darin, bei Nicht-Übereinstimmung der Markierung des oder der mittels des Cache-Indexteils und der Gruppeninformation adressierten Cache-Einträge mit der Realadresse nur dann einen Zugriff durch Indizierung des Cache-Speichers mittels der Zweitgruppeninformation und dem Cache-Indexteil der virtuellen Adresse zu versuchen, wenn die Zweitgruppeninformation ver¬ schieden ist von der Gruppeninformation. In jedem anderen Fall wird der Cache-Zugriff abgebrochen und ein Cache-Miss signali¬ siert. Für den erforderlichen Vergleich der Zweitgruppeninfor- mation mit der Gruppeninformation ist ein Gruppeninformations- vergleich vorgesehen.
Bei einer alternativen Weiterbildung der Erfindung wird im An¬ schluß an einen zu einem Cache-Miss geführten Zugriff die er- neute Indizierung des Cache-Speichers mittels der Erstgruppen- information (und dem Cache-Indexteil) durchgeführt. Diese Indi¬ zierung kann entweder direkt nach der Erst-Indizierung mittels der Gruppeninformation der virtuellen Adresse oder nach der Indizierung mittels der Zweitgruppeninformation durchgeführt werden.
Vorzugsweise wird nach der mittels der Gruppeninformation er¬ folgten (und nicht zu einem Cache-Hit geführt habenden) Erst- Indizierung und vor der erneuten Indizierung mittels Erst- oder Zweitgruppeninformationuntersucht, ob die Zweitgruppeninforma¬ tion von der Gruppeninformation unterschiedlich bzw. mit der Gruppeninformation identisch ist. Ist die Zweitgruppeninforma¬ tion von der Gruppeninformation verschieden, so wird die erste erneute Indizierung (Zweit-Indizierung) mittels der Zweitgrup- peninformation durchgeführt. Hat diese Zweit-Indizierung wiede¬ rum nicht zu einem Cache-Hit geführt, so wird anschließend eine Dritt-Indizierung mittels der Erstgruppeninformation versucht (Normalfall) . Ist hingegen bei Gleichheit von Zweitgruppenin¬ formation und Gruppeninformation die Erstgruppeninformation unterschiedlich zur Gruppeninformation, so wird die Indizierung mit der Zweitgruppeninformation, die faktisch mit der Erst- Indizierung bereits versucht wurde und nicht zum Erfolg führte (Gruppeninformation und Zweitgruppeninformation sind iden¬ tisch) , übersprungen, und die erneute Indizierung des Cache- Speichers (hier analog zu oben auch Dritt-Indizierung genannt) mittels der Erstgruppeninformation durchgeführt (Spezialfall) . Vorzugsweise wird in beiden zuvor beschriebenen Fällen die Dritt-Indizierung mit der Erstgruppeninformation nur dann durchgeführt, wenn die Erstgruppeninformation sowohl von der Gruppeninformation als auch von der Zweitgruppeninformation verschieden ist.
Alternativ wird die Zweit-Indizierung stets mit der Erstgrup¬ peninformation versucht, um dann bei nicht erfolgtem Cache-Hit die Dritt-Indizierung mittels der Zweitgruppeninformation durchzuführen. Es ist auch möglich, bei der ersten neuerlichen Indizierung insbesondere Zufallsgenerator gesteuert zwischen den beiden Möglichkeiten auszuwählen, nämlich zwischen der Zweit-Indizierung mit der Zweitgruppeninformation und der Dritt-Indizierung mit der Erstgruppeninformation oder der Zweit-Indizierung mit der Erstgruppeninformation und der Dritt- Indizierung mit der Zweitgruppeninformation. Anstelle eines Zufallsgenerators oder zusätzlich zu diesem können bei der Entscheidung zwischen den beiden obigen Möglichkeiten voraus¬ gehende Treffer (Cache-Hit) bzw. Nichttreffer (Cache-Miss) Berücksichtigung finden.
Zur besseren Ausnutzung der Belegung eines Cache-Speichers ist gemäß einer alternativen Ausgestaltung der Erfindung vorge¬ sehen, den Cache-Speicher durch eine Kombination aus dem Cache- Indexteil der (realen oder virtuellen) Adresse und einem Zu¬ satzindex zu indizieren, wobei der Zusatzindex der Adresse zugeordnet, aber nicht deren Bestandteil ist. Durch ent¬ sprechende Wahl des Zusatzindexes läßt sich die Indizierung des Cache-Speichers gezielt beeinflussen, womit eine Möglichkeit zur verbesserten Belegungsausnutzung gegeben ist. Der Zusatz- index wird z. B. von einer MMU und/oder einem TLB geliefert, die auch die Realadresse bzw. den zum Zugreifen auf den Cache- Speicher benötigten Teil der Adresse liefern.
Die beigefügten Ansprüche 12 bis 15 betreffen Varianten einer Cach -Speicheranordnungmit First- undSecond-Level-Cache-Spei¬ chervorrichtung der oben angegebenen erfindungsgemäßen Arten.
Nachfolgend wird anhand der Zeichnung ein Ausführungsbeispiel der Erfindung näher erläutert. Im einzelnen zeigen:
Fig. 1 schematisch den Aufbau eines TLB so, wie er für den Cache-Speicher verwendet wird,
Fig. 2 den Vorbereitungsschritt für die Inidzierung des Cache- Speichers,
Fig. 3 den ersten Zugriffsschritt beim Cache-Speicher,
Fig. 4 den Farbkorrekturschritt beim Cache-Speicher,
Fig. 5 als Blockschaltbild einen Zweitfärben-Cache mit Zweit- farbenbus zur Verbindung meherer Zweitfarben-Cache- Speicher,
Fig. 6 den Aufbau eines real indizierten Cache-Speichers,
Fig. 7 den Aufbau eines virtuelle indizierten und virtuell markierten Cache-Speichers,
Fig. 8 den Aufbau eines virtuell indizierten und real markier¬ ten Cache-Speichers, - 10
Fig. 9 den Aufbau eines auf farbtreuer Allokation basierenden Cache-Speichers,
Fig. 10 den Schritt der Prüfung auf Farbtreue bei einem Cache- Speicher nach Fig. 9,
Fig. 11 den Farbkorrektur-Schritt bei einem Cache-Speicher nach Fig. 9,
Fig. 12 den Zugriffsschritt bei einem Cache-Speicher nach Fig. 9 und
Fig. 13 einen real indizierten Cache mit der Adresse zugeordne¬ tem Zusatzindex.
Der zur Umsetzung der virtuellen Adresse in die Realadresse verwendete Zweitfarben-TLB unterscheidet sich von konventio¬ nellen TLBs dadurch, daß er pro Eintrag nicht nur virtuelle Seitennummer, reale Seitennummer und eventuell (hier nicht auf- geführte) Status- und Zugriffskontrollinformationen (Access- Attribute) enthält, sondern zusätzlich noch eine Zwei tfarbe pro virtueller Seite (siehe auch Fig. 1) . Bei einem Hit liefert der TLB die Realadresse (r' , c ' ) und die zugehörige Zweitfarbe (c") .
Es spielt keine Rolle, ob es sich bei dem TLB um einen direct mapped, n-Wege assoziativen oder vollständig assoziativen TLB handelt. Im n-Wege Fall werden gleichzeitig n Einträge ange¬ wählt, und ihre virtuellen Adressen werden parallel mit vpn verglichen. Im voll-assoziativen Fall entfällt die Hash- und Auswahlfunktion vollständig und alle TLB-Einträge werden gleichzeitig gegen vpn geprüft.
Unabhängig von der verwandten Page Table Struktur wird bei einem TLB-Miss ein TLB-Eintrag neu aus der Page Table Daten- Struktur geladen. Dabei wird aus der Page Table nicht nur Real- adresse und Zugriffsattribut, sondern auch die Zweitfarbe über- nommen (d.h. mindestens jeder gültige Page Table Eintrag auf der niedrigsten Stufe enthält auch die gewählte Zweitfärbe) .
Die Zweitfarbe kann vom Betriebssystem frei gewählt werden, insbesondere auch derart, daß obige Invarianzbedingung stets erhalten bleibt. Es gilt die Aussage, daß, wenn zwei TLB-Ein- träge auf dieselbe reale Seitenadresse verweisen, ihre Zweit¬ farben übereinstimmen (Invarianzbedingung) .
Grundidee ist, für die Allokation im direct mapped oder n-Wege assoziativen Cache stets die Zweitfarbe und nicht die Erstfarbe (reale Farbe) zu verwenden. Zugriffe über virtuelle Adressen, die mit der Zweitfarbe übereinstimmen, sind dann schnell; ande¬ re brauchen einen zusätzlichen Farbkorrektur-Schritt (bei c ' = c" verhält sich das System wie ein konventioneller Cache) .
Bezeichnungen (siehe auch Fig. 2) :
v virtuelle Adresse vpn virtuelle Seitennummer c virtuelle Farbe (Gruppeninformation der virtuellen Adresse rpn reale Seitennummer c' reale Farbe, auch Erstfärbe genannt (Erstgruppeninforma¬ tion) c" Zweitfarbe (Zweitgruppeninformation) r' höherwertiger Teil von rpn (ohne C) c Indexfarbe (derjenige Teil, der neben dem Indexteil der virtuellen Adresse zum Indizieren des Cache benutzt wird) ϊ niederwertiger- Teil der Cache-Eintrags-Nummer
Jeder Ca 'ιe-Eintrage (Zeile) enthält als Markierung je ein Feld .£ und c_, ein Datenfeld d sowie weitere nicht aufgeführte
Statusfelder.
Eine aktuelle Cache-Zeile wird jeweils durch einen Index i aus¬ gewählt, dessen höherwertige Bits als Indexfarbe c bezeichnet werden. Virtuelle, Erst-, Zweit- und Indexfarbe haben jeweils gleichviele Bits.
Schritt 1. Zu Beginn eines Cache-Zugriffs wird der Indexport (c, ϊ) aus der virtuellen Adresse geladen (siehe Fig. 2) . Gleichzeitig startet der TLB eine Adreßum- setzung mit vpn als Input.
Schritt 2. Der durch (c,ϊ) adressierte CAche-Eintrag wird aus- gelesen. Die vom TLB gelieferte reale Seitenadresse
(r' , c ' ) wird mit der im Cache-Eintrag gespeicherten Realadresse (^, 0^ und die auch vom TLB gelieferte Zweitfärbe c" wird mit der Indexfarbe c verglichen (Fig. 3) . Bei Gleichheit der Realadressen ( (r' , c ' ) = (rif Ct) ) handelt es sich um einen Cache-Treffer, d.h. die Daten des Caches werden übernommen (Lese¬ zugriff) oder die neuen Daten in den Cache ge¬ schrieben (Schreibzugriff) . Der Cache-Zugriff ist damit beendet. Handelt es sich bei dem Cache-Spei- eher um einen n-Wege assoziativen Cache, wird die vom TLB gelieferte Realadresse parallel mit den in den n gleichzeitig adressierten Einträgen enthalte¬ nen Realadressen verglichen. Ein Cache-Treffer liegt vor, wenn ein Vergleich Übereinstimmung lie- fert. Der zugehörige Eintrag wird ausgelesen oder neu geschrieben, was von Access-Attributen und Statusinformationen abhängt.
Schritt 3. Trat in Schritt 2 kein Cache-Treffer auf (in allen Fällen (r' , c ' ) ≠ (r_, c_) ) und unterscheidet sich die Indexfarbe von der Zweitfärbe ( c ≠ c") , wird eine Farbkorrektur versucht (Fig. 4) : c wird mit der Zweitfärbe c" geladen und es wird wiederum ein Schritt 2 ausgeführt. Schritt 4. In jedem anderen Fall wird der Cache-Zugriff abge¬ brochen und Miss signalisiert.
Aus Gründen der Übersichtlichkeit wurde nur das Auslesen und Schreiben ganzer Cache-Einträge beschrieben. Unter Berücksich¬ tigung niederwertiger Adreßbits können natürlich nach dem üb¬ lichen und bekannten Verfahren auch nur Teile eines Eintrags gelesen oder geschrieben werden. Auswirkungen auf die hier beschriebene Steuerlogik treten nicht auf.
Wahlfreie Allokation von Cache-Einträgen anhand von Erst- oder Zweitfarbe (auch innerhalb einer Seite gemischt) wird durch Modifikation der obigen Schritte 2 und 3 möglich. Dazu wird wie folgt verfahren:
Schritt 2. Der durch ( c, ϊ) adressierte Cache-Eintrag wird aus¬ gelesen. Die vom TLB gelieferte reale Seitenadresse (r' , c ' ) wird mit der im Cache-Eintrag gespeicherten Realadresse (ri t cd) , die Erstfarbe c ' mit der Indexfarbe c und die auch vom TLB gelieferte Zweit- färbe c" ebenfalls mit der Indexfarbe c verglichen. Bei Gleichheit der Realadressen ( (r' , c ' ) = (rt f C^) ) handelt es sich um einen Cache-Treffer, d.h. die Daten des Caches werden übernommen (Lesezugriff) oder die neuen Daten in den Cache geschrieben (Schreibzugriff) . Der Cache-Zugriff ist damit be¬ endet.
Schritt 3. Trat in Schritt 2 kein Cache-Treffer auf (in allen Fällen (r' , c ' ) ≠ (r ^ ) und trat bei diesem Cache-
Zugriff noch kein Umleitungsschritt auf und (a) ist die Indexfarbe identisch mit der Zweitfarbe (c = c") und unterscheiden sich Erst- und Zweitfarbe (c' ≠ c") , wird eine Umleitung ver- sucht: σ wird mit der Erstfarbe c ' geladen, ein Umleitungsschritt wird vermerkt und es wird wiederum ein Schritt 2 ausgeführt; (b) oder unterscheidet sich die Indexfarbe von der Zweitfarbe ( c ≠ c") , wird eine Farbkorrektur versucht (Fig. 4) : c wird mit der Zweitfarbe c " geladen und es wird wiederum ein Schritt 2 aus¬ geführt.
Variante 1: Erst- und Zweitfarbe tauschen ihre Rollen
Schritt 3. Trat in Schritt 2 kein Cache-Treffer auf (in allen Fällen (r' , c ' ) ≠ (r_ , c_) ) und trat bei diesem Cache- Zugriff noch kein Umleitungsschritt auf und
(a) ist die Indexfarbe identisch mit der Erstfarbe ( c = c") und unterscheiden sich Erst- und Zweitfarbe (c' ≠ c") , wird eine Umleitung ver¬ sucht: c wird mit der Zweitfarbe c " geladen, ein Umleitungsschritt wird vermerkt und es wird wiederum ein Schritt 2 ausgeführt; oder
(b) unterscheidet sich die Indexfarbe von der Erst¬ farbe ( c ≠ c ' ) , wird eine Farbkorrektur ver¬ sucht: c wird mit der Erstfärbe c' geladen und es wird wiederum ein Schritt 2 ausgeführt.
Variante 2: Ist die virtuelle Farbe weder Erst- noch Zweitfar¬ be, wird gewürfelt, in welcher Reihenfolge c ' und c" versucht werden sollen:
Schritt 3. Trat in Schritt 2 kein Cache-Treffer auf (in allen Fällen (r' , c ' ) ≠ (r_, c ) ) und trat bei diesem Cache-
Zugriff noch kein Umleitungsschritt auf und (a) ist die Indexfarbe identisch mit der Erstfarbe ( δ = c') und unterscheiden sich Erst- und Zweitfärbe ( c ' ≠ c") , wird eine Umleitung ver- sucht: c wird mit der Zweitfarbe c" geladen, ein Umleitungsschritt wird vermerkt und es wird wiederum ein Schritt 2 ausgeführt; oder
(b) ist die Indexfarbe indentisch mit der Zweitfar¬ be ( c = c") und unterscheiden sich Erst- und Zweitfärbe ( C ≠ c") , wird eine Umleitung ver¬ sucht: c wird mit der Erstfärbe c ' geladen, ein Umleitungsschritt wird vermerkt und es wird wiederum ein Schritt 2 ausgeführt; oder
(c) unterscheidet sich die Indexfarbe von Erst- und Zweitfarbe (c ≠ C und c ≠ c") , wird eine Farb¬ korrektur versucht, indem c mit der Erstfärbe C oder mit der Zweitfarbe c" geladen wird, und es wird wiederum ein Schritt 2 ausgeführt.
Der Entscheidungsmechanismus in Punkt 3c kann zufällig funk¬ tionieren oder vorausgegangene Treffer und Nichttreffer berück¬ sichtigen. Eine weitere Variante besteht darin, daß der TLB außer der Zweitfarbe auch einen Strategiehinweis abspeichert, der vom Entscheidungsmechanismus ausgewertet wird.
Für Multiprozessorsysteme mit mehreren Prozessoren und diesen jeweils direkt zugeordneten Cache-Speiehern gilt, daß fast alle Cache-Kohärenzprotokolle Kenntnis der Zweitfarbe erfordern. So¬ mit muß nicht nur der Prozessor, sondern auch der Speicherbus neben der Real-adresse auch die Zweitfarbe liefern (Fig. 5) . Zur Realisierung wird der externe Adreßbus um einen Zweitfar- benbus erweitert. Wird dieser konsistent bedient, kann jedes auf konventionellen real markierten Caches funktionierende Ko¬ härenzprotokoll ohne Mehraufwand realisiert werden.
Der Cache jedes Prozessors legt beim Zugriff nicht nur die Realadresse sondern auch die Zweitfarbe auf den Bus. Das ist immer möglich, denn die Zweitfarbe wird bei Lesezugriffen vom TLB geliefert und kann bei Schreibzugriffen aus dem Cache-Index extrahiert werden. Das Problem ist also für Multiprozessor-Systeme gelöst, unter der Voraussetzung, daß die Page Table Bäume aller Prozessoren keine widersprüchlichen Zweitfärben-Zuordnungen haben, d.h. die oben aufgeführten Invarianzbedingung auchprozessorübergreifend gilt.
Aus Konsistenzgründen müssen auch Busmaster, die nicht über virtuelle Adressen zugreifen, beispielsweise DMA oder Bild¬ schirmprozessoren, den Zweitfarbenbus bedienen.
Die einfachste Lösung ist, als Zweitfarbe die Realfarbe zu nehmen und das Konsistenzproblem dem Betriebssystem zu über¬ lassen. Dieses muß solche Bereiche dann entsprechend allokieren (Zweitfärbe = Realfarbe) oder aber die Caches vorher flushen.
Solche Einschränkungen kann man durch Versorgung der ent¬ sprechenden Controller mit Zweitfarbeninformation vermeiden. Bei der Programmierung eines DMA-Baustein würde man dann pro Speicherbereich nicht nur Adresse und Länge, sondern auch die Zweitfarbe programmieren.
Bei Zugriffen der MMU auf die Page Tables kann der TLB keine Zweitfarbeninformation liefern. Solche Zugriffe können dann mit Realfarbe als Zweitfarbe abgewickelt werden.
Eine andere Möglichkeit ist, dafür eine spezielle Zweitfarbe zu verwenden oder aber die Zweitfarbeninformation beim Parsieren des Baumes zusammen mit den Adressen für die Tabelle der näch¬ sten Stufe aus den Page Table Einträgen auszulesen. Damit kann unter Umständen die Belegung des Caches mit Page Table Informa¬ tionen gesteuert werden.
Soll die Einschränkung aufgegeben werden, daß die Zweitfarbe eines Realbereichs für alle zugreifenden Prozessoren identisch ist, kann man in jedem Page Table Eintrag einen Satz von Zweit- färben anstelle einer einzigen abspeichern. Jeder Prozessor wird um ein Register erweitert, das angibt, welcher Eintrag des Zweitfarbensatzes für diesen Prozessor gültig ist (somit kann der Zweitfarbensatz deutlich kleiner als die Zahl der Prozesso¬ ren sein) .
Der Zweitfarbenbus wird dann so erweitert, daß er einen ganzen Satz von Zweitfarben anbietet. Bei write back Caches muß dann allerdings der Zweitfarbensatz im Cache abgespeichert werden. Bei write through Caches reicht es, wenn der TLB den jeweiligen Satz speichert.
Eine alternative, allerdings sehr aufwendige und schlecht ska¬ lierbare Methode verwendet einen RTB oder eine zweite MMU (mit TLB) , die die jeweilige Zweitfärbe aus der Realadresse ablei- ten.
Anhand von Fig. 13 soll auf eine weitere Ausführungsform eines in diesem Falle real indizierten Cache-Speichers eingegangen werden.
Die Idee, die Cache Allokation nicht nur durch die Adresse, sondern auch durch eine Information zu steuern, die zusätzlich zur Realadresse in den Page Table Einträgen enthalten ist, kann auch für real indizierte Caches eingesetzt werden. Zwar be- schleunigt sie dann den einzelnen Cachezugriff im Trefferfall nicht, erlaubt aber durch Clash-Reduzierung eine bessere Aus¬ lastung und höhere Hit-Rate. Diese Variante ist insbesondere für Second-Level-Caches interessant.
Der neben der Adresse r für die Indizierung benutzte Zusatz- index c' ' ' kann entsprechend der oben verwandten Terminologie mit Drittfarbe bezeichnet werden. Die Drittfarbe kann (muß aber nicht) ein breiteres Bitfeld sein .als die früher aufgeführte Zweitfarbe. Sie kann auch identisch mit der Zweitfarbe sein oder sie als Teil enthalten (das Ganze funktioniert natürlich auch ausschließlich mit Drittfarbe, d. h. ohne Zweitfarbe) . Die MMU bzw. der TLB liefert die Realadresse r und die Dritt- färbe c ' ' ' (siehe Figur 13). Die Drittfarbe c ' ' ' wird in der map-Funktion mit dem zur Cache-Indizierung verwandten Cache- Indexteil der Realadresse r verknüpft (kombiniert) . Einfache Verknüpfungen sind z. B.:
1. Ersetzen eines Teils von r durch c ' ' ' .
2 . Exklusives Odern eines Teils von r mit c ' ' ' .
3. Addition eines Teils von r mit c ' ' ' .

Claims

ANSPRUCHE
Cache-Speichervorrichtung zum Speichern von Daten, mit einem ein- oder mehrweg-assoziativen Cache-Speicher, der durch vorbestimmte Bits einer mehrere Bits aufwei¬ senden virtuellen Adresse (v) indizierbar ist, die einen Cache-Indexteil ( ϊ) zum Adressieren eines von mehreren jeweils mindestens eine Markierung (r±, c und mindestens ein Datenfeld (d umfassenden Cache- Einträgen des Cache-Speichers und einen eine virtuelle Seitennummer repräsentierenden Seitennummer-Adreßteil (vpn) aufweist, welcher eine Gruppeninformation (c) zur Spezifikation einer von mehreren Gruppen enthält, zu der die durch den Seitennummer-Adreßteil (vpn) der vir¬ tuellen Adresse (v) repräsentierte virtuelle Seite ge¬ hört, \ obei die virtuelle Adresse (v) in eine mehrere Bits aufweisende Realadresse umsetzbar ist, der eine Erst- und eine Zweitgruppeninformation ( c ' , c") zugeord¬ net ist, wobei der Cache-Speieher mindestens einen Markierungs¬ vergleicher zum Vergleichen der Markierung oder vorbe¬ stimmter Bits der Markierung eines durch den Cache- Indexteil (i) und durch die Gruppeninformation der vir¬ tuellen Adresse (v) oder die Erst- oder Zweitgruppenin¬ formation indizierten Cache-Eintrags mit vorbestimmten Bits (r' , c ' ) einer aus der virtuellen Adresse umgesetz¬ ten Realadresse aufweist und eine Cache-Adressierung gemäß der folgenden Schritte versucht wird: a) mittels des Cache-Indexteils (i) und der Gruppen¬ information (c) der virtuellen Adresse (v wird der Cache-Speicher indiziert, und pro Weg des Cache- Speichers wird ein Cache-Eintrag adressiert, b) die Markierungen bzw. deren vorbestimmte Bits sämtlicher derart adressierter Cache-Einträge werden in den zugehörigen Markierungsvergleichern mit den vorbestimmten Bits (r' , c ' ) der aus der vir tuellen Adresse (v) umgesetzten Realadresse ver glichen, c) bei Übereinstimmung einer der Markierungen (ri t c_ mit vorbestimmten Bits (r' , c ' ) der Realadress liegt ein Cache-Hit vor und die Cache-Adressierun ist beendet, wobei Daten in das durch diese Markie rung spezifizierte Datenfeld (d) einschreibbar ode aus diesem Datenfeld (d) auslesbar sind, d) liegt in Schritt b) keine Übereinstimmung vor, s wird der Cache-Speicher mittels des Cache-Index teils (i) der virtuellen Adresse (v) und der Zweit gruppeninformation ( c") indiziert und die Schritt b) und c) für den oder die derart adressierte Cache-Einträge durchgeführt, e) ist in dem dabei durchgeführten Schritt b) wiederu keine Übereinstimmung gegeben, so liegt ein Cache Miss vor und die Cache-Adressierung wird abge brochen.
2. Cache-Speichervorrichtung nach Anspruch 1, dadurch gekenn zeichnet, daß zum Umsetzen einer virtuellen Adresse i eine Realadresse eine Translation-Lookaside-Buffer- (TLB )Einheit einerMemory-Management-Unit- (MMU-)Einheitvorge sehen ist, die neben der Realadresse oder Teilen der Real- adresse auch die dieser zugeordneten Erst- und Zweitgrup- peninformationen (c' , c") liefert.
3. Cache-Speichervorrichtung nach Anspruch 2, dadurch gekenn¬ zeichnet, daß im Falle eines TLB-Miss mittels Page-Table auch die Erst- und Zweitgruppen-Informationen ( c' , c") fü die in der TLB-Einheit gespeicherten Realadressen bestimm werden.
4. Cache-Speichervorrichtung nach einem der Ansprüche 1 bi 3, dadurch gekennzeichnet, daß Schritt d) nur dann durch- geführt wird, wenn die Zweitgruppeninformation verschieden ist von der Gruppeninformation.
5. Cache-Speichervorrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß das im Anschluß an den Schritt b) , der entweder erstmalig oder gemäß Schritt d) ausgeführt wird, wie folgt verfahren wird: e) liegt in Schritt b) keine Übereinstimmung vor, so wird der Cache-Speicher mittels des Cache-Indexteils ( ϊ) der virtuellen Adresse (v) sowie der Erstgruppeninformation
( c ' ) der aus der virtuellen Adresse (v) umgesetzten Realadresse indiziert und die Schritte b) und c) für den oder die derart adressierten Cache-Einträge durch¬ geführt, und f) bei Nicht-Übereinstimmung in Schritt b) ein Cache-Miss vorliegt und die Cache-Adressierung abgebrochen wird.
6. Cache-Speichervorrichtung nach Anspruch 5, dadurch gekenn¬ zeichnet, daß Schritt e) nur dann durchgeführt wird, wenn die Erstgruppeninformation sowohl von der Gruppeninforma¬ tion als auch von der Zweitgruppeninformation verschieden ist.
7. Cache-Speichervorrichtung nach Anspruch 5 oder 6, dadurch gekennzeichnet, daß nach der erstmaligen Abarbeitung von Schritt c) zunächst Schritt e) und dann Schritt d) durch¬ geführt wird.
8. Cache-Speichervorrichtung nach einem der Ansprüche 5 und 6, dadurch gekennzeichnet, daß eine Entscheidungsvorrich¬ tung vorgesehen ist, mittels derer entschieden wird, ob im Anschluß an die erstmalige Abarbeitung von Schritt c) zu¬ nächst Schritt e) und dann Schritt d) oder zunächst Schritt d) und dann Schritt e) durchgeführt werden.
9. Cache-Speichervorrichtung nach Anspruch 8, dadurch gekenn¬ zeichnet, daß die Entscheidungsvorrichtung einen Zufalls- generator aufweist.
10. Cache-Speichervorrichtung nachAnspruch 8, dadurch gekenn¬ zeichnet, daß die Entscheidungsvorrichtung vorherige Cache-Hits für die anstehende virtuelle Adresse berück¬ sichtigt und die Entscheidung in Abhängigkeit davon fällt.
11. Speichervorrichtung nach einem der Ansprüche 1 bis 10, da¬ durch gekennzeichnet, daß in einem Multiprozessor-System mit einem Bus und mindestens einem Cache-Speicher über den Bus neben Daten und Realadressen auch die Erst- und/oder die Zweitgruppeninformationen übertragen werden.
12. Cache-Speichervorrichtung zum Speichern von Daten mit einem ein- oder mehrweg-assoziativen Cache-Speicher, der durch eine Kombination aus einem Cache-Indexteil einer mehrere Bits aufweisenden Adresse (r) und einem der Adresse (r) zugeordneten, frei vorgebbaren Zusatz¬ index ( c' ' ' ) , welcher nicht Teil der Adresse (r) ist, indizierbar ist.
13. Cache-Speichervorrichtung nach Anspruch 12, dadurch ge¬ kennzeichnet, daß auch der Zusatzindex ( c ' ' ' ) mit Hilfe von Page Tables bestimmt wird.
14. Cache-Speichervorrichtung nach Anspruch 12 oder 13, da¬ durch gekennzeichnet, daß ein Teil der Adresse (r) und der Zusatzindex ( c ' ' ' ) von einerTranslation-Lookaside-Buffer- (TLB-)Einheit geliefert wird.
15. Cache-Speichervorrichtung zum■Speichern von Daten, mit einer First-Level-Cache-Speichervorrichtung und einer Second-Level-Cache-Speichervorrichtung, wobei die First-Level-Cache-Speichervorrichtung als Cache-Speichervorrichtung gemäß einem der Ansprüche 1 bis 11 und die Second-Level-Cache-Speichervorrichtung als Cache-Speichervorrichtung gemäß einem der Ansprüche 12 bis 14 ausgebildet ist.
16. Cache-Speichervorrichtung nach Anspruch 15, dadurch ge¬ kennzeichnet, daß der Zusatzindex anhand der Zweitgrup¬ peninformation gebildet ist, und zwar insbesondere iden¬ tisch mit der Zweitgruppeninformation ist oder diese ent¬ hält.
17. Cache-Speichervorrichtung zum Speichern von Daten, mit einer First-Level-Cache-Speichervorrichtung und einer Second-Level-Cache-Speichervorrichtung, wobei die First-Level-Cache-Speichervorrichtung und die Second-Level-Cache-Speichervorrichtung jeweils gemäß einem der Ansprüche 12 bis 14 ausgebildet sind.
18. Cache-Speichervorrichtung nach Anspruch 15 und 13 oder 14, dadurch gekennzeichnet, daß die MMU-Einheit oder die TLB- Einheit für die First-Level-Cache-Speichervorrichtung und die Second-Level-Cache-Speichervorrichtung einen gemein¬ samen Zusatzindex oder zwei getrennte Zusatzindizes lie¬ fert.
EP95916674A 1994-04-22 1995-04-19 Cache-speichervorrichtung zum speichern von daten Withdrawn EP0756729A1 (de)

Applications Claiming Priority (7)

Application Number Priority Date Filing Date Title
DE4414116 1994-04-22
DE4414116 1994-04-22
DE4416562 1994-05-11
DE4416562 1994-05-11
DE19504483A DE19504483A1 (de) 1994-04-22 1995-02-10 Cache-Speichervorrichtung zum Speichern von Daten
DE19504483 1995-02-10
PCT/EP1995/001471 WO1995029445A1 (de) 1994-04-22 1995-04-19 Cache-speichervorrichtung zum speichern von daten

Publications (1)

Publication Number Publication Date
EP0756729A1 true EP0756729A1 (de) 1997-02-05

Family

ID=27206300

Family Applications (1)

Application Number Title Priority Date Filing Date
EP95916674A Withdrawn EP0756729A1 (de) 1994-04-22 1995-04-19 Cache-speichervorrichtung zum speichern von daten

Country Status (4)

Country Link
US (1) US6009503A (de)
EP (1) EP0756729A1 (de)
JP (1) JPH09512122A (de)
WO (1) WO1995029445A1 (de)

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5870550A (en) 1996-02-26 1999-02-09 Network Engineering Software Web server employing multi-homed, moldular framework
US8117298B1 (en) 1996-02-26 2012-02-14 Graphon Corporation Multi-homed web server
EP1158749A3 (de) * 2000-04-07 2001-12-05 E-Color, Inc. Verfahren und vorrichtung zur verteilung eines farbkorrigierten bildes dürch ein netzwerk mit hilfe verteiltercachespeicher
US6654859B2 (en) * 2001-07-26 2003-11-25 International Business Machines Corporation NUMA page selection using coloring
US7451271B2 (en) * 2004-04-05 2008-11-11 Marvell International Ltd. Physically-tagged cache with virtually-tagged fill buffers
US8417915B2 (en) * 2005-08-05 2013-04-09 Arm Limited Alias management within a virtually indexed and physically tagged cache memory
US9390031B2 (en) * 2005-12-30 2016-07-12 Intel Corporation Page coloring to associate memory pages with programs
JP4783229B2 (ja) * 2006-07-19 2011-09-28 パナソニック株式会社 キャッシュメモリシステム
US9158710B2 (en) * 2006-08-31 2015-10-13 Intel Corporation Page coloring with color inheritance for memory pages
US9336147B2 (en) * 2012-06-12 2016-05-10 Microsoft Technology Licensing, Llc Cache and memory allocation for virtual machines
US10162694B2 (en) 2015-12-21 2018-12-25 Intel Corporation Hardware apparatuses and methods for memory corruption detection
US10853256B2 (en) * 2019-01-04 2020-12-01 Arm Limited Cache operation in an apparatus supporting both physical and virtual address mapping
US11782816B2 (en) * 2019-03-19 2023-10-10 Jens C. Jenkins Input/output location transformations when emulating non-traced code with a recorded execution of traced code
US11422935B2 (en) * 2020-06-26 2022-08-23 Advanced Micro Devices, Inc. Direct mapping mode for associative cache
US12393523B2 (en) 2022-03-31 2025-08-19 Intel Corporation Circuitry and methods for implementing micro-context based trust domains
US12417099B2 (en) 2022-04-02 2025-09-16 Intel Corporation Circuitry and methods for informing indirect prefetches using capabilities

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1988009014A2 (en) * 1987-05-14 1988-11-17 Ncr Corporation Memory addressing system
US5226133A (en) * 1989-12-01 1993-07-06 Silicon Graphics, Inc. Two-level translation look-aside buffer using partial addresses for enhanced speed
US6116768A (en) * 1993-11-30 2000-09-12 Texas Instruments Incorporated Three input arithmetic logic unit with barrel rotator
US5752069A (en) * 1995-08-31 1998-05-12 Advanced Micro Devices, Inc. Superscalar microprocessor employing away prediction structure

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO9529445A1 *

Also Published As

Publication number Publication date
US6009503A (en) 1999-12-28
JPH09512122A (ja) 1997-12-02
WO1995029445A1 (de) 1995-11-02

Similar Documents

Publication Publication Date Title
EP0756729A1 (de) Cache-speichervorrichtung zum speichern von daten
DE60320026T2 (de) Verbessertes speichermanagement für echtzeit-anwendungen
DE69819686T2 (de) Objekt und verfahren zum bereitstellen eines effizienten mehrbenutzerzugriff auf verteilten betriebssystemkernkode durch instanzierung
DE68924206T2 (de) Verfahren und Einrichtung zum Filtern von Ungültigkeitserklärungsanforderungen.
DE69427625T2 (de) Adressübersetzungsmechanismus für Rechnersystem mit virtuellen Speicher, der eine Vielzahl von Seitengrössen unterstützt
DE69025302T2 (de) Hochleistungsrasterpuffer- und -cachespeicheranordnung
DE4022885C2 (de) Verfahren zum Verschieben von Speicherbereichen und Hierarchie-Speichersystem
DE10002120B4 (de) Adressumsetzpufferanordnung und Verfahren für den Betrieb einer Adressumsetzpufferanordnung
DE2302074A1 (de) Speicherschutzanordnung in einem multiprozessorsystem
DE2423194A1 (de) Vorrichtung zur adressengewinnung und -berechnung in einem segmentierten speicher
DE112023003283T5 (de) Speichercontroller mit befehlsumordnung
DE69726795T2 (de) Kodierungsverfahren des Verzeichnisstatus in einem gemeinsamen, verteilten Speichersystem mit koherenten Pufferspeichern
DE69027919T2 (de) Anordnung und Verfahren zur Unterstützung des Zugriffs auf E/A-Geräte durch grosse, direkt abgebildete Datencache-Speicher
EP0755541A1 (de) Cache-speichervorrichtung zum speichern von daten
DE112019000627T5 (de) Speicherstrukturbasiertes Coherency Directory Cache
WO1996023260A1 (de) Verfahren zum betreiben einer adressumsetzvorrichtung
DE69808628T2 (de) Mikroprozessorcachespeicherübereinstimmung
EP1352318B1 (de) Mikroprozessorschaltung für tragbare datenträger
DE3832758C2 (de) Verfahren zum Adressieren eines im Rückschreib-Modus betriebenen virtuellen Cache-Speichers
DE3689276T2 (de) Verfahren zur Aktualisierung der Informationen in einem Adressenübersetzungspufferspeicher.
DE19516949A1 (de) Speichervorrichtung zum Speichern von Daten
DE102007055138B4 (de) System zum Zugreifen auf einen Einzelport-Mehrwege-Cache
DE19947055A1 (de) Verfahren und Vorrichtung zur Steuerung eines Cache-Speichers
DE19538961C2 (de) Speichervorrichtung zum Speichern von Daten
DE19504483A1 (de) Cache-Speichervorrichtung zum Speichern von Daten

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 19961012

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE CH DE FR GB IT LI NL

17Q First examination report despatched

Effective date: 19980109

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 19980721