# US 2015/0106567 A1 · Computer Processor Employing Cache Memory With Per-Byte Valid Bits

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106567 A1
- Document ID: US20150106567A1
- Status: Published application
- Kind: A1
- Application number: 14/515,178
- Filed: 2014-10-15
- Published: 2015-04-16
- Earliest claimed: 2013-10-15
- Assignees: Mill Computing, Inc.
- Applicants: Mill Computing, Inc.
- Inventors: Roger Rawson Godard; Arthur David Kahlich
- Web page: https://patentgrep.com/patent/US20150106567A1

## CPC

- G06F 12/1045: associated with a data cache
- G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)}
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/0893: Caches characterised by their organisation or structure
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F 12/121: using replacement algorithms
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 16/20: of structured data, e.g. relational data
- G06F 2212/1024: Latency reduction
- G06F 2212/1028: Power efficiency
- G06F 2212/283: Plural cache memories
- G06F 2212/6032: Way prediction in set-associative cache
- G06F 2212/608: Details relating to cache mapping
- G06F 2212/684: TLB miss handling
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A computer processing system with a hierarchical memory system that associates a number of valid bits for each cache line of the hierarchical memory system. The valid bits are provided for each cache line stored in a respective cache and make explicit which bytes are semantically defined and which are not for the associated given cache line. Memory requests to the cache(s) of the hierarchical memory system can include an address specifying a requested cache line as well as a mask that includes a number of bits each corresponding to a different byte of the requested cache line. The values of the bits of the byte mask indicate which bytes of the requested cache line are to be returned from the hierarchical memory system. The memory request is processed by the top level cache of the hierarchical memory system, looking for one or more valid bytes of the requested cache line corresponding to the target address of the memory request. The valid bytes of the cache line corresponding to the byte mask as stored in cache can be identified by reading out the valid bit(s) and data byte(s) stored by the cache for putative matching cache lines for those data bytes that are specified by the byte mask of the memory request, while ignoring the valid bit(s) and data byte(s) stored by the cache for putative matching cache lines for those data bytes that are not specified by the byte mask of the memory request. Extensions to shared multiprocessor systems is also described and claimed.

## Claims

### Claim 1

A computer processing system comprising:
a hierarchical memory system having at least one cache; and
a processor having execution logic that generates memory requests that are supplied to the hierarchical memory system;
wherein the at least one cache stores a plurality of cache lines as well as a plurality of valid bits for each cache line, wherein each cache line includes a plurality of data bytes, and wherein the plurality of valid bits for a given cache line correspond to the plurality of data bytes of the given cache line and provide an indication of the validity of the corresponding data bytes of the given cache line.

### Claim 2 (depends on 1)

A computer processing system according to claim 1, wherein:
the memory requests each include a cache line address that specifies a particular cache line as well as a request byte data that specifies at least one particular data byte of the cache line specified by the cache line address.

### Claim 3 (depends on 2)

A computer processing system according to claim 2, wherein:
the request byte data comprises a byte mask with a number of bits that correspond to the number of data bytes in a given cache line.

### Claim 4 (depends on 2)

A computer processing system according to claim 2, wherein:
the cache is configured to process the memory request by accessing at least one cache line stored by the cache that putatively matches the cache line address of the memory request, and processing the valid bits of the accessed cache line together with the request byte data in order to determine if the cache line stores valid data bytes specified by the request byte data while ignoring valid bits and data bytes stored by the cache for putative matching cache lines for those data bytes that are not specified by the byte mask of the memory request.

### Claim 5 (depends on 4)

A computer processing system according to claim 4, wherein:
the at least one cache is an associative structure that stores the plurality of cache lines along with a tag for each cache line; and
the at least one cache is further configured to process the memory request by comparing the tag of the cache line address of the memory request to the tag of the cache line stored by the cache that putatively matches the cache line address of the memory request.

### Claim 6 (depends on 5)

A computer processing system according to claim 5, wherein:
the at least one cache is further configured to generate a plurality of per-byte hit/miss signals based on the processing of the valid bits of the accessed cache line and the tag comparison of the tag of the accessed cache line, wherein the plurality of per-byte hit/miss signals correspond to the number of data bytes in a given cache line.

### Claim 7 (depends on 6)

A computer processing system according to claim 6, wherein:
each per-byte hit/miss signals indicates whether the cache stores a corresponding valid data byte for the cache line corresponding to the cache line address but only for those data bytes specified by the request byte data.

### Claim 8 (depends on 5)

A computer processing system according to claim 5, wherein:
the at least one cache is further configured to output valid data bytes for the cache line corresponding to the cache line address of the memory request but only for those data bytes specified by the request byte data.

### Claim 9 (depends on 5)

A computer processing system according to claim 5, wherein:
the associative structure further stores a dirty bit for each cache line; and
the cache is further configured to output the dirty bit for the cache line corresponding to the cache line address of the memory request.

### Claim 10 (depends on 5)

A computer processing system according to claim 5, wherein:
the associative structure is one of a set-associative structure with a plurality of ways and a fully-associative structure.

### Claim 11 (depends on 1)

A computer processing system according to claim 1, wherein:
the memory requests include load requests and store requests.

### Claim 12 (depends on 11)

A computer processing system according to claim 11, wherein:
the at least one cache includes at least one buffer and at least one cache array for storing cache lines;
wherein the at least one buffer stores valid data bytes for newly written cache lines as well as cache lines newly evicted from the at least one cache array.

### Claim 13 (depends on 12)

A computer processing system according to claim 12, wherein:
the at least one cache processes a store request by writing the valid data bytes provided as part of the store request to the at least one buffer and marking such data bytes as dirty.

### Claim 14 (depends on 13)

A computer processing system according to claim 13, wherein:
in the event that the at least one cache array stores valid data bytes for the cache line specified by the store request, the at least one cache further processes the store request by merging valid data bytes of the cache line as stored in the buffer with the valid data bytes stored in the at least one cache array.

### Claim 15 (depends on 13)

A computer processing system according to claim 13, wherein:
the at least one cache further processes the store request by writing valid data bytes of the cache line as stored in the buffer into the at least one cache array and marking such data bytes as clean.

### Claim 16 (depends on 13)

A computer processing system according to claim 13, wherein:
the at least one cache is further configured to lower valid data bytes of an evicted cache line marked as dirty as stored in the at least one buffer to a lower level of the hierarchical memory system.

### Claim 17 (depends on 16)

A computer processing system according to claim 16, wherein:
the lower level of the hierarchical memory system is configured to store the valid data bytes of the evicted cache line marked as dirty as lowered by the cache by overwriting any corresponding cache line or creating a new cache line and marking it dirty.

### Claim 18 (depends on 12)

A computer processing system according to claim 12, wherein:
the at least one cache is configured to process a load request by accessing both the at least one buffer and the at least one cache array to determine if either one stores valid data bytes for the cache line specified by the cache line address of the load request.

### Claim 19 (depends on 18)

A computer processing system according to claim 18, wherein:
the at least one cache further processes the load request by issuing a read request to the next lower level in the hierarchical memory system, where the read request specifies a number of data bytes for the requested cache line that missed in both the at least one buffer and the at least one cache array.

### Claim 20 (depends on 19)

A computer processing system according to claim 19, wherein:
the lower level of the hierarchical memory system is configured to hoist valid data bytes of the requested cache line as specified in the read request that hit in the lower level of the hierarchical memory system for storage in the at least one cache.

### Claim 21 (depends on 20)

A computer processing system according to claim 20, wherein:
the at least one cache is configured to carry out a byte-wide merger process with respect to the valid data bytes for a given cache line as hoisted from the lower level of the hierarchical memory system and the valid data bytes for the given cache line as stored in the at least one cache array.

### Claim 22

A shared memory multiprocessor system comprising:
a plurality of processors with a hierarchical memory system that includes at least one private cache per processor and shared memory resources;
wherein the at least one private cache of each given processor stores a plurality of cache lines as well as a plurality of valid bits for each cache line, wherein each cache line includes a plurality of data bytes, and wherein the plurality of valid bits for a given cache line correspond to the plurality of data bytes of the given cache line and provide an indication of the validity of the corresponding data bytes of the given cache line;
wherein the private caches of the hierarchical memory system are coupled to one another by an interconnect network; and
wherein the at least one private cache of each given processor is configured to carry out a cache coherence protocol that allows the private caches for different processors to hold the same cache line in modified state so long as the sets of valid bits held by the respective private caches for the different processors are disjoint with respect to one another.

### Claim 23 (depends on 22)

A shared memory multiprocessor system according to claim 22, wherein:
in processing a store request for a cache line that is not stored in a given private cache, the cache coherence protocol is configured to broadcast a message that invalidates any copy of particular data bytes of the cache line in other private caches.

### Claim 24 (depends on 23)

A shared memory multiprocessor system according to claim 23, wherein:
the message includes an address for an affected cache line and a byte mask that indicates the affected bytes of that cache line.

### Claim 25 (depends on 24)

A shared memory multiprocessor system according to claim 24, wherein:
at least one recipient cache that receives the message is configured to use the byte mask to share use of zero or more bytes of the cache line.

### Claim 26 (depends on 25)

A shared memory multiprocessor system according to claim 25, wherein:
if the byte mask of the received message refers to one or more bytes of the cache line that are disjoint from one or more valid bytes of the cache line stored in recipient cache, then the recipient cache is configured to not modify the state of the cache line.

### Claim 27 (depends on 25)

A shared memory multiprocessor system according to claim 25, wherein:
if the byte mask of the received message refers to one or more bytes of the cache line that overlap one or more valid bytes of the cache line stored in the recipient cache, then the recipient cache is configured to mark the overlapping bytes invalid in the cache line of the recipient cache.

### Claim 28 (depends on 27)

A shared memory multiprocessor system according to claim 27 wherein:
if all bytes are marked invalid in the cache line of the recipient cache, then the recipient cache is configured to change the state of the cache line to an invalid state and to clear the dirty bit for the cache line when set.
