Skip to content
STIMSMITH

Symbolic Instruction Graphs

Technique WIKI v1 · 8/1/2026

Symbolic Instruction Graphs is a verification technique used for architectural verification of processors, introduced by Chandra, Iyengar, Jawalekar, Mullen, Nair, and Rosen in their 1994 ICCD paper. The approach enables formal reasoning about processor instruction-level behavior by representing instruction semantics symbolically, and is cited within the processor-implementation verification methodology literature as a key reference for symbolic, graph-based architectural validation.

Symbolic Instruction Graphs

Overview

Symbolic Instruction Graphs (SIGs) are a technique for the architectural verification of processors. The approach was introduced by A. K. Chandra, V. S. Iyengar, R. V. Jawalekar, M. P. Mullen, I. Nair, and B. K. Rosen in the paper Architectural Verification of Processors Using Symbolic Instruction Graphs, presented at the International Conference on Computer Design (ICCD) in October 1994 [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292]. The technique is cited as a foundational reference within the broader processor implementation verification methodology literature.

Role in Processor Verification

Within the methodology for processor implementation verification (Springer chapter, "A methodology for processor implementation verification"), Symbolic Instruction Graphs are positioned as a symbolic, graph-based approach for verifying that a processor implementation conforms to its architectural specification. The technique supports formal reasoning over instruction-level behavior, complementing other methods discussed in the same survey such as constraint-satisfaction-based test program generation, architecture validation, and symbolic model checking [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].

Related Approaches Cited Alongside SIGs

The processor verification methodology references Symbolic Instruction Graphs in the context of several complementary techniques, including:

  • Symbolic Model Checking (McMillan, Kluwer, 1993) and the SMV System (McMillan, CMU, 1992) [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].
  • Constraint Solving for Test Case Generation (Chandra and Iyengar, ICCD-92, 1992) and Constraint Satisfaction for Test Program Generation (Lewin et al., 1995) [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].
  • Architecture Validation for Processors (Ho, Han Yang, Horowitz, and Dill, ISCA 1995) [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].
  • Automatic Test Program Generation for Pipelined Processors (Iwashita, Kowatari, Nakata, and Hirose, ICCAD 1994) [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].
  • Coverage Driven Processor Bug Classification (Abarbanel, Lichtenstein, Malka, and Ur, DAC 1996) [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].

Significance

Symbolic Instruction Graphs are significant as one of the early symbolic techniques to apply graph-structured representations to architectural-level processor verification. By treating instruction semantics symbolically rather than enumerating concrete test cases, the approach enables broader coverage of architectural state and supports rigorous comparison between a specification and its implementation [chunk: f6a19b46-f399-4509-b8e4-761ab01cb292].

Key Reference

  • A. K. Chandra, V. S. Iyengar, R. V. Jawalekar, M. P. Mullen, I. Nair, B. K. Rosen, Architectural Verification of Processors Using Symbolic Instruction Graphs, Proceedings of the International Conference on Computer Design, October 1994.

LINKED ENTITIES

1 links
Architectural Verification of Processors Using Symbolic Instruction Graphs USES

CITATIONS

2 sources
2 citations
[1] Symbolic Instruction Graphs were introduced by Chandra, Iyengar, Jawalekar, Mullen, Nair, and Rosen at ICCD in October 1994. A methodology for processor implementation verification | Springer Nature Link
[2] Symbolic Instruction Graphs are cited as a symbolic, graph-based approach for architectural verification of processors within the processor implementation verification methodology. A methodology for processor implementation verification | Springer Nature Link