a regulated transitive reduction (rtr) for longer memory race recording
Now at VMware. Multithreaded deterministic replay has important applications in cyclic debugging, fault tolerance and intrusion analysis. Memory race recording is a key technology for multithreaded deterministic replay. In this paper, we considerably improve our previous always-on Flight Data Recorder (FDR) in four ways: Longer recording by reducing the log size growth rate to approximately one byte per thousand dynamic instructions. Lower hardware cost by reducing the cost to 24 KB per processor core. Simpler design by modifying only the cache coherence protocol, but not the cache. Broader applicability by supporting both Sequential Consistency (SC) and Total Store Order (TSO) memory consistency models (existing recorders support only SC).These improvements stem from several ideas: (1) a Regulated Transitive Reduction (RTR) recording algorithm that creates stricter and vectorizable dependencies to reduce the log growth rate; (2) a Set/LRU timestamp approximation method that better approximates timestamps of uncached memory locations to reduce the hardware cost; (3) an order-value-hybrid recording methodthat explicitly logs the value of potential SC-violating load instructions to support multiprocessor systems with TSO.
reduction memorialized race recording records multithreading replay applications debugging fault tolerance analysis technologies log paper data size approximation dynamic instruction hardware cost processor core cache coherence cache support sequential consistency consistency order model stem algorithm dependencies timestamp method locatability value multiprocessor systems determinism