可重构计算专题读书报告杨晓晖(BA07011001)yangxhcs@ 冯晓静(SA07011002)bangyan@ 赵琼(SA07011013)qiongz@裴建国(SA07011083)ustcowen@ 俞华铭(SA07011053)yhm2007@ 王仁(SA07011089)wangren@ 张志雄(SA07011090)zzxiong@中国科学技术大学计算机科学技术系2007年12月录1可重构计算概述（杨晓晖） (1)1.1引言 (1)1.2可重构计算分类 (2)1.3可重构计算体系结构 (5)1.4可重构计算模型 (7)1.5可重构计算算法 (8)1.6问题讨论 (9)本章小结 (10)参考文献 (10)2案例分析之一：可重构超级计算（冯晓静，赵琼） (11)2.1引言 (11)2.2论文工作 (11)2.3问题及讨论 (12)2.4对论文的思考 (14)本章小结 (15)参考文献 (15)3案例分析之二：可重构计算在数据挖掘中的应用（裴建国，俞华铭） (16)3.1引言 (16)3.2算法实例 (16)3.3主要贡献 (17)3.4问题讨论 (20)本章小结 (22)参考文献 (22)4案例分析之三：可重构计算在分子动力学仿真中的应用（王仁，张志雄）.23 4.1引言 (23)4.2仿真算法分析 (23)4.3与相关工作的比较 (24)4.4问题讨论及解决 (25)4.5对论文的思考 (25)本章小结 (26)参考文献 (26)5结论与展望（杨晓晖） (27)1可重构计算概述1.1引言传统的计算方式主要有两种[1][8]。
一种是专用集成电路（Application Specific Integrated Circuit，ASIC），以硬件方式执行特定的操作。
由于ASIC专为某一特定计算任务设计，因此可以快速高效地执行所针对的计算任务。
然而，ASIC一旦生产出来后就再也无法改变其功能。
即使只要修改其中一小部分功能，也不得不投入巨资重新进行设计和生产，显然在生产量达不到一个很大的规模时，这个代价是很昂贵的。
另外一种是通用微处理器（General Purpose Processor，GPP），执行一系列指令来完成特定的计算任务。
如果计算任务发生变化，通过改写程序即可改变软件中所包含的指令序列，GPP通过执行不同的指令序列即可完成不同的计算任务，而硬件无需做出任何改动。
因此GPP非常具有灵活性，但是这种灵活性是以牺牲性能为代价换取的。
处理器为了完成一个计算任务，需要从存储器中逐条取得指令和数据然后加以译码和执行，每次操作都需要很大的执行开销。
所以GPP的性能远远落后于ASIC。
可重构计算（Reconfigurable Computing，RC）正是为了填补硬件实现和软件实现之间的空白而提出的，它试图在达到比软件实现更高性能的同时，还能提供一定的硬件实现灵活性[1]。
可重构计算的定义多种多样。
Bondalapati和Prasanna将可重构计算定义为“通过后生产方式（post-fabrication）和处理单元的时空编程连接（spatially and temporally programmed connection）实现的计算”[5]。
DeHon和Wawrzynek认为可重构计算是“一种具有两个重要特征的计算机组织类型：在生产后可以被定制用来解决任何问题；能够在很大程度上利用空间定制的计算来完成计算任务”[4]。
Hartenstein则把可重构计算资源称为“活件（Morphware）”、“配件（Configware）”和“流件（Flowware）”[7]。
如图1-1所示，可重构计算本质上可以看作是“在（微处理器的）灵活性和（ASIC的）性能之间的一个折衷，时间计算和空间计算的一种结合”[7]。
同时，可重构计算还可以看作是“在灵活性和面积/功耗之间的一个折衷”[2]，如图1-2所示，基于FPGA实现的可重构处理器或者嵌入式可重构逻辑可以使用比ASIP或者GPP更低的面积和功耗，来提供比ASIC更好的灵活性。
图1-3则进一步揭示了可重构计算“空间计算和时间计算相结合”的本质[4]。
可重构计算具有如下特征[5]：●空间计算：数据处理由空间分布的计算来实现；●可配置的数据通路：通过配置机制，互联网络和计算单元的功能可以在运行时动态变化（以适应不同的计算任务需求）；●分布式控制：计算单元基于本地配置来进行数据处理；●分布的资源：计算所需的资源，如计算单元和存储器，都是分布的。
图1-1可重构计算填补了ASIC与微处理器之间的空白[7]图1-2可重构计算是在灵活性和面积/功耗之间的一个折衷[2]图1-3可重构计算是空间计算和时间计算的一种结合[4]1.2可重构计算分类可重构计算总的来讲可以按照逻辑块粒度、可重构单元耦合程度和重构方式来进行分类。
1.2.1按照逻辑块粒度分类大多数可重构硬件都是一个基于多个基本功能单元组合而成的阵列，这个基本功能单元就是逻辑块。
所谓逻辑块的粒度是指由映射工具综合而成可重构硬件的最小功能单元的大小和复杂度[8]。
按照逻辑块的粒度，可重构计算可以分为如下五类[2][3][5]：●甚细粒度体系结构：逻辑块能够实现1-3输入的处理能力，如Xilinx6200系列FPGA；●细粒度体系结构：逻辑块一般实现4输入的基本处理功能，如Altera FLEX10K；●中粒度体系结构：逻辑块可以实现更加复杂的4输入的处理功能，如Garp；●粗粒度体系结构：逻辑块能够实现字宽度的复杂运算，如RaPid；●甚粗粒度体系结构：每个逻辑块就相当于一个微处理器，如RAW。
逻辑块粒度越细，单个逻辑块的功能就越简单，可重构硬件的功能就越灵活，但是电路集成度就越低，逻辑块之间的连线就越多，所需要的面积和功耗也会越大；反之，逻辑块粒度越粗，单个逻辑块的功能就越复杂，电路集成度就越高，逻辑块之间的连线就越少，所需的面积和功耗也较低，但是可重构硬件的灵活性会变差[3][5]。
1.2.2按照可重构单元耦合程度分类如图1-4和图1-5所示，可重构计算按照可重构处理单元（Reconfigurable Processing Unit，RPU）与主处理器之间的耦合程度或连接方式，可以分为如下四类[2][3]：●连接I/O总线的RPU，其作用相当于一个外部的独立处理单元（Standalone ProcessingUnit)；●连接局部总线的RPU，其作用相当于一个附加的处理单元（Attached ProcessingUnit）；●与主处理器直接连接的RPU，其作用相当于一个协处理器（CoProcessor）；●集成到主处理器内部的RPU，其作用相当于主处理器的一个功能单元（Function Unit）。
图1-4RPU与主处理器之间的连接方式[2]图1-5可重构系统的耦合程度[3]1.2.3按照重构方式分类简单地，重构方式分为静态重构（static reconfiguration）和动态重构（dynamic reconfiguration）两大类[1]。
静态重构又称编译时重构（compile time reconfiguration），是最简单、最常见的一种重构方式[2]。
如图1-6所示，静态重构在系统编译时完成配置信息的生成，在执行前进行逻辑块的重构，系统在投入运行后逻辑块的功能不能改变，除非系统终止运行[1][2]。
动态重构又称运行时重构（run-time reconfiguration）[2]。
如图1-7所示，系统可以在运行时收集所需的状态信息，然后据此生成新的配置信息，并在系统运行过程中完成逻辑块的重构，从而改变其功能[1]。
图1-6静态重构[1]图1-7动态重构[1]动态重构又可以进一步分为单上下文可重构（single context reconfigurable）、多上下文可重构（multi-context reconfigurable）、部分可重构（partially reconfigurable）[2]，以及流水线可重构（pipeline reconfigurable）[3]，分别如图1-8、图1-9所示。
图1-8动态可重构方式[2]在单上下文可重构体系架构中，配置信息以串行流（serial stream）的形式存储在配置存储器中。
当发生上下文切换时，即改变系统的配置时，需要重新装入新的配置信息，才能完成对可重构部件的配置，因此配置信息在串行流中的分割会对重构延迟产生较大影响。
Xilinx4000系列就属于这种架构。
在多上下文可重构体系结构中，每个配置位对应着配置存储器中的多个存储位，但是任一时刻只有一个存储位处于激活状态。
当需要上下文切换时，只需要改变配置位和存储位的对应关系即可实现系统的快速重构。
多上下文重构相当于多个单上下文重构的堆叠实现。
典型产品有Chameleon公司的CS2000系列。
部分可重构体系结构针对配置只需要使用全部可重构硬件的一部分，或者只有一部分配置需要改变的情况。
部分可重构硬件可以在一部分硬件运行的同时改变另外一部分硬件的配置，这是通过给每个可配置位编址访问来实现的。
部分可重构硬件体系结构可以进一步减少重构时间，缩短重构延迟。
Xilinx6200系列和Virtex系列都属于可部分重构的体系结构。
流水线可重构体系结构可以看作是部分可重构体系结构的一个特殊的例子，它可以实现流水线各段的部分重构[3]。
如图1-9所示，重构过程是逐段进行的，这意味着配置信息要先于数据信息到达流水线的各段。
完成硬件配置的流水段可以进行相应的运算。
在整个流水线部件中，配置和运算是在不同的流水段中交叉进行的。
图1-9流水线可重构体系结构[3]1.3可重构计算体系结构1.3.1设计综合方法利用可重构体系结构来实现更高的计算性能，需要开发高效的配置设计技术。
但是现有的设计方法都是基于ASIC设计工具的、传统的逻辑综合方法，无法充分发挥可重构硬件的加速潜能，其最大问题就在于设计过程[1]。
如图1-10的左图所示，逻辑综合方法利用行为模型进行设计，但是算法的语义和本质却在软硬件的映射过程中丢失了。
图1-10逻辑综合方法与算法综合方法[1]算法特定且实例相关的配置是实现高加速比的一个关键所在。
基于算法的综合方法[1]，如图1-10的右图所示，提出了一个“算法-模型-体系结构”的综合设计方法。
算法经过调度成为模型，模型进而映射为体系结构；反之，体系结构抽象为模型，模型再参数化为算法。
这种局部优化的设计方法可以获得更好的面积与时延性能。
1.3.2可重构计算体系结构可重构体系结构从现场可编程门阵列（Field Programmable Gate Array，FPGA）发展而来，现在已经有很多种类的商业化FPGA产品面市，各种各样的可重构计算系统也随之被构建起来。