（电子科学与技术专业论文）基于循环流水化的粗粒度可重构体系结构研究.pdf

国防科学技术大学研究生院学位论文 a b s t r a c t i nr e c e n t y e a r s ，c o a r s e g r a i n e dr e c o n f i g u r a b l e a r c h i t e e t o r e sh a v eb e c o m e i n c r e a s i n g l yi m p o r t a n ta l t e r n a t i v e sf o ra c c e l e r a t i n gm u l t i m e d i aa p p l i c a t i o n s m o r ea n d m o r ec o a r s e - g r a i n e dr e e o n f i g u r a b l ea r c h i t e c t u r e sh a v eb e e np r o p o s e d c o a r s e - g r a i n e d r e c o n f i g u r a b l ea r c h i t e c t u r e sb c o o m ei m p o r t a n td u et oi t sc o m b i n a t i o no ft h ea d v a n t a g e s o fb o t ha s i c sa n dg e n e r a lp r o c e s s o r s h o w e v e r , r e c e n ta r c h i t e c t u r e sh a v ec o m p l e x p r o c e s s i n ge l e m e n t sa n dn e t w o r kw i t h o mu t i l i z i n gt h ec h a r a c t e ro fp r o g r a m s t h e r e s e a r c ho ft h i sp a p e rt r y st od e s i g nac o a l f s e g r a i n e dr e c o n t i g a r a b l ea r c h i t e c t u r ew i t h s i m p l ep r o c e s s i n ge l e m e n t sa n dn e t w o r k , w h i c hc a np u tt h e a r c h i t e c t u r ea n d c o m p u t a t i o nt o g e t h e r i nt h i sp a p e r ，w ep r o p o s eac o a r s e g r a i n e dr e c o n f i g u m b l ea r c h i t e c t u r en a m e d l e a p ( l o o pe n g i n eo na r r a yp r o c e s s o o ，w h i c hi sb a s e do nl o o pp i p e l i n i n ge x e c u t i o n m o d e t h el e a pa r c h i t e c t u r ei sad a t a - d r i v e na r c h i t e c t u r e ，w h i c hh a sar e c o n f i g u r a b l e p r o c e s s i n ge l e m e n t sa r r a ya n dd a t am e m o r yt h a tp r o v i d e sr e c o n f i g u r a t i o n t h i s a r c h i t e c t u r ea i m st om a pt h e e x p r e s s i o ns t a t e m e n t s o fh i g hl e v e lp r o g r a m m i n g l a n g u a g e so n t op r o c e s s i n gc l e m e n sa n db u i l dap i p e l i n i n gd a t a f l o ws t r u c t u r ea c c o r d i n g t oas t a t i cd a t a f l o wg r a p h , a n da c c o m p l i s h e st a s k sa u t o m a t i c a l l ya n de f f i c i e n t l yf o r a p p l i c a t i o n s t h el e a pa r c h i t e c t u r eh a sm a n yi m p o r t a n tf e a t u r e s i th a sat e c h n i q u ep r o v i d e s l o o ps e l f - p i p e l i n i n g e x e c u t i o na n dar e c o n f i g u r a t i o nm e c h a n i s mt om a i n t a i n a p p l i c a t i o n sc o n s i s t e n c yw h i l em i n i m i z i n gt h ei m p a c to np e r f o r m a n c e t oa c h i e v el o o p s e l f - p i p e l i n i n g ，b a l a n c i n gi sp e r f o r m e dt h r o u g ha d d i t i o no f m o r es t o r a g e ( i ef i f o s ) i n e a c hp r o c e s s i n ge l e m e m t h eb a n d w i d t ho fl o c a lm e m o r yc a l lb eu l t i l i z e df u l l yf o rb e s t p e r f o r m a n c eu s i n gm e m o r ys c h e d u l i n g , a n dt h et i m ef o rd a t at r a n s m i t t i n gi sh i d e db y t h ec o n c u r r e n c yo f d a t at r a n s f e ra n dc o m p u t a t i o n t od e m o n s t r a t et h ee f f e c t i v e n e s sa n de x c e l l e n c eo fl e a pa r c h i t e c t u r e ，t h i sp a p e r p r o v i d e ss o m ec a s es t u d y so fa l g o r i t h mm a p p i n gt ot h el e a pa r c h i t e c t u r e a tl a s t ，t w o p r o t o t y p i n gp h a s e so ft h el e a pa r c h i t e c t u r eh a v eb e e ni m p l e m e n t e d o na na l t e r a f p g ae p ls s o f l 5 0 8 c 6 t h eh o s t c o m p u t e rc a nc o m m u n i c a t ew i t ht h el e a p p r o t o t y p e st h r o u g hp c ib u s ，a n dt e s t b e n c hc o d e sh a v er u ns u c c e s s f u l l y o nt h e p r o t o t y p e s k e yw o r d s ：l e a p ，c o a r s e - g r a i n e dr e c o n f i g u r a b l ea r c h r e c t u r e ，l o o p s e l f - p i p e l i n i n g ，f p g a 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1l e a p 操作集合 表2 2d i r 表示意义 表2 3 存储体的配置细节 表2 4 两种互连结构的比较。 表3 1 循环流水线。 表4 1 主机命令 1 ：! 。：! ( ) 2 1 表4 2m p e 在优化前后的综合结果。 表4 3c p e 不同设计时的综合结果比较3 5 表4 4l e a p 原型的综合结果3 5 表5 1f f t 测试性能3 9 表5 2f f t 实现的性能比较3 9 表5 3 边缘检测测试性能4 2 表5 4 边缘检测实现的性能比较4 2 表5 5 中值滤波测试性能 表5 6 中值滤波实现的性能比较 4 4 4 4 表5 7 矩阵乘测试性能4 7 表5 8 矩阵乘实现的性能比较 表5 9f d c t ，i d c t 实现的性能比较5 0 表5 1 0 量化实现的性能比较5 l 第1 i i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 五类可重构计算系统 图1 2 细粒度功能单元 图1 3 商用f p g a 的逻辑模块结构 4 4 图1 4a d r e s 可重构功能单元5 图2 1l e a p 结构框图9 图2 2 接口控制器结构框图 图2 3d m a 控制寄存器 图2 4o p t i o n s 域 图2 5 循环程序分解的结构模型 图2 6m p e 的结构模型 1l 1 ：! 1 4 1 4 图2 7m p e 的结构设计框图1 5 图2 8 二级流水地址产生器波形图1 6 图2 9c p e 的结构模型。 图2 1 0e p e 的结构设计框图 图2 1 1 数据格式 图2 1 2 带有预测位的a l u 。 图2 1 3 双存储体的结构 图2 1 4 双存储体的配置 1 6 1 7 1 7 1 8 图2 1 5 静态互连结构2 l 图2 1 6 网络拓扑结构和路由器结构2 2 图3 1 数据驱动体系结构上的循环流水化2 3 图3 2 循环自动流水化2 4 图3 3 执行模型2 5 图3 4 数据驱动型a l u 2 7 图3 5 多重配置机制2 8 图4 1p r o c s u p e r s t a r 开发板结构框图。3 l 图4 2 改进后的接口控制器3 2 图4 3 地址生成器的逻辑结构3 3 图4 4a l u 的逻辑结构3 4 图5 18 点s i n g l e t o nf f t 的数据流图。3 7 图5 2s i n g l e t o nf f t 算法c 语言描述3 8 图5 3 存储体的配置3 8 第1 v 页 国防科学技术大学研究生院学位论文 图5 4s o b e l 边缘检测算法4 0 图5 5s o b e l 边缘检测算法的数据流图4 0 图5 6 边缘检测算法映射时局部存储器的使用4 1 图5 7 中值滤波算法c 语言描述4 3 图5 8 奇偶排序法4 3 图5 9 求中值的奇偶排序法4 3 图5 1 0 矩阵乘4 5 图5 “矩阵乘在3 1 0 的l e a p 的映射( 原始方案) 4 5 图5 1 2 矩阵乘的存储调度4 6 图5 1 3 矩阵乘在3 1 0 的l e a p 的映射( 优化方案) 4 7 图5 1 4 视频编码和译码系统框图4 8 图5 1 5f d c t 和i d c t 算法c 语言描述4 9 图5 1 6f d c t i d c t 在3 l o 的l i ；a p 的映射4 9 图5 1 7 帧内量化函数5 l 图5 1 8 量化函数数据流图5 l 图5 1 9 量化矩阵 图5 2 0l e a p 与微机和d s p 的加速比5 2 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所儆的任何贡献均已在论文 中作了明确的说明并表示谢敖 。 学位论文题目：基王筮叠逋盔垡盟担撞廑互重掏住丞丝控噩容 学位论文作者签名： 勉蔓! 拄日期：2 一。6 年i t 月，2 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 。 学位论文题目：基王筮巫遣壅丝煎担整度互重控堡丞箜控盈究 学位论文作者签名： 作者指导教师签名： 日期：2 口口6 年1 1 月，2 日 日期：0 口口6 年t 1 月p 日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 研究背景 当前，越来越多的应用领域同时要求计算的高性能和灵活性，a i s c 和微处理 器两种实现方式显示出了各自的不足。计算密集的应用需要比以前更多的计算能 力来支持，比如科学计算、流视频、图像识别和处理以及交互式服务。同时，对 功耗、生产成本和上市时间的需求也在日益增长，特别是在嵌入式处理器领域。 在面对这些挑战的多种计算实现技术中，可重构计算成为其中最有优势的计算形 式。 1 1 1 三种实现技术 要满足当前计算需求可能采用的三种实现技术【1 1 1 2 1 ： ( 1 ) 高性能微处理器。微处理器是一种使用软件编程的方法，而且是一种最 灵活的解决方案。处理器执行一组指令来完成计算任务，通过改变软件，在不改 变硬件的情况下改变系统的功能。对于一般的处理器来说，这种灵活性是由性能 的降低作为代价。高性能处理器提供了一种解决当前计算需求的现成的方法，然 而对于多数应用来说，单处理器往往还是不能满足要求。另外，大量功耗和昂贵 的价格使其更不能满足嵌入式系统的要求，就算微处理器按照摩尔定理，密度每 1 8 个月翻一番，这样的速度也很难赶上嵌入式应用的需求。 ( 2 ) 专用集成电路。专用集成电路( a s i c ) ，也就是使用“硬连线”把一组 独立的部件连接在一起形成板级的解决方案。a s i c 被设计成完成特定的计算，其 执行速度特别快，效率特别高。不像软件实现，a s i c 提供了一种对大多数应用都 能实现大量并行性的自然的实现方式。另外，a s i c 不需要有串行的取指过程，这 串行的取指成了约束微处理器性能的致命的缺点。更重要的，a s i c 比其他的实现 方式更能减少功耗。然而对于嵌入式应用a s i c 往往是不灵活、不经济的。这主要 由两个因素决定：l 、生产一片a s i c 的价格相当昂贵，最多可达l 百万美元【3 】；2 、 开发定制电路所需要的时间相当长。这些因素决定了开发和设计a s i c 需要相当高 “非重发性工程成本”( n r c 成本 4 b 。 ( 3 ) 可重构计算系统。一个典型的可重构计算系统由一个或多个处理器和可 重构功能单元阵列组成。处理器执行串行或非关键代码，而能够有效地映射到硬 件的代码均在可重构阵列上运行。像定制的专用集成电路一样，映射到可重构阵 列上的应用可以有效地利用硬件带来的并行性；同时，嵌入式设计者能够在可重 构阵列上得到功能单元和存储单元恰当的组合，从而可以提供满足不同应用的计 第1 页 国防科学技术大学研究生院学位论文 算结构。与a s i c 不同的是，不必为不同的应用设计不同的可重构阵列，这就意味 着可重构计算系统能够减少a s i c 实现时的设计时间；另外可重构阵列的功能单元 可以改变，随着嵌入式系统使用环境的改变，功能单元可以很快地匹配新的环境。 比如，使用可重构阵列的设备在某种模式时可以实现大量矩阵乘运算，在另一种 模式下，又可以实现大量的信号处理。 虽然可重构计算系统有着很多优势，对于设计者来说，同样需要注意可重构 系统带来的一些限制。比如：在位级的走线虽然灵活，但它占用了大量的硅片面 积，对于不需要现场升级的应用来说，a s i c 或门阵列便可以以很低的代价得到很 高的性能。 1 1 2 可重构计算 一个典型的可重构计算系统由一个或多个处理器和可重构功能单元阵列组 成，处理器运行不能在可重构阵列上有效实现的操作，比如数据相关控制和可能 的存储器访问。可重构系统的编译包括了辅助编程者手工进行电路映射的工具， 以及使用高级语言生成配置文件的工具。可重构系统的设计过程可以分为以下几 个部分： ( 1 ) 软硬件划分。设计者需要把一个程序分成在硬件上实现的部分和在主机 ( h o s t ) 上用软件实现的部分。以可重构硬件为目标的计算会被综合成门级电路描 述或寄存器传输级描述。 ( 2 ) 工艺映射。门级电路描述或寄存器传输级描述的电路被映射成可重构硬 件中的逻辑模块，这些模块放置在特定物理模块中，然后使用可重构走线把各个 模块连接起来。 ( 3 ) 配置。电路等待着被实时地配置在硬件上，有时需要预先地把电路配置 完毕。 值得注意的是，可重构计算仍是一个需要完善的领域。在开发一个可重构系 统时，仍然面临着许多挑战： ( 1 ) 可重构阵列的结构，以及可重构阵列、处理器和存储器三者之间的接口 的结构必须非常有效。一些可重构计算系统由商用的f p g a 实现【5 - 9 1 ，另外一些采 用定制的可重构硬件实现【1 3 1 。 ( 2 ) 计算机辅助设计和编译工具的开发。这些涉及到如何对软硬件进行划分， 何时对硬件进行重构，如何改变功能单元，还有算法的描述如何有效地映射在可 重构硬件上。 可重构计算最早于1 9 6 3 年出现，加里福尼亚大学的g e r a l de s t r i n 首先提出可 重构计算的概念1 2 4 1 。8 0 年代才渐渐出现可重构系统原型，可重构技术的发展主要 第2 页 国防科学技术大学研究生院学位论文 受工艺水平的限制。直到9 0 年代后期，先进的v l s i 技术促进了多种可重构数据 通路的设计，使可重构计算系统上的很多应用的性能都超过了通用微处理器和 a s i c ，可重构计算才真正成为研究的热点。 1 2 研究现状 工艺的持续发展和硬件设计自动化水平的不断提高使可重构计算的研究在近 1 5 年中蓬勃发展，可重构计算已成功应用于诸多领域，针对不同应用领域的计算 特点，可重构系统在灵活性和高效性方面进行了合理折衷。 1 2 1 可重构系统分类 典型的可重构系统由一个或多个处理器、可重构单元阵列和多个存储器组成。 根据可重构单元阵列与c p u 之间的耦合度，可以把可重构系统分为五类【l 】( 见图 1 ) 。 在图1 1 a 中，可重构阵列由一个或多个独立的器件组成，主机使用自己的输 入输出接口和可重构阵列通信。这种结构中可重构阵列和处理器之间的数据传输 相当慢，因此这种结构只适用于不需要处理器交互的应用，硬件仿真系统往往属 于这种结构。图1 1 b 、1 1 c 中的两种结构，通信开销低于第一种结构。图1 1 d 所 示结构中处理器和可重构阵列紧紧地耦合在一起，可重构阵列成了处理器的一部 分，为处理器提供生成定制指令的可重构功能单元。图1 1 e 中，处理器被嵌入到 了可重构阵列中，这个处理器可以是硬核，也可以是使用可重构单元实现的处理 器软核。五种可重构计算系统中第一种是最常用的，往往用于商业性的可重构平 台的设计。 1 2 2 可重构功能单元 可重构体系结构被分为粗粒度可重构体系结构和细粒度可重构体系结构。细 粒度可重构体系结构由可以实现位级操作的功能单元组成，f p g a 便是典型的结 构；粗粒度可重构体系结构中处理单元主要是执行字节级操作的算术逻辑功能单 元。我们简要介绍这两类功能单元。 许多可重构系统使用商用f p g a 作为可重构平台，这些f p g a 包括3 到6 个 查找表，每个查找表作为一个细粒度功能单元。图1 2 说明了查找表的结构，它能 够实现最多3 个输入的功能单元，多个查我表组合在一起便形成了更大的功能单 元。图1 3 所示是两种典型的逻辑单元，一种是a l t e m 的逻辑阵列模块( l a b ) 1 6 1 ， 另一种是x i l i n x 的可重构逻辑模块( c l b ) 9 1 。图1 3 a 中l a b 由十个l e 组成， 第3 页 国防科学技术大学研究生院学位论文 每个l e ( 逻辑单元) 便是一个查找表；图1 3 b 中c l b 由四个s l i c e 组成，s l i c e 包 含了两个查找表。 n “均蚺 p t o o o 曲a g 峨 a 外部独立处理单元 c 协处理器 b 附属处理单元 口。口口口口口口 口口 ad l a c p u 口 芑 。 口 g 同窨2 o l j a 口口口口口口口a e 嵌入处理器的可重构阵列 图1 1 五类可重构计算系统 d 可重构功能单元 图1 2 细粒度功能单元 第4 页 口口口警一籼一口 口 耕椭 一c 一口罢晨 国防科学技术大学研究生院学位论文 乱a l t e r a 逻辑阵列模块 b x i l i n x 的可重构逻辑模块 图1 3 商用f p g a 的逻辑模块结构 含有查找表的f p g a 非常灵活，可以实现任何电路，但与粗粒度相比细粒度 结构占用更多的面积，带来更大的延迟和更多的功耗。粗粒度体系结构虽然缺少 灵活性，却能有效地实现更强大的功能单元。以a d r e s 结构为例子( 图1 4 ) ， 可重构功能单元包含了一个带有两个寄存器文件的3 2 位a l u ，a l u 可以配置成 实现加、乘运算或其他逻辑功能的功能单元【l l 】。 o n t o u 协3 2 艄i 嘲协3 2 - b i t i n p u l s 1 一b t麓- b l p r e d a n l e r i n d 图1 4a d r e s 可重构功能单元 1 2 3 粗粒度可重构体系结构 粗粒度可重构体系结构与细粒度结构相比，除了在面积和功耗方面的优势外， 在配置存储器和配置时间的需求上也有很大的降低，同时它还降低了布局布线问 题的复杂度。德国k a i s e r s l a u t e m 大学的h a n e n s t e i n 教授对过去1 0 年来的粗粒 度可重构体系结构进行了总结，认为粗粒度可重构平台由于弥补了a s i c 和微处理 器各自的不足，已经处于主流位置【2 5 l 。下面介绍几种粗粒度可重构体系结构。 r e m a r c 【l 卅和m o m h o s y s 【lo j 具有相似的结构和特点，它们都属于由一个r i s c 第5 页 国防科学技术大学研究生院学位论文 处理器和可重构单元矩阵组成的典型可重构体系结构。m o r p h o s y s 是动态重构，而 r e m a r c 是静态重构：m o r p h o s y s 中同一行和同一列的重构单元r c 共享配置程 序，而r e m a r c 中每个重构单元( n a n o 处理器) 拥有自己的配置指令，全局控 制单元控制每个重构单元同步执行。 a d r e s t “j 是一种把宏粒度可重构矩阵和v l i w 处理器集成在一起的单一结 构，a d r e s 的研究者认为通过把宏粒度可重构矩阵和v l i w 处理器紧紧地耦合在 一起，可以提高性能，简化编程模型，并且可以减少通信代价，达到资源共享。 x p p i l2 j 是一种由自适应计算单元p a e 组成的层次化阵列。常规的流处理应用 可以很有效地在这种结构上实现，非常规的应用也可以通过分布的“事件信号” 对数据流的控制来提高执行效率。 p 结构与其它结构最大的不同在于其自动的 数据处理机制和层次化的配置协议，可以实现全局的或局部的实时重构和自重构。 另外，也有许多人在研究如何解决在设计粗粒度可重构体系结构时遇到的问 题。文献【2 7 】针对如何分配功能单元来平衡性能和面积约束提出了多种算法，设计 者可以使用这些技术设计出未来的粗粒度可重构体系结构。第一种算法在保证硬 件性能要求的条件下生成结构，第二种算法允许设计者牺牲灵活性来达到更大的 吞吐率，最后一种算法利用更灵活的面积约束来生成有效的结构。将来，设计者 可以利用c a d 工具设计专用领域的粗粒度可重构体系结构。 1 3 1 研究内容 1 3 研究内容与意义 当前粗粒度可重构体系结构的研究并没有结合程序特征，处理单元和网络结 构较为复杂。本课题的研究目标是试图研究一种结构直接针对以循环为核心的应 用程序在运行时的特征，它有着简单的处理单元和网络结构，并通过灵活的重构 机制达到结构与计算的最优结合。 本文的研究内容主要包括以下几个部分： ( 1 ) l e a p 体系结构的设计。l e a p 体系结构是一个加速循环执行的可重构 体系结构，这是在以往的阵列处理器体系结构【2 8 】1 2 9 1 研究成果上进一步研究提出的 新型结构，其主要部分是处理单元阵列，处理单元的设计影响整个计算性能；同 时还需要考虑如何选择互连网络，局部处理器的设计也关系着是否能够提供足够 的带宽和访存形式，作为协处理器，l e a p 还需要有高性能的接口控制器。 ( 2 ) 循环自动流水化技术。研究循环流水化的特点；研究l e a p 结构在硬件 上如何保证从高级语言到体系结构的直接映射；研究循环与流水线的直接关系； 研究如何实现循环自动流水化技术。 第6 页 国防科学技术大学研究生院学位论文 ( 3 ) 基于f p g a 的l e a p 原型设计和算法映射。研究如何针对f p g a 的特性 进行原型设计；研究如何对系统进行优化；研究如何把算法映射到结构上；如何 充分利用结构的特性进行数据重用和存储调度；如何对应用进行性能分析。 1 3 2 研究意义 计算机研究者一直在寻找一条途径，它能够在速度和通用性之间寻找一种平 衡。可重构处理器设计方法充分利用了这一事实：计算类程序运行的大部分时间 花费在一部分很少的代码上。对于很多应用来说，硬件加速器比通用处理器能够 显著地提高性能，这种设计方法在速度和通用性之间找到了一种至今看来是最好 的平衡。可重构处理器的本质在于它是一种通用的硬件加速器。 可重构计算建立在可编翌逻辑器件基础之上，能够根据应用的计算特点。通 过改变硬件连接关系，达到硬件结构与计算的最优结合。从目前的研究现状来看， 基于传统f p g a 器件实现的可重构计算虽然证明了可重构计算的有效性，但是研 究表明，f p g a 器件在资源利用率、硬件重构速度以及算法自动综合等方面表现仍 然不很理想，需要在新的模型下提出新的结构，才能解决其固有问题。 本文的主要贡献在于，在程序特征的基础上，提出了新的基于流水化的可重 构计算模型和程序执行模型，提出了新的可重构体系结构以及配套的应用程序映 射方法，并提出了灵活的数据重用和存储调度策略。本文阐明了如何利用可重构 思想支持流水线执行方式，本文所描述的l e a p 体系结构能在实际应用中作为图 形加速器、m p e g 压缩加速器使用，而且还可以广泛应用于嵌入式应用领域。 1 4 论文结构 第一章是绪论，说明了课题的研究背景，在介绍国外一些相关研究的基础上， 概括了本文的主要研究内容和研究意义，最后给出了文章的组织结构。 第二章介绍了l e a p 体系结构框架，并对其各个部分的设计进行了说明，主 要介绍了系统控制、处理单元、局部存储器和互连网络。 第三章介绍了循环自动流水化技术，简要介绍循环流水化领域的相关研究， 然后从硬件支持角度说明了循环自动流水化的实现。 第四章介绍了基于f p g a 的l e a p 结构原型实现和优化，先说明了原型实现 时的结构框架，然后针对m p e 和e p e 进行了优化。 第五章介绍了几个算法在l e a p 上的映射，其中包括f f t 算法、s o b e l 边缘检 测算法、中值滤波算法、矩阵乘、f d c t i d c t 和量化。 第六章总结了本文所作工作，并对将来工作作了迸一步展望。 第7 页 国防科学技术大学研究生院学位论文 第二章l e a p 体系结构 近年来，许多粗粒度可重构体系结构被作为加速计算密集程序执行的协处理 器来使用，已经在各个应用领域表现出很强的能力，甚至表现得比传统上使用的 d s p 、a s i c 和s o c 更优秀。l e a p 结构与一般粗粒度可重构体系结构最主要的区 别在于它能够把高级语言直接映射到处理单元阵列上，通过操作在阵列结构上的 分布，处理单元阵列能够自动地完成循环的计算任务。这种结构不需要集中的控 制，没有集中的多端口寄存器和数据存储体，它紧密结合程序的特征，极大地开 发了程序的循环级并行、指令级并行和任务级并行。l e a p 结构特别适合于具有流 处理特征的算法的加速，可以应用于多媒体、d s p 和图像处理等领域。 2 2 1 结构和组成 2 1l e a p 体系结构概述 l e a p ( l o o pe n g i n eo na r r a yp r o c e s s o r ) 是一个加速循环执行的可重构阵列处 理器体系结构，它由多个计算单元和访存单元组成计算阵列，计算单元仅是一个 具有指令和操作数存储功能的a l u ，计算单元之间通过高速通道连接，支持循环 直接映射到循环阵列上执行。l e a p 结构能够有效开发循环内部的语句级并行和循 环间循环片级并行，为多种应用提供了高性能可重构计算平台。 l e a p 结构是由s c 处理器( 或主机) 和可重构单元阵列组成的典型粗粒度 可重构体系结构，它拥有1 6b i t s 的数据通道和4 3b i t s 的控制通道( 包括4 0b i t s 配 置总线和3b i t s 启动总线) 。图2 1 描绘了l e a p 的结构框图，它包括四个部分： 接口控制器、数据( 局部) 存储器、处理单元阵列和网络。主机通过接口控制器 与l e a p 进行通讯，并与l e a p 共享外部存储器。多个l e a p 阵列可以串在一起 组成功能更强的处理阵列。 配置稻寤动馨线 处理单元阵列( p e a ) 同一行的p e 挂在了同一条总线分支上，总线采用离散 的结构有利于降低总线延迟。配置总线用于传递配置信息和配置加载使能，启动 总线用于控制阵列的运行。 处理单元 处理单元( p e ，p r o c e s s i n ge l e m e n t ) 是对数据进行处理的功能部件，为了达 到存储操作和计算的分离，p e 被分成了两种；计算处理单元( c p e ) 和存储器处 理单元( m p e ) ，n a p e 专门负责存储器访问，c p e 仅具有计算功能。 局部存储器 第8 页 国防科学技术大学研究生院学位论文 某些结构中存储器被同一行或同- n 的p e 所共享，l e a p 的局部存储器仅被 相邻两个n a p e 共享，这样是试图把存储操作和计算完全分离从而得到更好的性能。 局部存储器用于缓存数据，m p e 可以直接从局部存储器中取得数据，并把结果存 入局部存储器。 互连网络 m p e 一端直接与局部存储器相连，一端通过静态s w i t c hm a t r i x ( 开关矩阵) 网络与c p e 相连，所有c p e 也被s w i t c hm a t r i x 网络连接在一起，整个网络形成2d t o r u s 网。循环运行时m p e 与c p e 的连接关系是固定的，可以通过互连网络的配置 信息确定这种连接关系。 接口控铂器 l e a p 结构作为协处理器需要与主处理器连接，接口控制器完成配置信息的加 载、数据的加载和结果返回，以及对协处理器发送运行指令，对循环运行状态进 行监控。 每个m p e 、c p e 和网络都有多层配置，局部存储器被分成多个独立的离散的 模块，通过链表式d m a 机制实现数据加载、配置加载和运算的重叠执行。 f r o m t o h o s t p r o c e s s o r 图2 1l e a p 结构框图 2 2 2 操作集合 l e a p 结构支持的操作指令集合分为整数算术运算( 有符号) 、逻辑运算、整 第9 页 国防科学技术大学研究生院学位论文 数测试、特殊操作( 无符号) 和分支操作( 见表2 1 ) 。特殊操作包括了图像处理 中一些常用的操作；三个分支操作把控制相关转变成数据相关，适合在数据驱动 的l e a p 结构上采用。 表2 1l e a p 操作集合 2 2 3 主要特点 l e a p 结构具有以下特点： 硬件上支持循环的自动流水化，极大地开发了程序的并行性； 特别适合于具有流处理特征的算法； 能够支持计算和数据移动同时进行，隐藏数据传输时间； 可以形成多种规模的处理单元阵列； 第l o 页 国防科学技术大学研究生院学位论文 每个p e 具有深度为1 6 的指令存储器( 配置存储器) 存储配置信息； 具有优化的1 6 - b i t 功能单元，可以实现多种特殊的运算功能： 包含了规约指令的指令集( 操作) ，可以实现快速的规约操作； 具有可重构能力的局部存储器和数据网络； 采用了屏蔽位的存储地址模式，以流水的方式生成地址，提高了系统频率： 能够快速的进行配置切换，有利于提高性能； 硬件实现简单。 2 2 1 接口控制器 2 2 系统控制 接口控制器直接接收主机传送来的数据、命令和配置流，把数据和配置流暂 存于外部存储体，当系统进行配置和运行时，外部存储体的数据和配置流分别送 到了数据( 局部) 存储器和p e 的指令存储器( 图2 2 ) 。命令通道用于分派各种 命令给相应的单元执行各自的动作。当主机需要检测l e a p 运行状态或d m a 状态 时状态信息被送入用于缓存消息的消息队列，这个消息队列把消息送给主机。数 据和其他需要反馈给主机的信息共用了这个数据通道。 3 1 图2 2 接口控制器结构框图 1 61 50 图2 3 d m a 控制寄存器 d m a 控制器完成局部存储器( 或其它数据通道) 和外部存储器的数据传输。 d m a 控制器包括d m a 控制寄存器和d m a 传输引擎，d m a 控制寄存器接受主机 第1 i 页 8器02盘长宝8 oq2q p砷。口ii_口置 国防科学技术大学研究生院学位论文 的配置，d m a 传输引擎独立于主机的控制，d m a 控制寄存器如图2 3 所示。图 2 4 所示o p t i o n s 域的内容，“d i r ”表示d m a 的数据传递方向，含义见表2 2 。 3 l1 81 71 6 图2 4 0 p t i o n s 域 表2 2 d i r 表示意义 2 2 2 状态寄存器 在一些粗粒度可重构体系结构中，局部和全局的寄存器文件对其性能有重要 的影响【蚓，而在l e a p 中，由于其流水线的执行方式，并不需要有全局的寄存器 文件供所有或部分p e 使用，仅有一些状态寄存器放在了接口控制器中。主机需要 检测l e a p 的各种状态，从而控制l e a p 的某些操作的进行和保证l e a p 正确运 行。l e a p 需要向主机提供的状态包括： ( 1 ) 每一个m p e 的状态( c p e 无任何状态标志) ，该状态告诉主机每个m p e 被赋予的任务是否执行完毕。 ( 2 ) d m a 传输状态，该状态告诉主机d m a 传输是否执行完毕，是否可以开 始新的d m a 传输。 另外，主机还可以得到d m a 控制寄存器的内容。 2 2 3 控制通道 控制通道包括配置总线和启动总线( 图2 1 ) 。主机通过配置总线对m p e 和 c p e 进行配置信息的传输，并加载配置；启动总线用于在m p e 和c p e 配置之后启 动系统的执行，即启动映射在阵列中的循环的执行。 4 0 b i t 配置总线包括： 3 2 b i t 配置信息总线； 1 - b i t 配置信息有效信号： 4 - b i t 指令r a m 地址总线； 1 - b i t 配置信号； 2 b i t 循环序号。 当某p e 运行时，p e 同样允许接口控制器通过配置信息总线把配置信息缓存 第1 2 页 国防科学技术大学研究生院学位论文 在该p e 的指令存储器中。这样可以做到对配置时间的隐藏，加上l e a p 结构配置 信息量少的优点，在大部分应用中可以做到配置信息的传输不会对性能产生任何 影响。配置信息中含有相应的标志表示其对应的p e 的号，当对某个p e 进行配置 时，不会对其他p e 产生影响。指令r a m 地址总线、配置信号和循环序号一起对 p e 进行可重构操作，接受这个操作的p e 的指令存储器中应该保存有循环序号所 对应的配置信息( 称为指令) 。在l e a p 结构中重构的粒度对应于单个循环，是 完成某个循环的所有p e 而不是单个p e ，从而增大了重构的灵活性。这种方式进 行的一次重构对应于一个循环的重构，这个重构的过程仅需要几个周期( 图z i ) 。 这种策略的好处是当一些p e 接收配置流信息时，另一些p e 可以同时进行重构。 3 b “启动总线包括： l - b i t 启动信号； 2 - b i t 循环序号。 启动操作的对象为n a p e ，启动的目的是把数据流的阀门打开，循环结束时阀 门自动关上。启动操作的粒度对应于单个循环，所以需要使用循环的序号来指出 此次所启动的循环，从而不会对已经启动或不需要启动的循环产生影响。多个循 环可以相继启动，间隔仅为1 个时钟周期。 利用配置总线可以快速地把配置信息传给每一个p e ，在设计总线时必须考虑 到总线带来的延迟和运行可以达到的最大频率之间的折中。为提高总线频率我们 采用了分布式的总线形式，并在总线的节点上插入了一些寄存器( 图2 1 ) ，这影 响到了数据在总线上的传输延迟。 2 3 处理单元 l e a p 体系结构通过流水线的执行方式把循环映射在p e 阵列上，循环程序自 身被分解为多个部分由各个p e 实现。图2 5 说明了循环程序进行分解的思想，这 种分解是循环映射到p e 阵列上很自然的过程。“循环状态机”对应于f o r 语句 中的循环控制条件，运算阵列对应于f o r 语句中循环体；“循环状态机”控制着 从存储器中取数和存数，运算阵列以流水线的方式对存储器中取出的数据进行运 算。 循环的这种流水线执行方式( 第三章将详细介