MDG tools for the verification of RTL designs

K. D. Anon, N. Boulerice, E. Cerny, Francisco Corella, M. Langevin, X. Song, Sofiène Tahar, Ying Xu, Zijian ZhouLecture Notes in Computer Science 1996 · DOI · OpenAlex

Abstract

Traditional hardware verification methods, such as Reduced Ordered Binary Decision Diagrams (ROBDDs), face significant challenges when scaling to complex Register Transfer Level (RTL) designs due to the "state explosion problem." This paper presents Multiway Decision Graphs (MDGs) and an associated suite of tools designed to address these limitations by incorporating abstract sorts and uninterpreted function symbols.

Introduction

For years, automated hardware verification relied heavily on ROBDDs. However, ROBDDs require every circuit component to be represented as Boolean variables. In complex datapaths—such as those found in modern processors—this leads to an exponential increase in the number of variables, making verification computationally infeasible. To bridge this gap, the authors propose MDGs, which allow for reasoning at a higher level of abstraction, effectively managing the complexity of large-scale RTL designs.

Methodology and System Architecture

The core innovation of this work is the Multiway Decision Graph (MDG), a data structure based on a subset of many-sorted first-order logic. Unlike ROBDDs, MDGs support abstract sorts, allowing data values to be treated as single variables rather than bit-vectors. Furthermore, uninterpreted function symbols enable the tool to treat complex operations (e.g., addition) as "black boxes," focusing on the control logic rather than implementation details.

The hardware is modeled using Abstract State Machines (ASMs), a generalization of Finite State Machines that accommodates abstract data types. The MDG toolset is organized into a layered architecture to facilitate modularity and extensibility.

The layered architecture of the MDG toolset, illustrating the hierarchy from the core package to high-level verification modules.

As shown in the architecture diagram, the system consists of three primary layers:

  1. MDG Package: The foundational layer providing basic operators such as disjunction and relational products.
  2. Utilities: A middle layer containing tools for pretty-printing and reachability analysis.
  3. Application Modules: The top layer, which implements specific verification tasks like combinational and sequential verification.

The entire suite is implemented in Quintus Prolog 3.2, leveraging its strengths in symbolic processing and logic programming.

Key Insights and Results

The use of MDGs provides several advantages over traditional Boolean-level verification:

  • Compactness: Abstract sorts allow MDGs to represent complex logic with significantly fewer nodes than ROBDDs.
  • Lifting Techniques: The authors successfully "lifted" Boolean-level techniques, such as implicit enumeration, to the abstract level (abstract implicit enumeration).
  • Functional Toolset (V1.0): The developed suite supports both combinational equivalence checking and sequential invariant checking.
  • MDG-HDL: A Prolog-style Hardware Description Language was introduced, allowing designers to specify hardware using abstract variables directly.
  • Error Tracing: The tool can generate counterexamples (traces) when an invariant is violated, aiding in the debugging process.

Discussion and Future Work

While MDGs offer a powerful alternative to ROBDDs, certain challenges remain. Because the underlying logic is first-order, reachability analysis is not guaranteed to terminate in all scenarios. The authors propose state generalization and term rewriting as potential mitigation strategies. Additionally, while Prolog is excellent for prototyping, the current implementation is less space-efficient than specialized ROBDD tools for simple finite state machines.

Future work focuses on extending the toolset to support a restricted first-order temporal logic, enabling more comprehensive model-checking capabilities beyond simple invariant checking.

Summary updated

BibTeX
@inproceedings{anon1996mdg,
  author = {K. D. Anon and N. Boulerice and E. Cerny and Francisco Corella and M. Langevin and X. Song and Sofiène Tahar and Ying Xu and Zijian Zhou},
  title = {{MDG tools for the verification of RTL designs}},
  booktitle = {Lecture Notes in Computer Science},
  year = {1996},
  doi = {10.1007/3-540-61474-5\_96},
}

Loading related content...

Figure