This paper introduces an innovative translation validation framework designed for MLIR-based compilers, which has garnered considerable prominence in fields such as machine learning, high-performance computing and hardware design. Despite rigorous testing, compilers based on MLIR might still induce incorrect results and undefined behaviors, necessitating verification work. Our framework first takes a pair of MLIR programs as inputs and check their function signature’s compatibility before encoding them into SMT expressions. Then it uses the Z3 SMT solver to check whether the target program refines the source program. Our framework transcends the dialect limitations of past solutions, thereby providing validation support to a wider range of MLIR-based compilers. We demonstrate its effectiveness through evaluations on prominent open-source MLIR-based compilers, where we identified bugs and undefined behaviors. We further demonstrate the capability of this framework by validating two practical deep-learning accelerator designs.

Modern application-specific System-on-Chip designs include a variety of accelerator blocks that customize microcontrollers with domain-specific instruction sets and optimized microarchitectures. Unfortunately, accelerator implementations can be highly error-prone, undermining the reliability and security of the entire system. In spite of recent successes in formal methods, full verification of a complex accelerator microarchitecture is still beyond the scope of state-of-the-art formal technologies. In this paper, we address this problem through a novel methodology for incremental verification that can be tightly integrated with the design process. Our approach depends on a new foundation for microarchitecture correctness that enables viewing microarchitecture features as program transformations in a compiler design. The foundations enable designing microarchitecture features as incremental, semantics-preserving optimizations. We show how to use the foundations to develop correct-by-construction implementations of various advanced features of modern microprocessors. We demonstrate the viability of the foundations in designing correct-by-construction methodology for a superscalar microarchitectural implementation of the Versatile Tensor Accelerator.

Agile hardware design enables designers to produce new design iterations efficiently. Equivalence checking is critical in ensuring that a new design iteration conforms to its specification. In this paper, we introduce an equivalence checking framework for hardware designs represented in HalideIR. HalideIR is a popular intermediate representation in software domains such as deep learning and image processing, and it is increasingly utilized in agile hardware design. We have developed a fully automatic equivalence checking workflow seamlessly integrated with HalideIR and several optimizations that leverage the incremental nature of agile hardware design to scale equivalence checking. Evaluations of two deep learning accelerator designs show our automatic equivalence checking framework scales to hardware designs of practical sizes and detects inconsistencies that manually crafted tests have missed.

We present a scalable approach for formally verifying the correctness of the Compute Engine (CE) against its ISA (Instruction Set Architecture) specification in an FHE (Fully Homomorphic Encryption) accelerator, critical to many applications where safety and security of information is of vital importance. It combines algorithmic verification of the micro-architecture modules in the CE against their functional specifications and implementation verification of the CE hardware against its micro-architecture algorithmic specifications. The correctness of the CE is guaranteed by treating micro-architecture modules as semantic-preserving program transformations and leveraging the composability of the semantic-preserving properties well established in compiler design and verification.

Correctness must be a first principle in hardware/-software co-design, especially for security and safety critical applications. We will give an overview of our scalable approach for correctness-assured hardware/software design at behavioral level, based on formalizing microarchitecture features as program transformations in an incremental compiler design and microprocessor correctness as a refined notation of compiler correctness. We will show how our approach is applied to designing a formally verified FHE (Fully Homomorphic Encryption) accelerator.

HalideIR is a popular intermediate representation for compilers in domains such as deep learning, image processing, and hardware design. In this paper, we present an automated verification framework for HalideIR-based compiler transformations. The framework conducts verification using symbolic execution in two steps. Given a compiler transformation, our automated verification framework first uses symbolic execution to enumerate the compiler transformation's paths, and then utilizes symbolic execution to verify if the output program for each transformation path is equivalent to its source. We have successfully applied this framework to verify 46 transformations from the three most-starred HalideIR-based compilers on GitHub and detected 4 transformation bugs undetected by manually crafted unit tests.

This paper proposes a High-Level Synthesis (HLS) framework for domain-specific computing. The framework contains three key components: 1) ScaleHLS, a multi-level HLS compilation flow. Aimed to address the lack of expressiveness and hardware-dedicated representation of traditional software-oriented compilers. ScaleHLS introduces a hierarchical intermediate representation (IR) for the progressive optimization of HLS designs defined in various high-level languages. ScaleHLS consists of three levels of optimizations, including graph, loop, and directive levels, to realize an efficient compilation pipeline and generate highly-optimized domain-specific accelerators. 2) AutoScaleDSE is an automated design space exploration (DSE) engine. Real-world HLS designs often come with large design spaces that are difficult for designers to explore. Meanwhile, the connections between different components of an HLS design further complicate the design spaces. In order to address the DSE problem, AutoScaleDSE proposes a random forest classifier and a graph-driven approach to improve the accuracy of estimating the intermediate DSE results while reducing the time and computational cost. With this new approach, AutoScaleDSE can evaluate thousands of HLS design points and find the Pareto-dominating design points within a couple of hours. 3) PyTransform is a flexible pattern-driven design customization flow. Existing HLS flows demand manual code rewriting or intrusive compiler customization to conduct domain-specific optimizations, leading to unscalable or inflexible compiler solutions. PyTransform proposes a Python-based flow that enables users to define custom matching and rewriting patterns at a high level of abstraction, being able to be incorporated into the DSL compilation flow in an automatic and scalable manner. In summary, ScaleHLS, AutoScaleDSE, and PyTransform aim to address the challenges present in the compilation, DSE, and customization of existing HLS flows, respectively. With the three key components, our newly proposed HLS framework can deliver a scalable and extensible solution for designing domain-specific languages to automate and speed up the process of designing domain-specific accelerators.

The past decade has witnessed increasing adoption of high-level synthesis (HLS) to implement specialized hardware accelerators targeting either FPGAs or ASICs. However, current HLS programming models entangle algorithm specifications with hardware customization techniques, which lowers both the productivity and portability of the accelerator design. To tackle this problem, recent efforts such as HeteroCL propose to decouple algorithm definition from essential hardware customization techniques in compute, data type, and memory, increasing productivity, portability, and performance.

This article proposes a specification mining framework,FlowMiner, that automatically mines patterns from highly concurrent communication traces for system-on-chip (SoC) designs. It addresses the problem of the lack of comprehensive, accurate, and up-to-date specifications necessary to perform rigorous and thorough validation of complex SoC designs. The extracted patterns characterize how components of an SoC design communicate and coordinate with each other to realize various system functions. InFlowMiner, a set of inference rules and optimization techniques are presented to reduce mining complexity. Evaluation of this framework in several experiments shows promising results.

Concise and abstract models of system-level behaviors are invaluable in design analysis, testing, and validation. In this paper, we consider the problem of inferring models from communication traces of system-on-chip (SoC) designs. The traces capture communications among different blocks of a system design in terms of messages exchanged. The extracted models characterize the system-level communication protocols governing how blocks exchange messages, and coordinate with each other to realize various system functions. In this paper, the above problem is formulated as a constraint satisfaction problem, which is then fed to a satisfiability modulo theories (SMT) solver. The solutions returned by the SMT solver are used to extract the models that accept the input traces. In the experiments, we demonstrate the proposed approach with traces collected from a transaction-level simulation model of a multicore SoC design and a trace of a more detailed multicore SoC modeled in GEM5.

This paper presents a fuzzing framework for Unified Extensible Firmware Interface (UEFI) BIOS with the Simics virtual platform. Firmware has increasingly become an attack target as operating systems are getting more and more secure. Due to its special execution environment and the extensive interaction with hardware, UEFI firmware is difficult to test compared to user-level applications running on operating systems. Fortunately, virtual platforms are widely used to enable early software and firmware development by modeling the target hardware platform in its virtual environment before silicon arrives. Virtual platforms play a critical role in left shifting UEFI firmware validation to pre-silicon phase. We integrated the fuzzing capability into Simics virtual platform to allow users to fuzz UEFI firmware code with high-fidelity hardware models provided by Simics. We demonstrated the ability to automatically detect previously unknown bugs, and issues found only by human experts.

Reconstructing system-level behavior from silicon traces is a critical problem in post-silicon validation of System-on-Chip designs. Current industrial practice in this area is primarily manual, depending on collaborative insights of the architects, designers, and validators. This paper presents a trace analysis approach that exploits architectural models of system-level protocols to reconstruct design behavior from partially observed silicon traces in the presence of ambiguous and noisy data. The output of the approach is a set of all potential interpretations of a system's internal execution abstracted to system-level protocols. To support the trace analysis approach, a companion trace signal selection framework guided by system-level protocols is also presented, and its impacts on the complexity and accuracy of the analysis approach are discussed. That approach and the framework have been evaluated on a multi-core System-on-Chip prototype that implements a set of common industrial system-level protocols.

We consider the conflicts between requirements from security and post-silicon validation in SoC designs. Post-silicon validation requires hardware instrumentations to provide observability and controllability during on-field execution; this in turn makes the system prone to security vulnerabilities, resulting in potentially subtle security exploits. Mitigating such threats while ensuring that the system is amenable to post-silicon validation is challenging, involving close collaboration among security, validation, testing, and computer architecture teams. We examine the state of the practice in this area, the trade-offs and compromises made, and their limitations. We also discuss an emerging approach that we are contemplating to address this problem.

In current SoCs, key infrastructure capabilities are distributed across many components and involve tight software, firmware, and hardware interaction. Examples include resets, power management, security, and more. The architectural complexity of these features often results in specification errors that when found quite late in the product life cycle are very costly to fix. This means that we have to find ways to analyze the architectural specification and not only the implementation. To address these issues, we describe a framework called iPave that supports the following capabilities: (1) A common, formal system-level specification serving as a contract between different design teams; (2) Specification analysis with focus on cross-component assumptions and dependencies; and (3) A method to reuse the specification as a global checker to assure that the implementation is compliant with the specification across all validation platforms (simulation, emulation, silicon). At the front end of this framework we have an intuitive visual formalism, iFlow, which makes it easy for architects to specify system-level protocols, while at the back end we have a new logical formalism, called Logic Sequence Diagrams (LSDs), which enables formal compliance checking across different validation platforms.

This paper presents a post-silicon debug methodology that provides a means to rewind, or backspace, a chip from a known crash state using a combination of on-chip real-time data collection and off-chip formal analysis methods. A complete debug flow is presented that considers practical considerations such as area, on-chip non-determinism and signal propagation delay. This flow, along with a low-overhead breakpoint circuit, allows for state-accurate breakpointing capabilities without the need to monitor the entire state of the chip. The flow and associated hardware was tested using a hardware prototype, which consists of an OpenRISC processor instrumented with the debug hardware connected to a PC running the formal verification algorithms. Traces hundreds of cycles long were obtained using the methodology presented in this paper.

Behavioral synthesis is the compilation of an Electronic system-level (ESL) design into an RTL implementation. We present a suite of optimizations for equivalence checking of RTL generated through behavioral synthesis. The optimizations exploit the high-level structure of the ESL description to ameliorate verification complexity. Experiments on representative benchmarks indicate that the optimizations can handle equivalence checking of synthesized designs with tens of thousands of lines of RTL.

In this paper, we present a suite of optimizations targeting automatic abstraction refinement for Generalized Symbolic Trajectory Evaluation (GSTE). We optimize both model refinement and spec refinement supported by AutoGSTE: a counterexample-guided refinement loop for GSTE. Experiments on a family of benchmark circuits have shown that our optimizations lead to major efficiency improvements in verification involving abstraction refinement.

Post-silicon debug is the problem of determining what's wrong when the fabricated chip of a new design behaves incorrectly. This problem now consumes over half of the overall verification effort on large designs, and the problem is growing worse. We introduce a new paradigm for using formal analysis, augmented with some on-chip hardware support, to automatically compute error traces that lead to an observed buggy state, thereby greatly simplifying the post-silicon debug problem. Our preliminary simulation experiments demonstrate the potential of our approach: we can "backspace" hundreds of cycles from randomly selected states of some sample designs. Our preliminary architectural studies propose some possible implementations and show that the on-chip overhead can be reasonable. We conclude by surveying future research directions.

In this paper, we present AutoGSTE, a comprehensive approach to automatic abstraction refinement for generalized symbolic trajectory evaluation (GSTE). This approach addresses imprecision of GSTE's quaternary abstraction caused by underconstrained input circuit nodes, quaternary state set unions, and existentially quantified-out symbolic variables. It follows the counterexample-guided abstraction refinement framework and features an algorithm that analyzes counterexamples (symbolic error traces) generated by GSTE to identify causes of imprecision and two complementary algorithms that automate model refinement and specification refinement according to the causes identified. AutoGSTE completely eliminates false negatives due to imprecision of quaternary abstraction. Application of AutoGSTE to benchmark circuits from small to large size has demonstrated that it can quickly converge to an abstraction upon which GSTE can either verify or falsify an assertion graph efficiently.

This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis.

With the trends toward higher-level design, verification models written in software, and hardware/software codesign, it is increasingly important to verify that RTL hardware behaves correctly according to an executable software specification. In this paper, we propose a natural way to formalize a cycle-accurate software specification as an annotated control flow graph, and then we introduce a novel partitioned model-checking algorithm that exploits the annotated control flow graph. Preliminary experimental results show that our new method runs faster than standard model checking.

GSTE (Generalized Symbolic Trajectory Evaluation) is a high capacity formal verification technology that has been successfully applied to verifying complex Intel designs with tens of thousands of state elements. In this paper, we extend the use of GSTE by developing a dynamic checker that verifies a GSTE specification against a scalar simulation trace. Unlike previous approaches, both the formal checker and the dynamic checker work directly on a GSTE specification without the need for an intermediate monitor circuit. Our approach also offers a straight forward way to measure the quality (coverage) of a specification. The dynamic checker has been used in the real-life micro-processor design verification.

We address the problem of implication of assertion graphs that occur in generalized symbolic trajectory evaluation (GSTE). GSTE has demonstrated its powerful capacity in formal verification of digital systems. Assertion graphs are used for property and model specifications. We present a novel implication technique for assertion graphs. It relies on direct Boolean reasoning on each edge (and vertex) of an assertion graph, thus avoiding the reachability computation in GSTE. We have successfully applied. both model-based and language-based implications on real industrial circuits. Experimental results demonstrate the promising performance of our approach.

Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.

Symbolic trajectory evaluation (STE) is a lattice-based model checking technology that uses a form of symbolic simulation. It offers an alternative to 'classical' symbolic model checking that, within its domain of applicability, often is much easier to use and much less sensitive to state explosion. The limitation of STE, however, is that it can only express and verify properties over finite time intervals. In this paper, we present a generalized STE (GSTE) that extends STE style model checking to properties over infinite time intervals. We further strengthen the power of GSTE by introducing a form of backward symbolic simulation. It can be shown that these extensions together with a notion of fairness give STE the power to verify all /spl omega/-regular properties. The generalization also gives one the power to choose and adjust the level of model abstraction in a verification effort. We shall use a large-scale industrial memory design to demonstrate the strength and practicality of GSTE.

Generalized Symbolic Trajectory Evaluation (GSTE) [17, 18, 19] is a very significant extension of STE that has the power to verify all ω-regular properties but at the same time preserves the benefits of the original STE [16]. It also extends the symbolic quaternary model used by STE to support seamless model refinement for efficiency and accuracy trade-off in GSTE model checking. In this paper, we present a case study on FIFO verification to illustrate the strength of GSTE and demonstrate its methodology in specifying and verifying large scale designs.

Symbolic trajectory evaluation (STE) is a lattice-based model checking technology based on a form of symbolic simulation. It offers an alternative to 'classical' symbolic model checking that, within its domain of applicability, often is much easier to use and much less sensitive to state explosion. The limitation of STE, however, is that it can only express and verify properties over finite time intervals. In this paper, we present a generalized STE (GSTE) that extends STE style model checking to properties over infinite time intervals. We further strengthen the power of GSTE by introducing a form of backward symbolic simulation. It can be shown that these extensions, together with a notion of fairness, give STE the power to verify all /spl omega/-regular properties. We use a large-scale industrial memory design to demonstrate the power and practicality of GSTE.

In this paper w e presen t a lazy model checking approach aimed at improving the efficiency and capacity of symbolic model checking. The lazy approach dynamically computes an abstraction of a circuit model for each pre-image computation based on the partial result leading to the computation. A t the heart of the approach is a lazy algorithm for transition relation building and pre-image computation. A variable minimization heuristic is then proposed to maximize the benefit of the lazy algorithm in iterative fix-point computations. This approach shows greater promise in complexit y reduction than the cone of influence approach.