时间约束下数字系统的设计空间搜索方法研究

【作者】 徐峰；

【导师】 俞承芳； 汪源源；

【作者基本信息】 复旦大学 ， 电路与系统， 2010， 博士

【摘要】 在市场需求的推动下,数字系统的规模越来越大,逻辑功能越来越复杂。传统设计方法所能提供的设计效率渐渐无法满足设计需要,高层次综合(High-level Synthesis, HLS)已成为EDA(Electronic Design Automation)设计以及系统设计方法学领域的研究热点。而设计空间搜索是数字系统高层次综合中最重要的问题。在数字系统设计中,系统的时间性能通常是最重要的性能指标,它直接决定了系统是否能够满足用户的需要。因此,本文对时间约束下数字系统的设计空间搜索问题进行研究,主要研究工作包括：1)根据常用算术模块的多种设计原理,采用不同的结构、不同的流水线深度,以FPGA(Field Programmable Gate Array)为平台对这些模块进行设计实现,为本文设计空间搜索方法的研究提供实际的模块库支持。研究分析了模块的数据吞吐间隔、数据延迟、最高运行时钟频率和资源代价等属性,提出优选资源集的概念。在给定时钟频率下,通过筛选优选资源集以排除不必考虑的模块,从而缩小搜索空间。2)研究非流水系统的设计空间搜索问题。寻找在满足系统数据延时约束的条件下,系统资源代价最小的设计方案。首先提出设计空间的分层搜索方法,进而又提出调度与搜索相融合的LSBB(List Scheduling Branch and Bound)搜索算法。该算法将模块选择及模块数量的搜索与列表调度融合到一个分支定界过程中,将搜索与调度同时进行,从而使搜索树更加细化,提高了搜索速度。对于实际设计中可能出现的数据流图规模,LSBB算法都能在很短的时间内给出近似最优的设计方案。3)研究流水系统的设计空间搜索问题。考虑的是单向数据流系统,寻找在满足系统数据吞吐间隔约束的条件下,系统资源代价最小的设计方案。针对可变启动间隔的模块,对流水线调度问题进行建模和分析,得到存在完整调度方案的充分必要条件。基于这个结论,得以将模块选择问题与调度问题相分离,分别进行处理,从而降低了设计空间搜索问题的难度。采用整数线性规划(Integer Linear Programming, ILP)方法对模块选择问题进行建模并求解。提出一种混合流水的迭代调度算法,即HPIS(Hybria Pipeline Iterative Scheduler)算法,处理流水线调度问题,寻求系统数据延迟尽可能小的调度方案。该算法在调度过程中通过保证模块的剩余调度能力,从而避免资源冲突的产生；通过优先级提升和迭代过程以寻找更紧凑的调度安排。对于实际设计中可能出现的数据流图规模，ILP方法都能在很短的时间内求解出模块选择方案,HPIS算法可以在多项式时间内给出比较好的流水线调度方案。4)基于本文的模块库,采用常用的数字信号处理算法作为测试样例,对本文的设计空间搜索算法进行实验测试。基于实验结果,研究分析了系统的时间约束、时钟频率对设计方案的资源代价和数据延迟的影响。5)将本文的设计空间搜索方法应用于实际工程项目中一个高斯滤波器的设计,并按照本文方法给出的设计方案进行设计实现。在满足系统时间性能要求的前提下降低了系统的资源消耗。这表明本文方法对实际数字系统设计具有一定的实用价值。更多还原

【Abstract】 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.更多还原