Cache management for a number of threads

The illustrative embodiments provide a method, a computer program product, and an apparatus for managing a cache. A probability of a future request for data to be stored in a portion of the cache by a thread is identified for each of the number of threads to form a number of probabilities. The data is stored with a rank in a number of ranks in the portion of the cache responsive to receiving the future request from the thread in the number of threads for the data. The rank is selected using the probability in the number of probabilities for the thread.

BACKGROUND

The disclosure relates generally to data processing system and more specifically to cache management in data processing systems. Even more specifically, the disclosure relates to insertion of data in a cache.

2. Description of the Related Art

Caches are commonly used in data processing systems to store data for use by one or more processors. When a processor requests data from memory, the data is loaded into the cache from a memory, such as main memory or another cache. A cache may be comprised of memory that has a faster access time than the memory from which the cache is loaded. For example, a level 2 cache has a faster access time than main memory, and a level 1 cache has faster access time than the level 2 cache. In some illustrative examples, data processing systems contain smaller amounts of memory with faster access time to reduce the cost of manufacturing the data processing system.

The data is stored in the cache because a processor may access the same data multiple times. Retrieving the data from the cache is faster than retrieving the data from a lower level cache or main memory. A lower level cache is a cache that is separated from a processor by more levels of cache than a higher level cache. For example, an L2 cache located outside a processor unit is a lower level cache than an L1 cache located within the processor unit.

Because a cache is commonly smaller than the memory from which the cache data is loaded, the cache may implement several techniques to manage the cache. For example, a cache may be associative and be designed with multiple ways. An associative cache with multiple ways is designed such that a particular group of locations in main memory may be stored in any of a particular number of positions within the cache. For example, each cache set in an 8 way associative cache may store data from 8 memory addresses within a particular portion of main memory at a particular time.

Another technique used to manage the cache is a replacement process. In a cache with multiple ways, data in the cache may be overwritten to store data requested by the processor that is not presently stored within the cache. One replacement process is a least recently used (LRU) process. In a cache that implements a least recently used process, the data in each way of a cache is ranked according to the order the data was accessed by a processor unit. In other words, the data in each way is ranked from most recently used to least recently used. When a processor requests data not presently stored in the cache, the data is stored in the position in the way that holds the rank of least recently used.

Cache management is more challenging when multiple threads are running on a processor unit and using the same cache. The threads may not use memory in the same way. For example, one thread may use the same data very frequently, while another thread frequently uses data only once.

SUMMARY

The illustrative embodiments provide a method, a computer program product, and an apparatus for managing a cache. A probability of a future request for data to be stored in a portion of the cache by a thread is identified for each of the number of threads to form a number of probabilities. The data is stored with a rank in a number of ranks in the portion of the cache responsive to receiving the future request from the thread in the number of threads for the data. The rank is selected using the probability in the number of probabilities for the thread.

DETAILED DESCRIPTION

With reference now to the figures and in particular with reference toFIG. 1, an exemplary diagram of data processing environments is provided in which illustrative embodiments may be implemented. It should be appreciated thatFIG. 1is only exemplary and is not intended to assert or imply any limitation with regard to the environments in which different embodiments may be implemented. Many modifications to the depicted environments may be made.

With reference now toFIG. 1, a diagram of a data processing system is depicted in accordance with an illustrative embodiment. In this illustrative example, data processing system100includes communications fabric102, which provides communications between processor unit104, memory106, persistent storage108, communications unit110, input/output (I/O) unit112, and display114.

Memory106and persistent storage108are examples of storage devices116. A storage device is any piece of hardware that is capable of storing information, such as, for example, without limitation, data, program code in functional form, and/or other suitable information either on a temporary basis and/or a permanent basis. Memory106, in these examples, may be, for example, a random access memory, or any other suitable volatile or non-volatile storage device. Persistent storage108may take various forms, depending on the particular implementation. For example, persistent storage108may contain one or more components or devices. For example, persistent storage108may be a hard drive, a flash memory, a rewritable optical disk, a rewritable magnetic tape, or some combination of the above. The media used by persistent storage108may be removable. For example, a removable hard drive may be used for persistent storage108.

Communications unit110, in these examples, provides for communication with other data processing systems or devices. In these examples, communications unit110is a network interface card. Communications unit110may provide communications through the use of either or both physical and wireless communications links.

Input/output unit112allows for the input and output of data with other devices that may be connected to data processing system100. For example, input/output unit112may provide a connection for user input through a keyboard, a mouse, and/or some other suitable input device. Further, input/output unit112may send output to a printer. Display114provides a mechanism to display information to a user.

Instructions for the operating system, applications, and/or programs may be located in storage devices116, which are in communication with processor unit104through communications fabric102. In these illustrative examples, the instructions are in a functional form on persistent storage108. These instructions may be loaded into memory106for execution by processor unit104. The processes of the different embodiments may be performed by processor unit104using computer implemented instructions, which may be located in a memory, such as memory106.

These instructions are referred to as program code, computer usable program code, or computer readable program code that may be read and executed by a processor in processor unit104. The program code, in the different embodiments, may be embodied on different physical or computer readable storage media, such as memory106or persistent storage108.

Program code118is located in a functional form on computer readable media120that is selectively removable and may be loaded onto or transferred to data processing system100for execution by processor unit104. Program code118and computer readable media120form computer program product122. In one example, computer readable media120may be computer readable storage media124or computer readable signal media126. Computer readable storage media124may include, for example, an optical or magnetic disc that is inserted or placed into a drive or other device that is part of persistent storage108for transfer onto a storage device, such as a hard drive, that is part of persistent storage108. Computer readable storage media124also may take the form of a persistent storage, such as a hard drive, a thumb drive, or a flash memory that is connected to data processing system100. In some instances, computer readable storage media124may not be removable from data processing system100.

Alternatively, program code118may be transferred to data processing system100using computer readable signal media126. Computer readable signal media126may be, for example, a propagated data signal containing program code118. For example, computer readable signal media126may be an electro-magnetic signal, an optical signal, and/or any other suitable type of signal. These signals may be transmitted over communications links, such as wireless communications links, an optical fiber cable, a coaxial cable, a wire, and/or any other suitable type of communications link. In other words, the communications link and/or the connection may be physical or wireless in the illustrative examples. The computer readable media also may take the form of non-tangible media, such as communications links or wireless transmissions containing the program code.

In some illustrative embodiments, program code118may be downloaded over a network to persistent storage108from another device or data processing system through computer readable signal media126for use within data processing system100. For instance, program code stored in a computer readable storage media in a server data processing system may be downloaded over a network from the server to data processing system100. The data processing system providing program code118may be a server computer, a client computer, or some other device capable of storing and transmitting program code118.

As another example, a storage device in data processing system100is any hardware apparatus that may store data. Memory106, persistent storage108, and computer readable media120are examples of storage devices in a tangible form.

The different illustrative embodiments recognize and take into account a number of considerations. The different illustrative embodiments recognize and take into account that multiple threads may use a cache shared among the multiple threads differently. For example, a first thread may frequently reuse a small amount of data. A second thread may use a large amount of data once without reusing the data. The different illustrative embodiments recognize that a least recently used cache replacement process allows the second thread to cause data being frequently reused by the first thread to be replaced in the cache. Delays may be caused because the first thread may request the same data from the memory again. The second thread also may not benefit from the storage of the data for the second thread in the cache because the second thread does not reuse the data.

The different illustrative embodiments also recognize and take into account that a probability of a thread reusing data in a cache may be identified by monitoring a subset of the cache sets in the cache. Over a particular length of time or number of cache accesses, the probability may be identified by creating a usage profile for the thread. The usage profile is a number of counters associated with the thread that represent the rank of the data in the least recently used cache replacement process. In one illustrative embodiment, a counter for the current rank of the data may be incremented when the data in the cache is requested by the thread. In another illustrative embodiment, the counter for the rank closest to the least recently used rank held by the data while in the cache and before being requested by the thread may be incremented when the data is replaced in the cache.

The different illustrative embodiments also recognize and take into account that a probability density function may be calculated using the counters for the thread. The value for each counter may be divided by the sum of the values for all counters for the thread to form a normalized value for each counter. The normalized values may then be reflected over an axis at the midpoint between lowest rank and highest rank. That is, the normalized value for the lowest rank may become the highest value in the probability density function.

The different illustrative embodiments also recognize and take into account that the probability density function may be used during the next period in the cache sets that are not identifying the probability for a subsequent period. In other words, the cache sets not performing the probability identification may store data requested by the threads with a least recently used rank based on the probability density function. A random number may be generated for the rank of the requested data. The random number is weighted with the probability density function of the thread requesting the data. The data may then be stored in the cache with the rank of the weighted random number.

Turning now toFIG. 2, a cache management environment is depicted in accordance with an illustrative embodiment. Cache management environment200may be implemented in data processing system100inFIG. 1. Components of cache management environment200may also be implemented across a number of data processing systems, such as data processing system100.

Cache management environment200contains cache228, processing unit220, and cache management process202. Processing unit220is an example of processor unit104inFIG. 1. Processor unit220runs number of threads222. Number of threads222are tasks that are run on processing unit220in a substantially concurrent manner. Thread224is a task running on processing unit220within number of threads222.

Cache228is a memory in cache management environment200. In some illustrative examples, cache228stores data, such as data238because cache228is capable of transferring data238to and from processing unit220more quickly than another memory or cache. Cache228is associated with processing unit220. In this illustrative example, processing unit220is connected to cache228such that data in cache228may be transferred to and from processing unit220. In these examples, cache228is associative cache264. Associative cache264is a cache228that is divided into at least one portion230. Portion230is a section of cache228. Cache228may be divided into cache sets. In these examples, portion230is subset of cache sets232.

A first component is considered to be associated with a second component by being secured to the second component, bonded to the second component, fastened to the second component, and/or connected to the second component in some other suitable manner. The first component also may be connected to the second component through using a third component. The first component is also considered to be associated with the second component by being formed as part of and/or an extension of the second component.

Portion230contains data234and data238. Data234and data238may be copies of data stored in main memory or another cache. In some illustrative embodiments, cache228is smaller than a memory or cache from which data238is copied. Thus, data238may be replaced in portion230when additional data is stored in cache228. In these examples, cache228implements least recently used cache replacement policy248. A policy is a number of rules. A policy may also include parameters. In this illustrative example least recently used cache replacement policy248is a policy used to select a candidate for replacement in portion230. For example, data238may be replaced in portion230with other data if data238is the candidate for replacement.

Cache management process202implements least recently used cache replacement policy248by selecting a candidate data238with rank240that meets a criteria. In these examples, the criteria is satisfied when rank240represents that data238is least recently accessed data254in portion230. Number of ranks246represents the ranking for order of access250of data234and data238in portion230. That is, number of ranks246ranks data234, data238, and other data stored in portion230from most recently accessed data252to least recently accessed data254.

Order of access250is the order in which data, such as data238, in portion230was accessed by thread224. Accessed means reading, writing, or a combination of reading and writing. Most recently accessed data252is rank240in number of ranks246associated with data238when data238is the data last accessed by processing unit220. Least recently accessed data254is rank240in number of ranks246associated with data238when data238was last accessed by processing unit220prior to all other data in portion230.

For example, rank240may be stored in number of ranks246. Number of ranks246may be an array of values. The size of the array may be the same as portion230such that number of ranks246stores a value corresponding to each data238in portion230. In one illustrative embodiment, rank240is associated with data238by being at the same position within the array of number of ranks246as data238is within portion230. For example, if data238is located in the third position within an array representing portion230, rank240is associated with data238by being stored in the third position in the array representing number of ranks246.

Data238is assigned rank240based on order of access250. In other words, rank240associated with data238is changed each time another data in portion230is accessed or replaced. Rank240begins at most recently accessed data252and increases toward least recently accessed data254. When rank240is least recently accessed data254, the value for rank240is the size of portion230.

For example, assume portion230contains 8 positions for data, such as data238. Rank240associated with data238is set to zero when data238is stored in portion230. When other data, such as data234, is stored in portion230, rank240associated with data238is set to 1. In this example, the value of rank240when rank240is least recently accessed data254is 8 because portion230has 8 positions for data238. As additional data is stored in portion230, rank240associated with data238is incremented until rank240is 8. The additional data may overwrite data presently stored in portion230, such as data234. When another data in portion230is accessed by processing unit220, data238is replaced with the requested data. Rank240for the requested data is set to most recently accessed data252. In this example, rank240is set to 0.

Cache management process202monitors requests in cache228. Cache management process202may be run by processing unit220. Alternatively, cache management process202may be implemented using a number of gates, including, but not limited to, AND gates, OR gates, and XOR gates. Cache management process202may perform the monitoring for period210. Period210may be amount of time212, number of cache accesses214, or another suitable measurement. For example, period210may be 900 accesses of cache228by processing unit220. The accesses may be performed by thread224in number of threads222.

Cache management process202monitors requests in cache228to identify number of probabilities206. Number of probabilities206are probability208of each thread224in number of threads222accessing data, such as data238, in future request204. Future request204is an operation of thread224that has not yet occurred. The operation may be a read, a write, or a combination of reads and writes. Probability208is a likelihood that thread224requests data, such as data234, after the data is already stored in portion230. In other words, probability208is the likelihood that thread224reuses data that has been requested while the data is stored in the cache.

Probability208is identified by cache management process202using number of counters256. Number of counters256are values associated with thread224and a rank, such as rank240. For example, counter242is in number of counters256and associated with rank240. In one illustrative embodiment, cache management process202begins counter242at zero. Cache management process202increments counter242associated with rank240each time data238with rank240is accessed by thread224.

For example, data238is at rank240. Other data in portion230is then accessed by thread224. Assume rank240of data238represents that rank240is least recently accessed data254. Thread224accesses data238. In response to thread224accessing data238, cache management process202increments counter242associated with rank240. In this example, cache management process202increments counter242associated with rank240that represents least recently accessed data254.

In some illustrative embodiments, counter226is also present. Counter226is associated with an access of data not presently stored in portion230. In other words, counter226is associated with a cache miss. Cache management process202increments counter226each time thread224requests data not presently stored in portion230.

In another illustrative embodiment, cache management process202begins counter242at zero. Cache management environment202increments counter242each time data238is replaced in portion230. Data238may be replaced by being overwritten with data from a memory. For example, the memory may be persistent storage108inFIG. 1.

Cache management process202increments counter242associated with highest rank244held by data238. Highest rank244is rank240farthest from most recently accessed data252held by data238before being accessed by224.

For example, assume cache228is an 8-way associative cache. Rank240is 1 when data238is most recently accessed data252. Rank240is 8 when data238is least recently accessed data254. In this example, data238is stored in portion230with rank240of 1. Assume two other data are then stored in portion230. Rank240of data238is then 3. In this example, data238is then accessed by thread224. Cache management process202detects the access of data238and sets highest rank244to 3.

In this example, other data is stored in portion230until rank240becomes 8. When rank240is 8, rank240is also least recently accessed data254. When additional data is stored in portion230, data238is overwritten in portion230. Cache management process202then increments counter242associated with rank 3.

In some illustrative embodiments, counter226is also present. Counter226is incremented when data238is stored in portion230but not subsequently accessed by thread224. Cache management process202continues identifying probability208until period210expires. Period210may be an amount of time212, a number of cache accesses214, or another suitable period.

Once period210has expired, cache management process202generates probability density function216for each thread224in number of threads222. Probability density function216is a function that describes number of probabilities206for number of threads222. Cache management process202generates probability density function216by dividing the value of each counter in number of counters256by sum262. Sum262is a value found by adding the values for the counters in number of counters256.

Cache management process202then reflects number of counters256over axis258. Axis258may be located at n/2 counter260. N/2 counter is counter242representing rank240associated with a midpoint between most recently accessed data252and least recently accessed data254. For example, if cache228is an 8-way associative cache, n/2 counter260is at counter242associated with rank240of 4.

Reflecting number of counters256over axis258means that number of counters256is inverted such that the value associated with the rank240for most recently accessed data252in probability density function216was the value associated with the rank240for least recently accessed data252in number of counters256.

For example, in an 8-way associative cache where rank 1 is most recently accessed data252and rank 8 is least recently accessed data254, counter242associated with rank 1 is reflected across axis258in probability density function216. Counter242for rank 1 is thus assigned to rank 8 in probability density function216and counter242for rank 8 is assigned to rank 1 in probability density function216. Likewise, counter242associated with rank 2 in number of counters256is assigned to rank 7 in probability density function216and counter242associated with rank 7 in number of counters256assigned to rank 2. Cache management process202continues reflecting number of counters256across axis258to form probability density function until all counters242in number of counters256are reflected.

Once probability density function216is generated, probability density function216is applied to cache228for period266. Period266follows period210. For example, if period210is amount of time212, and amount of time212is 1 second, period266is amount of time212of 1 second that follows period210. In some illustrative embodiments, probability density function216is applied to portion268of cache228. In such illustrative embodiments, the cache management process continues to monitor portion230during period266while applying probability density function216to portion268and/or other portions of cache228during period266.

Applying probability density function216means that each time thread224accesses data in portion268, cache management process202generates random number218. Random number218is weighted using probability density function216. In other words, random number218is more likely to be a number for which probability density function has a higher value than a number for which probability density function has a lower value. For example, if probability density function216contains rank 1 with a value of 20 and rank 2 with a value of 10, random number218is twice as likely to be rank 1 than rank 2.

Cache management process202assigns a rank to the requested data in portion268. For example, if cache228is a 2-way associative cache and random number218is 2, the rank of the data in portion268is set to 2. In other words, the rank is set to least recently accessed data254. In this example, if thread224requests data not presently stored in portion268, the data is overwritten because the data holds the rank of least recently accessed data254.

In another illustrative example, thread224requests data already present in portion268. In such an example, cache management process202generates random number218. Random number218is weighted using probability density function216. The rank of the data already present in portion268is then set to the value of random number218. In other words, the rank of the data is updated in response to being accessed by thread224.

For example, cache228may contain additional portions230. In such illustrative embodiments, probability density function216may be applied to the other portions of cache228while cache management process202monitors accesses by thread224in portion230. Additionally probability density function216may be generated for each thread224in number of threads222. Thus, when data234is stored in portion230after being requested, rank236associated with data234is set according to probability density function216for whichever thread224in number of threads222that requested data234.

Turning now toFIG. 3, an illustration of a cache is depicted in accordance with an illustrative embodiment. Cache300may be an example implementation of cache228inFIG. 2. In this illustrative embodiment, cache300contains tag arrays318, reach bits320, data arrays322, probability density functions302-308, and counters310-316.

Tag arrays318are arrays of values that indicate the memory addresses for the data stored in data arrays322. When data in the cache is requested by a thread, a particular address in memory may be included in the request. A cache controller may search tag arrays318or a portion of tag arrays318for the address in the request. If the address is located in tag arrays318, the corresponding entry in data arrays322is returned to the thread. Thus, data arrays322are arrays that contain data from memory or another cache. The memory addresses from which the data in data arrays322was copied are stored in the corresponding locations in tag arrays318.

In this illustrative example, cache lines324are example implementations of portion230and/or subset of cache sets232inFIG. 2. A cache management process generates a probability density function for each thread, based on accesses to the data in cache300by the thread. In one illustrative example, cache lines324comprise approximately 5% of the cache lines in cache300. Cache lines324implement a least recently used replacement policy, such as least recently used cache replacement policy248.

In these examples, a cache management process generates probability density function302based on accesses by thread0, probability density function304based on accesses by thread1, probability density function306based on accesses by thread2, and probability density function308based on accesses by thread3to cache lines324. Probability density functions302-308may each be an array of values with a size equal to the number of ways in cache300. Probability density functions302-308may be stored, for example, in a static random access memory (SRAM).

Counters310-316are each arrays that contain values representative of the cache access behavior with respect to cache lines324for a particular thread. Counters310-316may be set to contain zeroes at the beginning of a particular period. More specifically, counter310is an array containing values representing the accesses of cache lines324by thread0. In one illustrative embodiment, the cache management process increments the value in the location within counter310that represents the rank of the data accessed by thread0at the time of the access.

In another illustrative embodiment, the cache management process increments a value within counter310at the time data in cache lines324is replaced. The value within counter310that is incremented is stored in the location within counter310that represents the reach of the data being replaced. The reach of the data being replaced is the highest rank held by the data prior to being accessed by thread0. The highest rank is an example of highest rank244fromFIG. 2.

The reach of the data may be stored in reach bits320. In this illustrative embodiment, reach bits320comprise an array of values the same size as data array322for a particular cache set in cache sets324. In other words, in an 8-way associative cache, reach bits320may be an array of size 8. The reach bits may be stored in a static random access memory (SRAM). The static random memory may be located within cache300or outside cache300.

For example, assume cache300is an 8-way associative cache. The rank of a first data is 1 when the data holds the rank of most recently accessed data. The rank of the first data is 8 when the first data is the least recently accessed data in one of cache sets324. In this example, the first data is stored in the one of cache sets324with the rank of 1. Assume two other data are then stored in the particular cache set in cache sets324. After the two other data are stored in the particular cache set, the rank of the first data is 3. In this example, the first is then accessed by the thread that requested the first data. The process detects the access of the first and sets the highest rank of the first data to 3 in the position within reach bits320corresponding to the location of the first data within data array322.

Likewise, counter312is an array containing values representing the accesses of cache lines324by thread1, counter314is an array containing values representing the accesses of cache lines324by thread2, counter316is an array containing values representing the accesses of cache lines324by thread2, and counter318is an array containing values representing the accesses of cache lines324by thread4.

Turning now toFIG. 4, an illustration of a graph representing a number of accesses for each rank is depicted in accordance with an illustrative embodiment. The graph may be representative of each counter242in number of counters256. The accesses may be accesses of cache228by thread224inFIG. 2.

Graph400represents a number of accesses for each rank, such as rank240, by a particular thread in an 8-way associative cache. Graph400is representative of an illustrative embodiment in which a cache management process increments the counter associated with a rank each time the particular rank is accessed by a particular thread. Rank axis402is a horizontal axis that represents the rank held by data accessed by the thread at the time the data is accessed. Number of accesses axis404is a vertical axis representing the number of accesses of data with the particular rank for the thread.

In this illustrative example, bar406represents the number of accesses of data in the cache that had rank 1 at the time the data was accessed by the thread. Bar406indicates that approximately 2,600,000 accesses of data with rank 1 were recorded for the thread. Bar408represents the number of accesses of data in the cache that had rank 2 at the time the data was accessed by the thread. Bar408indicates that approximately 3,000,000 accesses of data with rank 2 were recorded for the thread.

Bar410represents the number of accesses of data in the cache that had rank 3 at the time the data was accessed by the thread. Bar410indicates that approximately 1,750,000 accesses of data with rank 3 were recorded for the thread. Bar412represents the number of accesses of data in the cache that had rank 4 at the time the data was accessed by the thread. Bar412indicates that approximately 800,000 accesses of data with rank 4 were recorded for the thread.

Bar414represents the number of accesses of data in the cache that had rank 5 at the time the data was accessed by the thread. Bar414indicates that less than 400,000 accesses of data with rank 5 were recorded for the thread. Bar416represents the number of accesses of data in the cache that had rank 6 at the time the data was accessed by the thread. Bar416indicates that approximately 250,000 accesses of data with rank 6 were recorded for the thread.

Bar418represents the number of accesses of data in the cache that had rank 7 at the time the data was accessed by the thread. Bar418indicates that approximately 100,000 accesses of data with rank 7 were recorded for the thread. Bar420represents the number of accesses of data in the cache that had rank 8 at the time the data was accessed by the thread. Bar420indicates that approximately 100,000 accesses of data with rank 8 were recorded for the thread.

Bar422represents the number of requests by the thread for data that was not present in the cache at the time of the request. In this illustrative example, bar422is indicated as rank 9 because the maximum rank in the 8-way cache is 8. Bar422may be an example representation of counter226inFIG. 2. Bar422indicates that more than 3,000,000 accesses of data not present in the cache were recorded for the thread. In this illustrative example, bars406-422indicate that the thread frequently accesses the same data several times repeatedly or substantially repeatedly, and then infrequently accesses the data until it is no longer stored in the cache.

Turning now toFIGS. 5-7, an example of cache management for a number of threads is depicted in accordance with an illustrative embodiment.

With specificity toFIG. 5, a number of ranks are depicted in accordance with an illustrative embodiment. Number of ranks500may be an example implementation of number of ranks246inFIG. 2. Number of ranks500may be set by a cache management process, such as cache management process202, in a cache management environment, such as cache management environment200. In this illustrative embodiment, number of ranks500ranks data in an 8-way associative cache. However, any suitable number of ways may be in the cache.

Rank502is designated as rank 1. In this illustrative embodiment, rank502is assigned to data that is the most recently accessed data in the portion of the cache represented by number of ranks500. The most recently accessed data is an example implementation of most recently accessed data252inFIG. 2. In an illustrative embodiment, rank502is assigned to data that was most recently copied from memory and stored in the portion of the cache.

Rank504is designated rank 2 and represents the next most recently accessed data in the portion of the cache represented by number of ranks500. The rank of data with rank502is set to rank504when other data is copied from memory into the cache. Likewise, rank506represents rank 3 and the next most recently accessed data in the portion of the cache after rank504, rank508represents rank 4 and the next most recently accessed data in the portion of the cache after rank506, rank510represents rank 5 and the next most recently accessed data in the portion of the cache after rank508, rank512represents rank 6 and the next most recently accessed data in the portion of the cache after rank61, rank514represents rank 7 and the next most recently accessed data in the portion of the cache after rank512, and rank516represents rank 8 and the next most recently accessed data in the portion of the cache after rank514.

Replacement518is a result of data holding rank516and other data being copied from memory and stored in the cache. That is, once data is the least recently accessed data and additional data is stored in the cache, data holding rank516is overwritten in replacement518.

Access520represents an access in the portion of the cache of the data holding rank506. An access may be a read operation, a write operation, or a read and a write operation. The data holding rank506is then assigned rank502to represent that the data is the most recently accessed data in the portion of the cache. The ranks of data in the portion of the cache with a rank closer to rank502than the data holding rank506are set one rank closer to rank516. For example, data holding rank502is assigned rank504. Access524is an additional access of data holding rank506like access520. Likewise, access522represents an access in the portion of the cache of the data holding rank512. The data holding rank512is then assigned rank502and the ranks of data in the portion of the cache with a rank closer to rank502than the data holding rank506are set one rank closer to rank516.

Turning now toFIG. 6, an illustration of a number of counters is depicted in accordance with an illustrative embodiment. Number of counters602is an example implementation of number of counters256inFIG. 2. Number of counters602may be incremented by a cache management process, such as cache management environment200.

Number of counters602comprises a counter for each rank in number of ranks500. In other words, column 1 in number of counters602represents rank502, column 2 in number of counters602represents rank504, and so on. Rank 9 in number of counters602represents a cache miss. In other words, rank 9 in number of counters602represents a request for data by the thread that was not present in the cache at the time of the request.

In this illustrative example, number of counters602is set to zero at the beginning of each period. The period is an example implementation of period210ofFIG. 2. In these examples, the period consists of time t1604, time t2606, time t3608, time t4610, and time t5612.

In this illustrative example, assume first data is requested by the thread at time t1604and that the first data is not present in the cache. The first data is stored in the cache and assigned rank502. Because the first data was not present in the cache at the time of the request, the counter for rank 9 in number of counters602is incremented to 1. The value of the counter is represented by bar614.

Assume that at time t2606, second data presently stored in the portion of the cache with rank506is requested by the thread. The second data is reassigned rank502and the counter for the rank of the third data at the time of the request is incremented. Reassigning the rank of the second data to rank502is represented by access520. Because the second data was present in the cache at the time of the request, the counter for rank 3 in number of counters602is incremented to 1. The value of the counter is represented by bar616. The rank of the first data is changed from rank502to rank504.

Assume that at time t3608, third data presently stored in the portion of the cache with rank512is requested by the thread. The third data is reassigned rank502and the counter for the rank of the third data at the time of the request is incremented. Reassigning the rank of the third data to rank502is represented by access522. In other words, because the third data was present in the cache at the time of the request, the counter for rank6in number of counters602is incremented to 1. The value of the counter is represented by bar618. The rank of the first data is changed from rank504to rank506. The rank of the second data is changed from rank502to rank504.

Assume that at time t4610, fourth data presently stored in the portion of the cache with rank506is requested by the thread. The fourth data is reassigned rank502and the counter for the rank of the fourth data at the time of the request is incremented. Reassigning the rank of the third data to rank502is represented by access524. In other words, because the fourth data was present in the cache at the time of the request, the counter for rank 3 in the number of counters602is incremented to 2. The value of the counter is represented by bar616. The rank of the first data is changed from rank506to rank508. The rank of the second data is changed from rank504to rank506. The rank of the third data is changed from rank502to rank504.

Assume that at time t5612, fifth data not presently stored in the portion of the cache is requested by the thread. Also assume that the portion of the cache has no empty data positions. Because the portion of the cache has no empty data positions, data in the portion of the cache is replaced. The data presently holding rank516is replaced in replacement518. The fifth data is then stored in the cache by overwriting the data holding rank516. The fifth data is assigned rank502and the counter for cache misses is incremented because fifth data was not stored in the cache at the time of the request. In this illustrative example, cache misses are represented in number of counters at rank 9. The counter for rank 9 in number of counters602is incremented to 2. The value of the counter is represented by bar614. The rank of the first data is changed from rank508to rank510. The rank of the second data is changed from rank506to rank508. The rank of the third data is changed from rank504to rank506. The rank of the fourth data is changed from rank502to rank504.

With specificity toFIG. 7, an illustration of a second number of counters is illustrated in accordance with an illustrative embodiment. Number of counters702is an example implementation of number of counters256inFIG. 2. Number of counters may be incremented by a cache management process, such as cache management environment200.

Number of counters702comprises a counter for each rank in number of ranks500. In other words, column 1 in number of counters702represents rank502, column 2 in number of counters702represents rank504, and so on. A counter in number of counters702are incremented when data is replaced in the portion of the cache ranked by number of ranks500. The counter in number of counters702that is incremented is the counter representing the highest rank in the portion of the cache held by the data prior to being accessed by the thread. For example, data stored in the cache and accessed again when the data holds rank506would be assigned a highest rank of 3.

However, in this illustrative embodiment, rank 9 in number of counters702represents data that was not assigned a highest rank. In other words, rank 9 in number of counters702represents data that was stored in the cache as a result of a request from a thread and replaced in the cache without being accessed again by the thread.

In this illustrative example, number of counters702is set to zero at the beginning of each period. The period is an example implementation of period210inFIG. 2. In these examples, the period consists of time t1604, time t2606, time t3608, time t4610, and time t5612.

In this illustrative example, assume first data is requested by the thread at time t1604and that the first data is not present in the cache. The first data is stored in the cache and assigned rank502. No counters are incremented because no data was replaced in the portion of the cache.

Assume that at time t2606, second data presently stored in the portion of the cache with rank506is requested by the thread. The second data is reassigned rank502. Reassigning the rank of the second data to rank502is represented by access520. No counters are incremented because no data was replaced in the portion of the cache. The rank of the first data is changed from rank502to rank504.

Assume that at time t3608, third data presently stored in the portion of the cache with rank512is requested by the thread. The third data is reassigned rank502. Reassigning the rank of the third data to rank502is represented by access522. No counters are incremented because no data was replaced in the portion of the cache. The rank of the first data is changed from rank504to rank506. The rank of the second data is changed from rank502to rank504.

Assume that at time t4610, fourth data presently stored in the portion of the cache with rank506is requested by the thread. The fourth data is reassigned rank502. Reassigning the rank of the third data to rank502is represented by access624. No counters are incremented because no data was replaced in the portion of the cache. The rank of the first data is changed from rank506to rank508. The rank of the second data is changed from rank504to rank506. The rank of the third data is changed from rank502to rank504.

Assume that at time t5612, fifth data not presently stored in the portion of the cache is requested by the thread. Also assume that the portion of the cache has no empty data positions at the time the fifth data is requested. Because the portion of the cache has no empty data positions, data in the portion of the cache is replaced. The data presently holding rank516is replaced in replacement518. The fifth data is then stored in the cache by overwriting the data holding rank516.

The counter in number of counters702representing the highest rank held by the data being replaced prior to being accessed by the thread is incremented. In this illustrative example, assume the data was accessed by the thread once when the rank held by the data was rank512, but the data was not accessed while it was in rank514or516. Thus, the counter associated with rank 6 is incremented to 1. Bar704represents the value of 1 for the counter representing rank 6.

The fifth data is assigned rank502. The rank of the first data is changed from rank508to rank510. The rank of the second data is changed from rank506to rank508. The rank of the third data is changed from rank504to rank506. The rank of the fourth data is changed from rank502to rank504.

Turning now toFIG. 8, a flowchart of a process for managing a cache is depicted in accordance with an illustrative embodiment. The process may be performed by cache management process202in cache management environment200inFIG. 2.

The process begins by identifying a probability of a future request for data to be stored in a portion of the cache by a thread for each of the number of threads to form a number of probabilities (step802). The probability is a likelihood that a thread requests data, such as data234inFIG. 2, after the data is already stored in a portion of the cache. In other words, probability is the likelihood that the thread reuses data that is stored in the cache.

The process then determines whether a future request was received from the thread in the number of threads (step804). The future request may be in a period subsequent to the period during which operation802was performed. In other words, if the measurement period is 900 cache accesses, operation804may be performed once the 900 cache accesses have occurred. If the process determines that the future request for the data was not received from the thread in the number of threads, the process terminates.

If the process determines that the future request for the data was received from the thread in the number of threads at step804, the process stores the data with a rank in a number of ranks in the portion of the cache, wherein the rank is selected using the probability in the number of probabilities for the thread (operation806). Selecting the rank using the probability may be performed by generating a random number weighted by a probability density function that was generated from the probability for the thread. The process terminates thereafter.

Turning now toFIG. 9, a flowchart of a process for identifying a probability of a future request for data to be stored in a portion of the cache by a thread for each of the number of threads to form a number of probabilities is depicted in accordance with an illustrative embodiment. The process may be performed by cache management process202in cache management environment200inFIG. 2. The process is an example implementation of operation802fromFIG. 8.

The process begins by waiting for a thread to access a portion of the cache (step902). The portion may be a subset of the cache sets in the cache. The process then determines whether the access in the portion of the cache was a cache hit (step904). In other words, the process determines whether the data requested by the thread was present in the portion of the cache. If the process determines that the access in the portion of the cache was a cache hit, the process increments a counter associated with the thread and the rank presently held by the requested data (step906). For example, if the cache is an 8-way associative cache and the data requested by the thread is present in the cache with order of access rank 3, the process increments the counter associated with the particular thread and rank 3. The process then proceeds to step910.

If the process determines that the access in the portion of the cache was not a cache hit at step904, the process increments a counter associated with cache misses for the thread (step908). A cache miss is an event that occurs when data requested by the thread is not present in the cache. The data may have to be loaded from main memory and stored in the cache. In these illustrative examples, the counter associated with cache misses is considered to be associated with the rank above the maximum rank. For example, in an S-way associative cache where rank 1 is most recently accessed data and rank 8 is least recently accessed data, the counter associated with cache misses may be considered to be associated with rank 9.

The process then determines whether a period has elapsed (step910). The period may be a period of time or a number of cache accesses. If the process determines that the period has not elapsed, the process returns to step902. If the process determines that the period has elapsed, the process generates a probability density function for each thread (step912). The probability density function may be generated using the counters associated with the thread. In one illustrative embodiment, the probability density function is generated by reflecting the number of counters over an axis located at a midpoint in the number of counters. For example, in an 8-way associative cache, each counter is reflected over an axis at rank 4. In other words, the value of the counter associated with rank 1 becomes the value for rank 8 in the probability density function. Likewise, the value of the counter associated with rank 8 becomes the value for rank 1 in the probability density function. The process terminates thereafter.

Turning now toFIG. 10, a flowchart of a second process for identifying a probability of a future request for data to be stored in a portion of the cache by a thread for each of the number of threads to form a number of probabilities is depicted in accordance with an illustrative embodiment. The process may be performed by cache management process202in cache management environment200inFIG. 2. The process is another example implementation of step802fromFIG. 8.

The process begins by waiting for data to be replaced in the cache (step1002). The data may be an example of data238inFIG. 2. Replacing the data may comprise overwriting data stored in the cache with data from memory or another cache requested by a thread. The process then determines whether the highest rank held by the data is greater than or equal to the rank representing most recently accessed data (step1004). The highest rank may be a highest rank held by the data prior to being accessed by the thread, such as highest rank244inFIG. 2. In one illustrative embodiment, the process determines whether the data was accessed by the thread after the initial access that caused the data to be stored in the cache at step1004.

For example, assume the cache is an 8-way associative cache. The rank of a first data is 1 when the data holds the rank of most recently accessed data. The rank of the first data is 8 when the first data is the least recently accessed data in the cache set. In this example, the first data is stored in the cache set with the rank of 1. Assume two other data are then stored in the cache set. After the two other data are stored in the cache set, the rank of the first data is 3. In this example, the first is then accessed by the thread that requested the first data. The process detects the access of the first and sets the highest rank of the first data to 3.

If the process determines that the highest rank held by the data is greater than or equal to the rank representing most recently accessed data at step1004, the process increments a counter associated with the highest rank and the thread (step1006). Continuing with the previous example, assume other data is stored in the cache set until the rank of the first data becomes 8. When the rank of the first data is 8, the rank of the first data represents the least recently accessed data in the cache set. When additional data is stored in the cache set, the first data is overwritten in the cache set. The process then increments the counter associated with rank 3 and the thread. The process then proceeds to step1010.

If the process determines that the highest rank held by the data is less than the rank representing most recently accessed data at step1004, the process increments a counter associated with a rank one greater than the maximum rank and the thread (step1008). For example, assume the cache is an 8-way cache. Assume that the most recently accessed data is represented with rank 1 and the least recently accessed data is represented with rank 8. The maximum rank is 8. Thus, the counter associated with the rank one greater than the maximum rank is 9. The process increments the counter associated with the thread and rank 9.

The process then determines whether a period has elapsed (step1010). The period may be a period of time or a number of cache accesses. If the process determines that the period has not elapsed, the process returns to operation1002. If the process determines that the period has elapsed, the process generates a probability density function for each thread (operation1012). The probability density function may be generated using the counters associated with the thread. In one illustrative embodiment, the probability density function is generated by reflecting the number of counters over an axis located at a midpoint in the number of counters. For example, in an 8-way associative cache, each counter is reflected over an axis at rank 4. In other words, the value of the counter associated with rank 1 becomes the value for rank 8 in the probability density function. Likewise, the value of the counter associated with rank 8 becomes the value for rank 1 in the probability density function. The process terminates thereafter.

Turning now toFIG. 11, a flowchart of a process for storing the data with a rank in a number of ranks in the portion of the cache, wherein the rank is selected using the probability in the number of probabilities for the thread is depicted in accordance with an illustrative embodiment. The process may be performed by cache management process202in cache management environment200inFIG. 2. The process is another example implementation of operation806fromFIG. 8.

The process begins by determining whether data requested by a thread is presently stored in the cache set (step1102). In these examples, the cache set is an example implementation of portion268inFIG. 2. The cache set may be a cache set to which a probability density function is applied, such as probability density function216fromFIG. 2.

If the process determines that data requested by the thread is presently stored in the cache set, the process generates a random number weighted by the probability density function for the thread requesting the data (step1104). The random number is an example implementation of random number218inFIG. 2. The process then sets the rank of the data requested by the thread to the random number (step1106). The process then waits for another cache access (step1108). When another cache access is received at step1008, the process returns to step1102.

If the process determines that data requested by the thread is not presently stored in the cache set, the process generates a random number weighted by the probability density function (step1110). The random number is an example implementation of random number218inFIG. 2. The random number is an integer between 1 and the number of ways in the cache set. The process then stores the data in the cache and sets the rank of the data requested by the thread to the random number (step1112). The process then advances to step1108. It should be noted that the process may be terminated or interrupted by a number of events. For example, a user may terminate the process, or the process may terminate after a particular period of time. The process may also terminate if processor usage is above or below a threshold.

It should be noted that in other illustrative examples, the random number is an integer between 1 and the number of ways in the cache set+1. In such examples, when the random number has a value of the number of ways in the cache set+1, step1112is not performed. For example, assume the cache is an 8-way cache. The random number may be between 1 and 9. If the random number generated at step1110is 9, the process does not store the data in the cache.

The different illustrative embodiments allow a cache management process to manage a cache being used by a number of threads where each thread has a particular profile of cache use. The number of cache hits is improved over a cache management process that implements a least recently used replacement policy for all portions of the cache because the data requested by a thread is stored in the cache with a rank that corresponds to the probability of the thread accessing the data again. Data for a thread that reuses the same data very frequently is more frequently stored with ranks closer to most recently accessed data. On the other hand, data for a thread that accesses a lot of data only once is more frequently stored with ranks closer to least recently accessed data. Thus, there is a smaller likelihood that data for the first thread that is likely to be accessed again will be replaced by data for the second thread that is unlikely to be accessed again than under a least recently used cache replacement policy.

The different illustrative embodiments also allow a profile of cache use for a particular thread to change over time. Because the profile is generated for the thread during each period, the profile of cache use for the thread is consistent with the recent cache use of the thread.

Thus, the illustrative embodiments provide a method, a computer program product, and an apparatus for managing a cache. A probability of a future request for data to be stored in a portion of the cache by a thread is identified for each of the number of threads to form a number of probabilities. The data is stored with a rank in a number of ranks in the portion of the cache responsive to receiving the future request from the thread in the number of threads for the data. The rank is selected using the probability in the number of probabilities for the thread.