Patent ID: 12189533

DETAILED DESCRIPTIONS

Implementations disclosed herein disclose multi-processor systems that employ hardware (HW)-enforced cache coherency in which when an agent, such as a CPU, a GPU, etc., wants to access a memory location, HW automatically determines whether another agent currently holds a copy of that memory location. If the access is a read and the memory location is cached by another agent, system memory might be stale, in which case the access must be satisfied by obtaining the data from the other agent's cache. If the access is a write, typically other cached copies must be first written back to system memory. The memory block for which HW-enforced cache coherency is maintained is called a coherence granule (cogran) and system may match its cogran size to the cache line size.

In some implementations, the system may maintain a list of which cograns are currently cached by which agents. In other implementations, there may be no central coherence directory that needs to be maintained, and instead, during the course of handling the requested memory access, all agents are queried to determine whether any holds a copy of the cogran in their cache. This query is commonly referred to as a snoop. An over-snoop condition occurs when an agent is snooped to search for a cogran in its cache and that agent does not currently hold a copy of that cogran. The snoop is functionally useless and unnecessarily perturbs that agent. A system disclosed herein discloses advantageous implementations using a snoop filter (SFT) to help reduce over-snooping. Such implementations reduce over-snooping penalties in terms of latency added to the memory access, interconnect bandwidth consumed for no functional benefit, and energy wasted to perform unnecessary cache lookup(s) at the agents that are over-snooped. A snoop filter may be thought of as a higher-level, inclusive, set-associative cache that has no data and whose purpose is to track the entire set of cograns held by the lower-level cache(s) for which cache coherence needs to be maintained.

An imprecise snoop filter is a filter that tracks that a cogran has been cached by some agent at some point. This SFT is smaller than other types but the lack of precision means that when a snoop needs to be sent, all coherent caches in the system need to be snooped. The lack of precision also means that the SFT generally loses the ability to detect when the cogran has been evicted from all the coherent caches.

A precise snoop filter may employ a vector to track exactly which agents have cached a copy of a cogran. A precise SFT requires a relatively large amount of area to implement because it tracks a lot of state, 1 bit per agent per cogran tracked. In this implementation, when an agent obtains a copy of a cogran to write into its cache, the agent's corresponding vector bit in the SFT entry tracking that cogran is set. When the agent later evicts the cogran, its corresponding vector bit in the SFT entry tracking that cogran is cleared. This has a couple of advantages over the imprecise SFT: (a) only the exact agents that need to be snooped will be snooped; (b) the snoop scope can be further reduced over time as individual agents evict the cogran from their caches and the SFT is updated accordingly, this applies only to evictions that the agents communicate to the SFT.

In a hybrid implementation an SFT may track precisely up to (n) agents (typically, 2-3) by recording their agent ID (AID) in the SFT's cogran tracking information. The AID may be a unique identifier for each agent that the SFT tracks. For example, the AID could be an encode of the SFT vector position that agent may otherwise set. Alternatively, the AID may be the agent's interconnect address—the ID used by the interconnect to send messages to that agent. When >(n) agents have cached a copy of the cogran, the SFT switches from AID-tracking to imprecise-tracking. When the hybrid implementation is in an AID-tracking_mode, there are no over-snoops because the SFT entry knows exactly whom to snoop. On the other hand, when the hybrid implementation is in an imprecise tracking_mode, the SFT entry indicates that all agents need to be snooped if the cogran is currently held, or tracked, by the SFT. When the system has many coherent agents (e.g., 128), this approach employs less HW than the precise vector SFT—recording (n) AIDs (for a small enough n) require fewer state bits than a large vector.

In a system with many coherent agents (e.g., 128) the over-snooping due to imprecise tracking is very costly in terms of fabric bandwidth consumed and energy wasted. Furthermore, the larger SFT needed for precise tracking is very costly in terms of area which also causes snoop (and other) message travel distances to grow. Workloads with many agents sharing data structures or sharing instruction pages may quickly exhaust the precise-AID tracking ability of the hybrid approach and may lead to the imprecise tracking_mode being used more often. While some amount of over-snooping may be tolerated because the various imprecise tracking modes generally don't have the ability to recover back to precise tracking as cograns are evicted, snoop filter management itself incurs an over-snooping overhead. Specifically, when the snoop filter is unable to know which cograns are no longer cached by any agents, the snoop filter may more frequently send “filter flush” snoops to make room in the SFT itself so that it may install a newly tracked cogran in the SFT. The purpose of a filter flush snoop for an SFT entry is to cause a victimized cogran to be evicted from all agents because the SFT may lose the ability to track that cogran when it completes the victimization of that SFT entry.

FIG.1discloses an implementation of a cache coherence system100using snoop filters that improves upon one or more of the above implementations. Specifically, the cache coherence system100may be implemented on a multi-core architecture that includes a number of central processing unit (CPU) cores,102and104, a graphical processing unit (GPU)106, one or more input/output (I/O) agents108, a point of serialization (PoS)110, and a memory114. Although the present example shows two CPU cores and one GPU, it is understood that any number of CPU cores and CPUs can be used without deviating from the scope of the present disclosure. Examples of the I/O agents108include, but are not limited to, Industry Standard Architecture (ISA) devices, Peripheral Component Interconnect (PCI) devices, PCI-X devices, PCI Express devices, Universal Serial Bus (USB) devices, Advanced Technology Attachment (ATA) devices, Small Computer System Interface (SCSI) devices, and InfiniBand devices.

The processing unit cores102,104,106, and the I/O agents108may be referred to as agents102-108, each referenced by agent IDs (AIDs). These agents102-108may have multiple levels of internal caches such as L1, L2, and L3 caches. As the agents102-108cache coherent memory blocks (cograns) in their internal caches, a snoop filter (SFT)150may keep track of those cograns and of which agents102-108have cached each one. Any of the agents102-108may issue coherent or non-coherent requests and the PoS110ensures the serialization of the memory access requests using the snoop filter150to provide memory coherency.

For example, the PoS110receives a coherent request120from a CPU102. In response to the coherent request120, the PoS110issues a snoop command122to the CPU cores104, the GPU106, and the I/O agents108. The CPU cores104, the GPU106, and the I/O agents108may provide the requested coherent information back to the PoS110. When sending the snoop122, the PoS110refers to the SFT150.

An example implementation of the SFT150is illustrated by SFT150a. The SFT150aincludes a data structure to track the address and agent(s)102-108that have obtained a copy of every cogran that is currently cached by agents102-108. The SFT150amay have an n-way set-associative organization as indicated by n-arrays154. The snoop filter150amay include an array of entries152, the content of the entries152is further described below. Each of the entries152may include a Tag field, such as the Tag field218disclosed inFIG.2, that is used to store a tag portion of physical address (PA) that identifies a cogran. For example, for cogran size of 64 bytes, and SFT being a 16-way associative SFT, bits 15:6 of the PA may be used to select an SFT set and bits 47:16 of the PA may be stored as the tag in the Tag field218of the SFT entries152. When the SFT150aneeds to perform a lookup to see if a cogran's PA is present in the SFT150a, it selects one of the 16 sets using PA[15:6]. Subsequently, for the selected set, the SFT150amay compare156the PA[47:16] against the tag values stored in the Tag field218of the 16 SFT entries152in the selected set. If the Tag field218of any of the 16 SFT entries in the selected set finds a match, then its way (e.g., way 5) is currently tracking the cogran being looked up.

In an implementation of the SFT150adisclosed herein, a logical entry152may be configured to hold up to n agent IDs (AIDs) in a base SFT entry162and to dynamically allocate an extra SFT entry164in an SFT set for the cases where a cogran is shared by more than n agents. For example, in one implementation n may be three (3) such that the base SFT entry162is configured to hold 3 AIDs and in cases where a cogran is shared by more than 3 agents, the extra SFT entry164is dynamically allocated. Additionally, when the extra SFT entry164is dynamically allocated, the base SFT entry162amay hold a portion of the SFT entry's tracking vector and the extra SFT entry164may hold another, remainder, portion of the SFT entry's tracking vector. Here a tracking vector includes a number of validity bits with the length of the tracking vector being the maximum number of agents102-108that might obtain the cogran corresponding to the Tag field of that SFT entry. There is thus a 1:1 correspondence between each agent instance and each bit of the tracking vector. In one implementation, the tracking vector may have 128 bits, thus tracking 128 agents102-108for the cogran corresponding to the Tag field of that SFT entry. Each validity bit may take a value of valid or invalid indicating a cache validity state of the cogran for an agent identified by the validity bit.

For example, the value of a validity bit being valid may indicate that the agent102-108that corresponds to that validity bit has cached the cogran corresponding to the Tag field of that SFT entry in its private cache, referred to as a valid cache validity state for that agent. On the other hand, a value of invalid for an invalidity bit indicates that the agent102-108that corresponds to that validity bit has not cached the cogran corresponding to the Tag field of that SFT entry in its private cache, referred to as an invalid cache validity state for that agent102-108. The tracking vector and the validity bit values are further described below with respect toFIG.4.

Specifically, the base SFT entry162aholds the SFT entry's state information and the extra SFT entry164may give the base SFT entry162aan additional storage needed to track additional agents, for example 128 agents, in a fine-grained manner for the times that a cogran is widely shared beyond the n AIDs in the base SFT entry162a. In other words, a logical SFT entry in the SFT150amay include either one base SFT entry162that may track up to n AIDs or combination of one base SFT entry162aand an extra SFT entry164that is able to track every agent in the system that might coherently cache a cogran.

When the logical SFT entry includes only one base SFT entry162, the entry_state field166of the SFT entry162may be either IDLE or SEARCHABLE and the Tracking_mode field168of the SFT entry162be one of NA (if entry_state=IDLE), AID or IMPRECISE. On the other hand, when the logical SFT entry includes a combination of one base SFT entry162aand an extra SFT entry164, the Entry_state field166of the base SFT entry162amay be changed to SEARCHABLE and the Tracking_mode field168of the base SFT entry162amay be changed to VECTOR or AID_ME. On the other hand, in this case, the Entry_state field166of the extra SFT entry164is set to EXTRA and the Tracking_mode field168of the extra SFT entry164is set to NA. when the Tracking_mode field168of the base SFT entry162ais changed to VECTOR, the tracking_info field of the extra entry162amay store portion of tracking vector. When the Tracking_mode field168of the base SFT entry162ais changed to AID_ME, the tracking_info field of the base entry162aand the tracking_info field of the extra entry164may store more AIDs.

In an implementation disclosed herein, the cache coherence system100enables the logical SFT entry152to de-allocate the extra SFT entry164when it is no longer needed to hold the tracking information. Specifically, the cache coherence system100enables the extra SFT entry164to be victimized without victimizing the logical SFT entry152. Furthermore, the two physical SFT entries162aand164that make the logical SFT entry152are consolidated into a single physical SFT entry. Specifically, the two physical SFT entries162aand164are consolidated into the extra SFT entry164if an SFT victim selection logic170of the cache coherence system100determines to evict an SFT base entry such as the SFT base entry162that has an extra SFT entry associated therewith. The implementation of the cache coherence system100with the victim selection logic170in this manner enables the extra SFT entry164to hold more agent IDs (AIDs) rather than being limited to holding a precise vector. Furthermore, it also enables the logical SFT entry152to have more than one extra entries. The functioning of the victim selection logic170to achieve these objectives is disclosed below in further detail.

The detailed structure of the base SFT entries162and162a, and the extra SFT entry164are illustrated in further detail below inFIG.2. The implementation of the SFT entry152in the manner disclosed herein allows the cache coherence system100to take advantage of the fact that most cograns are not cached concurrently by more than a few of the agents104-108.

FIG.2illustrates a structure of a logical snoop filter entry200implementing the technology disclosed herein. Specifically, the logical snoop filter entry200may be configured to hold up to n agent IDs (AIDs) in a base SFT entry262and to dynamically allocate an extra SFT entry264in an SFT set for the cases where a cogran is shared by more than n agents. For example, in one implementation n may be three (3) such that the base SFT entry262is configured to hold up to 3 AIDs and in cases where a cogran is shared by more than 3 agents, the extra SFT entry264is dynamically allocated. Additionally, when the extra SFT entry264is dynamically allocated, the base SFT entry262amay hold a portion of the SFT entry's tracking vector and the extra SFT entry264may hold another, remainder, portion of the SFT entry's tracking vector. Alternatively, with the allocation of the extra SFT entry264, in one mode, both the base SFT entry262aand the extra SFT entry264may be configured to store a series of AIDs.

The base SFT entry262may include an Entry_state field214that may be set to either IDLE or SEARCHABLE. A Tracking_mode field216may be one of NA (if entry_state=IDLE), AID or IMPRECISE. Additionally, the base SFT entry262may include a Tag field218and a miscellaneous field220. A Tracking_info field222may include 3 AIDs and an ECC field224may store error correction code bits.

It may be determined that a logical SFT entry200has an extra entry when its Entry_state214is set to SEARCHABLE and its Tracking_mode216is set to VECTOR or AID_ME. When the Tracking_mode216of the base entry262ais set to VECTOR, the base entry262ais configured for SFT hit determination and can hold a portion of the SFT entry's tracking vector. When the Entry_state214is set to SEARCHABLE, and the Tracking_mode216is set to AID_ME, the base entry262ais configured to store a series of AIDs in its Tracking_info field222a. Furthermore, in this mode the extra SFT entry264is configured to also store a series of AIDs.

Additionally, the base SFT entry262amay include a Tag field218aand a miscellaneous field220a, and an extra_entry field221. An ECC field224amay store error correction code bits. The extra_entry field221indicates which other SFT physical entry has been assigned to be the extra entry for the logical SFT entry to which a base SFT entry262abelongs if that logical SFT entry200has an extra entry. In one implementation, the extra_entry field221is present, even when the logical SFT entry200has no associated extra entry. In an alternative implementation, the extra_entry field221does not exist when the implementation of the logical SFT entry200hard codes for each physical base SFT entry, which other physical entry has been pre-assigned to be that physical base SFT entry's extra entry when the logical SFT entry200's state indicates that it has an extra entry.

The extra SFT entry264may have its entry_state field214bset to EXTRA and its Tracking_mode field is (not applicable) NA. The remainder of the portion of the SFT entry's tracking vector may be stored in a Tracking_info field222bwhen the tracking_mode216is set to VECTOR or store a series of AIDs when the tracking_mode216is set to AID_ME. An ECC field224bmay store error correction code bits.

Thus, the logical SFT entry200is either (a) just the base SFT entry262when it has no associated extra SFT entry or (b) a combination of the base SFT entry262aand its associated extra SFT entry264. The base SFT entry262participates in SFT lookups in that the base SFT entry262contains a cogran's tag that is compared against tag bits of a physical address (PA) of the cogran to determine whether the lookup finds a hit in the SFT. For example, for a 64-byte cogran being tracked in a 16-way SFT, the tag bits of the PA of the cogran may be PA[47:16], which may be compared with a Tag field of the SFT entry262. On the other hand, the extra SFT entry264may be associated with a base SFT entry, such as base SFT entry262aand may contain agent tracking information for that base SFT entry.

FIG.3illustrates example entry states300for the physical SFT entry of the cache coherence system disclosed herein. As illustrated herein the each logical SFT entry independently switches between the three entry states, namely: IDLE302, SEARCHABLE304, and EXTRA306, depending on real-time conditions and its configuration settings. Specifically, the cache coherence system disclosed herein allows going back to using a single SFT physical entry to hold a logical SFT entry when a logical SFT entry's extra entry is no longer needed to hold tracking information. Thus, the entry_state of a physical entry may change from EXTRA306to IDLE302when (a) when the extra SFT entry is deallocated in response to determining that the number of agents tracked by the extra SFT entry is reduced to the point that the base SFT entry can hold that information, (b) when the extra SFT entry is deallocated in response to determining that only a single agent is tracked by the extra SFT entry, for example by determining that a single vector bit remains valid, and (c) when a logical SFT entry including two physical SFT entries are consolidated into a logical SFT entry including only one physical SFT entry in response to victimization of a logical SFT entry's extra physical SFT entry.

A physical SFT entry's entry state may also change from EXTRA306to SEARCHABLE304when a logical SFT entry including two physical SFT entries are consolidated into a logical SFT entry including only one physical SFT entry in response victimization of a logical SFT entry's base physical SFT entry. In this case, the former extra SFT entry becomes the new base SFT entry. In other words, a logical SFT entry that's comprised of two physical SFT entries may be consolidated into a single physical SFT entry (a) if the extra SFT entry is victimized or if it's no longer needed to hold tracking_info, and therefore the extra SFT entry may be de-allocated or (b) if the base SFT entry is victimized, and therefore, the logical SFT entry may be consolidated to a single physical SFT entry that was formerly its extra SFT entry.

FIG.4illustrates example values of a tracking_info field400for the logical SFT entry of the cache coherence system disclosed herein. The tracking_info field400may store tracking information regarding the agents being tracked by the SFT entry. Specifically, in an AID mode, the width of the tracking_info field402may be provisioned to hold up to 3 AIDs with a width of 13b each, including 12b to identify the AID and 1b to indicate whether the AID is currently valid. In an alternative implementation, a different number of bits may be used to identify the AID. As illustrated herein, in the AID mode the tracking_info field402includes an AID (0)404and its validity bit406, an AID (1)408and its validity bit410, and an AID (2)412and its validity bit414. In the VECTOR mode, 128b of the tracking_info field416are divided such that the first 39b of the tracking vector are stored in a tracking_info_LO field418in base entry262awith the remaining bits of the vector stored in a tracking_info_HI field420in the extra entry264. Alternatively, the width of the tracking_info field416may be as wide as necessary to track as many agents that may obtain a cogran, and therefore need to be snooped. Furthermore, in an alternative implementation, the 128b of the tracking_info field416may be divided in an alternative manner, such as for example, zero (0) bits in the tracking_info_LO field418and all bits in the tracking_info_HI field420.

In this implementation, each agent that needs to be tracked by the SFT may have a unique validity bit in the tracking_info that maps to a particular vector bit position. Thus, for example, the tracking_info_LO field418may have 39 validity bits422-424and the tracking_info_HI field418may have 89 validity bits426-428. Thus, for example, if a validity bit 15 has a value valid, it indicates a valid cache validity state for the agent corresponding to the validity bit 15 indicating that this agent has cached the cogran corresponding to the Tag field of the SFT entry. On the other hand, if a validity bit 22 has a value invalid, it indicates an invalid cache validity state for the agent corresponding to the validity bit 22 indicating that this agent has not cached the cogran corresponding to the Tag field of the SFT entry.

When the base entry of the logical SFT entry is in the AID_ME mode, the tracking_info440afield of the base SFT entry holds a series of AIDs442and related validity bits444. Furthermore, in this mode the tracking_info field440bof the extra SFT entry also holds a series of AIDs446and related validity bits448. Here each AID442,446may be 12b and the validity bits444,448may be 1 bit.

FIG.5illustrates operations500when an SFT needs to allocate an entry to begin tracking a new cogran. Specifically, when the SFT needs to start tracking a cogran, it attempts to allocate an available physical entry to serve as the new logical SFT entry. An operation504determines if an SFT entry is available for use. If an SFT entry is available, an operation506chooses an available SFT entry, an operation510sets the available SFT entry's tracking_mode to AID, and an operation512records the AID and the cogran in the selected SFT entry.

If no physical entry is available, i.e., if no SFT entry is IDLE, an operation508selects an existing entry to victimize. Subsequently, an operation514determines if the selected SFT entry's entry_state is EXTRA. If so, an operation516determines if the SFT is configured to consolidate the selected entry to a single SFT entry when the selected extra SFT entry is victimized. If yes, an operation520uses the operations disclosed below inFIG.6to consolidate to a single SFT entry and as per operation522the victimized SFT entry is now made available to be reused for the new cogran. Once the victimized entry is no longer in use, it's now available to be reused for the new cogran to be installed in the SFT. In this case, the entry's entry_state is set to SEARCHABLE, its tracking_mode is set to AID, its tag field is updated for the new cogran, and its tracking_info is updated to hold the AID of the agent obtaining a copy of the cogran, and as part of updating the tracking_info, the VLD bit associated with the AID field it wrote is set.

If the SFT is not configured to consolidate the selected entry to a single SFT entry an operation524sends a filter flush snoop to all agents who may hold a copy of the victimized cogran, the cogran that's being tracked by the victimized SFT entry. Subsequently, an operation526sets the entry_state of the selected logical SFT entry's base SFT entry to IDLE and an operation528sets the entry_state of the selected logical SFT entry's extra SFT entry to IDLE.

If the operation514determines that the selected SFT entry's entry_state is not EXTRA, an operation518determines if the selected SFT entry's tracking_mode is VECTOR. If yes, an operation530determines if the SFT is configured to consolidate the selected entry to a single SFT entry when the selected base SFT entry is victimized and if so, an operation532uses the operations ofFIG.7below to consolidate to a single entry.

If the operation518determines that the selected SFT entry's tracking_mode is not VECTOR, an operation534sends a sends a filter flush snoop to all agents who may hold a copy of the victimized cogran. Subsequently, an operation536sets the entry_state of the selected logical SFT entry's base SFT entry to IDLE.

FIG.6illustrates operations600when an SFT is configured to consolidate to a single entry when an extra entry is victimized. Specifically, if any of the following conditions (a)-(c) about the logical SFT entry to which the victim extra entry belongs is true, then when the extra entry's entry_state is changed to IDLE (because it was victimized), the base entry's tracking_mode is changed to IMPRECISE. If the logical SFT entry: (a) the logical SFT entry to which the victim extra entry belongs is currently tracking more agents than a single physical entry alone is able to track precisely, (b) the logical SFT entry to which the victim extra entry belongs has >1 vector bit asserted and the SFT is configured to change its tracking_mode to IMPRECISE when >1 vector bit asserted upon consolidation, or (c) the logical SFT entry to which the victim extra entry belongs has 1 vector bit asserted and the SFT is configured to change its tracking_mode to IMPRECISE even when 1 vector bit asserted upon consolidation.

Specifically, an operation604determines if only one (1) vector bit is set for the logical SFT entry to which the victim extra entry belongs. If yes, an operation606determines if the SFT is configured to revert its tracking_mode216to AID when only one vector bit remains set. If the SFT is not configured to revert its tracking_mode216to AID when only one vector bit remains set, an operation616sets the tracking_mode of the base SFT entry to IMPRECISE. Subsequently, an operation618updates that base entry as needed to account for agents whose associated vector bit are currently set in the extra entry, and an operation620sets the tracking_mode of the extra SFT entry to IDLE. Note that an agent may be indicated by either the position of its bit in a tracking vector or by an AID. If the operation606determines that the SFT is configured to revert its tracking_mode216to AID when only one vector bit remains set, an operation610sets the tracking_mode of the base SFT entry to AID, an operation612converts the vector bit to the equivalent AID, records the AID in the base SFT entry, sets the corresponding VLD bit for the AID field being written, and an operation614sets the entry_state of the extra SFT entry to IDLE.

If the operation604determines if more than one (1) vector bit is set for the logical SFT entry to which the victim extra entry belongs, an operation608determines if the SFT is configured to revert its tracking_mode216to AID when more than one vector bit remains set. If yes, an operation622further determines if the base SFT entry has enough space to hold the AIDs corresponding to the agents that remain in the vector (i.e., whose vector bits remain set). If yes, an operation624sets the tracking_mode of the base SFT entry to AID, an operation626converts the vector bits to AIDs and records the vector in the base SFT entry, and an operation628sets the entry_state of the extra SFT entry to IDLE.

FIG.7illustrates operations700when the SFT is configured to consolidate to a single entry when a base entry is victimized and when the SFT needs to victimize a base entry that has an associated extra entry. An operation704defines “base entry 1”=the victim logical SFT entry's base entry and an operation706defines “base entry 2”=the victim logical SFT entry's extra entry. In this case, if any of the following conditions about the logical SFT entry being victimized is true, then when the logical entry is consolidated into a single physical entry (base entry 2), base entry 2's tracking_mode is set to IMPRECISE: (a) if the logical SFT entry is currently tracking more agents than a single physical entry alone is able to track precisely, (b) if the logical SFT entry has >1 vector bit asserted and the SFT is configured to change its tracking_mode to IMPRECISE when >1 vector bit is asserted upon consolidation, or (c) if the logical SFT entry has 1 vector bit asserted and the SFT is configured to change its tracking_mode to IMPRECISE even when 1 vector bit is asserted upon consolidation.

Therefore, an operation708determines if there is only one vector bit that is set for the victim logical SFT entry. If yes, an operation710determines if the SFT is configured to revert an SFT entry's tracking_mode to AID when only one vector bit remains set. If so, an operation714sets the base entry 2's tracking_mode to AID and an operation716converts that vector bit to the equivalent AID, records the AID in the base entry 2's tracking_info, and sets the VLD bit corresponding to the AID field that's being written in base entry 2. Subsequently, an operation724sets base entry 2's entry_state to SEARCHABLE and an operation726sets the base entry 1's entry_state to IDLE.

If the operation708determines that more than one vector bits are set for the victim logical SFT entry, an operation712determines if the SFT is configured to revert an SFT entry's tracking_mode to AID if more than one vector bit remains set. If yes, an operation718determines if a single physical entry of the SFT has enough space to hold AIDs corresponding to the agents that remain in the vector (i.e., whose vector bits remain set). If yes, an operation728sets the base entry 2's tracking_mode to AID and an operation730converts the vector bits to their corresponding AIDs, records the AIDs in base entry 2, and sets the VLD bits corresponding to the AID fields of the tracking_info that are being written to base entry 2. Subsequently the control passes to operation724.

If (a) the operation710determines that the SFT is not configured to revert an SFT entry's tracking_mode to AID when only one vector bit remains set, (b) the operation712determines that the SFT is not configured to revert an SFT entry to AID if more than one vector bit remains set, or (c) if the operation718determines that no single physical entry of the SFT has enough space to hold AIDs for agents that remain in the vector, then an operation720sets the base entry 2's tracking_mode to IMPRECISE. Subsequently, an operation722updates the base entry 2 as needed to account for agents whose associated vector bits are currently set in the extra SFT entry, and the control passes to operation724. Thus, regardless of whether base entry 2's tracking_mode ends up set to AID or IMPRECISE, base entry 2's entry_state is set to SEARCHABLE and base entry 1's entry_state is set to IDLE. Furthermore, the base entry 1 can now be used as needed for another logical SFT entry.

FIG.8illustrates operations800for a case for updating a logical SFT entry when an agent gives up its copy of a cogran. An operation804determines if the tracking_mode of the SFT entry that needs to be updated is set to AID. If so, an operation806further determines if the AID to be removed is the only remaining AID in the SFT entry. If yes, an operation810sets the base entry's entry_state to IDLE. However, if the AID to be removed is the not the only remaining AID in the SFT entry, an operation812removes the AID from the base entry.

If the operation804determines that the tracking_mode of the SFT entry that needs to be updated is not set to AID, an operation808determines if the base SFT entry's tracking_mode is set to VECTOR. If the base SFT entry's tracking_mode is not set to VECTOR, an operation816determines that the tracking_mode is IMPRECISE and updates the SFT as needed for removal of the agent from the SFT entry's tracking_info. If the base SFT entry's tracking_mode is set to VECTOR, an operation814clears the tracking vector bit position corresponding to the agent that's being removed from the tracking_info. Subsequently, an operation818determines if any bits of the tracking vector are still set. If no bits of the tracking vector are still set, an operation822sets the base SFT entry's entry_state to IDLE and an operation824sets the extra SFT entry's entry_state to IDLE.

If one or more bits of the tracking vector are still set, an operation820determines if there is only one bit of the tracking vector that is still set. If there is only one bit of the tracking vector still remains set, an operation826further determines whether the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set. If yes, it indicates that the SFT is configured to allow the extra base entry to be de-allocated while the logical SFT entry continues to track the cogran when there is only a single vector bit asserted. In this case an operation830coverts the vector bit to its equivalent AID and records the AID in the base SFT entry and the AID field's corresponding VLD bit is set. An operation832sets the extra SFT entry's entry_state to IDLE indicating de-allocation of the extra SFT entry and an operation834sets the base SFT entry's tracking_mode to AID. If the operation826determines the SFT is not configured to revert its tracking_mode to AID when only one vector bit remains set, the base SFT entry's tracking_mode remains set to VECTOR and the extra SFT entry continues to be used.

If the operation820determines that more than one bit of the tracking vector remains set, an operation828determines whether the SFT is configured to revert its tracking_mode to AID when more than one vector bit remains set. If the operation828determines the SFT is configured to revert its tracking_mode to AID when more than one vector bit remains set, an operation836further determines if the base SFT entry has enough space to hold AIDs corresponding to the agents whose vector bits remain set. If so, the control is transferred to operation830to covert the vector bits to their equivalent AIDs, record the AIDs in the base SFT entry, and set their corresponding VLD bits in the base SFT entry.

FIG.9illustrates operations900for a case when the SFT needs to allocate an entry to begin tracking a cogran. Specifically, as per operations900when the SFT needs to allocate an entry to begin tracking a cogran, it selects one of the available (if any) physical SFT entries to be the base SFT entry for the logical SFT entry that's being allocated. If no physical SFT entry is available to be used, i.e., none is IDLE, the SFT selects an SFT entry to victimize. An operation904determines if the SFT has a physical SFT entry available for use. If so, an operation906selects an available SFT entry. Subsequently, an operation908sets the selected SFT entry's tracking_mode to AID and sets the SFT entry's entry_state to SEARCHABLE and an operation910records the agent's AID, sets the VLD bit for the AID field, and records the cogran's tag in the selected SFT entry.

If no SFT entry is available to be used, an operation912selects a victim entry. Subsequently, an operation914determines if the selected victim entry's entry_state is EXTRA. If the selected victim entry's entry_state is EXTRA, an operation916determines whether the SFT is configured to consolidate a logical SFT entry to a single SFT entry when the extra SFT entry of the logical SFT entry is victimized. If yes, an operation920initiates the operations further disclosed below inFIG.10and an operation922indicates that a victim entry is now ready to be used with the new cogran. If the operation916determines that the SFT is not configured to consolidate a logical SFT entry to a single SFT entry when the extra SFT entry of the logical SFT entry is victimized, an operation924sends a filter flush snoop for the victimized cogran to all agents who may hold a copy of the victimized cogran. Subsequently, an operation926sets the base SFT entry's entry_state to IDLE and an operation928sets the extra SFT entry's entry_state to IDLE.

If the operation914determines that the selected victim entry's entry_state is not EXTRA, an operation918determines whether the selected victim entry's tracking_mode is either AID_ME or VECTOR. If no, an operation934sends a filter flush snoop to all agents who may hold a copy of the victimized cogran and an operation936sets the base SFT entry's entry_state to IDLE. If the operation918determines that the selected victim entry's tracking_mode is either AID_ME or VECTOR, an operation930determines if the SFT is configured to consolidate a logical entry to a single entry when a base SFT entry is victimized. If so, an operation932calls the operations disclosed below inFIG.11and as per operation922the victim entry is now ready to be reused for the new cogran.

FIG.10illustrates operations1000for a case when a logical SFT entry is comprised of two physical entries and the logical SFT entry's extra entry has been selected to be victimized. The operations1000may be initiated at920in response to determining that the SFT is configured to consolidate a logical SFT entry to a single SFT entry when the extra SFT entry of the logical SFT entry is victimized. Specifically, these operations are for a case when a logical SFT entry is comprised of two physical entry's and the logical SFT entry's extra entry has been selected to be victimized. An operation1004determines whether the base SFT entry's tracking_mode is set to VECTOR. If not, the tracking_mode is set to AID_ME and an operation1008determines if the base SFT entry has enough space to hold the AIDs that are remaining in the extra SFT entry being victimized. If so, an operation1014copies the AIDs from the extra entry to the base SFT entry and an operation1016sets the base SFT entry's tracking_mode to AID, and an operation1017sets the extra SFT entry's entry_state to IDLE.

If the operation1008determines that the base SFT entry does not have enough space to hold the AIDs that are remaining in the extra SFT entry being victimized, an operation1018sets the base SFT entry's tracking mode to IMPRECISE and an operation1020updates the base SFT entry as needed to account for agents whose AIDs are currently valid in the logical SFT entry's tracking_info. Subsequently, operation1021sets the extra SFT entry's entry_state to IDLE.

If the operation1004determines that the base SFT entry's tracking_mode is set to VECTOR, an operation1006determines whether there is only one vector bit set in the logical SFT entry. If so, an operation1010determines if the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set. If so, an operation1022converts the vector bit to its equivalent AID, records the AID in the base SFT entry, and sets the corresponding VLD bit for the AID field being written. Subsequently, an operation1024sets the base SFT entry's tracking_mode to AID, and an operation1026sets the extra SFT entry's entry_state to IDLE. If the SFT is not configured to revert its tracking_mode to AID when only one vector bit remains set, control transfers to operation1030.

If the operation1006determines that there are more than one vector bits set for the associated logical SFT entry, an operation1012determines whether the SFT is configured to revert its tracking_mode to AID if more than one vector bit remains set. If no, an operation1030sets the base SFT entry's tracking_mode to IMPRECISE, an operation1032updates the base SFT entry as needed to account for agents whose associated vector bits are currently set in the logical SFT entry's tracking_info. Subsequently, and an operation1034sets the extra SFT entry's entry_state to IDLE. On the other hand, if the operation1012determines that the SFT is configured to revert its tracking_mode to AID if more than one vector bit remains set, an operation1028determines whether the base SFT entry has enough space to hold AIDs for agents that remain in the tracking vector. If the base SFT entry does not have enough space to hold AIDs for agents that remain in the tracking vector, control transfers to operation1030to update the base SFT entry as needed to account for agents whose associated vector bits are currently set in the extra SFT entry.

If the operation1028determines that the base SFT entry has enough space to hold AIDs for the number of agents that remain in the tracking vector, an operation1036converts vector bits to their equivalent AIDs and records the AIDs along with their associated VLD bits in the tracking_info field of the base SFT entry. Subsequently, an operation1038sets the base SFT entry's tracking_mode to AID, and an operation1040sets the extra SFT entry's entry_state to IDLE to indicate that the extra SFT entry is available for use for another cogran.

FIG.11illustrates alternative operations1100for a case when a logical SFT entry is comprised of two physical entry's and the logical SFT entry's base entry has been selected to be victimized. The operations1100may be initiated at932in response to determining that the SFT is configured to consolidate a logical entry to a single entry when a base SFT entry is victimized. Specifically, these operations are for a case when a logical SFT entry is comprised of two physical entry's and the logical SFT entry's base entry has been selected to be victimized. An operation1104defines the victim SFT entry's base entry as “base entry 1” and an operation1106defines the victim SFT entry's extra entry as “base entry 2.”

An operation1108determines if the victim SFT entry's tracking_mode is set to VECTOR. If not, an operation1112determines whether a base SFT entry has enough space to hold all the valid AIDs that remain in the victim SFT entry (also referred to as the victim logical SFT entry). If a base SFT entry does not have enough space to hold all the valid AIDs that remain in the victim logical SFT entry, an operation1122sets the base entry 2's tracking_mode to IMPRECISE. An operation1124updates the base SFT entry 2 as needed to account for agents whose associated AIDs are currently held by the victim logical SFT entry. Subsequently, an operation1130sets the base entry 2's entry_state to SEARCHABLE and an operation1132sets the base entry 1's entry-state to IDLE. If the operation1112determines that the base SFT entry has enough space to hold the AIDs that remain in the victim logical SFT entry, an operation1140sets the base entry 2's tracking_mode to AID and an operation1142consolidates the AIDs from the victim logical SFT entry to base entry 2's tracking_info field and sets their associated VLD bits. Subsequently, the operation1130sets the base entry 2's entry_state to SEARCHABLE and the operation1132sets the base entry 1's entry-state to IDLE.

If the operation1108determines that the victim logical SFT entry's tracking_mode is set to VECTOR, an operation1110determines if only one vector bit is set in victim logical SFT entry. If more than one vector bits are set for the associated logical SFT entry, an operation1116determines whether the SFT is configured to revert its tracking_mode to AID if more than one vector bits remain set. If yes, an operation1134determines whether a single physical entry has enough space to hold AIDs for agents that remain in the vector. If yes, the control is transferred to operation1118. An operation1118sets the base entry 2's tracking_mode to AID, and an operation1120converts the vector bits from the victim logical SFT entry to their equivalent AIDs, copies those AIDs to base entry 2's tracking_info field and sets their associated VLD bits. However, if operation1134determines whether that a single physical entry does not have enough space to hold AIDs for agents that remain in the vector, an operation1136sets the base entry 2's tracking_mode to IMPRECISE and an operation1138updates the base entry 2 as needed to account for agents whose associated vector bits are currently set in the extra SFT entry. Subsequently, the operation1130sets the base entry 2's entry_state to SEARCHABLE and the operation1132sets the base entry 1's entry-state to IDLE.

If the operation1116determines that the SFT is not configured to revert its tracking_mode to AID if more than one vector bits remain set, in this case also the control transfers to operation1136that sets the base entry 2's tracking_mode to IMPRECISE.

If the operation1110determines that only one vector bit is set in the victim logical SFT entry, an operation1114determines if the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set. If the SFT is not configured to revert to AID when only one vector bit remains set, the control transfers to operation1136that sets the base entry 2's tracking_mode to IMPRECISE. However, if the operation1114determines that the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set, an operation1126sets the base entry 2's tracking_mode to AID and an operation1128converts the vector bit to its equivalent AID and records the AID in the tracking_info field of the base entry 2 together with its VLD bits.

FIG.12illustrates operations1200for a case when SFT needs to add a new agent to its existing tracking for a cogran, the logical SFT entry's tracking_mode=AID, and the implementation supports holding additional AIDs in an extra SFT entry. Specifically, the implementations disclosed herein allows the SFT to use an extra SFT entry to record the new agent's AID when it's needed. When the SFT is configured to add an AID to a logical SFT entry's extra physical entry, the SFT updates the logical SFT entry's tracking_mode to be AID_ME to indicate the presence of an extra entry and it records the extra entry's location.

An operation1204determines if the base SFT entry is able to, or it has space to, record an additional AID in its tracking_info field. If so, an operation1206adds the new agent's AID to the tracking_info field of the base SFT entry. If the base SFT entry is not able to record an additional AID to its tracking_info field, an operation1208determines if the SFT is configured to dynamically add and enable an extra SFT entry. If the SFT is not configured to dynamically add and enable an extra SFT entry, an operation1212sets the base SFT entry's tracking_mode to IMPRECISE, an operation1214updates the imprecise tracking for any currently tracked agents, and an operation1216adds a new agent to the imprecise tracking.

If the SFT is configured to dynamically add and enable an extra SFT entry, an operation1210determines whether SFT has any available entry to use. If so, an operation1218selects an available entry. If the SFT does not have any available entry to use, an operation1220selects a victim entry as if it were allocating a new entry. If the victim entry's entry_state is EXTRA, refer toFIG.10; else if the victim entry's tracking_mode is either VECTOR or AID_ME, refer toFIG.11; else send a “filter flush” snoop on behalf of the victim entry. Once the victim entry's entry_state is able to be set to IDLE, operation1222sets that entry's entry_state to EXTRA. Subsequently, an operation1224records the extra SFT entry's location, or way, in the base SFT entry. An operation1226determines if the SFT is configured to record AIDs in an extra SFT entry. If yes, an operation1228sets the base SFT entry's tracking_mode to AID_ME and an operation1230adds the new agent's AID to the extra SFT entry and sets the corresponding VLD bit for the AID. If the operation1226determines that the SFT is not configured to record AIDs in an extra SFT entry, an operation1232sets the base SFT entry's tracking_mode to VECTOR, an operation1234sets the tracking vector bit positions in the extra SFT entry corresponding to any currently tracked agents, and an operation1236sets the tracking vector bit position in the extra SFT entry for the new agent.

FIG.13illustrates operations1300for a case when SFT needs to add an agent to its existing tracking for a cogran and the logical SFT entry's tracking_mode is set to AID_ME. Specifically, the operations1300adds the new AID to the base SFT entry if the base SFT entry has space to accept the AID or adds the new AID to the extra SFT entry if the extra SFT entry has room to accept the AID. If the logical SFT entry does not have room to record the new AID in either the base SFT entry or the extra SFT entry, it is configured to switch its tracking_mode to VECTOR, in which case, the SFT updates the tracking_mode of the logical SFT entry to VECTOR and sets tracking_info bits as appropriate for all the AIDs that the logical SFT entry currently holds as well as for the new AID of the agent that it's adding to the logical SFT entry. If the SFT is not configured to switch from tracking_mode=AID_ME to tracking_mode=VECTOR, then the SFT switches the tracking_mode of the SFT entry to IMPRECISE and updates the tracking_info as needed for the AIDs that it currently holds as well as the new AID that it's adding to the logical SFT entry.

An operation1304determines if the base SFT entry is able to record an additional AID to its tracking_info field. If so, an operation1306adds the new agent's AID to the base SFT entry and as per operation1314the tracking_mode of the base SFT entry remains set to AID_ME. If the operation1304determines that the base SFT entry is not able to record an additional AID to its tracking_info field, an operation1308determines whether the extra SFT entry is able to record an additional AID to its tracking_info field. If so, an operation1310adds the new agent's AID to the extra SFT entry and as per operation1314the tracking_mode of the base SFT entry remains set to AID_ME.

If the operation1308determines that even the extra SFT entry is not able to record the additional AID, an operation1312determines if the SFT is configured to use a vector to track the agents that hold a copy of the SFT entry's cogran. If so, an operation1316sets the base SFT entry's tracking_mode to VECTOR, an operation1318sets the tracking vector bit positions in the extra SFT entry for any currently tracked agents, and an operation1320sets the tracking vector bit position in the extra SFT entry for the new agent. If the SFT is not configured to record the AID in a vector, an operation1322sets the tracking_mode of the base SFT entry to IMPRECISE, an operation1324updates to imprecise tracking for any currently tracked agents, and an operation1326adds the new agent to the imprecise tracking.

FIG.14illustrates operations1400for a case when SFT needs to add an agent to its existing tracking for a cogran and the logical SFT entry's tracking_mode is set to either VECTOR or IMPRECISE. An operation1404determines if the SFT entry's tracking_mode is VECTOR. If so, an operation1406sets the tracking vector bit position in the extra SFT entry for the new agent, while the tracking_mode remains set to VECTOR. If the SFT entry's tracking_mode is not VECTOR, the tracking_mode is imprecise and an operation1408updates the SFT as needed to add the new agent's AID, while the tracking_mode remains set to IMPRECISE.

FIG.15illustrates operations1500for a case when SFT needs to remove an agent from its tracking for a cogran and the logical SFT entry's tracking_mode is set to AID. Specifically, the operations1500remove the AID from tracking and if the logical SFT entry is no longer tracking any agents, the logical SFT entry may be de-allocated by setting the entry_state of the base SFT entry to IDLE. An operation1504determines if the AID corresponding to the agent to be removed is the only AID in the SFT entry. If so, an operation1506sets the base SFT entry's entry_state to IDLE, while the tracking_mode of the base SFT entry remains set to AID. If the AID to be removed is not the only AID in the SFT entry, an operation1508removes the AID from the base entry, while the tracking_mode of the base SFT entry remains set to AID.

FIG.16illustrates operations1600for a case when SFT needs to remove an agent from its existing tracking for a cogran and the logical SFT entry's tracking_mode is set to AID_ME. In this case, the SFT removes the AID corresponding to that agent from whichever SFT entry, either the base SFT entry or the extra SFT entry that is currently holding that agent's AID. If after the AID is removed, the number of remaining AIDs held by the logical SFT entry can fit into a single physical entry and the SFT is configured to consolidate AIDs to a single physical SFT entry, any AIDs held by the extra SFT entry are moved to the base SFT entry, the extra SFT entry's entry_state is set to IDLE, and the base SFT entry's tracking_mode is set to AID.

An operation1604determines if an AID is to be removed from an extra SFT entry. If so, an operation1606removes the AID from the extra SFT entry. If an AID is not to be removed from an extra SFT entry, an operation1608removes the AID from the base SFT entry. Subsequently, an operation1610determines if the base SFT entry has any space available to hold all the AIDs that remain in the extra SFT entry. If the base SFT entry does not have any space available to hold AIDs that remain in the extra SFT entry, the tracking_mode of the logical SFT entry remains set to AID_ME.

If the base SFT entry has any space available to hold all the AIDs that remain in the extra SFT entry, an operation1612further determines if the SFT is configured to revert to AID mode when possible. In response to determining that the SFT is configured to revert to AID mode, an operation1614moves all the AIDs from the extra SFT entry to the base SFT entry, an operation1616sets the extra SFT entry's entry_state to IDLE, and an operation1618sets the base SFT entry's tracking_mode to AID. If the SFT is not configured to revert to AID mode, the tracking_mode of the logical SFT entry remains set to AID_ME.

FIG.17illustrates operations1700for a case when SFT needs to remove an agent from its existing tracking for a cogran and the base SFT entry's tracking_mode is set to either VECTOR or IMPRECISE.

An operation1704determines if the base SFT entry's tracking_mode is set to VECTOR. If the base SFT entry's tracking_mode is not set to VECTOR, the tracking_mode of the base SFT entry is determined to be IMPRECISE and an operation1708updates the SFT as needed to remove the agent from its existing tracking of a cogran. If the base SFT entry's tracking_mode is set to VECTOR, an operation1706clears the tracking vector bit position corresponding to the agent that is to be removed. Subsequently, an operation1710determines if there are any vector bits in the tracking vector that are still set. If no more vector bits in the tracking vector are still set, an operation1714sets the base SFT entry's entry_state to IDLE and an operation1716sets the extra SFT entry's entry_state to IDLE and the entry is de-allocated.

If there are any vector bits in the tracking vector that are still set, an operation1712determines if there is only one vector bit remaining set in the tracking vector. If so, an operation1718further determines if the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set in the tracking vector. If the SFT is configured to revert its tracking_mode to AID when only one vector bit remains set in the tracking vector, an operation1722converts the vector bit to its equivalent AID and records the AID along with its VLD bit to the base SFT entry's tracking_info field. An operation1724sets the extra SFT entry's entry_state to IDLE and operation1726sets the base SFT entry's tracking_mode to AID.

If the operation1712determines that there are more than one vector bits remaining set in the tracking vector, an operation1720determines if the SFT is configured to revert its tracking_mode to AID_ME. If the SFT is configured to revert its tracking_mode to AID_ME, an operation1728further determines if the base SFT entry has enough space to hold a number of AIDs corresponding to the number of vector bits that remain set. If the base SFT entry has enough space to hold AIDs corresponding to the vector bits that remain set, an operation1742converts the vector bits to their equivalent AIDs, records the AIDs in the tracking_info field of the base SFT entry, and sets their corresponding VLD bits. An operation1744sets the extra SFT entry's entry_state to IDLE and an operation1746sets the base SFT entry's tracking_mode to AID. If the operation1728determines that the base SFT entry does not have enough space to hold AIDs corresponding to the vector bits that remain set, an operation1732determines if a combination of base SFT entry and the extra SFT entry has enough space to hold a number of AIDs corresponding to the number of vector bits that remain set. If the combination of base SFT entry and the extra SFT entry has enough space to hold AIDs corresponding to the vector bits that remain set, an operation1736converts the vector bits of the tracking vector to their equivalent AIDs, an operation1738records some of the AIDs in the base SFT entry and records the remaining AIDs in the extra SFT entry and sets their corresponding VLD bits, and an operation1740sets the base SFT entry's tracking_mode to AID_ME.

If the operation1720determines that the SFT is not configured to revert to AID_ME, an operation1730determines if the SFT is configured to revert its tracking_mode to AID mode if more than one vector bit remains set in the tracking vector. If so, an operation1734further determines if the base SFT entry has enough space to hold a number of AIDs corresponding to the number of vector bits that remain set. If so, the control transfers to operation1742, which converts the vector bits to their equivalent AIDs, records the AIDs in the tracking_info field of the base SFT entry, and sets their corresponding VLD bits.

The cache coherence system disclosed herein uses logical SFT entry structure to dynamically use an extra SFT entry to store a portion of tracking vector or to store additional AIDs and to revert to a single physical entry any time the number of agents being tracked can fit into a single SFT entry. As a result, as agents communicate to the cache coherence system that they are evicting a cogran from their private cache and as a result when the extra SFT entries are no longer needed, the SFT de-allocates the extra SFT entries. This results in more efficient use of the SFT entries as extra SFT entries are de-allocated when they are no longer needed to hold tracking information for the current cograns.

Furthermore, the implementation disclosed herein that allow for more than one extra SFT entries to be dynamically added and/or subtracted which enables reducing the size of a physical SFT entries to a smaller size, for example to track only a single agent. Implementations having higher number of smaller physical SFT entries allows the SFT to be better able to dynamically reconfigure itself to have a lot of precise tracking for the cograns that need it and to make that storage space available to track a higher number of cograns when there is less sharing of cograns is going on.

FIG.18illustrates an example system1800that may be useful in implementing the high latency query optimization system disclosed herein. The example hardware and operating environment ofFIG.18for implementing the described technology includes a computing device, such as a general-purpose computing device in the form of a computer20, a mobile telephone, a personal data assistant (PDA), a tablet, smart watch, gaming remote, or other type of computing device. In the implementation ofFIG.18, for example, the computer20includes a processing unit21, a system memory22, and a system bus23that operatively couples various system components, including the system memory22to the processing unit21. There may be only one or there may be more than one processing units21, such that the processor of a computer20comprises a single central-processing unit (CPU), or a plurality of processing units, commonly referred to as a parallel processing environment. The computer20may be a conventional computer, a distributed computer, or any other type of computer; the implementations are not so limited.

The system bus23may be any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, a switched fabric, point-to-point connections, and a local bus using any of a variety of bus architectures. The system memory22may also be referred to as simply the memory and includes read-only memory (ROM)24and random-access memory (RAM)25. A basic input/output system (BIOS)26, contains the basic routines that help to transfer information between elements within the computer20, such as during start-up, is stored in ROM24. The computer20further includes a hard disk drive27for reading from and writing to a hard disk, not shown, a magnetic disk drive28for reading from or writing to a removable magnetic disk29, and an optical disk drive30for reading from or writing to a removable optical disk31such as a CD ROM, DVD, or other optical media.

The computer20may be used to implement a high latency query optimization system disclosed herein. In one implementation, a frequency unwrapping module, including instructions to unwrap frequencies based at least in part on the sampled reflected modulations signals, may be stored in memory of the computer20, such as the read-only memory (ROM)24and random-access memory (RAM)25.

Furthermore, instructions stored on the memory of the computer20may be used to generate a transformation matrix using one or more operations disclosed inFIGS.5-17. Similarly, instructions stored on the memory of the computer20may also be used to implement one or more operations ofFIGS.5-17. The memory of the computer20may also one or more instructions to implement the high latency query optimization system disclosed herein.

The hard disk drive27, magnetic disk drive28, and optical disk drive30are connected to the system bus23by a hard disk drive interface32, a magnetic disk drive interface33, and an optical disk drive interface34, respectively. The drives and their associated tangible computer-readable media provide non-volatile storage of computer-readable instructions, data structures, program modules and other data for the computer20. It should be appreciated by those skilled in the art that any type of tangible computer-readable media may be used in the example operating environment.

A number of program modules may be stored on the hard disk, magnetic disk29, optical disk31, ROM24, or RAM25, including an operating system35, one or more application programs36, other program modules37, and program data38. A user may generate reminders on the personal computer20through input devices such as a keyboard40and pointing device42. Other input devices (not shown) may include a microphone (e.g., for voice input), a camera (e.g., for a natural user interface (NUI)), a joystick, a game pad, a satellite dish, a scanner, or the like. These and other input devices are often connected to the processing unit21through a serial port interface46that is coupled to the system bus23, but may be connected by other interfaces, such as a parallel port, game port, or a universal serial bus (USB). A monitor47or other type of display device is also connected to the system bus23via an interface, such as a video adapter48. In addition to the monitor, computers typically include other peripheral output devices (not shown), such as speakers and printers.

The computer20may operate in a networked environment using logical connections to one or more remote computers, such as remote computer49. These logical connections are achieved by a communication device coupled to or a part of the computer20; the implementations are not limited to a particular type of communications device. The remote computer49may be another computer, a server, a router, a network PC, a client, a peer device, or other common network node, and typically includes many or all of the elements described above relative to the computer20. The logical connections depicted inFIG.18include a local-area network (LAN)51and a wide-area network (WAN)52. Such networking environments are commonplace in office networks, enterprise-wide computer networks, intranets, and the Internet, which are all types of networks.

When used in a LAN-networking environment, the computer20is connected to the local area network51through a network interface or adapter53, which is one type of communications device. When used in a WAN-networking environment, the computer20typically includes a modem54, a network adapter, a type of communications device, or any other type of communications device for establishing communications over the wide area network52. The modem54, which may be internal or external, is connected to the system bus23via the serial port interface46. In a networked environment, program engines depicted relative to the personal computer20, or portions thereof, may be stored in the remote memory storage device. It is appreciated that the network connections shown are example and other means of communications devices for establishing a communications link between the computers may be used.

In an example implementation, software, or firmware instructions for the cache coherence system1810may be stored in system memory22and/or storage devices29or31and processed by the processing unit21. high latency query optimization system operations and data may be stored in system memory22and/or storage devices29or31as persistent data-stores.

In contrast to tangible computer-readable storage media, intangible computer-readable communication signals may embody computer readable instructions, data structures, program modules or other data resident in a modulated data signal, such as a carrier wave or other signal transport mechanism. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, intangible communication signals include wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media.

Some embodiments of high latency query optimization system may comprise an article of manufacture. An article of manufacture may comprise a tangible storage medium to store logic. Examples of a storage medium may include one or more types of computer-readable storage media capable of storing electronic data, including volatile memory or non-volatile memory, removable or non-removable memory, erasable or non-erasable memory, writeable or re-writeable memory, and so forth. Examples of the logic may include various software elements, such as software components, programs, applications, computer programs, application programs, system programs, machine programs, operating system software, middleware, firmware, software modules, routines, subroutines, functions, methods, procedures, software interfaces, application program interfaces (API), instruction sets, computing code, computer code, code segments, computer code segments, words, values, symbols, or any combination thereof. In one embodiment, for example, an article of manufacture may store executable computer program instructions that, when executed by a computer, cause the computer to perform methods and/or operations in accordance with the described embodiments. The executable computer program instructions may include any suitable type of code, such as source code, compiled code, interpreted code, executable code, static code, dynamic code, and the like. The executable computer program instructions may be implemented according to a predefined computer language, manner, or syntax, for instructing a computer to perform a certain function. The instructions may be implemented using any suitable high-level, low-level, object-oriented, visual, compiled and/or interpreted programming language.

The high latency query optimization system disclosed herein may include a variety of tangible computer-readable storage media and intangible computer-readable communication signals. Tangible computer-readable storage can be embodied by any available media that can be accessed by the high latency query optimization system disclosed herein and includes both volatile and nonvolatile storage media, removable and non-removable storage media. Tangible computer-readable storage media excludes intangible and transitory communications signals and includes volatile and nonvolatile, removable, and non-removable storage media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Tangible computer-readable storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CDROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other tangible medium which can be used to store the desired information, and which can be accessed by the high latency query optimization system disclosed herein. In contrast to tangible computer-readable storage media, intangible computer-readable communication signals may embody computer readable instructions, data structures, program modules or other data resident in a modulated data signal, such as a carrier wave or other signal transport mechanism. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, intangible communication signals include signals moving through wired media such as a wired network or direct-wired connection, and signals moving through wireless media such as acoustic, RF, infrared and other wireless media.

A system disclosed herein includes a 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 including selecting a physical SFT entry to be victimized, the physical SFT entry being one of a base SFT entry and an extra SFT entry of a logical SFT entry in a snoop filter (SFT) and consolidating the base SFT entry and the extra SFT entry into one physical entry.

A method disclosed herein includes selecting a physical SFT entry to be victimized, the physical SFT entry being one of a base SFT entry and an extra SFT entry of a logical SFT entry in a snoop filter (SFT) and consolidating the base SFT entry and the extra SFT entry into one physical entry.

An implementation of the system disclosed herein includes One or more physically manufactured computer-readable storage media, encoding computer-executable instructions for executing on a computer system a computer process, the computer process including selecting a physical SFT entry to be victimized, the physical SFT entry being one of a base SFT entry and an extra SFT entry of a logical SFT entry in a snoop filter (SFT) and consolidating the base SFT entry and the extra SFT entry into one physical entry.

The implementations described herein are implemented as logical steps in one or more computer systems. The logical operations may be implemented (1) as a sequence of processor-implemented steps executing in one or more computer systems and (2) as interconnected machine or circuit modules within one or more computer systems. The implementation is a matter of choice, dependent on the performance requirements of the computer system being utilized. Accordingly, the logical operations making up the implementations described herein are referred to variously as operations, steps, objects, or modules. Furthermore, it should be understood that logical operations may be performed in any order, unless explicitly claimed otherwise or a specific order is inherently necessitated by the claim language. The above specification, examples, and data, together with the attached appendices, provide a complete description of the structure and use of exemplary implementations.