可變數(shù)據(jù)集合維護問題的硬件加速結(jié)構與方法

摘要：針對可變數(shù)據(jù)集合維護問題，提出了一種通用的硬件結(jié)構，根據(jù)接收到的操作指令靈活地實現(xiàn)鏈表數(shù)據(jù)結(jié)構的大多數(shù)常用功能，并支持一些高級功能.不僅能夠使用鏈表指針對結(jié)點進行定位，還可以像傳統(tǒng)的線性編址存儲器一樣直接使用物理地址進行數(shù)據(jù)訪問.為了解決存儲資源受限問題，設計了一種存儲資源回收機制對失效結(jié)點進行回收.實驗結(jié)果表明，提出的通用硬件鏈表結(jié)構可以優(yōu)化對可變數(shù)據(jù)進行維護的處理過程，而且該結(jié)構資源占用較少、功耗較低，與PC上的軟件鏈表數(shù)據(jù)結(jié)構相比，硬件鏈表結(jié)構在執(zhí)行時間上也具有較高的加速比.

關鍵詞：可變數(shù)據(jù)集合維護；硬件加速；鏈表

中圖分類號：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

在數(shù)字圖像處理領域^[1]，尤其是在目標識別與跟蹤應用中[2-5]，經(jīng)常會遇到可變數(shù)據(jù)集合維護問題.當對圖像中的目標進行識別跟蹤時，需要首先將圖像中的一個或多個可能包含運動目標的興趣區(qū)域信息提取出來，這些區(qū)域信息形成一個數(shù)據(jù)集合.隨著處理過程的推進，可能會發(fā)現(xiàn)新的興趣區(qū)域，這就需要在該數(shù)據(jù)集合中加入該興趣區(qū)域的信息；當某個興趣區(qū)域被排除后，需要從該數(shù)據(jù)集合中把對應的信息去掉；另外，有些興趣區(qū)域可能需要進行合并、分割[1，6].因此，這種數(shù)據(jù)集合中的數(shù)據(jù)元素是不斷變化的，需要一種合適的數(shù)據(jù)結(jié)構對該數(shù)據(jù)集合進行組織和維護，所采用的數(shù)據(jù)結(jié)構必須能夠使得其中的數(shù)據(jù)元素可以被靈活地存取和操作.

鏈表數(shù)據(jù)結(jié)構可以滿足這種需求.鏈表支持隨機訪問和刪除，每個結(jié)點使用指針指向其前驅(qū)和（或）后繼結(jié)點.在硬件數(shù)字圖像處理系統(tǒng)中，當遇到這類可變數(shù)據(jù)集合維護問題時，需要設計相應的硬件鏈表結(jié)構.然而現(xiàn)有的存儲結(jié)構不能完全實現(xiàn)鏈表數(shù)據(jù)結(jié)構的功能.首先，若將數(shù)據(jù)集合保存在線性編址存儲器中，當一個元素合并到另一個元素中或者不滿足特定規(guī)則而被過濾掉時，這個元素將被刪除，這就要求標記該地址上的元素不再有效，也就是必須維護一個元素地址的集合，然而這個地址集合也必須存儲在一個存儲器中，又回歸到可變數(shù)據(jù)集合維護問題.其次，現(xiàn)有的FIFO存儲器也無法完全滿足要求，F(xiàn)IFO只有一個讀端口且只能順序讀取數(shù)據(jù)，而在多個元素執(zhí)行合并操作時需要同時讀取多個信息，F(xiàn)IFO數(shù)據(jù)只能讀取一次，不能滿足對數(shù)據(jù)元素的多遍處理.人們已經(jīng)設計實現(xiàn)了一些針對具體應用的硬件鏈表結(jié)構，如，魏本杰等人設計了硬件鏈表并將其應用于三維多分等級樹編碼^[7]； Lu等人設計了硬件鏈表結(jié)構并應用于FPGA的在線布局操作^[8]，用來在對FPGA進行動態(tài)重構時保存FPGA上空閑矩形區(qū)域的相關信息；Papaefstathiou等人將硬件鏈表結(jié)構應用于網(wǎng)絡處理器中的隊列管理^[9]，等等.這些硬件鏈表結(jié)構大多為面向某個特定應用，具有一定的專用性.

本文設計了一種通用的高速硬件鏈表結(jié)構.這種硬件鏈表結(jié)構可以根據(jù)接收到的操作指令實現(xiàn)鏈表數(shù)據(jù)結(jié)構的大多數(shù)常用功能，比如增加或刪除數(shù)據(jù)結(jié)點、對某個特定結(jié)點進行讀取或更新操作、基于數(shù)據(jù)內(nèi)容進行結(jié)點定位等，另外該結(jié)構還支持一些高級功能.該鏈表結(jié)構不僅能夠使用鏈表指針對結(jié)點進行定位，還可以像傳統(tǒng)的線性編址存儲器一樣直接使用物理地址進行數(shù)據(jù)訪問.由于存儲資源有限，因此設計了一種存儲資源回收機制對失效結(jié)點進行回收.該硬件鏈表結(jié)構在FPGA上進行了實驗測試，結(jié)果表明，該結(jié)構資源占用較少、功耗較低，與PC上的軟件鏈表數(shù)據(jù)結(jié)構相比，硬件鏈表結(jié)構在執(zhí)行時間上也具有較高的加速比.

1 設計難點及解決方案

由于有編譯器和操作系統(tǒng)的支持，軟件實現(xiàn)的鏈表功能強大、靈活，將軟件鏈表的功能和用法完全向硬件平臺移植需要克服缺少編譯器和操作系統(tǒng)支持所造成的困難，這些困難可以通過改變鏈表使用方式和充分利用硬件特性來解決.

在軟件鏈表數(shù)據(jù)結(jié)構中，對結(jié)點的訪問是通過鏈表指針完成的.讀取、刪除某個結(jié)點時需要從表頭遍歷若干個結(jié)點之后才能定位到待訪問結(jié)點，增大了輸出延遲.在本文的硬件鏈表結(jié)構中，通過充分利用硬件特性，不僅可以通過鏈表指針對結(jié)點進行定位，還可以像傳統(tǒng)的線性編址存儲器一樣直接使用物理地址進行數(shù)據(jù)訪問.

軟件鏈表數(shù)據(jù)結(jié)構中被刪除的結(jié)點將由操作系統(tǒng)負責回收，但是在本文的硬件鏈表結(jié)構中，由于沒有操作系統(tǒng)支持，因此設計了專用的存儲資源回收模塊，自主管理存儲空間的重復使用.

2 硬件鏈表體系結(jié)構設計

硬件鏈表體系結(jié)構主要由5部分組成：存儲控制模塊MC， 鏈表控制模塊LC， 存儲資源回收模塊MR， 地址選擇模塊AS和輸出選擇模塊OS，如圖1所示.

當一個操作指令instruction word輸入時，LC首先對指令進行解析，得到具體的命令mode，數(shù)據(jù)data和（或）地址addr，并送入MC，其中addr由AS從外部地址addr_outside（從instruction word中獲得）和內(nèi)部地址addr_inside（內(nèi)部計算得到的地址）中選擇.然后，MC對鏈表中的數(shù)據(jù)元素進行操作并輸出結(jié)果，根據(jù)操作指令的不同，所輸出的結(jié)果可能為結(jié)點數(shù)據(jù)、結(jié)點地址或者某些標志位.MR負責將已經(jīng)失效的結(jié)點的地址空間進行回收.OS負責將MC的輸出根據(jù)操作指令送入不同的部件.

該硬件鏈表是雙向鏈表，圖2給出了數(shù)據(jù)在鏈表中的存儲格式.鏈表中每個結(jié)點由數(shù)據(jù)域data， 前向指針prev， 后向指針next和結(jié)點是否在鏈表中標志valid四項組成.定義NULL指針的地址為全1，占用一個地址空間，規(guī)定表頭結(jié)點的前向指針和表尾結(jié)點的后向指針都指向NULL.如果鏈表地址寬度為W，那么鏈表最大長度為2W-1.此外，為了便于遍歷鏈表和插入新結(jié)點，對外提供表頭指針head_ptr和表尾指針tail_ptr，以及當前鏈表中的結(jié)點數(shù)目no_items.圖2中所示的鏈表容量為255，當前長度為4，表頭地址是00，表尾地址是03.

2.1 存儲控制模塊MC

MC對鏈表中的數(shù)據(jù)元素進行操作并輸出結(jié)果.在硬件實現(xiàn)時，通常需要對每個結(jié)點的data， prev， next和valid域同時進行訪問.因此，為了實現(xiàn)并行訪問，data， prev和next分別保存在3個不同的RAM存儲模塊中，分別稱為Data_RAM，Prev_RAM和Next_RAM.每個RAM都是雙端口的，可以同時進行讀寫.valid域的存儲模塊稱為Valid_Tab，由于valid域讀寫頻繁，并且其數(shù)據(jù)量小、FPGA提供豐富的寄存器資源，本文使用寄存器數(shù)組實現(xiàn)Valid_Tab，這樣既可以降低邏輯復雜性，又可以避免訪問RAM的長延遲.

MC從LC獲得具體的命令mode，數(shù)據(jù)data和（或）地址addr，并對Data_RAM， Prev_RAM， Next_RAM和Valid_Tab進行操作.通常，在對某結(jié)點執(zhí)行讀寫操作前，需要首先確定該目標結(jié)點的位置.如果目標結(jié)點在存儲器中的物理地址是未知的，可以通過鏈表指針prev或next從其他結(jié)點不斷遍歷到目標結(jié)點；如果物理地址是已知的，就可以直接通過物理地址對該結(jié)點進行定位.

2.2 鏈表控制模塊LC

LC使用狀態(tài)機控制整個鏈表結(jié)構的運行.它對輸入的instruction word進行解析，得到具體的命令mode，數(shù)據(jù)data和（或）地址addr，并送入MC；同時LC還控制AS從addr_outside和addr_inside中選擇合適的地址；當命令mode為刪除命令delete時，LC將控制MR對被刪除的結(jié)點空間進行回收；另外，LC還控制OS將MC輸出的數(shù)據(jù)送入正確的模塊.

例如，當對一個已知物理地址的結(jié)點進行數(shù)據(jù)更新操作時，LC對instruction word進行解析得到命令mode為update，數(shù)據(jù)data為該結(jié)點的新數(shù)值，而AS所選擇的地址addr為從instruction word中獲得的該結(jié)點的物理地址；接下來MC將位于addr地址的結(jié)點數(shù)據(jù)更新為data；最后，OS將更新后的數(shù)值輸出作為反饋.

再例如，當希望根據(jù)內(nèi)容確定該結(jié)點在鏈表中的位置時，LC對instruction word進行解析得到命令mode為search，數(shù)據(jù)data為希望查找的數(shù)值，而addr為表頭結(jié)點的地址；接下來，MC訪問表頭結(jié)點，并將表頭結(jié)點的數(shù)值與輸入的data進行比較，若相同，則搜索結(jié)束；否則，AS選擇的地址為addr_inside，該地址信息為當前結(jié)點的next域?qū)臄?shù)值，這樣MC就可以訪問鏈表中的下一個結(jié)點并進行比較操作.這種過程不斷重復直到找到所需的數(shù)據(jù)或者搜索過程進行到表尾，最后，OS將所搜索到的結(jié)點的地址輸出，或者輸出NULL表示搜索失敗.

2.3 存儲資源回收模塊MR

當刪除一個鏈表結(jié)點時，它所占用的地址空間立刻被釋放掉.MR通過將該結(jié)點的valid域設為0對該結(jié)點進行回收.

在向鏈表中寫入一個新結(jié)點時，需要找到一個空閑位置，有兩種方法可以實現(xiàn)：第一種是指針avail始終指向可寫位置，這要求在一次寫操作完成后查找空閑位置；第二種方式是寫操作到來時才查找空閑位置.第一種方法看起來很好，寫結(jié)束后鏈表自動查找可用位置而外部模塊進行別的處理，是一種并行工作方式.但是如果進行連續(xù)寫操作時，必須在鏈表和外部模塊之間進行查詢和應答來判斷什么時刻可以真正啟動寫操作，這就大大增加了實現(xiàn)復雜性.第二種方法是一種“懶惰”工作方式，不需要進行顯式同步.

本文工作采用第二種方法實現(xiàn)存儲空間回收.寫請求到來時才開始查找一個可用位置avail，查找到的位置可能是一直空閑的地址或者是因結(jié)點已被刪除而重新可用的地址.設置標志寄存器LWA，表示上次寫入結(jié)點的地址，初始化為NULL，指針avail在上次寫入操作后指向LWA+1位置.查找過程就是從LWA+1逐個判斷，找到第一個滿足Valid_Tab[avail]=0的位置，當?shù)竭_最大地址時再從零地址開始查找直到LWA.如果鏈表不滿，總是可以找到一個空閑位置，否則就不會啟動查找過程而是直接終止寫操作.

找到可用位置后，向Data_RAM的avail地址中寫入新結(jié)點的數(shù)值data，將NULL作為新元素的后向指針寫入Next_RAM.如果寫入的是第一個元素，將NULL作為新元素的前向指針，否則將tail_ptr作為前向指針寫入Prev_RAM.將valid域置為1.將avail作為寫入前表尾元素的后向指針寫入Next_RAM，同時將LWA和tail_ptr指向avail，寫入第一個元素時要將head_ptr指向avail，將元素數(shù)目寄存器no_items都加1.

設鏈表地址寬度為W，最好的情況是查找之前avail位置就可用，比較1次；最壞情況是最后一個位置可用，比較2W-1次，平均比較次數(shù)是（2W-1+1）/2=2W-1.

2.4 地址選擇模塊AS

AS用來決定MC應該從外部輸入數(shù)據(jù)中讀取地址還是應該從內(nèi)部模塊中讀取地址.不同的操作命令獲取地址的來源不同，比如，當對一個已知物理地址的結(jié)點進行數(shù)據(jù)更新時，AS選擇的地址addr是從instruction word中獲得的；而當根據(jù)內(nèi)容確定結(jié)點在鏈表中的位置時，AS選擇的地址為從MC輸出的當前結(jié)點的next域?qū)闹?地址選擇信號addr_sel由LC根據(jù)instruction word解析得到.

2.5 輸出選擇模塊OS

OS用來決定鏈表輸出數(shù)據(jù)的類型.不同的鏈表操作得到的輸出數(shù)據(jù)類型是不同的，比如，讀操作輸出所讀結(jié)點的數(shù)據(jù)域data，寫操作返回寫入結(jié)點所在的地址.OS由LC控制，LC根據(jù)操作類型生成output_sel信號送入OS.

3 硬件鏈表的應用

應用系統(tǒng)通過將相應的instruction word送入硬件鏈表實現(xiàn)可變數(shù)據(jù)集合的維護.

硬件鏈表結(jié)構除了可以實現(xiàn)鏈表數(shù)據(jù)結(jié)構的基本操作（這些操作針對單個或部分結(jié)點進行），還可以實現(xiàn)一些針對所有鏈表結(jié)點的高級功能，比如計算所有鏈表結(jié)點的最大最小值、平均值、累加值或其他一些統(tǒng)計操作.這些全局操作的共同點就是對鏈表的遍歷操作，遍歷可以分為單指針遍歷和雙指針遍歷.單指針遍歷使用一個指針從表頭到表尾依次訪問鏈表元素，適用于計算最大最小值、累加和等操作.雙指針遍歷使用指針A和B，A首先指向表頭，B依次遍歷A后面剩余元素，將A前進一個元素，B回到A后面再次遍歷，重復上述過程直到A指向表尾.雙指針遍歷用于關聯(lián)鏈表中的一對元素，比如求任意兩個元素之間的相似度.本文設計的鏈表為上述兩種遍歷提供支持，算法偽代碼如圖3所示，圖中Read操作返回當前結(jié)點數(shù)值和下一個結(jié)點地址.

硬件鏈表對外提供表頭和表尾指針，可以方便地實現(xiàn)堆棧和隊列.堆棧是后進先出的表結(jié)構，基于鏈表實現(xiàn)時將進棧元素寫在表尾，出棧時刪除最后一個元素并返回它的值.隊列是先進先出的表結(jié)構，基于鏈表實現(xiàn)時將進入隊列元素寫在表尾，每次都刪除表頭元素并返回它的值.

4 實驗與分析

本文在FPGA上對硬件鏈表結(jié)構進行了測試，F(xiàn)PGA芯片采用Altera Stratix II EP2S 130F1020 C5，使用Mentor Graphics ModelSim進行仿真，并使用Quartus II進行綜合.鏈表數(shù)據(jù)寬度設為32位.

本文選擇6個不同容量的鏈表進行測試，資源使用情況和時鐘頻率如表1所示.由于valid域是使用寄存器數(shù)組實現(xiàn)的，當鏈表容量增大時，需要的寄存器必然會增加，地址譯碼需要的邏輯單元也會隨之增加，譯碼的邏輯級數(shù)增加導致時鐘頻率下降.根據(jù)綜合報告，容量小于256時，決定時鐘頻率的關鍵路徑是從存儲器輸出到寄存器延遲；容量大于等于256時，決定時鐘頻率的關鍵路徑是從寄存器到寄存器延遲.理論上鏈表需要的存儲器位數(shù)跟鏈表長度成正比，根據(jù)結(jié)果進行線性回歸可得到兩者滿足線性關系y=52.41x-746.99.

為了對硬件鏈表結(jié)構的處理速度進行評價，本文對圖3所示的雙指針遍歷操作進行了測試.測試過程不對鏈表數(shù)據(jù)進行任何處理，只是將它們從鏈表中按雙指針遍歷的順序讀出.表3給出了FPGA上的硬件鏈表結(jié)構和PC（Pentium 4 2.8GHz CPU， 512MB內(nèi)存）上的軟件鏈表的性能比較，結(jié)果表明，硬件鏈表的處理速度比軟件鏈表數(shù)據(jù)結(jié)構的處理速度快，對于長度分別為32， 64， 128， 256， 512， 1 024， 2 048和4 096的鏈表，硬件鏈表結(jié)構與軟件鏈表相對于雙指針遍歷操作在執(zhí)行速度上的加速比最少為6.56，最大達到1 362.8.加速比隨著鏈表長度的增加而增加，原因在于PC上的軟件鏈表需要操作系統(tǒng)進行存儲管理，而硬件鏈表上的存儲管理是專門針對鏈表數(shù)據(jù)結(jié)構優(yōu)化的，更為高效.對于本次實驗中所進行的圖3所示的雙指針遍歷操作，本文提出的硬件鏈表結(jié)構完成該操作在理論上所需要的時鐘周期數(shù)可粗略表示為n×（n-1），這是因為鏈表中元素個數(shù)為n時，圖3所示兩層循環(huán)的外層迭代次數(shù)為n，對于第i次外層迭代（i=0，1，…，n-1），內(nèi)層迭代的次數(shù)為n-i-1，根據(jù)等差數(shù)列的計算方法，可知共需n×（n-1）/2次迭代，而每次迭代需要至少兩個時鐘周期完成從鏈表中讀出兩個數(shù)據(jù)的操作，因此可知執(zhí)行雙指針遍歷所需的周期數(shù)至少為n×（n-1）.設計鏈表長度為4 096，根據(jù)綜合結(jié)果，此時的工作頻率為107 MHz，那么當鏈表中的有效數(shù)據(jù)個數(shù)分別為表3中第一列所列數(shù)值時，從表3中第三列可以看出，實際的實驗結(jié)果基本符合理論上計算得到的執(zhí)行時間.

5 結(jié) 論

本文研究了對圖像中的運動目標檢測提取過程進行硬件加速的算法、體系結(jié)構等關鍵問題，然后針對運動目標檢測提取過程中的“可變數(shù)據(jù)集合維護問題”進行了存儲優(yōu)化，提出了一種通用的高速硬件鏈表結(jié)構，對該結(jié)構的設計思路與設計方法進行了詳細介紹.實驗結(jié)果表明，使用硬件加速技術可以大大提高運動檢測提取過程的處理速度，使用較少的硬件代價從原始圖像中過濾掉了大量無關信息，從而避免了后續(xù)的目標識別與跟蹤模塊對該運動區(qū)域以外數(shù)據(jù)的處理，提高了處理效率.而通用硬件鏈表結(jié)構則優(yōu)化了對可變數(shù)據(jù)進行維護的處理過程，具體到目標識別跟蹤應用，可以用來提高對運動區(qū)域進行更新、合并等操作的靈活性.

參考文獻

[1] GONZALEZ R C， WOODS R E. Digital image processing [M]. 2nd ed. New Jersey， USA： Prentice Hall， 2002.

[2] DOU Y， XU J. FPGA-Accelerated Active Shape Model for Real-Time People Tracking [C]//LYNN C. Proceedings of the Asia-Pacific Computer Systems Architecture Conference. Berlin Heidelberg： Springer， 2007： 268-279.

[3] GAVRILA D M， PHILOMIN V. Real-time object detection for smart vehicles [C]//Proceedings of International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 1999： 87-93.

[4] HEZEL S， GAVRILA D， KUGEL A， et al. FPGA-based template matching using distance transforms [C]//Proceedings of 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. New York： IEEE， 2002：89-97.

[5] XU J， DOU Y. Robust and real-time automatic target recognition using partial hausdorff distance measure on reconfigurable hardware [C]//Proceedings of IEEE International Conference on Field-Programmable Technology. New York： IEEE， 2006：25-32.

[6] SONKA M， HLAVAC V， BOYLE R. Image processing， analysis， and machine vision [M]. 2nd ed. Pacific Grove， CA： Brooks/Cole， 1999.

[7] 魏本杰，劉明業(yè)，張曉昆，等.三維多分等級樹算法的VLSI設計與仿真 [J].計算機輔助設計與圖形學學報，2006，18（12）： 1867-1871.

WEI Ben-jie， LIU Ming-ye， ZHANG Xiao-kun， et al. VLSI design and simulation of the 3D SPIHT algorithm [J]. Journal of Computer-Aided Design Computer Graphics， 2006， 18（12）： 1867-1871. （In Chinese）

[8] LU Y， MARCONI T， GAYDADJIEV G， et al. An efficient algorithm for free resources management on the FPGA [C]//Proceedings of the Conference on Design， Automation and Test in Europe. Washington， DC： IEEE Computer Society，2008： 1095-1098.

[9] PAPAEFSTATHIOU I， ORPHANOUDAKIS T， KORNAROS G， et al. Queue management in network processors [C]//Proceedings of the Conference on Design， Automation and Test in Europe. Washington， DC： IEEE Computer Society， 2005： 112-117.