基于ＤＳＰ算法的正向设计方法学概论.doc

基于算法的正向设计方法学概论 摘要：基于DSP算法的正向设计方法学为系统芯片设计师提供重要的学术素养。本文结合图表概论正向设计方法学中的数学变换思想，一是DSP算法变换，二是相应的ULSI架构变换。研究结论是作为技术核心的DSP-ULSI最佳映射，贡献首先DSP算法变换，其次ULSI架构变换，此间始终构造把握评价函数。 航天、医疗和安全业界的问题牵引，驱动数字信号处理（DSP）走过经典与现代，奔向智能计算与实时测控的融合，进而日益增强着DSP算法的时间和空间复杂性，迫使ULSI规模的ASIC架构优化，演进为由DSP算法驱动的正向设计方法学。 我们以DSP算法驱动ULSI-ASIC架构优化的正向设计环路为背景，以4种DSP算法变换和8种ULSI基本架构为路标，概论DSP算法优化和ULSI架构优化方法。 第一节正向设计优化介绍设计思想和典型概念，包括映射评价、DSP算法和ULSI架构。 第二节DSP算法变换介绍四种算法变换中的两种，包括坐标旋转和分布计算。 第三节介绍ULSI架构变换，总结出八种典型变换方法，重点介绍其中的管线和并行。 1正向设计优化 自顶向下的正向设计，在每个阶段都要重视映射评价，设计的开始要继承一些逆向设计思维。此间每一次向下映射的贡献，首先DSP算法变换，其次ULSI架构变换。 正向设计的竞争力，首先10-20万片以上的ULSI规模ASIC的牵引，其次数学技巧的合理应用，同时要重视EDA工具的熟练使用和升级培训。 我们将DSP算法驱动ULSI-ASIC架构优化的正向设计环路概括成图1。 1.1映射评价 运作ASIC正向设计流程，其间每一次向下的阶段性设计环节，都可以概括入映射这个概念。映射的数学本质就是变换。 指导映射的评价函数的一般构造方法是：巧妙组合所映射的下一层中的关键技术指标，构造生成一个单调变化的新参数，此为评价函数。 重视以评价函数寻优的引导地位，我们用图2来概括正向设计中的关键知识模块。从图2可以清楚地看出：问题建模的作用类似大脑；算法优化的作用优于架构优化的作用；设计工程师不但应该谙熟主流正向设计工具，更应该以评价函数为基础（或者称为有色眼镜），从DSP算法切入，抓住算法A（Algorithm），直奔算法集成电路ASIC的ULSI架构优化主题。 1.2DSP算法 算法定义为将一组数据变换到另外一组数据的方法。DSP算法的基本内容是变换和滤波。其研究意义在于信息处理、识别和挖掘。 DSP典型算法：相关，卷积，滤波，运动估值（ME），离散余弦变换（DCT），矢量量化（VQ），动态规划，抽取和插值，小波，等等。 DSP算法优点：区别于模拟信号处理ASP（例，谱分析精度：模拟法为10Hz；数字法为0.01Hz），鲁棒性表现于温漂和工艺，字长控制精度，本质无误差（放大信号同时消噪）；区别于其他通用计算，需要实时吞吐率（采样率），且由数据驱动。 DSP算法运算：乘积，加法，延迟（寄存）。基本公式为积和运算：Yn=i=0maiXn-i。 DSP算法图示：四种框图包括，信号流图SFG（可转置，仅描述线性单速率DSP系统），数据流图DFG（可变换，更接近实际架构，调度并发实现至并发硬件），依赖图DG（展示并行和数据流，可变换，描述脉动阵列）；框图的图示意义是，展示并行性和数据驱动，展示时间折中和空间折中，启发探索架构选择（通过算法变换）。 DSP算法实现：CPU（单，双，多），DSP（基于一种RISC），ULSI-ASIC（由DSP算法变换映射ULSI架构变换和优化），FPGA（算法变换，可编程，中等颗粒），CPLD（可编程，大颗粒）。 DSP集成指标：空间和面积，吞吐率和钟频，功耗，量化噪声和舍入噪声。 DSP研究思路：DSP算法变换和优化，ULSI架构变换和优化，DSP算法变换与ULSI架构变换联合优化；除特别指明应用于FPGA之外，其余均聚焦服务于ULSI-ASIC优化设计。 1.3ULSI架构 ULSI架构这一概念的提法，可以认为模仿了计算机组成架构的分析理念。 ULSI架构主要描述ASIC的内部电路模块，是以怎样关联着的平面结构网络摆在管芯之中的，其形状类似于建筑物的平面图纸。 我们较早熟悉的是围绕单CPU（核）所构建的ASIC的内部平面网络。 我们应该熟悉的是ASIC内部网络必须是和谐的，包括数据流、控制流和关键存储体的良性互动。 未来将面临的是由二维架构升格为三维架构。 2DSP算法变换 各种DSP算法的本质是积和（SoP）公式变形，构造方法是系数缩放、变量扩增、变量平移、积和扩增、积和映射以及各种方法的组合等等。例如，自相关（麻省理工，1951年）基于变量平移和变量扩增。 林林点点的快速DSP算法，借助于公式和数学定理进行化简和逼近，分解要点是基于子运算、重复性、规律性和并行性，热衷于以和代积。例如，FFT算法（CooleyandTukey，1965年）巧妙利用了DFT变换中旋转因子W的周期性和对称性。 揭示DSP算法锤炼设计和ULSI集成架构实现之间的关系，认真分析特定算法的内在特征（并行性、模块性和信号流机制），构造评价函数，灵巧尝试算法变换，寻优DSP算法使之并行化、模块化和层次化，降低其时间和空间复杂度，从而提速降耗。此间的典型数学技巧已概括入表1。 2.1坐标旋转 1956年至1971年，采用坐标旋转的算法得到开发和统一。该算法的基础是在直角坐标（1619年，笛卡尔）和极坐标（1691年，伯努利）中做坐标旋转，根据被计算函数的特点选取两种坐标系之一。坐标变换发明者本人的研究声音是：在变换过的坐标系中，某些特殊函数的运算得以强力简化。 坐标旋转算法对应的架构，只需加法、移位和迭代等基本操作，无需乘除运算。DSP算法基于坐标旋转易于组合出创新架构。 2.2分布计算 概念：分布计算（Croisier，1973年）是算法变换优化的经典范例，用于设计矢量乘法元架构。 方法：矢量经由二进制编码，内积重新排序与混合，基于查找表（LUT）实现与乘数无关，结果使乘法运算“分布”成读ROM且加权累加。 用途：卷积和DCT的实现。 如果说地位重要的DSP算法变换，其数学技巧具有发散的性质，那么，ULSI架构优化的变换技巧则有规律可循。 3ULSI架构优化 实际需求的DSP的吞吐率（采样率）与计算能力及性能之间存在两条鸿沟，基于架构（包括可重构）是重要解决方案。因此，DSP算法变形（逼近）优化在先，然后直接或组合映射ULSI架构。评价标准可参考ULSI架构全局模型的三要素：网络几何结构G，处理单元F，网络定时T。 优秀的DSP算法适配到合理的ULSI架构，是创新过程，通用法则急需总结。应特别注意：DSP算法得以ULSI实现的有效性，决定于算法内部数据流的复杂性。 已知DSP算法，基于DSP积、和的元架构，设计ULSI系列高层次架构的方法，可概论为以下8种，其特点列于表2。 3.1管线（流水线） 意义：缩短关键路径，提速降耗；管线即流水线。 本质：时间并行处理，方法是流水线锁存器插入SFG的前馈割集。 缺点：对非递归网络，增加了锁存器数目和系统时延；流水的多时钟风格因时钟歪斜而异化。 改进：一是采用波流水线，减少流水级数，但不增加锁存器数目；另一为异步流水，基于握手信号通信而无全局同步。 3.2并行 意义：缩短关键路径，提速降耗。 本质：空间并行处理方法，复制原始串行硬件，构造并入并出系统。 特点：其一，并行与流水线互为对偶，二者都挖掘计算的并发性，一为并行，另一为交替（同步或异步）；其二，并行和流水的降耗思路：降低电源电压，以提高采样速度换取功耗降低。 4结论讨论 DSP算法起源于17世纪的有限差分、数值积分和数值差值等经典算法。 DSP算法一般是积和项的叠加繁衍。DSP算法是一种粘合剂，将“数字汇聚”粘合在一起。 从DSP算法映射到ULSI架构，是集成电路正向设计中极其重要的研究课题之一。 针对算法的计算核积和项，分兵两路展开研究：一是通过编程，使算法适应冯诺伊曼结构或哈佛结构的既有CPU或DSP（数字信号处理器）；另一是改变ULSI架构来使之适合算法面向算法的专用处理器阵列设计，而ULSI（或3D-SOC）的规则布线要求，需要算法结构化对称化，以便分解为并行计算。 源于工程实践的算法具有多样性的特点，必须改造算法为：有规律、重复且并行，如此才能最高速硬件化实现该算法；对于复杂算法，只好运用组合的非常规架构来映射实现。其中，并行是藏在处理核内的加速器！ 区别于通用处理器，当ASIC是可能达到算法性能指标的唯一选择时，成本因素则降为第二位，必须面向算法研制专用处理器阵列。为降低专用ULSI的成本壁垒，专用处理器基于逻辑元件和寄存器的特定架构组合与连接，在牺牲一定可编程灵活性的代价下，特定内核的处理速度可大幅度提高（例如：提速1至2个数量级），避免了因灵活性而付出的硬件开销；与软件实现相比，专用硬件实现更小巧，更高速，更低耗。 当专用硬件的性能比现有处理器高10倍以上时，业界才愿意去设计ASIC；越来越复杂的ASIC设计