（电路与系统专业论文）基于并行多处理单元的数字信号处理器设计研究[电路与系统专业优秀论文].pdf

摘要 随着数字化时代的到来，数字信号的处理技术成为电子信息与计算机科学领 域研究的前沿与重点之一。相对于模拟信号，数字信号具有高可靠性、易存储、高 处理精度、高灵活性、易加密等优点。因而使得数字信号处理技术在通信、多媒 体、仪器仪表、工业控制、医学图像、军事、航空航天等领域都得到了广泛的应 用。数字信号处理器是数字信号处理技术实现的关键之一，拥有广阔且发展迅速的 商业前景。此外，数字信号处理器的设计又横跨电子科学、计算机科学、信号处理 学与微电子科学等多个学科领域，具有很强的学术价值。 近年来，数字信号处理器的设计研究日益成为i c 设计方面的热点之一。主要 的研究工作集中在两方面：一是通用数字信号处理器的研究；另一个是专用可编程 信号处理器的研究。前者灵活性强、开发周期短，但性能较差。后者灵活性较差且 开发周期较长，但对特定算法有很好的性能。本文借鉴了s o c 设计方法中i p 核复 用的思想，参考文献 z p g + 0 0 1 的提出的结构，介绍了一种基于并行多处理单元的 数字信号处理器架构平台。这种结构既具备很好的可扩展性又能充分利用数字信号 处理算法中的内在并行性，在灵活性、开发周期与性能等方面取得了更好的平衡。 本文以该体系架构为基础，开展了一些设计与研究工作。 本文的工作主要包括： ( 1 ) 、对现有的数字信号处理器结构进行总结，并根据数字信号处理算法的要求对 各种体系结构进行比较； ( 2 ) 、介绍基于并行多处理单元的数字信号处理器的体系结构，并对其特点进行归 纳； ( 3 1 、详细叙述一种基于并行多处理单元的数字信号处理器实例的v l s i 设计，并对 其中的关键模块采用基于自动综合工具的评估方法进行了优化设计； ( 4 ) 、研究了常用数字信号处理核心算法在该架构平台上的实现方法，并与t i 公司 的商用d s p 进行性能比较，以此来验证平台的高效性和可扩展性； ( 5 ) 、对基于该平台的可测性设计进行了探讨。 总之，本文希望将算法级、体系结构级和电路级的研究相结合，对基于并行 多处理单元这一新的处理器架构的数字信号处理器实现与研究做出一定的贡献。 关键词：数字信号处理器，数字信号处理，多处理器，超大规模集成电路 中图分类号：t n 4 7 a b s 仃a c t w h e nt h ed i g i t a le r ai sc o m i n g ，d i g i t a ls i g n a lp r o c e s s i n g t e c h n i q u ei sb e c o m i n g t h e r e s e a r c hf r o n t i e ra n d e m p h a s i s o fe l e c l r o n i ci n f o r m a t i o n a n d c o m p u t e r s c i e n c e c o m p a r e dw i t ha n a l o gs i g n a l ，d i g i t a ls i g n a li sm o r es t a b l e ，e a s i e rt os t o r e ，a b l et ob e p r o c e s s e dm o r ea c c u r a t e l y , m o r f e x i b l ea n de a s i e rt ob ee n c r y p t e d a 1 it h o s es t r o n g p o i n t s m a k ed i g i t a l s i g n a lw i d e l yu s e di n a r e a so ft e l e c o m m u n i c a t i o n ，m u l t i m e d i a ， i n s t n n n e n t s ，i n d u s t r i a lc o n t r o l ，m e d i c a li m a g e ，m i l i t a r ya n da v i a t i o n ，e t c a so n eo ft h e k e yf a c t o r so fd i g i t a ls i g n a lp m c e s s i n gt e c h n i q u e ，d i g i t a ls i g n a lp r o c e s s o rh a sw i d ea n d r a p i d l yb o o m i n gc o m m e r c i a lp r o s p e c t b e s i d e s ，d i g i t a ls i g n a lp r o c e s s o rd e s i g nc r o s s e s t h ef i e l d so fe l e c t r o n i cs c i e n c e ，c o m p u t e r s c i e n c e ，s i g n a lp r o c e s s i n ga n dm i c r o e l e c t r o n i c s ， w h i c hd e m o n s t r a t e si t sa c a d e m i c s i g n i f i c a n c e t h e s ey e a r s ，r e s e a r c hi nd i g i t a l s i g n a lp r o c e s s o rd e s i g ni sb e c o m i n go n eo ft h e p o p u l a ra s p e c t so fi cd e s i g n m a i nr e s e a r c hw o r kc o n c e n t r a t e so nt w oa s p e c t s ：o n ei s g e n e r a ld i g i t a ls i g n a lp r o c e s s o r ，t h eo t h e ri sa p p l i c a t i o ns p e c i f i e dp r o g r a m m a b l ed i g i t a l s i g n a lp r o c e s s o r ，t h ef o i t n e ri sm o r ef l e x i b l ea n de a s i e rf o ra p p l i c a t i o nd e v e l o p m e n t , b u t i th a sr e l a t i v e l yp o o r e rp e r f o r m a n c e 1 1 1 el a t t e rh a sb e t t e rp e r f o r m a n c ei ns o m es p e c i f i e d a l g o r i t h m s ，b u ti ts u f f c r sf r o mp o o r e rf l e x i b i l i t ya n dl o n g e rt e r r ao fd e v e l o p m e n t i nt h i s d i s s e r t a t i o n ，w ea d o p tt h em e t h o do fi pm u s i n gi n s o cd e s i g na n dr e f e rt ot h e a r c h i t e c t u r ei n z p ( 斗0 0 1t od e v e l o pad i g i u ds i g n a lp r o c e s s o rp l a t f o r l nb a s e do n p a r a l l e l m u i r i p l ep r o c e s s i n gu n i t s t h i sa r c h i t e c t u r en o to n l yp o s s e s s e sg o o de x p a n s i b i l i t y ，b u t a l s ow e l le x p l o r e st h ep a r a l l e l i s mo f d i g i t a ls i g n a lp r o c e s s i n ga l g o r i t h m s ，w h i c hc a nm a k e g o o dt r a d e o f f sa m o n gf l e x i b i l i t y ，t e r mo fd e v e l o p m e n ta n dp e r f o r m a n c e ，b a s e do nt h i s p l a t f o r m ，w eh a v el a u n c h e ds o m e r e s e a r c ha n dd e v e l o p m e n tw o r k t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ec o n c l u d e da sf o l l o w s ： l 、s u m m a r i z e st h e p r e s e n t a r c h i t e c t n r e sf o r d i g i t a ls i g n a lp r o c e s s o r s a n dm a k e s c o m p a r i s o na c c o r d i n g t ot h er e q u e s t so f c o m m o n s i g n a lp r o c e s s i n ga l g o r i t h m s 2 、i n t r o d u c e st h ea r c h i t e c t u r eb a s e do n p a r a l l e lm u l t i p l ep r o c e s s i n g u n i t sa n d s u m m a r i z e si t sc h a r a c t e r i s t i c s 3 1i n t r o d u c e sv l s ii m p l e m e n t a t i o no fa nd i g i t a ls i g n a lp r o c e s s o ri n s t a n c eb a s e do nt h i s a r c h i t e c t l l r ei nd e t a i l a d o p t st h ee v a l u a t i o nm e t h o db a s e do na u t o m a t i cs y n t h e s i s t o o l st oo b t a i no p t i m i z e dd e s i g n ，e s p e c i a l l yf o rs o m ek e ym o d u l e s 4 ) d o e s r e s e a r c ho n a p p l i c a t i o no f c o m m o n d i g i t a ls i g n a lp r o c e s s i n ga l g o r i t h m so n t h i s a r c h i t e c t u r ea n dn l a k e sc o m p a r i s o nw i t hac o m m e r t i a ld s pf r o mt it od e m o n s t r a t e t h ee f f i c i e n c ya n de x p a n s i b i l i t yo f t h ep l a t f o r m 5 、m a k e sd i s c u s s i o no nd f ri s s u e so f t h ep l a t f o r m i ns u m m a r y , w e h o p et oc o m b i n et h er e s e a r c ho fa l g o r i t h ml e v e l ，a r c h i t e c t u r el e v e l a n d l o g i cl e v e lt om a k e s o m ec o n t r i b u t i o n st ot h er e s e a r c ha n di m p l e m e n t a t i o no f p a r a l l e l m u l t i p l ep r o c e s s i n g u n i t sb a s e da r c h i t e c t u r e an e wa r c h i t e c t u r eo f d s p i n d e xt e r m s ：d i g i t a ls i g n a lp r o c e s s o r , d i g i t a ls i g n a lp r o c e s s i n g ，m u l t i p l ep r o c e s s o r v l s i i i 第一章引言 第一章引言 1 1 数字信号处理概述 早在上个世纪初期，信号处理的数学理论已经发展到了比较成熟的阶段。 但是由于数字电子计算机的技术尚未成熟，信号处理的对象主要集中在模拟信 号领域。直至1 9 6 5 年，c o o l e r 和t u k e y 在文献 c t 6 5 1 中提出了快速傅立叶变换 ( f f t ) 算法，降低了离散傅立叶变换所需的乘法次数，使数字信号的实时处理成 为可能。此后，随着集成电路和数字计算机技术的不断发展，硬件数字信号处 理的能力在不断增强，数字信号处理技术的应用领域也在不断地扩大，其优越 性也得到了更好的体现。 与模拟信号相比，数字信号具有更高的可靠性和抗干扰能力，使其更利于 传送和保存；此外，数字信号更便于由计算机进行处理，并且能达到较高的处 理精度；其次，数字系统比模拟系统具有更高的灵活性；最后，数字信号可以 方便地进行差错控制以及信息加密。正是由于这些优点，数字信号处理技术在 通信、多媒体、仪器仪表、工业控制、医学图像、军事、航空航天等领域都得 到了广泛的应用。同时，用于数字信号处理的硬件数字信号处理器的市场 也在飞速发展：1 9 9 9 年，市场规模为4 4 亿美元；到2 0 0 1 年己超过7 0 亿美元； 预计到2 0 0 4 年，市场规模将达1 9 0 亿美元。可见，数字信号处理技术的研究具 有重要的意义。 一个典型的数字信号处理系统的框图如图1 1 所示。外界的模拟信号一般 通过模数转换器( a d c ) 转化为数字信号，数字信号由专门的硬件进行处理( 一 般包括滤波、变换、编码、解码等工作) ，处理完的数字信号可以存储起来或通 过数模转换器( d a c ) 转化为模拟信号输出。从图中可以看出，负责进行数字信 号处理的硬件( 即数字信号处理器，以下简称d s p ) 在整个数字信号处理系统 中起着非常关键的作用，它很大程度上决定了系统的功能、处理速度、处理能 力、功耗、软硬件复杂度等。所以d s p 的研究对整个数字信号处理技术的实现 与发展都有着举足轻重的作用。 鹣未处理的孰已处理的 模数转陋数字信号处理( d s p )吆数模转 换器f 滤波、变换、编 换器 ( a d c )r 码、解码等) 广 0 9 a c ) 图1 - 1典型数字信号处理系统的框图 第一章引言 d s p 可以通过全硬件来实现，也就是由一个专用的电路来进行数字信号处 理的运算。这种实现方法相当直接，并且具有很好的性能。由于一个电路只针 对某一种d s p 算法，因而可以在最大程度上进行有针对性的电路优化，从而利 用很少的硬件资源来获得优越的性能。当然，这种实现方法的灵活性很差，实 现某种算法的电路完全无法应用在另一种算法中，甚至仅仅改变一下算法的参 数都需要对电路进行重新设计。另外，这种实现方法的开发周期较长，开发的 难度也比较大。 与硬件实现相对应的是通过通用可编程d s p 以及其上的软件来实现d s p 算 法。这种实现方法具有很大的灵活性，只需要改变软件就可以实现各种d s p 算 法，从而也缩短了系统的开发时间，降低了开发难度。也正是由于可编程d s p 的通用性，无法针对特定的算法进行优化，影响了这种实现方式的性能。另外， 它对通用d s p 的设计提出了很高的挑战，怎样兼顾可编程的通用性和d s p 算 法的特殊性是设计时考虑的主要问题之一。一个典型的通用d s p 一般具有如表 1 - 1 所示的一些特性，以满足其在数字信号处理领域的特殊要求 s h i 0 0 l 。 表1 1典型d s p 算法对d s p 处理器的要求及相应的实现方法 要求实现 算术运算 单周期高速乘加并行阵列乘法器 条件执行条件判断逻辑 饱和溢出处理专用处理硬件 并行移位桶形移位器 内存存取 单周期与运算并行的多重存取多重总线结构及专用地址生成器 特殊的寻址模式环形队列以及比特反转寻址硬件等 并行地址指针调整专用地址自加器 程序控制 无额外代价的( z e r o o v e r h e a d ) 循环专用循环硬件 高效的子程序调用及中断响应硬件堆栈等 另外一种方案是两者的折中，通过设计一个专用指令集的可编程d s p 来获 得有针对性的优化效果和一定的可编程性。该方案的主要问题在于无论在硬件 结构设计还是指令集设计时都必须以d s p 算法为核心进行软硬件的综合考虑， 必须采取软硬件协同设计的策略，这又增加了设计工作的复杂度和工作量。 以上三种实现方案在灵活性和性能上的权衡可以用图1 2 来形象地表示。 其中，通用d s p 的灵活性最好；全硬件实现在性能上的优势最为突出；专用可 编程d s p 则是两者的折中。 第一章引言 能 灵活性 图1 2三种类型d s p 在灵活性和性能方面的比较 1 2d s p 发展的新要求 近年来，随着各种技术的进一步发展，系统对d s p 又有了新的要求。首先， 数字通信与多媒体等应用领域的发展要求d s p 具有更强大的处理能力。例如第 三代无线通信、高清晰度电视、实时三维图像加速、医学信息处理等都包含大 量复杂的d s p 运算，需要强大的d s p 进行支持。d s p 运算能力提高的主要途 径是提高其并行处理的能力。所以如何充分开发d s p 算法的并行性，如何尽可 能利用d s p 算法的内在并行性成为当前d s p 发展的一项挑战。 其次，便携式移动应用对低功耗的追求也成为影响d s p 发展的一项重要因 素。所以如何在保持d s p 强大的处理能力同时又尽可能地降低功耗以满足当前 移动应用的需求是设计者将面i 临的又一难题。 随着集成电路技术与产业化的不断发展，高性能与低功耗已经不再是设计 者追求的唯一目标，功能的专用化( c u s t o m i z a t i o n ) 和推向市场的时机 ( t i m e t o m a r k e t ) 已成为行业发展的重要动力，也成为设计者必须考虑的重要目 标 b c 0 2 。功能专用化要求针对不同的应用设计专门的电路，从而可以显著提 高特定应用下的性能。由于d s p 一般应用在数据处理集中的领域，因而这一点 显得尤为重要。比如对于b d t i 的f i r 滤波测试程序，i n t e lp e n t i u mh i 处理器 需要的周期数是t i5 4 系列d s p 的两倍，是t i6 2 系列d s p 的四倍 e b 0 0 。说 明对于d s p 算法而言，功能专用化的设计比简单地提高主频更为重要。但是， 功能的专用化不可避免地造成设计开发的难度增大，从而影响到开发周期，特 别是当d s p 应用领域不断扩大、其应用的划分也更为细致以后更是如此。s o c 设计方法的发展为这个问题提供了可行的解决方案。s o c 设计方法的关键在于 i p 核的复用技术，设计并已通过验证的口核可以重复利用在多个s o c 系统中。 这样，芯片设计者就可以通过利用先前已设计好的i p 核来构建自己的芯片，从 1 b d t i 全称是b e r k e l e y d e s i g n t e c h n o l o g y , i n c ，它是一个独立从事d s p 处理器分析与d s p 软件优化的公 司。 第一章引言 而加快设计周期。并且通过这样的设计方法，设计者还可以通过选择合适的i p 核来达到功能专用化的目的。所以，怎样借鉴s o c 的设计方法，有效地解决功 能专用性和设计周期之间地矛盾将成为今后d s p 设计方法的一个突破方向。 另外，在一个典型的d s p 应用系统中，除了一块d s p 芯片用于数据处理 外一般还包括一块通用微处理器芯片用于系统控制和输入输出控制等工作。随 着集成电路技术的不断发展，芯片集成度的不断提高，为微处理器与d s p 的单 芯片解决方案的实现提供了可能。若微处理器与d s p 可以通过单一芯片实现， 那么将极大地简化整个应用系统的复杂度、降低应用系统的成本、提高应用系 统的可靠性。 1 3 前人的工作 很多年以来，d s p 处理器都是计算机科学、电子科学和半导体科学研究的 重点之一，实验室成果与商业成果都层出不穷。 在通用d s p 领域，发展方向主要集中在提高性能和降低功耗。历史上第一 款成功的商用d s p 是德州仪器公司( t i ) 于1 9 8 2 年推出的t m s 3 2 0 1 0 。当时这个 型号的d s p 仅仅依靠哈佛( h a r v a r d ) 总线和专用的硬件乘法器就取得了在数字信 号处理领域极大的成功，是第一代d s p 的代表。在8 0 年代后期出现的第二代 d s p 被称为传统型d s p ，其代表是1 9 8 7 年m o t o r o l a 公司推出的d s p 5 6 0 x x 系 列。这一代d s p 在继承了上一代产品的优点外，广泛采用了乘一累加单元( m a c ) 来取代原来的乘法单元。同时，d s p 中还是用了专用的地址生成单元来产生数 据读写的地址。这一代d s p 一般可以在3 3 m h z 得时钟主频上获得1 6 5 m i p s 的 性能。9 0 年代中期出现了增强传统型的d s p ( 第三代d s p ) ，t i 的t m s 3 2 0 c 5 x 系列成为这一代d s p 的代表。第三代d s p 除了在硬件资源、总线带宽等方面 较前两代d s p 有了较大提高外，其重要的特点是“单指令多数据( s i m d ) ”技术 的应用。第三代d s p 可以工作在超过5 0 m h z 的时钟频率上，并且可以达到每 个时钟周期一条指令的执行效率。9 0 年代末、本世纪初又出现了以单周期多指 令为主要特征的第四代d s p 。在这一代d s p 中，超长指令字( v l r w ) 的技术得 到了较多的应用。由于这一代d s p 突破了过去的每个周期一条指令的限制，使 其性能有了飞速的提高。这四代d s p 的性能比较如图l 一3 所示，图中纵轴表示 的是b d t i 测试程序得分。 第一章引言 图i - 3四代通用d s p 的性能比较 正如上文所述，专用可编程d s p 因为在功能专用性和开发周期上取得了较 好的折中，从而获得了研究者极大的重视。尤其随着数字通信和多媒体技术的 飞速发展，该领域也涌现了大量的研究成果，如文献 c t c + 0 1 k i i + 0 1 k i h + 0 1 】 f l l c + 0 1 等。但是现有的专用可编程d s p 普遍采用的是传统通用d s p 的体系 结构，缺乏一个一致的设计平台，不同d s p 之间的功能模块也难以复用，从而 造成每一个不同的d s p 都需要从头设计，增加了设计难度和设计时间。 除此以外，有很多d s p 的解决方案致力于将d s p 功能与微处理器功能集 成在一个芯片中实现。其中包括d s p 增强功能的m c u 以及m c u 加d s p 协处 理器的解决方案。a r m 公司的a r m i o e 系列m c u 以及i n f i n e o n 公司的t r i c o r e 是d s p 增强功能m c u 的代表。a r m i o e 系列通过减少乘法指令的周期数、增 加对双寄存器读写的支持、增加溢出保护等措施来提供对d s p 功能的支持；而 t r i c o r e 系列则是通过在r i s c 体系结构中引入s i m d 技术实现了d s p 功能。另 外，如a r m 公司的p i c c o l o 协处理器则是协处理器解决方案的代表。 近年来，随着f p g a 技术的发展，它在数字信号处理领域的独特优势体现 出来，从而基于f p g a 的可重配置体系结构作为一种新的计算模型得到了广泛 的研究与应用。在大学实验室里已开发出不少这样的处理器。如由b r i 曲a n l y o u n g 大学开发的d s p r l g n 9 9 及加州大学伯克利分校开发的g a r p 处理器 h a u 0 0 等。文献【z p g + o o 】则将带有异构处理单元的可重配置体系结构运用在低 功耗的d s p 设计中，他们使用o 2 5 1 t m ，六层金属的c m o s 工艺，在1 v 的工 作电压、4 0 m h z 的主频下取得了1 8 m w 的功耗。 第一章引言 1 4 本文的工作 本文在参考文献 z p g + 0 0 的基础上，提出了基于并行多处理单元的d s p 结构( m p u - d s p ) 。将在考察各d s p 算法共同特性的基础上对各种已有的d s p 解决方案进行比较，并且详细介绍m p u d s p 的结构和优势。本文将重点挖掘 该结构在并行性和灵活性方面的优势。更重要的是，我们借鉴了s o c 的设计方 法学，将m p u d s p 设计为一个开放的、灵活的、可扩展的d s p 平台：系统中 的处理单元是重复利用的p 核，可以根据实际应用的需求来增减系统中处理单 元的数量或者改变处理单元的功能来提高系统性能。同时，它还可以有效地降 低系统地开发时间，在性能与开发周期方面获得更好的折中。 在此基础上，本文将介绍一种基于m p u d s p 的实例的实现细节，并且讨 论在该d s p 平台上如何有效地实现常用的d s p 算法核心以及如何利用平台的 扩展性提高算法的执行效率。此外，本文还将对m p u d s p 的可测性设计和 些尚待进一步研究的方向进行论述。本文的主要目的在于突出m p u d s p 作为 一个开放的、可扩展的平台的特点及优越性，并力图将体系结构级的研究与算 法级和电路级的研究进行充分的结合。 本文共分为九个章节。第一章即引言。第二章从d s p 算法入手，由算法引 导出对硬件的讨论：首先对d s p 算法的特点进行归纳总结，在此基础上得出 d s p 算法对硬件的要求，最后对现有的几种硬件实现方案进行逐一讨论。第三 章从体系结构的角度介绍了m p u d s p 平台及其特点，并与第二章介绍的几种 实现方案进行了比较。第四和第五两章具体介绍一个基于m p u d s p 结构的d s p 处理器( d s p l 6 ) 的v l s i 实现。其中，第四章侧重于功能和结构级的设计，而第 五章则重点介绍关键模块的电路级设计。第六章则是关于d s p 算法如何在 d s p l 6 上实现的讨论，并与在t i 公司的t m s 3 2 0 c 5 4 x 系列d s p 上的实现结果 进行比较，突出d s p l 6 的性能。第七章主要介绍如何利用m p u d s p 平台的可 扩展性来提高d s p 算法的执行效率。第八章是关于可测性设计方面的一些考虑。 最后一章将有一个总结，并且对一些未完成的工作和将来的研究方向进行展望。 第二章d s p 算法的特点及各种实现结构 第二章d s p 算法的特点及各种实现结构 这一章首先通过理论分析和算法举例介绍d s p 算法一些重要的共有特性， 在为d s p 算法设计计算结构时，这些特性和要求必须得到充分的重视。然后， 在此基础上总结一下各种d s p 的实现结构，并且分析各自的优缺点。 2 1 d s p 算法的主要特点 2 l 1 实时性的特点 般来说，d s p 算法的输入数据都是一些具有固定采样率的信号，并且也 要求系统以一定的速率对输入信号进行处理，作出响应。所以，d s p 算法般 都有实时性的要求。例如c d 中的数字音频信号的采样率是4 4 1 k h z ，典型数 字视频信号的采样率范围在十到几十m h z 左右。此外，数字通信领域和实时控 制领域的应用对d s p 的实时性也有很高的要求。 d s p 算法实时性的特点对它的计算硬件的要求主要体现在三个方面。首 先，硬件必须具有足够的处理能力和处理速度来适应特定速率的输入数据流， 并且能够在可接受的延迟时间内给出处理的结果。另外，还要求算法在硬件中 执行的延迟是静态的、固定的、可预见的。也就是说，当算法在某个硬件平台 上编程完毕以后，该算法执行所需的延迟就已经决定了并且是事先可计算的。 只有满足了这点，设计者才能对d s p 算法的实现进行评估和控制。最后，若 希望硬件有较好的通用性，则硬件还必须具有大范围可伸缩的处理能力，以此 来对不同速率的应用提供实时性的支持。 2 1 2 并行性的特点 在d s p 算法的众多共同特征中，内在并行性可以说是对d s p 处理器的结 构产生影响最大的一种特性。正是由于这些并行性的存在，才使得设计者有可 能满足日益复杂的d s p 算法对实时性的苛刻要求。正如引言以及下一节将提到 的，对d s p 算法并行性的挖掘是近年来d s p 发展的主要动力，也将是未来d s p 发展的重要方向之一。 理论上，d s p 算法的并行性可分为空间并行性和时间并行性两个方面。在 硬件实现上，空间并行性可以通过并行处理的方法来实现；时间并行性则可以 通过流水线的方法来实现。下面以f i r 滤波算法为例来说明d s p 算法的并行性。 第二章d s p 算法的特点及各种实现结构 一个n 阶f i r 滤波算法可以用2 1 式来描述： 一i 儿，z 】= q x n 一0 - - c o 虹九】+ c l x n 1 + + c 一l x ，2 一+ l 】 ( 2 1 ) 忙o 与式2 1 相对应的算法框图( 数据流图) 如图2 - 1 所示。 y 【n 】 图2 1f i r 算法的框图 由图2 1 可见，原来本算法所需的n 次乘法可以通过并行执行的方式同时 执行，总共只需一次乘法的时间；原来本算法所需的n 次加法可以采用树型结 构并行执行，理论上只占用l o g a n 次加法时间。这就是f i r 算法的空间并行性。 另一种实现方案是采用时序重组( r e t i m i n g ) 的技术 l g s 8 3 】，相应的数据流图如 图2 - 2 所示。在图2 - 2 中，一个乘法运算以及紧接其后的一个加法运算组成了 一级流水线。当系统正常工作时，n 级的流水线都可以并行执行，从而使n 阶 f i r 运算具有常数的时间复杂度。这可以看作是f i r 算法的时间并行性。从以 上的分析可知，f i r 滤波算法具有很高的空间并行性和时间并行性。 x i n 】 y n l 图2 2经过时序重组后的f i r 算法框图 从以上的分析可以看出，并行性是d s p 算法的一个重要特性，充分利用 d s p 算法的并行性可以有效地提高处理性能、降低软硬件开销。d s p 算法的并 行性对d s p 硬件主要有以下一些要求。首先，d s p 硬件需要有足够的硬件资源 来满足并行处理的要求。一方面，这要求d s p 需要有多个可并行工作的处理单 元，能够对输入数据进行并行的处理：另一方面，还要求d s p 能提供足够的存 储带宽，以满足并行处理单元大量数据存取的需要。其次，处理单元之间以及 处理单元与存储器之间的互连必须有很高的灵活度。因为，不同的d s p 算法要 第二章d s p 算法的特点及备种实现结构 求数据之间有不同的通信方式。所以，只有高度灵活的互连才能适应不同的数 据通信模式。最后，还要求d s p 的硬件资源便于分配和管理，这样才能有效地 利用有限的硬件资源来达到最大的并行性。 2 1 3 存在算法核心 d s p 算法的又一个重要特征是每一个算法都具有一个算法核心，算法核心 是d s p 算法内层的循环操作。一个d s p 算法往往是对算法核心规则地反复循 环。所以，算法核心单次执行的运算量并不大，但是它的反复执行则构成了整 个d s p 算法的主要运算量。例如f i r 滤波算法的核心就是每一阶滤波进行的乘 加运算( m a c ) 。事实上，乘加运算也是很多d s p 算法共同的核心。 正是由于d s p 算法核心的存在，而且d s p 算法主要的运算量就集中在算 法核心上，使得d s p 设计者有可能通过算法核心的重点优化来获得整个d s p 算法的优化执行结果。典型的d s p 处理器对乘加运算的优化以及专用d s p 处 理器针对某个特定算法的优化都是基于这样的考虑。 2 1 4 数据结构和存取模式 从大量描述d s p 算法的数学公式中可以看出，d s p 算法涉及的数据结构往 往是一些向量或矩阵。相应的，d s p 处理器需要在处理一定标量数据的基础上 面临大量一维、二维甚至更高维的向量运算。所以，概括地讲，向量和矩阵是 d s p 算法数据结构的主要形式。 向量数据和矩阵数据一般都存储在内存中，不同的d s p 算法就牵涉到对内 存不同模式的访问。表2 1 列举了几种不同的内存访问模式，并用伪代码说明 了这些访问模式的循环实现方法。表中，第一种访问方式是对向量数据的顺序 访问，这是一种最常见的访问方式，几乎所有的d s p 运算中都需要使用到这种 访问方式；第二种是对向量数据的循环访问，这种访问方式在访问f i r 滤波运 算的输入数据时经常使用；第三种是对矩阵数据的行优先顺序访问，这是一种 最常见的访问矩阵数据的方式，大多数矩阵运算都需要用到这种访问方式；第 四种是对下三角矩阵数据的行优先对角访问。 由于数据的存取在d s p 运算中具有相当重要的意义，所以d s p 硬件有必 要进行有针对性的优化。一方面，如上一节所述，需要提供足够的存储带宽； 另一方面，还需要针对d s p 算法常见的内存访问模式来优化相应的地址生成过 程。这一般可以通过专门的地址生成单元来实现，它可以通过一系列相对简单 的算术和逻辑操作来完成地址的计算而不需要完整的数据通路，并且地址生成 单元又要具有足够的灵活性，以适应不同d s p 算法的需要。 第二章d s p 算法的特点及各种实现结构 数据结构访问模式循环实现 n 个元素的顺序访问 p = & a 【o ； 向量a ( 0 ，1 ，2 ，n 2 ，n 1 )f o r ( i - 0 ；i n ；i + + ) 在内存中 p 2 p + 1 ； 顺序存放， 首地址为循环访问 f o r ( i - o ；i n ；i + + ) a 【0 】( 0 ，1 ，2 ，n 一2 ，n - 1 ，p = & a i ； 1 ，2 ，n 一2 ，n - 1 ，0 ，f o r ( j = 0 ；j n ：j + + ) 2 3 n - 2 ，n - 1 ，0 ，l ，i f ( p = & a n 一1 ) p ：& a 【o 】； 、 i ，i + l ，n 一2 ，n 一1 ，0 ，i - 1 ， e l s e p = p + l ； n 1 ，0 ，1 ，n 一3 ，h i - 2 ) ) n * n 的矩行优先顺序访问 p = a o o ； 阵a 在内【( o ，0 ) ，( o ，1 ) ，( o j 小2 ) ，( 0 ，n 1 ) ，f o r ( i _ o ；i 心 ；i + + ) 存中按行( 1 ，o ) ，( 1 ，1 ) ，( 1 n 一2 ) ，( 1 ，n 1 ) ，f o r ( ；= o ；j n ；j + + ) 存放，首地p = p + l ； 址为 ( i ，o ) ，( i ，1 ) ，( i ，s - 2 ) ，( i ，n - 1 ) ， ) & a 【o o 】 ( n 一1 ，o ) ，( n 1 ，1 ) ，( n 一1 ，n 1 ) 行优先对角访问p = & a 【0 l o l ； ( o ，o ) ，f o r ( i _ l ；i = n ；i + + ) ( 1 ，o ) ，( 1 ，1 ) ，f o r ( j = o ；j n 的最小整数； 地址增量的绝对值不大于循环缓存的大小，即1 s t e p l n ； 循环寻址的初始地址必须位于循环缓存内a 若符合以上要求，则地址的低k 位可以看作是循环缓存的索i ( i n d e x ) ，s i z e 寄存器的值就是循环缓存索引的边界。这样，循环变址的算法就可归纳如下： 第五章d s p l 6 中关键模块的优化实现 i f ( 0 n ，其进位也不一定能传递到加法器的进位输出； 另一方面，它无法直接支持模n 的减法，因为模n 的减法并不能简单地将减数 取反加一转换为加法运算。这样，基于 b j 8 7 】的加法器无法直接满足d s p 中循 环变址的运用。 r 图5 3 【b j 8 7 提出的模n 加法器 我们对【b j 8 7 】加法器进行了两点改进，使其满足循环变址运算的要求： ( 1 ) 、将计算结果直接减去循环缓存的边界值来判断地址是否越界，而不是像 【b j 8 7 那样用加z 来判断，这样越界判断的进位信号可以传递到最高位。 循环缓存的边界值可以通过寻址的初始地址和s i z e 值经过一定运算得到。 第五章d s p l 6 中关键模块的优化实现 ( 2 ) 、当变址偏移量为负数时，先将地址加上s i z e 再进行运算就可得到正确结果。 变址并加上s i z e 的操作可以通过保留进位加法器( c s a ) 进行。 经过改进的 b j 8 7 力h 法器如图5 - 4 所示。其中需要根据初始地址和缓存大 小计算缓存边界，其原理如下：设s i z e 寄存器的内容为：s n 1 s 。_ 2 s i s o ，a d d r 寄 存器的内容为：a n i a n 一2 a l a o 。首先根据s i z e 寄存器的内容确定h i ：若s 。1 到s 。 为全零，则h j = o ，否则h i = l ，即 h i = s n i i s a l i s i( 5 4 ) 图5 4 改进的 b j 8 7 模n 加法器 3 _ = z ) - 翻2 妒 图5 - 5 图5 - 4 中的边界计算模块 第五章d s p l 6 中关键模块的优化实现 式中，“j ”表示逻辑或。所有的n 一1 个h i 组成矢量h ，这样，若k 是满足2 0 s i z e 的最小整数，则低k 位的h i 都为1 ，其余h i 都为0 。然后，将h 取反后和a d d r 相与就可屏蔽地址中的低k 位，得到循环缓存的上边界( u p p e r ) 。最后，再将缓 存上边界与s i z e 相或，就可得到缓存下边界( 1 0 w e r ) 。 在硬件实现时，h i 的计算借用了树型前缀( p r e f i x ) 力 1 法器中的高基s k a l a n s k y 前缀计算结构 b l 0 1 1 ，采用了三级或阵列实现。最后一级或阵列可以与下一级 的与阵列合并采用复合门逻辑以降低电路延时。整个结构如图5 + 5 所示，图中 黑色圆点是与f - j ；虚线框中的是复合门；白色圆点表示直i l 臣( f e e d t h r o u g h ) 。 5 3 3 运算单元整合与方案比较 方案一 将上文介绍的进位反转加法器和循环寻址加法器进行整合，就可得到a g u 变址所需的运算单元，整个运算单元的框图如图5 6 所示。图中的预处理模块 如右侧的虚线框中所示，它综合了进位反转加法器的倒序操作和模n 加法器补 偿s i z e 的操作，总共产生三个结果：原地址、地址偏移量和s i z e 补偿量。这三 个结果经过一级c s a 与一级进位传播加法器相加得到第一级的和。同时边界计 算模块计算出循环缓存的上、下边界。另外，倒序模块根据是否为进位反转运 a d d r s l z e 专孽 图5 - 6 方案一的a g u 运算单元总体框图 第五章d s p l 6 中关键模块的优化实现 算对第一级和进行倒序处理得到第一个结果。第二级加法器用第一级和减去缓 存的下边界，得到第二级的和。第二级和需要与缓存上边界相或，补偿地址的 高位，得到第二