一種基于改進(jìn)蟻群優(yōu)化算法的軟硬件劃分方法

胡 偉

?

一種基于改進(jìn)蟻群優(yōu)化算法的軟硬件劃分方法

胡 偉

(黃山學(xué)院 信息工程學(xué)院，安徽 黃山 245021)

軟硬件劃分問題是嵌入式系統(tǒng)的軟硬件協(xié)同設(shè)計中重要的問題之一﹒針對該問題，提出一種基于改進(jìn)蟻群優(yōu)化算法的軟硬件劃分方法﹒通過禁忌搜索算法改進(jìn)蟻群算法的局部搜索過程，利用禁忌表記錄近期的搜索過程，通過禁忌表比對阻止算法重復(fù)進(jìn)入，提高了算法的最優(yōu)解搜索效率，加快了算法的執(zhí)行速度﹒實驗數(shù)據(jù)證明改進(jìn)的蟻群優(yōu)化算法能提高45%左右的工作效率，同時驗證了該算法能夠有效地解決軟硬件劃分問題，提高軟硬件協(xié)同設(shè)計的效率﹒

嵌入式系統(tǒng)；軟硬件協(xié)同設(shè)計；軟硬件劃分；蟻群優(yōu)化算法

隨著嵌入式系統(tǒng)的規(guī)模和功能日益增大，通過軟硬件協(xié)同設(shè)計的方法進(jìn)行嵌入式系統(tǒng)設(shè)計已經(jīng)逐漸取代了傳統(tǒng)設(shè)計方法﹒其中，軟硬件劃分是軟硬件協(xié)同設(shè)計中的關(guān)鍵步驟，其主要任務(wù)是如何將系統(tǒng)功能合理地劃分到可重構(gòu)系統(tǒng)中的軟件和硬件上，并在滿足各項設(shè)計約束條件的前提下，為系統(tǒng)提供最佳的軟硬件配置方案﹒

軟硬件劃分是一類NP-complete問題[1]﹒常用的軟硬件劃分算法分3類：規(guī)劃類算法、構(gòu)造式算法和啟發(fā)式算法[2-4]﹒規(guī)劃類軟硬件劃分算法包括線性規(guī)劃算法和動態(tài)規(guī)劃算法等；構(gòu)造式算法有GCLP(Global Criticality Local Phase)算法和容錯性實時分布式嵌入式系統(tǒng)的軟硬件劃分算法等﹒但以上2類算法在求解復(fù)雜問題時，都會出現(xiàn)算法執(zhí)行時間長及全局搜索能力差的缺點﹒因此不少學(xué)者研究了啟發(fā)式軟硬件劃分算法，其中比較典型的有：爬山算法[5]、模擬退火算法[6]、遺傳算法[1,7,8]、禁忌搜索算法[9]等，此類算法的搜索過程在其定義的啟發(fā)信息指導(dǎo)下逐步向最優(yōu)解收斂﹒爬山算法的策略是“以退為進(jìn)”，但其易陷局部最優(yōu)解；遺傳算法是模擬了生物進(jìn)化和遺傳學(xué)機(jī)理的計算模型，模擬生物進(jìn)化過程來搜索最優(yōu)解的方法，但此類算法最優(yōu)解的收斂速度在執(zhí)行到一定階段后會變得緩慢；模擬退火算法源于固體加熱后的退火原理，模擬固體內(nèi)部粒子的冷卻與結(jié)晶過程，搜索過程受退火溫度控制，但對問題規(guī)模較大的情況，系統(tǒng)得到最優(yōu)解的時間較長；禁忌搜索算法是一種亞啟發(fā)式隨機(jī)搜索算法，模擬了人類的智力過程，“爬山”能力較強(qiáng)，但其頻繁的數(shù)據(jù)存取操作使得搜索速度減低﹒

1 問題描述

1.1 軟硬件劃分功能

軟硬件劃分算法要求在滿足預(yù)定的系統(tǒng)約束的前提下實現(xiàn)系統(tǒng)性能的最優(yōu)化，通常將算法優(yōu)化的起始點設(shè)置為系統(tǒng)功能的全軟件實現(xiàn)﹒

在軟硬件劃分過程中，由C++等高級語言描述嵌入式系統(tǒng)的功能﹒對于一個特定的嵌入式系統(tǒng)，首先將它劃分成一定粒度大小的若干任務(wù)，然后用有向無環(huán)圖(DAG)形式的控制數(shù)據(jù)流圖來描述，如圖1所示﹒在圖1中，(1，2，3…)代表嵌入式系統(tǒng)中的節(jié)點，每一個節(jié)點代表一個任務(wù)，節(jié)點之間的邊代表了節(jié)點間的通信過程，即節(jié)點間的數(shù)據(jù)通路和調(diào)用關(guān)系﹒

軟硬件劃分算法決定硬件和軟件可分別實現(xiàn)哪些節(jié)點﹒軟硬件劃分后，所有任務(wù)都能被映射到一個劃分后的分組中，且對劃分結(jié)果進(jìn)行評估，當(dāng)劃分結(jié)果在速度、功耗、面積與性能等方面均達(dá)到一個很好的平衡時結(jié)束算法，否則繼續(xù)執(zhí)行算法來產(chǎn)生新的劃分，并對其進(jìn)行新的評價﹒

圖1 節(jié)點系統(tǒng)任務(wù)的有向無環(huán)圖

1.2 軟硬件劃分模型

本文的軟硬件劃分模型采用主從處理器(Master Slave Processor)的體系結(jié)構(gòu)模型，如圖2所示，其中主處理器一般是通用處理器，而從處理器則采用專用的ASIC硬件或可編程邏輯器件FPGA，主從處理器之間共享存儲并通過內(nèi)部總線形式實現(xiàn)數(shù)據(jù)的通訊﹒

圖2 體系結(jié)構(gòu)模型

假設(shè)嵌入式系統(tǒng)中有個任務(wù)節(jié)點，那么第個節(jié)點(∈{1，…，})采用第種方式實現(xiàn)(其中=0表示采用軟件實現(xiàn)，=1表示采用硬件實現(xiàn))，系統(tǒng)主要包括4個屬性：硬件面積(，)；執(zhí)行時間(，)；成本(，)；功耗(，)﹒

文中的劃分問題可以描述如下：

系統(tǒng)總的功耗可以描述為：

其中為系統(tǒng)的最大面積；為系統(tǒng)的最大執(zhí)行時間；為系統(tǒng)的限制成本；為系統(tǒng)總功耗﹒該問題是一個多限制條件下的功耗最優(yōu)問題，即要求滿足式(1)的前提條件下式(2)中最低﹒

1.3 改進(jìn)蟻群優(yōu)化算法在軟硬件劃分上的研究

1.3.1 蟻群優(yōu)化算法

生物學(xué)家研究發(fā)現(xiàn)，幾乎沒有視覺的螞蟻之所以能在食物和巢穴直接找到最短路徑，是因為其能夠在覓食中所經(jīng)過的路徑上留下一種被稱為信息素(Pheromone)的物質(zhì)，而后來的螞蟻就能夠感知到這種信息素的存在和強(qiáng)度，信息素的強(qiáng)度與螞蟻選擇該條路徑的概率成正比﹒因此，蟻群的集體覓食行為反映成一種正反饋現(xiàn)象：即在螞蟻行走的多條路徑中，相對最短的路徑上會留下更多信息素，信息素強(qiáng)度越大，后來的螞蟻選擇該條路徑的概率也越大，該路徑上走的螞蟻越多，從而更增強(qiáng)了信息素濃度﹒蟻群就是通過這種方式來進(jìn)行最短路徑的選擇，并實現(xiàn)快速覓食的目的﹒意大利學(xué)者M(jìn).Dorigo等提出的蟻群優(yōu)化算法(ACOA，Ant Colony Optimization Algorithm)就是一種模擬螞蟻覓食行為的生物優(yōu)化算法[10]﹒

蟻群優(yōu)化算法的主要優(yōu)點[11]是：(1)正反饋機(jī)制，可以通過不斷更新信息素的方式高效地收斂到最優(yōu)解；(2)通用隨機(jī)優(yōu)化的特性；(3)分布式優(yōu)化方法的特征更有利于實現(xiàn)并行計算；(4)具有全局優(yōu)化方法的特征﹒而其主要缺點為：由于初期信息素的缺乏，會導(dǎo)致在搜索的初期階段進(jìn)行積累信息素操作的時間較長，影響求解速度﹒

1.3.2 算法設(shè)置

(1)參數(shù)選擇﹒算法參數(shù)選擇，一方面參考通用測試集中所用參數(shù)，同時又在本算法實現(xiàn)過程中按算法執(zhí)行的實際效果作調(diào)整，數(shù)值見表1﹒

表1 參數(shù)設(shè)置

1.3.3 解的構(gòu)造

禁忌表tabu(=1，2，…，)被定義為用來記錄給第只螞蟻分配過的實現(xiàn)﹒禁忌表有動態(tài)調(diào)整的功能，可以隨著進(jìn)化過程的進(jìn)行而動態(tài)變化，這使得人工蟻群具有記憶的功能﹒每次循環(huán)完成，所有的螞蟻完成1次分配，禁忌表將被填滿﹒τ()表示時刻螞蟻將節(jié)點分配到上時，留在(，)對上的信息素強(qiáng)度﹒假設(shè)在初始狀態(tài)時，留在各(，)對上的信息素相等，在進(jìn)行下1次循環(huán)時，每只螞蟻將節(jié)點分配到上的概率按照公式(3)計算，同時更新禁忌表﹒這個過程將循環(huán)操作次，直到蟻群中所有的螞蟻都完成循環(huán)分配操作，最終得到相應(yīng)的解﹒

1.3.4 局部搜索

普通蟻群算法容易陷入局部最優(yōu)解，因此需要采用局部搜索來對局部最優(yōu)解進(jìn)行優(yōu)化，得到更加靠近最優(yōu)解的當(dāng)前最優(yōu)解﹒目前常用局部搜索算法包括以下3種：兩交換算法(two-opt)、三交換算法(three-opt)和禁忌搜索算法(TS算法)﹒其中兩交換算法的操作速度比較快，而TS算法效率更高，“爬山”能力更強(qiáng)，能獲得更優(yōu)的解﹒

TS算法就是對于找到的一部分局部最優(yōu)解，去有意識地避開它，但并非完全隔絕，跳出局部最優(yōu)解，從而獲得更多的搜索區(qū)域﹒本文算法采用TS算法改進(jìn)蟻群算法的局部搜索過程﹒

1.3.5 信息素更新

2 算法實現(xiàn)

本文的算法由4個主要步驟組成﹒

3 實驗

3.1 實驗環(huán)境

目前國際上還沒有在嵌入式系統(tǒng)的軟硬件劃分領(lǐng)域發(fā)布標(biāo)準(zhǔn)測試集，故可用工具隨機(jī)生成給定參數(shù)的有向無環(huán)圖，并對節(jié)點與節(jié)點邊賦屬性值的方式來構(gòu)建測試集﹒TGFF工具是一款應(yīng)用于任務(wù)劃分及調(diào)度等方面研究的有向無環(huán)圖生成工具﹒利用TGFF工具生成25、50、75、100和125個節(jié)點的5個有向無環(huán)圖，其參數(shù)見表2﹒

表2 DAG的數(shù)據(jù)參數(shù)

3.2 結(jié)果與分析

本文將模擬退火(SA)算法、基本蟻群算法和所提出的改進(jìn)蟻群優(yōu)化算法進(jìn)行比較﹒算法采用C++語言在Intel Core i5 2.2 GHz主機(jī)，4 GB RAM，Windows 7操作系統(tǒng)的環(huán)境下實現(xiàn)﹒

圖3~圖4分別給出了3種算法在算法速度和平均加速比上的對比結(jié)果﹒圖4中的平均加速比是指嵌入式系統(tǒng)在軟硬件劃分以后的運行時間與嵌入式系統(tǒng)采用全軟件實現(xiàn)的運行時間相比得到的性能加速比﹒

圖3 3種算法的速度比

圖4 3種算法的平均加速比

在算法速度方面進(jìn)行分析，節(jié)點數(shù)量在50的情況下，本文算法的執(zhí)行時間為0.47 ms，基本蟻群算法的執(zhí)行時間為0.35 ms，兩者比較接近，而SA算法的執(zhí)行時間為1.21 ms，本文算法和基本蟻群算法稍優(yōu)于SA算法，但差距并不是非常明顯；在節(jié)點數(shù)量在125的情況下，本文算法的執(zhí)行時間為200.15 ms，基本蟻群算法的執(zhí)行時間為290.43 ms，而SA算法的執(zhí)行時間為700.1 ms，明顯體現(xiàn)出本文算法速度最快﹒在平均加速比方面進(jìn)行分析，3種算法都能達(dá)到35%到45%左右的加速比，且沒有明顯的差距，說明這3種算法都能實現(xiàn)一個較好的軟硬件劃分，能使得嵌入式系統(tǒng)達(dá)到一個較好的性能﹒

表3列出了針對5個DAG利用3種算法實現(xiàn)的劃分結(jié)果數(shù)據(jù)﹒根據(jù)表3可明顯看出，當(dāng)節(jié)點數(shù)到75個以上時，本文算法的速度開始明顯快于SA算法和基本蟻群算法，并呈現(xiàn)出節(jié)點數(shù)越大，本文算法的優(yōu)勢越明顯的趨勢﹒對表3中的統(tǒng)計數(shù)據(jù)綜合分析可以得出，在得到相同甚至更優(yōu)化劃分的情況下，本文提出的改進(jìn)蟻群優(yōu)化算法的工作效率要高于SA算法和基本蟻群算法﹒

實驗證明，在DAG的節(jié)點數(shù)在50個左右以及節(jié)點數(shù)量更小的情況下，本文算法、SA算法和基本蟻群算法的劃分效率相近，但是本文算法和基本蟻群算法的速度稍高于SA算法﹒在DAG的節(jié)點數(shù)達(dá)到75個或節(jié)點數(shù)量更大的情況下，本文算法體現(xiàn)出更好的穩(wěn)定性，能較好的克服基本蟻群算法容易陷入局部最優(yōu)解的缺點，同時算法的速度又明顯高于SA算法﹒對125個節(jié)點DAG的算法劃分結(jié)果分析，本文算法的整體工作效率是SA算法的3.5倍左右﹒采用TS算法改進(jìn)蟻群算法的局部搜索過程后，本文算法的整體工作效率是基本蟻群算法的1.45倍左右﹒

表3 實驗結(jié)果比較

4 結(jié)論

本文針對嵌入式系統(tǒng)軟硬件劃分問題，在基于控制數(shù)據(jù)流圖的軟硬件劃分模型的基礎(chǔ)上，提出了基于改進(jìn)蟻群優(yōu)化算法的軟硬件劃分算法并進(jìn)行了算法實驗﹒實驗結(jié)果表明，本文提出的算法能有效地完成軟硬件劃分，并具有較好的計算效率和穩(wěn)定性﹒下一步的工作將改進(jìn)算法的局部搜索策略，優(yōu)化算法的工作效率，使算法的收斂速度更快﹒另外，對蟻群優(yōu)化算法初始信息素的生成策略研究也是今后的研究方向﹒

[1]ZHANG L F. Research on techniques of hardware/software co-synthesis and virtual microprocessor[D]. Changsha: National University of Defense Technology, 2002.

[2]LOPEZ-VALLEJO M, LOPEZ J C. On the hardware-software partitioning problem: system modeling and partitioning techniques[J]. ACM Transactions on Design Automation for Electronic Systems, 2003, 8(3): 269-297.

[3]ARATó P, MANN Z A, ORBáN A. Algorithmic aspects of hardware software partitioning[J]. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1): 136-156.

[4]WU J G, SRIKANTHAN T, JIAO T. Algorithmic aspects for functional partitioning and scheduling in hardware software co-design[J]. Design Automation for Embedded Systems, 2008, 12(4): 345-375.

[5]ERNST R, HENKEL J, BENNER T. Hardware-software cosynthesis for microcontrollers[J]. IEEE Design & Test of Computers, 1993, 10(4): 64-75.

[6]PENG Z B, KUCHCINSKI K. An algorithm for partitioning of application specific systems[C]. European Conf on Design Automation (EDAC). Paris: IEEE Computer Society Press, 1993, 20(5): 316-321.

[7]GUO X D, LIU J R, WEN H. A method for hardware/software partitioning using genetic algorithm[J]. Journal of Computer Aided Design & Computer Graphics, 2001, 13(1): 24-27.

[8]SAHA D, BASU A, MITRA R S. Hardware software partitioning using genetic algorithm[C]. Tenth International Conference on Vlsi Design. Hyderabad: IEEE Computer Society Press, 1997. 155-160.

[9]ELES P, PENG Z B, KUCHCINSKI K, et al. System level hardware/software partitioning based on simulated annealing and tabu search[J]. Design Automation for Embedded Systems, 1997, 2(1): 5-32.

[10]WANG G, GONG W R, KASTNER R. A new approach for task level computational resource bi-partitioning[C]. International Conference on Parallel & Distributed Computing & Systems. California: 2003

[11]DING J L, CHEN Z Q, YUAN Z Z. On the combination of genetic algorithm and ant algorithm[J]. Journal of Computer Re-search and Development, 2003, 40(9): 1351-1356.

[12]BARBAROSOGLU G, OZGUR D. A tabu search algorithm for the vehicle routing problem[J]. Computers & Operations Research, 1999, 26(3): 255-270.

(責(zé)任編校：龔倫峰)

A Method of Hardware and Software Partitioning Based on Modified Ant Colony Optimization Algorithm

HU Wei

(College of Information Engineering, Huangshan University, Huangshan, Anhui 245021, China)

Aiming at the hardware and software partitioning in the hardware and software co-design of the embedded system, a method of hardware and software partitioning based on modified ant colony optimization algorithm is proposed. The tabu search table is used to record the recent search process that can prevent the algorithm from entering repeatedly. The tabu search algorithm is used to make better the local search of ant colony algorithm, which can improve the search efficiency of the optimal solution and the executive speed of the algorithm. The experimental data show that modified ant colony optimization algorithm that can improve the efficiency of about 45%. The experiment results show that compared with conventional algorithm, the algorithm can be used to solve the hardware and software partitioning problem effectively and efficiently.

embedded system; hardware and software codesign; hardware and software partitioning; ant colony optimization algorithm

TP301.6

A

10.3969/j.issn.1672-7304.2017.06.0011

1672–7304(2017)06–0050–05

2017-11-07

安徽省高校優(yōu)秀中青年骨干人才國內(nèi)外訪學(xué)研修重點項目(gxfxZD2016229)

胡偉(1978- )，男，安徽績溪人，講師，碩士，主要從事計算機(jī)及嵌入式系統(tǒng)研究．E-mail: 79760667@qq.com