Static set partitioning for caches

[0001] An embodiment of the invention relates generally to computers and more particularly to partitioning a cache within a computer.

[0002] A computer stores data in memory. Data may be computer-executable instructions and control structures used to operate the computer or information of importance to a user of the computer. In order to do useful work, the computer operates on and performs manipulations against this data; for example, the computer might add two pieces of data together or compare two pieces of data to determine which is larger. Ideally, a computer would have a singular, indefinitely large and very fast memory, in which any particular data would be immediately available to the computer. In practice this has not been possible because memory that is very fast is also very expensive.

[0003] Thus, computers typically have a hierarchy (or levels) of memory, each level of which has greater capacity than the preceding level, but which is also slower with a less expensive per-unit cost. These levels of the hierarchy may form a subset of one another, that is, all data in one level may also be found in the level below, and all data in that lower level may be found in the one below it, and so on until we reach the bottom of the hierarchy. In order to minimize the performance penalty that the hierarchical memory structure introduces, the computer would like to store the most frequently-used data in the fastest memory and the least frequently-used data in the slowest memory.

[0004] For example, a computer might contain:

[0005] 1) a cache that contains the most frequently-used data;

[0006] 2) a RAM (Random Access Memory) that contains all the data in the cache plus the next-most frequently-used data; and

[0007] 3) a, disk drive that contains all the data in the computer.

[0008] In order to determine which data should be placed in the faster memory; for example in the cache or RAM, the computer may attempt to predict which data will be frequently used. In order to predict use frequency, computers have typically used the theory of temporal locality of reference: recently-used data is likely to be used again soon. Using this theory, when the computer needs a piece of data, it looks first in the cache. If the data is not in the cache, the computer then retrieves the data from a lower level of memory, such as RAM or a disk drive, and places the data in the cache. If the cache is already full of data, the computer must determine which data to remove from the cache in order to make room for the data currently needed. One removal method is for the computer to replace the data that has been unused for the longest time. This exploits a corollary of temporal locality: if recently-used data is likely to be used again, then the best candidate for removal is the least recently-used data. Thus, one method for replacing data in fast memory is the Least Recently Used (LRU) method.

[0009] The LRU method only yields good computer performance when the temporal locality of reference theory holds true; that is, in situations where the recently-used data is actually likely to be used again soon. If the temporal locality of reference theory does not hold true, then the LRU method by itself performs poorly. An example of when the LRU method may perform poorly is when multiple instruction streams (threads or processes) are all accessing the same cache. Multiple instruction streams can result from, e.g., a computer that has multiple processors, multiple cores within a processor, or multiple instruction streams executing concurrently on the same processor. These instruction streams may access completely different data, yet their cache accesses may be interspersed.

[0010] Thus, when multiple streams are accessing data, the temporal locality of reference theory does not necessarily hold true across multiple streams, and poor performance can result because the streams may interfere with each other's cache use, and the computer may discard the data from the cache that is actually likely to be used next.

[0011] FIG. 1 depicts a block diagram of an electronic device for implementing an embodiment of the invention.

[0012] FIG. 2 depicts a block diagram of an example cache, according to an embodiment of the invention.

[0013] FIG. 3 depicts a flowchart of example processing, according to an embodiment of the invention.

[0014] FIG. 4 depicts a block diagram of example processing, according to an embodiment of the invention.

[0015] FIG. 1 depicts a block diagram of an electronic device for implementing an embodiment of the invention. An electronic device 110 may include a cache controller 136, a memory 139, and a storage device 140, all connected via a bus 180. The cache controller 136 may be connected to a processor 135 and a cache 137.

[0016] The processor 135 may represent a central processing unit of any type of architecture, such as a CISC (Complex Instruction Set Computing), RISC (Reduced Instruction Set Computing), VLIW (Very Long Instruction Word), or a hybrid architecture, although any appropriate processor may be used. The processor 135 may execute instructions and may include that portion of the electronic device 110 that controls the operation of the entire electronic device. Although not depicted in FIG. 1, the processor 135 typically includes a control unit that organizes data and program storage in memory and transfers data and other information between the various parts of the electronic device 110. The processor 135 may request data from the cache controller 136, which requests the data from the cache 137. If the requested data is not present in the cache 137, then the processor may look for the data in the memory 139. If the requested data is not present in the memory 139, then the processor may look for the data in the storage device 140.

[0017] Although the electronic device 110 is shown to contain only a single processor 135 and a single bus 180, in another embodiment an electronic device may have multiple processors and/or have multiple buses with some or all performing different functions in different ways.

[0018] The cache controller 136 controls the storage and retrieval of data from the cache 137. Although the cache controller 136 is drawing as being separate from the processor 135 and the cache 137, in other embodiments the cache controller 136 may be included in the processor 135 or the cache 137. In an embodiment, the cache controller 136 may be implemented in hardware. But, in another embodiment, the cache controller 136 may be implemented in instructions that execute on a processor. Processing for the cache controller 136 is further described below with reference to FIGS. 3 and 4.

[0019] The cache 137 is a level of memory hierarchy encountered once an address leaves the processor 135. The cache 137 stores data that has been used by the processor 135 and might be used in the future. Although only one cache 137 is shown, in another embodiment the cache 137 may have multiple levels. In an embodiment, the processor 135 is a multi-threaded processor and the cache 137 is an L1/L2/L3 (Level 1/Level 2/Level 3) cache for the multithreaded processor where different request streams correspond to different threads that time-share the processor 135. In another embodiment, the cache 137 is an L3 (Level 3) cache and the processor 135 is a multi-core processor where different request streams correspond to the threads/processes running on each core. In another embodiment, the cache 137 is shared by multiple processors with each processor having its own request stream and priority. In another embodiment, the cache 137 is an eDRAM chipset cache, and different request streams correspond to the processor 135 to memory 139 stream and an I/O device (such as the storage device 140) to memory 139 request stream. In another embodiment, the cache 137 is a software cache used by proxy servers. In an embodiment, the cache 137 is organized in a set-associative scheme. In another embodiment, the cache 137 is organized in a fully associative scheme. In another embodiment, the cache 137 is organized in any appropriate scheme. The cache 137 is further described below with reference to FIG. 2.

[0020] The memory 139 may represent one or more mechanisms for storing data. For example, the memory 139 may include random access memory (RAM), magnetic disk storage media, optical storage media, or any other appropriate type of machine-readable media. Although only one memory 139 is shown, in another embodiment, multiple types and/or multiple levels of memory may be present.

[0021] The storage device 140 may represent one or more mechanisms for storing data. For example, the storage device 140 may include read only memory (ROM), random access memory (RAM), magnetic disk storage media, optical storage media, flash memory devices, and/or other machine-readable media. In other embodiments, any appropriate type of storage device may be used. Although only one storage device 140 is shown, multiple storage devices and multiple types of storage devices may be present. Further, although the electronic device 110 is drawn to contain the storage device 140, it may be distributed across other electronic devices.

[0022] The storage device 140 may include a compiler 190 and an application 192. The compiler 190 may contain instructions that execute on the processor 135 to compile source code in the application 192 into object code for execution on the processor 135. The compiler 190 may assign stream identifiers to portions of the object code as further described below with reference to FIGS. 3 and 4. Although the compiler 190 is shown to be included in the storage device 140, in another embodiment the compiler 190 may be in another electronic device. Of course, the storage device 140 may also contain additional software and data (not shown), which is not necessary to understanding an embodiment of the invention. Although only one application 192 is shown, in another embodiment multiple application may be present, some or all of which may generate multiple instruction streams to execute on the processor 135.

[0023] The bus 180 may represent one or more busses (e.g., PCI, ISA (Industry Standard Architecture), X-Bus, EISA (Extended Industry Standard Architecture), or any other appropriate bus and/or bridge (also called a bus controller).

[0024] The electronic device 110 may be implemented using any suitable hardware and/or software, such as a personal computer or other appropriate electronic device. Portable computers, laptop or notebook computers, PDAs (Personal Digital Assistants), two-way alphanumeric pagers, portable telephones, pocket computers, network appliances, minicomputers, and mainframe computers are examples of other possible configurations of the electronic device 110. The hardware and software depicted in FIG. 1 may vary for specific applications and may include more or fewer elements than those depicted. For example, other peripheral devices such as audio adapters, or chip programming devices, such as EPROM (Erasable Programmable Read-Only Memory) programming devices may be used in addition to or in place of the hardware already depicted. Thus, an embodiment of the invention may apply to any hardware configuration that employs a cache.

[0025] As will be described in detail below, aspects of an embodiment pertain to specific apparatus and method elements implementable on an electronic device. In another embodiment, the invention may be implemented as a program product for use with an electronic device. The programs defining the functions of this embodiment may be delivered to an electronic device via a variety of signal-bearing media, which include, but are not limited to:

[0026] (1) information permanently stored on a non-rewriteable storage medium (e.g., read-only memory devices attached to or within an electronic device, such as a CD-ROM readable by a CD-ROM drive);

[0027] (2) alterable information stored on a rewriteable storage medium (e.g., a hard disk drive or diskette); or

[0028] (3) information conveyed to an electronic device by a communications medium, such as through a computer or the telephone network accessed via a network, including wireless communications.

[0029] Such signal-bearing media, when carrying machine-readable instructions that direct the functions of the present invention, represent embodiments of the present invention.

[0030] FIG. 2 depicts a block diagram of example contents of the cache 137, according to an embodiment of the invention. Shown in the cache 137 is one set including 8 blocks: blocks 202, 204, 206, 208, 210, 212, 214, and 216. A set is a group of blocks in the cache 137. Blocks 202 and 204 are associated with stream 1 and form the first subset of the set. Blocks 206, 208, 210, 212, 214, and 216 are associated with stream 2 and form the 2^nd subset of the set. Thus, the set is broken down into two subsets corresponding to the two streams. Although the example of FIG. 2 shows the cache 137 with one set, two subsets corresponding to two streams, and eight blocks with two blocks in the first subset and six blocks in the second subset, in another embodiment the cache 137 may contain any number of sets, subsets, blocks, and allocation of blocks within subsets.

[0031] In an embodiment, the cache 137 may be said to be set associative, meaning that a block can be placed in a restricted set of places in the cache 137. A block may be first mapped onto a set, and then the block may be placed anywhere within the set. In an embodiment, the set for a given block may be chosen by bit selection; that is, (block address) MOD (number of sets in the cache), but in another embodiment any appropriate set selection technique may be used. If there are N blocks in a set, the cache placement is said to be n-way set associative. Thus, the number of ways is the number of blocks in a set. In another embodiment, the cache 137 is organized in a fully associative scheme. In another embodiment, the cache 137 may be organized in any appropriate scheme.

[0032] In an embodiment, blocks in the cache 137 are accessed via an address, which may include a block address and a block offset. The block address may be further broken down into a tag and an index. The tag may be used to check all the blocks in the set and the index may be used to select the set. The block offset may be the address of the desired data within the block. In another embodiment, any appropriate addressing scheme may be used.

[0033] Since the cache 137 is partitioned into subsets within a set, the streams do not interfere with each other. Thus, even if one stream is poorly behaved, e.g., it demonstrates a lack of temporal locality of reference, the performance of the other stream or streams will not be impacted.

[0034] FIG. 3 depicts a flowchart of example processing for two request streams, according to an embodiment of the invention. Control begins at block 300. Control then continues to block 305 where two request streams possessing potentially different spatial and/or temporal properties access the cache 137. Control then continues to block 310 where the cache controller 136 may assign a stream identifier (0 or 1 in an embodiment, although any appropriate identifier may be used) to each request to identify the associated stream. In another embodiment, the compiler 190 may assign the stream identifier. In an embodiment, the stream identifier may indicate the priority of the stream. In an embodiment, the user of the application 192 may specify the priority of streams based on, e.g., knowledge of the properties of the streams or the level of importance/criticality of the stream. In another embodiment, the developer of the application 192 may specify the priority of the streams based, e.g., on the knowledge of the properties of the streams. In another embodiment, the manufacturer of the application 192 may specify the priority of the streams based, e.g., on its intended functionality.

[0035] Control then continues to block 315 where the cache controller 136 divides the set into 2 subsets, one subset consisting of X ways and the other subset consisting of S-X ways where S (an integer) may be the number of ways in each set in the cache 137 and X (also an integer) may be a tunable parameter. In an embodiment the developer of the cache 137 may assign the cache 137 with only one possibility for the value of X. In another embodiment, X may be a configurable parameter that is available to be changed by the application 192, the user of the application 192, and/or the compiler 190. By keeping X low, one stream is restricted to a smaller space in the set. (In the example of FIG. 2, S8, X2 for stream 1, and S-X6 for stream 2.) In an embodiment, X may be found in a configuration file. In another embodiment, X may be accessible via the BIOS (Basic Input/Output System) of the electronic device 110.

[0036] Control then continues to block 320 where the cache controller 136 searches through all tags in the set for each cache lookup/access request for a given stream and locates the requested block if it is present in the cache 137. Control then continues to block 322 where the cache controller 136 determines whether the requested data was found in block 320.

[0037] If the determination at block 322 is true, the data is found in the cache 137, so control continues to block 324 where the cache controller 136 returns the data from the cache 137 to the instruction executing on the processor 135 that requested the data. Finding the requested data in the cache 137 is called a cache hit. Control then continues to block 399 where the function returns.

[0038] If the determination at block 322 is false, then the data is not found in the cache 137, so the cache controller 136 generates a cache miss, which may cause the cache controller 136 to look for the data in another level of the cache 137 (if one is present) or the processor 135 may request the data from another level of storage, which may be the memory 139 or the storage device 140. If the processor 135 finds the requested data in another level of storage, then control continues to block 325 where the data is brought into the cache 137 and the cache controller 136 may allocate the block of data into the I^th subset in the cache 137, where I is the identifier of the request stream and the identifier of the associated subset. Control then continues to block 399 where the function returns.

[0039] Any appropriate cache replacement policy may be used, depending on the type of cache being used, the properties of the streams, and the operating environment. Existing replacement policies may be used for each subset instead of for each set.

[0040] FIG. 4 depicts a block diagram of example processing for another embodiment with multiple request streams.

[0041] Control begins at block 400. Control then continues to block 405 where multiple request streams possessing potentially different spatial and/or temporal properties access the cache 137 where N is the number of physical request streams. Control then continues to block 410 where the cache controller 136 may assign a logical stream identifier (0 to M1 in an embodiment, although any appropriate identifier may be used) to each request to identify the associated logical stream. In another embodiment, the compiler 190 may assign the stream identifier. In an embodiment, the stream identifier may indicate the priority of the stream. In an embodiment, the user of the application 192 may specify the priority of streams based, e.g., on knowledge of the properties of the streams or the level of importance/criticality of the stream. In another embodiment, the developer of the application 192 may specify the priority of the streams based, e.g., on the knowledge of the properties of the streams. In another embodiment, the manufacturer of the application 192 may specify the priority of the streams based, e.g., on its intended functionality. In an embodiment the number of physical request streams (N) may be the same as the number of logical request streams (M). In another embodiment, M and N may be different.

[0042] Control then continues to block 415 where the cache controller 136 divides the set into M subsets, each subset containing S/M ways where S is the number of ways in each set in the cache 137. In another embodiment, the cache controller 136 may divide the set into M subsets, with each subset containing a number of ways determined by the cache designer, wherein the number of ways in each subset may be equal or some or all may be different from each other.

[0043] Control then continues to block 420 where the cache controller 136 searches through all tags in the set for each cache lookup/access request for a given stream and locates the requested block if it is present in the cache 137. Control then continues to block 422 where the cache controller 136 determines whether the requested data was found in block 420.

[0044] If the determination at block 422 is true, the data is found in the cache 137, so control continues to block 424 where the cache controller 136 returns the data from the cache 137 to the instruction executing on the processor 135 that requested the data. Finding the requested data in the cache 137 is called a cache hit. Controller then continues to block 499 where the function returns.

[0045] If the determination at block 422 is false, then the data is not found in the cache 137, so the cache controller 136 generates a cache miss, which may cause the cache controller 136 to look for the data in another level of the cache 137 (if one is present) or the processor 135 may request the data from another level of storage, which may be the memory 139 or the storage device 140. If the processor 135 finds the requested data in another level of storage, then control continues to block 425 where the data is brought into the cache 137, and the cache controller 136 may allocate the data block into the I^th subset of the cache 137, where I is the identifier of the logical request stream and the identifier of the associated subset. Control then continues to block 499 where the function returns.

[0046] Any appropriate cache replacement policy may be used, depending on the type of cache being used, the properties of the streams, and the operating environment. Existing replacement policies can be used for each subset instead of for each set.

[0047] In the previous detailed description of exemplary embodiments of the invention, reference was made to the accompanying drawings (where like numbers represent like elements), which form a part hereof, and in which was shown by way of illustration specific exemplary embodiments in which the invention may be practiced. These embodiments were described in sufficient detail to enable those skilled in the art to practice an embodiment of the invention, but other embodiments may be utilized and logical, mechanical, electrical, and other changes may be made without departing from the scope of an embodiment of the present invention. The previous detailed description is, therefore, not to be taken in a limiting sense, and the scope of embodiments of the present invention is defined only by the appended claims.

[0048] Numerous specific details were set forth to provide a thorough understanding of embodiments of the invention. However, embodiments of the invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure embodiments of the invention.