Research On High-level Synthesis Algorithm And The Comparison Of Two Sequential Synthesis Theories In EDA

With the development of science and technology, IC(integrated circuit) is striding for the SOC(System on a chip)stage, and it is in GSI stage now. Tools for test, emulation and simulation, such as VHDL language, have been developed for the design of IC. However, there are still many problems of theory and technology unresolved in this process. Based on this consideration, this paper investigates two important parts of EDA-high level synthesis and logic synthesis, by combining computational complexity theory. Two conclusions and two algorithms are given in this paper.Just as this paper points out, most problems about combination and sequential optimization are in fact NP-complete, so, it's impossible to find a general algorithm to solve all the problem presently. So, many researchers present heuristic algorithms to solve the problems, but no one provides a framework to find a heuristic framework to systematically analyze these algorithms.By inheriting from works done by others, we introduce Turing machine model, which is of most importance to the computational complexity theory, high level synthesis and logic synthesis. We also discuss such concepts as P and NP, approximate algorithm performance, and ascribe problems of high-level synthesis to combinational problem. For typical problems in high-level synthesis, we point out its maximum optimum.Further, we study the algorithm of interconnect unit in high level synthesis, and formulate the allocation of interconnect unit in this paper. By basing on analyzing the model of data path connection diagram, we provide a sequence of definition about data path niter-connect diagram, and then present an IU-Allocation algorithm. By utilizing this algorithm, we did an experiment about autocorrelation data circuit of linear forecast system and analyzed the tune complexity of the algorithm.Also, we introduce the concept and application of data path synthesis, andpresent an data path synthesis algorithm based on evolutionary computation. By combining extant heuristic algorithm and evolutionary algorithm, it can intelligently search relative bigger space. At the same time, this paper discusses how to reduce hardware resources and compress execution time when we use these algorithms to schedule or allocate classical differential equation and optimize data paths. The simulation experiments imply that it can effectively improve the quality of high-level synthesis.We also focus on the comparison of two important theories-Boolean process and TBF. Both theories are developed from Boolean function in order to systematically deal with logic and tuning problems. The most important difference between the two theories is that Boolean process still use Boolean domain while TBF still adopt the old system except that it introduced the time variable. Also this paper studies the complexity of Boolean process in dealing with path sensitization and find that the tune complexity is exponential.At last, we give a survey of logic synthesis and an overview about the source and development of OBDD, and also introduce the status quo of OBDD minimization.Further, we formulated exact OBDD minimization in algorithms, heuristic OBDD minimization algorithms, fast OBDD minimization algorithms OBDD minimization using don't care sets and related concepts.