US 8,713,258 B1Granted

Estimating stack distances

AssigneeGoogle Inc.

InventorRobert Cypher

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for estimating the stack distance of an access to a cache. In one aspect, a method includes determining a current estimate value of the stack distance. For each of K buckets, a minimum value and a maximum value are initialized, wherein each bucket corresponds to a range of possible fingerprint values for accesses. A first access is processed, including: determining a first fingerprint value for the first access; identifying a first bucket for the first access based on the first fingerprint value; and determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket, and in response, increasing the current estimate value and adjusting the minimum value or the maximum value for the first bucket.

Claims30

Dependent claims

A method performed by one or more data processing apparatus, the method comprising:

initializing a current estimate value for an estimate of a stack distance of a later access to an address in a cache, the current estimate value indicating an estimate of a number of accesses to the cache having unique addresses between the later access to the address and an earlier access to the address;
initializing, for each of K buckets wherein K is greater than zero, a minimum value and a maximum value for the bucket, wherein each bucket corresponds to a range of possible fingerprint values for the accesses, and wherein the minimum value for the bucket is based at least partly on a lowest fingerprint value in the range corresponding to the bucket and the maximum value for the bucket is based at least partly on a highest fingerprint value in the range corresponding to the bucket;
and
processing at least a first access between the earlier access and the later access to update the current estimate value, including:
determining a first fingerprint value for the first access;
identifying a first bucket of the K buckets for the first access based on the first fingerprint value;
determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket;
and
responsive to determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket, increasing the current estimate value and adjusting the minimum value or the maximum value for the first bucket.

6 more elements

A system comprising one or more data processing apparatus configured to perform operations comprising:

initializing a current estimate value for an estimate of a stack distance of a later access to an address in a cache, the current estimate value indicating an estimate of a number of accesses to the cache having unique addresses between the later access to the address and an earlier access to the address;
initializing, for each of K buckets wherein K is greater than zero, a minimum value and a maximum value for the bucket, wherein each bucket corresponds to a range of possible fingerprint values for the accesses, and wherein the minimum value for the bucket is based at least partly on a lowest fingerprint value in the range corresponding to the bucket and the maximum value for the bucket is based at least partly on a highest fingerprint value in the range corresponding to the bucket;
processing at least a first access between the earlier access and the later access to update the current estimate value, including:
determining a first fingerprint value for the first access;
identifying a first bucket of the K buckets for the first access based on the first fingerprint value;
determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket;
and
responsive to determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket, increasing the current estimate value and adjusting the minimum value or the maximum value for the first bucket.

5 more elements

A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

initializing a current estimate value for an estimate of a stack distance of a later access to an address in a cache, the current estimate value indicating an estimate of a number of accesses to the cache having unique addresses between the later access to the address and an earlier access to the address;
initializing, for each of K buckets wherein K is greater than zero, a minimum value and a maximum value for the bucket, wherein each bucket corresponds to a range of possible fingerprint values for the accesses, and wherein the minimum value for the bucket is based at least partly on a lowest fingerprint value in the range corresponding to the bucket and the maximum value for the bucket is based at least partly on a highest fingerprint value in the range corresponding to the bucket;
processing at least a first access between the earlier access and the later access to update the current estimate value, including:
determining a first fingerprint value for the first access;
identifying a first bucket of the K buckets for the first access based on the first fingerprint value;
determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket;
and
responsive to determining that the first fingerprint value is between the minimum value and the maximum value for the first bucket, increasing the current estimate value and adjusting the minimum value or the maximum value for the first bucket.

5 more elements

Dependencies are inferred from the claim text.