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

摘要

在市场需求的推动下，数字系统的规模越来越大，逻辑功能越来越复杂。传统设计方法所能提供的设计效率渐渐无法满足设计需要，高层次综合(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 PipelineIterative Scheduler)算法，处理流水线调度问题，寻求系统数据延迟尽可能小的调度方案。该算法在调度过程中通过保证模块的剩余调度能力，从而避免资源冲突的产生；通过优先级提升和迭代过程以寻找更紧凑的调度安排。对于实际设计中可能出现的数据流图规模，ILP方法都能在很短的时间内求解出模块选择方案，HPIS算法可以在多项式时间内给出比较好的流水线调度方案。
　　4)基于本文的模块库，采用常用的数字信号处理算法作为测试样例，对本文的设计空间搜索算法进行实验测试。基于实验结果，研究分析了系统的时间约束、时钟频率对设计方案的资源代价和数据延迟的影响。
　　5)将本文的设计空间搜索方法应用于实际工程项目中一个高斯滤波器的设计，并按照本文方法给出的设计方案进行设计实现。在满足系统时间性能要求的前提下降低了系统的资源消耗。这表明本文方法对实际数字系统设计具有一定的实用价值。