Back to search

Georgia Institute of Technology

Efficient Verification of Bit-Level Pipelined Machines Using Refinement

Abstract

dc:description.abstract

Functional verification is a critical problem facing the semiconductor industry: hardware designs are extremely complex and highly optimized, and even a single bug in deployed systems can cost more than $10 billion. We focus on the verification of pipelining, a key optimization that appears extensively in hardware systems such as microprocessors, multicore systems, and cache coherence protocols. Existing techniques for verifying pipelined machines either consume excessive amounts of time, effort, and resources, or are not applicable at the bit-level, the level of abstraction at which commercial systems are designed and functionally verified. We present a highly automated, efficient, compositional, and scalable refinement-based approach for the verification of bit-level pipelined machines. Our contributions include: (1) A complete compositional reasoning framework based on refinement. Our notion of refinement guarantees that pipelined machines satisfy the same safety and liveness properties as their instruction set architectures. In addition, our compositional framework can be used to decompose correctness proofs into smaller, more manageable pieces, leading to drastic reductions in verification times and a high-degree of scalability. (2) The development of ACL2-SMT, a verification system that integrates the popular ACL2 theorem prover (winner of the 2005 ACM Software System Award) with decision procedures. ACL2-SMT allows us to seamlessly take advantage of the two main approaches to hardware verification: theorem proving and decision procedures. (3) A proof methodology based on our compositional reasoning framework and ACL2-SMT that allows us to reduce the bit-level verification problem to a sequence of highly automated proof steps. (4) A collection of general-purpose refinement maps, functions that relate pipelined machine states to instruction set architecture states. These refinement maps provide more flexibility and lead to increased verification efficiency. The effectiveness of our approach is demonstrated by verifying various pipelined machine models, including a bit-level, Intel XScale inspired processor that implements 593 instructions and includes features such as branch prediction, precise exceptions, and predicated instruction execution.

Degree

thesis:*
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Srinivasan, Sudarshan Kumar
Advisor dc:contributor.advisor
  • Manolios, Panagiotis
Committee members dc:contributor.committeemember
  • Chatterjee, Abhijit
  • Gopalakrishnan, Ganesh
  • Lim, Sung-Kyu
  • Yalamanchili, Sudhakar

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/19815

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Srinivasan, Sudarshan Kumar. Efficient Verification of Bit-Level Pipelined Machines Using Refinement. Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/19815