可变数据集合维护问题的硬件加速结构与方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇可变数据集合维护问题的硬件加速结构与方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对可变数据集合维护问题，提出了一种通用的硬件结构，根据接收到的操作指令灵活地实现链表数据结构的大多数常用功能，并支持一些高级功能.不仅能够使用链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访问.为了解决存储资源受限问题，设计了一种存储资源回收机制对失效结点进行回收.实验结果表明，提出的通用硬件链表结构可以优化对可变数据进行维护的处理过程，而且该结构资源占用较少、功耗较低，与PC上的软件链表数据结构相比，硬件链表结构在执行时间上也具有较高的加速比.
关键词：可变数据集合维护；硬件加速；链表
中图分类号：TP391.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 Laboratory for Parallel and Distributed Processing， National Univ of Defense Technology， Changsha，
Hunan 410073， China； 3. Unit 91655， People’s Liberation Army， Beijing 100036，China）
Abstract： A general hardware structure was proposed to accelerate variable data set management， which was designed to accept 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 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 proposal in FPGA achieved high speedups.
Key words： variable data set management； hardware acceleration；linked-list
在数字图像处理领域[1]，尤其是在目标识别与跟踪应用中[2-5]，经常会遇到可变数据集合维护问题.当对图像中的目标进行识别跟踪时，需要首先将图像中的一个或多个可能包含运动目标的兴趣区域信息提取出来，这些区域信息形成一个数据集合.随着处理过程的推进，可能会发现新的兴趣区域，这就需要在该数据集合中加入该兴趣区域的信息；当某个兴趣区域被排除后，需要从该数据集合中把对应的信息去掉；另外，有些兴趣区域可能需要进行合并、分割[1，6].因此，这种数据集合中的数据元素是不断变化的，需要一种合适的数据结构对该数据集合进行组织和维护，所采用的数据结构必须能够使得其中的数据元素可以被灵活地存取和操作.
链表数据结构可以满足这种需求.链表支持随机访问和删除，每个结点使用指针指向其前驱和（或）后继结点.在硬件数字图像处理系统中，当遇到这类可变数据集合维护问题时，需要设计相应的硬件链表结构.然而现有的存储结构不能完全实现链表数据结构的功能.首先，若将数据集合保存在线性编址存储器中，当一个元素合并到另一个元素中或者不满足特定规则而被过滤掉时，这个元素将被删除，这就要求标记该地址上的元素不再有效，也就是必须维护一个元素地址的集合，然而这个地址集合也必须存储在一个存储器中，又回归到可变数据集合维护问题.其次，现有的FIFO存储器也无法完全满足要求，FIFO只有一个读端口且只能顺序读取数据，而在多个元素执行合并操作时需要同时读取多个信息，FIFO数据只能读取一次，不能满足对数据元素的多遍处理.人们已经设计实现了一些针对具体应用的硬件链表结构，如，魏本杰等人设计了硬件链表并将其应用于三维多分等级树编码[7]； Lu等人设计了硬件链表结构并应用于FPGA的在线布局操作[8]，用来在对FPGA进行动态重构时保存FPGA上空闲矩形区域的相关信息；Papaefstathiou等人将硬件链表结构应用于网络处理器中的队列管理[9]，等等.这些硬件链表结构大多为面向某个特定应用，具有一定的专用性.
本文设计了一种通用的高速硬件链表结构.这种硬件链表结构可以根据接收到的操作指令实现链表数据结构的大多数常用功能，比如增加或删除数据结点、对某个特定结点进行读取或更新操作、基于数据内容进行结点定位等，另外该结构还支持一些高级功能.该链表结构不仅能够使用链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访问.由于存储资源有限，因此设计了一种存储资源回收机制对失效结点进行回收.该硬件链表结构在FPGA上进行了实验测试，结果表明，该结构资源占用较少、功耗较低，与PC上的软件链表数据结构相比，硬件链表结构在执行时间上也具有较高的加速比.
1 设计难点及解决方案
由于有编译器和操作系统的支持，软件实现的链表功能强大、灵活，将软件链表的功能和用法完全向硬件平台移植需要克服缺少编译器和操作系统支持所造成的困难，这些困难可以通过改变链表使用方式和充分利用硬件特性来解决.
在软件链表数据结构中，对结点的访问是通过链表指针完成的.读取、删除某个结点时需要从表头遍历若干个结点之后才能定位到待访问结点，增大了输出延迟.在本文的硬件链表结构中，通过充分利用硬件特性，不仅可以通过链表指针对结点进行定位，还可以像传统的线性编址存储器一样直接使用物理地址进行数据访问.
软件链表数据结构中被删除的结点将由操作系统负责回收，但是在本文的硬件链表结构中，由于没有操作系统支持，因此设计了专用的存储资源回收模块，自主管理存储空间的重复使用.
2 硬件链表体系结构设计
硬件链表体系结构主要由5部分组成：存储控制模块MC， 链表控制模块LC， 存储资源回收模块MR， 地址选择模块AS和输出选择模块OS，如图1所示.
当一个操作指令instruction word输入时，LC首先对指令进行解析，得到具体的命令mode，数据data和（或）地址addr，并送入MC，其中addr由AS从外部地址addr_outside（从instruction word中获得）和内部地址addr_inside（内部计算得到的地址）中选择.然后，MC对链表中的数据元素进行操作并输出结果，根据操作指令的不同，所输出的结果可能为结点数据、结点地址或者某些标志位.MR负责将已经失效的结点的地址空间进行回收.OS负责将MC的输出根据操作指令送入不同的部件.
该硬件链表是双向链表，图2给出了数据在链表中的存储格式.链表中每个结点由数据域data， 前向指针prev， 后向指针next和结点是否在链表中标志valid四项组成.定义NULL指针的地址为全1，占用一个地址空间，规定表头结点的前向指针和表尾结点的后向指针都指向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存储模块中，分别称为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进行操作.通常，在对某结点执行读写操作前，需要首先确定该目标结点的位置.如果目标结点在存储器中的物理地址是未知的，可以通过链表指针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输出的数据送入正确的模块.
例如，当对一个已知物理地址的结点进行数据更新操作时，LC对instruction word进行解析得到命令mode为update，数据data为该结点的新数值，而AS所选择的地址addr为从instruction word中获得的该结点的物理地址；接下来MC将位于addr地址的结点数据更新为data；最后，OS将更新后的数值输出作为反馈.
再例如，当希望根据内容确定该结点在链表中的位置时，LC对instruction word进行解析得到命令mode为search，数据data为希望查找的数值，而addr为表头结点的地址；接下来，MC访问表头结点，并将表头结点的数值与输入的data进行比较，若相同，则搜索结束；否则，AS选择的地址为addr_inside，该地址信息为当前结点的next域对应的数值，这样MC就可以访问链表中的下一个结点并进行比较操作.这种过程不断重复直到找到所需的数据或者搜索过程进行到表尾，最后，OS将所搜索到的结点的地址输出，或者输出NULL表示搜索失败.
2.3 存储资源回收模块MR
当删除一个链表结点时，它所占用的地址空间立刻被释放掉.MR通过将该结点的valid域设为0对该结点进行回收.
在向链表中写入一个新结点时，需要找到一个空闲位置，有两种方法可以实现：第一种是指针avail始终指向可写位置，这要求在一次写操作完成后查找空闲位置；第二种方式是写操作到来时才查找空闲位置.第一种方法看起来很好，写结束后链表自动查找可用位置而外部模块进行别的处理，是一种并行工作方式.但是如果进行连续写操作时，必须在链表和外部模块之间进行查询和应答来判断什么时刻可以真正启动写操作，这就大大增加了实现复杂性.第二种方法是一种“懒惰”工作方式，不需要进行显式同步.
本文工作采用第二种方法实现存储空间回收.写请求到来时才开始查找一个可用位置avail，查找到的位置可能是一直空闲的地址或者是因结点已被删除而重新可用的地址.设置标志寄存器LWA，表示上次写入结点的地址，初始化为NULL，指针avail在上次写入操作后指向LWA+1位置.查找过程就是从LWA+1逐个判断，找到第一个满足Valid_Tab[avail]=0的位置，当到达最大地址时再从零地址开始查找直到LWA.如果链表不满，总是可以找到一个空闲位置，否则就不会启动查找过程而是直接终止写操作.
找到可用位置后，向Data_RAM的avail地址中写入新结点的数值data，将NULL作为新元素的后向指针写入Next_RAM.如果写入的是第一个元素，将NULL作为新元素的前向指针，否则将tail_ptr作为前向指针写入Prev_RAM.将valid域置为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应该从外部输入数据中读取地址还是应该从内部模块中读取地址.不同的操作命令获取地址的来源不同，比如，当对一个已知物理地址的结点进行数据更新时，AS选择的地址addr是从instruction word中获得的；而当根据内容确定结点在链表中的位置时，AS选择的地址为从MC输出的当前结点的next域对应的值.地址选择信号addr_sel由LC根据instruction word解析得到.
2.5 输出选择模块OS
OS用来决定链表输出数据的类型.不同的链表操作得到的输出数据类型是不同的，比如，读操作输出所读结点的数据域data，写操作返回写入结点所在的地址.OS由LC控制，LC根据操作类型生成output_sel信号送入OS.
3 硬件链表的应用
应用系统通过将相应的instruction word送入硬件链表实现可变数据集合的维护.
硬件链表结构除了可以实现链表数据结构的基本操作（这些操作针对单个或部分结点进行），还可以实现一些针对所有链表结点的高级功能，比如计算所有链表结点的最大最小值、平均值、累加值或其他一些统计操作.这些全局操作的共同点就是对链表的遍历操作，遍历可以分为单指针遍历和双指针遍历.单指针遍历使用一个指针从表头到表尾依次访问链表元素，适用于计算最大最小值、累加和等操作.双指针遍历使用指针A和B，A首先指向表头，B依次遍历A后面剩余元素，将A前进一个元素，B回到A后面再次遍历，重复上述过程直到A指向表尾.双指针遍历用于关联链表中的一对元素，比如求任意两个元素之间的相似度.本文设计的链表为上述两种遍历提供支持，算法伪代码如图3所示，图中Read操作返回当前结点数值和下一个结点地址.
硬件链表对外提供表头和表尾指针，可以方便地实现堆栈和队列.堆栈是后进先出的表结构，基于链表实现时将进栈元素写在表尾，出栈时删除最后一个元素并返回它的值.队列是先进先出的表结构，基于链表实现时将进入队列元素写在表尾，每次都删除表头元素并返回它的值.
4 实验与分析
本文在FPGA上对硬件链表结构进行了测试，FPGA芯片采用Altera Stratix II EP2S 130F1020 C5，使用Mentor Graphics ModelSim进行仿真，并使用Quartus II进行综合.链表数据宽度设为32位.
本文选择6个不同容量的链表进行测试，资源使用情况和时钟频率如表1所示.由于valid域是使用寄存器数组实现的，当链表容量增大时，需要的寄存器必然会增加，地址译码需要的逻辑单元也会随之增加，译码的逻辑级数增加导致时钟频率下降.根据综合报告，容量小于256时，决定时钟频率的关键路径是从存储器输出到寄存器延迟；容量大于等于256时，决定时钟频率的关键路径是从寄存器到寄存器延迟.理论上链表需要的存储器位数跟链表长度成正比，根据结果进行线性回归可得到两者满足线性关系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上的软件链表需要操作系统进行存储管理，而硬件链表上的存储管理是专门针对链表数据结构优化的，更为高效.对于本次实验中所进行的图3所示的双指针遍历操作，本文提出的硬件链表结构完成该操作在理论上所需要的时钟周期数可粗略表示为n×（n-1），这是因为链表中元素个数为n时，图3所示两层循环的外层迭代次数为n，对于第i次外层迭代（i=0，1，…，n-1），内层迭代的次数为n-i-1，根据等差数列的计算方法，可知共需n×（n-1）/2次迭代，而每次迭代需要至少两个时钟周期完成从链表中读出两个数据的操作，因此可知执行双指针遍历所需的周期数至少为n×（n-1）.设计链表长度为4 096，根据综合结果，此时的工作频率为107 MHz，那么当链表中的有效数据个数分别为表3中第一列所列数值时，从表3中第三列可以看出，实际的实验结果基本符合理论上计算得到的执行时间.