基于FPGA的圖著色問題求解

張益豪 張子超 劉小青② 冷 煌② 王之元 許 進(jìn)②

①(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)

②(北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100871)

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

1 引言

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

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

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

2 圖著色問題的回溯算法

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

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

圖1 四頂點(diǎn)平面圖

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

圖2 四頂點(diǎn)平面圖的著色方案

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

圖3 回溯法算法流程圖

3 基于FPGA的圖著色實(shí)現(xiàn)方案

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

圖4 基于FPGA的圖著色實(shí)現(xiàn)方案

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

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

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

4 硬件實(shí)現(xiàn)

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

表1 FPGA資源消耗

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

圖5 頂點(diǎn)著色方案驗(yàn)證的功能仿真

隨著頂點(diǎn)個(gè)數(shù)的增加，在每次迭代中判斷當(dāng)前著色方案是否有效所需的運(yùn)算量增加。具體來說，利用3個(gè)周期的或運(yùn)算來判斷當(dāng)前頂點(diǎn)的著色方案是否與鄰接節(jié)點(diǎn)著色方案相同。本文基于空間換時(shí)間的思想，通過增加單個(gè)周期內(nèi)或運(yùn)算的個(gè)數(shù)，保證每次迭代時(shí)FPGA內(nèi)部運(yùn)算所需時(shí)鐘周期個(gè)數(shù)與頂點(diǎn)的個(gè)數(shù)無關(guān)。因此隨著頂點(diǎn)個(gè)數(shù)的增加，每次color_next的改變?nèi)匀粌H需10個(gè)周期，且每次迭代時(shí)FPGA執(zhí)行運(yùn)算所消耗的時(shí)間與頂點(diǎn)個(gè)數(shù)無關(guān)。而隨著頂點(diǎn)個(gè)數(shù)的增加，每次迭代時(shí)軟件實(shí)現(xiàn)方案會消耗更多的時(shí)間。例如當(dāng)圖的頂點(diǎn)個(gè)數(shù)為512時(shí)，利用Matlab實(shí)現(xiàn)每次迭代所消耗的時(shí)間為15.611 μs。

為了驗(yàn)證所實(shí)現(xiàn)硬件的正確性，本文基于通用異步收發(fā)傳輸器協(xié)議實(shí)現(xiàn)了FPGA與通用處理器之間的通信。對具有如圖6所示鄰接矩陣A的12頂點(diǎn)圖G進(jìn)行著色。根據(jù)該圖的類型，通用處理器需將146 bit信息傳輸?shù)紽PGA中，其中前144 bit為鄰接矩陣A的1維表示，最后2 bit信息是表示圖類型的initial_state信號?；?6進(jìn)制將該146 bit表示為961186010D2B29AA59029BB2E582DD24622 D01，并將該信息通過串口傳輸?shù)紽PGA內(nèi)部進(jìn)行運(yùn)算。通過將FPGA運(yùn)算的結(jié)果與通用處理器中圖著色的運(yùn)算結(jié)果對比，驗(yàn)證了FPGA內(nèi)部輸出的解是具有鄰接矩陣A的圖G的所有獨(dú)立著色方案集。

圖6 12頂點(diǎn)圖的鄰接矩陣

5 結(jié)束語

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