基于蟻群優(yōu)化算法的虛擬現(xiàn)場可編程門陣列部署策略

許英鑫，孫 磊，趙建成，郭松輝

（信息工程大學(xué)，鄭州450001）

（*通信作者電子郵箱xxyyxx151@163.com）

0 引言

近期，國家互聯(lián)網(wǎng)應(yīng)急中心發(fā)布的《2018 中國互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告》顯示，云平臺(tái)已經(jīng)成為發(fā)生網(wǎng)絡(luò)攻擊的重災(zāi)區(qū)，隨著我國5G、IPv6、物聯(lián)網(wǎng)等試用工作逐步推進(jìn)，越來越多的業(yè)務(wù)場景正在向云端遷移，集中式的安全服務(wù)與密碼運(yùn)算需求凸顯。在廣闊市場需求的推動(dòng)下，國內(nèi)外各大產(chǎn)商紛紛布局云計(jì)算安全防護(hù)技術(shù)。以現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）、特 殊 應(yīng) 用 集 成 電 路（Application Specific Integrated Circuit，ASIC）芯片等硬件作為密碼運(yùn)算的加速協(xié)處理器，為租戶提供高速的密碼運(yùn)算服務(wù)的做法逐漸受到各大云服務(wù)提供商的青睞。例如，Amazon推出的AWS CloudHSM 服務(wù)，通過硬件安全模塊來負(fù)責(zé)租戶私有密鑰和存儲(chǔ)和管理［1］；阿里云聯(lián)合江南天安把經(jīng)過國家密碼管理局認(rèn)證的硬件密碼機(jī)聚合成池為云租戶云數(shù)據(jù)加密服務(wù)［2］。另一方面，由于缺乏高效經(jīng)濟(jì)的加速器虛擬化解決方案，租戶不得不獨(dú)占式使用昂貴的加速器資源，在降低資源利用率的同時(shí)提高了服務(wù)成本。

FPGA 虛擬化技術(shù)允許將支持部分重新配置的單個(gè)FPGA 設(shè)備劃分為多個(gè)虛擬FPGA（virtual FPGA，vFPGA），當(dāng)租戶需求發(fā)生變更時(shí)，只有一個(gè)或多個(gè)部分的FPGA 邏輯需要修改，而不影響其余部分的正常運(yùn)行［3］。在本論文課題組前期的工作中，已經(jīng)在研究現(xiàn)有云安全解決方案的基礎(chǔ)上，設(shè)計(jì)了可重構(gòu)密碼資源池的管理和調(diào)度框架，并提出了基于多任務(wù)多階段預(yù)測的vFPGA 調(diào)度算法［4］。通過虛擬化技術(shù)把支持局部重構(gòu)的FPGA 虛擬成多個(gè)vFPGA，并作為密碼運(yùn)算協(xié)處理器按照租戶所需的密碼運(yùn)算需求（如AES、RSA和MD5等）進(jìn)行分配。然而，在實(shí)驗(yàn)過程中發(fā)現(xiàn)，vFPGA 的初始部署會(huì)對(duì)FPGA 的使用數(shù)量產(chǎn)生較大影響。為了進(jìn)一步提高FPGA 資源利用率、降低服務(wù)成本，需要對(duì)vFPGA 部署策略進(jìn)行進(jìn)一步的研究。

從提高資源利用率的角度出發(fā)，研究如何獲得一個(gè)最優(yōu)部署策略，把用戶所需的vFPGA 資源部署到最少的FPGA 上可以歸納為vFPGA 部署（Virtual FPGA Placement，VFP）問題。在租戶規(guī)模較小時(shí)，該問題可以作為線性規(guī)劃（Linear Programming，LP）問題來求解，但是隨著租戶數(shù)量的快速增長，啟發(fā)式方法，如遺傳算法（Genetic Algorithm，GA）或蟻群優(yōu)化（Ant Colony Optimization，ACO）算法等，在處理該類NP困難問題時(shí)能夠提供更高的求解效率。其中，ACO 算法由于在蟻群中采用全局共享信息素，使得經(jīng)驗(yàn)信息可以在蟻群中迅速傳播，從而有助于多螞蟻之間的合作，提高全局勘探能力，從而獲得更好的求解效果。

本文內(nèi)容包括以下幾個(gè)方面:

1）結(jié)合FPGA 的工作特點(diǎn)對(duì)ACO 算法進(jìn)行優(yōu)化，設(shè)計(jì)了一個(gè)新的vFPGA 部署策略，增加了螞蟻的資源狀態(tài)感知功能；

2）在實(shí)施vFPGA 資源調(diào)度時(shí)，預(yù)留了一定的空閑空間從而有效降低了因租戶需求變更而導(dǎo)致發(fā)生SLA沖突的概率；

3）對(duì)CloudSim［5］進(jìn)行功能擴(kuò)展，使其支持FPGA 類和vFPGA類的仿真，并合成工作流對(duì)文章提出的算法進(jìn)行評(píng)估。

1 相關(guān)工作

為了解決云計(jì)算中的資源分配部署的問題，國內(nèi)外學(xué)者們做了大量的努力，并取得了豐碩的成果。

線性規(guī)劃被首先用于求解類似的問題。Speitkamp等［6］針對(duì)服務(wù)器部署優(yōu)化問題，基于數(shù)學(xué)規(guī)劃思想提出了一個(gè)基于多個(gè)決策模型的優(yōu)化方案，通過服務(wù)器的整合提高數(shù)據(jù)中心的資源利用率。Teyeb 等［7］以降低能耗為目標(biāo)，在多租戶云數(shù)據(jù)中心通過兩個(gè)整數(shù)線性規(guī)劃方程優(yōu)化虛擬機(jī)的部署。Dai等［8］雖然同樣把虛擬機(jī)資源分配問題當(dāng)成LP 問題，但是使用了貪婪算法進(jìn)行求解，解決了使用靜態(tài)策略時(shí)由于需求變化感知滯后而導(dǎo)致的資源分配不平衡問題，降低了數(shù)據(jù)中心的能耗。然而當(dāng)租戶規(guī)模較大時(shí)，使用整數(shù)規(guī)劃求解數(shù)據(jù)中心資源分配部署問題，往往需要較大的計(jì)算開銷，影響資源調(diào)度的及時(shí)性。

現(xiàn)階段，通過啟發(fā)式方法，如遺傳算法等，對(duì)VFP 問題進(jìn)行求解能夠提供更高的計(jì)算效率。Veredas 等［9］使用遺傳算法對(duì)FPGA 部署進(jìn)行優(yōu)化，從而保證了關(guān)鍵路徑的最小化，有效降低了系統(tǒng)的總體開銷。Riahi等［10］基于多目標(biāo)遺傳算法，設(shè)計(jì)了一個(gè)高效的虛擬機(jī)部署框架以最大限度地減少資源浪費(fèi)，并在云平臺(tái)上進(jìn)行實(shí)現(xiàn)，驗(yàn)證了所提框架的可行性。在系統(tǒng)運(yùn)行的過程中，如果僅僅考慮提高資源利用率，則可能導(dǎo)致資源的過度分配。當(dāng)租戶的資源需求增加時(shí)，由于系統(tǒng)資源分配存在著一定的滯后性，可能導(dǎo)致服務(wù)阻塞，甚至宕機(jī)，嚴(yán)重影響租戶滿意度。為了在有效地降低系統(tǒng)能耗開銷和持續(xù)的服務(wù)質(zhì)量之間進(jìn)行折中，Haghighi 等［11］結(jié)合聚類的思想，對(duì)遺傳算法進(jìn)行了改進(jìn)，提出了一種改進(jìn)的k均值聚類遺傳算法。

ACO 算法是另一種啟發(fā)式方法，最初是為了解決旅行商問題而提出。相比遺傳算法，ACO 算法更加便于與其他智能算法進(jìn)行結(jié)合，能夠針對(duì)具體的應(yīng)用場景進(jìn)行相應(yīng)優(yōu)化，同時(shí)由于覓食原則、避障原則等原則的加入，提供了更大的選擇空間，讓其在解決VFP 及類似問題時(shí)，往往能取得更好的效果。楊星等［12］設(shè)計(jì)了一種改進(jìn)的蟻群算法并用于指導(dǎo)虛擬機(jī)部署，通過增加性能感知策略，并改變單只螞蟻的信息素更新規(guī)則，能夠有效避免虛擬機(jī)之間的硬件資源競爭。為了從全局優(yōu)化的角度來最小化物理服務(wù)器的使用數(shù)量，Liu等［13］把ACO算法的一個(gè)變種——蟻群系統(tǒng)（Ant Colony System，ACS）與信息素沉積策略相結(jié)合，用于解決虛擬機(jī)部署問題。同樣的ACO 算法在FPGA 資源池能耗優(yōu)化及硬件任務(wù)調(diào)度方面的應(yīng)用也取得了一定的成效［14-15］。

在可重構(gòu)密碼資源池中，VFP 問題并不是標(biāo)準(zhǔn)的旅行商問題。在對(duì)蟻群算法進(jìn)行優(yōu)化時(shí)，需要考慮以下兩個(gè)問題:首先，用戶動(dòng)態(tài)變化的vFPGA 資源需求，對(duì)系統(tǒng)的FPGA 資源彈性提出了更高的要求，需要在提高FPGA 資源利用效率的同時(shí)，保證系統(tǒng)的服務(wù)質(zhì)量；其次，為了減少系統(tǒng)重構(gòu)開銷和通信帶寬占用，需要避免vFPGA的頻繁遷移。

2 基于蟻群算法的vFPGA部署策略

本章首先定義了VFP 問題并建立了數(shù)學(xué)模型，然后給出了基于蟻群算法的vFPGA部署策略。

2.1 問題描述

密碼資源池根據(jù)基礎(chǔ)設(shè)施即服務(wù)交付模型以虛擬機(jī)（Virtual Machine，VM）實(shí)例的形式向租戶提供計(jì)算資源，每個(gè)VM 分配有一塊vFPGA 作為進(jìn)行密碼運(yùn)算的實(shí)體。系統(tǒng)可以劃分為三個(gè)層次，分別是FPGA 資源池層、管理平臺(tái)層和租戶應(yīng)用層。具體框架如圖1所示。

圖1 密碼資源池框架Fig. 1 Framwork of cryptographic resource pool

FPGA資源池為服務(wù)器集群，每臺(tái)服務(wù)器以支持局部可重構(gòu)的FPGA 作為計(jì)算實(shí)體。借助FPGA 虛擬化技術(shù)，每塊FPGA 可以劃分為多塊vFPGA，各vFPGA 之間相互獨(dú)立，對(duì)其中一塊進(jìn)行重新配置時(shí)，不影響其他vFPGA 的正常工作。服務(wù)器虛擬化結(jié)構(gòu)如圖2所示。

圖2 服務(wù)器虛擬化結(jié)構(gòu)Fig. 2 Virtualization structure of servers

管理平臺(tái)由資源管理、需求管理、網(wǎng)絡(luò)管理三個(gè)模塊組成，以3 個(gè)模塊的監(jiān)控信息作為調(diào)度決策的依據(jù)，調(diào)度決策過程如圖3所示。

圖3 調(diào)度決策過程Fig. 3 Scheduling and decision-making process

首先，管理平臺(tái)獲取租戶工作流、資源狀態(tài)、網(wǎng)絡(luò)狀態(tài)等系統(tǒng)狀態(tài)信息，通過預(yù)測模型得到工作流需求預(yù)測值及資源列表；其次，全局調(diào)度器根據(jù)需求信息和資源信息通過優(yōu)化蟻群算法求解VFP 問題，得到部署矩陣為各個(gè)租戶VM 分配vFPGA資源。實(shí)現(xiàn)過程如算法1所示。

最后，工作在VM 內(nèi)部的本地調(diào)度器是在得到租戶需求預(yù)測值及vFPGA 資源后，根據(jù)租戶需求將部署在該VM 上vFPGA 資源根據(jù)租戶需求進(jìn)行動(dòng)態(tài)重構(gòu)。實(shí)現(xiàn)過程如算法2所示。

租戶應(yīng)用層分為工作流及密碼服務(wù)實(shí)體兩個(gè)部分。其中，工作流由租戶產(chǎn)生，隨著租戶密碼運(yùn)算需求的變化而動(dòng)態(tài)變化。密碼服務(wù)實(shí)體即租戶VM 是向租戶提供密碼服務(wù)的載體，每個(gè)VM分配有vFPGA資源作為密碼運(yùn)算協(xié)處理器。

為了更好地描述VFP 問題，對(duì)可重構(gòu)密碼資源池進(jìn)行抽象，并建立了數(shù)學(xué)模型，模型參數(shù)表示及其對(duì)應(yīng)的含義如表1所示。

VFP問題的目標(biāo)方程如式（1）所示:

約束方程如下:

其中:由于跨FPGA 通信需要大量的帶寬支持，容易導(dǎo)致系統(tǒng)的堵塞，造成通信延遲，因此，使用式（4）來確保把vFPGA 分配給一個(gè)且只有一個(gè)FPGA。在式（6）中，free表示在單片F(xiàn)PGA中預(yù)留的動(dòng)態(tài)可重構(gòu)面積占總邏輯面積的百分比，取值為［0，1］。預(yù)留面積用于避免FPGA 資源的過度分配而導(dǎo)致的頻繁遷移。

表1 系統(tǒng)模型參數(shù)及其對(duì)應(yīng)的含義Tab.1 System model parameters and their meanings

2.2 問題求解

在使用蟻群算法對(duì)VFP 問題進(jìn)行求解的過程中，本文結(jié)合密碼資源池的實(shí)際應(yīng)用需求，對(duì)算法流程和參數(shù)設(shè)置進(jìn)行了一定的優(yōu)化。

首先，由于蟻群算法是從全局的角度進(jìn)行vFPGA 部署優(yōu)化，每次調(diào)用算法獲取部署矩陣時(shí)，租戶vFPGA 部署位置往往需要進(jìn)行變更，盡管該租戶所需vFPGA 資源并未發(fā)生變化。頻繁的vFPGA 遷移需要大量的通信開銷，增加重配置時(shí)延，影響系統(tǒng)服務(wù)質(zhì)量。為了減少不必要的vFPGA 遷移操作，在系統(tǒng)工作過程中，根據(jù)工作流預(yù)測的結(jié)果，按照資源占有和需求情況，對(duì)其中的資源不足和過剩實(shí)例進(jìn)行標(biāo)記，每次運(yùn)行算法只需對(duì)標(biāo)記實(shí)例進(jìn)行部署優(yōu)化。

其次，針對(duì)負(fù)載均衡問題，在一般蟻群算法的基礎(chǔ)上，賦予了螞蟻資源數(shù)量感知能力，在算法執(zhí)行的過程中，增加對(duì)過載節(jié)點(diǎn)低負(fù)載節(jié)點(diǎn)的感知。通過適度提高信息素濃度，鼓勵(lì)螞蟻更多地把vFPGA 部署到低負(fù)載節(jié)點(diǎn)中，通過大幅降低信息素濃度減小過載節(jié)點(diǎn)被螞蟻發(fā)現(xiàn)的概率。

最后，針對(duì)預(yù)測模型存在一定預(yù)測誤差而導(dǎo)致為租戶分配的vFPGA 資源不足的問題，在模型預(yù)測的基礎(chǔ)上增加了一定的預(yù)留空間，能夠在有效保證系統(tǒng)的QoS 的同時(shí)，減少vFPGA的遷移次數(shù)。

在標(biāo)記實(shí)例階段，需要根據(jù)預(yù)測結(jié)果確定FPGA 中所有租戶在下一階段的vFPGA資源需求之和，如式（7）所示:

如式（8）所示，當(dāng)FPGA 上動(dòng)態(tài)可重構(gòu)部分的邏輯單元數(shù)無法滿足部署在其上的所有vFPGA 的需求時(shí)，定義其為資源不足實(shí)例。

如式（9）所示，當(dāng)FPGA 上動(dòng)態(tài)可重構(gòu)部分的邏輯單元數(shù)在滿足部署在其上的所有vFPGA 的需求后仍有剩余時(shí)，標(biāo)記其為資源過剩實(shí)例。

運(yùn)用優(yōu)化蟻群算法求解VFP 問題的總體流程如圖4所示。

圖4 優(yōu)化蟻群算法總體流程Fig. 4 Flow chart of optimized ACO algorithm

步驟2 初始化部署矩陣，產(chǎn)生方案K0，把M塊vFPGA 部署到N塊FPGA 中，平均每塊FPGA 上部署塊vFPGA中，此時(shí)minNum(K0)=N，之后生成并初始化一只螞蟻；

步驟3 匹配vFPGA與FPGA，在t時(shí)刻螞蟻z把vfj部署到fi的概率可以用式（10）計(jì)算，其中，Tvf表示待部署vFPGA 表，Tf表示未過載的FPGA表；

步驟4 更新Tvf和Tf，假設(shè)在步驟3 中vfj被部署于fi，把vfj從Tvf移出，當(dāng)fi過載時(shí)把它從Tf移出，返回步驟3，否則跳到步驟5；

步驟5 每只螞蟻得到一個(gè)解，得到當(dāng)前最優(yōu)解；

步驟6 根據(jù)式（11）更新信息素矩陣，其中ρ為揮發(fā)因子；

步驟7 重復(fù)步驟2～6 直到最大代數(shù)，得到全局最優(yōu)解，最后在擴(kuò)展后的CloudSim中運(yùn)行仿真，并記錄結(jié)果。

2.3 時(shí)間復(fù)雜度分析

假設(shè)密碼資源池中使用的FPGA 數(shù)量為M，平均每塊FPGA 上部署Navg塊vFPGA。密碼資源池中租戶規(guī)模即vFPGA 總量為N，租戶需要的密碼運(yùn)算類型數(shù)為k。在本節(jié)，本文分別從實(shí)例標(biāo)記、全部調(diào)度和局部調(diào)度三個(gè)方面對(duì)調(diào)度算法的時(shí)間復(fù)雜度進(jìn)行分析。

首先，在實(shí)例標(biāo)記階段，為了得到FPGA 資源使用情況，需要遍歷密碼資源池中所有的FPGA 實(shí)例，計(jì)算該FPGA 中所有vFPGA 下一階段的各種算法的資源需求，并與現(xiàn)有資源量進(jìn)行對(duì)比得到實(shí)例類型，其時(shí)間復(fù)雜度為O（kNNavg）。

其次，本地調(diào)度器的功能是在租戶虛擬機(jī)中按需對(duì)本地vFPGA 進(jìn)行局部重配置。進(jìn)行局部重配置之前需要計(jì)算vFPGA 內(nèi)部各個(gè)算法IP 核的數(shù)量變化，其時(shí)間復(fù)雜度為O（kNavg）。因?yàn)槊艽a資源池中vFPGA 數(shù)量為N，所以整個(gè)局部調(diào)度階段的時(shí)間復(fù)雜度為O（kNNavg）。

最后，全局調(diào)度階段的時(shí)間復(fù)雜度可以分為利用優(yōu)化蟻群算法求得部署矩陣X和為VM 分配相應(yīng)的vFPGA 資源兩個(gè)相互獨(dú)立的部分。利用優(yōu)化蟻群算法進(jìn)行求解時(shí)，需要進(jìn)行部署調(diào)優(yōu)的標(biāo)記實(shí)例數(shù)量在0～M，螞蟻數(shù)量與vFPGA 數(shù)量一致為0～MNavg，迭代次數(shù)為30，算法時(shí)間復(fù)雜度為O（）。得到部署矩陣后，需要遍歷X對(duì)標(biāo)記FPGA 進(jìn)行重新劃分，并把vFPGA 分配給對(duì)應(yīng)的VM，其時(shí)間復(fù)雜度為O（）。因此，全局調(diào)度階段的時(shí)間復(fù)雜度為。

綜上所述，由于實(shí)例標(biāo)記、本地調(diào)度和全局調(diào)度是3 個(gè)相互獨(dú)立的階段，密碼算法IP 核種類為k，通常為一個(gè)較小的常數(shù)，又有N≈，所以整個(gè)調(diào)度算法的時(shí)間復(fù)雜度為O（MN2）。

3 實(shí)驗(yàn)與評(píng)價(jià)

在云平臺(tái)仿真工具CloudSim［5］的基礎(chǔ)上進(jìn)行擴(kuò)展，增加了FPGA 類、vFPGA 類分別部署在Host 類、Vm 類上。由同一FPGA 虛擬出的所有vFPGA 在空間上共享該FPGA 的邏輯單元，vFPGA上有不同類型的算法功能模塊，用于處理對(duì)應(yīng)類型的算法任務(wù)。實(shí)驗(yàn)過程中，借鑒文獻(xiàn)［16］進(jìn)行工作流合成及取樣。使用滿足正態(tài)分布的隨機(jī)工作流作為租戶任務(wù)請(qǐng)求輸入，該工作流的時(shí)間跨度為48 h，時(shí)間序列采樣間隔為10 min，前24 h 作為訓(xùn)練集，后24 h 作為測試集。時(shí)間序列預(yù)測算法和資源調(diào)度算法嵌入在數(shù)據(jù)中心代理中，從第25 h 開始，系統(tǒng)每10 min執(zhí)行一次資源調(diào)度算法，使用自回歸整合滑動(dòng)平均（AutoRegressive Integrated Moving Average，ARIMA）模型對(duì)租戶工作流進(jìn)行預(yù)測，預(yù)測步數(shù)為3。最后，分別統(tǒng)計(jì)不同實(shí)驗(yàn)設(shè)置下的vFPGA 遷移次數(shù)、SLA 沖突率和平均FPGA實(shí)例啟用數(shù)量對(duì)算法的性能進(jìn)行評(píng)價(jià)。

3.1 實(shí)驗(yàn)設(shè)置

借鑒文獻(xiàn)［16-17］進(jìn)行實(shí)驗(yàn)設(shè)置，在CloudSim 初始化時(shí)，創(chuàng)建一個(gè)部署有600臺(tái)Host的Datacenter，每臺(tái)Host配置相同，均為2 660 MIPS，16 GB RAM 和一塊FPGA。其中，MIPS 表示單位時(shí)間內(nèi)能夠執(zhí)行的百萬指令數(shù)量，是衡量CPU 性能的指標(biāo)。FPGA 類的參數(shù)按照Xilinx VC709 FPGA 開發(fā)板中XC7VX690T FPGA的參數(shù)進(jìn)行設(shè)置，板上內(nèi)存8 GB，總邏輯單元數(shù)為693，120，其中7%為靜態(tài)邏輯區(qū)域，其余為局部動(dòng)態(tài)可重構(gòu)區(qū)域［15］。通過QuartusⅡ13.0工具進(jìn)行綜合布線，并使用ModelSim 工具進(jìn)行仿真得到實(shí)現(xiàn)AES、RC4、RSA 和MD5 算法IP核需要的邏輯單元數(shù)量和算法處理速度，具體數(shù)據(jù)如表2所示，每個(gè)算法IP核的重構(gòu)時(shí)延為16 ms?？芍貥?gòu)密碼資源池中每名租戶需要一塊vFPGA 提供密碼運(yùn)算服務(wù)，在初始狀態(tài)下每塊FPGA 虛擬出4 塊vFPGA，以0 時(shí)刻各租戶的需求作為vFPGA分配和配置的依據(jù)。初始狀態(tài)下的資源分配策略并沒有考慮各個(gè)服務(wù)器中FPGA 資源的利用情況，在1時(shí)刻系統(tǒng)第一次運(yùn)行vFPGA調(diào)度算法時(shí)會(huì)對(duì)整個(gè)密碼資源池的資源分配進(jìn)行大幅度的調(diào)整，此時(shí)的數(shù)據(jù)無法正確地反映算法的性能優(yōu)劣，所以選擇從2時(shí)刻開始對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行記錄。SLA沖突率的定義如式（12）所示，其中，CTS表示SLA沖突次數(shù)，當(dāng)用當(dāng)租戶擁有的vFPGA資源無法滿足其運(yùn)算需求時(shí)，CTS值加1。

表2 不同算法IP核參數(shù)Tab. 2 IP core parameters of different algorithm

3.2 實(shí)驗(yàn)結(jié)果分析

首先，測試vFPGA 部署算法對(duì)系統(tǒng)性能的影響。現(xiàn)有的vFPGA 部署算法［15］一般采用的是靜態(tài)部署的策略，即在每塊FPGA 上部署固定數(shù)量的vFPGA 并分配給租戶使用。此時(shí)，系統(tǒng)仍然能夠根據(jù)預(yù)測模型的預(yù)測結(jié)果進(jìn)行FPGA 動(dòng)態(tài)重構(gòu)，但是無法完成vFPGA實(shí)例的遷移。

分別采用默認(rèn)部署（Without Scheduler，WS）算法、蟻群算法（ACO）及優(yōu)化蟻群（Improved Ant Colony Optimization，IACO）算法三種調(diào)度方案進(jìn)行對(duì)比實(shí)驗(yàn)。其中，在WS 算法中，vFPGAs部署在每個(gè)FPGA的數(shù)量默認(rèn)為4，8和12；借鑒文獻(xiàn)［13］進(jìn)行ACO 算法和IACO 算法的參數(shù)選擇，其中螞蟻數(shù)量與待部署vFPGA 數(shù)量一致，迭代的代數(shù)為30，α= 1，β=1，ρ= 0.1。在IACO 算法中預(yù)留空間free取值為3%；租戶的數(shù)量分別為500、1 000、1 500 和2 000。每個(gè)租戶分配有一塊vFPGA提供密碼運(yùn)算服務(wù)。實(shí)驗(yàn)結(jié)果如圖5所示。

從FPGA 使用數(shù)量的角度出發(fā)，當(dāng)采用WS 算法時(shí)，F(xiàn)PGA啟用數(shù)量與vFPGA 初始放置數(shù)量成反比，當(dāng)默認(rèn)部署數(shù)量為12 時(shí)，F(xiàn)PGA 使用數(shù)量在所有方案中最少，但是此時(shí)SLA 沖突達(dá)到25%以上，遠(yuǎn)遠(yuǎn)超過其他方案，這是由于當(dāng)有太多vFPGA 部署在一個(gè)FPGA 時(shí)，不同租戶之間競爭有限的邏輯區(qū)域而導(dǎo)致的。如果一塊FPGAh 上默認(rèn)部署的vFPGA 資源較少，則會(huì)增加FPGA 的使用量。因此，WS 算法適用于租戶vFPAG資源需求固定或者變化較小的場景中。

采用ACO 算法可以使用較少數(shù)量FPGA 來滿足租戶的資源需求，但是在SLA沖突率方面，ACO算法的SLA沖突率大小取決于預(yù)測模型的預(yù)測精度，同時(shí)在用戶規(guī)模較大的情況下，租戶的需求動(dòng)態(tài)變化往往會(huì)導(dǎo)致vFPGA 的最優(yōu)部署位置的變化，需要頻繁地遷移。因此，ACO 適用于資源緊張、租戶對(duì)服務(wù)質(zhì)量要求不高的場景中。

IACO 算法的使用能夠在vFPGA 遷移次數(shù)、SLA 沖突率和FPGA 實(shí)例啟用數(shù)量間進(jìn)行折中。相較于傳統(tǒng)的ACO 算法，IACO 算法雖然增加了FPGA 的使用數(shù)量，但是能夠有效減少vFPGA遷移次數(shù)，且賦予了密碼資源池更高的資源彈性，可以有效避免因工作流預(yù)測精度不足而導(dǎo)致的SLA沖突

其次，測試預(yù)留空間free取值對(duì)系統(tǒng)性能的影響。在租戶的數(shù)量為500，1 000、1 500和2 000時(shí)，使用優(yōu)化蟻群算法指導(dǎo)vFPGA 部署，測試系統(tǒng)的性能。測試過程中螞蟻數(shù)量與待部署vFPGA 數(shù)量一致，迭代的代數(shù)為30，α= 1，β= 1，ρ= 0.1。free取值分別為0，3%，6%，9%，12%和15%。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同規(guī)模下free取值對(duì)系統(tǒng)性能的影響Fig. 6 Influence of free value on system performance under different scale

由圖6 仿真結(jié)果可知:首先，在不同租戶規(guī)模下，密碼資源池FPGA 使用量隨預(yù)留空間free取值的增大而增大。這是由于free取值增大之后，降低了系統(tǒng)中FPGA 資源的利用率，需要通過激活更多的FPGA 來滿足租戶的密碼運(yùn)算需求。其次，系統(tǒng)發(fā)生SLA 沖突的概率隨著free的增大而減小，最后趨于平穩(wěn)。因?yàn)轭A(yù)留空間的存在，當(dāng)租戶資源需求的預(yù)測值小于實(shí)際需求值時(shí)，可以利用預(yù)留空間進(jìn)行局部重構(gòu)，從而降低了系統(tǒng)發(fā)生SLA 沖突的概率。同樣的，vFPGA 遷移次數(shù)也隨著free取值的增大而減小，最后逐漸趨于0。增大free可以減少標(biāo)記實(shí)例的數(shù)量、縮小問題規(guī)模，從而減少vFPGA 遷移次數(shù)，由于全局調(diào)度器首次把FPGA 邏輯資源劃分為多個(gè)vFPGA時(shí)留有一定的空閑空間，所以，在系統(tǒng)運(yùn)行的過程中租戶資源需求的變化不容易導(dǎo)致過載情況的發(fā)生，此時(shí)，只需要在當(dāng)前FPGA 中進(jìn)行動(dòng)態(tài)重配置，而不需要進(jìn)行vFPGA 遷移操作。因此，預(yù)留空間的設(shè)計(jì)能夠在FPGA 資源利用率和系統(tǒng)服務(wù)質(zhì)量間進(jìn)行折中，在本文仿真場景下，綜合考慮FPGA使用數(shù)量、系統(tǒng)服務(wù)質(zhì)量、vFPGA 遷移開銷，當(dāng)free取值為9%時(shí)，系統(tǒng)的總體性能最優(yōu)。

4 結(jié)語

本文在課題組前期工作的基礎(chǔ)上，提出了一個(gè)基于優(yōu)化蟻群算法的vFPGA 部署策略，把vFPGA 資源把vFPGA 當(dāng)成像CPU、內(nèi)存一樣的硬件資源根據(jù)租戶需求進(jìn)行動(dòng)態(tài)調(diào)度，在保證租戶滿意度的前提下，降低了服務(wù)成本，進(jìn)一步提高了密碼資源池的資源利用效率和租戶的應(yīng)用體驗(yàn)?？梢詮囊韵聝蓚€(gè)方向展開下一步的工作:一是以降低綜合布線開銷和提高資源利用效率為目標(biāo)，從硬件層面研究FPGA 可重構(gòu)區(qū)域劃分?jǐn)?shù)量的優(yōu)化問題；二是把基于FPGA 的密碼資源池中其他資源，例如CPU、內(nèi)存、磁盤空間等納入考慮范圍，研究vFPGA資源的部署和調(diào)度問題。