基于FPGA的并行計算技術

1  微處理器與FPGA

微處理器普遍采用馮·諾依曼結構，即存儲程式型計算機結構，主要包括存儲器和運算器2個子系統。其從存儲器讀取資料和指令到運算器，運算結果儲存到存儲器，然後進行下一次讀取-運算-儲存的操作過程。通過開發專門的資料和指令組合，即控制程式，微處理器就可以完成各種計算任務。馮·諾依曼型計算機成功地把資訊處理系統分成了硬體裝置和軟體程式兩部分，使得衆多資訊處理問題都可以在通用的硬體平台上處理，隻需要開發具體的應用軟體，進而極大地降低了開發資訊處理系統的複雜性。然而，馮·諾依曼型計算機也有不足之處，由于資料和指令必須在存儲器和運算器之間傳輸才能完成運算，使得計算速度受到存儲器和運算器之間資訊傳輸速度的限制，形成所謂的馮·諾依曼瓶頸[1]；同時，由于運算任務被分解成一系列依次執行的讀取-運算-儲存過程，是以運算過程在本質上是串行的，使并行計算模式在馮·諾依曼型計算機上的應用受到限制。

受到半導體實體過程的限制，微處理器運算速度的提高已經趨于緩慢，基于多核處理器或者叢集計算機的并行計算技術已經逐漸成為提高計算機運算性能的主要手段。并行計算裝置中包含多個微處理器，可以同時對多組資料進行處理，進而提高系統的資料處理能力。基于叢集計算機的超級計算機已經成為解決大型科學和工程問題的有利工具。然而，由于并行計算裝置中的微處理器同樣受馮·諾依曼瓶頸的制約，是以在處理一些資料密集型，如圖像分析等問題時，計算速度和成本效益不理想。

現場可程式設計門陣列（FPGA）是一種新型的數字電路。傳統的數字電路晶片都具有固定的電路和功能，而FPGA可以直接下載下傳使用者現場設計的數字電路。FPGA技術颠覆了數字電路傳統的設計-流片-封裝的工藝過程，直接在成品PFGA晶片上開發新的數字電路，極大地擴大了專用數字電路的使用者範圍和應用領域。自從20世紀80年代出現以來，FPGA技術迅速發展，FPGA晶片的半導體數量從最初的數萬個迅速發展到現在的數十億個半導體[2]，FPGA的應用範圍也從簡單的邏輯控制電路發展成為重要的高性能計算平台。

FPGA晶片中的每個邏輯門在每個時鐘周期都同時進行着某種邏輯運算，是以FPGA本質上是一個超大規模的并行計算裝置，非常适合用于開發并行計算應用。目前，FPGA已被成功地應用到分子動力學、基因組測序、神經網路、人工大腦、圖像處理、機器博弈等領域，取得了數十到數千倍的速度提高和優異的成本效益[3-18]。

2  FPGA并行算法的設計與開發

FPGA通過邏輯電路實作計算功能，而微處理器則通過程式和存儲器控制計算過程。FPGA和微處理器在基本架構上的根本差別，決定了它們算法的設計理念和方法也存在很大差別[4-5]。與微處理器相比，FPGA最主要的優勢是可以同時對大量變量進行邏輯運算和指派，實作并行運算；而FPGA最主要的劣勢則是失去了微處理器所提供的許多基本計算工具，如浮點數計算、初等函數取值等。在設計FPGA算法時，應該充分發揮FPGA可以同時對大量變量進行邏輯運算和指派的優勢，而盡量避免使用浮點數運算、初等函數取值等數值計算功能，是以并不是任何并行計算問題都适于在FPGA上實作。一般來說，FPGA最适用于需要大量并行邏輯或者整數運算的計算任務。例如，圖像處理應用中的線性除噪、形态學變換、邊緣檢測、模式比對等應用，就非常适合在FPGA上實作[10-16]。

FPGA算法中常用的電路結構包括流水線型和并行陣列型兩種（見圖1）。在流水線型結構中，計算任務被分解成多個子任務，由多個子電路依次完成，多組資料依次進入流水線電路，同時進行不同階段的計算（見圖1（a））。忽略首批資料進入流水線的延遲，流水線型電路處理資料的用時等于所有子任務中最長的用時。如果每個子任務都可以采用組合電路來完成而不需要時序電路，則所有子任務都可以在一個FGPA時鐘内完成，進而實作極高的運算速度和成本效益。

圖 1  流水線型電路和并行陣列型電路

在并行陣列型電路中，多組并行排列的子電路同時接收整體資料的多個部分進行并行計算（見圖1（b））。并行陣列型電路中的子電路本身可以是簡單的組合電路，也可以是複雜的時序電路，如流水線型電路。如果受邏輯資源限制，無法同時處理全部資料，也可以依次處理部分資料，直到完成全部資料的處理。

圖2示出了FPGA系統的開發流程。一般采用硬體描述語言（HDL），如Verilog、VHDL等，實作FPGA并行算法。雖然有一些類似C語言的軟體可以幫助沒有數字電路設計經驗的使用者實作FPGA設計，但是由于包括C語言在内的微處理器程式設計語言蘊含了許多微處理器的計算模式和理念，是以會影響或幹擾FPGA并行算法的實作。使用HDL可以更好地結合FPGA的計算模式，設計出更合理的并行算法。一般選用FPGA開發闆作為FPGA開發和測試的平台。開發過程中所需要完成的功能仿真、設定管腳、編譯綜合等步驟需要依托FPGA供應商提供的編譯和通信測試軟體。

下面以二值形态學腐蝕變換為例，設計一個簡單的并行FPGA算法。如果把一幅二值圖像中所有前景像素的集合稱為A，把某個核心集合稱為B；把該核心中心在x圖像點時所包含的前景像素的集合稱為B(x)，則以B為結構元素的腐蝕變換定義為集合{X|B(x)A}。具體的計算任務是以包含右相鄰和下相鄰像素的核心為結構元素，對多幅6×6的二值圖像進行連續兩次腐蝕變換。采用Verilog語言，設計了一個三級流水線電路（見圖3和圖4）來實作這個計算任務。這個電路處理一幅圖像的平均時間是一個FPGA時鐘。在邏輯資源允許的情況下，相同的算法可以處理任何尺寸的圖像，而且處理時間保持為一個FPGA時鐘。

腐蝕變換電路的Verilog源程式如下：

 3  FPGA在機器博弈方面的應用

機器博弈是智能科學技術的一個重要研究領域。搜尋博弈樹是機器博弈的基本方法。由于博弈樹的狀态空間巨大，是以提高搜尋速度一直是機器博弈領域的重要研究課題。采用專用數字電路可以顯著提高搜尋速度。曾經擊敗國際象棋世界冠軍的機器博弈系統Deep Blue就是采用了專用數字電路來提高樹搜尋的速度[19]。FPGA提供了實作樹搜尋專用數字電路的更便捷的方法。目前已經有人嘗試采用FPGA提高中國象棋和9路圍棋的搜尋速度[17-18]。下面介紹的基于FPGA的9路圍棋博弈系統中吃子算法的設計，展示了FPGA算法設計的特點和方法。

圍棋規則規定，棋盤上的每個棋子本身或者與其相連的棋子必須至少與一個空位相鄰（至少有一口氣），不符合這個規則的棋子必須被拿掉（吃子）。實作這一規則的串行算法是依次在某個棋子本身的4連通點，或者與其相連同色棋子的4連通點搜尋空位。有兩個原因使這個串行算法不适于在FPGA上應用。首先，由于算法是串行的，是以無法在流水線型電路上實作，影響計算速度；其次，由于算法需要可尋址的儲存空間，無法在FPGA上直接實作。

設計以下并行算法來實作吃子規則（見圖4），即不斷地去除與空位直接相連的同色棋子（相當于腐蝕形态學變換），最後剩下的棋子就是需要拿掉的棋子。把這些棋子從棋盤中去掉就完成了吃子規則。這個算法可以通過一個19級流水線電路實作，處理一個棋盤的平均時間隻要一個FPGA時鐘。為了實作流水線型電路，圖4中對棋盤的複制是必需的步驟。這個示例說明了在FPGA上實作并行計算不能簡單翻譯微處理器上的原有算法，而是要根據FPGA和計算問題的具體特點，從新設計相應的并行算法。

圖 4  吃子算法

基于相似的并行算法，用一個167級的流水線實作了模拟黑白雙方各走一步的功能，并在此基礎上實作了對整盤圍棋的蒙特卡羅模拟，比基于微處理器的蒙特卡羅模拟快了170倍[18]。

4  結束語

本文介紹FPGA并行計算技術的基本特點和方法。選擇适當的計算問題，結合FPGA可以對大量變量同時進行邏輯運算和指派的特點，設計高性能的并行算法，可以實作計算速度和成本效益的大幅提高。近年來，FPGA的邏輯資源和運算速度飛速發展，使得FPGA并行計算的應用領域不斷拓展，同時FPGA的設計測試工具也在不斷完善，使得更多數字電路領域之外的科技工作者可以涉足FPGA并行計算，為FPGA高性能計算的爆發性發展提供了條件。作為一個新興的交叉領域，我們期待FPGA并行計算在包括智能科學技術在内的更多領域産生突破性的結果。