Search papers, labs, and topics across Lattice.
TRACE is an innovative framework designed to enhance the efficiency of formal verification for complex arithmetic circuits by integrating advanced traversal strategies and proof efficiency techniques. It addresses the computational bottleneck associated with verifying arithmetic primitives, such as multiplication and addition, by allowing for flexible analysis of memory usage and verification time across various circuit types. Experimental results demonstrate that TRACE successfully verified previously unverifiable circuits, marking a significant advancement in the capabilities of Symbolic Computer Algebra engines.
TRACE can verify previously unverifiable circuits, pushing the boundaries of formal hardware verification for complex arithmetic operations.
Modern hardware verification of complex circuits relies heavily on the efficiency of formal methods. For complex arithmetic circuits in particular Symbolic Computer Algebra (SCA) engines which represent pseudo-boolean functions using polynomials are crucial. As circuit complexity grows in the age of AI, verification of arithmetic primitives, including Multiplication, Addition, Multiply-Accumulate (MAC), becomes a computational bottleneck. To address this, we introduce TRACE (Traversal and Reasoning Algebraic Computing Engine), a highly efficient framework designed to investigate the intersection of traversal strategies and proof efficiency. Unlike existing SCA tools which are mainly limited to multipliers, TRACE offers a flexible framework for researchers to analyze memory usage and verification time across a wide range of arithmetic circuits (adder, multiplier and MAC). To overcome the state-explosion problem inherent in polynomial expansion, the engine incorporates advanced reduction techniques, including optimized traversal strategies, conflict removal, and polarity-based optimization for compact symbolic representations. Our experimental results show that for optimized MAC, for the first time, TRACE was able to verify previously unverifiable circuits
