Granted Patent B2

US 12,561,248 · App. 18/493,951 · Granted Feb 24, 2026

Inventor: Eric Francis Robinson (Raleigh, NC)

Assignee: Microsoft Technology Licensing, LLC

G06F12/0831G06F12/0891

Abstract

Claims (45)

1 . A method, comprising:

generating a full tracking vector wherein each bit of the full tracking vector indicates cache validity state of a coherence granule (cogran) in an agent cache for a related agent;

dividing the full tracking vector into a plurality of partial vectors (PVECs);

for each PVEC, determining whether a cache validity state of at least one bit in the PVEC is set to valid; and

in response to determining that the cache validity state of at least one bit in a given PVEC is set to valid, storing the given PVEC and an associated PVEC pointer in a tracking_info field of a base snoop filter (SFT) entry for the cogran and setting a summary bit related to the PVEC vector to one (1), wherein the associated PVEC pointer indicates the location of the given PVEC in the full tracking vector.

2 . The method of claim 1 , further comprising changing a tracking_mode of the base SFT entry to PVEC.

3 . The method of claim 1 , wherein dividing the full tracking vector into a plurality of PVECs further comprises dividing the full tracking vector into four PVECs.

4 . The method of claim 1 , further comprising:

determining that more than one PVECs of the full tracking vector have at least one bit set to valid; and

in response to determining that more than one partial vectors of the full tracking vector have at least one bit set to valid, acquiring an available SFT entry as an extra SFT entry, and storing an additional PVEC and its PVEC pointer in a tracking_info field of the extra SFT entry.

5 . The method of claim 4 , further comprising changing an entry_state of the base SFT entry to SEARCHABLE_E and changing an entry_state of the extra SFT entry to EXTRA.

6 . The method of claim 1 , further comprising:

determining that an extra SFT entry is unable to store any more PVECs; and

in response to determining that the extra SFT entry is unable to store any more PVECs, changing a tracking_mode of the base SFT entry to IMPRECISE.

7 . The method of claim 1 , further comprising, in response to determining that more than one PVECs has a PVEC summary bit set to one, setting an entry_state of the base SFT entry to SEARCHABLE_E.

8 . The method of claim 1 , wherein the full tracking vector tracks 128 agents and each PVEC has 32 bits.

9 . One or more tangible computer-readable storage media, encoding computer-executable instructions for executing on a computer system a computer process, the computer process comprising:

generating a full tracking vector wherein each bit of the full tracking vector indicates cache validity state of a coherence granule (cogran) in an agent cache for a related agent;

dividing the full tracking vector into a plurality of partial vectors (PVECs);

for each PVEC, determining whether a cache validity state of at least one bit in the PVEC is set to valid; and

in response to determining that a cache validity state of at least one bit in a given PVEC is set to valid, storing the given PVEC and an associated PVEC pointer in a tracking_info field of a base snoop filter (SFT) entry for the cogran and setting a summary bit related to the PVEC vector to one (1), wherein the associated PVEC pointer indicates the location of the given PVEC in in the full tracking vector.

10 . The one or more tangible computer-readable storage media of claim 9 , wherein the computer process further comprises changing a tracking_mode of the base SFT entry to PVEC.

11 . The one or more tangible computer-readable storage media of claim 9 , wherein dividing the full tracking vector into a plurality of PVECs further comprises dividing the full tracking vector into four PVECs.

12 . The one or more tangible computer-readable storage media of claim 9 , wherein the computer process further comprises:

determining that more than one PVECs of the full tracking vector have at least one bit set to valid; and

in response to determining that more than one partial vectors of the full tracking vector have at least one bit set to valid, acquiring an available SFT entry as an extra SFT entry, and storing an additional PVEC and its PVEC pointer in a tracking_info field of the extra SFT entry.

13 . The one or more physically tangible computer-readable storage media of claim 12 , wherein the computer process further comprises changing an entry_state of the base SFT entry to SEARCHABLE_E and changing an entry_state of the extra SFT entry to EXTRA.

14 . The one or more tangible computer-readable storage media of claim 9 , wherein the computer process further comprises:

determining that an extra SFT entry is unable to store any more PVECs; and

in response to determining that the extra SFT entry is unable to store any more PVECs, changing a tracking_mode of the base SFT entry to IMPRECISE.

15 . The one or more tangible computer-readable storage media of claim 9 , wherein the computer process further comprises in response to determining that more than one PVECs has a PVEC summary bit set to one, setting an entry_state of the base SFT entry to SEARCHABLE_E.

16 . A system comprising:

memory;

one or more processor units; and

a cache coherence system stored in the memory and executable by the one or more processor units, the cache coherence system encoding computer-executable instructions on the memory for executing on the one or more processor units a computer process, the computer process comprising:

generating a full tracking vector wherein each bit of the full tracking vector indicates a cache validity state of a coherence granule (cogran) in an agent cache for a related agent;

dividing the tracking vector into a plurality of partial vectors (PVECs);

for each PVEC, determining whether a cache validity state of at least one bit in the PVEC is set to valid; and

in response to determining that a cache validity state of at least one bit in a given PVEC is set to valid, storing the given PVEC and an associated PVEC pointer in a tracking_info field of a base snoop filter (SFT) entry for the cogran and setting a summary bit related to the PVEC vector to one (1), wherein the associated PVEC pointer indicates the location of the given PVEC in in the full tracking vector.

17 . The system of claim 16 , wherein the computer process further comprises changing a tracking_mode of the base SFT entry to PVEC.

18 . The system of claim 16 , wherein dividing the full tracking vector into a plurality of PVECs further comprises dividing the full tracking vector into four PVECs.

19 . The system of claim 18 , wherein the computer process further comprises:

determining that more than one PVECs of the full tracking vector have at least one bit set to valid; and

in response to determining that more than one partial vectors of a full tracking vector have at least one bit set to valid, acquiring an available SFT entry as an extra SFT entry, and storing an additional PVEC and its PVEC pointer in a tracking_info field of the extra SFT entry.

20 . The system of claim 16 , wherein the computer process further comprises, in response to determining that a cache validity state of one or more of the PVECs are set to valid, storing the one or more PVECs in the base entry.

Assignments (1)

Continuity (1)

References Cited (11)