CORRELATED ADDRESSES AND PREFETCHING
1. An apparatus comprising:
- cache circuitry comprising a plurality of cache lines, wherein the cache circuitry is adapted to treat one or more of the cache lines as trace lines each comprising correlated addresses and each being tagged by a trigger address; and
prefetch circuitry to cause data at the correlated addresses stored in the trace lines to be prefetched.
An apparatus is provided that includes cache circuitry that comprises a plurality of cache lines. The cache circuitry treats one or more of the cache lines as trace lines each having correlated addresses and each being tagged by a trigger address. Prefetch circuitry causes data at the correlated addresses stored in the trace lines to be prefetched.
- 1. An apparatus comprising:
cache circuitry comprising a plurality of cache lines, wherein the cache circuitry is adapted to treat one or more of the cache lines as trace lines each comprising correlated addresses and each being tagged by a trigger address; and prefetch circuitry to cause data at the correlated addresses stored in the trace lines to be prefetched.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
- 19. A method comprising:
storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and causing data at the correlated addresses stored in the trace lines to be prefetched.
- 20. An apparatus comprising:
means for storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and means for causing data at the correlated addresses stored in the trace lines to be prefetched.
The present disclosure relates to data processing. More particularly, it relates to prefetching.
Prefetching is a technique in which data is proactively fetched from main memory and stored near to a processor at a time before that data is explicitly requested by that processor. In this way when the processor requires the data, it is nearby and can be obtained quickly. Prefetching is usually triggered by a memory address being accessed, either explicitly or via another prefetch operation. However, when addresses are correlated, this can lead to complex sequences of actions that may result in higher latency being experienced in order to obtain the desired data from memory.
Viewed from a first example configuration, there is provided an apparatus comprising: cache circuitry comprising a plurality of cache lines, wherein the cache circuitry is adapted to treat one or more of the cache lines as trace lines each comprising correlated addresses and each being tagged by a trigger address; and prefetch circuitry to cause data at the correlated addresses stored in the trace lines to be prefetched.
Viewed from a second example configuration, there is provided a method comprising: storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and causing data at the correlated addresses stored in the trace lines to be prefetched.
Viewed from a third example configuration, there is provided an apparatus comprising: means for storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and means for causing data at the correlated addresses stored in the trace lines to be prefetched.
The present invention will be described further, by way of example only, with reference to embodiments thereof as illustrated in the accompanying drawings, in which:
Before discussing the embodiments with reference to the accompanying figures, the following description of embodiments is provided.
In accordance with some aspects, there is provided an apparatus comprising: cache circuitry comprising a plurality of cache lines, wherein the cache circuitry is adapted to treat one or more of the cache lines as trace lines each comprising correlated addresses and each being tagged by a trigger address; and prefetch circuitry to cause data at the correlated addresses stored in the trace lines to be prefetched.
In such aspects, a collection of addresses are correlated with each other. The correlation could, for instance, be temporal so that all of the addresses are accessed within a same period or so that all of the addresses are accessed as a consequence of one of the addresses being accessed. Other forms of temporal correlation (or correlation in general) are also possible. The correlated addresses are stored in one of the cache lines, referred to as a trace line, which makes up the cache lines in the cache circuitry. Furthermore, the trace line is tagged by a trigger address. The addresses could be addresses for storage circuitry other than the cache circuitry and could be for use in a memory hierarchy. For instance, the addresses could be addresses of data that is backed up by a DRAM. Prefetch circuitry causes the data stored at the correlated addresses that are provided in a trace line to be prefetched from, e.g. from the underlying DRAM. In this way, all of the correlated addresses can be fetched at the same time, thereby potentially reducing latency.
In some embodiments, the prefetch circuitry is adapted to cause the data at the correlated addresses to be prefetched in response to the trigger address being accessed. By prefetching the data when the trigger address is accessed, the data at the correlated addresses can be accessed in advance of it being needed. The trigger address can therefore be set to a first address that subsequently causes the correlated addresses to be accessed. These need not all be accessed as a direct result of the trigger address being accessed. For instance, the trigger address could access data that thereby causes another of the correlated addresses to be accessed.
In some embodiments, the apparatus comprises obtaining circuitry to obtain the correlated addresses, wherein the correlated addresses relate to data where a miss has occurred. A miss occurs in a cache when data is requested that is not present in the cache. Typically, this will happen as a consequence of the data not having been (pre)fetched. The present apparatus therefore considers correlated data addresses that have not otherwise been prefetched by any prefetching circuitry. By causing these data addresses to be prefetched in the future, the efficiency of the overall system may be improved by causing a greater proportion of data to be subject to prefetching and thereby reducing effective memory latency.
In some embodiments, the correlated addresses relate to data that has been explicitly fetched. Such data has not, therefore, been proactively fetched (e.g. prefetched).
In some embodiments, the correlated addresses relate to data that has been fetched as part of a load operation. In such embodiments, the correlated addresses do not relate to data that has been fetched as part of a store operation or data that is to be stored at one of the correlated addresses.
In some embodiments, the correlated addresses contain at least one storage location where another of the correlated addresses is stored. Such a dependence between the correlated addresses means that only after one of the correlated addresses is retrieved can another correlated address be retrieved. This in turn means that, if both addresses have missed in the cache, there is an increased latency as a consequence of missed data having to be retrieved in order to be accessed, in order for another item of data to be retrieved etc.
In some embodiments, the trigger address and the correlated addresses form a linked list. A linked list is a data structure in which elements of the list each contain a pointer to another element of the list. Accessing a linked list can result in a chain of memory accesses occurring in which each element is retrieved once previous elements in the list have been retrieved. The memory access time increases linearly with the length of the linked list, assuming that all the correlated addresses have missed and must therefore be sequentially accessed via the main memory. Hence, for long linked lists, there may be a long delay before some of the underlying data can be accessed. Such a situation could arise, for instance, in a programming language such as C, where one may refer to a pointer to an item of data, where the data itself could be another pointer. Consequently, one could refer to a pointer of a pointer of a pointer (etc.) of an item of data, which may take time to fully dereference. In addition, the presence of virtual memory can cause additional problems. In particular, since there may be little or no spatial correspondence between virtual addresses and physical addresses, there is no certainty that any pointer in the chain will have been prefetched by virtue of being spatially proximal to another accessed address.
In some embodiments, each line in the plurality of cache lines include a c flag and a d flag to indicate whether that line is one of the trace lines; the c flag and the d flag are mutually-exclusive. The ‘c’ flag indicates whether correlated addresses are present while the ‘d’ flag indicates whether data other than correlated addresses is present. The two flags are mutually exclusive so that a cache line cannot contain both correlated addresses and data other than correlated addresses. However, it is possible for a line to contain neither correlated addresses nor data other than correlated addresses—in which case the cache line is considered to be empty or invalid.
In some embodiments, the correlated addresses in each of the trace lines are compressed. This makes it possible for more addresses to be stored in a single cache line than if compression was not used.
There are a number of ways in which compression can be achieved. However, in some embodiments, the correlated addresses in a given trace line are compressed by storing a base address and, for each individual address in the correlated addresses of the given trace line, a delta between the base address and the individual address. Each cache line therefore contains a base address and a number of different deltas.
In some embodiments, the base address comprises common bits between the plurality of correlated addresses in the given trace line; and the delta comprises remaining bits from the individual address when the common bits are removed. The addresses can be decompressed by concatenating the delta with the common bits. As an alternative, the delta could be an offset from the base address (e.g. achieved via subtraction), with leading zeros (or ones) removed. However, such embodiments could provide a variable number of deltas in a single cache line. In some embodiments, an offset could be calculated using a binary operator such as a XOR and again by removing leading zeros (or ones). Other options will be known to the skilled person.
In some embodiments, the apparatus comprises eviction circuitry to evict the plurality of cache lines from the cache circuitry in dependence on one or more standard eviction conditions, wherein the eviction circuitry is inhibited from evicting the trace lines in dependence on one or more correlated-address eviction conditions. In these embodiments, cache lines that do not contain correlated addresses are subjected to standard eviction conditions. These could, for instance, be based on a Least Recently Used (LRU) principle. In contrast, the trace lines are subject to further (or, in some embodiments, different) eviction conditions because they are more likely to contain more data than a cache line that contains other data and so should be removed with more caution.
In some embodiments, the one or more correlated-address eviction conditions includes a fill condition; the plurality of cache lines are grouped into a plurality of sets; each set in the plurality of sets has a set counter, which is incremented in response to a fill being made to that set; and the fill condition causes a given trace line in the set to be made evictable based on the set counter associated with the given trace line. In such embodiments, a particular trace line is kept at least until a certain number of fills are made to the set containing that trace line. Typically, cache eviction takes place in response to a fill, since the act of adding new data to the cache causes other cache lines to have to be evicted. Hence, by keeping the trace line based on the number of fills that have taken place, it is possible to keep the trace line for longer than another cache line would be kept. Note that the counter need not be incremented in response to every fill that takes place. In some embodiments, the counter can be incremented for every number of fills that takes place, for fills having particular criteria (e.g. the address having particular bits), or with random probability. By not incrementing the counter in response to every fill that takes place, it is possible to implement a smaller counter.
In some embodiments, the given trace line in the set is associated with a line counter; the line counter is incremented each time the set counter of the given line reaches a predetermined value; and the fill condition causes the given line to be made evictable when the line counter reaches a further predetermined value. In order for a trace line to made evictable, therefore, the set counter associated with that trace line must reach its predetermined value a number of times. This helps to avoid a situation in which the counter is already near the predetermined value when a new trace line is added, thereby causing the trace line to be made evictable very quickly or even immediately.
In some embodiments, the apparatus comprises trigger queue circuitry to store a plurality of triggering addresses, wherein in response to the trigger address of the given line missing when the trigger queue circuitry is at its maximum capacity, the line counter associated with the given line is incremented. In these embodiments, when a trigger address (e.g. an address that misses in the cache that also causes other misses to occur) is encountered, an attempt is made to add that trigger to the queue. Other misses that occur in the near future are attributed to the latest entry in the queue. The queue has a maximum capacity. Hence, if a trigger address is detected when the queue is full, that trigger address cannot be added. Furthermore, if that trigger address is the tag of a trace line in the cache, then that trace line is demoted (e.g. brought closer to being evicted). This scenario recognises the fact that it is not always possible to store all correlated addresses. Thus, the addresses that are found later in the process (e.g. later in a chain or linked list) are deprioritised. This is because the probability with which an address will be accessed in a chain/linked lists decreases as one iterates through the chain/linked list. For example, in a linked list where the only start point is the first entry of the linked list, the first entry must always be accessed. The second entry must be accessed where access is desired to any entry other than the first entry. The third entry must be accessed where access is desired to any entry other than the first entry or second entry, and so on. The final entry is only accessed where access is desired to the final entry itself. There is therefore expected to be less value in adding entries further down the chain. To avoid keeping such entries, these entries are brought closer to eviction if they have already been added and if there are other entries to be added (as is the case where the queue is full).
In some embodiments, the one or more correlated-address eviction conditions includes a double-hit condition; the double-hit condition causes a given trace line to be made evictable in response to the cache circuitry hitting, in response to a request, on both the given cache line and a further cache line that is other than one of the trace lines; and the given cache line and the further cache line have a same tag. If the trigger address is a tag for a data line in the cache then it cannot also be the tag for a trace line in the cache. In some of these embodiments, in response to adding a new trace line when the cache contains the further cache line that is other than one of the trace lines, the further cache line is marked as being evictable. Hence, in these embodiments, when correlated addresses are added, any existing line containing data is made evictable. If, later, a line containing correlated addresses and data is discovered that have the same tag, it is assumed that the triggering address now points to data and thus the trace line is made evictable. In other embodiments, this could be reversed so that existing correlated data lines are made evictable when a data line is to be added and the sudden appearance of a correlated data line (e.g. a trace line) having the same tag means that the data line is to be made evictable.
In some embodiments, the cache circuitry is adapted to limit a number of the trace lines to a predetermined level. The number could be an absolute value, an absolute percentage, a ratio, or another way of defining a limit. Furthermore, the limit could apply to the entire cache or a portion of the cache such as a set. For instance, in some embodiments, the cache circuitry is adapted to limit the number of the trace lines on a per-set basis so that only 75% of the lines in each set are permitted to be trace lines.
Particular embodiments will now be described with reference to the figures.
In this example, each of the cache lines contains two mutually exclusive flags. A ‘c’ flag 240 indicates whether the cache line contains one or more correlated addresses, thereby indicating that the cache line is a trace cache line 220. The ‘d’ flag 250 indicates that the cache line does not contain the one or more associated addresses and instead contains regular data. Such cache lines are not trace lines 220 but are instead regular data lines 230. The two flags 240, 250 are mutually-exclusive such that both flags cannot be set simultaneously. However, it is possible for neither flag to be set thereby indicating that the cache line is invalid or contains neither data nor correlated addresses. All of the cache lines 220, 230 shown in
In addition, in the present example, obtaining circuitry 270 obtains the address of the data value for which a miss occurred. Such a data value is a data value that was not able to be prefetched by any of the available prefetching circuitry in the apparatus. Accordingly, there is value to be had in causing this data value to be prefetched in the future. By the means of a queue 310, the obtaining circuitry 270 attempts to determine the triggering memory address that caused the missed memory address to be accessed, together with any other memory addresses that missed and were accessed at a similar time. These are gathered and then filled into the cache 210 as a trace line 220. The behaviour of the obtaining circuitry 270 in combination with the queue is shown in more detail with respect to
Eviction circuitry 300 is provided to perform maintenance on the cache, including tracking evictability of cache lines. In particular, the eviction circuitry 300 causes an existing data line 230 that is tagged with an address to be evicted if a trace line 220 is added that uses the same tag. Other behaviour of the eviction circuitry with regards to updating the eviction status of the trace lines 220 is illustrated with respect to
With the above descriptions in mind, the process proceeds as follows: the queue 310 is initially empty. Thus, when a miss occurs on data value ‘A’, it is added to the queue 310. Training then begins on value ‘A’ as shown by the arrow in
Since the value stored in location ‘A’ is a reference to location ‘B’ and since there is a miss on ‘B’, the data at location ‘B’ will be fetched. Since ‘A’ is currently being trained, value ‘B’ will be added as an associated/correlated address for the value currently being trained (A). The value at ‘B’ makes reference to location ‘C’. In this example, however, ‘C’ is already known to be a trigger. ‘C’ is added to the queue 310 since the queue 310 is not currently full. As a consequence of ‘C’ being triggered, values ‘D’, ‘E’, and ‘F’ are prefetched. ‘D’ and ‘E’ are added to the currently trained value (‘A’). The currently trained value (A′) then becomes full. That is, no further addresses can be associated with ‘A’. Consequently, ‘A’ is popped from the queue 310 and training resumes on the next trigger in the queue (‘C’). ‘F’ is thus added to the cache line for the newly trained address (‘C’). Since ‘F’ refers to ‘G’, which in turn refers to ‘H’, and since ‘G’ and ‘H’ both miss, these values will then be added to a trace line triggered by the currently trained value (‘C’).
Accordingly, it will be appreciated that over time, the associated addresses and triggers may move around. In particular, in this example, there was originally assumed to be a trigger ‘C’ that caused ‘D’, ‘E’, and ‘F’ to be prefetched. However, as shown in
The process begins at a step 605 where the next (or first) cache line for consideration is obtained. At a step 610, it is determined whether the line in question is a trace line 220, or a data line 230. If the line is a data line 230, then at step 615 it is determined whether the standard eviction conditions are met. Such eviction conditions will be known to the skilled person and may rely on policies such as LRU. If the conditions are met, then at step 620, the line is set as being evictable. Consequently, when an eviction must take place, this line is considered to be acceptable for replacement or removal.
If the line is not a data line (e.g. it is a trace line) then the process proceeds from step 610 to step 625 where it is determined whether the set counter 280 is at a predetermined value. For instance, the predetermined value may be 0. As previously stated, the set counter 280 is incremented each time a line fill operation occurs on the cache circuitry 210 in a particular set. The counter 280 therefore represents the number of fills that have taken place in the set (since the counter last overflowed). If the set counter 280 is at its predetermined value, then at step 630, the line counter 260 for the current entry is decremented, and the set counter 280 is reset (or allowed to overflow). Then, at step 635 it is determined whether the line counter 260 is at the predetermined value. Effectively, the line counter 260 indicates the number of times that the set counter 280 has reached its predetermined value. The line counter 260 is therefore used in combination with the set counter 280 to estimate the number of set fills that have taken place since the line was added. If the line counter 260 is at its predetermined value at step 635, then the process proceeds to step 620 where the line is set as being evictable. A line is therefore set as being evictable as a consequence as a number of fill operations having taken place since the line was added to the cache circuitry 210. If the line counter 260 is not at its predetermined value, then the process proceeds to step 640, which is also the case if the set counter 280 is not at its predetermined value at step 625.
If at step 640 it is determined that the tag of the cache line in question was considered to be a trigger that could not be added to the training queue 310 (as illustrated in
At step 655, it is determined whether a double hit occurs, this is a situation in which two cache lines are hit on by the same trigger—one a trace line 220 and one a data line 230. In this situation, it is assumed that the trace line 220 has become invalid, and so is directly set as evictable at step 620. If there was no double hit, then the process proceeds to step 605 where the next line is obtained.
In this example, both the set counter 280 and the line counter 260 are used to measure the number of fills that occur before determining whether a particular trace line 220 is considered to be evictable or not. The combination of counters 260, 280 recognises the fact that if only a single counter was provided, then that counter may be close to its predetermined value at the time a line was added. A trace line could then be added and deleted almost immediately. Conversely, if a large counter was added for each cache line, then this would result in a large amount of wasted space. Furthermore, the fill operation would be time consuming since every time a fill occurred within a set, all the counters in that set would need to be updated. The combination of counters 260, 280 therefore makes it possible to inhibit the removal of a cache line until a minimum number of fill operations has occurred, without necessitating a large amount of storage or a time-consuming update process.
In other embodiments, the delta could be derived from a target address by performing a subtraction between the base address and the target address. Decompression could then take place by performing an addition of the delta to the base address. Other techniques will be known to the skilled person.
In some embodiments, each cache line could specify the degree of compression provided. In particular, a number of different compression levels could be provided that indicate the number of bits that make up the base address. For instance, level one compression could correspond to two bits being used to make up the base address. Level two compression could be used to indicate four bits being used to the base address, level three with six bits and level four with eight bits. The compression level would be set to the highest that is possible for a set of correlated addresses. For instance, if all the correlated addresses only had six common prefixed bits, then the compression level would be set to three (six bits). Similarly, if all of the input addresses had seven bits in common, then a compression level of four would not be appropriate since this would include non-common-bits in the base address. The level would therefore be set to three. In this way, each trace line can use a different level of compression, as appropriate. This allows for maximum compression in some cases, while also allowing addresses that are highly dissimilar (or far removed from each other) to form part of the same correlation and thereby be stored in the same trace line.
Clearly it will be appreciated by the skilled person that the improvement provided is highly dependent on the underlying architecture and the task that is being executed. Some systems may provide improvements even beyond those illustrated with respect to
As a result of the above, it can be shown that the technique of determining the number of correlated addresses that are not otherwise fetched by prefetching circuitry can be used in situations such as linked lists where a number of correlated addresses must each be fetched from memory, leading to a long memory latency for the underlying data value to be accessed. This is undesirable since it can lead to a number of high inefficiencies. Consequently, by storing these correlated addresses in repurposed cache lines as trace lines 220 it is possible for those lines to be prefetched in the future thereby reducing the extent to which memory latency occurs.
In the present application, the words “configured to . . . ” are used to mean that an element of an apparatus has a configuration able to carry out the defined operation. In this context, a “configuration” means an arrangement or manner of interconnection of hardware or software. For example, the apparatus may have dedicated hardware which provides the defined operation, or a processor or other processing device may be programmed to perform the function. “Configured to” does not imply that the apparatus element needs to be changed in any way in order to provide the defined operation.
Although illustrative embodiments of the invention have been described in detail herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes, additions and modifications can be effected therein by one skilled in the art without departing from the scope and spirit of the invention as defined by the appended claims. For example, various combinations of the features of the dependent claims could be made with the features of the independent claims without departing from the scope of the present invention.