# US 10,503,646 B2 · Decoupling trace data streams using cache coherence protocol data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,646 B2 - Document ID: US10503646B2 - Status: Granted - Kind: B2 - Application number: 15/872,453 - Filed: 2018-01-16 - Published: 2019-07-18 - Granted: 2019-12-10 - Earliest claimed: 2018-01-16 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Jordi Mola - Web page: https://patentgrep.com/patent/US10503646B2 ## CPC - G06F 12/084: with a shared cache - G06F 11/362: Debugging of software - G06F 11/3636: {by tracing the execution of the program} - G06F 2212/656: Address space sharing - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Decoupling trace data streams using cache coherence protocol (CCP) data. One or more trace data streams include cache activity trace data and CCP trace data relating to executing a plurality of threads. The cache activity trace data includes inter-thread data dependencies comprising dependent cache activity trace entries, which each record a corresponding memory access by a corresponding thread in reliance on traced CCP dependence between threads. The inter-thread data dependencies are removed to create independent cache activity trace data for each of the plurality of threads that enables each thread to be replayed independently. The removal includes, for each dependent cache activity trace entry (i) identifying a corresponding value of the corresponding memory access by the corresponding thread based on the traced CCP dependence between threads, and (ii) recording the corresponding value of the corresponding memory access on behalf of the corresponding thread. ## Claims ### Claim 1 A computer system, comprising: one or more processors; and one or more computer-readable media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to decouple trace data streams using cache coherence protocol (CCP) data, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following: identify, within a trace of a prior execution of an application, one or more trace data streams that log execution of a plurality of threads during the prior execution of the application, the one or more trace data streams including cache activity trace data and CCP trace data, the cache activity trace data including one or more inter-thread data dependencies comprising at least one dependent cache activity trace entry that records a memory access by a first thread to a particular memory address in reliance on CCP trace data that identifies a data dependence between the first thread and a second thread, the data dependence indicating that the first and second threads both accessed the particular memory address; and remove the one or more inter-thread data dependencies, to create independent cache activity trace data for each of the plurality of threads that enables each thread to be replayed independent of others of the plurality of threads, including, for the at least one dependent cache activity trace entry, perform at least the following: based on the CCP trace data that identifies the data dependence between the first and second threads, identify a value of the memory access by the first thread to the particular memory address, the identifying being based on identifying the value of the memory access from cache activity trace data trace data recorded for the second thread; and record the value of the memory access into a trace data stream corresponding to the first thread, the recording enabling the memory access to be replayed from the trace data stream corresponding to the first thread, independent of the cache activity trace data trace data recorded for the second thread. ### Claim 2 (depends on 1) The computer system of claim 1, wherein identifying the value of the memory access by the first thread comprises: replaying the first thread to a point of the memory access; and based on the CCP trace data that identifies the data dependence between the first and second threads, replaying the second thread to identify the value. ### Claim 3 (depends on 1) The computer system of claim 1, wherein identifying the value of the memory access by the first thread comprises: while replaying the first thread, skipping replay of the memory access; and based on the CCP trace data that identifies the data dependence between the first and threads, replaying the second thread to identify the value. ### Claim 4 (depends on 1) The computer system of claim 1, wherein identifying the value of the memory access by the first thread comprises: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying that the memory access by the first thread is dependent on a memory operation by the second thread; and identifying the value based on cache activity trace data for the second thread. ### Claim 5 (depends on 1) The computer system of claim 1, wherein removing the one or more inter-thread data dependencies includes: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying a system of inequalities expressing the one or more inter-thread data dependencies; and identifying an ordering of memory access events based on solving the system of inequalities. ### Claim 6 (depends on 1) The computer system of claim 1, wherein removing the one or more inter-thread data dependencies includes: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying a directed graph expressing the one or more inter-thread data dependencies; and identifying an ordering of memory access events based on the one or more inter-thread dependencies in the directed graph. ### Claim 7 (depends on 1) The computer system of claim 1, wherein removing the one or more inter-thread data dependencies comprises iteratively replaying one or more portions of the plurality of threads, in which each iteration includes replacing at least one dependent cache activity trace entry with an independent cache activity trace entry that stores a memory value directly. ### Claim 8 (depends on 1) The computer system of claim 1, wherein recording the value of the memory access into the trace data stream corresponding to the first thread comprises recording the value into a data packet identifies at least one of: a processing unit that executed the first thread; or a socket containing the processing unit that executed the first thread. ### Claim 9 (depends on 1) The computer system of claim 1, wherein recording the value of the memory access into the trace data stream corresponding to the first thread comprises recording the value into a data packet that is part of a data steam that is exclusive to a processing unit that executed the first thread. ### Claim 10 (depends on 1) The computer system of claim 1, wherein the cache activity trace data is based at least on a subset of processor data cache misses caused by the plurality of threads during the prior execution of the application, and wherein the CCP trace data is based at least on a subset of cache coherence state changes that occurred due to the processor data cache misses caused by the plurality of threads during the prior execution of the application. ### Claim 11 (depends on 1) The computer system of claim 1, wherein removing the one or more inter-thread data dependencies comprises resolving an ambiguity based at least in part on: replaying a first path of execution using a first starting condition; and replaying a second path of execution using a second starting condition, the first starting condition and the second starting condition being different options selected from multiple options of the ambiguity. ### Claim 12 (depends on 11) The computer system of claim 11, the first path of execution converging with the second path of execution. ### Claim 13 A method, implemented at a computer system that includes one or more processors, for decoupling trace data streams using cache coherence protocol (CCP) data, the method comprising: identifying, within a trace of a prior execution of an application, one or more trace data streams that log execution of a plurality of threads during the prior execution of the application, the one or more trace data streams including cache activity trace data and CCP trace data, the cache activity trace data including one or more inter-thread data dependencies comprising at least one dependent cache activity trace entry that records a memory access by a first thread to a particular memory address in reliance on CCP trace data that identifies a data dependence between the first thread and a second thread, the data dependence indicating that the first and second threads both accessed the particular memory address; and removing the one or more inter-thread data dependencies, to create independent cache activity trace data for each of the plurality of threads that enables each thread to be replayed independent of others of the plurality of threads, including, for the at least one dependent cache activity trace entry, perform at least the following: based on the CCP trace data that identifies the data dependence between the first and second threads, identify a value of the memory access by the first thread to the particular memory address, the identifying being based on identifying the value of the memory access from cache activity trace data trace data recorded for the second thread; and record the value of the memory access into a trace data stream corresponding to the first thread, the recording enabling the memory access to be replayed from the trace data stream corresponding to the first thread, independent of the cache activity trace data trace data recorded for the second thread. ### Claim 14 (depends on 13) The method of claim 13, wherein identifying the value of the memory access by the first thread comprises: replaying the first thread to a point of the memory access; and based on the CCP trace data that identifies the data dependence between the first and second threads, replaying the second thread to identify the value. ### Claim 15 (depends on 13) The method of claim 13, wherein identifying the value of the memory access by the first thread comprises: while replaying the first thread, skipping replay of the memory access; and based on the CCP trace data that identifies the data dependence between the first and second threads, replaying the second thread to identify the value. ### Claim 16 (depends on 13) The method of claim 13, wherein, for at least one dependent cache activity trace entry, identifying the corresponding value of the corresponding memory access by the corresponding thread comprises: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying that the memory access by the first thread is dependent on a memory operation by the second thread; and identifying the value based on cache activity trace data for the second thread. ### Claim 17 (depends on 13) The method of claim 13, wherein removing the one or more inter-thread data dependencies includes: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying a system of inequalities expressing the one or more inter-thread data dependencies; and identifying an ordering of memory access events based on solving the system of inequalities. ### Claim 18 (depends on 13) The method of claim 13, wherein removing the one or more inter-thread data dependencies includes: based on the CCP trace data that identifies the data dependence between the first and second threads, identifying a directed graph expressing the one or more inter-thread data dependencies; and identifying an ordering of memory access events based on the one or more inter-thread dependencies in the directed graph. ### Claim 19 (depends on 13) The method of claim 13, wherein removing the one or more inter-thread data dependencies comprises iteratively replaying one or more portions of the plurality of threads, in which each iteration includes replacing at least one dependent cache activity trace entry with an independent cache activity trace entry that stores a memory value directly. ### Claim 20 A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors to cause a computer system to decouple trace data streams using cache coherence protocol (CCP) data, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following: identify, within a trace of a prior execution of an application, one or more trace data streams that log execution of a plurality of threads during the prior execution of the application, the one or more trace data streams including cache activity trace data and CCP trace data, the cache activity trace data including one or more inter-thread data dependencies comprising at least one dependent cache activity trace entry that records a memory access by a first thread to a particular memory address in reliance on CCP trace data that identifies a data dependence between the first thread and a second thread, the data dependence indicating that the first and second threads both accessed the particular memory address; and remove the one or more inter-thread data dependencies, to create independent cache activity trace data for each of the plurality of threads that enables each thread to be replayed independent of others of the plurality of threads, including, for the at least one dependent cache activity trace entry, perform at least the following: based on the CCP trace data that identifies the data dependence between the first and second threads, identify a value of the memory access by the first thread to the particular memory address, the identifying being based on identifying the value of the memory access from cache activity trace data trace data recorded for the second thread; and record the value of the memory access into a trace data stream corresponding to the first thread, the recording enabling the memory access to be replayed from the trace data stream corresponding to the first thread, independent of the cache activity trace data trace data recorded for the second thread.