BACKGROUND

1. Field of the Invention

This invention is related to the field of processors and caching, and more particularly to cache management instructions.

2. Description of the Related Art

The rapid increase in operating frequency and performance of general purpose processors has been at the heart of increased computer system performance. At the same time, the amount of system memory (e.g. in the form of dynamic random access memory, or DRAM, of various types) has been increasing in size. However, the memory latency has not decreased to match the increases in processor performance. The latency of memory access is often a performance limiter.

To reduce the average memory latency, caches have been implemented within processors and/or in other locations that are logically between the processors and the system memory. Generally, the caches are small, low latency memories. Recently accessed data is typically stored in the cache, available for low latency access (as compared to system memory latency) by the processors.

While caches were originally designed to be transparent to the software executed by the processors, providing some cache management instructions has become common. The cache management instructions generally permit software to force data from main memory into the cache, or to force data stored in the cache out of the cache (either by invalidating the data in the cache, or writing the data back to the main memory).

SUMMARY

In one embodiment, an apparatus comprises at least a first processor and a second processor, a first cache coupled to the first processor, and a second cache coupled to the first cache. The first cache is private to the first processor, and the second cache is shared by at least the first processor and the second processor. The first processor is configured to execute a first instruction, including forming an address responsive to one or more operands of the first instruction. Responsive to a hit on a first cache block in the first cache by the address, the first cache is configured to transmit the first cache block to the second cache. The second cache is configured to retain the first cache block responsive to its transmission in response to the first instruction, and the first cache is configured to invalidate the first cache block in the first cache for at least one cache state in the first cache.

In another embodiment, a system comprises a first processor, a main memory system, and a cache hierarchy coupled between the first processor and the main memory system. The cache hierarchy comprises at least a first cache. The first processor is configured to execute a first instruction, including forming an address responsive to one or more operands of the first instruction. The system is configured to push a first cache block that is hit by the first address in the first cache to a target location within the cache hierarchy or the main memory system, wherein the target location is unspecified in a definition of the first instruction within an instruction set architecture implemented by the first processor, and wherein the target location is implementation-dependent.

BRIEF DESCRIPTION OF THE DRAWINGS

The following detailed description makes reference to the accompanying drawings, which are now briefly described.

FIG. 1 is a high level block diagram of one embodiment of a system.

FIG. 2 is a more detailed block diagram of one implementation of the system shown in FIG. 1.

FIG. 3 is a truth table illustrating one embodiment of cache state changes for one embodiment of a push for sharing instruction.

FIG. 4 is a flowchart illustrating operation of one embodiment of a non-target cache in response to a push for sharing instruction.

FIG. 5 is a flowchart illustrating operation of one embodiment of a target cache in response to a push for sharing instruction.

FIG. 6 is a block diagram of one embodiment of a processor.

FIG. 7 is a block diagram of one embodiment of a computer accessible storage medium.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF EMBODIMENTS

In one embodiment, a processor and its associated cache hierarchy support a push for sharing (PushSh) instruction. The PushSh instruction may be defined in the instruction set architecture of the processor to potentially move a cache block from one location in the cache hierarchy to another location (referred to as a target location of the PushSh instruction). The target location may be either in another cache or in the main memory system, and may be an implementation-dependent location. That is, the architectural definition of the PushSh instruction does not specify the target location, allowing designers to chose an effective target location for a given processor/cache hierarchy. The architectural definition of the PushSh instruction is independent of the cache hierarchy and main memory subsystem that may be provided in a given system.

In one embodiment, the cache hierarchy may include multiple cache levels. The cache levels may be viewed from the point of view of the processor, with level 1 (or L1) being the first cache that is searched for a cache block corresponding to a given address, level 2 (or L2) being the second cache that is searched (e.g. if the cache block is not found in the L1 cache or has insufficient cache state to perform the desired access), etc. Some cache levels may include caches that are private to a given processor (e.g., only that processor may directly search the private caches for a given address, although other caches may be snooped for coherence purposes). Other levels may be shared by the processor and one or more other processors in the system (e.g. each processor that shares the cache may directly search for a given address in the shared cache). For such an embodiment, one implementation of the PushSh instruction may search each private cache and may push the cache block (if found in the private caches) to a cache level having a shared cache. For example, in a chip multiprocessor implementation, the shared cache may be shared with other processors on the same chip (e.g. all the other processors, or a subset of the other processors). In an implementation in which processors are arranged into a node (whether or not the node is a chip multiprocessor), the shared cache may be shared among processors in the node.

Pushing a cache block from one cache to a target location may refer to transferring the cache block from the cache to the target location. For at least some cache states in the source cache, the cache block may be invalidated in the source cache. The cache block may be transferred to the target location even if the cache block is not modified (or dirty). In some embodiments, if the target location is the main memory system, the cache block need not be transferred if the cache block is not dirty since the main memory system already has a copy of the cache block.

The PushSh instruction may be used by a thread which has operated upon a cache block (or blocks) and reaches a point at which it becomes likely that the next access to the cache block will be performed by another thread (perhaps executing on another processor). By pushing the block to a target location that is shared with the other processor (that is executing the other thread), the read latency for the other thread may be reduced as compared to the latency that would occur if the block was obtained from the private caches of the processor using the coherence mechanism implemented in the system. Thus, the PushSh instruction may be a performance hint to the processor and system hardware, indicating that the cache block may be moved to a target location that is better, from a latency standpoint, for providing the cache block to a different processor. In some implementations, the target location may be in the main memory system, although the definition of the PushSh instruction does not require that the target location be in the memory system. Additionally, the definition of the PushSh instruction does not require that any data that is modified with respect to the main memory system be written to the main memory system due to execution of the PushSh instruction. Such operation is not prohibited, but is not required. Some implementations may even implement the PushSh instruction as a â€œno operationâ€ (noop) instruction that has no effect. For example, the PushSh instruction may be nooped if the target location would already have a copy of the cache block (e.g. the target location is inclusive of the source cache) or if a suitable target location cannot be found that would frequently give a performance benefit.

As mentioned previously, a cache may generally comprise a memory that stores copies of data that are also stored in the main memory system. That is, the system may use a memory address space to address the storage locations in the main memory system. The same memory addresses may be used to locate copies of the data in the caches. The caches may be divided into cache block storage locations, each of which is capable of storing a cache block of data. The cache block may be the unit of allocation and deallocation in the cache, and may be any size in various embodiments (e.g. 32 bytes, 64 bytes, 128 bytes or larger or smaller cache block sizes). The cache blocks may generally be aligned in memory to a cache block boundary. Thus, any cache block that is stored in the cache has a corresponding block of data in the main memory system, although the cache block in the cache may be modified with respect to the corresponding data in the main memory system. A memory address (or more briefly â€œaddressâ€ herein) may be searched in a given cache, which may detect a hit if the cache block is stored in the cache or a miss if the cache block is not stored in the cache. The main memory system, on the other hand, always has a copy of the data corresponding to the address and thus there is no concept of hit or miss in the main memory system for a given memory address. Pages of data may be paged in and out of the memory from other storage, such as disks and the like, but such mapping is handled by virtual address mechanisms and not the memory space addresses.

The cache may maintain a cache state for each stored cache block. The cache state may indicate whether or not the cache block is valid, and may also indicate if it is modified with respect to other copies of the cache block in other caches or in the main memory system. The cache state may also indicate coherence state for the cache coherence mechanism implemented by the system, if any.

Turning now to FIG. 1, a high level block diagram of one embodiment of a system 10 is shown. The system 10 may include one or more processors, such as processors 12A-12D shown in FIG. 1. Any number of processors may be included in various embodiments. The system 10 may include one or more private caches 14A-14D, each coupled to the respective processor 12A-12D as shown in FIG. 1. The system 10 may further include shared caches 16A-16B. The shared cache 16A is coupled to the private caches 14A-14B in the illustrated embodiment, and similarly the shared cache 16B is coupled to the private caches 14C-14D. The shared cache is thus coupled to the private caches corresponding to the processors that share that cache. In other embodiments, if there is more than one level of shared cache, a lower level shared cache may be coupled to an upper level shared cache that is shared by one or more of the processors that share the lower level shared cache. Similarly, in other embodiments, there may be multiple levels of private cache, and a lower level private cache may be coupled to an upper level private cache that is private to the same processor. Optionally, the shared caches 16A-16B may be coupled to communicate with each other. Alternatively, the shared caches 16A-16B may communicate only with the main memory system 18.

The processors 12A-12D may be configured to execute the PushSh instruction. Specifically, the PushSh instruction may specify one or more operands, which may be used to form an address corresponding to the cache block to be pushed. There may be one operand specifying the address, or there may be two or more operands that may be combined (e.g. added) to produce the address. The address may be a physical address that specifies the cache block in the main memory system 18. The operands may directly form the physical address, or the operands may form an effective or virtual address that the processors 12A-12D may translate to the physical address using the address translation functionality specified by the processor's instruction set architecture.

A given processor 12A-12D may transmit the PushSh operation and address to the private cache(s) 14A-14D coupled to that processor. For example, the processor 12A is shown perform a PushSh operation having an address â€œAâ€ to the private cache 14A. It is noted that, while the private caches 14A-14D are shown separate from the processors 12A-12D in FIG. 1 for illustration, the private caches 14A-14D may be an integral part of the processors themselves, tightly coupled to the processor's pipelines.

If the private cache 14A-14D detects a hit for the cache block addressed by address A, the private cache 14A-14D may push the cache block toward the target location (e.g. to a lower level shared cache, or to the main memory system 18, in various implementations). The private cache 14A-14D may also update its cache state for the cache block as well. For at least some cache states (prior to the PushSh instruction), the private cache 14A-14D may invalidate the cache block. In some embodiments, the private cache 14A-14D may invalidate the cache block for any previous cache state. In other embodiments, some previous states may result in a copy being retained, as described in more detail with regard to FIG. 3 below for one embodiment.

If the shared cache 16A-16B receives a cache block due to a PushSh operation (e.g. the shared cache 16A in FIG. 1), the shared cache 16A-16B may retain the cache block. That is, the shared cache 16A-16B may be the target location in this embodiment. In other embodiments, a given shared cache may not be the target location (e.g. if there is more than one level of shared cache or the main memory system is the target location for the implementation). Thus, the term â€œnon-targetâ€ cache may generally refer to any cache (private or shared) that is not the target cache for a PushSh operation and the term target location (or target cache) may be used to refer to the location/cache that is the target.

If the pushed cache block is a hit in the target cache, the target cache may update the stored cache block with the pushed cache block (and may update the cache state to match the cache state that the upper level cache had, if the cache state is more permissive than the current cache state in the target cache). If the pushed cache block is a miss in the target cache, the target cache may allocate a cache block storage location to store the pushed cache block. The allocation may cause the eviction of a stored cache block, which may be written back to the main memory system (or a lower level cache than the target cache, if one is present in the system).

In one embodiment, a variation of the PushSh instruction may be provided (via a separate opcode or via another operand of the PushSh instruction). The variation may push the cache block to a location in the home node of the cache block, for distributed shared memory systems. In various embodiments, the location in the home node may be a cache in the home node (e.g. a shared cache in the home node, or even a private cache in the home node); the home node main memory; or a cache or other buffer provided specifically to support the PushSh to the home node. The home node for a given cache block may be the node that includes the main memory that stores the cache block. A variant that pushes the cache block to the home node may be useful for cases in which the processor that is expected to read the cache block does not have a shared cache with the processor that executes the PushSh instruction (e.g. one of the processors 12C-12D, if the processor 12B executes the PushSh to home variant, illustrated as PushShH in FIG. 1). In the embodiment of FIG. 1, for example, the PushShH instruction is executed by the processor 12B and a PushShH operation for the cache block having the address â€œBâ€ is transmitted to the private cache 14B, the shared cache 16A, and into the shared cache 16B. Any mechanism for transmitting the data to the shared cache 16B for storage may be used. For example, one embodiment may use a technique similar to that described in U.S. Pat. No. 7,155,572. The disclosure of the above patent is incorporated herein by reference in its entirety. To the extent that anything in the incorporated patent conflicts with the material in this application, the material in this application controls.

Turning next to FIG. 2, a block diagram of one embodiment of the system 10 (system 10a) is shown in more detail. Numerous other embodiments are possible. In the embodiment of FIG. 2, the system 10a is a multi-node distributed shared memory system. Each node 20A-20B includes a memory controller (MC 22A-22B) that may be coupled to memory modules forming a portion of the main memory system of the system 10a (memory modules not shown in FIG. 2). Together, the memory controllers 22A-22B and the attached memory may be an embodiment of the main memory system 18 shown in FIG. 1. Additionally, each node 20A-20B includes processors (e.g. processors 24A-24D), each processor including L1 and L2 private caches in this embodiment (reference numerals 26A-26D, respectively). A shared L3 cache 28A-28B is included in each node 20A-20B, and is shared by the processors in that node. A node controller 30A-30B couples the processors 24A-24D, the memory controllers 22A-22B, and the L3 caches 28A-28B and routes communications between them. Additionally, the node controller 30A-30B couples HyperTransportâ„¢ (HT) interfaces 32A-32H for external communication. The HT interfaces 32D and 32E are coupled to communicate between the nodes 20A-20B. Other nodes (not shown) may be coupled to the nodes 20A-20B via other HT interfaces, or the HT interfaces may be used to couple to various peripheral devices. Other embodiments may use other interconnects to link nodes.

As mentioned above, the L1 and L2 caches 26A-26D may be private caches for the respective processors 24A-24D. That is, the caches 26A-26D may be an embodiment of the private caches 14A-14D shown in FIG. 1. The L3 caches 28A-28B are shared, and thus may be an embodiment of the shared caches 16A-16B shown in FIG. 1. If the processor executes a PushSh instruction, the L1 and L2 caches in that processor push the affected cache block to the L3 cache in the node. If the PushShH variant is implemented, the affected cache block may be pushed to the L3 cache in the home node, the main memory in the home node, or other location in the home node.

In one embodiment, each node 20A-20B may comprise a single integrated circuit, implementing a chip multiprocessor configuration. Other embodiments of the system 10 are contemplated as well. For example, an embodiment of the system 10 may be similar to the standard personal computer configuration having one or more processors coupled via a â€œfront sideâ€ interconnect to a northbridge, which includes the memory controller and peripheral interfaces. Still further, embodiments are contemplated in which each processor is coupled to one or more caches in a lookaside or inline configuration, coupled to an interconnect between the lowest level caches and the main memory system (and possibly peripherals).

Turning next to FIG. 3, a truth table is shown illustrating an exemplary embodiment of the cache state changes that may occur in one embodiment of PushSh instruction execution. The embodiment of FIG. 3 illustrates the MOESI cache coherency protocol states: Modified, Owned, Exclusive, Shared, and Invalid. In the modified state, the cache block is dirty (i.e. it has been modified compared to the copy of the block stored in memory). In the owned state, the cache block was modified and has subsequently been shared with at least one other cache. The main memory system copy may not have been updated yet, and so the cache having the owned state may have the responsibility to ensure that the main memory system copy is updated. In the exclusive state, the cache has a clean copy of the cache block but no other cache has a copy. In the shared state, the cache has a copy and it is either clean or another cache has ownership of the cache block. In the invalid state, the cache's copy is not valid (e.g. it does not have a usable copy of the cache block). Other embodiments may use other coherency protocols (e.g. MESI, MSI, etc.).

In FIG. 3, the initial state of the cache block in a non-target cache (e.g. a private cache or a shared cache that is not the target of the PushSh instruction) is shown in the left column. The initial state is the state of the cache block in the non-target cache when the PushSh operation is presented to the cache. The corresponding final state in the non-target cache is in the middle column, and the final state in the target cache (when the pushed cache block has been stored therein) is shown in the right column. The target cache final state matches the initial cache state in the non-target cache. In some cases, if the target cache has a cache state that is more permissive (where modified is most permissive and invalid is least permissive) than the cache state from the non-target cache for the pushed cache block, the target cache may retain its own state.

As can be seen in the middle column, the final state in the non-target cache may generally be invalid. In some embodiments, the final state may always be invalid. That is, the cache block may always be invalidated from the non-target cache. However, if the initial state is owned or shared, some embodiments may have a final state of shared for the cache block. In these case of the owned or shared state, coherence activity may be needed before a write may be performed by another processor, and thus there is no advantage to going to the invalid state over the shared state. However, if the cache block is read again by the processor that executes the PushSh instruction, it may have a shared copy to read with low latency.

Turning next to FIG. 4, a flowchart is shown illustrating operation of one embodiment of a non-target cache in response to a PushSh operation. While the blocks are shown in a particular order for ease of understanding, other orders may be used. Blocks may be performed in parallel by combinatorial logic in the non-target cache. Blocks, combinations of blocks, and/or the flowchart as a whole may be pipelined over multiple clock cycles.

The address of the cache block affected by the PushSh operation may be checked against the cache. If the address is a miss (decision block 40, â€œnoâ€ leg), the non-target cache may take no other action (except to pass the PushSh operation on to the next lower level of cache, if any). If the address is a hit (decision block 40, â€œyesâ€ leg), and the cache does not receive the affected cache block from a higher level cache (decision block 42, â€œnoâ€ leg), the cache may read the block from the cache memory and transmit it to the next lower cache level, along with the cache state and the PushSh operation (block 44). The cache may also invalidate the cache block (block 46). In some embodiments, the cache may retain the block in shared state if the initial state was owned or shared. If the affected cache block is received from the higher cache level (decision block 42, â€œyesâ€ leg), the cache may pass the received cache block along with the PushSh operation to the next lower cache level and may invalidate the cache block in the cache (block 46). As mentioned previously, in some embodiments, the cache may retain the block in shared state if the initial state was owned or shared.

Turning next to FIG. 5, a flowchart is shown illustrating operation of one embodiment of a target cache in response to a PushSh operation. While the blocks are shown in a particular order for ease of understanding, other orders may be used. Blocks may be performed in parallel by combinatorial logic in the target cache. Blocks, combinations of blocks, and/or the flowchart as a whole may be pipelined over multiple clock cycles.

The address of the cache block affected by the PushSh operation may be checked against the cache. If the address is a miss (decision block 50, â€œnoâ€ leg) and a cache block is received from a higher level cache (decision block 52, â€œyesâ€ leg), the target cache may allocate a cache block storage location to store the cache block received from the higher level cache. The allocation may involve evicting a cache block currently stored in the cache block storage location (block 54). If the evicted cache block is modified with respect to the main memory system (e.g. the owned or modified cache states of the MOESI protocol), the evicted block may be transferred to the main memory system (or a lower level cache, if any). The target cache may write the received cache block to the allocated storage location (block 56) and may update the cache state to the cache state received from the higher level cache. If the address is a hit (decision block 50, â€œyesâ€ leg), the cache may write the received cache block (if any) to the cache at the hitting storage location (block 56). Again, the cache may update the stored cache state to the cache state provided from the higher level cache. The PushSh operation is not propagated any further than the target cache, since the target location has been reached.

It is noted that, for an embodiment in which the target location is the main memory system, operation may be similar to that of FIG. 5 except that the cache block is written to memory without any check for a â€œhitâ€ and there is no state update. The target location may be the main memory system for the PushSh instruction and/or the PushShH variant, in various embodiments.

The above operation of FIGS. 4 and 5 assumes that the cache state of the cache block in a higher level cache is more permissive or the same permissiveness as the cache state at the current level. If that is not the case, the cache may check its own cache state against the cache state provided from the higher level cache, and may provide the more permissive state (FIG. 4) or may update its state to the more permissive state (FIG. 5). Additionally, if the lower level cache has the more permissive cache state, the lower level cache may not update the stored cache block with the received data (e.g. if the lower level cache has modified data and the upper level cache does not, then the data need not be updated).

Turning now to FIG. 6, a block diagram of one embodiment of the processor 24A is shown in more detail. Other processors 24B-24D may be similar. In the illustrated embodiment, the processor 24A includes an L1 instruction cache 60, an execution core 62, an L1 data cache 64, and an L2 cache 66. The caches 60, 64, and 66 together may comprise the L1/L2 cache 26A in FIG. 2. The L1 instruction cache 60 and the L1 data cache 64 are coupled to the L2 cache 66. Additionally, the L1 instruction cache 60 and the L1 data cache 64 are coupled to the execution core 62.

FIG. 6 illustrates the path of a PushSh instruction/operation in the processor 24A. For example, the PushSh instruction may be fetched by the execution core 62 from the instruction cache 60, and may be executed by the execution core 62. The execution may include forming the address of the cache block affected by the PushSh instruction from one or more operands of the PushSh instruction (including translating the effective address to the physical memory address, if applicable). The execution core 62 may transmit a PushSh operation to the L1 data cache 64, including the address â€œAâ€ of the affected cache block. The L1 data cache 64 may pass the PushSh operation on to the L2 cache 66 (along with the cache block from the L1 data cache 64 and its cache state, if the cache block is a hit in the L1 data cache 64). The L2 cache 66 may pass the PushSh operation to the next lower level cache (e.g. the shared L3 cache 28A). The L2 cache 66 may provide the cache block from the L1 data cache 64, if any, or the cache block from the L2 cache 66, if any, and the corresponding cache state as well.

The caches 60, 64, and 66 may have any desired capacities and configurations (e.g. direct mapped, set associative, etc.). Additionally, some embodiments may implement a shared L1 instruction/data cache. The execution core 62 may implement any desired microarchitecture (e.g. in order or out of order execution, superscalar scalar or scalar, superpipelined, multithreaded or single threaded, etc.).

Turning now to FIG. 7, a block diagram of one embodiment of a computer accessible storage medium 200 is shown. Generally speaking, a computer accessible storage medium may include any storage media accessible by a computer during use to provide instructions and/or data to the computer. For example, a computer accessible storage medium may include storage media such as magnetic or optical media, e.g., disk (fixed or removable), tape, CD-ROM, or DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, volatile or non-volatile memory media such as RAM (e.g. synchronous dynamic RAM (SDRAM), Rambus DRAM (RDRAM), static RAM (SRAM), etc.), ROM, Flash memory, non-volatile memory (e.g. Flash memory) accessible via a peripheral interface such as the Universal Serial Bus (USB) interface, etc., microelectromechanical systems (MEMS), etc. The media may be insertable into the computer, integrated into the computer (e.g. a fixed disk or RAM), or coupled to the computer via a communication medium such as a network and/or a wireless link. A carrier medium may include computer accessible storage media as well as transmission media such as wired or wireless transmission.

The computer accessible storage medium 200 in FIG. 7 may store producer code 202. The producer code 202 may generally comprises instructions which, when executed, write data to one or more cache blocks and push those blocks using the PushSh instruction to a lower level cache to be shared with a thread executing on another processor. The producer code 202 may be part of many possible usages of the PushSh instruction. For example, the producer code 202 may be used by the producer in any producer/consumer model. Specifically, many types of thread-to-thread communication are performed through memory. Typically, the producer of the communication writes a message to memory, and the consumer reads the message. The producer may write the message, and then may use the PushSh instruction to push the written message to a shared cache from which the consumer may rapidly read the message. Examples of communication mechanisms that may use the instruction include sockets and pipes. Additionally, in semaphore-based locking mechanisms (in which the producer writes the â€œunlockâ€ value and the consumer reads the value), the producer may write the unlock value and may push the unlock value to the shared cache, where it may be more rapidly read by the consumer to detect the unlock of the semaphore. In distributed shared memory systems, message buffers may be allocated locally to a consumer, and remote writers (in other nodes) may write the message buffers. In typical invalidate-based coherence schemes, the writer reads the local message buffer cache blocks in order to update them. The reader than reads the local message buffer cache blocks (and the coherence mechanism causes the updated data to be transferred back to the reader's node). The data is always in the wrong node, in this case. However, with the PushSh instruction, the writer may push the updated cache blocks back to the home (reader's) node, and thus the messages may be obtained locally by the reader.

The producer code 202 is illustrated, for one embodiment, in exploded view in FIG. 7. The producer code 202 may include instructions to read a cache block â€œAâ€ , instructions to update the cache block as desired, and the PushSh instruction to push the cache block â€œAâ€ to a shared cache. There may be multiple cache blocks read, updated, and/or pushed and the instructions for different cache blocks may be interleaved.

Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.