Key information

Title
Snoop filter scalability
Application number
20220189
Case type
National
Status
22.04.2024 Patent meddelt (B1)
Filed
10.02.2022
Effective date
10.02.2022
Publicly available
11.08.2023
Next annual fee due
28.02.2027
Applicant
Numascale AS (NO)
Owner
Numascale AS (NO)
Inventor
Helge Simonsen (NO) et al.
Agent
BRYN AARFLOT AS (NO)
Granted
22.04.2024
Patent number
347869
Expiry date
10.02.2042

Abstract and drawing

Disclaimer: This text has been machine-scanned and may contain errors – please refer to "Publications" for legally binding content.
The invention relates to a snoop filter device, a node controller, a multicomponent computer system, a computer-implemented method, a data processing system and a computer-readable storage medium aiming at enabling improved tracking of a scalable number of cache elements in multiprocessor systems. The invention involves scaling of a snoop filter device according to the number of cache elements that it is desireable to track.

Publications

B1A1
Checking availability of the latest published version...

Documents

 Expand Download files (24)
Date
 Date Doc. No. Process Case number In/Out Journal description To/from
 26.04.2024 13-01 Saksbehandling 20220189(347869) UT PT Registreringsbrev nasjonal patent (15) (PT20220189)
16.02.2024 12-01 Saksbehandling 20220189 UT Intention to grant BRYN AARFLOT AS
 04.01.2024 11-01 Saksbehandling 20220189 UT PT Varsel om betaling av første årsavgift (3317) (PT20220189) BRYN AARFLOT AS
 06.11.2023 10-03 Saksbehandling 20220189 INN Response NIPO BRYN AARFLOT AS
 06.11.2023 10-02 Saksbehandling 20220189 INN 131521Claim-no BRYN AARFLOT AS
 06.11.2023 10-01 Saksbehandling 20220189 INN Korrespondanse (Hovedbrev inn) BRYN AARFLOT AS
 24.08.2023 09-01 Saksbehandling 20220189 UT Substantive examination BRYN AARFLOT AS
 06.03.2023 08-06 Saksbehandling 20220189 INN Response NIPO BRYN AARFLOT AS
 06.03.2023 08-05 Saksbehandling 20220189 INN 131521Description-en rev01 BRYN AARFLOT AS
 06.03.2023 08-04 Saksbehandling 20220189 INN 131521Description-en rev01 marked up BRYN AARFLOT AS
 06.03.2023 08-03 Saksbehandling 20220189 INN 131521Claim-en rev01 BRYN AARFLOT AS
 06.03.2023 08-02 Saksbehandling 20220189 INN 131521Claim-en rev01 marked up BRYN AARFLOT AS
 06.03.2023 08-01 Saksbehandling 20220189 INN Korrespondanse (Hovedbrev inn) BRYN AARFLOT AS
 09.09.2022 07-02 Saksbehandling 20220189 UT PT report 10:56:10
09.09.2022 07-01 Saksbehandling 20220189 UT Substantive examination BRYN AARFLOT AS
 22.03.2022 06-03 Saksbehandling 20220189 INN Power of attorney - signed BRYN AARFLOT AS
 22.03.2022 06-02 Saksbehandling 20220189 INN Declaration - signed BRYN AARFLOT AS
 22.03.2022 06-01 Saksbehandling 20220189 INN Korrespondanse (Hovedbrev inn) BRYN AARFLOT AS
 23.02.2022 05-01 Saksbehandling 20220189 INN Korrespondanse (Hovedbrev inn) BRYN AARFLOT AS
 23.02.2022 04-01 Saksbehandling 20220189 INN Korrespondanse (Hovedbrev inn) BRYN AARFLOT AS
 11.02.2022 03-01 Saksbehandling 20220189 UT Formal Examination 1 BRYN AARFLOT AS
 11.02.2022 02-01 Saksbehandling 20220189 UT Information to inventor BRYN AARFLOT AS
 10.02.2022 01-02 Saksbehandling 20220189 INN 131521Description-claim-abstract-figure-en basis BRYN AARFLOT AS
 10.02.2022 01-01 Saksbehandling 20220189 INN Søknadsskjema Patent BRYN AARFLOT AS

Description, claims and drawings

Disclaimer: This text has been machine-scanned and may contain errors – please refer to "Publications" for legally binding content. Description
Technical field[0001] The disclosure relates to a snoop filter device, a node controller, a multicomponent computer system, a computer-implemented method, a data processing system and a computer-readable storage medium, aiming at enabling improved tracking of a scalable number of cache elements in multiprocessor systems.Background[0002] Efficiently maintaining cache coherence is a central requirement for obtaining high performance shared memory multiprocessor systems.[0003] Shared memory multiprocessor systems usually contain one or more shared main memory agents in addition to a series of local memory agents, called cache agents, or just cache. The cache agents may belong to a local processor or a node of processors and are characterized by their high speed and small size compared with main memory. Storing data in a local cache agent that e.g., belongs to a working set of a local CPU will thus largely improve the overall performance of the multiprocessor system as the frequently used data in the working set can be more quickly accessed by the local CPU.[0004] Having a series of local cache agents, each holding data locally, gives rise to the problem with how to maintain cache coherence. If a CPU modifies a cache line in a local cache agent through e.g., a write-operation, other cache agents holding a copy of the same cache line will be unaware of this write operation, and their copy of the respective cache line will consequently be out of date. These out-ofdate cache lines may then be defined as stale.[0005] To obtain cache coherence, i.e., eliminating stale data, a wide variety of techniques and procedures have been implemented. This involves implementing a variety of cache coherence protocols, like the MSI, MESI, MOESI protocols, as well as implementing a variety of cache coherence mechanisms, including directory-based cache coherence mechanisms as well as snoopy bus-based methods.[0006] Snoopy bus-based methods usually involve what is called a snooper that snoops all the transactions that are being communicated across one or more connections between various agents in the multiprocessor system, e.g., across a bus, and updates the local cache accordingly. The snooper may belong to a node controller, a cache agent, or cache element, and the connections may run between various agents in the computer system, including cache agents, cache nodes, cache elements, CPUs etc. Whenever a transaction that modifies a cache line is being communicated, the snooper snoops this transaction, checks whether any of its respective agents hold a copy of this cache line, and modifies the cache line according to the transaction communicated across the bus.[0007] The main mechanism to achieve cache coherence today is directory-based.Directory based cache coherence implies that directories are used to manage caches in place of snoopy methods due to the snoopy mechanisms’ poor scalability due to the use of broadcasting. Directory-based coherence avoids broadcast by storing information about the status of an address in a “directory”. The directory entry for a cache line contains information about the state of the cache line in all caches. Caches look up information from the directory as necessary - Cache coherence is maintained by point-to-point messages between the caches (not by broadcast mechanisms).[0008] The concept of a snoop filter has been developed in order to improve on the efficiency of snoopy based cache coherence mechanisms and directory-based cache coherence mechanisms. A snoop filter is a directory-based structure that maintains information regarding the coherence state of a series of cache lines stored in the cache. In a multi-processor system, a snoop filter may for example monitor the bus traffic and filter out the transactions on the bus not relating to a cache line that is stored in the appurtenant cache element. This results in the snooper having to perform fewer power and time-consuming lookups, and hence improves the efficiency of the snoopy based cache coherence mechanism.[0009] A snoop filter is commonly structured to maintain information in a series of entries, where each entry comprises a tag and one or more additional bits related to the appurtenant tag. The tag is a unique identifier of a cache line while the additional bits e.g., may indicate the state of a cache line identified by the tag. The additional bit/bits may as an example make up one or more presence vectors, each containing information regarding whether the cache line identified by the tag is stored in the cache, and optionally where in the cache, or in which cache element the cache line is stored.[0010] A snoop filter may be incorporated in a node controller that may be connected to a variable number of cache elements. For the node controller to function when connected to different number of cache elements, the node controller needs to be able to track a variable number of cache elements in its snoop filter. This has historically been achieved in two ways: either by scaling the presence vector in each snoop filter entry according to the number of cache elements tracked, or to let each presence vector represent multiple cache elements.[0011] The scaling approach involving scaling of the presence vectors comes with the drawback that the amount of scaling that can be performed is limited and that scaling of the presence vectors result in damaging of the address capabilities of each snoop filter entry. Letting each presence vector represent more than one cache element comes on the other hand with the drawback of a significant loss in precision for how accurately the snoop filter can track a cache element.[0012] It is the goal of the present invention to improve on the structure of a snoop filter to enable improved tracking of a variable number of cache elements.Summary of the invention[0013] In a first aspect of the invention, the invention provides a snoop filter device for being organized in order to track a variable C number of cache elements, where the snoop filter device comprises an Si number of initial snoop filter instances, the snoop filter device is connectable to a C number of cache elements, the snoop filter device is configured to be organized, when the snoop filter device is connected to the C number of cache elements, by grouping initial snoop filter instances together into an Sf number of final snoop filter instances, each initial snoop filter instance comprises an Li number of snoop filter storage locations organized in an ni-way set associative manner with an mi number of sets and an ni number of storage locations per set, such that Li equals mi · ni, each final snoop filter instance comprises an Lf number of snoop filter storage locations organized in an nf-way set associative manner with an mf number of sets and an nf number of storage locations per set, such that Lf equals mf · nf, and where each snoop filter storage location is configured to store a tag identifying a cache line storable in a cache element, and to store a P number of presence vectors, each presence vector containing information regarding the presence of the cache line identified by the tag, where the product Sf·mf·nf equals the product Si·mi·ni, where Sf < Si and where Sf equals C/P,[0014] According to one embodiment of the invention each cache line comprises a cache line address comprising a given tag and a given k bit cache line index, and any snoop filter instance of the snoop filter device, when 2k > mf, is configured to store the given tag in a set indicated by the log2(mf) least or most significant bits of the given k bit cache line index.[0015] According to another embodiment of the invention P ≤ 16. [0016] According to yet another embodiment of the invention P = 1 or P = 2.[0017] According to yet another embodiment of the invention Sf ≥ 2, each snoop filter instance among the Sf final snoop filter instances is configured to store the same tag in one if its storage locations, and each of the storage locations of the snoop filter device that stores the same tag are configured to store different presence vector/vectors.[0018] According to yet another embodiment of the invention each snoop filter storage location is mapped to one cache element.[0019] According to yet another embodiment of the invention each presence vector comprises several presence bits, and the number of presence bits is equal to a number of bits required to write a cache element identifier plus one additional bit.[0020] According to yet another embodiment of the invention each presence vector consists of one presence bit.[0021] In a second aspect of the invention, the invention provides a node controller comprising a snoop filter device according to the first aspect of the invention.[0022] In a third aspect of the invention, the invention provides a multicomponent computer system comprising: a C number of cache elements, and a snoop filter device connected with the C cache elements, or a node controller where the snoop filter device of the node controller is connected with the C cache elements.[0023] In a fourth aspect of the invention, the invention provides a computerimplemented method comprising the step of: organizing a snoop filter device according to the first aspect of the invention, when the snoop filter device is connected to a C number of cache elements, such that the product Sf·mf·nf equals the product Si·mi·ni, and where Sf equals C/P.[0024] In a fifth aspect of the invention, the invention provides a data processing system comprising means for carrying out the computer-implemented method.[0025] In a sixth aspect of the invention, the invention provides a computer-readable storage medium comprising instructions which, when executed by a computer system, causes the computer system to carry out the computer-implemented method.[0026] Other advantageous features will be apparent from the accompanying claims. Brief description of the drawings[0027] To make the invention more readily understandable, the discussion that follows will refer to the accompanying drawings, in which: [0028] Figure 1a is a schematic illustration of a snoop filter device that comprises an Si number of initial snoop filter instances, where each initial snoop filter instance comprises an Li number of snoop filter storage locations;[0029] Figure 1b is a schematic illustration of a snoop filter device connectable with C number of cache elements;[0030] Figure 2a-c are schematic illustrations of a snoop filter device where Si initial snoop filter instances are organized into Sf final snoop filter instance, where each final snoop filter instance is organized in an nf-way set associative manner;[0031] Figure 3 is a schematic illustration of a presence vector comprising a plurality of bits and a presence vector comprising one bit;[0032] Figure 4 schematically illustrates that a tag of a given cache line address may be stored in a set of a snoop filter instance indicated by at least parts of a k bit index of that given cache line address;[0033] Figure 5 is a schematic illustration of a snoop filter storage location according to the invention that is configured to store a tag identifying a cache line storable in a cache element, and to store P presence vectors;[0034] Figure 6 is a schematic illustration of a snoop filter device comprising S snoop filter instances where a tag, tag A, is stored in each of the snoop filter instances;[0035] Figure 7 is a schematic illustration of a snoop filter device comprising a plurality of snoop filter instances where tags, tag A, B and Z, are stored in each of the snoop filter instances;[0036] Figure 8 is a schematic illustration of a snoop filter instance where each snoop filter storage location is mapped to one cache element;[0037] Figure 9 is a schematic illustration of a presence vector comprising several presence bits sufficient to explicitly express a cache identifier, and one occupation bit;[0038] Figure 10 illustrates a node controller comprising a snoop filter device;[0039] Figure 11 illustrates a node controller comprising a snoop filter device;[0040] Figure 12 illustrates a multicomponent computer system comprising a C number of cache elements, and a snoop filter device connected with the C cache elements;[0041] Figure 13 illustrates a multicomponent computer system comprising a C number of cache elements, and a node controller comprising a snoop filter device, where the node controller is connected with the C cache elements; and[0042] Figure 14 illustrates a computer-implemented method according to the invention. Detailed description of the Invention[0043] In the following, general embodiments as well as exemplary embodiments of the invention will be described. References and possible numerals will be made to the accompanying drawings. It shall be noted, however, that the drawings are exemplary embodiments only, and that other features and embodiments may well be within the scope of the invention as described.[0044] The present invention relates to a snoop filter device, a node controller, a multicomponent computer system, a computer-implemented method, a data processing system and a computer-readable storage medium aiming at enabling improved tracking of a variable number of cache elements in multiprocessor systems.[0045] In a first aspect of the invention, the invention provides a snoop filter device for being organized to track a variable C number of cache elements. Here, the snoop filter device is connectable to C cache elements, directly or indirectly.[0046] Figure 1a schematically illustrates a snoop filter device that comprises Si initial snoop filter instances. Si being a real positive integer. Here, each initial snoop filter instance comprises an Li number of snoop filter storage locations. The Li snoop filter storage locations are organized in an ni-way set associative manner, meaning that the snoop filter device follows an entry placement policy similar to that of a set-associative cache. The ni-way set associative organization means as illustrated in figure 1a that each initial snoop filter instance may be imagined as an ni · mi matrix of storage locations, where mi being the number of sets and ni being the number of storage locations per set. ni can in other words be said to be the number of ways and each initial snoop filter instance may thus be said to be an ni-way set associative snoop filter. The total number of storage locations in each initial snoop filter instance equals Li. Li equals according to the invention × storage locations.[0047] Figure 1b illustrates a snoop filter device connectable to C cache elements, C being a real positive integer. The connection may be a direct connection, e.g., via a bus, or indirectly, e.g., via components such as routers, node controllers etc. C may for example be a real positive integer being a power of 2, but can in principle be any real positive number. The snoop filter device is according to the invention configured to be organized when the snoop filter device is connected to C cache elements. Said organization is performed by grouping initial snoop filter instances together into an Sf number of final snoop filter instances, meaning that Sf consequently will be smaller than Si, e.g., such that 2= , x = {1,2,3,…}. The snoop filter device may thus be said to be configured to group initial snoop filter instances together into an Sf number of final snoop filter instances. A person skilled in the art will appreciate that the snoop filter device here may be considered as specially adapted to group initial snoop filter instances together into an Sf number of final snoop filter instances. The snoop filter device may alternatively be operated by a separate agent, e.g., a CPU or node controller, that may be considered as specially adapted to group initial snoop filter instances together into an Sf number of final snoop filter instances. Grouping of initial snoop filter instances may be implemented by programming the snoop filter device, or the agent operating the snoop filter device, to perform the grouping, e.g., at a software or hardware level. Organization is in the context of the present invention considered as an equivalent term as reorganization and the two terms may be used interchangeably herein.[0048] Each of the Sf number of final snoop filter instances comprises according to the invention an Lf number of snoop filter storage locations, where the Lf snoop filter storage locations are organized in an nf-way set associative manner. As for the initial snoop filter instances the latter means that the snoop filter device, after grouping of initial snoop filter instances, follows an entry placement policy similar to that of a set-associative cache. Figure 2a – 2c illustrates a final snoop filter instance that is organized in an nf-way set associative manner. The nf-way set associative organization means that each final snoop filter instance may be imagined as an nf · mf matrix of storage locations, where mf being the number of sets and nf being the number of storage locations per set. nf can in other words be said to be the number of ways and each final snoop filter instance may thus be said to be an nf-way set associative snoop filter. The total number of storage locations in each final snoop filter instance equals Lf. Lf equals according to the invention × total number of storage locations.[0049] It will be appreciated by a person skilled in the art that any snoop filter instance, being an initial snoop filter instance or final snoop filter instance may be considered structured fully associatively, in a direct mapped manner, or in a setassociative manner based on the exact values ni,f and mi,f. This structuring means that the snoop filter device may follow an entry placement policy similar to that of a fully associative cache, direct mapped cache or a set-associative cache respectively. As a way of example, an nexample1-way set associative snoop filter instance will be direct-mapped in the case of nexample1 being equal to 1 and mexample1 being equal to the number of storage locations in the snoop filter instance. Another example would be an nexample2-way set associative snoop filter instance that will be fully associative in the case of nexample2 being equal to the number of storage locations in the snoop filter instance and mexample2 being equal to 1.[0050] Any snoop filter instance, that being an initial snoop filter instance or final snoop filter instance, may according to the invention be considered as having the same functionality as a general snoop filter. A general snoop filter may here be considered as an independent snoop filter, e.g., a snoop filter comprising only one instance. A directory of a snoop filter instance may according to any embodiment of the present invention be considered comprising the storage locations of that snoop filter instance. Each snoop filter instance is configured to operate in parallel with any other snoop filter instance, e.g., synchronously or asynchronously.[0051] It will be appreciated by a person skilled in the art that the storage locations of any snoop filter instance, that being an initial snoop filter instance or final snoop filter instance, may be considered as making up a registry. The registry may consequently be considered as configured to store a number of snoop filter entries, with one entry per storage location. An entry may be considered as the information stored in a storage location.[0052] Figure 5 schematically illustrates a snoop filter storage location according to the invention that is configured to store a tag identifying a cache line storable in a cache element, and to store P presence vectors. Item a) of figure 5 shows storage of one presence vector, item b) of figure 5 shows storage of two presence vectors and item c) of figure 5 shows storage of 16 presence vectors in an entry. A tag and a presence vector stored in the same storage location of a snoop filter instance may according to any embodiment of the invention be considered as being associated with each other.[0053] A presence vector may in short be interpreted as at least one bit that contains information regarding whether the cache line identified by the tag stored in the same storage location as said presence vector is present in a given cache element. A presence vector may in addition contain an identifier for the said cache line. Figure 3 is a schematic illustration of a presence vector where item a of figure 3 comprises one bit and item b of figure 3 comprises a plurality of bits. The number of presence vectors P in each storage location is according to the invention a constant number. P does in other word not change with the reorganization of the snoop filter device, i.e., P does not scale with C. The number P may e.g., be chosen when fabricating the snoop filter device, or be chosen when configuring the snoop filter device, e.g., during a rebooting operation.[0054] The number of presence vectors P storable in each snoop filter storage location is according to the invention a real positive integer, e.g., a real positive integer number to the power of 2. The P number of presence vectors storable in each snoop filter storage location is according to one embodiment of the invention smaller or equal to 16. P may be equal to 1, or alternatively be equal to 2. Figure 5 illustrates three examples of a snoop filter entry, one where P = 1, one where P =2 and one where P = 16.[0055] A tag may in the context of the present invention be considered as a unique identifier of a cache line and is typically included as at least part of a cache line address. A cache line address may additionally comprise any one or more of an index, an offset, flag bits, and any number of state bits etc. A cache line address or a part of a cache line address may together with a cache block constitute a cache line. A cache line comprises in other words at least a cache block and optionally at least parts of a cache line address. A tag can according to any embodiment of the invention be considered as associated with the cache line that it identifies.[0056] The snoop filter device is as illustrated in figure 2 configured to be organized by grouping initial snoop filter instances together into an Sf number of final snoop filter instances, e.g., such that 2x · Sf = Si, x = {1,2,3,…}. In the snoop filter instance in the middle of figure 2a 2Sf = Si which means that the number of sets are reduced so 2mi = mf. In the rightmost snoop filter instance 2= , where x = 2 and consequently 4Sf = Si and thus 4mi = mf. In the middle of figure 2b each set of the final snoop filter instance comprises a double number of entries, i.e., nf = 2ni, thus mi = mf and 2Sf = Si. In the rightmost figure nf = 4ni and 4Sf = Si. The snoop filter device may in other words be considered as being organized from an initial snoop filter organization to a final snoop filter organization. The initial snoop filter organization may thus be defined by the parameters Si, mi and ni, while the final snoop filter organization may be defined by the parameters Sf, mf and nf. The grouping of initial snoop filter instances into a number of final snoop filter instances will result in the number of final snoop filter instances Sf being smaller than the number of initial snoop filter instances Si. The number of storage locations in the snoop filter device will, however, remain the same such that . The organization of the snoop filter device will thus be made in such a manner that the product Sf·mf·nf equals Si·mi·ni.[0057] Each snoop filter instance of the snoop filter device, that being an initial snoop filter instance or a final snoop filter instance, may according to the invention store any individual given tag in maximum one of its storage locations. As the storage location storing the given tag will also store P different presence vectors, i.e., P presence vectors associated with the given tag, each snoop filter instance will consequently hold information regarding the presence of the cache line identified by the given tag in P separate cache elements. One may in other words say that each snoop filter instance may track P separate cache elements for each tag. As the snoop filter device comprises an Si or Sf number of snoop filter instances, the snoop filter device as a whole may consequently hold information regarding the presence of a given cache line identified by a given tag in P · Si,f separate cache elements. Each snoop filter instance may thus track P · Si,f separate cache elements for each tag.[0058] A storage location of one snoop filter instance may store a given tag that is also stored in a storage location of another snoop filter instance. The entries in the two different instances, each comprising the same tag, may further comprise different presence vectors. The snoop filter device according to this invention may therefore track more cache elements that are storing a cache line identified by a single tag compared to a conventional snoop filter device. Figure 6 is a schematic illustration of a snoop filter device comprising S snoop filter instances where a tag, tag A, is stored in each of the S snoop filter instances. The tag A is here associated with two separate presence vectors for each snoop filter instance meaning that the snoop filter device may track a maximum of 2·S cache elements where the cache line identified by tag A is stored. Figure 7 is a schematic illustration of a snoop filter device comprising a plurality of snoop filter instances where separate tags, tag A, B and Z, are stored in each of the snoop filter instances. The number of cache elements that the snoop filter device can track may in figure 7 be seen to depend on the number of presence vectors in each storage location.[0059] With P being constant, a snoop filter device may according to the invention maximally hold information regarding the presence of a given cache line identified by a given tag in P · Si separate cache elements. One may in other words say that a snoop filter device may track a maximum of P · Si separate cache elements for each tag. The snoop filter device may through grouping of snoop filter instances be organized to track fewer separate cache elements for each tag than P · Si. A snoop filter device being organized with Sf < Si snoop filter instances may consequently track a maximum of P · Sf < P · Si separate cache elements for each tag. A snoop filter device according to the invention may consequently track a variable number C of cache elements. As a way of example, a snoop filter device installed as a component in a computing system that comprises fewer cache elements Cexample than P · Si may group its initial snoop filter instances together in order to organize the snoop filer according to the number Cexample, i.e., such that P · Sf = Cexample or at least such that P · Sf < Cexample < P · Si. Such grouping will allow for larger final snoop filter instances in the final organization of the snoop filter device, i.e., more sets and/or ways in each final snoop filter instance than in the initial snoop filter organization. The initial snoop filter organization may in this example in the event where grouping is not performed have idle snoop filter instances and the snoop filter instances in use will here be smaller than they could optionally have been. The number of final snoop filter instances Sf may thus according to the invention be determined from the number of cache elements connected to the snoop filter device, C, and the number of presence vectors in each storage location P. Sf may thus scale, or in other words vary, with C and P such that Sf = C/P.[0060] The snoop filter device according to the present invention is connectable to a number of cache elements C. Each cache element may further be considered as comprising a number of cache agents, and a cache element may as a whole be referred to as an agent, i.e., for example a proxy agent. A cache element may in the context of the present invention be interpreted as an arbitrary collection of cache agents. A cache element may e.g., be interpreted as comprising any number of cache agents, e.g., an integer number of cache agents, or a fractional number of cache agents. An example of a cache element may thus be half a cache agent, one cache agent, two cache agents, one whole cache agent plus half of another cache agent etc. Cache agents in each cache element may be connected directly, collectively or a combination of directly and collectively to the snoop filter device. It will be appreciated by a person skilled in the art that any cache element may be considered as any physical cache unit, fraction of a physical cache unit or group of cache units that is uniquely identified by one cache identifier. A cache identifier is thus according to the invention an identifier for a cache element.[0061] Figure 9 is a schematic illustration of a presence vector comprising any number of presence bits, e.g., so that the number of presence bits in each presence vector is sufficient to explicitly express a cache identifier. A presence vector may additionally or alternatively comprise one occupation bit. The occupation bit may be set true if a cache line identified by the tag associated with said presence vector is present at the cache element represented by the cache identifier, and false if the cache line is not present.[0062] Figure 8 is a schematic illustration of a snoop filter instance where each snoop filter storage location is mapped to one cache element. Each snoop filter storage location of a snoop filter device may according to any embodiment of the present invention be mapped to one cache element. This mapping means that any one snoop filter storage location may only track the cache element to which it is mapped. Any one snoop filter storage location may in other words only contain information that relates to cache lines that are stored in the cache element to which that snoop filter storage location is mapped. Each snoop filter storage location may thus be said to be bijectively mapped to one cache element. A snoop filter storage location storing a given tag may consequently indicate that the cache element to which that snoop filter storage location is mapped holds a copy of the cache line identified by that tag. The same snoop filter storage location may consequently not contain any information regarding which part of the cache element, e.g., which specific cache agent, that holds a copy of the cache line. The same snoop filter storage location may not contain information regarding the presence of the cache line in other cache elements in the system. Each snoop filter storage location of the snoop filter device may according to any embodiment of the invention be considered as being configured to be mapped to one cache element each. Multiple snoop filter storage locations may each be mapped to the same cache element. This means that the snoop filter device may employ multiple snoop filter storage locations to track multiple cache lines in one cache element.[0063] A snoop filter device is according to one embodiment of the invention designed such that each snoop filter storage location is implicitly mapped to one cache element. Each snoop filter storage location is in this case implicitly mapped to one cache element each via a storage location in a snoop filter instance. This mapping may be hardwired, firmware-integrated and/or software-integrated. Consequently, any presence bits constituting a presence vector may not have to explicitly express the cache identifier for the cache element. The number of presence bits per presence vector may be one bit that indicates whether the cache element identified by the cache identifier holds a copy of a certain cache line. The one presence bit is be set true if a cache line identified by the tag associated with said presence bit is present at the cache element to which the storage location of the presence bit is mapped, and false if the cache line is not present.[0064] Each storage location of the snoop filter device is according to the invention configured to store snoop filter entries with the same format. The format of a snoop filter entry is determined by which type of storage location elements the entry comprises and the number of bits allocated to each storage location element. Examples of such storage location elements are: a tag, one or more presence vectors, one or more state bits, etc. The format of a snoop filter entry is also determined by the number of bits allocated to each storage location element, e.g., the number of tag bits and the number of presence bits per presence vector. Two snoop filter entries with the same format thus comprise the same type of storage location elements with the same number of bits allocated to each storage location element. Figure 3 illustrates a snoop filter entry comprising one presence vector, where the presence vector comprises a plurality of bits (Figure 3a) and where the presence vector consists of one bit (Figure 3b).[0065] A snoop filter device can be considered as a device that monitors data traffic to keep track of the coherency state of data blocks belonging to various cache lines. The monitored data traffic may comprise information in the form of at least parts of a cache line address, e.g., information that a certain cache line is being modified. A cache line address may comprise a tag and a k-bit index, where at least a part of the k bits are used to determine/index which set in a set associative snoop filter instance that contains an entry with the index’s appurtenant, i.e., associated, tag. A tag belonging to a certain cache line address can in this case only be stored as a part of an entry in a set of a set associative snoop filter instance indicated by the index of that cache line address. A cache line may thus in other word be associated with a set in an instance via the index of its cache line address.[0066] A cache line address may, as illustrated in figure 4, comprise a tag and a k-bit index, where at least a part of the k-bit index may be used to determine/index which set in a snoop filter instance that contains an entry holding the index’s appurtenant, i.e., associated, tag. A 4-bit index can for example index 16 different sets, while an 8-bit index can index 256 different sets. In some cases, e.g. as illustrated in figure 4, a cache line comprises a k-bit index where 2k > mi,f, meaning that the full index of the cache line address may indicate a set which does not exist in snoop filter instance. Any snoop filter instance of the snoop filter device may, when 2k > mi,f, therefore store the tag associated with the k bit index in a set indicated by the log2(mi,f) least or most significant bits of the k bit index. The length k of the index may be determined by various system parameters, such as the associativity of various agents, e.g., cache elements or snoop filter agents. The degree of associativity here means the value of n in an n-way set associative agent. An agent being direct mapped has as previously described an associativity n = 1, an agent being two-way set associative has an associativity n = 2, an agent being four-way set associative has an associativity n = 4, and so on.[0067] A snoop filter device may, as schematically illustrated in figure 2, be fabricated with an initial number Si of snoop filter instances implemented in the snoop filter device. This initial number of snoop filter instances may e.g., be hardware or software implemented and determines the maximal number of snoop filter instances that the snoop filter device can comprise. An example of such a snoop filter device is an ASIC-based snoop filter device fabricated with an initial number of physically implemented instances. The initial number of snoop filter instances may be any power of two, e.g., 8, 16, 32, 64, or 128.[0068] The snoop filter device may according to an embodiment of the invention be driven by a separate unit, e.g., a node controller or a CPU. Said unit may be configured to operate the initial snoop filter instances fully independently or to operate groups of two or more final snoop filter instances simultaneously as if they were one instance. The unit driving the snoop filter device may, in order to track the maximum number of cache elements, operate each of the Si initial snoop filter instances individually. As each snoop filter instance can track P number of cache elements per tag, the maximal number Cmax of cache elements that a snoop filter device can track in this case becomes Cmax = P · Si. If it is desirable to track a number of cache elements that is lower than the maximum Cmax, the unit driving the snoop filter device may group multiple initial snoop filter instances into Sf larger final instances, i.e., effective instances. Grouping of snoop filter instances may in practice be done for example through addressinterleaving. [0069] As an example, a snoop filter device may be designed with an initial number Si of initial snoop filter instances with mi sets in each initial instance and with ni storage locations per set in each initial instance. Si, m,, and n, may here be any positive integer, e.g., Si = 29, where g = {1,2,...}, m, = 2h, where h = {0,1,2,...} and n, = 2j, where j = {0,1,2,...}. The snoop filter device is as here described configured to track a maximum Cmax number of cache elements, where Cmax= P ■ Si. The snoop filter device may track a number C < Cmax of cache elements by grouping multiple initial snoop filter instances together. If it for example is desirable to track C = Cmax/2 cache elements with a snoop filter device designed with Si number of initial snoop filter instances, the snoop filter device, or component driving the snoop filter device, may e.g., group two and two initial snoop filter instances together. In the latter case the snoop filter device would end up with an Sf = Si/2 number of final snoop filter instances, m and mf will be determined according to the equation meaning in this example that If for example then then mf [0070] Si, m,, and n, may according to any embodiment of the invention each be any positive integers, e.g., Si = 29, where g = {1,2,...}, m, = 2h, where h = {0,1,2,...} and n, = 2j, where j = {0,1,2,...}. m, may e.g., be in the order of hundred, thousand or ten thousand, n, may e.g., be in the order of hundred, thousand or ten thousand. Si may e.g., be equal 8, 16, 32, 64, 128 or 256.[0071] Figure 10 and 11 illustrates a node controller comprising a snoop filter device.The node controller may be configured to drive a snoop filter device and may be configured to group initial snoop filter instance in the snoop filter device into final snoop filter instances. The snoop filter device may here be connected to C cache elements via the node controller.[0072] Figure 12 illustrates a multicomponent computer system comprising a C number of cache elements, and a snoop filter device connected with the C cache elements. Figure 13 illustrates a multicomponent computer system comprising a C number of cache elements, and a node controller comprising a snoop filter device, where the node controller is connected with the C cache elements.[0073] Figure 14 illustrates a computer-implemented method comprising the step of: organizing a snoop filter device according to the first aspect of the invention, when the snoop filter device is connected to a C number of cache elements, such that the product Sf-mpm equals the product Si-mi-n,, and where Sf equals C/P. The computer-implemented method may, as appreciated by a person skilled in the art, be performed by suitable means. Suitable means may here be a CPU, group of CPUs, a node controller or other suitable means. The computer-implemented method may be stored as a series of executable instruction on a computerreadable storage medium, e.g. installed in a node controller as schematically illustrated in figure 10 and 11. Said instructions may be executed by a computer system, or a component of a computer system, e.g. a CPU, group of CPUs or a node controller. The execution of said instructions may cause the computer system to carry out said computer-implemented method.
Claims
Claims1. A snoop filter device for being organized in order to track a variable C number of cache elements, where- the snoop filter device comprises an Si number of initial snoop filter instances,- the snoop filter device is connectable to a C number of cache elements, - the snoop filter device is configured to be organized, when the snoop filter device is connected to the C number of cache elements, by grouping initial snoop filter instances together into an Sf number of final snoop filter instances,- each initial snoop filter instance comprises an Li number of snoop filter storage locations organized in an ni-way set associative manner with an mi number of sets and an ni number of storage locations per set, such that Li equals mi · ni,- each final snoop filter instance comprises an Lf number of snoop filter storage locations organized in an nf-way set associative manner with an mf number of sets and an nf number of storage locations per set, such that Lf equals mf · nf, and where- each snoop filter storage location is configured to store a tag identifying a cache line storable in a cache element, and to store a P number of presence vectors, each presence vector containing information regarding the presence of the cache line identified by the tag,where the product Sf·mf·nf equals the product Si·mi·ni, where Sf < Si and where Sf equals C/P.2. The snoop filter device according to claim 1 or 2, where- each cache line comprises a cache line address comprising a given tag and a given k bit cache line index, and- any snoop filter instance of the snoop filter device, when 2k > mf, is configured to store the given tag in a set indicated by the log2(mf) least or most significant bits of the given k bit cache line index.3. The snoop filter device according to any one of the preceding claims, where P ≤ 16.4. The snoop filter device according to claim 4, where P = 1 or where P = 2.5. The snoop filter device according to any one of the preceding claims, where- Sf ≥ 2,- each snoop filter instance among the Sf final snoop filter instances is configured to store the same tag in one if its storage locations, and where - each of the storage locations of the snoop filter device that stores the same tag are configured to store different presence vector/vectors.6. The snoop filter device according to any one of the preceding claims, where each snoop filter storage location is mapped to one cache element.7. The snoop filter device according to any one of the preceding claims, wherein each presence vector comprises a number of presence bits, and where the number of presence bits is equal to a number of bits required to write a cache element identifier plus one additional bit.8. The snoop filter device according to any one of the claims 1 - 6, wherein each presence vector consists of one presence bit.9. A node controller comprising a snoop filter device according to any one of the claims 1 – 8.10.A multicomponent computer system comprising:- a C number of cache elements, anda snoop filter device according to any one of the claims 1 - 8 connected with the C cache elements, ora node controller according to claim 9 where the snoop filter device of the node controller is connected with the C cache elements.11.A computer-implemented method comprising the step of:a) organizing a snoop filter device according to any one of the claims 1 – 8, when the snoop filter device is connected to a C number of cache elements, such that the product Sf·mf·nf equals the product Si·mi·ni, and where Sf equals C/P.12.A data processing system comprising means for carrying out the method of claim 12.13.A computer-readable storage medium comprising instructions which, when executed by a computer system, causes the computer system to carry out the method of claim 12.Patentkrav1. En snoopfilterenhet som er organisert for å spore et variabelt antall C hurtigbufferelementer, der- snoopfilterenheten omfatter et antall Si initielle snoopfilterinstanser,- snoopfilterenheten kan kobles til C antall hurtigbufferelementer,- snoopfilterenheten er konfigurert for å være organisert, når den er koblet til C antall hurtigbufferelementer, ved å gruppere initielle snoopfilterinstanser sammen i et Sf antall endelige snoopfilterinstanser,- hver initielle snoopfilterinstans består av et Li antall snoopfilterlagringssteder organisert på en ni-veis sett-assosiativ måte med et mi antall sett og et ni antall lagringssteder per sett, slik at Li er lik mi · ni,- hver siste snoopfilterinstans består av et Lf antall snoopfilterlagringssteder organisert på et nf-veis sett-assosiativ måte med et mf antall sett og et nf antall lagringssteder per sett, slik at Lf er lik mf · nf, og der- hvert snoopfilterlagringssted er konfigurert for å lagre en tag som identifiserer en hurtigbufferlinje som kan lagres i et hurtigbufferelement, og for å lagre P antall tilstedeværelsesvektorer, der hver tilstedeværelsesvektor inneholder informasjon om tilstedeværelsen av hurtigbufferlinjen identifisert av taggen,- hvor produktet Sf·mf·nf er lik produktet Si·mi·ni, der Sf < Si, og der Sf er lik C/P.2. Snoopfilterenheten ifølge krav 1 eller 2, der- hver hurtigbufferlinje består av en hurtigbufferadress som inneholder en gitt tagg og en gitt k-bit hurtigbufferlinjeindeks, og- enhver snoopfilterinstans av snoopfilterenheten, når 2k > mf, er konfigurert for å lagre den gitte taggen i et sett angitt av log2(mf) minst eller mest betydningsfulle biter av den gitte k-bit hurtigbufferlinjeindeksen.3. Snoopfilterenheten ifølge et hvilket som helst av de foregående kravene, der P ≤ 16.4. Snoopfilterenheten ifølge krav 4, der P = 1 eller der P = 2.5. Snoopfilterenheten ifølge et hvilket som helst av de foregående kravene, der- Sf ≥ 2,- hver snoopfilterinstans blant de Sf endelige snoopfilterinstansene er konfigurert for å lagre den samme taggen i ett av sine lagringssteder, og der- hvert av lagringsstedene til snoopfilterenheten som lagrer den samme taggen, er konfigurert for å lagre forskjellig(e) presensvektor(er).6. Snoopfilterenheten ifølge et hvilket som helst av de foregående kravene, der hvert snoopfilterlagringssted er kartlagt til ett hurtigbufferelement.7. Snoopfilterenheten ifølge et hvilket som helst av de foregående kravene, der hver tilstedeværelsesvektor består av et antall tilstedeværelsesbiter, og der antallet tilstedeværelsesbiter er lik antallet biter som kreves for å skrive en hurtigbufferelementidentifikator pluss én ekstra bit.8. Snoopfilterenheten ifølge et hvilket som helst av kravene 1-6, der hver tilstedeværelsesvektor består av én tilstedeværelsesbit.9. En nodestyringsenhet som omfatter en snoopfilterenhet ifølge noen av kravene 1–8.10. Et flerkomponent datamaskinsystem som omfatter:- C antall hurtigbufferelementer, ogen snoopfilterenhet ifølge noen av kravene 1–8 koblet til de C hurtigbufferelementene, elleren nodestyringsenhet ifølge krav 9 hvor snoopfilterenheten til nodestyringsenheten er koblet til de C hurtigbufferelementene.11. En datamaskinimplementert fremgangsmåte som omfatter trinnet av å:a) organisere en snoopfilterenhet ifølge et hvilket som helst av kravene 1–8, når snoopfilterenheten er koblet til C antall hurtigbufferelementer, slik at produktet Sf·mf·nf er lik produktet Si·mi·ni, og der Sf er lik C/P.12. Et dataprossesseringssystem som omfatter midler for å utføre fremgangsmåten ifølge krav 11.13. Et datalagringsmedium som inneholder instruksjoner som, når de utføres av et datamaskinsystem, forårsaker at datamaskinsystemet utfører fremgangsmåten ifølge krav 11.
Drawings

Priority

No priority

Patent classes

IPC classesG06F 12/084G06F 12/0806G06F 12/0846CPC classesG06F 12/08G06F 12/0806G06F 12/084G06F 12/0846

Citations

US 2021294743 A1 (A1)US 2006224840 A1 (A1)US 2016117249 A1 (A1)

Applicants, owners and inventors

Owners
Numascale AS
Innspurten 15 0663 OSLO NO (OSLO Municipality, Oslo county)Org. number: 992462787Inventors
Helge Simonsen
Thorleifs alle 3 B 0489 OSLO NO (OSLO Municipality, Oslo county)
Thibaut Palfer-Sollier
Mortensrudveien 8 X 1283 OSLO NO (OSLO Municipality, Oslo county)
Kai Arne Midjås
Hakkespetten 9 1407 VINTERBRO NO (ÅS Municipality, Akershus county)
Steffen Persvold
Gladengveien 8 D 0661 OSLO NO (OSLO Municipality, Oslo county)
Einar Rustad
Godliaveien 2 B 0682 OSLO NO (OSLO Municipality, Oslo county)
Thomas Moen
Jomfrubråtveien 39 B 1179 OSLO NO (OSLO Municipality, Oslo county)
Goutam Debnath
19797 SW Sarah Street OR97007 BEAVERTON US
Mario Lodde
Via Montalbo 3 08016 BORORE (NU) IT

Agent

BRYN AARFLOT AS
BRYN AARFLOT AS

Org. number: 979993269

Name and address are automatically synchronized with the Brønnøysund Register Centre.

Open in The Brønnøysund Register Centre
Stortingsgata 8 0161 OSLO NO (OSLO Municipality, Oslo county)
Org. number: 979993269
Reference: 131521/HT

Status history

Payment history

Oppositions and appeals

No oppositions or appeals

Administrative limitation

No administrative limitation

Liens and licences

No liens or licenses registered

Gazette entries

No Gazette entries foundOnly events from 2024.03.04 and onwards are shown.