基于FPGA的圖著色問題求解

張益豪 張子超 劉小青② 冷 煌② 王之元 許 進②

①(北京大學信息科學技術學院 北京 100871)

②(北京大學高可信軟件技術教育部重點實驗室 北京 100871)

③(國防科技創新研究院人工智能研究中心 北京 100073)

1 引言

圖著色問題是計算機科學中的一項重要研究內容，不論在理論還是應用方面均具有重要的研究價值。例如，圖著色問題可應用于求解第4代移動通信系統中設備到設備通信的資源分配問題[1]，將大量目標程序分配給少量中央處理器(C e n t r a l Processing Unit, CPU)中寄存器的寄存器分配問題[2]，在滿足一定約束條件下的時間表安排問題等[3]。盡管圖著色問題在實際生活中應用廣泛，但該問題屬于NP-完全問題，因此如何尋找精確算法來求解NP-完全問題一直是近年來研究的熱點[4]。然而，NP-完全問題的一個重要特性是如果采用窮舉法求解，隨著問題規模的增加，時間復雜度將會以指數級增長[5]。因此，一些算法被提出以降低求解圖著色問題的時間復雜度，常見的算法包括動態規劃、分支定界、整數線性規劃以及回溯法。

動態規劃、分支定界與整數線性規劃均可求得圖著色問題的一組解，但有時求得圖著色問題的所有可行解是有意義的。例如，當一個圖G=(V,E)存在一條割邊e=時 ，其中V={v1,v2,...,vn}是由頂點vi構成的集合且E={e1,e2,...,em}是由邊ei構成的集合，則G-e的兩個連通分量可以作為兩個圖分別進行圖著色。此時，由于G-e的兩個連通分量僅通過割邊e=連接，因此只要vs與vt的 顏色不同，就能夠得到原圖G的一組有效著色方案。若G-e的兩個連通分量著色完成后vs與vt的顏色相同，則可通過置換函數改變任一連通分量的著色方案，使得vs與vt的顏色不同。回溯法[11]一般用來求解圖著色問題的所有解，其基本思想是以深度優先搜索整個解空間，同時通過剪枝來減小所需搜索解空間的大小。

通常求解圖著色問題的算法是在通用處理器上利用軟件所實現的。然而，隨著頂點規模的增加，通過軟件實現圖著色算法會造成通用處理器性能的下降以及能耗的提升。盡管已經存在許多軟件解決方案來提高求解圖相關問題的性能與能量效率，但當前通用處理器的硬件結構仍然是影響性能和能量效率的一個重要因素[12]。現場可編程邏輯門陣列(Field Programmable Gate Array, FPGA)是由可配置邏輯塊(Configurable Logic Blocks, CLBs)，輸入輸出(Input/Output, I/O)模塊與可編程的互連資源所構成的可編程邏輯電路[13]。FPGA具有能耗低，開發周期短，易于對設計中出現的錯誤及時修正，以及適用于實時性系統和分布式系統等特點[14]，因此與圖相關的問題能夠基于FPGA設計專用硬件電路來求解[15]。

2 圖著色問題的回溯算法

回溯法求解圖著色問題的思路是對圖的所有可能著色方案進行搜索，并判斷著色方案是否滿足相鄰頂點所分配的顏色不同。以未著色的圖作為根節點，依據圖中頂點與頂點之間的鄰接關系和深度優先搜索策略，從根節點出發遍歷圖中的每個頂點，從而對解空間進行遍歷。在每一次訪問圖中節點的過程中，需要判斷當前節點是否存在滿足圖著色問題約束的著色方案。若存在滿足約束的顏色，則對該節點進行著色并從該節點繼續遍歷未訪問的節點；若不存在滿足約束的顏色，則逐層向該節點的祖先節點回溯，從而完成剪枝，避免對以該節點為根節點的子樹進行搜索。

接下來本文以對圖1中的平面圖進行四著色為例說明回溯法的流程。在圖1中，數字表示頂點標號。利用回溯法，可以得到圖1的24種著色方案，如圖2所示。詳細來說，圖2中樹的根節點(樹的第1層)表示所有的頂點均未著色，樹的第i層表示已有(i-1)個 頂點著色，且連接第i層 與第(i+1)層邊的顏色表示頂點i被分配的顏色。假設先用紅色對頂點1進行著色，當對頂點2進行著色時，由于頂點1與頂點2連接，若為頂點2分配紅色，則相鄰頂點具有相同的顏色，此時不滿足圖著色問題的約束。因此只能用綠色、紫色、咖啡色之一對頂點2進行著色。若存在所有著色方案均無效的頂點，則返回該頂點的父節點，改變父節點的著色方案。

圖1 四頂點平面圖

由圖2可以看出，圖1的四頂點平面圖共有24種著色方案。然而，給定任意一種著色方案，剩余的著色方案可以根據置換函數得到。圖1的色組劃分[16]是唯一的，則其獨立著色方案集(其中任意一個方案都不能通過其他著色方案經置換函數得到)僅有1個元素。因此，如果利用回溯法僅求取獨立著色方案集，可以減小搜索解空間的大小。除此之外，在FPGA中，存儲容量主要由隨機存取存儲器(Random Access Memory, RAM)的大小決定。FPGA內部的RAM由塊RAM(Block RAM)和分布式RAM(Distributed RAM)組成[17]。給定FPGA型號，Block RAM的大小是固定的。Distributed RAM由查找表(Look Up Table, LUT)構成，會占用FPGA內部大量的邏輯資源[18]。因此相比于通用處理器，FPGA內部的存儲資源受限[19]。隨著圖的頂點數逐漸增大，求取所有的四著色方案不僅會增加時間復雜度，也有可能造成需存儲解的個數以指數級增長。因此，為了減小在FPGA內部存儲所求解的數量，需要求取圖的獨立著色方案集。

圖2 四頂點平面圖的著色方案

令Kn′表示n′個頂點的完全圖，由于任意兩個頂點之間都存在一條邊，則要使Kn′滿足圖著色問題的約束，至少需要n′種顏色。因此一個S-可著色的圖G只能含有n′≤S的完全子圖Kn′，其中n′≤S。若圖G的最大完全子圖頂點數為T，則將圖G記為GT。首先利用T種顏色對任一最大完全子圖中的T個頂點著色并固定這T個頂點的著色方案。接下來利用回溯法對GT中剩余頂點進行著色，則能夠有效避免圖著色問題中解的同構性。綜上所述，依據圖G的最大完全子圖的頂點數，可將圖G分為不同的類型。例如，4-可著色圖可以分為G2,G3,G4。算法的流程圖如圖3所示。

圖3 回溯法算法流程圖

3 基于FPGA的圖著色實現方案

FPGA通常自頂向下地設計層次化及正則化的模塊，其中正則化設計指的是最大化利用已設計的模塊以提高模塊的復用率。每個模塊具有不同的功能，通過上層模塊對下層模塊的調用來實現最終的功能函數。合理地設計模塊劃分可以將復雜的問題轉化為較小的問題，從而簡化設計的復雜度[20]。本文將基于回溯法的圖著色問題求解分為3個模塊，分別是輸入模塊、核心計算模塊與輸出模塊，如圖4所示。3個模塊共享時鐘源信號clk與低有效復位信號rst_n。接下來以圖的四著色問題為例說明該流程圖。

圖4 基于FPGA的圖著色實現方案

在輸入系統中，輸入信號data_in由兩部分組成：圖G的鄰接矩陣與圖類型G2,G3,G4的表示信號initial_state，其中initial_state是兩比特的信號，01, 10與11分別表示G2,G3與G4。圖類型表示信號initial_state代表圖G的最大完全子圖，而求解圖G的最大完全子圖也屬于NP完全問題。為了簡化求解的復雜度，本文在通用處理器上采用啟發式算法求取圖G的最大完全子圖。值得注意的是，即使求取圖G的完全子圖并不是最大的，只會造成FPGA內部所需存儲解的個數增加，而不會影響圖著色問題的求解。圖G的鄰接矩陣通過串行的方式傳輸到輸入系統中，輸入系統利用一塊RAM實現串并轉換：RAM中每一個地址ram_addr_rd對應一個頂點，而ram_addr_rd對應的值為與該頂點相鄰的信息。即輸入系統通過從核心計算系統獲得ram_addr_rd來確定當前正在對哪個頂點進行著色，而輸入系統根據ram_addr_rd讀取RAM中代表該頂點鄰域信息的data_internal信號并傳送給核心計算系統。輸入信號的有效使能data_en用來表明輸入數據中哪些信號是有效的。在系統初始化時，核心計算系統處于空閑狀態，而當輸入模塊接收整個鄰接矩陣與圖類型信號后，用來表示信號已接收完成的一個脈沖信號initial_en被傳送給核心計算系統，表明核心計算系統可以開始進行圖著色的相關運算。

在核心計算系統中，當接收到initial_en信號后，根據圖的類型信息initial_state對前T個頂點進行固定的著色初始化。通過ram_addr_rd信號來控制從輸入系統中讀取哪個頂點的鄰域信息。核心系統中增加一個信號v_color_yn表示對應的頂點是否被著色。若未著色則從第1種顏色開始嘗試，若已著色則根據當前著色計算下一個可能的著色方案color_next。結合data_internal，v_color_yn和color_next來判斷當前頂點的鄰接頂點是否存在相同的著色。若不存在則將color_next賦值給包含所有頂點著色方案的信號color_vector，若存在則依據color_next的值決定是否需要回溯。回溯的操作可以通過改變ram_addr_rd的值來回溯到當前節點的父節點。若核心計算系統通過運算得到一種有效的四著色方案時，則將著色方案信號color_vector和表示著色方案有效的使能信號result_en傳送到輸出系統進行保存。當所有的著色方案完成遍歷后，核心運算系統會將done_en信號置為有效位，表明所有運算已結束。若運算已結束并且result_en始終無效，則說明當前圖不存在有效的著色方案。由于圖著色方案可能存在大量的解，而解的數量無法預先得知。同時，FPGA內部用來存儲解的RAM是預先固定好的，且FPGA內部能夠用來存儲的RAM 容量受限。因此當輸出系統無法保存新的著色方案時，需要置full_en有效，使核心系統停止當前的運算，并保存當前運算的信息。待輸出系統中的RAM有新的存儲空間接收著色方案時，置full_en無效，此時核心計算系統繼續進行之前的運算。注意到回溯法中每一次迭代的主要步驟是驗證當前節點的著色與其鄰接節點的著色是否相同，該驗證可以通過或運算實現。即只要存在一個鄰接頂點的著色與當前節點的著色相同，則當前節點無法著色，需要改變著色方案或進行回溯。

在輸出系統中，result_en信號用來判斷當前著色方案color_vector是否有效。若有效則將color_vector存儲在RAM中，若當前RAM中存儲的著色方案個數已達到最大值，則置full_en有效，使得核心計算系統停止當前運算。根據輸入使能信號output_en與output_en_all來決定是否將RAM中的著色方案輸出，其中output_en 1次只輸出1個有效著色方案，而output_en_all一次性將所有著色方案全部輸出。RAM中存儲的著色方案通過并串轉換生成data_out信號輸出，使能信號data_out_en用來表明當前輸出是否有效。注意到圖著色問題可能無解，因此本文利用信號solution_yn表示該圖是否存在有效的著色方案。

4 硬件實現

本文在型號為EP4CE6E22C8的FPGA上，利用Verilog語言實現了基于回溯法的圖的四著色問題求解。在Altera平臺的Quartus Prime 18.0的開發環境中經過綜合后，得到圖的頂點個數與FPGA內部資源消耗的關系，如表1所示。在表1中，本文采用邏輯元件(Logic Element, LE)和寄存器的個數來表示FPGA內部的資源。LE是構成FPGA中CLB模塊的重要單元，通常用來實現邏輯電路[21]。不同的FPGA型號會有不同數量的LE，例如EP4CE6E22C8僅有6000個LE，而Stratix GX10M擁有10200000個LE[22]。由表1可以看出FPGA內部的資源LE與寄存器均基本與圖的頂點個數成正比，造成這種現象的主要原因是表示頂點是否被著色的信號v_color_yn與頂點著色方案信號color_vector所需的比特數與頂點數成正比，且驗證當前節點著色方案與鄰接節點著色是否相同是通過或運算實現的，而或運算的操作數是color_vector。表1的資源消耗主要用于實現圖4的輸入系統、核心計算系統與輸出系統。但在輸入輸出系統中并不包含用于和外部通信的傳輸協議模塊。

表1 FPGA資源消耗

接下來以12頂點的圖四著色為例，分析基于FPGA的圖著色算法性能。進行靜態時序分析后，得到當FPGA內核電壓為1.2 V，溫度為85°C時，系統允許工作的最大時鐘頻率為139.65 MHz，而當FPGA內核電壓為1.2 V，溫度為0°C時，系統允許工作的最大時鐘頻率為147.17 MHz。由圖3的回溯算法流程圖可知，算法的運行復雜度由改變頂點著色方案的次數和每次迭代時判斷能否著色所消耗的時間共同決定。由于在FPGA平臺上實現圖著色算法不能減小改變頂點著色方案的次數，因此僅需考慮回溯法中每次迭代所消耗的時間。圖5可以看出每次color_next的改變最多僅需10個時鐘周期，注意到每次頂點著色方案的改變所需時間周期并不固定，這是因為除了判斷當前著色方案是否有效外，還需根據是否回溯改變ram_addr_rd以選取當前著色的頂點。因此，若FPGA內部使用100 MHz的時鐘，則每次迭代所消耗的時間為10/100=0.1 μs。同時，在主頻為3.0 GHz的通用處理器中，利用Matlab對1000組12頂點的圖進行四著色，平均每次迭代所消耗的平均時間為5.397 μs。由此可見，相比于在通用處理器中采用軟件實現圖著色算法，基于FPGA實現的圖著色算法執行速度更快。若采用性能更高的FPGA，可以進一步提高系統允許工作的最大時鐘頻率，從而減小基于回溯法求解圖著色問題的時間。

圖5 頂點著色方案驗證的功能仿真

隨著頂點個數的增加，在每次迭代中判斷當前著色方案是否有效所需的運算量增加。具體來說，利用3個周期的或運算來判斷當前頂點的著色方案是否與鄰接節點著色方案相同。本文基于空間換時間的思想，通過增加單個周期內或運算的個數，保證每次迭代時FPGA內部運算所需時鐘周期個數與頂點的個數無關。因此隨著頂點個數的增加，每次color_next的改變仍然僅需10個周期，且每次迭代時FPGA執行運算所消耗的時間與頂點個數無關。而隨著頂點個數的增加，每次迭代時軟件實現方案會消耗更多的時間。例如當圖的頂點個數為512時，利用Matlab實現每次迭代所消耗的時間為15.611 μs。

為了驗證所實現硬件的正確性，本文基于通用異步收發傳輸器協議實現了FPGA與通用處理器之間的通信。對具有如圖6所示鄰接矩陣A的12頂點圖G進行著色。根據該圖的類型，通用處理器需將146 bit信息傳輸到FPGA中，其中前144 bit為鄰接矩陣A的1維表示，最后2 bit信息是表示圖類型的initial_state信號。基于16進制將該146 bit表示為961186010D2B29AA59029BB2E582DD24622 D01，并將該信息通過串口傳輸到FPGA內部進行運算。通過將FPGA運算的結果與通用處理器中圖著色的運算結果對比，驗證了FPGA內部輸出的解是具有鄰接矩陣A的圖G的所有獨立著色方案集。

圖6 12頂點圖的鄰接矩陣

5 結束語

圖著色問題一直是近年來研究的熱點問題，本文基于FPGA利用回溯法實現了圖著色問題的求解。首先利用最大完全子圖固定了部分頂點的著色，使得圖著色問題的解是獨立著色方案集。隨后在Altera公司的EP4CE6E22C8芯片上設計并實現了基于回溯法的圖著色問題求解。最后的實驗結果表明，基于FPGA的圖著色算法在每次迭代時，判斷能否著色所消耗的時間小于在通用處理器中利用軟件實現迭代所需的時間，并且FPGA內部所消耗的資源與圖的頂點個數成正比。