# US 11,907,091 B2 · Trace recording by logging influxes to an upper-layer shared cache, plus cache coherence protocol transitions among lower-layer caches > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,091 B2 - Document ID: US11907091B2 - Status: Granted - Kind: B2 - Application number: 15/898,372 - Filed: 2018-02-16 - Published: 2019-08-22 - Granted: 2024-02-20 - Earliest claimed: 2018-02-16 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Jordi Mola - Web page: https://patentgrep.com/patent/US11907091B2 ## CPC - G06F 11/3037: {where the computing system component is a memory, e.g. virtual memory, cache (accessing, addressing or allocating within memory systems or architectures G06F12/00; checking stores for correct operation G11C29/00)} - G06F 11/3466: {Performance evaluation by tracing or monitoring} - G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)} - G06F 11/3636: {by tracing the execution of the program} - G06F 12/0811: with multilevel cache hierarchies - G06F 12/0815: Cache consistency protocols - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Trace recording based on data influxes to an outer-level cache and cache coherence protocol (CCP) transitions between inner caches. Example computing device(s) include a plurality of processing units, a plurality of (N-1)-level caches, and an N-level cache that is associated with two or more of the (N-1)-level caches and that is a backing store for the two or more (N-1)-level caches. Based at least on detecting influx(es) of data to a location in the N-level cache during execution across the processing units, the computing device(s) causes the influx(es) of data to be logged. The computing device(s) also causes one or more (N-1)-level CCP transitions between the two or more (N-1)-level caches to be logged. The (N-1)-level CCP transitions result from the location being accessed by two or more of the processing units. ## Claims ### Claim 1 A computing device, comprising: a plurality of processing units; a plurality of (N-1)-level caches; an N-level cache that is associated with two or more of the plurality of (N-1)-level caches, and that is configured as a backing store for the two or more (N-1)-level caches; and control logic that includes computer-executable instructions to configure the computing device to record execution of an entity that executes parallel threads across two or more of the plurality of processing units, based on performing at least the following: based at least on detecting an influx of memory data from a particular memory location in system memory to a particular cache location in the N-level cache that results from execution of a first thread of the entity by a first of the plurality of processing units, cause the influx of memory data to the particular cache location in the N-level cache to be logged into a replayable trace of the entity; and based at least on having caused the influx of memory data to the particular cache location in the N-level cache to be logged into the replayable trace of the entity, subsequently cause one or more (N-1)-level cache coherence protocol (CCP) transitions between the two or more (N-1)-level caches to be logged into the replayable trace of the entity, the (N-1)-level CCP transitions resulting from the particular cache location being accessed by a second of the plurality of processing units based on execution of a second thread of the entity by the second of the plurality of processing units. ### Claim 2 (depends on 1) The computing device as recited in claim 1, wherein: the computing device also comprises a plurality of (N-2)-level caches, and in which each (N-1)-level cache is associated with two or more of the plurality of (N-2)-level caches, and the (N-1)-level cache is configured as a backing store for the two or more (N-2)-level caches; and the stored control logic also configures the computing device to cause one or more (N-2)-level CCP transitions between the two or more (N-2)-level caches to be logged into the replayable trace of the entity, the (N-2)-level CCP transitions resulting from the particular cache location being accessed by the two or more of the plurality of processing units. ### Claim 3 (depends on 1) The computing device as recited in claim 1, wherein the influx of memory data results from one or more cache misses on the N-level cache as a result of execution of the first thread of the entity. ### Claim 4 (depends on 1) The computing device as recited in claim 1, wherein the one or more (N-1)-level CCP transitions comprise one or more points of transition among periods of stores and periods of loads. ### Claim 5 (depends on 4) The computing device as recited in claim 4, wherein causing the one or more (N-1)-level CCP transitions to be logged comprises logging a value stored in the particular cache location at one or more of the points of transition. ### Claim 6 (depends on 1) The computing device as recited in claim 1, wherein: the computing device also comprises a buffer; and the control logic also configures the computing device to perform deferred logging into the replayable trace of the entity based on one or more one or more of: storing the influx of memory data from the particular memory location to the buffer, or storing the one or more (N-1)-level CCP transitions between the two or more (N-1)-level caches to the buffer. ### Claim 7 (depends on 1) The computing device as recited in claim 1, wherein the computing device also comprises one or more logging control bits that control whether one or more of the plurality of processing units participate in logging. ### Claim 8 (depends on 1) The computing device as recited in claim 1, wherein the control logic comprises one or more of circuitry or stored microcode. ### Claim 9 (depends on 1) The computing device as recited in claim 1, wherein at least the N-level cache includes one or more accounting bits that identify one or more of (i) whether a value at the particular cache location has been logged, or (ii) whether the value at the particular cache location should be logged. ### Claim 10 (depends on 9) The computing device as recited in claim 9, wherein the control logic also configures the computing device to set at least one accounting bit in the N-level cache based on a communication from one or more of the (N-1)-level caches. ### Claim 11 (depends on 9) The computing device as recited in claim 9, wherein the control logic also configures the computing device to use the one or more accounting bits to refrain from logging influxes of memory data resulting from speculative execution of an instruction. ### Claim 12 (depends on 1) The computing device as recited in claim 1, wherein causing the one or more (N-1)-level cache coherence protocol (CCP) transitions between the two or more (N-1)-level caches to be logged into the replayable trace of the entity comprises causing an identity of a point of the each (N-1)-level CCP transition to be logged into the replayable trace of the entity, including identifying the point of each (N-1)-level CCP transition as corresponding to one of (i) a first transition from a load CCP state of the particular cache location to a store CCP state of the particular cache location, or (ii) a second transition from the store CCP state of the particular cache location to the load CCP state of the particular cache location. ### Claim 13 (depends on 12) The computing device as recited in claim 12, wherein the load CCP state comprises at least one of an owned CCP state or a shared CCP state, and wherein the store CCP state comprises at least one of modified CCP state or an exclusive CCP state. ### Claim 14 (depends on 12) The computing device as recited in claim 12, wherein the first transition corresponds to a transition from a first period of one or more loads to a second period of one or more stores, and the second transition corresponds to a transition from a third period of one or more stores to a fourth period of one or more loads. ### Claim 15 A method for recording execution of an entity that executes parallel threads across two or more of a plurality of processing units based on memory data influxes to an outer-level cache and CCP transitions between inner caches, the method being implemented at a computing device that includes (i) the plurality of processing units, (ii) a plurality of (N-1)-level caches, and (iii) an N-level cache that is associated with two or more of the plurality of (N-1)-level caches and that is configured as a backing store for the two or more (N-1)-level caches, the method comprising: based at least on detecting an influx of memory data from a particular memory location in system memory to a particular cache location in the N-level cache that results from execution of a first thread of the entity by a first of the plurality of processing units, causing the influx of memory data to the particular cache location in the N-level cache to be logged into a replayable trace of the entity; and based at least on having caused the influx of memory data to the particular cache location in the N-level cache to be logged into the replayable trace of the entity, subsequently causing one or more (N-1)-level cache coherence protocol (CCP) transitions between the two or more (N-1)-level caches to be logged into the replayable trace of the entity, the (N-1)-level CCP transitions resulting from the particular cache location being accessed by a second of the plurality of processing units based on execution of a second thread of the entity by the second of the plurality of processing units. ### Claim 16 (depends on 15) The method of claim 15, wherein the computing device also includes (iv) a plurality of (N-2)-level caches, and in which each (N-1)-level cache is associated with two or more of the plurality of (N-2)-level caches, and the (N-1)-level cache is configured as a backing store for the two or more (N-2)-level caches, the method also comprising: causing one or more (N-2)-level CCP transitions between the two or more (N-2)-level caches to be logged into the replayable trace of the entity, the (N-2)-level CCP transitions resulting from the particular cache location being accessed by the two or more of the plurality of processing units. ### Claim 17 (depends on 15) The method of claim 15, the method also comprising causing one or more CCP transitions based on activity of a single processing unit to be logged. ### Claim 18 (depends on 15) The method of claim 15, wherein at least the N-level cache includes one or more accounting bits that identify one or more of (i) whether a value at the particular cache location has been logged, or (ii) whether the value at the particular cache location should be logged, and wherein the method further comprises setting at least one accounting bit in the N-level cache based on a communication from one or more of the (N-1)-level caches. ### Claim 19 (depends on 15) The method of claim 15, wherein at least the N-level cache includes one or more accounting bits that identify one or more of (i) whether a value at the particular cache location has been logged, or (ii) whether the value at the particular cache location should be logged, and wherein the method further comprises using the one or more accounting bits to refrain from logging influxes of memory data resulting from speculative execution of an instruction. ### Claim 20 A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by a computing device that includes (i) a plurality of processing units, (ii) a plurality of (N-1)-level caches, and (iii) an N-level cache that is associated with two or more of the plurality of (N-1)-level caches and that is configured as a backing store for the two or more (N-1)-level caches, the computer-executable instructions being executable to cause the computing device to perform at least the following as part of recording execution of an entity that executes parallel threads across two or more of the plurality of processing units: based at least on detecting an influx of memory data from a particular memory location in system memory to a particular cache location in the N-level cache that results from execution of a first thread of the entity by a first of the plurality of processing units, cause the influx of memory data to the particular cache location in the N-level cache to be logged into a replayable trace of the entity; and based at least on having caused the influx of memory data to the particular cache location in the N-level cache to be logged into the replayable trace of the entity, subsequently cause one or more (N-1)-level cache coherence protocol (CCP) transitions between the two or more (N-1)-level caches to be logged into the replayable trace of the entity, the (N-1)-level CCP transitions resulting from the particular cache location being accessed by a second of the plurality of processing units based on execution of a second thread of the entity by the second of the plurality of processing units.