Dependence Graph Based Verification and Synthesis of Hardware/Software Co-Designs with SAT Related Formulation

Abstract

Program slicing is a software-analysis technique that generates System Dependence Graphs (SDGs) by which dependencies among program statements can be identified through their traversal. We have developed a program slicing tool for SpecC, a C-based system level design language for hardware/software co-designs, on top of a program slicer for C/C++. This program slicing tool can generate SDGs from any combined descriptions in C, C++, and SpecC, and can be used to analyze design descriptions for hardware/software co-designs uniformly and smoothly in all the combined descriptions. In this paper, after reviewing our program slicer that generates SDGs, we present verification and synthesis techniques for hardware/software co-designs through various analyses on SDGs and generations of SAT/ILP problems from them. For analysis and verification of the combined descriptions, we examine SDGs statically by traversing them with SAT/ILP solvers as verification engines. With this method, many static checks can be efficiently realized even if the target design descriptions are fairly large. We first present techniques for checking synchronization among concurrent processes described in SpecC through symbolic analysis on SDGs. The techniques could verify the synchronization of MPEG4 descriptions with about 48,000 lines within 10 seconds. The techniques can be applied to automatic conversions between sequential and parallel computations. One such application to automatic program serialization is presented. By using the technique for automatic program serialization, we could serialize Vocoder descriptions with about 10,000 lines in around 1 minute. As for synthesis from the combined descriptions, we present an optimal code generation method based on SAT formulation. It can generate codes for reconfigurable processors with minimum code lengths. The sizes of problems as SAT formulation range from 10,000 to 100,000 variables and 100,000 to 500,000 clauses for the largest configurations. With appropriate uses of the state-of-the-art SAT solvers and related tools, we show that fairly practical sizes of verification and synthesis problems can be solved by analyzing SDGs generated from the combined descriptions.