Under Time Constraints, Digital System Design Space Search Method Study

Driven by the market requirement, the size of the digital system is becoming larger and larger while the logic is becoming more and more complex. The traditional design methodology seems unable to meet the design needs. High-level synthesis (HLS) is now a popular research topic in electronic design automation (EDA) and system design methodology. Design space exploration is the most important problem in high-level synthesis.In digital design, the timing performance is most important, since it affects whether the custom's requirements can be met. So we focus on the design space ex-ploration problem under time constraints. Our research work mainly includes:1) Based on various design principles of common used arithmetic modules, we build a module library to support our research work. The modules in this library are implemented on the FPGA (Field Programmable Gate Array) platform, with different structures and different pipeline depths. We study the properties of the modules, such as the data introduction interval, the delay time, the maximum frequency and the cost. We propose the concept called the optimal module set. Under a certain system frequency, only the modules in the optimal module set need be considered. So the design space that needs to explore is reduced.2) The design space exploration problem in non-pipeline systems is studied. We try to find the design scheme with the minimal cost, under the delay time constraint. A three-stage exploration method is proposed firstly. Then the List Scheduling Branch and Bound (LSBB) algorithm is proposed. In this algorithm, the exploration for module selection and module amount is combined with the list scheduling, and they are carried out concurrently. So the exploration tree is refined, and the speed of exploration is improved. For system size in practical design, the LSBB algorithm can provide near optimal design scheme in a little time.3) The design space exploration problem in pipeline systems is studied. We fo- cus on the problem in non-recursive systems and try to find the design scheme with the minimal cost, under the constraint of data introduction interval. We consider the pipeline modules with variable introduction interval and build a model for the pipeline scheduling problem. The necessary and sufficient condition for a full schedule to exist is obtained in our analysis. With this conclusion, the module selection problem and the scheduling problem could be handled respectively, so the difficulty of the whole exploration problem is reduced.We use the integer linear programming (ILP) method to solve the module selec-tion problem. The Hybria Pipeline Iterative Scheduler (HPIS) algorithm is proposed to solve the pipeline scheduling problem, which tries to find the scheduling scheme with the minimal system delay. In this algorithm, the remaining capacities of the modules are guaranteed in the scheduling procedure, so resource conflict is avoided. This algo-rithm tries to find a schedule with a small delay using the method of priority promotion and the iterative progress. For system size in practical design, the ILP method can al-ways solve the module selection problem in a little time. And the HPIS algorithm can solve the scheduling problem in polynomial time.4) Based on our module library, we take several common used digital signal pro-cessing (DSP) benchmarks for experiments. We analyze the influence of timing con-strains and system frequency on the system cost and system delay.5) We apply our method on the design of a Gaussian filter, which is a module in a practical project. And we implement the Gaussian filter according to the design scheme given by our method. The system cost is reduced while the timing constraint is met. This indicates that our method has some practical value for digital system design.