Introduction
In the field of computer architecture, cycle-accurate simulators serve as the primary tool for evaluating new processor designs before physical fabrication. These simulators are notoriously complex, often comprising tens of thousands of lines of hand-coded C or C++. This complexity introduces a significant verification challenge: ensuring the simulator accurately reflects the intended architectural behavior.
Traditional approaches to this problem typically fall into two extremes: error-prone manual inspection of massive trace files or mathematically rigorous formal verification. While formal verification is robust, it often requires the simulator to be built from a formal specification, which is frequently impractical for legacy or hand-coded systems. This paper proposes the Automated Verification System (AVS), a "middle ground" framework that utilizes First-Order Logic (FOL) to verify simulator outputs against architectural constraints.
The Automated Verification System (AVS)
The AVS framework shifts the focus from verifying the simulator's source code to verifying its execution traces. This decoupling allows the system to be applied to any simulator regardless of its implementation language. The AVS workflow consists of four primary stages:
- Trace Representation: The simulator generates a trace file where each event is recorded as an n-tuple. These tuples include critical data such as instruction addresses, instance counts, pipeline stages, and timestamps.
- FOL Constraint Specification: Users define the expected behavior of the architecture using First-Order Logic. For example, a constraint might specify that any instruction entering the "Decode" stage must eventually reach the "Issue" stage, provided no pipeline rollback occurs.
- Compilation: Using standard lexical and parsing tools (Flex and Bison), the AVS compiler translates these FOL statements into optimized, independent C++ programs.
- Sliding Window Execution: To manage the gigabytes of data generated by modern simulations, the generated verifier employs a sliding window technique. This approach processes segments of the trace in memory, checking for constraint violations without requiring the entire file to be loaded simultaneously.
Architectural Insights through Logic
One of the core strengths of the AVS framework is the iterative refinement of constraints. The authors observed that the act of formalizing architectural rules in FOL often reveals ambiguities in the engineer's understanding of the design. For instance, an initial constraint might fail because the engineer forgot to account for specific hardware behaviors, such as pipeline rollbacks (when a processor clears its pipeline). By updating the FOL constraints to incorporate these edge cases, engineers develop a more precise and robust definition of the hardware's intended logic. In this way, FOL acts as a high-level specification language that hides the complexity of nested loops and state management.
Results and Performance
The evaluation of AVS demonstrates that FOL is sufficiently expressive to capture a wide array of complex architectural rules, including resource limitations (e.g., not exceeding available memory ports) and intricate instruction dependencies. The sliding window mechanism proved essential for efficiency, significantly reducing the memory footprint and allowing the system to handle long-running simulations that would otherwise be computationally prohibitive. By automating the generation of checkers, AVS replaces the ad-hoc, manual scripting processes typically used in industry with a standardized, formal methodology.
Limitations and Future Work
While AVS provides a powerful tool for verification, several areas for improvement remain. The current requirement for manual window size selection can lead to missed dependencies if the window is too small; future iterations aim to automate this through temporal analysis of the constraints. Additionally, the authors are exploring "stream-mining" to further enhance performance and machine learning techniques to automatically discover constraints from known-good traces. To handle even more complex temporal relationships, the integration of Planning Domain Definition Language (PDDL) is being considered to optimize underlying search algorithms.
Summary updated