Patent ID: 8843910
Filing Date: 2014-09-23
Classification: G06F

Abstract:
1. A computer-readable storage medium storing instructions that, when executed by a computing system, cause the computing system to perform operations identifying functionally distinct memory access reorderings for a multithreaded program, the operations comprising: executing the program; during execution of the program, for each of one or more selected memory locations, observing the relative times at which each thread of the program performs read accesses to the memory location and write accesses to the memory location; using the observed memory accesses by the threads to the selected memory location to maintain vector clocks for each thread and each selected memory location, the vector clocks of the selected memory locations each having a component for each thread indicating a time corresponding to the most recent state of thread that could be represented by the contents of the memory location, the vector clocks of the threads each having a component for each other thread indicating a time corresponding to the most recent state of other thread that could have been communicated to the thread, directly or indirectly, through any of the selected memory locations; identifying each instance in which, in a vector clock of a first thread, a component for a second thread advanced from a first time to a second time, wherein a time window is delineated starting at the first time and ending at the second time; for each identified instance,