（电路与系统专业论文）二维阵列型可重构计算设计空间搜索方法研究.pdf

浙江大学博士学位论文 摘要 摘要 可重构计算作为一种新的高性能计算解决方案，它具有较高的性能和灵活 性，是通用处理器和a s i c 的折衷。由于具有较高的灵活性，可重构计算的设计 空间巨大，为某个特定的应用领域设计一个优化的可重构计算体系是一项十分复 杂的任务。在可重构计算体系设计初期，搜索可重构计算体系的设计空间，选择 一个优化的可重构计算体系是一项十分重要的研究工作。本文研究了二维阵列型 可重构计算的设计空间搜索方法。 为了使设计空间搜索方法不依赖于任何具体的可重构计算体系，本文定义了 描述可重构计算体系的结构特征参数，并提出了可重构计算体系的层次型参数模 型。层次型参数模型既能反映可重构计算体系的结构特征，又能反映可重构计算 体系的层次性。层次型参数模型具有良好的灵活性，能够描述不同类型的二维阵 列型可重构计算体系。由于在高层次对可重构计算体系的结构特征进行数学抽 象，层次型参数模型能够提高可重构计算体系的设计空间搜索速度。 在可重构计算设计空间搜索过程中，应用领域中的每个算法对可重构计算体 系的互连资源提出了不同的需求。论文研究了可重构计算体系的互连资源估计问 题。在建立应用算法网表布线随机模型的基础上，提出了基于随机模型的可重构 计算体系的互连资源估计方法，从而能够估计应用领域中的各个算法在可重构计 算体系上实现时所需要的各种互连资源的数目，确定了可重构计算体系的互连资 源。 可重构功能处理单元阵列是可重构计算体系的核心部件。论文研究了可重构 功能处理单元阵列的设计空间，推导了可重构功能处理单元阵列的面积、性能和 功耗的估计公式。通过分析应用算法的变换方法、应用算法在可重构计算体系上 的执行模型以及性能估计方法，给出了性能约束的可重构功能处理单元阵列设计 空间搜索方法，从而使可重构计算体系的设计空间搜索方法能够跨越静态可重构 计算体系和动态可重构计算体系，并能够在满足应用算法性能约束的前提下，为 应用领域中的算法搜索一个最优的可重构功能处理单元阵列。 存储器结构是可重构计算体系的重要组成部分，其影响应用算法在可重构计 算体系上的执行时间。论文讨论了存储器结构的设计空间搜索方法，研究了存储 器结构中局部数据存储器容量、配置上下文存储器容量和局部数据存储器与可重 构功能处理单元阵列之间的接口带宽，推导了局部数据存储器容量和配置上下文 存储器容量的最大值以及局部数据存储器与可重构功能处理单元阵列之间接口 带宽的最大值，最后提出了面积约束的存储器结构设计空间搜索方法，在搜索域 选择性能最优的存储器结构。 浙江大学博士学位论文 关键词二维阵列型可重构计算体系，层次型参数模型，互连资源，可重构功能 处理单元阵列设计空间搜索，存储器结构设计空间搜索 塑垩查兰堡主堂垡堡苎 塑蔓 a - b s n ? a c t r e c 帆f i g i l r a b l ec o m p u t i n g i san e w p a r a d i g mf o rc u e n th i g hp e r f o r m a n c e c o m p u t i n 岛w h i c hp r o m i s e sa i ii n t e m e d i a t ct r a d e - o f fb e t 、】l r e e a p p l i c a t i o ns p e c i f i c i n t e 掣a t e dc i r c u i l s ( a s i c s ) a i i dg e n e r a lp u r p o s em i c m p r o c e s s o r s i tp m v i d e s p o w e r f i l lf l e x i b i l i t ya n dp e r f o n n a n c e b e c a u s eo f i t sf l e x i b i l i t y ，r e n f i g l l r a b l e c o m p u t i n ga r c h i t e c t l l r e ( 狐) h a sa v 鹞td e s i 舯s p a c e ，a n di ti sah a r dt a s kt od e v e l o p a no p t i m i z e dr c af o ra p p l i c a t i o ns p e c i f i cd o m a i n re x i s t sv e r yh i g hv a l u et os e a r c h 也ed e s i 口s p a c eo fr c aa n dg u i d ei t sd e s i 辨a ta ne a i l ys t a g c t h ed i s s c n a t i o n e m p h a s i z e so nt h em e t h o df o rt w od i m e n s i o na r r a yb a s e dr c ad e s i g ns p a c e e x p l o r a t i o n i i lo r d e r t om a k ed e s i g ns p a c ee x p l o r a t i o nm e t t i o di n d e p e n d e mo na n yc o n c r e t e r c a ，t h ed i s s e n a t i o nd e f i n e sas e to fa r c h i t e c t u r a lp a r a l n e t e r s ，w h i c hc h a r a c t e r i z e d i 惯b r e n tr c a b a s e do ni t ，h i e r a r c h i c a lp a r a m e t e rm o d e lf o rr c ai sp r c s e n t e d ，w h i c h n o to n 】yc h a r a c t e f i z e sr c a ，b u ta j s o 如s c b e st h ea r c j l j l e c t u r c sh i e 删h y i l h a s p o w e r f u ln e x i b i l i t y ，a i i dc 孤d e s c r i b ed i f f e f e i l tt w od i i i l e n s i o na r r a yb a s e d r c a 。 b e c a u s em a m e m a t i c a la b s t r a c t i o nf b rr c ai sa th i g hl e v e l ，h i e r a r c h i c a lp a r a m e t e r m o d e la c c e l e r a t e sr c a d e s i 印s p a c ee x p l o r a t i o n d u r i n gd e s i g ns p a c ec x p l o r a t i o n ，e a c ha l g o r i t h l i lm a k e s ad i f f c r e n td e m a n do c o n n e c t i o nr e s o u r c e so fr c a c o n n e c t i o nr c s o u r c e se s t i m a t i o nf o rr c ai sd i s c u s s e d i nt h ed i s s e n a t i o n b ye s t a b l i s h i n gs t o c h a s t i cm o d e lf o fa p p l i c a t i o na l g o r i t h mn e t r o u t i n 吕am e t h o df o re s t i m a t i n gr c a c o n i l e c t i o nr e s o u r c eb a s e do ns t o c h a s t i cm o d e l i s 舀v e n 1 tg i v e st h en u m b e o fe a c hc o 皿c c t i o nr e s o u r c e sf o fa p p l i c a t i o na i g o r i t h m w h j c hi si m p l e m e n t e do nr c a ，a n dt h en u m b e ro fc o n n e c t i o nr e s o u r c e so fr c aj s d e t e h n i n e d r e c o n f i g u r a b l ep r o c e s s i n ge l e m e n t 硼y i sak e yc o m p o n e n ti nr c a w i t h a i l a l y z i n gr e c o n f i g i i r a b l ea r r a yd e s i g i ls p a c c ，t h ed i s s e n a t i o nc x p l a i l l st h ea l g o r i t h mt 0 e s t i m a t ea r e a ，t j m ea n dp o w 。rf o rr e c o n 6 9 i i r a b l ea 玎a y b ys t u d y i n gm m s f o 加a t i o n ， e x e c i l t i n gm o d e la n de x e c u t i n gt i m eo fa p p l i c a t i o na l g o r i t t i l n ，a na l g o r i t h mw i t h p e i o f i i l a i l c ec o n s t r a hf o rf d n 矗g 啪b i ep r o c e s s i n ge l e m e n ta r r a yd e s i g ns p a c e e x p l o r a t i o ni sp m p o s e d t h ea l g o f j t | i i np r o d u c e st h eb e s tr e 0 0 n f j g i i r a b l ep r o c e s s i n g e l e m e ma r r a yf o ra p p l i c a t i o nd o m a i n ，w h i c hm e e t st h ep e 埔) m a n c ee x p e c t a t i o n so f a p p l i c a i i o na 1 9 0 r i t l l i l l m e m o r ya f c h i t e c t u r ei sa ni m p o n a n tc o m p o n c n tj nr c a f i n a l l y ，t h em e t h o df o r m e m o r ya r c h i t e c t u r ed e s i g i ls p a c ee x p l o r a t i o ni nr c ai sd i s c u s s e d t h ed i s s e r t a t i o n m 浙江大学博上学位论文 摘要 百v e st h em a x i m u m f o rl o c a ld a t am e m o r ys i z e ，c o n f i g u r a t i o nc o n t e x tm e m o r ys i z e a dt h cb a i l d w i d t ho fi n t e f f a c eb e 咐e e nl o c a ld a t am e m o f ya l l dr e c o n f i g i 】怕b l ea r r a y a n “g d i i t h m w i t ha r e ac o n s t i a i n tf o rm e m o r ya i c h i t e c t u r ed e s i g ns p a c ee x p l o r a t i o ni s p r o p o s e d ，w h i c ha c q u i r e sm e m o r ya r c h i t e c t i l r ew i t ht h eb e s tp e r f o 册柚c ef o r 印p l i c a t i o nd o m a i n k e yw o r d s m od i m e n s i o na r r a yb a s e dr c c o n f i g u r a b l ec o m p u t i n ga r c h i t e c t i l r c ； h i e r a r c h i c a lp a 姗e t e rm o d e l ；c o 曲e c t i o nf e s o u r c e s ；r c c o n f i g u r a b l ep r o c e s s i n g e l e m e n t 彻yd e s i 印s p a c ce x p l o f a t i o n ；m e m o r ya f c h i t e c t l l r cd 船i 驴s p a c ee x p l o r a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得澎姿盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名哼凌哈 签字日期妒年 乡月f 日 学位论文版权使用授权书 本学位论文作者完全了解迸鎏盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盘鎏盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：雩噩嘲 签字日期：州年 ；月箩日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签 签字日期：力否年月曰 电话： 邮编： 浙江大学博士学位论文 第l 章绪论 第1 章绪论 目前，许多高性能的计算平台都以通用处理器为核心。通用处理器具有高度 的灵活性，在通用处理器上，不同的应用软件通过固定的硬件结构能够实现不同 的应用功能。通用处理器的灵活性是以牺牲性能代价获得的，指令的顺序执行和 频繁的存储器操作，使其很难满足许多强计算领域的性能要求。a s i c ( a p p l j c a t i o n s p e c i f i ci n t e 掣a t c da r c u i t ) 作为高性能计算的一个解决方案，它具有优越的性能， 但a s i c 一般针对专门的应用算法，固定的结构和功能限制了它在信息安全、多 媒体等许多多标准和多算法领域的应用。 可重构计算作为一种新的高性能计算解决方案，它是通用处理器和a s i c 的 折衷，具有较高的性能和灵活性。与a s i c 相比，可重构计算具有较高的灵活性， 它利用硬件的适应性，能够在运行时改变硬件的功能。与通用处理器相比，可重 构计算具有较高的性能，它利用硬件的灵活性挖掘应用算法中的细粒度和粗粒度 并行性，提高了应用算法的执行性能。 由于可重构计算具有较高的灵活性，其设计空间巨大，为某个特定的应用领 域设计一个优化的可重构计算体系是一件十分复杂的任务。在可重构计算体系设 计初期，对可重构计算体系的设计空间进行搜索，选择一个优化的可重构计算体 系是一项十分重要的研究工作。 1 1 研究背景 可重构的思想起源于f p g a s ( f i e l dp r o g r a m a b l eg a t ea r r a v s ) 。f p g a 由逻辑单元矩阵和逻辑单元之间的互连网络组成。通过改变下载到f p g a 上的配 置数据，改变逻辑单元的功能和互连网络的连接关系，从而使f p g a 能够实现对 多个应用算法的计算加速。随着f p g a 在工业领域取得巨大成功，可重构计算逐 渐引起了研究者的注意。 f p g a 是一个通用器件，其设计的目的是实现自由逻辑，所以使用f p g a 实现 应用算法的计算加速，存在一些不足之处。1 。首先，f p g a 需要大量的配置数据， 配置时间较长；其次，作为通用器件，f p g a 的布线资源过于丰富，导致面积和 功耗增大，性能降低。为了克服f p g a 的不足之处，近几年来，人们对此进行了 许多研究，并提出了许多不同架构的可重构计算体系。 在可重构计算体系的研究初期，研究者提出的可重构计算体系非常类似于 f p g a ，它们都是由功能处理单元( 类似于f p g a 中的可配置逻辑单元) 和功能处 理单元之间的互连结构( 类似于f p g a 中的布线资源) 组成的可重构功能处理单 元阵列。在实现应用算法的计算加速时，可重构功能处理单元阵列在外部处理器 浙江大学博士学位论文 第1 章绪论 的控制下实现应用算法的计算加速功能。 二十世纪九十年代以来，集成电路工艺取得了非常迅速的发展，已从亚微米 ( 0 5 到l 微米) 进入到深亚微米( 小于o 5 微米) ，进而进入到超深亚微米( 小 于o 2 5 微米) o3 。随着集成电路制造工艺的迅速发展，单一芯片上可以容纳的 晶体管数目大幅增加，集成电路设计进入了s o c ( s y s t e mo nc h i p ) 时代。在许 多多标准和算法的应用领域，将二维的可重构功能处理单元阵列作为i p ( i n t e l l e c t u a lp r o p e r t y ) 模块，集成到s o c 芯片上，构成可重构计算平台是 可重构计算体系的发展方向“1 ”。 可重构功能处理单元阵列 图1 1s o c 芯片上集成可重构功能处理单元阵列的可重构计算体系 在s 0 c 芯片上集成可重构功能处理单元阵列的可重构计算体系如图1 1 所 示。它由主处理器、主存储器、局部数据存储器、数据控制器、配置上下文存储 器和可重构功能处理单元阵列等六部分组成。在可重构计算体系中，主处理器主 要完成以下四个方面的工作。 1 ) 执行应用算法中非计算密集型的任务： 2 ) 控制可重构功能处理单元阵列的运行； 3 ) 加载可重构功能处理单元阵列的配置数据； 4 ) 启动局部数据存储器和主存储器之间的数据传送以及配置上下文存储器 与主存储器之间的数据传送。 可重构计算体系一般采用主存储器和局部数据存储器组成的两级存储器结 构。局部数据存储器是可重构计算体系中的一个重要部件，它的功能相当于数据 c a c h e ，其利用应用算法中数据的局部性，减少了可重构功能处理单元阵列访问 主存储器的次数。在可重构计算体系中，为了充分利用可重构功能处理单元阵列 的并行处理能力，局部数据存储器和可重构功能处理单元阵列之间的接口一般具 2 浙江大学博士学位论文 第1 章绪论 有较大的带宽，以便能够并发地为可重构功能处理单元阵列提供多个数据。 应用算法在可重构计算体系上实现时，应用算法中顺序执行的代码经过传统 的编译器编译后，一般在主处理器上执行。算法中计算密集的循环结构的代码( 为 表述方面，在本文的后续章节中，将这部份代码简称为应用算法) 一般在可重构 功能处理单元阵列上执行。这部分代码经过特殊的编译工具编译后，产生可重构 功能处理单元阵列的配置数据和控制数据。配置数据配置阵列中功能处理单元的 功能和功能处理单元之间的互连结构，使可重构功能处理单元阵列成为应用算法 的加速硬件。编译产生的控制数据控制应用算法在可重构功能处理单元阵列上的 执行顺序和执行方式。 1 2 研究现状 目前，可重构计算体系的研究工作主要集中在两个方面“，其一为可重构计 算体系架构研究；其二为可重构计算体系的设计空间搜索方法研究。在可重构计 算体系的研究初期，研究的重点为可重构计算体系架构。可重构计算体系架构的 研究表明，设计一个适用于所有应用领域的通用的优化可重构计算体系是一件不 切实际的工作，切实可行的是为某个应用领域设计一个优化的可重构计算体系。 可重构计算体系架构研究和可重构计算体系设计空间搜索方法研究密切相关，可 重构计算体系架构的研究工作为设计空间搜索方法的研究奠定了坚实的基础，它 为可重构计算体系的设计空间搜索指明了搜索范围，有助于缩小可重构计算体系 的设计空间。 1 2 1 可重构计算体系 近十几年来，研究者提出了许多不同架构的可重构计算体系“1 ，表1 1 总 结了几种典型的可重构计算体系的特点。不同架构的可重构计算体系的特点可以 从五个方面来描述，即功能处理单元的粒度、可重构功能处理单元阵列结构、可 重构功能处理单元阵列的配置方式、在可重构功能处理单元阵列中是否嵌入分布 式存储器以及功能处理单元之间的互连结构。 1 2 1 1 功能处理单元的粒度 在可重构计算体系中，功能处理单元的粒度是指功能处理单元的操作数宽 度。按照粒度划分，可重构计算体系可以分为细粒度可重构计算体系、粗粒度可 重构计算体系和混合粒度可重构计算体系。在细粒度可重构计算体系中，功能处 理单元在比特层次操作。在粗粒度可重构计算体系( 如m o r p h o s v s 等) 中，功 能处理单元包含完整的功能部件，如算术逻辑单元、乘法器等，其能够实现算法 层次的操作。在混合粒度的可重构计算体系( 如p i p e r e n c h 等) 中，功能处理单 3 浙江人学博士学位论文 第1 章绪论 元既能实现比特层次的逻辑操作，又能实现算法层次的操作。 表1 1 典型的可重构计算体系的特点比较 发表阵列结 配置 分布 结构互连结构式存粒度 时间构方式 储器 1 6 籼d i 1 9 9 0c r o s s b a r静态 c r o s s b a r 交叉开关没有 b i t 1 6 p a d d i _ 2 1 9 9 3c f o s s b a r静态 c m s s b a r 交叉开关没有 b i t 2 维阵 d p n g a 【81 9 9 4 静态交叉盒互连没有 4 b i t 列 2 维阵 3 2 艮e s s a f r a y i 9 】 1 9 9 5 静态相邻连接没有 列b “ 线性阵 1 6 r a p i d 啪11 9 9 6 静态 通道互连结构有 列 b i t 2 维阵1 6 m a n u x 1 9 9 6 动态多长度线互连结构有 列 b i t 2 维阵相邻连接结合行列近3 2 k r c s s a a y ，i i i 1 9 9 7 静态没有 列 邻连接 b i t 2 维阵 r a w 2 3 】1 9 9 7 静态交叉盒互连有混合 列 线性阵 p i p c r e n c h “ 1 9 9 8 动态 通道互连结构没有 4 b i t 列 2 维阵1 6 m o t p h 0 s y s 剐 1 9 9 8 动态多长度线互连结构没有 列 b i t 2 维阵 c h e s s 2 7 11 9 9 9 静态近邻连接有 4 b i t 列 2 维阵 相邻连接结合行列近1 6 d r e a m 2 0 0 0 动态 有 列邻连接 b i t 细粒度可重构计算体系具有较好的灵活性，其功能处理单元能够构造功能复 杂的计算模块，但细粒度可重构计算体系的灵活性是以性能和面积为代价而获得 的。当用细粒度可重构计算体系的功能处理单元构造复杂的计算模块时，由于功 能处理单元之间互连延时的影响，计算模块的性能较差。此外，由于功能处理单 元在比特层次操作，在实现应用算法时，细粒度可重构计算体系需要大量的功能 处理单元和大容量的配置存储器，导致芯片面积增大。由于功能处理单元能够在 算法层次上操作，粗粒度可重构计算体系的性能较高，并且配置存储器的容量较 小。混合粒度的可重构计算体系具有粗粒度和细粒度可重构计算体系的优点，但 结构设计复杂，增加了应用算法的映射问题的复杂度。 4 浙江大学博士学位论文 第l 章绪论 1 2 1 2 可重构功能处理单元阵列的配置方式 在使用可重构计算体系实现应用算法加速时，通过下载配置数据的比特流到 可重构功能处理单元阵列上的配置存储器，配置阵列中功能处理单元的功能和功 能处理单元之间的互连结构，使可重构功能处理单元阵列成为应用算法的加速部 件。可重构功能处理单元阵列的配置速度和方法取决于阵列的配置接口。可重构 功能处理单元阵列的配置接口通常采用串行接口或并行接口。串行接口每次只能 传送一个比特数据，而并行接口一次可以传送1 个字节( 半字或字) 数据。 按照配置方式，可重构计算体系分为静态可重构计算体系和动态可重构计算 体系。对于静态可重构计算体系，在装载新的配置数据流时，可重构功能处理单 元阵列必须停止工作，如l ( r e s s a r r a y 架构。动态可重构计算体系允许功能处理 单元和互连结构处于工作状态时，装载可重构功能处理单元阵列的配置数据。动 态可重构计算体系具有较好的灵活性，能够使用小规模的可重构功能处理单元阵 列完成比较复杂的任务，但由于需要切换配置数据的上下文，与静态可重构计算 体系相比，其性能较差。 1 。2 1 3 可重构功能处理单元阵列结构 可重构计算体系中的可重构功能处理单元阵列结构分为三种，即二维阵列型 结构、线性阵列结构和c r o s s b a r 结构。二维阵列型结构按照长方形( 或正方形) 排列阵列中的功能处理单元，处于同一行和列上的功能处理单元之间设置直接的 互连线，而非同一行或列的功能处理单元之间不设置直接的互连线( 除近邻之间 的互连线) 。文献【2 9 】的研究表明二维阵列型结构能够提供丰富的互连资源，并 且互连线的长度较短，功耗较低。因此，最近提出的可重构计算体系中的阵列结 构一般都采用了二维阵列型结构。 线性阵列结构按照一个或多个线性阵列安排阵列中的功能处理单元。线性阵 列结构中的每个功能处理单元都可以作为流水线的一级，应用算法的流水线能够 十分方便地映射到线性阵列上。线性阵列结构虽然有助于应用算法的映射，但其 缺乏灵活性，因而限制了它的应用范围。c m s s b a r 结构沿着c r o s s b a r 交叉开关安 排功能处理单元，功能处理单元通过c r o s s b a r 交叉开关相互连接。c m s s b a r 结构 虽然能够提供十分丰富的互连资源，实现任意两个功能处理单元之间的相互连 接，但增加了应用算法映射的复杂度。 1 2 1 4 分布式存储器 在可重构功能处理单元阵列中，嵌入分布式存储器能够有效地提高功能处理 单元并发地获取操作数能力，提高可重构计算体系的性能。在可重构功能处理单 元阵列中，分布式存储器的容量一般较小，不适合存储应用算法中的大量数据， 其主要用于存储计算的中间结果。在可重构功能处理单元阵列中嵌入分布式存储 浙江大学博士学位论文 第1 章绪论 器，虽然能够提高可重构计算体系的性能，但增加了应用算法映射的难度和硬件 设计的复杂度。 1 2 1 5 功能处理单元之间的互连结构 在可重构计算体系中，功能处理单元之间的互连结构不仅影响可重构计算体 系的性能，而且影响应用算法映射的复杂程度。复杂的互连结构虽然能够提供大 量的互连资源，但需要较大的芯片面积，并增加了算法映射的复杂度。功能处理 单元之间的互连结构主要有五种，即交叉盒互连结构( s w j i c h b o x ) 、多长度线互 连结构( m u l t i h n 鲜h ) 、通道互连结构、相邻连接互连结构和相邻连接结合行列 近邻连接的互连结构。 在最近提出的典型的可重构计算体系中，d p f p g a 架构和r a w 架构的功 能处理单元之间采用了交叉盒互连结构；p a d d i 架构采用了类似于交叉盒的 c r o s s b a r 交叉开关结构。交叉盒互连结构提供了大量的互连资源，具有非常高的 灵活性，但巨大的设计空间增加了应用算法的映射问题复杂度。 m a t 血架构和m o r p h o s y s 架构的功能处理单元之间使用了多长度线的互连结 构。多长度线的互连结构为同一行和列上的功能处理单元之间提供了不同长度的 直接连线，其具有较好的灵活性，但随着多长度线数量的增加，设计空间增大， 应用算法的映射问题比较复杂；此外，过多的多长度线给芯片的面积带来了较大 的负担。 r a p l d 架构是一个线性阵列结构，其功能处理单元之间使用了通道互连结 构。在r a p i d 的布线通道中，r a p i d 使用分段的总线作为互连资源。在r a p i d 架构中，简单的通道互连结构易于应用算法映射，但缺乏灵活性，限制了r a p i d 架构的应用范围。 c 加巳s s 架构中的功能处理单元之间采用了相邻连接的互连结构。相邻连接 的互连结构十分简单，降低了应用算法的映射问题的复杂度。在实现功能处理单 元之间长的互连线时，由于需要级联多个相邻连接的连线，增加了功能处理单元 之间的互连延时。 在相邻连接结合行列近邻连接的互连结构中，短的互连线由相邻连接实现， 长的互连线由行列近邻连接实现，i ( r e s s a r r a y 架构使用了这种互连结构。相邻连 接结合行列近邻连接的互连结构既能够提供大量的局部互连线，又能够提供少量 的长互连线，因而既保持了强大的互连能力，又降低了应用算法映射问题的复杂 度。 1 2 2 可重构计算体系的设计空间搜索 对于一般的a s i c 设计，文献【3 0 ，3 1 】研究了设计空间搜索方法。在可重构计 6 浙江大学博士学位论文 第l 章绪论 算体系中，由于需要实现应用领域中的一组算法，并且应用领域中的每个算法对 可重构计算体系的设计提出了不同的要求，这使可重构计算体系的设计空问搜索 方法不同于a s i c 的设计空间搜索方法。在可重构计算体系设计空间搜索过程中， 设计空间搜索可以在不同的抽象层次上进行。在不同的抽象层次上，可重构计算 体系的设计空间大小不同，抽象层次越高可重构计算体系的设计空间越大。可重 构计算体系的设计空间搜索方法主要有两种，即综合比较方法和估计比较方 法。 综合一比较方法将应用领域中的算法综合到不同的可重构计算体系，估计可 重构计算体系的性能和面积，然后通过比较它们的性能和面积，选择最优的可重 构计算体系。综合比较方法的优点是能够获得比较精确的结果，但其存在两个 缺点。首先，在将应用算法综合到搜索域中的每个可重构计算体系时，每个可重 构计算体系都需要与之相对应的综合工具，或者使用通用的综合工具。如果使用 通用的综合工具，则需要为搜索域中的每个可重构计算体系提供一个比较精确的 物理模型。其次，由于在综合过程中需要执行非常耗时的布局和布线过程，综合 一比较方法的搜索速度较慢，搜索范围较小。 估计一比较方法克服了综合一比较方法的不足之处，其通过估计的方法获得不 同架构的可重构计算体系的面积、性能和功耗。由于不需要执行综合过程中的复 杂的布局和布线算法，估计一比较方法能够快速搜索较大的设计空间。估计一比较 方法的估计结果不具有绝对精度，而只具有相对精度。由于在设计空间搜索过程 中，只是通过比较不同架构的可重构计算体系的面积、性能和功耗，选择最优的 可重构计算体系，相对精度的估计结果能够满足设计空间搜索的要求。 在可重构计算体系设计空间搜索过程中，在不同的结构抽象层次上，综合一 比较方法和估计一比较方法可以相互补充。在较高的结构抽象层次，由于可重构 计算体系的设计空问巨大，使用估计比较方法能够快速得到搜索结果。在较低 的抽象层次上，可重构计算体系的设计空问较小，使用综合一比较方法能够得到 比较精确的结果，并能够反映架构细节的变化。 表1 2 总结了近几年提出的四种典型的可重构计算体系设计空间搜索方法的 特点。在表1 2 中，方法1 表示m o r i t z 提出的设计空间搜索方法；方法2 表示b o s s u e t 提出的设计空间搜索方法；方法3 表示b m e i 提出设计空间搜索方法；方法4 表示 x p l o r e 方法。在四种方法中，方法1 、方法3 和方法4 为二维阵列型可重构计算设 计空间搜索方法，方法2 为通用的可重构计算设计空间搜索方法。 从搜索方法的角度来看，方法1 和方法2 使用估计比较方法搜索可重构计算 体系的设计空间，由于不需要复杂的布局和布线过程，这两种方法的搜索速度较 快，能够搜索较大范围的设计空间。方法3 和方法4 使用了综合一比较方法搜索可 7 浙江大学博士学位论文 第1 章缔论 重构计算体系的设计空间。在综合过程中，复杂的布局和布线过程需要非常大的 计算量，严重影响了设计空间的搜索速度。 表1 2 四种可重构计算体系设计空间搜索方法的特点 搜索方 算法描述结构描述 搜索方 搜索结果 法 法 估计一比 方法1 1参数描述参数模型r a w 搜索域中的最优架构 较 层次功能模估计一比 方法2 h c d f g 最优架构 型较 综合一比 方法3 眦3l c o d e参数模型 a d r e s 搜索域中的最优架构 较 a l e - x 语言描综合比k r e s s a r r a y 搜索域中的合适 方法4 “1参数模型 述 较架构 从搜索结果的角度来看，方法l 、方法3 和方法4 都是架构相关的设计空间搜 索方法，它们通过为指定的架构域中的可重构计算体系建立参数化的模型，在此 架构域中搜索最优的可重构计算体系。由于架构相关的搜索方法只能在指定架构 域的很小的搜索范围内搜索，它们很难为应用算法搜索到一个真j 下意义上的最优 架构。方法2 是一个通用的设计空间方法，其不依赖于任何具体的可重构计算体 系，能够帮助设计者搜索细粒度可重构计算体系、粗粒度可重构计算体系和异种 功能处理单元组成的可重构计算体系。 方法4 能够为应用领域中的诸多算法搜索一个优化的静态可重构计算体系。 方法4 从应用领域的诸多算法中选择数据通路最复杂的算法作为设计空间搜索的 参考算法。在设计空问搜索过程中，其为参考算法搜索一个合适的架构，然后在 此架构上验证应用领域中的其余算法。如果其余的算法在此架构上实现时的性能 能够满足算法要求，方法4 将此架构作为应用领域的合适架构。方法1 、方法2 和 方法3 都无法为应用领域中的诸多算法搜索一个优化的可重构计算体系，它们只 能为应用领域中的每个算法搜索一个最优的可重构计算体系。由于应用领域中的 各个算法具有不同的性能要求，为每个算法搜索的最优可重构计算体系不能作为 应用领域的最优架构。 在设计空间搜索过程中，方法4 搜索满足应用算法性能要求的可重构计算体 系；方法1 在面积和平衡的约束下，搜索性能最优的可重构计算体系；方法3 能够 从面积和性能两个方面比较不同架构的可重构计算体系；方法2 能够在满足性能 约束的条件下，搜索功耗最低的可重构计算体系。方法1 、方法3 和方法4 的搜索 结果能够确定可重构计算体系的可重构功能处理单元的阵列规模、功能处理单元 的功能、功能处理单元之间的互连结构等架构参数；方法2 的搜索结果能够确定 最低层的层次单元中的存储器的容量、功能处理单元的类型和数目以及可重构计 浙江大学博士学位论文 第1 章绪论 算体系的层次。由于在搜索过程中使用抽象的代价描述层次单元之间的互连结 构，方法2 的搜索结果无法确定可重构计算体系的互连结构。 随着集成电路制造工艺的迅速发展，将可重构功能处理单元阵列作为i p 模 块集成到s o c 芯片上，构成可重构计算平台是可重构计算体系的发展方向。在 s o c 芯片上集成可重构功能处理单元阵列的可重构计算体系中，存储器的结构对 可重构计算体系的面积和性能存在较大影响。在可重构计算体系设计空间搜索过 程中，搜索存储器结构的设计空间为可重构计算体系选择一个合适的存储器结构 是可重构计算体系设计空间搜索的一个重要内容。上述的四种设计空间搜索方法 只能搜索可重构计算体系中的可重构功能处理单元阵列的设计空间，而忽视了存 储器结构对可重构计算体系的影响。 在可重构计算体系设计空间搜索过程中，可重构计算体系采用静态配置方式 或动态配置方式与应用领域中各个算法的性能要求密切相关。在上述四种典型的 设计空间搜索方法中，它们只能在静态可重构计算体系搜索域中或动态可重构计 算体系搜索域中搜索最优的可重构计算体系，无法比较用静态可重构计算体系和 动态可重构计算体系实现应用领域中所有算法的优劣。 1 3 研究内容和创新点 1 3 1 研究内容 本文致力于二维阵列型可重构计算的设计空间搜索方法研究。本文研究的可 熏构计算设计空间搜索方法属于估计比较方法，其不依赖于任何具体的可重构 计算体系，能够为应用领域中的所有算法搜索一个全局最优的可重构计算体系。 在设计空间搜索过程中，它能够比较用静态可重构计算体系和动态可重构计算体 系实现应用领域中所有算法的优劣，帮助设计者确定可重构计算体系的互连结 构、可重构功能处理单元的阵列规模、功能处理单元的功能以及可重构计算体系 的存储器结构。本文涉及的内容如下： 第二章介绍了近几年提出的几种典型的可重构计算体系，分析了各种可重构 计算体系的特点。接着介绍了最近几年提出的四种典型的可重构计算体系的设计 空间搜索方法，详细介绍了各种设计空问搜索方法的搜索流程。 第三章介绍了论文提出的可重构计算设计空间搜索方法流程，接着介绍了应 用算法的h c d f g 描述和应用算法分析。定义了描述可重构计算体系的结构特征 参数。在特征参数的基础上，提出了可重构计算体系的层次型参数模型，并具体 描述了层次型参数模型的顶层描述结构、块描述结构、单元描述结构和功能描述 结构。最后通过实例验证了可重构计算体系层次型参数模型的通用性。 第四章介绍了应用算法在可重构计算体系上的编译方法，通过在应用算法编 9 浙江大学博士学位论文 第1 章绪论 译过程中生成动态宏单元库，使应用算法编译方法能够适应不同架构的可重构计 算体系。接着介绍了可重构计算体系的三种互连资源，在建立应用算法网表布线 随机模型的基础上，提出了可重构计算体系的互连资源估计方法。此方法能够估 计应用领域中的各个算法在可重构计算体系上实现时所需要的各种互连资源数 目。 第五章分析了可重构功能处理单元阵列的设计空间，研究了可重构功能处理 单元阵列的面积、性能和功耗的估计方法。最后介绍了应用算法的变换方法以及 应用算法在可重构计算体系上的执行模型和性能估计方法，并给出了性能约束的 可重构功能处理单元阵列的设计空间搜索方法。设计空间搜索方法分两步执行， 首先，对于设计空间搜索域的每个可重构功能处理单元阵列结构，在应用算法的 执行时问受约束的条件下，搜索此阵列结构实现应用领域中所有算法时的最小实 现代价：其次，根据每个可重构功能处理单元阵列的最小实现代价，在可重构功 能处理单元阵列的搜索域中搜索最优的可重构功能处理单元阵列。 第六章分析了存储器结构的组成以及存储器结构的设计空间，推导了局部数 据存储器容量和配置上下文存储器容量的最大值以及局部数据存储器与可重构 功能处理单元阵列之间接口带宽的最大值，并提出了面积约束的存储器结构的设 计空间搜索方法。搜索方法分两步搜索存储器结构的设计空间，首先，在存储器 结构的面积受约束的条件下生成存储器结构的初始结构；其次，在存储器结构面 积受约束的情况下，以初始结构为基础搜索存储器结构的设计空间，搜索性能最 优的存储器结构。 1 3 2 创新点 论文的创新点主要有以下四点： 1 、在定义了描述可重构计算体系的结构特征参数的基础上，提出了可重构计算 体系的层次型参数模型。在可重构计算体系设计空间搜索过程中，采用可重构计 算体系的层次型参数模型具有三个、优点，其一是能够反缺可重构计算体系的结构 特征；其二是能够反映可重构计算体系的层次性；其三是具有良好的灵活性，能 够描述不同类型的二维阵列型可重构计算体系。 2 、在建立应用算法网表在可重构计算体系上布线随机模型的基础上，提出了基 于随机模型的可重构计算体系的互连资源估计方法。此方法能够估计应用领域中 各个算法网表在可重构计算体系上实现时所需要的各种互连资源数目，从而确定 可重构计算体系的各种互连资源数目。在可重构计算体系设计空间搜索过程中， 估计各种互连资源数目能够指导互连结构的设计。 3 、提出了估计可重构功能处理单元阵列的面积、性能和功耗的方法。通过对应 1 0 浙江大学博士学位论文 第1 章绪论 用算法进行并行展开和任务分割变换，将应用算法以不同的实现方式在可重构计 算体系上实现，使设计空间搜索方法能够在静态可重构计算体系搜索域中和动态 可重构计算体系搜索域中搜索最优的可重构计算体系。根据应用算法的不同实现 方式在可重构计算体系上的执行模型，估计了应用算法在可重构计算体系上实现 时的性能。以应用算法在可重构计算体系上实现时的性能、可重构功能处理单元 阵列的面积和功耗为依据，提出了基于性能约束的可重构功能处理单元阵列设计 空间搜索方法。 4 、分析了可重构计算体系的存储器结构的组成以及存储器结构的设计空间，推 导了局部数据存储器容量和配置上下文存储器容量的最大值以及局部数据存储 器与可重构功能处理单元阵列之间接口带宽的最大值，并提出了面积约束的存储 器结构的设计空间搜索方法。此方法能够搜索最优的存储器结构，使应用领域中 的算法在可重构计算体系上实现时能够获得最优的执行性能。 1 1 浙江大学博士学位论文 第2 章可重构计算体系及其设计空间搜索方法 第2 章可重构计算体系及其设计空间搜索方法 自从) ( i l i n 】【公司在1 9 8 5 年率先推出商用化的f p g a 以来，f p g a 在工业领 域取得了巨大成功。在f p g a 商用化的初期，即g