Back to search

North Dakota State University

Refinementbased Verification of Elastic Pipelined System with Early Evaluation

Abstract

dc:description.abstract

This thesis presents a formal verification procedure to check correctness of the synchronous elastic pipelined system that incorporates early evaluation against its synchronous parent system. Note that the goal of the verification procedure is not to establish the correctness of the algorithm for synthesizing elastic circuits, but instead, to find bugs and formally prove the correctness of elasticized designs with early evaluation. Dataflow through elastic architectures is complicated by the insertion of any number of elastic buffers in any place in the design. Elastic token-flow diagrams are introduced, which are used to track the flow of data in elastic architectures. We provide a method to construct such diagrams. The thesis also develops a highly automated and systematic procedure based on elastic token-flow diagrams that compute functions that map states of elastic systems to states of the synchronous parent systems. Such functions, known as refinement maps, are used to compare behaviors of elastic and synchronous systems and hence prove their equivalence. The effectiveness of this method is demonstrated by verifying 8 synchronous elastic pipelined processor models with early evaluation.

Degree

thesis:*
Grantor dc:publisher
North Dakota State University
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cai, Yangwei

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • NDSU policy 190.6.2

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10365/33769

Chain of custody

source
Harvested from
North Dakota State University
Base URL
library.ndsu.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Cai, Yangwei. Refinementbased Verification of Elastic Pipelined System with Early Evaluation. North Dakota State University, 2010. https://hdl.handle.net/10365/33769