（信息与通信工程专业论文）可重构计算中dsp技术的研究.pdf

摘要 在数字信号处理的应用中，传统的方法足采用通用处理器( d s p ) 或专用集成电路( a s i c ) 来实现各种算法。但多年来的实践证明，这 两种方法都存在一些不足。而可重构计算既具有专用计算系统的性能， 又有通用计算系统的灵活性，对于实现高性能的数字信号处理系统有很 高的应用价值。 为了发挥可重构计算的优势，我们必须解决两个问题：一是什么 样的数字信号处理算法适于用可重构计算技术实现：二是数字信号处理 算法如何映射到可重构器件中才能有最高的性能。 j 我水必论的可重构计算一般指的是基于f p g a 的系统设计。因此， 我竹首先详细介绍f p g a 的体系结构和特点；然后分析一类数字信号 处理算法，探讨何种算法适合于用可重构计算技术实现；最后，我稍举 例说l ! j j 数字信号处理算法如何映射到f p g a 器件中，并对它们的性能 进行讨论。 关键词 可重计算、数字信号处理、超大规模集成电路、现场可编程门阵 列、分布式计算 i第页 垦堕翌堂楚查丕堂婴塑尘堕堂垡堡塞 一 a b s t r a c t l nt h e a p p l i c a t i o n o fd i g i t a l s i g n a lp r o c e s s i n g ( d s p ) ，t r a d i t i o n a l t e c h n i q u ei sb a s e do ng e n e r a lp u r p o s ep r o g r a m m a b l ed s p s a n da p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u s ( a s l c ) b u tt h e r e a r es o m es h o r t a g e si nt h e s e w a y s r e c o n f i g u r a b l ec o m p u t a t i o n h a s h i g hp r o c e s ss p e e d o f s p e c i a l p u r p o s ec o m p u t i n g s y s t e m a n d g o o df l e x i b i l i t y o f g e n e r a lp u r p o s e c o m p u t i n gs y s t e m ，a n ds u i t a b l ef o rh i g hp e r f o r m a n c ed s p s y s t e m i no r d e rt o e x p l o i ta d v a n t a g e o fr c o n f i g u r a b l e c o m p u t a t i o n ，t w o q u e s t i o n s m u s tb ea n s w e r e d f i r s ti sw h a tk i n do fd s pa l g o r i t h m c a n i m p l e m e n t e db yr c o n f i g u r a b l ec o m p u t i n gt e c h n i q u e ，t h e s e c o n di sh o w m a p t h e s ed s pa lg o r i t h mm a pi n t or c o n f i g u r a b l ec o m p u t i n gd e v i c e t h er c o n f i g u r a b l ec o m p u t a t i o nw et a l ka b o u th e r ei sb a s e do nf p g a s ot h ea r c h i t e c t u r ea n dc h a r a c t e r i s t i co ff p g ai si m r o d u c e df i r s t l y ；t h e nt h e i m p l e m e n t a t i o np o s s i b i l i t yo nr e c o n f i g u r a b l ec o m p u t i n gs y s t e mo fs o m e d s p a l g o r i t h m si sa n a l y z e d ；a tl a s t ，t h em e t h o do fm a p p i n gd s pa l g o r i t h m i n t or e c o n n g u r a b l ed e v i c ei se x p l a i n e db yt w oe x a m p l e s k e y w o r d s r e c o n f i g u r a b i ec o m p u t a t i o n 、d i g i t a ls i g n a lp r o c e s s ( d s p ) 、v e r y l a r g es c a l ei n t e g r a t i o n ( v l s i ) 、f i e l d p r o g r a m m a b l eg a t ea r r a y ( f p g a ) 、 d i s t r i b u t e da r i t h m e t i c ( d a ) 第1 l 页 国防科学技术大学研究生院学位论文 第一章绪论 第一节、引言 在现代数字信号处理和数字图象处理的应用中，高速度和大规模的计算能力 是十分必要的。为了实现这种应用，通常有两种方法：一是采用高性能的通用处理 器( 如d s p 处理器) 作为基本的计算单元，并选择合适的体系结构进行系统设 计；二是专用处理器方法，采用各种硬连线结构的专用电路( a s i c ) 作为基本的 计算单元，并选择合适的体系结构进行系统设计，其所有的核心算法都由a s i c 电 路实现。 以上两利，方法在一定条件下是最优的方案，但也存在一些不足： ( 1 ) 通用处 理器编程灵活，设计周期短，成本低，但运算时的指令开销大，计算速度难以提 高，硬件的利用率比较低：( 2 ) 专用处理器的计算速度快，具有高的计算性能， 而且体积小，但设计周期长，成本高，硬件结构固定，不具有可编程能力，只能实 现单一算法；( 3 ) 两种方法都不具备根据算法调整相应的通信结构和数据字长的 能力。 现在，随着集成电路工艺和电子系统设计自动化水平的提高，以及并行处理技 术的发展，可重构计算( r e c o n f i g u m b l e c o m p u t a t i o n ) 技术显示出了良好的发展趋 势。可重构计算系统既具有通用计算系统的灵活性，又有专用处理系统的性能，对 于实现高性能信号处理系统具有很高的应用价值。 本文将探讨两个方面的问题：( 1 ) 可重构计算技术的适应范围，即什么样的 d s p 算法适合用可重构计算技术实现；( 2 ) d s p 算法到可重构器件的映射，即如 何用f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 器件实现d s p 算法才能获得高性能。 1 、可重构计算的定义 第二节、可重构计算技术 第l 页 国防科学技术大学研究生院学位论文 可重构计算是- - i 3 新兴的技术，虽然早在1 9 6 0 年，可重构计算的思想就已经 被提出，但是由于当时器件技术的限制，这种思想并没有得到广泛的关注和深入的 研究。直到8 0 年代末，才出现了第一代可重构计算系统- - d e c p e r l e ，掀起了可 重构计算研究的一轮热潮。 目前，关于可重构计算并没有一个统一的标准定义，不同的研究者由于研究问 题角度的不同对可重构计算有着不同的理解，因而也提出了不同的定义。在这里我 们选择两个有代表性的定义来描述可重构计算的特征。 ( 1 ) 可重构计算机是一种通过将计算单元进行制造后( p o s t - f a b r i c a t e ) 空域连接 ( s p a i a lc o n n e c t i o n ) 以实现计算的器件。 该定义中的两个要点是：，制造后的功能定义；二，利用空域连接进行计算。所 谓制造后，是指器件功能的定义是在i c 器件出厂之后由用户完成的，这与a s i c 器什的功能在：卷片工厂加工过程中定义形成对比。a s i c 器件的功能是在芯片生成 厂制造过程中通过掩膜、刻蚀等一系列工艺过程完成的，在这个意义上可重构计算 系统与通用处理器十分相似。功能定义时问的延后意味着可重构计算系统可以由用 户根据特定的应用背景实现多种不同的功能。空域连接指的是用逻辑f - j 矛n 连线来实 现计算，与此相对的另一种完成计算的方式是用算术逻辑运算单元( a l u ) 和在 a l u 上实现的指令序列，后者被称为时域连接方式。 ( 2 ) 可重构计算系统就是通用( g e n e r a lp u r p o s e ) 定制( c u s t o m ) 硬件。 这个定义突出通用和定制这两个特点。所谓通用就是可以用同一个硬件平台完 成多种计算功t i ；而定制就是将硬件按照一个特定应用的结构、行为特点进行设计 与优化。通用性是可编程处理器的优势，而通过定制获得高性能是a s i c 器件的特 长。这个定义说明了可重构计算可以兼具可编程处理器的通用性和a s i c 器件高性 能的优点。 j _ 2 、可重构处理器( r e c o n f i g u r a b l ep r o c e s s o r s ) 可重构处理器主要由三部分组成：( 1 ) 基本的功能单元，常用p e 或c e l l 来 表示；这些基本功能单元中一般包含有决定其功能和与互连网络连接关系的配置存 储器，；( 2 ) 互连网络，用于实现基本功能单元之间连接的柔性互连资源( 互连 线、丌关逻辑等) ，它是实现可重构处理器灵活性的基础；( 3 ) 输入输出单元， 用于缓冲从外围管脚上输入黼出的数据。 第2 页 国防科学技术大学研究生院学位论文 目d u ，典型的重构处理器是一些基于静态存储器( s r a m ) 技术的高容量的 f p g a 器件，如美国x i l i n x 公司的x c 4 0 0 0 、x c 6 2 0 0 序列f p g a 等。在这类可重构 处理器中，基本的功能单元一般是具有n 个输入信号的查找表n l u t ( ni n p u t l o o k - u pt a b l e ) 、它能实现以这n 个输入为变量的任意逻辑函数；从节约：卷片面积 考虑，n 的典型值是4 ，即采用4 输入查找表( 4 l u d 是高性能与占用面积之间较好 的折衷办法。由于这些功能单元只能处理一位( 二进制位：b i t ) 信息。故是一种细 粒度( 1 m e g r a i n ) 结构。为了提高可重构处理器的处理能力和互连资源，也出现了 一些用户定制的粗粒度( c o a r s e - g r a i n ) 结构的可重构处理器；在这类可重构处理器 中，基本功能单元是根据特定应用的需要而设计的较为复杂的算术逻辑单元 ( a l u ) 或处理单元( p e ：p r o c e s s i n ge l e m e n t ) 。 需要况明的是，按照传统观念，独立的f p g a 器件是不具备处理器的特性的， 但f p g a 器件嵌a n 某个计算系统中并进行管脚分配之后，它的输入输出信号便已 确定，至于输入输出信号之间的关系则是通过重构机制来动态确定的，因此，在这 个意义上f p g a 可以被称为可重构处理器。 可重构处理器与传统处理器相比，具有很多独特之处，主要表现为：( 1 ) 指 令分发。如果将可重构处理器中每个功能单元的“配置”看作“指令”，那么可重 构处理器中的指令是局部配置的，这显然可以作到对指令流的压缩，且在每个周期 内可能执行更多的指令；( 2 ) 中间结果的空间分布。只要可重构处理器中的空间 允许，中间值可以完全并行地从输出函数送入输入函数：( 3 ) 构造模块。可重构 处理器具有更多和可用的细粒度、独立可配置的构造模块，这可以允许处理器在一 个时间步内执行大量的计算操作；( 4 ) 分布式的和可调度的资源结构有利于消除 通信瓶颈。在传统的处理器中，用于运算和控制的硬件资源往往是集中式的，相当 于一个可用资源库；而可重构处理器中的配置存储器、互连网络、功能单元等都是 分夼式的，且可根据需要来进行调度和裁剪；可重构处理器的这种结构具有通过片 上局部化的高速并行带宽来进行独立的、局部的访问操作能力，这就使得可重构处 理器能够避免传统处理器中存在的通信瓶颈问题。 3 、可重构计算系统( r e c o n f i n u r a b l ec o m p u t i n gs y s t e m ) 可重构计算系统也常被称作可重构的定制计算系统( c c m ：c u s t o mc o m p u t i n g m a c h i n e ) 。可重构计算是八十年代未、九十年代初开始兴起的一个研究领域；其 基本特征是系统中有一个或多个可重构处理器( 最典型的可重构处理器就是已进行 第3 页 里堕型堂丝查查鲎塑茎生堕堂垡迨塞 一一一 管脚分配的、大容量的可重构f p g a 器件) ，可重构处理器之间或可重构处理器与 i s a 结构处理器之间通过某种灵活的互相连接起来均可以构成一个完整的计算系 统。 可重构计算系统可以分成两大类：一是可动态重构的计算系统t 也即在线局部 可重构的计算系统，其特点是可重构处理器中一部分硬件进行运算或信号处理的同 时能够对另一部分硬件进行重构；其余的可重构计算系统则属于静态可重构系统。 在可重构计算系统中，全部或大量的关键算法由可重构硬件来实现，其方法 为：根据具体算法得出符合可重构硬件实现的结构，并由结构设计出相应的电路， 通过c a d 系统将电路描述转化为以可重构硬件进行功能重构的配霹代码；其实质 是对可重构硬件中的基本功能单元通过丰富的互连资源进行结构重组，我们认为， 这相当于先在可重构处理器。l j 定制出基本的可重构计算单元( 如信号与图像处理【l | 的乘法累加器) ，再确定硬件系统设计策略( 如全局并行局部串行、局部并行全 局串行等) ，并在这些计算单元的基础上实现更复杂的规则阵列结构，从而完成复 杂的计算任务。 可重构计算系统具有许多与可编程的i s a 结构计算系统所不同的行为特征，其 设计手段和方法也有较大差异。由于可重构系统主要通过可重构硬件来实现各类关 键算法，没有i s a 结构通用计算系统中的指令开销问题，其计算性能往往高出通 用指令集系统一个数量级以上；同时，可重构计算系统中可重构处理器功能也可以 被动态地改变，这对于需要自适应能力的系统是很有意义的。 4 、可重构计算的优势 虽然可重构计算的研究与发展目前尚处于起步阶段，但是它已经表现出了性能 方酊噱人的潜力。从可重构计算系统的抽象体系结构来看，由于减少了在控制、指 令发布、指令和数据存储方面的硬件面积刀：销，而给用于实现计算功能的有效硬件 留下了更多的硬件面积，可以带来高于常规计算系统数十倍的密度优势。 由于它拥有大量的逻辑计算单元和丰富的连线资源，可以在从位级、循环 级、指令级到应用级等广泛的层次上实现并行计算，在实现具有内部并行性的应用 算法时将可以充分发挥应用本身的并行性，极大地提高系统运行的性能。 从重构的机制的角度来看，一方面，可重构计算系统根据特定应用如特殊数据 可以直接定制系统，利用空域连接完成计算，把冗余部件减到最小，提高系统的效 率和处理的速度；另一方面，可重构计算系统的运行时重构可以使多个电路在不同 第4 页 旦堕型堂堡查盔堂婴塞生堕堂焦鲨塞 一一 时间共享同一块硬件资源，大大提高了硬件利用率。 这儿个方面的因素共同决定了可重构计算系统将兼具可编程处理器的通用性和 a s i c 器件的高性能，必将对未来的通用和专用计算领域产生深远的影响。 第三节、可重构计算的历史与现状 第一个真正意义上的可重构计算系统是1 9 8 9 年由d e c 巴黎实验室开发成功的 p a m ( p r o g r a m m a b l e a c t i v em e m o r y ) ，它与s r c 开发的s p l a s h 属于第一代可重 构系统，采用的器件都是x i l i n x x c 3 0 0 0 系列f p g a 。p a m 与s p l a s h 这两个系统 在一些特定的应用领域，如图象滤波、卷积、数学形态学、特征提取和目标跟踪方 面达到了比常规最高性能的方法高出几个数量级的极高的性能。展现了可重构计算 所具备的潜力，掀起了可重构计算研究的热潮。在此后出现了大量的可重构系统， 其中有作为协处理器的p r i s m 、d i s c 和c v a ，它们是与主机系统共享寄存器文件 或者主存的独立的系统；有p r i s c 、c l f i m e r a 等功能单元部件，它们位于系统的数 掘通道，接受系统的指令，属于主机系统的一部分。此外还有m a t r i x 等动态可重 构器件；e , a p i d ，r a w 等粗粒度器件；q u i c k t u m 等逻辑仿真器也属于可重构计算系 统的范畴。 目前在可重构计算的研究中遇到的挑战主要在两个方面。一是现在作为实现可 重构计算系统基础器件的f p g a 本身并不完全适应可重构计算的要求。常规的 f p g a 是为实现“胶合逻辑”( g l u e l o g i c ) 电路而设计的，不适应计算的要求。 除了可以无限次重构这个优点之外，常规f p g a 的数据通道宽度只有一位，没有浮 点运算部件，重构日寸问太长等等都是阻碍可重构计算系统提商性能的因素。二是开 发工具的不完善。目前还没有一个标准的、通用的设计流程，没有高性能的电路综 合、稚局粕线算法，现有的可重构系统计算机辅助开发工具是面向硬件丌发人员而 不是面向算法开发人员，并且速度太慢，经常需要几十分* , i n j l 个小时才能完成一 个中等规模的设计，远远无法适应重构的需要。 第四节、本文的主要工作和内容简介 可重构硬件作为一种崭新的计算器件，其作用不止于简单地集成若干中小规 模集成电路和仅仅作为a s i c 器件廉价的代用品。可重构器件以及可重构计算系统 第5 页 国防科学技术大学研究生院学位论文 的结构是一种与可编程通用处理器和专用硬件电路并列的，值得我们深入研究的体 系结构形式。 在本文中，我们着重研究d s p 算法如何映射到可重构器件中。但我们首先要 确定哪一类算法适合用可重构计算技术实现。在分析数字信号处理算法和f p g a 器 件结构特点的基础上，我们找出一类适合可重构计算的算法，并用两个具体的例予 说明算法是如何映射到器件中的。 本文的内容安排如下：第一章，对可重构计算作一个全面的介绍，阐明可重构 计算的特点与优势；第二章，具体分析f p g a 的体系结构，介绍两种可重构器件： 第三章，设计定制的基于f p g a 的d s p 器件，从性能上比较与专用d s p 和a s i c 的差异：第四章，总结全文。 第6 页 国防科学技术大学研究生院学位论文 第二章f p g a 体系结构 第一节、引言 我们所谈论的可重构计算一般指的是基于f p g a 的系统设计，因此，f p g a 件的结构和性能对选择算法以及映射算法有着重要的影响。f p g a 器件的体系结构 与通常的大规模集成电路的结构是不同的。f p g a 针对重构特性对器件结构进行了 优化设计，因而具有自身的特点我们必须对这种特点有深入的了解，才能尽量发 挥f p g a 器件可重构计算的优势。本章将详细介绍f p g a 的体系结构及性能。 第二节、f p g a 器件 到目前为止，绝大多数可重构计算系统都是基于商用f p g a 产品的，这些商 用f p g a 的结构与性能对于我们分析、设计、实现可重构计算系统有着重要的影 响。下面将从逻辑单元体系结构对当前常用的商用f p g a 器件进行分析，包括 x i l i n x x c 4 0 0 0 系列f p g a 和x i l i n x x c 6 2 0 0 系列f p g a 图l 是f p g a 的抽象体系结构图。目前大多数f p g a 器件由逻辑单元阵列和 互连结构两个主要部分组成这两部分均由配置开关( s w i t c h ) 来控制它们的行 为，用户可以通过对这些配置开关的配置来完成指定的功能。 f p g a 器件实现配置开关的机制称为编程技术( p r o g l m n m i n gt e c h n o l o g y ) 。 常见的编程技术可以分为三类：一次性编程技术，可多次编程技术以及可无限次编 程技术。基于反熔丝( a n t i - f u s e ) 技术的编程技术属于一次性编程( o t p ) 技术； 基于e p r o m ，e e p r o m 和f l a s h m e m o r y 技术的编程技术属于可多次编程技术；而 基于s r a m 技术的属于可无限多次编程技术。可重构计算要求器件具备可无限多 次编程的能力，所以一般采用用基于s r a m 技术的f p g a 第7 页 国防科学技术大学研究生院学位论文 图lf p g a 的抽象体系结构图 f p g a 的逻辑单元结构 f p g a 中逻辑单元体系结构的设计是一个复杂性与通用性权衡的过程。可以 用粒度( g r a i n ) 来描述f p g a 中逻辑单元的复杂程度。从理论上说逻辑单元的 粒度由细到粗可以是晶体管级、与非门级、m u x 级、l u t 级、p l a 级直到c p u 级，可以大致分为粗粒度( c o a r s e g r a i n ) 与细粒度( t h i n g r a i n ) 两大类x c 4 0 0 0 系列，f l e x8 0 0 0 系列等属于粗粒度的f p g a ，它们包含数量较少，内部结构较复 杂的逻辑单元：x c 6 2 0 0 系列，a t 6 0 0 0 系列属于细粒度f p g a ，它们包含数量较 多，但内部结构较为简单的逻辑单元。目前，大多数商用f p g a 的逻辑单元主要由 4 - l l j t ( 四输入查找表) 和触发器组成。另一种f p g a 逻辑单元的分类方法是同构 型f p g a 和异构型f p g a 。f p g a 中所有逻辑单元为同一类型的称为同构f p g a ： 包含多利- 类型逻辑单元的f p g a 称为异构f p g a 。同构的f p g a 有很好的通用性， 能被现有的综合工具很好地支持，但它在实现某些具有特定要求的应用时效率较 低；异构f p g a 在牺牲通用性的前提下，在某些应用中能够获得更高的速度和更强 的功能，目前大多数商用的f p g a 属于同构型f p g a 。 第8 页 国防科学技术大学研究生院学位论文 第三节、x c 4 0 0 0 系列和x c 6 2 0 0 系列 下面，我们利用上面的讨论的知识来分析两种f p g a 器件：x i l i n x x c 4 0 0 0 系 列f p g a 和x c 6 2 0 0 系列f p g a 。 x i l i n xx c 4 0 0 0 系列f p g a 是一种粗粒度的同构型f p g a 。其逻辑单元称为 c l b ( c o n f i g t w a b l eb o g i cb l o c k ) 一可配置逻辑单元，它的结构如图2 所示。每个 c l b 中包含2 个4 一l u t ( f ，g ) ，一个3 一l u t ( h ) ，2 个触发器，以及快速进 位逻辑。其互连结构呈现层次式互连，如图3 所示。每个c l b 有2 个三态缓冲 器，以便c l b 连接到水平方向的长线上，每列连线中有若干全局时钟线和进位 链。所以，水平方向适于作为数据通道，而垂直方向适于作数据流。x i l i n xx c 4 0 0 0 系列的一个重要特性是其l u t 可以配置成各种模式的单端口、双端口r a m 。 图2x i l i n xx c 4 0 0 0 系列f p g a c l b 结构图 x i l i n xx c 6 2 0 0 系列f p g a 的前身是a l g o t r o n i x 公司的c a l ( c o n t i g u m b l ea r r a y l o g i c ) ，它属于典型的同构型细粒度f p g a 。其逻辑单元称为逻辑胞元( l o g i e c e l l ) 的结构如图4 所示。其中每个逻辑单元f u ( f u n c t i o n a l u n i t ) 可配置成为任何 一个二输入的函数，2 ：1 的选择器，o 或1 的常量，单输入的函数，以及以上这些 函数与触发器的组合，也可以用于存储状态，如图5 所示。 第9 页 里堕型堂垫查盔堂婴塑竺堕鲎焦丝壅 图4 x i l i n xx c 6 2 0 0 系列f p g a 逻辑胞元结构图 第1 0 页 国防科学技术大学研究生院学位论文 t i t 图5x i l i n x x c 6 2 0 0 系列f p g a 逻辑单元( f u ) 结构图 逻辑胞元可以参与布线，同时不影向自身完成逻辑功能，它包含两个4 ：l 的 m u x ，3 个2 ：l 的m u x 和一个触发器。x c 6 2 0 0 系列f p g a 的互连结构一方面继 承了c a l 的特点，在相邻逻辑胞元之间 ) i j 有局部连线，另一方面又采用了x i l i n x 公司系列f p g a 一贯的互连结构风格，分别加入了长度为4 ，1 6 ，的长线，构成 层次化的互连结构。此外，x c 6 2 0 0 互连结构中还有些全局连线，分别用于系统 用途( 包括时钟复位，电源和接地等) 和连线转向功能( 比如m a g i ew i r e ) 。 x i l i n x x c 6 2 0 0 系列最重要的特点是可以在不影响芯片中一部分电路正常：l 作的情 况下对另一部分电路进行重构。 第1 1 页 国防科学技术大学研究生院学位论文 第三章基于f p g a 的d s p 算法 第一节、可重构计算的适用范围 分析了f p g a 器件结构之后，我们再来研究本文州：头提出的两个问题：可重 构计算的适用范围和算法到f p g a 器件的映刳。 我们首先解决第一个问题。 可重构计算之所以有较高的性能，是通过并行处理和重构获得的。而重构特性 和通用处理器的编程性的差别是显而易见的，所以从本质上说，可重构计算应该属 于v l s i 并行计算机系统。从指令流与数据流的多倍性的角度。f l y n n 在1 9 6 6 年 将计算机分为下列四类； 单指令流单数据流( s i s d ) 单指令流多数据流( s i m d ) 多指令流单数据流( m i s d ) 多指令流多数据流( m d d ) v l s i 并行结构大多是属于单指令流多数据流( s i m d ) 的结构，这种结构对多 个重复的p e 由单一指令部件，按照同一指令流的要求同t i , t l 龟它们分配各自需要的 不同数据。图l 是这种结构的框图。这种结构改变了过去计算机结构上以c p uc 1 1 心或以主存为中心的典型冯诺依曼结构，采用以互连网络为中心的结构。 图1s 1 m d 结构 第1 2 页 国防科学技术- 人学研究生院学位沦文 但v l s i 并行计算机大都是属于专用计算机范畴，它们面向具体问题，列算法 有较强的依赖性。互连结构是固定的，而可重构计算系统也是面向具体问题，对算 法有一定的依赖性，但是它的互连结构是可变的，这正是可重构戮算系统与专用计 算机的最大区别。 一般来说，专用集成电路能完成的算法也能用f p g a 器件实现。专用集成电路 是针对具体算法把电路进行了最优化设计的，因而往往性能也是最高的。而f p g a 器件是由逻辑单元阵列和互连结构两部分组成的，而这两部分都要通过配胃j f ：关来 完成各种功能，因而必然降低了：占片的有用面积：同时对电路电无法进行最优化， 因此，若无法重构的话，f p g a 器件在性能上不如专用集成电路。 正是由于可重构的特点，我们自然丽然地想到，若是能把一个算法分成儿部 分，分别配置到f p g a 器件中，必然能提高硬件资源的利用率。事实也旷是蜘j 此， 比如b p 神经网络。我们把它分成三个顺序执行的部分，分别配镡到f p g a ，h 通 过各个部分的分时执行，确实提高了系统的总体性能。在这种情况下，要求算法有 明显的时分性。这种算法对器件没有明显的依赖性，不是我们要讨论的重点。 除了前面提到的外，还有没有其它适于用f p g a 实现的算法昵? 我们首先来看 几个数字信号处理中常用的算法： 卷积 卷积( c o n v o l u t i o n ) 是数字信号处理常用的基本运算。从数学上讲，一维卷积 问题可定义如下： 给定权系数 w 心，w l “输入序列( x 咕 ，计算序列( y 一y 2 ，y f m ， ，其计算 公式如下： 土 m = 2 二w ，x ，u l = w i x i + w 2 x + + w k x p k - i i = 1 当卷积用于数字滤波时， ) 【i ) 表示将被处理的输入信号序列，而 、v i 表示数字滤波 处理的冲激响应函数。根据 州 的不同，卷积处理可以达到不同的滤波效果，如图 象增强、信号平滑等。一般地，输出序列 y i 表示已被处理的信号。 从计算结构上看，它可以看成特殊形式的矩阵相乘的运算，写成矩阵形式如 下： 第1 3 页 国防科学技术大学研究生院学位论文 y l y 2 y 肛“ 一 x 2 1 x n i + i w 2 数字滤波 数字滤波是数字信号处理中经常使用的一种计算，它在图象处理中也有很重要 的作用。这里我们介绍有限冲激响应( f i r ) 滤波器。有限冲激响应滤波问题可定 义如下： 给定权系数 w ，, w 2 ，k ) 、输入序列 x ) 【：，x n ) ，计算序列 y 。y 2 ，) ，使 得： m = w i x ，+ j i - - - - - 3 v i 玛+ w 2 x “l + + 、 k x “k l 1 - 1 可以看出，本式和上式完全一样。 我们发现，相对于输入序列而言，权系数是不变的。若用通用d s p 处理器来 实现以上算法，则权系数必然被当作变量来处理，因而芯片的利用率不高导致处 理器的性能下降。而这种算法正好适于用可重构计算来实现。这一点我们将用后面 的例子来说明。 由此我们认为，有两类算法适合于可重构计算技术实现：一是在时问上可以分 段的算法，这样可以时分复用硬件资源；二是在算法中有大量的常数( 这里的常数 指的是在相当长时间内不变的数) ，以便于用分布式计算( d i s t r i b u t e da r i t h m e t i c ) 实现。 第二节、常系数乘法器， l 、介绍 d s p 功能的关键是实现在芯片利用率和性能上都有足够效率的乘法器的能 力。在通用处理器中，乘法器是一个两输入数据都可变的通用乘法器，这个乘法器 是经过优化的，有很高的执行性能。但它有明显的不足：一是乘法器的字长是固定 的，如1 6 位、3 2 位的乘法器。若执行一个1 9 位的乘法，则必须用3 2 位的乘法 器，这必然存在大量的资源浪费；二是在执行一类常系数乘法时，要把常数作为一 第1 4 页 “k 比 屯而 x 里堕整堂垫查盔堂堑塞生堕堂垡堡苎 个输入变量，因而使得常数乘法的简便易行的优点体现不出来。而在大规模集成电 路中，虽然一个固定的乘法器( 常系数，k ) 有占用更少的芯片面积的优点，但 由于电路的互联结构是固定的，实现常系数乘法器的代价太大，因而不适合应用任 务。 f p g a 器件的出现改变了这种局面。在1 9 9 3 年，o n - c h i p m e m o r y 和快速进位加 法的混合技术被发表了，并且得到了广泛的使用。 这种技术提供了一种改变乘法器来适合高速度数据通道的方法。现在，对 d s p 的要求是，要在非常高的数据率下能够执行。这自然地导致了高度并行处理方 法的出现，这种方法不再要求改变被乘数的值。 在这里我们阐述为什么常系数乘法器在d s p 中是最适当的选择，以及如何在 x c 4 0 0 0 e 中实现常( k ) 系数乘法器( k c m s ) 。 我们以f i r 滤波器作为例子，通过它来解释这种方法( 见图2 ) 。 图2f i r 滤波器原理图 在整个数据采样期间，通过相关的系数值，f i r 滤波器乘法累加先前的数据样 本( 抽头) 。对于一个给定的f 鼠滤波器，每个系数都是固定的。在标准d s p 器 件中，这种方法与微处理器的操作相似，在硬件中有一个专门的乘法累加 第1 5 页 国防科学技术火学研究生院学位 硷文 ( m a c ) 指令。当实现一个1 6 抽头f i r 滤波器的时候，抽头数据和相关的系数按 顺序被应用到m a c 。这不仅要求1 6 个m a c 指令来执行相关的数据处理，而且要 求一个两输入数据都可变的高性能乘法器。即使每个m a c 指令周期是2 0 n s ( 或者 5 0m i p s ) ，滤波器的最大的采样周期仍将被限制在3 2 0 n s ( 1 6 x 2 0 n s ) 或3 1 2 5 m s a m p l e s s 。在低取样率的应用中，这是一种可行的解决方法。 增加滤波器的采样速率需要一定程度的并行处理。在简单的情况下，增加第 二个5 0 m l p 处理器将把采样率提高到6 2 5 m s a m p l e s s 。但为了协调两个处理器之 洲的通信等问题，系统需要一定的额外丌销，这种系统的额外，r 销实际上使性能达 不到加倍的效果。每个处理机罩的乘法器都是通用的，同时在单个m a c 巾要完成 8 个抽头的计算。为了继续增加性能就需要更多的处理器。极限下有1 6 个处理 器，每个只为一个抽头提供服务。虽然在理论上性能将达到5 0m s a m p l e s s ，但是 系统的额外开销将削目；这种能力，或者需要增加儿个额外的处理器。这不是一个实 用的方案，但重要的是我们发现在这极端的情况下，每个乘法器都执行一个固定系 数值的抽头数据乘法。 这意味着通用乘法器在这里不再是最优的方案。所以，在全并行处理q ，经 常考虑的是常系数( k ) 乘法器( k c m s ) 。 一般来说，一个k c m 只有一个通用乘法器的规模的四分之一。因此，不管性 能指标是否能达到通用乘法器的4 倍，在实际应用中采用k c m s 实现一个并行的算 法通常是一种花费较小的方案，而性能的增加成了一种免费的收获。 2 、常系数乘法器的设计 以8 5 x 3 7 为例子，考虑一下我们是如何用手算十进制的乘法的： 8 5 x7 3 58 5 4 - 5 6 0 x3 7 6 9 5 叶乃饵5斗5 9 5 8 x o s x l 0 卜+ 2 5 5 0 3 4 5 我们按顺序用第二个数的每个数字来乘以第一个数的全部数字。然而，我们不 知道8 5 的乘法表，这样，我们实际上执行的是只限于局部的一位数乘法，再加上 第1 6 页 国防科学技术大学研究生院学位论文 d 口一列的值。而我们知道7 和3 的乘法表，在分别计算出3 0 和7 与8 5 的乘积后， 再把两个值相加。 如果必须执行很多包括8 5 的乘法，建造一张8 5 的乘法表将节省我们大量的时 问。这将把我们的计算任务降低到只需查一位数的乘积，然后相加。如图3 ： b 5 x4 7 6 5 1 0 5 9 + 3 4 0 4 0 4 6 0 0 0 x8 5 = 0 1x8 5 一b 5 2 x 6 5 = 1 7 0 3 x 8 5 = 2 5 5 4 x 8 5 = 3 4 0 5 x 8 5 = 4 2 5 b x 8 5 = 5 1 0 7x 8 5 = 5 0 5 8 x 8 5 = 6 8 0 口x 8 5 = 7 6 5 图38 5 的乘法表 常系数乘法技术是手算方法的十六进制的等价物。在r a m 或r o m 中实现的 查找表是对乘法表的适当编程。单个的十六进制数字用4 个b i t 表示，查找表将从 o 到1 5 ( f ) 。十进制数8 5 ( 5 5h e x ) 的乘法表用表l 表示。 就像手算乘法一样，有张8 5 的乘法表使这类处理非常快。像前面一样，最终 结果用简单的加法就可得到，只要加上适当的偏移。一个8b i t 的混合乘法器见图 4 。 图4 一个8 b i t 的混合加法器 第1 7 页 国防科学技术人学研究生院学位论文 表18 5 ( 5 5h e x ) 的乘法表 5 5 x2 b 3 a 7 寸bx5 5 + o a a o 2x 5 5 0 e 4 7 o x 5 5 = 0 0 08 x 5 5 = z a 8 1x5 5 = 0 5 59 x 5 5 = 2 f d 2x 5 5 = 0 max 5 5 = 3 5 2 3 x 5 5 = o f f ：1 3x 5 5 = 3 a 7 4 x 5 5 = 1 5 4cx 5 5 = 3 f c 5 x 5 5 昌1 a 9d x 5 5 = 4 5 1 6x 5 5 = 1 f eex 5 5 = 4 a 6 7 x 5 5 = 2 5 3f x 5 5 = 4 f b 3 、方案设计 x c 4 0 0 0 系列f p g a 的目标体系结构非常适合这种常系数乘法技术： 可配置逻辑块( c l b s ) 包括执行2b i t 加法的所有逻辑，还有一个到邻 近c l b s 的快速进位。设计时可用最小面积产生最优化的加法器。 任何c l b 都能被用来产生r a m 或r o m 。在不同情况下，一个c l b 能 配置成3 2 xlb i t 或1 6 ( 2 b i t 的存储器。任何数据宽的r a m 或r o m 能通过合并这些小的元素来实现，对在乘法器中建造查找表来说非常理 想。 建造查找表 在8 b i t 的例子中查找表必须提供从0 到1 5 倍的被乘数的值。这样的乘积 有1 2 个b r f 的宽度( 4 + 8 ) 。这需要6 个c l b s ，如图5 所示。 第1 8 页 国防科学技术人学硼f 究生院学位论文 4 4 一r d 1 1 p l o 曲 呻 p 7 d e 略 d 田 瞳 p 1 叩 i = c l b 图5 用6 个4 0 0 0 系列的c l b s 形成1 2 b i t 宽的查找表 每个c l b 存储器的数掘内容* ；是跨过所有乘积的位片，如8 5 ( 十进制) 的乘 法表所示( 见表2 ) 。必须对每个内存片用相关的数据编程。 以前常用的方法是，在一个基于r a m 的混合乘法器中，用一个简单的状态机 来控制一个计数器和累加器，它们把适当的数据写入内存单元。不过，当用r o m 表设计一个固定系数乘法p , s f i j h q 候，设计者必须规定存储器的内容。见表2 。 表28 5 ( 卜进制) 的查找表的位片数据 a d d r e 刚sd a 协 磷 呻d 5 p 4 d 3 p 2 d 1d o i h o x )i h 似) d 1 1 p 1 0p 9 d 8 0 x 5 5 = o o o =0000 0 ，麓 oooo0oo 1x 5 5 = 0 5 5 =0000 o 鬻 1 一 、 1o101 2x5 5 - 0 a a o000 a 臻 o 、 to1o 3 x5 5 = 0 f f to000 a 露 11 、 1 111 4 x5 5 = 1 5 4 =000 1 纛瓣 lo1 鼍 1o0 5 x6 5 a 1 9 -0001 ：砉_ i 辫 ot0l 、001 6 x5 5 - 1 f e 一0d0 目鬻 111 ， 10 7 x 5 5 ；2 5 3 =0010 7 静獭 1010 、 11 8x5 5 = 2 a 8 =0o10 。飘缀h t0 叭 0o gx5 5 。2 f d =0010 1 1 辫 1 1 1 ，l 0 1 ax5 5 e3 5 2 =0d 1 o 黟 1 o n 1001 10 bx5 5 ；3 7 。0o11 1 # ， 01 、00111 cx5 5 = 3 f c =0011 s 11 i 1l10o dx5 5 2 4 5 1 =01o0 o t 。 1o1000 1 ex5 5 - 4 a 6 =010o 毋酴 0 00170 fx5 5 - 4 f b -0 1o0 薅戮 11 1 、0 1 旦一一 11 11011011o11o1 o0 d 7 = 呻6 c 第1 9 页 国堕型堂垫查奎堂业塑尘堕堂堡堡塞 一一 4 、i 殳汁实现 自动瓶局布线软件已经发展了许多年，虽然还不够完善，但在大多数场合下， 能够完成常见设计的低层综合。不论如何设计，设计结果总是要形成“网表”描 述。) ( i l i n x 的网表结构( 婚) 是一个普通的a s c i i 文件，可以用任何字处理软件 进行编辑。我们直接编辑这个网表文件见图6 。 i - - 鸷i n ：t i 。1 7 0 ii - - i 一 一_ 一，i i一 一一i i 一：l 慧：瓣 s y m l p 以r o m 9 c h 帅r 洲l e x l u b v 目札o d e f - r o m r l o c - r i c o , i n i t 2 a t f n a o , i x o n 1 i 1 刚 毛i x 2 一n a s , i x 3