正向最大匹配算法【基于ＤＳＰ算法的正向设计方法学概论】

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

航天、医疗和安全业界的问题牵引，驱动数字信号处理（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设计完成后，也作为固定的硬件平台使用（最好嵌入 适量线控/程控功能），这已成为常用的系统正向设计方法。

基于EDA工具辅助进行最佳映射时的评价函数，其变量可是：芯片面 积（单元总数和布线数量）、时间和单元利用率。映射寻优的过程，必定是带着 工艺接口思想的DSP-ULSI变换组合优化循环。

当我们完成由DSP驱动的ULSI架构正向设计旅程，驱动力的接力棒， 尚需交还应用市场的问题牵引。

作者：李文石等