Scalable sampling methodology for logic simulation: Reduced-Ordered Monte Carlo

Monte Carlo (MC) simulation plays a key role in EDA as the gold standard against which heuristics are measured. It is also an important stand-alone technique for statistics-based tasks like power estimation and reliability analysis. Accurate simulation requires large sample sets and long runtimes, which can be hard to achieve with conventional MC. We propose an approach called Reduced-Ordered Monte Carlo (ROMC), which improves simulation efficiency, while still producing accurate results. ROMC takes advantage of the (partial) redundancy inherent in digital signals. It prioritizes input signals based on their observability at the outputs, and combines inputs based on a compatibility property that enables them to share samples. Experimental results are presented which demonstrate that the ROMC methodology can decrease simulation runtime by several orders of magnitude.