手机版
您的当前位置: 钻爱网 > 合同 > 租赁合同 > 正向最大匹配算法【基于DSP算法的正向设计方法学概论】

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

来源:租赁合同 时间:2019-11-25 07:52:01 点击:

基于DSP算法的正向设计方法学概论

基于DSP算法的正向设计方法学概论 摘要:基于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设计完成后,也作为固定的硬件平台使用(最好嵌入 适量线控/程控功能),这已成为常用的系统正向设计方法。

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

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

作者:李文石等

推荐内容

钻爱网 www.zuanai.cn

Copyright © 2002-2018 . 钻爱网 版权所有 湘ICP备12008529号-1

Top