Efficient support of sparse data structure access

Method and apparatus to efficiently organize data in caches by storing/accessing data of varying sizes in cache lines. A value may be assigned to a field indicating the size of usable data stored in a cache line. If the field indicating the size of the usable data in the cache line indicates a size less than the maximum storage size, a value may be assigned to a field in the cache line indicating which subset of the data in the field to store data is usable data. A cache request may determine whether the size of the usable data in a cache line is equal to the maximum data storage size. If the size of the usable data in the cache line is equal to the maximum data storage size the entire stored data in the cache line may be returned.

FIELD OF THE INVENTION

The present disclosure pertains to the field of processors and, in particular, to optimizing cache management techniques.

DESCRIPTION OF RELATED ART

Advances in semi-conductor processing and logic design have permitted an increase in the amount of logic that may be present on integrated circuit devices. As a result, computer system configurations have evolved from a single or multiple integrated circuits in a system to multiple cores, multiple hardware threads, and multiple logical processors present on individual integrated circuits. A processor or integrated circuit typically comprises a single physical processor die, where the processor die may include any number of cores, hardware threads, or logical processors. The ever increasing number of processing elements—cores, hardware threads, and logical processors--on integrated circuits enables more tasks to be accomplished in parallel. However, the execution of more threads and tasks put an increased premium on shared resources, such as memory, and the management thereof.

Typically, cache memory includes a memory between a shared system memory and execution units of a processor to hold information in a closer proximity to the execution units. In addition, cache is typically smaller in size than a main system memory, which allows for the cache to be constructed from expensive, faster memory, such as Static Random Access Memory (SRAM). Both the proximity to the execution units and the speed allow for caches to provide faster access to data and instructions. Caches are often identified based on their proximity from execution units of a processor. For example, a first-level (L1) cache may be close to execution units residing on the same physical processor. Due to the proximity and placement, first level cache is often the smallest and quickest cache. A computer system may also hold higher-level or further out caches, such as a second level (L2) cache, which may also reside on the processor but be placed between the first level cache and main memory. And a third level (L3) cache may be placed on the processor or elsewhere in the computer system, such as at a controller hub, between the second level cache and main memory.

Caches are usually organized into cache lines with each line containing some number of bytes, and the size of each cache line in a cache is consistent. Similarly, the size of data held by each cache line in a cache is also consistent. The larger the size of the data in a cache line the more energy is required to store, access, and modify the data. Based on the organization of a cache, the amount of energy required may vary. Thus, there is a need for energy efficient ways to organize data within caches.

DETAILED DESCRIPTION

In the following description, numerous specific details are set forth such as examples of specific hardware structures for determining cache lines, reading/writing to cache lines, and determining target caches, as well as placement of such hardware structures, such as at memory ports or at independent cache slices; specific processor units/logic, specific examples of processing elements, etc. in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that these specific details need not be employed to practice the present invention. In other instances, well known components or methods, such as specific counter circuits, alternative multi-core and multi-threaded processor architectures, specific un-core logic, specific memory controller logic, specific cache implementations, specific cache coherency protocols, and specific operational details of microprocessors, have not been described in detail in order to avoid unnecessarily obscuring the present invention.

Embodiments may be discussed herein to efficiently organize data in caches. In particular, embodiments of the present invention pertain to a feature for storing/accessing data of varying sizes in cache lines. In an embodiment, data may be stored in a field to store data. The field to store data may be part of a cache line in a cache, and may be confined to a maximum size. In an embodiment, a value may be assigned to a field indicating the size of usable data stored in a cache line. In an embodiment, if the field indicating the size of the usable data in the cache line indicates a size less than the maximum storage size, a value may be assigned to a field in the cache line indicating which subset of the data in the field to store data is usable data.

In an embodiment, the data in a cache line, or the value assigned to the field indicating the size of data stored in a cache line, or the value assigned to the field indicating which subset of the data in the field to store data is usable data may be read. In an embodiment, a cache request may determine whether the size of the usable data in a cache line is equal to the maximum data storage size. If the size of the usable data in the cache line is equal to the maximum data storage size the entire stored data in the cache line may be returned. In an embodiment, if the size of the usable data in a cache line is less than a maximum data storage size, the data in the cache line may be merged with associated data in memory, and the merged data may be stored in the cache line. The merged data's size may be equal to the maximum data storage size.

In an embodiment, a cache request may determine whether a usable data in a cache line is a particular subset of data. If the usable data in the cache line is not a particular subset of data, the data in the cache line may be merged with associated data in memory, and the merged data may be stored in the cache line. The merged data's size may be equal to the maximum data storage size.

In an embodiment, the maximum data storage size of a cache line may be 64 bytes. In an embodiment, the size of stored usable data in a cache line may be 4 bytes, 8 bytes, or 64 bytes.

Referring toFIG. 1, an embodiment of a processor including multiple cores is illustrated. Processor100, in one embodiment, includes one or more caches. Processor100includes any processor, such as a micro-processor, an embedded processor, a digital signal processor (DSP), a network processor, or other device to execute code. Processor100, as illustrated, includes a plurality of processing elements.

In one embodiment, a processing element refers to a thread unit, a thread slot, a process unit, a context, a logical processor, a hardware thread, a core, and/or any other element, which is capable of holding a state for a processor, such as an execution state or architectural state. In other words, a processing element, in one embodiment, refers to any hardware capable of being independently associated with code, such as a software thread, operating system, application, or other code. A physical processor typically refers to an integrated circuit, which potentially includes any number of other processing elements, such as cores or hardware threads.

Physical processor100, as illustrated inFIG. 1, includes two cores, core101and102. Here, core hopping may be utilized to alleviate thermal conditions on one part of a processor. However, hopping from core101to102may potentially create the same thermal conditions on core102that existed on core101, while incurring the cost of a core hop. Therefore, in one embodiment, processor100includes any number of cores that may utilize core hopping. Furthermore, power management hardware included in processor100may be capable of placing individual units and/or cores into low power states to save power. Here, in one embodiment, processor100provides hardware to assist in low power state selection for these individual units and/or cores.

Although processor100may include asymmetric cores, i.e. cores with different configurations, functional units, and/or logic, symmetric cores are illustrated. As a result, core102, which is illustrated as identical to core101, will not be discussed in detail to avoid repetitive discussion. In addition, core101includes two hardware threads101aand101b, while core102includes two hardware threads102aand102b. Therefore, software entities, such as an operating system, potentially view processor100as four separate processors, i.e. four logical processors or processing elements capable of executing four software threads concurrently.

Here, a first thread is associated with architecture state registers101a, a second thread is associated with architecture state registers101b, a third thread is associated with architecture state registers102a, and a fourth thread is associated with architecture state registers102b. As illustrated, architecture state registers101aare replicated in architecture state registers101b, so individual architecture states/contexts are capable of being stored for logical processor101aand logical processor101b. Other smaller resources, such as instruction pointers and rename allocater logic130may also be replicated for threads101aand101b. Some resources, such as re-order buffers in reorder/retirement unit135, ILTB120, load/store buffers, and queues may be shared through partitioning. Other resources, such as general purpose internal registers, page-table base register, low level data-cache and data-TLB115, execution unit(s)140, and portions of out-of-order unit135are potentially fully shared.

Processor100often includes other resources, which may be fully shared, shared through partitioning, or dedicated by/to processing elements. InFIG. 1, an embodiment of a purely exemplary processor with illustrative logical units/resources of a processor is illustrated. Note that a processor may include, or omit, any of these functional units, as well as include any other known functional units, logic, or firmware not depicted. As illustrated, processor100includes a branch target buffer120to predict branches to be executed/taken and an instruction-translation buffer (I-TLB)120to store address translation entries for instructions.

Processor100further includes decode module125is coupled to fetch unit120to decode fetched elements. In one embodiment, processor100is associated with an Instruction Set Architecture (ISA), which defines/specifies instructions executable on processor100. Here, often machine code instructions recognized by the ISA include a portion of the instruction referred to as an opcode, which references/specifies an instruction or operation to be performed.

In one example, allocator and renamer block130includes an allocator to reserve resources, such as register files to store instruction processing results. However, threads101aand101bare potentially capable of out-of-order execution, where allocator and renamer block130also reserves other resources, such as reorder buffers to track instruction results. Unit130may also include a register renamer to rename program/instruction reference registers to other registers internal to processor100. Reorder/retirement unit135includes components, such as the reorder buffers mentioned above, load buffers, and store buffers, to support out-of-order execution and later in-order retirement of instructions executed out-of-order.

As depicted, cores101and102share access to higher-level or further-out cache110, which is to cache recently fetched elements. Note that higher-level or furtherout refers to cache levels increasing or getting further way from the execution unit(s). In one embodiment, higher-level cache110is a last-level data cache—last cache in the memory hierarchy on processor100—such as a second or third level data cache. However, higher level cache110is not so limited, as it may be associated with or include an instruction cache. A trace cache—a type of instruction cache—instead may be coupled after decoder125to store recently decoded traces.

Note, in the depicted configuration that processor100also includes bus interface module105to communicate with devices external to processor100, such as system memory175, a chipset, a Northbridge, or other integrated circuit. Memory175may be dedicated to processor100or shared with other devices in a system. Common examples of types of memory175include dynamic random access memory (DRAM), static RAM (SRAM), non-volatile memory (NV memory), and other known storage devices.

FIG. 1illustrates an abstracted, logical view of an exemplary processor with a representation of different modules, units, and/or logic. However, note that a processor utilizing the methods and apparatus' described herein need not include the illustrated units. And, the processor may omit some or all of the units shown. To illustrate the potential for a different configuration, the discussion now turns toFIG. 2, which depicts an embodiment of processor200including an on-processor memory interface module—an un-core module—with a ring configuration to interconnect multiple cores. Processor200is illustrated including a physically distributed cache; a ring interconnect; as well as core, cache, and memory controller components. However, this depiction is purely illustrative, as a processor implementing the described methods and apparatus may include any processing elements, style or level of cache, and/or memory, front-side-bus or other interface to communicate with external devices.

In one embodiment, caching agents221-224are each to manage a slice of a physically distributed cache. As an example, each cache component, such as component221, is to manage a slice of a cache for a collocated core—a core the cache agent is associated with for purpose of managing the distributed slice of the cache. As depicted, cache agents221-224are referred to as Cache Slice Interface Logic (CSIL)s; they may also be referred to as cache components, agents, or other known logic, units, or modules for interfacing with a cache or slice thereof. Note that the cache may be any level of cache; yet, for this exemplary embodiment, discussion focuses on a last-level cache (LLC) shared by cores201-204.

Much like cache agents handle traffic on ring interconnect250and interface with cache slices, core agents/components211-214are to handle traffic and interface with cores201-204, respectively. As depicted, core agents221-224are referred to as Processor Core Interface Logic (PCIL)s; they may also be referred to as core components, agents, or other known logic, units, or modules for interfacing with a processing element Additionally, ring250is shown as including Memory Controller Interface Logic (MCIL)230and Graphics Hub (GFX)240to interface with other modules, such as memory controller (IMC)231and a graphics processor (not illustrated). However, ring250may include or omit any of the aforementioned modules, as well as include other known processor modules that are not illustrated. Additionally, similar modules may be connected through other known interconnects, such as a point-to-point interconnect or a multi-drop interconnect.

It's important to note that the methods and apparatus' described herein may be implemented in any cache at any cache level, or at any processor or processor level. Furthermore, caches may be organized in any fashion, such as being a physically or logically, centralized or distributed cache. As a specific example, the cache may include a physical centralized cache with a similarly centralized tag directory, such as higher level cache110. Alternatively, the tag directories may be either physically and/or logically distributed in a physically distributed cache, such as the cache organization illustrated inFIG. 2.

A cache stores quantities of data called cache lines or cache blocks. The term cache line and cache block may be used interchangeably.FIG. 3Aillustrates the basic structure of a cache line. A cache line301may be composed of two main parts: metadata (or tag)305and data315. The tag entry305identifies the contents of the corresponding data entry315. Status information310may include a validity bit indicating whether the data315in the cache line301is valid. The cache line301, and its underlying parts or fields such as the data field315may be of any size. Typically, the size of cache lines are consistent in a cache structure, and the data size may be fixed at 64 bytes. When a request for a data item smaller than 64 bytes, for example an 8-byte data item, misses the cache, a new line is allocated and all 64 bytes of the line are returned and filled into the cache. This is because most programs have spatial locality and the other 56 bytes of the line have a good probability of being accessed. However, some data structures are accessed sparsely, and demonstrate no spatial locality. In these situations only the 8 bytes of the request need to be returned because the other 56 bytes will not be accessed and it is a waste of energy to move them around.

FIG. 3Billustrates an embodiment of a cache structure with additional fields to address the wasted energy issue above. In addition to the fields, tag320, status325, and data345, the cache line302includes a field335to indicate the size of data held in data field345, and a field340to indicate which subset portion of data is held (i.e., field340indicates which portion of the data held in data field345is usable). For example, if the data field345can hold a maximum of 64 bytes of data, the data size field335may indicate that only 8 bytes out of the possible 64 bytes is stored in the corresponding cache line, and the data index field340may indicate that the third naturally aligned 8 bytes (i.e., bytes 17-24) of a 64-byte portion of data is stored in data field345. In an embodiment when a request for a subset, for example 8 bytes, of data encounters a cache miss, the request may only retrieve the required 8 bytes of the requested data from memory, store the retrieved 8 bytes of data into an associated cache line, and then return the requested data. The next time the same 8-byte data is requested, the request realizes that the data is present in the cache, and retrieves only the requested 8 bytes of data, therefore saving energy by not having to move around 64 bytes of data for every operation.

In an embodiment, as seen inFIG. 3B, a cache entry302may include a field330to indicate the cache coherency state of the cache line. Cache coherence is a useful mechanism in multiple processor systems to provide a shared memory abstraction to the programmer. When multiple processors cache a given shared memory location, a cache coherence problem may arise because a copy of the same memory location exists in multiple caches. A cache coherence protocol guarantees that a given memory location has a consistent view across all processors. Cache coherence protocols may include MSI, MESI (Illinois protocol), MOSI, MOESI, MERSI, MESIF, write-once, Synapse, Berkeley, Firefly, and Dragon protocols. The coherency state field330may be associated with any of the states relevant to different cache coherence protocols.

FIG. 4illustrates an embodiment for retrieving/storing data in a cache. A read probe may be sent by a requestor455for a subset of data in cache line402, which has the capacity to hold data that is larger than the requested subset of data. The request may find that the data in cache line402is larger than the requested data, and therefore, the request may return with a fill of the entire data445in the cache line, and a portion of the returned data may contain the requested data. For example, a read probe may be sent by a requestor455for an 8-byte section of a cache line which is capable of holding 64 bytes of data. The request may find that the data in the cache line402is the full 64-byte version of the data445, and therefore, the request may return with a 64-byte fill of the data, keeping the cache line in 64-byte mode.

FIG. 5illustrates an embodiment for retrieving/storing data in a cache. A read probe may be sent by a requestor555for the entire data information in cache line502. However, the cache line502may only contain a subset545of the requested data. Therefore, the subset data545may be merged with the missing portion of the requested data, which may be obtained from memory565, and the merged data575may be returned to the requestor555. In an embodiment, the subset data545, and the missing portion of the data obtained from memory565, may be returned to the requestor and the requestor may merge the data575. The merged data may be stored in cache line502. For example, a read probe may be sent by a requestor555for the entire 64 bytes of data in a cache line502, but the read probe may find that the cache line currently only contains an 8-byte subset545of the requested data. Therefore, the 8-byte version of the line545and the other56bytes of the line obtained from memory565, may be returned to the requestor555and merged575.

FIG. 6illustrates an embodiment for retrieving/storing data in a cache. A read probe may be sent by a requestor655for a subset of data in cache line602. However, the cache line602may only contain a different subset645of data. Therefore, the subset of data in the cache line645may be merged with a missing portion of corresponding data, which may be obtained from memory665, and the merged data675may be returned to the requestor655. In an embodiment, the subset data645, and the missing portion of the data obtained from memory665, may be returned to the requestor and the requestor may merge the data675. The merged data may be stored in cache line602. For example, a read probe may be sent by a requestor655for the first 8 bytes of data from a cache line602, but the read probe may find that the cache line currently only contains a different 8-byte subset of data645. Therefore, the 8 bytes of data in the cache line645and the other 56 bytes of the line obtained from memory665may be returned to the requestor655and merged675.

In the embodiments described, there are instances where the values 4 bytes and 8 bytes are used to describe the size of data subsets read/written. It should be evident that these values are not meant to restrict the invention, but are rather used for exemplary purposes. The size of subset data accessed in a cache line may be of any size. Similarly, there are instances where the value 64 bytes is used to describe the size of data in a cache line, and the maximum size of data. It should be evident that this value is not meant to restrict the invention, but is rather used for exemplary purposes. The size of data stored/accessed and the maximum size of data in a cache line may be of any size.

The embodiments of methods, hardware, software, firmware or code set forth above may be implemented via instructions or code stored on a machine-accessible or machine readable medium which are executable by a processing element. A machine-accessible/readable medium includes any mechanism that provides (i.e., stores and/or transmits) information in a form readable by a machine, such as a computer or electronic system. For example, a machine-accessible medium includes random-access memory (RAM), such as static RAM (SRAM) or dynamic RAM (DRAM); ROM; magnetic or optical storage medium; flash memory devices; electrical storage device, optical storage devices, acoustical storage devices or other form of propagated signal (e.g., carrier waves, infrared signals, digital signals) storage device; etc. For example, a machine may access a storage device through receiving a propagated signal, such as a carrier wave, from a medium capable of holding the information to be transmitted on the propagated signal.