Overview
Public references list multiple people named David Dill, including David L. Dill, an American computer scientist. In the supplied technical evidence, the relevant context is the Burch-Dill approach to formal microprocessor verification, cited by a 2018 Carnegie Mellon report on verifying pipelined Y86-64 processors with UCLID5. [Name ambiguity; Burch-Dill basis]
Burch-Dill verification context
The cited report frames formal microprocessor verification as proving that a pipelined implementation faithfully implements the sequential semantics of an Instruction Set Architecture (ISA). An ISA model describes architectural state such as registers, the program counter, and memory, and gives the sequential effect of each instruction. Pipelined processors overlap multiple instructions, so verification must show that every possible instruction sequence produces the same result as a purely sequential ISA implementation. [ISA verification context]
According to the report, the key ideas used in its UCLID5 verification effort are based on work described by Burch and Dill in 1994. The main requirement of that approach is to prove the existence of an abstraction function, α, that maps microprocessor states to architectural states and is maintained by each processor cycle. [Burch-Dill abstraction requirement]
Abstraction by flushing the pipeline
The report identifies Burch and Dill’s key contribution as showing that the abstraction function can be computed automatically by symbolically simulating the microprocessor while instructions are flushed out of the pipeline. The abstraction maps a pipeline state to the architectural state obtained after all partially executed instructions in the pipeline have completed. [Automatic abstraction by flushing]
For a single-issue microprocessor, the verification task is presented as an equivalence check between two symbolic simulations: one in which the pipeline is flushed and then one ISA instruction is executed, and another in which the pipeline executes one normal cycle and is then flushed. The report calls this verification style correspondence checking. [Correspondence checking]
Simulation structure
In the UCLID5 presentation, correspondence checking compares two sequences from the same arbitrary initial pipeline state P₀:
- σₐ: initialize PIPE, perform one PIPE step, flush for n steps, and save the resulting architectural projection as Sᵃ.
- σᵦ: initialize PIPE, flush for n steps, transfer architectural state to SEQ, save S₀ᵦ, execute one SEQ step, and save S₁ᵦ.
The resulting values correspond to Sᵃ = α(Pipe(P₀)), S₀ᵦ = α(P₀), and S₁ᵦ = Seq(α(P₀)). The correspondence condition is Sᵃ = S₁ᵦ or Sᵃ = S₀ᵦ for any possible initial pipeline state. The first case represents a PIPE cycle whose fetched instruction eventually completes and matches the SEQ step; the second covers a cycle with no architectural effect, such as a stall or an instruction canceled after a mispredicted branch. [UCLID5 sequence structure]
Term-level modeling
The report contrasts the Burch-Dill method with earlier automated hardware-verification work that often required precise bit-level models, which limited the size and complexity of verifiable systems. It states that Burch and Dill demonstrated the value of data abstraction through term-level modeling, where data values are treated as symbolic terms and units such as instruction decoders and ALUs may be modeled as uninterpreted functions. These abstractions allow the verifier to focus on pipeline control logic. [Term-level modeling]
Safety and liveness limitation
The report characterizes Burch-Dill verification as proving a safety property: every processor cycle has an effect consistent with some number of ISA-model steps, including k = 0 where no program progress occurs. It also notes a limitation: a deadlocked processor, or even a device that does nothing, can pass this safety check. Therefore, liveness must also be verified to rule out states in which the processor never makes progress. [Safety and liveness]