1、1可变数据集合维护问题的硬件加速结构与方法摘要：针对可变数据集合维护问题，提出了一种通用的硬件结构，根据接收到的操作指令灵活地实现链表数据结构的大多数常用功能，并支持一些高级功能.不仅能够使用链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访问.为了解决存储资源受限问题，设计了一种存储资源回收机制对失效结点进行回收.实验结果表明，提出的通用硬件链表结构可以优化对可变数据进行维护的处理过程，而且该结构资源占用较少、功耗较低，与 PC 上的软件链表数据结构相比，硬件链表结构在执行时间上也具有较高的加速比. 关键词：可变数据集合维护；硬件加速；链表 中图分类号：TP3
2、91.41 文献标识码：A Structure and Method for Hardware Acceleration of Variable Data Set Management XU Jin-bo1， DOU Yong2， SUN Cai-xia1， DONG Ya-zhuo3， WANG Shao-gang1， LU Ping-jing1， ZHANG Jun1 （1. College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China； 2. National Laborat
3、ory for Parallel and Distributed Processing， National Univ of Defense Technology， Changsha， Hunan 410073， China； 3. Unit 91655， Peoples Liberation 2Army， Beijing 100036，China） Abstract： A general hardware structure was proposed to accelerate variable data set management， which was designed to accept
4、 instructions flexibly and accomplish the commonly used functions and some more complicated functions of the linked-list data structure .The structure can access the data based on both pointer and address mechanism. In order to fully utilize the limited memory resources， we proposed a memory recycle
5、 scheme to reuse the memory space where the data have been deleted. Experimental results on FPGA show that our proposal can accelerate the variable data set management. Only few hardware resources were used and it consumed pretty low power. Compared with the software linked-list structure in PC， our
6、 proposal in FPGA achieved high speedups. Key words： variable data set management； hardware acceleration；linked-list 在数字图像处理领域1，尤其是在目标识别与跟踪应用中2-5，经常会遇到可变数据集合维护问题.当对图像中的目标进行识别跟踪时，需要首先将图像中的一个或多个可能包含运动目标的兴趣区域信息提取出来，这些区域信息形成一个数据集合.随着处理过程的推进，可能会发现新的兴趣区域，这就需要在该数据集合中加入该兴趣区域的信息；当某个兴趣区域被排除后，需要从该数据集合中把对应的信息去掉
7、；另外，3有些兴趣区域可能需要进行合并、分割1，6.因此，这种数据集合中的数据元素是不断变化的，需要一种合适的数据结构对该数据集合进行组织和维护，所采用的数据结构必须能够使得其中的数据元素可以被灵活地存取和操作. 链表数据结构可以满足这种需求.链表支持随机访问和删除，每个结点使用指针指向其前驱和（或）后继结点.在硬件数字图像处理系统中，当遇到这类可变数据集合维护问题时，需要设计相应的硬件链表结构.然而现有的存储结构不能完全实现链表数据结构的功能.首先，若将数据集合保存在线性编址存储器中，当一个元素合并到另一个元素中或者不满足特定规则而被过滤掉时，这个元素将被删除，这就要求标记该地址上的元素不再
8、有效，也就是必须维护一个元素地址的集合，然而这个地址集合也必须存储在一个存储器中，又回归到可变数据集合维护问题.其次，现有的 FIFO 存储器也无法完全满足要求，FIFO 只有一个读端口且只能顺序读取数据，而在多个元素执行合并操作时需要同时读取多个信息，FIFO 数据只能读取一次，不能满足对数据元素的多遍处理.人们已经设计实现了一些针对具体应用的硬件链表结构，如，魏本杰等人设计了硬件链表并将其应用于三维多分等级树编码7； Lu 等人设计了硬件链表结构并应用于 FPGA 的在线布局操作8，用来在对 FPGA 进行动态重构时保存 FPGA 上空闲矩形区域的相关信息；Papaefstathiou 等
9、人将硬件链表结构应用于网络处理器中的队列管理9，等等.这些硬件链表结构大多为面向某个特定应用，具有一定的专用性. 本文设计了一种通用的高速硬件链表结构.这种硬件链表结构可以根据接收到的操作指令实现链表4数据结构的大多数常用功能，比如增加或删除数据结点、对某个特定结点进行读取或更新操作、基于数据内容进行结点定位等，另外该结构还支持一些高级功能.该链表结构不仅能够使用链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访问.由于存储资源有限，因此设计了一种存储资源回收机制对失效结点进行回收.该硬件链表结构在 FPGA 上进行了实验测试，结果表明，该结构资源占用较少、功耗
10、较低，与 PC 上的软件链表数据结构相比，硬件链表结构在执行时间上也具有较高的加速比. 1 设计难点及解决方案 由于有编译器和操作系统的支持，软件实现的链表功能强大、灵活，将软件链表的功能和用法完全向硬件平台移植需要克服缺少编译器和操作系统支持所造成的困难，这些困难可以通过改变链表使用方式和充分利用硬件特性来解决. 在软件链表数据结构中，对结点的访问是通过链表指针完成的.读取、删除某个结点时需要从表头遍历若干个结点之后才能定位到待访问结点，增大了输出延迟.在本文的硬件链表结构中，通过充分利用硬件特性，不仅可以通过链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访
11、问. 软件链表数据结构中被删除的结点将由操作系统负责回收，但是在本文的硬件链表结构中，由于没有操作系统支持，因此设计了专用的存储资源回收模块，自主管理存储空间的重复使用. 2 硬件链表体系结构设计 5硬件链表体系结构主要由 5 部分组成：存储控制模块 MC， 链表控制模块 LC， 存储资源回收模块 MR， 地址选择模块 AS 和输出选择模块OS，如图 1 所示. 当一个操作指令 instruction word 输入时，LC 首先对指令进行解析，得到具体的命令 mode，数据 data 和（或）地址 addr，并送入 MC，其中addr 由 AS 从外部地址 addr_outside（从 in
12、struction word 中获得）和内部地址 addr_inside（内部计算得到的地址）中选择.然后，MC 对链表中的数据元素进行操作并输出结果，根据操作指令的不同，所输出的结果可能为结点数据、结点地址或者某些标志位.MR 负责将已经失效的结点的地址空间进行回收.OS 负责将 MC 的输出根据操作指令送入不同的部件. 该硬件链表是双向链表，图 2 给出了数据在链表中的存储格式.链表中每个结点由数据域 data， 前向指针 prev， 后向指针 next 和结点是否在链表中标志 valid 四项组成.定义 NULL 指针的地址为全 1，占用一个地址空间，规定表头结点的前向指针和表尾结点的后
13、向指针都指向 NULL.如果链表地址宽度为 W，那么链表最大长度为 2W-1.此外，为了便于遍历链表和插入新结点，对外提供表头指针 head_ptr 和表尾指针 tail_ptr，以及当前链表中的结点数目 no_items.图 2 中所示的链表容量为 255，当前长度为 4，表头地址是 00，表尾地址是 03. 2.1 存储控制模块 MC MC 对链表中的数据元素进行操作并输出结果.在硬件实现时，通常需要对每个结点的 data， prev， next 和 valid 域同时进行访问.因此，为了实现并行访问，data， prev 和 next 分别保存在 3 个不同的 RAM 存6储模块中，分别
14、称为 Data_RAM，Prev_RAM 和 Next_RAM.每个 RAM 都是双端口的，可以同时进行读写.valid 域的存储模块称为 Valid_Tab，由于valid 域读写频繁，并且其数据量小、FPGA 提供丰富的寄存器资源，本文使用寄存器数组实现 Valid_Tab，这样既可以降低逻辑复杂性，又可以避免访问 RAM 的长延迟. MC 从 LC 获得具体的命令 mode，数据 data 和（或）地址 addr，并对Data_RAM， Prev_RAM， Next_RAM 和 Valid_Tab 进行操作.通常，在对某结点执行读写操作前，需要首先确定该目标结点的位置.如果目标结点在存储
15、器中的物理地址是未知的，可以通过链表指针 prev 或 next 从其他结点不断遍历到目标结点；如果物理地址是已知的，就可以直接通过物理地址对该结点进行定位. 2.2 链表控制模块 LC LC 使用状态机控制整个链表结构的运行.它对输入的 instruction word 进行解析，得到具体的命令 mode，数据 data 和（或）地址 addr，并送入 MC；同时 LC 还控制 AS 从 addr_outside 和 addr_inside 中选择合适的地址；当命令 mode 为删除命令 delete 时，LC 将控制 MR 对被删除的结点空间进行回收；另外，LC 还控制 OS 将 MC 输
16、出的数据送入正确的模块. 例如，当对一个已知物理地址的结点进行数据更新操作时，LC 对instruction word 进行解析得到命令 mode 为 update，数据 data 为该结点的新数值，而 AS 所选择的地址 addr 为从 instruction word 中获得的该结点的物理地址；接下来 MC 将位于 addr 地址的结点数据更新为7data；最后，OS 将更新后的数值输出作为反馈. 再例如，当希望根据内容确定该结点在链表中的位置时，LC 对instruction word 进行解析得到命令 mode 为 search，数据 data 为希望查找的数值，而 addr 为表头结
17、点的地址；接下来，MC 访问表头结点，并将表头结点的数值与输入的 data 进行比较，若相同，则搜索结束；否则，AS 选择的地址为 addr_inside，该地址信息为当前结点的 next 域对应的数值，这样 MC 就可以访问链表中的下一个结点并进行比较操作.这种过程不断重复直到找到所需的数据或者搜索过程进行到表尾，最后，OS 将所搜索到的结点的地址输出，或者输出 NULL 表示搜索失败. 2.3 存储资源回收模块 MR 当删除一个链表结点时，它所占用的地址空间立刻被释放掉.MR 通过将该结点的 valid 域设为 0 对该结点进行回收. 在向链表中写入一个新结点时，需要找到一个空闲位置，有两
18、种方法可以实现：第一种是指针 avail 始终指向可写位置，这要求在一次写操作完成后查找空闲位置；第二种方式是写操作到来时才查找空闲位置.第一种方法看起来很好，写结束后链表自动查找可用位置而外部模块进行别的处理，是一种并行工作方式.但是如果进行连续写操作时，必须在链表和外部模块之间进行查询和应答来判断什么时刻可以真正启动写操作，这就大大增加了实现复杂性.第二种方法是一种“懒惰”工作方式，不需要进行显式同步. 本文工作采用第二种方法实现存储空间回收.写请求到来时才开始查找一个可用位置 avail，查找到的位置可能是一直空闲的地址或者是因结8点已被删除而重新可用的地址.设置标志寄存器 LWA，表示
19、上次写入结点的地址，初始化为 NULL，指针 avail 在上次写入操作后指向 LWA+1 位置.查找过程就是从 LWA+1 逐个判断，找到第一个满足 Valid_Tabavail=0的位置，当到达最大地址时再从零地址开始查找直到 LWA.如果链表不满，总是可以找到一个空闲位置，否则就不会启动查找过程而是直接终止写操作. 找到可用位置后，向 Data_RAM 的 avail 地址中写入新结点的数值data，将 NULL 作为新元素的后向指针写入 Next_RAM.如果写入的是第一个元素，将 NULL 作为新元素的前向指针，否则将 tail_ptr 作为前向指针写入 Prev_RAM.将 val
20、id 域置为 1.将 avail 作为写入前表尾元素的后向指针写入 Next_RAM，同时将 LWA 和 tail_ptr 指向 avail，写入第一个元素时要将 head_ptr 指向 avail，将元素数目寄存器 no_items 都加 1. 设链表地址宽度为 W，最好的情况是查找之前 avail 位置就可用，比较 1 次；最坏情况是最后一个位置可用，比较 2W-1 次，平均比较次数是（2W-1+1）/2=2W-1. 2.4 地址选择模块 AS AS 用来决定 MC 应该从外部输入数据中读取地址还是应该从内部模块中读取地址.不同的操作命令获取地址的来源不同，比如，当对一个已知物理地址的结点
21、进行数据更新时，AS 选择的地址 addr 是从 instruction word 中获得的；而当根据内容确定结点在链表中的位置时，AS 选择的地址为从 MC 输出的当前结点的 next 域对应的值.地址选择信号 addr_sel由 LC 根据 instruction word 解析得到. 92.5 输出选择模块 OS OS 用来决定链表输出数据的类型.不同的链表操作得到的输出数据类型是不同的，比如，读操作输出所读结点的数据域 data，写操作返回写入结点所在的地址.OS 由 LC 控制，LC 根据操作类型生成 output_sel 信号送入 OS. 3 硬件链表的应用 应用系统通过将相应的
22、instruction word 送入硬件链表实现可变数据集合的维护. 硬件链表结构除了可以实现链表数据结构的基本操作（这些操作针对单个或部分结点进行） ，还可以实现一些针对所有链表结点的高级功能，比如计算所有链表结点的最大最小值、平均值、累加值或其他一些统计操作.这些全局操作的共同点就是对链表的遍历操作，遍历可以分为单指针遍历和双指针遍历.单指针遍历使用一个指针从表头到表尾依次访问链表元素，适用于计算最大最小值、累加和等操作.双指针遍历使用指针 A和 B，A 首先指向表头，B 依次遍历 A 后面剩余元素，将 A 前进一个元素，B 回到 A 后面再次遍历，重复上述过程直到 A 指向表尾.双指针
23、遍历用于关联链表中的一对元素，比如求任意两个元素之间的相似度.本文设计的链表为上述两种遍历提供支持，算法伪代码如图 3 所示，图中 Read 操作返回当前结点数值和下一个结点地址. 硬件链表对外提供表头和表尾指针，可以方便地实现堆栈和队列.堆栈是后进先出的表结构，基于链表实现时将进栈元素写在表尾，出栈时删除最后一个元素并返回它的值.队列是先进先出的表结构，基于链表实10现时将进入队列元素写在表尾，每次都删除表头元素并返回它的值. 4 实验与分析 本文在 FPGA 上对硬件链表结构进行了测试，FPGA 芯片采用 Altera Stratix II EP2S 130F1020 C5，使用 Ment
24、or Graphics ModelSim 进行仿真，并使用 Quartus II 进行综合.链表数据宽度设为 32 位. 本文选择 6 个不同容量的链表进行测试，资源使用情况和时钟频率如表 1 所示.由于 valid 域是使用寄存器数组实现的，当链表容量增大时，需要的寄存器必然会增加，地址译码需要的逻辑单元也会随之增加，译码的逻辑级数增加导致时钟频率下降.根据综合报告，容量小于 256 时，决定时钟频率的关键路径是从存储器输出到寄存器延迟；容量大于等于256 时，决定时钟频率的关键路径是从寄存器到寄存器延迟.理论上链表需要的存储器位数跟链表长度成正比，根据结果进行线性回归可得到两者满足线性关系
25、 y=52.41x-746.99. 为了对硬件链表结构的处理速度进行评价，本文对图 3 所示的双指针遍历操作进行了测试.测试过程不对链表数据进行任何处理，只是将它们从链表中按双指针遍历的顺序读出.表 3 给出了 FPGA 上的硬件链表结构和 PC（Pentium 4 2.8GHz CPU， 512MB 内存）上的软件链表的性能比较，结果表明，硬件链表的处理速度比软件链表数据结构的处理速度快，对于长度分别为 32， 64， 128， 256， 512， 1 024， 2 048 和 4 096的链表，硬件链表结构与软件链表相对于双指针遍历操作在执行速度上的加速比最少为 6.56，最大达到 1 362.8.加速比随着链表长度的增加而增加，原因在于 PC 上的软件链表需要操作系统进行存储管理，而硬件链
