Apparatuses, methods, and systems for dual spatial pattern prefetcher

Systems, methods, and apparatuses relating to a dual spatial pattern prefetcher are described. In one embodiment, a prefetch circuit is to prefetch a cache line into a cache from a memory by tracking page and cache line accesses to the cache for a single access signature, generate a spatial bit pattern, for the cache line accesses for each page of a plurality of pages, that is shifted to a first cache line access for each page, generate a single spatial bit pattern for the single access signature for each of the spatial bit patterns that have a same spatial bit pattern to form a plurality of single spatial bit patterns, perform a logical OR operation on the plurality of single spatial bit patterns to create a first modulated bit pattern for the single access signature, perform a logical AND operation on the plurality of single spatial bit patterns to create a second modulated bit pattern for the single access signature, receive a prefetch request for the single access signature, and perform a prefetch operation for the prefetch request using the first modulated bit pattern when a threshold is not exceeded and the second modulated bit pattern when the threshold is exceeded.

TECHNICAL FIELD

The disclosure relates generally to electronics, and, more specifically, an embodiment of the disclosure relates to a dual spatial pattern prefetch circuit.

BACKGROUND

A processor, or set of processors, executes instructions from an instruction set, e.g., the instruction set architecture (ISA). The instruction set is the part of the computer architecture related to programming, and generally includes the native data types, instructions, register architecture, addressing modes, memory architecture, interrupt and exception handling, and external input and output (I/O). It should be noted that the term instruction herein may refer to a macro-instruction, e.g., an instruction that is provided to the processor for execution, or to a micro-instruction, e.g., an instruction that results from a processor's decoder decoding macro-instructions.

DETAILED DESCRIPTION

A processor may use a prefetcher (e.g., prefetch circuit) to prefetch data, for example, to predict access addresses and bring the data for those addresses into a cache or caches (e.g., from memory, such as, but not limited to dynamic random access memory (DRAM)).

High latency accesses, e.g., from the DRAM main memory, often stall the in-order retire of instructions of a processor (e.g., core) and reduce look-ahead for instruction-level-parallelism (ILP) extraction. Furthermore, while memory bandwidths increase with newer generations of DRAM, memory latencies increase as well in certain embodiments. A move to narrower channels (e.g., in Low-Power Double Data Rate (LPDDR) DRAM) also increases overall latency from DRAM. The embodiments herein overcome these problems through a novel address prediction mechanism that is simultaneously optimized for both prefetch coverage and accuracy at low storage costs and scales up the performance provided when memory bandwidth headroom increases.

There are various solutions to the memory wall limit on performance. These include increasing processor depth which adds tolerance to higher latency (a complex and expensive approach with effectiveness reduced when increasing processor width as well), on-die caches with low access latencies (bound by capacity/area of cache) and prefetching or predicting addresses required by loads in a program (bound by ability to predict a large portion of load addresses early). A high-performance processor may employ a combination of some or all of these solutions.

Certain embodiments herein focus on prefetching to improve processor performance. The main metrics of prefetching may generally be as follows:Coverage: The fraction of high latency accesses by the program saved by the prefetcher (e.g., the higher the better),Timeliness: The fraction of high latency access hidden by the prefetch (e.g., the more the better),Accuracy: The fraction of correctly predicted addresses by the prefetcher (e.g., the higher the better), andStorage: The storage requirements of the prefetcher (e.g., the smaller the better).

In certain embodiments, prefetchers need to simultaneously optimize for coverage, timeliness and accuracy while maintaining low storage cost. Certain prefetching techniques statically bias their optimizations more towards either coverage or accuracy. Bit pattern prefetchers may have prohibitively high storage requirements (e.g., about 100 KB).

Furthermore, with the evolving DRAM landscape and technologies prefetching techniques need the ability to dynamically adapt to bandwidth, boosting predictions and coverage when headroom exists and throttling down to high accuracy when the bandwidth utilized is close to peak in certain embodiments. The embodiments herein allow for the scaling of their performance with higher DRAM bandwidth headroom.

In one embodiment, each of the specified requirements (low storage cost and dynamically optimizing for both coverage and accuracy while scaling with DRAM bandwidth) are squarely, effectively, and efficiently addressed by the embodiments of the dual spatial bit pattern prefetcher disclosed herein.

In one embodiment, a dual spatial (bit) pattern prefetcher is a lightweight spatial region prefetcher that uses bit operations like rotation, bitwise logical OR, and bitwise logical AND to dynamically improve both coverage and accuracy at low storage cost and scale its performance with DRAM bandwidth headroom.

In certain embodiments, a dual spatial pattern prefetcher (e.g., prefetch circuit) contributes the following innovations:in one embodiment, a dual spatial pattern prefetcher (e.g., prefetch circuit) employs two modulated bit patterns to simultaneously optimize on coverage, accuracy and storage. Bit patterns are stored by rotating them to their triggering offset in a page. This effectively captures all possible deltas from the triggering offset,in one embodiment, bit patterns are stored compressed at higher (e.g., 128B) granularity rather than a lower (e.g., 64B) granularity to reduce storage and allow for the usage of two patterns simultaneously,in one embodiment, a coverage biased pattern adds bits/predictions through the use of simple bitwise OR operations, e.g., with a second accuracy biased pattern retaining recurring bits through simple bitwise AND operations, andin one embodiment, a method of tracking bandwidth and measuring coverage and accuracy allows for the dynamic selection of the best prediction candidate at run-time.

An important distinction of a dual spatial pattern prefetcher as disclosed herein is the scaling in performance with increasing memory bandwidth, which it is believed that no prior prefetcher has achieved.

A dual spatial pattern prefetcher as disclosed herein extracts more patterns from an address access stream (thus increasing prefetch coverage) and dynamically adapts to available memory bandwidth headroom in embodiments as follows.

In certain embodiments, a spatial bit pattern representation anchored around a trigger access effectively captures all deltas (local and global) from the trigger and exposes patterns that are otherwise obfuscated by reordering in the machine.

In one embodiment, prefetching is a speculation mechanism to predict future addresses to be accessed by the program. These address access patterns can be represented in various forms (e.g., full cacheline address, offsets in 2 KB/4 KB region, or deltas between successive offsets) and choosing an address access pattern that has the best chance of exposing repeating patterns can help boosting prefetch coverage and performance. Patterns in address accesses that are apparent when taking a global or accumulative view of accesses might not be visible when a restricted and low-level view of deltas between consecutive accesses is employed.

FIG.1illustrates a block diagram100of a multiple core hardware processor102with a prefetch circuit120according to embodiments of the disclosure. Any processor may include a prefetch circuit, e.g., the processors discussed below.FIG.1illustrates an embodiment of multiple processor cores (core A and core B) and multiple levels of caches (L1, L2, and L3), e.g., in a cache coherency hierarchy. Although two cores are depicted, a single or more than two cores may be utilized. Although multiple levels of cache are depicted, a single, or any number of caches may be utilized. Cache(s) may be organized in any fashion, for example, as a physically or logically centralized or distributed cache.

In an embodiment, a processor, such as a processor or processors including the processor cores illustrated in the Figures, or any other processor, may include one or more caches.FIG.1illustrates an embodiment of a three level (e.g., levels 1 (L1), 1 (L2), and 3 (L3)) cache. A processor may include at least one core and at least one un-core. In one embodiment, multiple cores (core A and B) are of a single processor102. A core (e.g., core A and core B) may include the components of a processor to execute instructions. An un-core may include all logic not in a core. A processor core (e.g., core A) may include components such as a level 1 instruction cache (L1I)108and a level 1 data cache (L1D)110. A core (e.g., core A) may include components such as an address generation unit (AGU)112, translation lookaside buffer (TLB)114, and a level 1 cache (L2)116. A core may or may not share a cache with other cores, e.g., core A and core B may share the level 3 cache (L3)118but not the L2116or L1 (208.210). A core may include any combination of these components or none of these components. Processor102(e.g., core A and core B) may access (e.g., load and store) data in the system memory124, e.g., as indicated by the arrows. In one embodiment, the system memory124communicates with the core over a bus, e.g., at a slower access and/or cycle time than the core accessing cache (e.g. cache on the processor102). System memory124may include a multidimensional array126, e.g., loaded into the system memory124previously to the execution of a prefetch instruction.

An address generation unit (e.g., AGU112), for example, address computation unit (ACU), may refer to an execution unit inside a processor (e.g., a core) that calculates addresses used to access memory (e.g., system memory124), for example, to allow the core to access the system memory. In one embodiment, the AGU takes an address stream (e.g., equations) as an input and outputs the (e.g., virtual) addresses for that stream. An AGU (e.g., circuit) may perform arithmetic operations, such as addition, subtraction, modulo operations, or bit shifts, for example, utilizing an adder, multiplier, shifter, rotator, etc. thereof.

A translation lookaside buffer (e.g., TLB114) may convert a virtual address to a physical address (e.g., of the system memory). A TLB may include a data table to store (e.g., recently used) virtual-to-physical memory address translations, e.g., such that the translation does not have to be performed on each virtual address present to obtain the physical memory address. If the virtual address entry is not in the TLB, a processor may perform a page walk to determine the virtual-to-physical memory address translation.

Prefetch circuit120may be a separate functional circuit (e.g., unit), for example, not utilizing the functional units (e.g., execution unit, Arithmetic Logic Unit (ALU), AGU, TLB, etc.) of a core. Prefetch circuit may be utilized by a prefetch instruction. Prefetch circuit may include circuitry (e.g., hardware logic circuitry) to perform the prefetching discussed herein. Prefetch circuit may be part of a processor (e.g., separate from a core(s)). Prefetch circuit may communicate with the core(s) of the processor, e.g., via communication resources, such as, but not limited to, a ring network. Processor102may communicate with the system memory124and/or caches (e.g., L1, L2, or L3 inFIG.1) via a memory controller (e.g., as part of the processor) and/or an interconnect. Prefetch circuit120may output a system memory addresses of the multidimensional block of elements that is to-be-loaded (e.g., copied) into cache (e.g., L1, L2, or L3 inFIG.1) from multidimensional array126in system memory124. Prefetch circuit120may output the system memory addresses to the memory controller (e.g., memory unit1270inFIG.12B) of processor102.

FIG.2illustrates spatial bit patterns206, anchored to a trigger access (depicted as being circled), that capture local and global deltas according to embodiments of the disclosure.FIG.2illustrates an example of multiple sets of accesses (e.g., each with a unique access signature) within a spatial region and their representation in various formats. The first access to the region is termed as the “trigger” access and marked with a black circle. For example, with first entry “02” in access stream A of streams202indicating an access of cache line 2 in page A, second entry “06” in access stream A indicating an access of cache line 6 in page A, etc. InFIG.2, access sets for pages B through E have the same trigger offset in their spatial region and touch all the same offsets but in different temporal order. Such variations may be an artifact of reordering due to arbitration and scheduling in the cache/memory sub-systems. The longer the access sequence, the higher the probability of variations in certain embodiments. In certain embodiments, these accesses all have different representations when successive deltas204are used but can be represented by a single spatial bit pattern. For example, access set B and access set C with trigger offset 1 have two delta representations (+4,−1,+7,+1 and +4,+6,−7,+8, respectively) but a single bit pattern representation BP2(0100 1100 0001 1000). Crucially, when bit patterns are rotated (e.g., left) and anchored to the “trigger” offset, all sets in the example coalesce into a single representation208(1001 1000 0011 0000). Such anchored bit patterns capture all deltas relative to a trigger access, including local (successive) and global (accumulated) inFIG.2.

In certain embodiments, both coverage and accuracy can be simultaneously optimized by using bitwise logical OR and AND operations to modulate two spatial bit patterns, one biased towards coverage and the other towards the accuracy.

Multiple access streams in a program can have anchored bit patterns that are similar (e.g., have some intersection in bits set) but not exactly the same. A dual spatial pattern prefetcher (e.g., prefetch circuit) as disclosed herein uses a novel and intuitive approach of using two modulated bit patterns, e.g., one biased towards coverage and the other towards accuracy. Coverage increases by adding bits to the predicted pattern, which can be achieved using a bitwise logical OR operation on two bit patterns. For example, only retaining bits that occur in the pattern tracks accuracy, and this is achieved via a bitwise logical AND operation on the two patterns.

FIG.3illustrates modulated bit patterns302according to embodiments of the disclosure.FIG.3shows an example of how multiple different address streams that map to three rotated bit patterns314,316,318can be modulated into a coverage-biased pattern320(e.g., bit vector) and an accuracy-biased pattern322(e.g., bit vector). For example, with first delta sequence set306for a first set of accesses, second delta sequence set308for a second set of accesses, and third delta sequence set310for a third set of accesses. A set of accesses may be grouped based on the program counter (PC) (e.g., instruction pointer) that caused that respective access, for example, the PC for the instruction that caused a respective access. In one embodiment, each set of accesses has a same (e.g., bottom or top) proper subset of bits of the PC, e.g., a same eight bits.

InFIG.3, first rotated and anchored spatial bit pattern314is formed from first delta sequence set306for a first set of accesses, second rotated and anchored spatial bit pattern316is formed from second delta sequence set308for a second set of accesses, and third rotated and anchored spatial bit pattern318is formed from third delta sequence set310for a third set of accesses, e.g., formed as discussed in reference toFIG.2.

InFIG.3, modulated bit pattern for convergence320(CovP) is generated by performing a (bitwise) logical OR operation324on first rotated and anchored spatial bit pattern314, second rotated and anchored spatial bit pattern316, and third rotated and anchored spatial bit pattern318. InFIG.3, modulated bit pattern for accuracy322(AccP) is generated by performing a (bitwise) logical AND operation324on first rotated and anchored spatial bit pattern314, second rotated and anchored spatial bit pattern316, and third rotated and anchored spatial bit pattern318.

In certain embodiments, a dynamic modulation of these bit patterns enables a simultaneous optimization for both coverage and accuracy, despite these metrics being at odds with each other. The available memory bandwidth headroom, coupled with a quantified measure of accuracy and coverage, can be used to select between the two different bit pattern candidates (e.g., coverage biased or accuracy biased) dynamically at run-time.

In certain embodiments, {+1} and {−1} are two most frequently occurring offset deltas in programs. For example, in certain programs, those two deltas appear more than 50% of the time on average. Therefore, instead of storing bit patterns with each bit representing a (e.g., 64B) cacheline granularity, a dual spatial pattern prefetcher (e.g., prefetch circuit) as disclosed herein may store a compressed bit pattern where each bit represents two adjacent (e.g., 64B) cachelines (e.g., 128B granularity). This directly halves the pattern storage requirement. While this could theoretically have up-to a 50% inaccuracy in predictions, a dual spatial pattern prefetcher (e.g., prefetch circuit) as disclosed herein may have less than one misprediction every five cachelines prediction (e.g., a 20% inaccuracy).

In certain embodiments, multiple prefetch triggers on a physical page increases prefetch coverage. Certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) incorporates measures to track accuracy and throttle predictions, and thus can dynamically make predictions at both full physical page (e.g., 4 KB) and half physical page (e.g., 2 KB) granularities. Instead of using a larger (e.g., 64 b) bit pattern for coverage-biased (CovP) and accuracy-biased (AccP) patterns, certain embodiments herein split each of them into two smaller (e.g., 32 b) patterns.

In one embodiment, two (e.g., small 2-bit) counters, named as MeasureCovPand MeasureAccP, track coverage and accuracy of each (e.g., 32 b) bit pattern, e.g., having both of these counters for each bit pattern. The prediction selection may also be made per 2 KB (e.g., 32 b) segment of a 4 KB page.

A dual spatial pattern prefetcher (e.g., prefetch circuit) as disclosed herein may include the following structures:a multiple (e.g., 64) entry first-in, first-out (FIFO) structure called a page buffer (PB) that tracks the most recently accessed (e.g., 4 KB) pages in a cache (e.g., the L2 cache). In one embodiment, each PB entry is indexed by a (e.g., 4 KB) physical page and stores a (e.g., 64 b) bit pattern (uncompressed and raw access pattern) that accumulates the cache (e.g., L2) accesses seen by the program loads and stores to the page. It may also store an (e.g., 8 b) hashed program counter (PC) (e.g., instruction pointer) and two (e.g., 6 b) triggering offsets, one for each (e.g., 2 KB) segment of a physical page, to generate signature and anchor access bit pattern;a multiple (e.g., 256) entry signature pattern table (SPT) that stores the correlation between a signature and the follower bit pattern. In certain embodiments, SPT is a direct mapped structure, indexed by signature.
In one embodiment, each SPT entry stores the following elements:CovP (e.g., 32 b): coverage-biased compressed bit pattern,AccP (e.g., 32 b): accuracy-biased compressed bit pattern,2×MeasureCovP(e.g., 2×2 b): saturating counters each tracking coverage feedback for 2 KB region within a physical page,2×MeasureAccP(e.g., 2×2 b): saturating counters each tracking accuracy feedback for 2 KB region within a physical page, and2×ORcount(e.g., 2×2 b): saturating counters to keep track of number of OR operations on two segments of CovP; andPrefetch Buffer (e.g., 16 entry—that holds 2 (e.g., 64 b) bit vectors for generated and issued prefetches.

FIG.4Aillustrates a flow diagram401for a dual spatial pattern prefetcher according to embodiments of the disclosure.FIG.4Billustrates a dual spatial pattern prefetch circuit400according to embodiments of the disclosure. In certain embodiments, a prefetch circuit400as inFIG.4Bis included to prefetch data, for example, to predict access addresses and bring the data for those addresses into a cache or caches (e.g., from memory). In one embodiment, prefetch circuit400inFIG.4Bis an instance of the prefetch circuit120inFIG.1. In one embodiment, prefetch circuit400inFIG.4Bis an instance of the prefetch circuit1278inFIG.12B.

In the following example, every demand access403(e.g., an L2 cache demand access for a miss in an L1 cache) (e.g., program access404) looks up405page buffer402(PB) by the physical page number (step1). If a corresponding entry is found, dual spatial pattern prefetcher (e.g., prefetch circuit) sets409the appropriate bit position in access bit pattern in PB entry. As checked at411, the first access to each (e.g., 2 KB) segment in the (e.g., 4 KB) page is eligible to trigger prefetches (step2). If not a triggering access, the flow advances to done421. If a triggering access, the access signature (e.g., program counter (PC)) of this trigger access is stored in the PB entry and used to index into the SPT406which returns the CovP and AccP predictions and the measure of their goodness (MeasureCovPand MeasureAccPcounters) at413(step3). Selection flow (e.g., detailed inFIG.5) uses the system bandwidth410and measure to select (e.g., via multiplexer408) a prediction pattern412for prefetch (step4). In certain embodiments, this prediction pattern412is rotated by rotation circuit414to align to the trigger access offset to generate a rotated prediction pattern416before issuing prefetches. On eviction from the PB (step5) as checked at417, for each trigger (e.g., per 2 KB segment), the stored bit pattern is rotated to anchor to trigger offset, hashed into the SPT using the stored trigger access signature (e.g., PC), and the patterns and counters are updated at419. If no PB hit at407, a new PB entry is inserted at415into page buffer402.

In one embodiment, each entry (e.g., row in a table-row matrix) includes (i) a physical page ID number (e.g., used for identification of the page when looking up the page buffer), (ii) a spatial bit pattern (for example, a bit vector that represents the spatial access stream information, e.g., illustrating the cache lines that have been accessed as a 1 and a 0 otherwise) to the page (e.g., this is the pattern that will be rotated and used to update the SPT CovP and AccP patterns), (iii) the program counter (PC) of the triggering (e.g., first) access to the segment (e.g., used to index into the SPT), and/or (iv) the cache line offset of the triggering (e.g., first) access to a segment. Table 1 illustrates an example of two entries in a page buffer with example values and the trigger accesses shown as underlined.

An example of operations in reference to Tables 1 and 2 is to detect a new access to page 0x65, this new access is from an instruction having a PC of 0x7FFECCA, it is to the 4th (e.g., indexed from 0-N, where N is a positive integer greater than 1) cache line in the page and this is a triggering access (e.g., first access to this segment of the page) (e.g., as detected from accessing Table 1), next, a look-up is performed in the SPT (e.g., in Table 2) using the (e.g., lower proper subset of) bits of the PC 0x7FF3CCA (for example, if using the bottom 8 bits, lookup entry 0xCA of the SPT), the SPT lookup yields both CovP and AccP pattern. For example, picking one of them to use based on the system bandwidth. In certain embodiments, the picked CovP or AccP pattern is now rotated to the right by the cache line offset of the triggering access (e.g., which is 4 in the example from Table 1 as shown by the underlined 1). In certain embodiments ofFIG.4B, the prefetch circuit400outputs the rotated prediction pattern416.

In certain embodiments, the positions of ones in this rotated prediction pattern are the prefetches to be issued for the cache lines (e.g., with no prefetches issued for the cache lines corresponding to the zeros).

Next, the SPT may be updated.

In certain embodiments, each SPT update has three bit patterns of information: (1) actual program access (e.g., spatial access) bit pattern (e.g., that is coming from victim PB entry), (2) CovP stored inside SPT entry, and (3) AccP that are stored inside that SPT entry.

Certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) measures coverage and accuracy metric of CovP and AccP individually by two ratios of PopCount (counting number of bits set in a bit pattern) as shown in Table 3 below.

FIG.5illustrates circuitry to update a coverage-biased modulated bit pattern (CovP)502and an accuracy-biased modulated bit pattern (AccP)504according to embodiments of the disclosure. Certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) modulate the stored CovP and AccP bit patterns based on the calculated ratios the following way:CovP modulation: CovP adds bit by a bitwise logical OR operation506on the stored CovP pattern (CovP pattern510inFIG.5) with the actual program (PROGRAM pattern514inFIG.5) access pattern. However, since an unchecked number of OR operations may eventually set all bits in a pattern, certain embodiments limit it to a certain number of (e.g., three) OR operations (e.g., tracked with a 2 b saturating counter OrCount). OrCountis incremented every time the OR operation adds any bits to the predicted pattern. To quantify the goodness of CovP, certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) employ a (e.g., 2 b) saturating counter MeasureCovPthat is incremented whenever the CovP prediction accuracy is less than a threshold AccThror the program coverage from CovP is less than a threshold CovThr. This allows to reset CovP to the incoming program pattern when MeasureCovPis saturated and either the current bandwidth utilization is above a first threshold (e.g., 75%) (e.g., highest quartile) or the coverage is still less than a lower threshold (e.g., 50%) (e.g., despite up-to three OR operations). Certain embodiments use the 50% quartile threshold for both ACCThrand CovThr. Thus certain embodiments update two modulated spatial bit patterns to simultaneously optimize for coverage and accuracy.AccP modulation: in embodiment, the accuracy-biased bit pattern requires retaining recurring bits in the bit pattern, which can be achieved by a bit-wise logical AND operation508. Rather than recursive AND operations on AccP, on every update, AccP is replaced by a bit-wise AND operation of the incoming program access bit pattern (PROGRAM pattern514inFIG.5) and the CovP (the coverage-biased pattern) (CovP pattern510inFIG.5) in certain embodiments. This effectively retains only bits that have consecutive recurrence counts in the bit pattern. Similar to the MeasureCovP, certain embodiments herein use a (e.g., 2 b) saturating counter MeasureAccPto track the goodness of AccP. MeasureAccPis incremented if AndP prediction accuracy is less than a threshold (e.g., 50%) and decrements otherwise. MeasureAccPis used to completely throttle down predictions when bandwidth utilization is high and inaccuracy is high in one embodiment.

FIG.6illustrates a flow diagram to select between a coverage-biased modulated bit pattern (CovP) and an accuracy-biased modulated bit pattern (AccP) according to embodiments of the disclosure.FIG.6shows an example flow used between CovP and AccP for prediction. When at602bandwidth utilization is in the highest quartile (75%), certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) select AccP at604if MeasureAccPis not saturated. When bandwidth utilization is in the second highest quartile (between 50% and 75%) at606, certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) select AccP at608if MeasureCovPis saturated (e.g., meaning CovP is too inaccurate for a desired use here) and CovP otherwise. When bandwidth utilization is less than 50%, certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) simply use CovP. These numbers are examples and other thresholds may be utilized. To minimize any pollution effects in this mode, if MeasureCovPis saturated (meaning CovP is inaccurate), certain embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) fill these prefetches vulnerably (e.g., zero age) in the on-die (e.g., L2 and/or L3) caches.

FIG.7illustrates an example size table700of storage for a dual spatial pattern prefetcher according to embodiments of the disclosure. Table700includes an entry for an example page buffer702(PB) and an example signature prediction table704(SPT).

FIG.8is a flow diagram800according to embodiments of the disclosure. Depicted flow800includes accessing a cache that stores cache lines by a processor802; tracking page and cache line accesses to the cache for a single access signature804; generating a spatial bit pattern, for the cache line accesses for each page of a plurality of pages, that is shifted to a first cache line access for each page806; generating a single spatial bit pattern for the single access signature for each of the spatial bit patterns that have a same spatial bit pattern to form a plurality of single spatial bit patterns808; performing a logical OR operation on the plurality of single spatial bit patterns to create a first modulated bit pattern for the single access signature810; performing a logical AND operation on the plurality of single spatial bit patterns to create a second modulated bit pattern for the single access signature812; receiving a prefetch request for the single access signature814; and performing a prefetch operation, to prefetch a cache line into the cache from a memory, for the prefetch request using the first modulated bit pattern when a threshold is not exceeded and the second modulated bit pattern when the threshold is exceeded816.

Thus, the embodiments of a dual spatial pattern prefetcher (e.g., prefetch circuit) disclosed herein have the ability to scale performance with increasing memory bandwidth by boosting coverage and throttling down to high accuracy when the bandwidth utilized is close to peak to achieve a significant increase in processor performance over another prefetcher. For example, by providing a dual spatial pattern prefetcher (e.g., prefetch circuit) that scales in performance to make the most use of ever increasing memory bandwidth (e.g., and the inability of other prefetchers to do so), simultaneously optimizes coverage and accuracy modulating two bit patterns through bit-wise operations AND and OR, and uses a novel but efficiently implemented method of tracking bandwidth and measuring the coverage and accuracy of predicted patterns, allowing for dynamic selection of the best prediction candidate at run-time.

Exemplary architectures, systems, etc. that the above may be used in are detailed below.

At least some embodiments of the disclosed technologies can be described in view of the following examples:Example 1. An apparatus comprising:a processor core to access a memory and a cache that stores cache lines; anda prefetch circuit to prefetch a cache line into the cache from the memory, wherein the prefetch circuit is to:track page and cache line accesses to the cache for a single access signature,generate a spatial bit pattern, for the cache line accesses for each page of a plurality of pages, that is shifted to a first cache line access for each page,generate a single spatial bit pattern for the single access signature for each of the spatial bit patterns that have a same spatial bit pattern to form a plurality of single spatial bit patterns,perform a logical OR operation on the plurality of single spatial bit patterns to create a first modulated bit pattern for the single access signature,perform a logical AND operation on the plurality of single spatial bit patterns to create a second modulated bit pattern for the single access signature,receive a prefetch request for the single access signature, andperform a prefetch operation for the prefetch request using the first modulated bit pattern when a threshold is not exceeded and the second modulated bit pattern when the threshold is exceeded.2. The apparatus of example 1, wherein the single access signature is a single instruction pointer value.3. The apparatus of example 1, wherein the prefetch request comprises a miss of data in the cache (e.g., wherein the cache having the miss is a first level cache).4. The apparatus of example 1, wherein the threshold is a bandwidth utilization threshold of the memory.5. The apparatus of example 1, wherein the prefetch circuit is further to update the first modulated bit pattern with results of a logical OR operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.6. The apparatus of example 5, wherein the actual program access bit pattern is for a victim page buffer entry.7. The apparatus of example 5, wherein the prefetch circuit is further to update the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and the actual program access bit pattern for the single access signature.8. The apparatus of example 1, wherein the prefetch circuit is further to update the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.Example 9. A method comprising:accessing a cache that stores cache lines by a processor;tracking page and cache line accesses to the cache for a single access signature;generating a spatial bit pattern, for the cache line accesses for each page of a plurality of pages, that is shifted to a first cache line access for each page;generating a single spatial bit pattern for the single access signature for each of the spatial bit patterns that have a same spatial bit pattern to form a plurality of single spatial bit patterns;performing a logical OR operation on the plurality of single spatial bit patterns to create a first modulated bit pattern for the single access signature;performing a logical AND operation on the plurality of single spatial bit patterns to create a second modulated bit pattern for the single access signature;receiving a prefetch request for the single access signature; andperforming a prefetch operation, to prefetch a cache line into the cache from a memory, for the prefetch request using the first modulated bit pattern when a threshold is not exceeded and the second modulated bit pattern when the threshold is exceeded.10. The method of example 9, wherein the single access signature is a single instruction pointer value.11. The method of example 9, wherein the prefetch request comprises a miss of data in the cache.12. The method of example 9, further comprising setting the threshold as a bandwidth utilization threshold of the memory.13. The method of example 9, further comprising updating the first modulated bit pattern with results of a logical OR operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.14. The method of example 13, wherein the actual program access bit pattern is for a victim page buffer entry.15. The method of example 13, further comprising updating the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and the actual program access bit pattern for the single access signature.16. The method of example 9, further comprising updating the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.Example 17. A non-transitory machine readable medium that stores program code that when executed by a machine causes the machine to perform a method comprising:accessing a cache that stores cache lines by a processor;tracking page and cache line accesses to the cache for a single access signature;generating a spatial bit pattern, for the cache line accesses for each page of a plurality of pages, that is shifted to a first cache line access for each page;generating a single spatial bit pattern for the single access signature for each of the spatial bit patterns that have a same spatial bit pattern to form a plurality of single spatial bit patterns;performing a logical OR operation on the plurality of single spatial bit patterns to create a first modulated bit pattern for the single access signature;performing a logical AND operation on the plurality of single spatial bit patterns to create a second modulated bit pattern for the single access signature;receiving a prefetch request for the single access signature; andperforming a prefetch operation, to prefetch a cache line into the cache from a memory, for the prefetch request using the first modulated bit pattern when a threshold is not exceeded and the second modulated bit pattern when the threshold is exceeded.18. The non-transitory machine readable medium of example 17, wherein the single access signature is a single instruction pointer value.19. The non-transitory machine readable medium of example 17, wherein the prefetch request comprises a miss of data in the cache.20. The non-transitory machine readable medium of example 17, further comprising setting the threshold as a bandwidth utilization threshold of the memory.21. The non-transitory machine readable medium of example 17, further comprising updating the first modulated bit pattern with results of a logical OR operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.22. The non-transitory machine readable medium of example 21, wherein the actual program access bit pattern is for a victim page buffer entry.23. The non-transitory machine readable medium of example 21, further comprising updating the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and the actual program access bit pattern for the single access signature.24. The non-transitory machine readable medium of example 17, further comprising updating the second modulated bit pattern with results of a logical AND operation on the first modulated bit pattern and an actual program access bit pattern for the single access signature.

In yet another embodiment, an apparatus comprises a data storage device that stores code that when executed by a hardware processor causes the hardware processor to perform any method disclosed herein. An apparatus may be as described in the detailed description. A method may be as described in the detailed description.

Exemplary Instruction Formats

Generic Vector Friendly Instruction Format

FIGS.9A-9Bare block diagrams illustrating a generic vector friendly instruction format and instruction templates thereof according to embodiments of the disclosure.FIG.9Ais a block diagram illustrating a generic vector friendly instruction format and class A instruction templates thereof according to embodiments of the disclosure; whileFIG.9Bis a block diagram illustrating the generic vector friendly instruction format and class B instruction templates thereof according to embodiments of the disclosure. Specifically, a generic vector friendly instruction format900for which are defined class A and class B instruction templates, both of which include no memory access905instruction templates and memory access920instruction templates. The term generic in the context of the vector friendly instruction format refers to the instruction format not being tied to any specific instruction set.

The class A instruction templates inFIG.9Ainclude: 1) within the no memory access905instruction templates there is shown a no memory access, full round control type operation910instruction template and a no memory access, data transform type operation915instruction template; and 2) within the memory access920instruction templates there is shown a memory access, temporal925instruction template and a memory access, non-temporal930instruction template. The class B instruction templates inFIG.9Binclude: 1) within the no memory access905instruction templates there is shown a no memory access, write mask control, partial round control type operation912instruction template and a no memory access, write mask control, vsize type operation917instruction template; and 2) within the memory access920instruction templates there is shown a memory access, write mask control927instruction template.

The generic vector friendly instruction format900includes the following fields listed below in the order illustrated inFIGS.9A-9B.

Base operation field942—its content distinguishes different base operations.

Augmentation operation field950—its content distinguishes which one of a variety of different operations to be performed in addition to the base operation. This field is context specific. In one embodiment of the disclosure, this field is divided into a class field968, an alpha field952, and a beta field954. The augmentation operation field950allows common groups of operations to be performed in a single instruction rather than 2, 3, or 4 instructions.

Scale field960—its content allows for the scaling of the index field's content for memory address generation (e.g., for address generation that uses 2scale*index+base).

Displacement Field962A—its content is used as part of memory address generation (e.g., for address generation that uses 2scale*index+base+displacement).

Displacement Factor Field962B (note that the juxtaposition of displacement field962A directly over displacement factor field962B indicates one or the other is used)—its content is used as part of address generation; it specifies a displacement factor that is to be scaled by the size of a memory access (N)—where N is the number of bytes in the memory access (e.g., for address generation that uses 2scale*index+base+scaled displacement). Redundant low-order bits are ignored and hence, the displacement factor field's content is multiplied by the memory operands total size (N) in order to generate the final displacement to be used in calculating an effective address. The value of N is determined by the processor hardware at runtime based on the full opcode field974(described later herein) and the data manipulation field954C. The displacement field962A and the displacement factor field962B are optional in the sense that they are not used for the no memory access905instruction templates and/or different embodiments may implement only one or none of the two.

Class field968—its content distinguishes between different classes of instructions. With reference toFIGS.9A-B, the contents of this field select between class A and class B instructions. InFIGS.9A-B, rounded corner squares are used to indicate a specific value is present in a field (e.g., class A968A and class B968B for the class field968respectively inFIGS.9A-B).

Instruction Templates of Class A

In the case of the non-memory access905instruction templates of class A, the alpha field952is interpreted as an RS field952A, whose content distinguishes which one of the different augmentation operation types are to be performed (e.g., round952A.1and data transform952A.2are respectively specified for the no memory access, round type operation910and the no memory access, data transform type operation915instruction templates), while the beta field954distinguishes which of the operations of the specified type is to be performed. In the no memory access905instruction templates, the scale field960, the displacement field962A, and the displacement scale filed962B are not present.

In the no memory access full round control type operation910instruction template, the beta field954is interpreted as a round control field954A, whose content(s) provide static rounding. While in the described embodiments of the disclosure the round control field954A includes a suppress all floating point exceptions (SAE) field956and a round operation control field958, alternative embodiments may support may encode both these concepts into the same field or only have one or the other of these concepts/fields (e.g., may have only the round operation control field958).

SAE field956—its content distinguishes whether or not to disable the exception event reporting; when the SAE field's956content indicates suppression is enabled, a given instruction does not report any kind of floating-point exception flag and does not raise any floating point exception handler.

In the no memory access data transform type operation915instruction template, the beta field954is interpreted as a data transform field954B, whose content distinguishes which one of a number of data transforms is to be performed (e.g., no data transform, swizzle, broadcast).

In the case of a memory access920instruction template of class A, the alpha field952is interpreted as an eviction hint field952B, whose content distinguishes which one of the eviction hints is to be used (inFIG.9A, temporal952B.1and non-temporal952B.2are respectively specified for the memory access, temporal925instruction template and the memory access, non-temporal930instruction template), while the beta field954is interpreted as a data manipulation field954C, whose content distinguishes which one of a number of data manipulation operations (also known as primitives) is to be performed (e.g., no manipulation; broadcast; up conversion of a source; and down conversion of a destination). The memory access920instruction templates include the scale field960, and optionally the displacement field962A or the displacement scale field962B.

Memory Access Instruction Templates—Temporal

Memory Access Instruction Templates—Non-Temporal

Non-temporal data is data unlikely to be reused soon enough to benefit from caching in the 1st -level cache and should be given priority for eviction. This is, however, a hint, and different processors may implement it in different ways, including ignoring the hint entirely.

Instruction Templates of Class B

In the case of the instruction templates of class B, the alpha field952is interpreted as a write mask control (Z) field952C, whose content distinguishes whether the write masking controlled by the write mask field970should be a merging or a zeroing.

In the case of the non-memory access905instruction templates of class B, part of the beta field954is interpreted as an RL field957A, whose content distinguishes which one of the different augmentation operation types are to be performed (e.g., round957A.1and vector length (VSIZE)957A.2are respectively specified for the no memory access, write mask control, partial round control type operation912instruction template and the no memory access, write mask control, VSIZE type operation917instruction template), while the rest of the beta field954distinguishes which of the operations of the specified type is to be performed. In the no memory access905instruction templates, the scale field960, the displacement field962A, and the displacement scale filed962B are not present.

In the no memory access, write mask control, partial round control type operation910instruction template, the rest of the beta field954is interpreted as a round operation field959A and exception event reporting is disabled (a given instruction does not report any kind of floating-point exception flag and does not raise any floating point exception handler).

Round operation control field959A—just as round operation control field958, its content distinguishes which one of a group of rounding operations to perform (e.g., Round-up, Round-down, Round-towards-zero and Round-to-nearest). Thus, the round operation control field959A allows for the changing of the rounding mode on a per instruction basis. In one embodiment of the disclosure where a processor includes a control register for specifying rounding modes, the round operation control field's950content overrides that register value.

In the no memory access, write mask control, VSIZE type operation917instruction template, the rest of the beta field954is interpreted as a vector length field959B, whose content distinguishes which one of a number of data vector lengths is to be performed on (e.g., 128, 256, or 512 byte).

In the case of a memory access920instruction template of class B, part of the beta field954is interpreted as a broadcast field957B, whose content distinguishes whether or not the broadcast type data manipulation operation is to be performed, while the rest of the beta field954is interpreted the vector length field959B. The memory access920instruction templates include the scale field960, and optionally the displacement field962A or the displacement scale field962B.

With regard to the generic vector friendly instruction format900, a full opcode field974is shown including the format field940, the base operation field942, and the data element width field964. While one embodiment is shown where the full opcode field974includes all of these fields, the full opcode field974includes less than all of these fields in embodiments that do not support all of them. The full opcode field974provides the operation code (opcode).

The augmentation operation field950, the data element width field964, and the write mask field970allow these features to be specified on a per instruction basis in the generic vector friendly instruction format.

Exemplary Specific Vector Friendly Instruction Format

FIG.10is a block diagram illustrating an exemplary specific vector friendly instruction format according to embodiments of the disclosure.FIG.10shows a specific vector friendly instruction format1000that is specific in the sense that it specifies the location, size, interpretation, and order of the fields, as well as values for some of those fields. The specific vector friendly instruction format1000may be used to extend the x86 instruction set, and thus some of the fields are similar or the same as those used in the existing x86 instruction set and extension thereof (e.g., AVX). This format remains consistent with the prefix encoding field, real opcode byte field, MOD R/M field, SIB field, displacement field, and immediate fields of the existing x86 instruction set with extensions. The fields fromFIG.9into which the fields fromFIG.10map are illustrated.

It should be understood that, although embodiments of the disclosure are described with reference to the specific vector friendly instruction format1000in the context of the generic vector friendly instruction format900for illustrative purposes, the disclosure is not limited to the specific vector friendly instruction format1000except where claimed. For example, the generic vector friendly instruction format900contemplates a variety of possible sizes for the various fields, while the specific vector friendly instruction format1000is shown as having fields of specific sizes. By way of specific example, while the data element width field964is illustrated as a one bit field in the specific vector friendly instruction format1000, the disclosure is not so limited (that is, the generic vector friendly instruction format900contemplates other sizes of the data element width field964).

The generic vector friendly instruction format900includes the following fields listed below in the order illustrated inFIG.10A.

Format Field940(EVEX Byte0, bits [7:0])—the first byte (EVEX Byte0) is the format field940and it contains 0x62 (the unique value used for distinguishing the vector friendly instruction format in one embodiment of the disclosure).

The second-fourth bytes (EVEX Bytes1-3) include a number of bit fields providing specific capability.

Data element width field964(EVEX byte2, bit [7]—W)—is represented by the notation EVEX.W. EVEX.W is used to define the granularity (size) of the datatype (either 32-bit data elements or 64-bit data elements).

EVEX.U968Class field (EVEX byte2, bit [2]—U)—If EVEX.U=0, it indicates class A or EVEX.U0; if EVEX.U=1, it indicates class B or EVEX.U1.

Alpha field952(EVEX byte3, bit [7]—EH; also known as EVEX.EH, EVEX.rs, EVEX.RL, EVEX.write mask control, and EVEX.N; also illustrated with α)—as previously described, this field is context specific.

Real Opcode Field1030(Byte4) is also known as the opcode byte. Part of the opcode is specified in this field.

MOD R/M Field1040(Byte5) includes MOD field1042, Reg field1044, and R/M field1046. As previously described, the MOD field's1042content distinguishes between memory access and non-memory access operations. The role of Reg field1044can be summarized to two situations: encoding either the destination register operand or a source register operand, or be treated as an opcode extension and not used to encode any instruction operand. The role of R/M field1046may include the following: encoding the instruction operand that references a memory address, or encoding either the destination register operand or a source register operand.

Scale, Index, Base (SIB) Byte (Byte6)—As previously described, the scale field's950content is used for memory address generation. SIB.xxx1054and SIB.bbb1056—the contents of these fields have been previously referred to with regard to the register indexes Xxxx and Bbbb.

Displacement field962A (Bytes7-10)—when MOD field1042contains 10, bytes7-10are the displacement field962A, and it works the same as the legacy 32-bit displacement (disp32) and works at byte granularity.

Full Opcode Field

FIG.10Bis a block diagram illustrating the fields of the specific vector friendly instruction format1000that make up the full opcode field974according to one embodiment of the disclosure. Specifically, the full opcode field974includes the format field940, the base operation field942, and the data element width (W) field964. The base operation field942includes the prefix encoding field1025, the opcode map field1015, and the real opcode field1030.

Register Index Field

FIG.10Cis a block diagram illustrating the fields of the specific vector friendly instruction format1000that make up the register index field944according to one embodiment of the disclosure. Specifically, the register index field944includes the REX field1005, the REX′ field1010, the MODR/M.reg field1044, the MODR/M.r/m field1046, the VVVV field1020, xxx field1054, and the bbb field1056.

Augmentation Operation Field

FIG.10Dis a block diagram illustrating the fields of the specific vector friendly instruction format1000that make up the augmentation operation field950according to one embodiment of the disclosure. When the class (U) field968contains 0, it signifies EVEX.U0 (class A968A); when it contains 1, it signifies EVEX.U1 (class B968B). When U=0 and the MOD field1042contains 11 (signifying a no memory access operation), the alpha field952(EVEX byte3, bit [7]—EH) is interpreted as the rs field952A. When the rs field952A contains a 1 (round952A.1), the beta field954(EVEX byte3, bits [6:4]—SSS) is interpreted as the round control field954A. The round control field954A includes a one bit SAE field956and a two bit round operation field958. When the rs field952A contains a 0 (data transform952A.2), the beta field954(EVEX byte3, bits [6:4]—SSS) is interpreted as a three bit data transform field954B. When U=0 and the MOD field1042contains 00, 01, or 10 (signifying a memory access operation), the alpha field952(EVEX byte3, bit [7]—EH) is interpreted as the eviction hint (EH) field952B and the beta field954(EVEX byte3, bits [6:4]—SSS) is interpreted as a three bit data manipulation field954C.

When U=1, the alpha field952(EVEX byte3, bit [7]—EH) is interpreted as the write mask control (Z) field952C. When U=1 and the MOD field1042contains 11 (signifying a no memory access operation), part of the beta field954(EVEX byte3, bit [4]—S0) is interpreted as the RL field957A; when it contains a 1 (round957A.1) the rest of the beta field954(EVEX byte3, bit [6-5]—S2-1) is interpreted as the round operation field959A, while when the RL field957A contains a 0 (VSIZE957.A2) the rest of the beta field954(EVEX byte3, bit [6-5]—S2-1) is interpreted as the vector length field959B (EVEX byte3, bit [6-5]—L1-0). When U=1 and the MOD field1042contains 00, 01, or 10 (signifying a memory access operation), the beta field954(EVEX byte3, bits [6:4]—SSS) is interpreted as the vector length field959B (EVEX byte3, bit [6-5]—L1-0) and the broadcast field957B (EVEX byte3, bit [4]—B).

Exemplary Register Architecture

FIG.11is a block diagram of a register architecture1100according to one embodiment of the disclosure. In the embodiment illustrated, there are 32 vector registers1110that are 512 bits wide; these registers are referenced as zmm0 through zmm31. The lower order 256 bits of the lower 16 zmm registers are overlaid on registers ymm0-16. The lower order 128 bits of the lower 16 zmm registers (the lower order 128 bits of the ymm registers) are overlaid on registers xmm0-15. The specific vector friendly instruction format1000operates on these overlaid register file as illustrated in the below tables.

In other words, the vector length field959B selects between a maximum length and one or more other shorter lengths, where each such shorter length is half the length of the preceding length; and instructions templates without the vector length field959B operate on the maximum vector length. Further, in one embodiment, the class B instruction templates of the specific vector friendly instruction format1000operate on packed or scalar single/double-precision floating point data and packed or scalar integer data. Scalar operations are operations performed on the lowest order data element position in an zmm/ymm/xmm register; the higher order data element positions are either left the same as they were prior to the instruction or zeroed depending on the embodiment.

Write mask registers1115—in the embodiment illustrated, there are 8 write mask registers (k0 through k7), each 64 bits in size. In an alternate embodiment, the write mask registers1115are 16 bits in size. As previously described, in one embodiment of the disclosure, the vector mask register k0 cannot be used as a write mask; when the encoding that would normally indicate k0 is used for a write mask, it selects a hardwired write mask of 0xFFFF, effectively disabling write masking for that instruction.

Scalar floating point stack register file (x87 stack)1145, on which is aliased the MMX packed integer flat register file1150—in the embodiment illustrated, the x87 stack is an eight-element stack used to perform scalar floating-point operations on 32/64/80-bit floating point data using the x87 instruction set extension; while the MMX registers are used to perform operations on 64-bit packed integer data, as well as to hold operands for some operations performed between the MMX and XMM registers.

Alternative embodiments of the disclosure may use wider or narrower registers. Additionally, alternative embodiments of the disclosure may use more, less, or different register files and registers.

Exemplary Core Architectures

In-Order and Out-of-Order Core Block Diagram

InFIG.12A, a processor pipeline1200includes a fetch stage1202, a length decode stage1204, a decode stage1206, an allocation stage1208, a renaming stage1210, a scheduling (also known as a dispatch or issue) stage1212, a register read/memory read stage1214, an execute stage1216, a write back/memory write stage1218, an exception handling stage1222, and a commit stage1224.

FIG.12Bshows processor core1290including a front end unit1230coupled to an execution engine unit1250, and both are coupled to a memory unit1270. The core1290may be a reduced instruction set computing (RISC) core, a complex instruction set computing (CISC) core, a very long instruction word (VLIW) core, or a hybrid or alternative core type. As yet another option, the core1290may be a special-purpose core, such as, for example, a network or communication core, compression engine, coprocessor core, general purpose computing graphics processing unit (GPGPU) core, graphics core, or the like.

The front end unit1230includes a branch prediction unit1232coupled to an instruction cache unit1234, which is coupled to an instruction translation lookaside buffer (TLB)1236, which is coupled to an instruction fetch unit1238, which is coupled to a decode unit1240. The decode unit1240(or decoder or decoder unit) may decode instructions (e.g., macro-instructions), and generate as an output one or more micro-operations, micro-code entry points, micro-instructions, other instructions, or other control signals, which are decoded from, or which otherwise reflect, or are derived from, the original instructions. The decode unit1240may be implemented using various different mechanisms. Examples of suitable mechanisms include, but are not limited to, look-up tables, hardware implementations, programmable logic arrays (PLAs), microcode read only memories (ROMs), etc. In one embodiment, the core1290includes a microcode ROM or other medium that stores microcode for certain macro-instructions (e.g., in decode unit1240or otherwise within the front end unit1230). The decode unit1240is coupled to a rename/allocator unit1252in the execution engine unit1250.

The execution engine unit1250includes the rename/allocator unit1252coupled to a retirement unit1254and a set of one or more scheduler unit(s)1256. The scheduler unit(s)1256represents any number of different schedulers, including reservations stations, central instruction window, etc. The scheduler unit(s)1256is coupled to the physical register file(s) unit(s)1258. Each of the physical register file(s) units1258represents one or more physical register files, different ones of which store one or more different data types, such as scalar integer, scalar floating point, packed integer, packed floating point, vector integer, vector floating point, status (e.g., an instruction pointer that is the address of the next instruction to be executed), etc. In one embodiment, the physical register file(s) unit1258comprises a vector registers unit, a write mask registers unit, and a scalar registers unit. These register units may provide architectural vector registers, vector mask registers, and general purpose registers. The physical register file(s) unit(s)1258is overlapped by the retirement unit1254to illustrate various ways in which register renaming and out-of-order execution may be implemented (e.g., using a reorder buffer(s) and a retirement register file(s); using a future file(s), a history buffer(s), and a retirement register file(s); using a register maps and a pool of registers; etc.). The retirement unit1254and the physical register file(s) unit(s)1258are coupled to the execution cluster(s)1260. The execution cluster(s)1260includes a set of one or more execution units1262and a set of one or more memory access units1264. The execution units1262may perform various operations (e.g., shifts, addition, subtraction, multiplication) and on various types of data (e.g., scalar floating point, packed integer, packed floating point, vector integer, vector floating point). While some embodiments may include a number of execution units dedicated to specific functions or sets of functions, other embodiments may include only one execution unit or multiple execution units that all perform all functions. The scheduler unit(s)1256, physical register file(s) unit(s)1258, and execution cluster(s)1260are shown as being possibly plural because certain embodiments create separate pipelines for certain types of data/operations (e.g., a scalar integer pipeline, a scalar floating point/packed integer/packed floating point/vector integer/vector floating point pipeline, and/or a memory access pipeline that each have their own scheduler unit, physical register file(s) unit, and/or execution cluster—and in the case of a separate memory access pipeline, certain embodiments are implemented in which only the execution cluster of this pipeline has the memory access unit(s)1264). It should also be understood that where separate pipelines are used, one or more of these pipelines may be out-of-order issue/execution and the rest in-order.

The set of memory access units1264is coupled to the memory unit1270, which includes a data TLB unit1272coupled to a data cache unit1274coupled to a level 2 (L2) cache unit1276. In one exemplary embodiment, the memory access units1264may include a load unit, a store address unit, and a store data unit, each of which is coupled to the data TLB unit1272in the memory unit1270. The instruction cache unit1234is further coupled to a level 2 (L2) cache unit1276in the memory unit1270. The L2 cache unit1276is coupled to one or more other levels of cache and eventually to a main memory.

In certain embodiments, a prefetch circuit1278is included to prefetch data, for example, to predict access addresses and bring the data for those addresses into a cache or caches (e.g., from memory1280). In one embodiment, prefetch circuit1278is an instance of the prefetch circuit inFIG.3B.

By way of example, the exemplary register renaming, out-of-order issue/execution core architecture may implement the pipeline1200as follows: 1) the instruction fetch1238performs the fetch and length decoding stages1202and1204; 2) the decode unit1240performs the decode stage1206; 3) the rename/allocator unit1252performs the allocation stage1208and renaming stage1210; 4) the scheduler unit(s)1256performs the schedule stage1212; 5) the physical register file(s) unit(s)1258and the memory unit1270perform the register read/memory read stage1214; the execution cluster1260perform the execute stage1216; 6) the memory unit1270and the physical register file(s) unit(s)1258perform the write back/memory write stage1218; 7) various units may be involved in the exception handling stage1222; and 8) the retirement unit1254and the physical register file(s) unit(s)1258perform the commit stage1224.

Specific Exemplary In-Order Core Architecture

FIG.13Ais a block diagram of a single processor core, along with its connection to the on-die interconnect network1302and with its local subset of the Level 2 (L2) cache1304, according to embodiments of the disclosure. In one embodiment, an instruction decode unit1300supports the x86 instruction set with a packed data instruction set extension. An L1 cache1306allows low-latency accesses to cache memory into the scalar and vector units. While in one embodiment (to simplify the design), a scalar unit1308and a vector unit1310use separate register sets (respectively, scalar registers1312and vector registers1314) and data transferred between them is written to memory and then read back in from a level 1 (L1) cache1306, alternative embodiments of the disclosure may use a different approach (e.g., use a single register set or include a communication path that allow data to be transferred between the two register files without being written and read back).

FIG.13Bis an expanded view of part of the processor core inFIG.13Aaccording to embodiments of the disclosure.FIG.13Bincludes an L1 data cache1306A part of the L1 cache1304, as well as more detail regarding the vector unit1310and the vector registers1314. Specifically, the vector unit1310is a 16-wide vector processing unit (VPU) (see the 16-wide ALU1328), which executes one or more of integer, single-precision float, and double-precision float instructions. The VPU supports swizzling the register inputs with swizzle unit1320, numeric conversion with numeric convert units1322A-B, and replication with replication unit1324on the memory input. Write mask registers1326allow predicating resulting vector writes.

FIG.14is a block diagram of a processor1400that may have more than one core, may have an integrated memory controller, and may have integrated graphics according to embodiments of the disclosure. The solid lined boxes inFIG.14illustrate a processor1400with a single core1402A, a system agent1410, a set of one or more bus controller units1416, while the optional addition of the dashed lined boxes illustrates an alternative processor1400with multiple cores1402A-N, a set of one or more integrated memory controller unit(s)1414in the system agent unit1410, and special purpose logic1408.

The memory hierarchy includes one or more levels of cache within the cores, a set or one or more shared cache units1406, and external memory (not shown) coupled to the set of integrated memory controller units1414. The set of shared cache units1406may include one or more mid-level caches, such as level 2 (L2), level 3 (L3), level 4 (L4), or other levels of cache, a last level cache (LLC), and/or combinations thereof. While in one embodiment a ring based interconnect unit1412interconnects the integrated graphics logic1408, the set of shared cache units1406, and the system agent unit1410/integrated memory controller unit(s)1414, alternative embodiments may use any number of well-known techniques for interconnecting such units. In one embodiment, coherency is maintained between one or more cache units1406and cores1402-A-N.

In some embodiments, one or more of the cores1402A-N are capable of multithreading. The system agent1410includes those components coordinating and operating cores1402A-N. The system agent unit1410may include for example a power control unit (PCU) and a display unit. The PCU may be or include logic and components needed for regulating the power state of the cores1402A-N and the integrated graphics logic1408. The display unit is for driving one or more externally connected displays.

Exemplary Computer Architectures

Referring now toFIG.15, shown is a block diagram of a system1500in accordance with one embodiment of the present disclosure. The system1500may include one or more processors1510,1515, which are coupled to a controller hub1520. In one embodiment the controller hub1520includes a graphics memory controller hub (GMCH)1590and an Input/Output Hub (IOH)1550(which may be on separate chips); the GMCH1590includes memory and graphics controllers to which are coupled memory1540and a coprocessor1545; the IOH1550is couples input/output (I/O) devices1560to the GMCH1590. Alternatively, one or both of the memory and graphics controllers are integrated within the processor (as described herein), the memory1540and the coprocessor1545are coupled directly to the processor1510, and the controller hub1520in a single chip with the IOH1550. Memory1540may include prefetcher code1540A, for example, to store code that when executed causes a processor to perform any method of this disclosure.

The optional nature of additional processors1515is denoted inFIG.15with broken lines. Each processor1510,1515may include one or more of the processing cores described herein and may be some version of the processor1400.

The memory1540may be, for example, dynamic random access memory (DRAM), phase change memory (PCM), or a combination of the two. For at least one embodiment, the controller hub1520communicates with the processor(s)1510,1515via a multi-drop bus, such as a frontside bus (FSB), point-to-point interface such as Quickpath Interconnect (QPI), or similar connection1595.

In one embodiment, the coprocessor1545is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, compression engine, graphics processor, GPGPU, embedded processor, or the like. In one embodiment, controller hub1520may include an integrated graphics accelerator.

There can be a variety of differences between the physical resources1510,1515in terms of a spectrum of metrics of merit including architectural, microarchitectural, thermal, power consumption characteristics, and the like.

In one embodiment, the processor1510executes instructions that control data processing operations of a general type. Embedded within the instructions may be coprocessor instructions. The processor1510recognizes these coprocessor instructions as being of a type that should be executed by the attached coprocessor1545. Accordingly, the processor1510issues these coprocessor instructions (or control signals representing coprocessor instructions) on a coprocessor bus or other interconnect, to coprocessor1545. Coprocessor(s)1545accept and execute the received coprocessor instructions.

Referring now toFIG.16, shown is a block diagram of a first more specific exemplary system1600in accordance with an embodiment of the present disclosure. As shown inFIG.16, multiprocessor system1600is a point-to-point interconnect system, and includes a first processor1670and a second processor1680coupled via a point-to-point interconnect1650. Each of processors1670and1680may be some version of the processor1400. In one embodiment of the disclosure, processors1670and1680are respectively processors1510and1515, while coprocessor1638is coprocessor1545. In another embodiment, processors1670and1680are respectively processor1510coprocessor1545.

Processors1670and1680are shown including integrated memory controller (IMC) units1672and1682, respectively. Processor1670also includes as part of its bus controller units point-to-point (P-P) interfaces1676and1678; similarly, second processor1680includes P-P interfaces1686and1688. Processors1670,1680may exchange information via a point-to-point (P-P) interface1650using P-P interface circuits1678,1688. As shown inFIG.16, IMCs1672and1682couple the processors to respective memories, namely a memory1632and a memory1634, which may be portions of main memory locally attached to the respective processors.

Processors1670,1680may each exchange information with a chipset1690via individual P-P interfaces1652,1654using point to point interface circuits1676,1694,1686,1698. Chipset1690may optionally exchange information with the coprocessor1638via a high-performance interface1639. In one embodiment, the coprocessor1638is a special-purpose processor, such as, for example, a high-throughput MIC processor, a network or communication processor, compression engine, graphics processor, GPGPU, embedded processor, or the like.

Chipset1690may be coupled to a first bus1616via an interface1696. In one embodiment, first bus1616may be a Peripheral Component Interconnect (PCI) bus, or a bus such as a PCI Express bus or another third generation I/O interconnect bus, although the scope of the present disclosure is not so limited.

As shown inFIG.16, various I/O devices1614may be coupled to first bus1616, along with a bus bridge1618which couples first bus1616to a second bus1620. In one embodiment, one or more additional processor(s)1615, such as coprocessors, high-throughput MIC processors, GPGPU's, accelerators (such as, e.g., graphics accelerators or digital signal processing (DSP) units), field programmable gate arrays, or any other processor, are coupled to first bus1616. In one embodiment, second bus1620may be a low pin count (LPC) bus. Various devices may be coupled to a second bus1620including, for example, a keyboard and/or mouse1622, communication devices1627and a storage unit1628such as a disk drive or other mass storage device which may include instructions/code and data1630, in one embodiment. Further, an audio I/O1624may be coupled to the second bus1620. Note that other architectures are possible. For example, instead of the point-to-point architecture ofFIG.16, a system may implement a multi-drop bus or other such architecture.

Referring now toFIG.17, shown is a block diagram of a second more specific exemplary system1700in accordance with an embodiment of the present disclosure. Like elements inFIGS.16and17bear like reference numerals, and certain aspects ofFIG.16have been omitted fromFIG.17in order to avoid obscuring other aspects ofFIG.17.

FIG.17illustrates that the processors1670,1680may include integrated memory and I/O control logic (“CL”)1672and1682, respectively. Thus, the CL1672,1682include integrated memory controller units and include I/O control logic.FIG.17illustrates that not only are the memories1632,1634coupled to the CL1672,1682, but also that I/O devices1714are also coupled to the control logic1672,1682. Legacy I/O devices1715are coupled to the chipset1690.

Referring now toFIG.18, shown is a block diagram of a SoC1800in accordance with an embodiment of the present disclosure. Similar elements inFIG.14bear like reference numerals. Also, dashed lined boxes are optional features on more advanced SoCs. InFIG.18, an interconnect unit(s)1802is coupled to: an application processor1810which includes a set of one or more cores202A-N and shared cache unit(s)1406; a system agent unit1410; a bus controller unit(s)1416; an integrated memory controller unit(s)1414; a set or one or more coprocessors1820which may include integrated graphics logic, an image processor, an audio processor, and a video processor; an static random access memory (SRAM) unit1830; a direct memory access (DMA) unit1832; and a display unit1840for coupling to one or more external displays. In one embodiment, the coprocessor(s)1820include a special-purpose processor, such as, for example, a network or communication processor, compression engine, GPGPU, a high-throughput MIC processor, embedded processor, or the like.

FIG.19is a block diagram contrasting the use of a software instruction converter to convert binary instructions in a source instruction set to binary instructions in a target instruction set according to embodiments of the disclosure. In the illustrated embodiment, the instruction converter is a software instruction converter, although alternatively the instruction converter may be implemented in software, firmware, hardware, or various combinations thereof.FIG.19shows a program in a high level language1902may be compiled using an x86 compiler1904to generate x86 binary code1906that may be natively executed by a processor with at least one x86 instruction set core1916. The processor with at least one x86 instruction set core1916represents any processor that can perform substantially the same functions as an Intel® processor with at least one x86 instruction set core by compatibly executing or otherwise processing (1) a substantial portion of the instruction set of the Intel® x86 instruction set core or (2) object code versions of applications or other software targeted to run on an Intel® processor with at least one x86 instruction set core, in order to achieve substantially the same result as an Intel® processor with at least one x86 instruction set core. The x86 compiler1904represents a compiler that is operable to generate x86 binary code1906(e.g., object code) that can, with or without additional linkage processing, be executed on the processor with at least one x86 instruction set core1916. Similarly,FIG.19shows the program in the high level language1902may be compiled using an alternative instruction set compiler1908to generate alternative instruction set binary code1910that may be natively executed by a processor without at least one x86 instruction set core1914(e.g., a processor with cores that execute the MIPS instruction set of MIPS Technologies of Sunnyvale, CA and/or that execute the ARM instruction set of ARM Holdings of Sunnyvale, CA). The instruction converter1912is used to convert the x86 binary code1906into code that may be natively executed by the processor without an x86 instruction set core1914. This converted code is not likely to be the same as the alternative instruction set binary code1910because an instruction converter capable of this is difficult to make; however, the converted code will accomplish the general operation and be made up of instructions from the alternative instruction set. Thus, the instruction converter1912represents software, firmware, hardware, or a combination thereof that, through emulation, simulation or any other process, allows a processor or other electronic device that does not have an x86 instruction set processor or core to execute the x86 binary code1906.