胡 偉

?

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

胡 偉

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

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

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

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

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

1 問(wèn)題描述

1.1 軟硬件劃分功能

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

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

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

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

1.2 軟硬件劃分模型

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

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

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

文中的劃分問(wèn)題可以描述如下：

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

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

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

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

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

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

1.3.2 算法設(shè)置

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

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

1.3.3 解的構(gòu)造

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

1.3.4 局部搜索

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

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

1.3.5 信息素更新

2 算法實(shí)現(xiàn)

本文的算法由4個(gè)主要步驟組成﹒

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 結(jié)果與分析

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

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

圖3 3種算法的速度比

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

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

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

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

表3 實(shí)驗(yàn)結(jié)果比較

4 結(jié)論

本文針對(duì)嵌入式系統(tǒng)軟硬件劃分問(wèn)題，在基于控制數(shù)據(jù)流圖的軟硬件劃分模型的基礎(chǔ)上，提出了基于改進(jìn)蟻群優(yōu)化算法的軟硬件劃分算法并進(jìn)行了算法實(shí)驗(yàn)﹒實(shí)驗(yàn)結(jié)果表明，本文提出的算法能有效地完成軟硬件劃分，并具有較好的計(jì)算效率和穩(wěn)定性﹒下一步的工作將改進(jìn)算法的局部搜索策略，優(yōu)化算法的工作效率，使算法的收斂速度更快﹒另外，對(duì)蟻群優(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)秀中青年骨干人才國(guó)內(nèi)外訪學(xué)研修重點(diǎn)項(xiàng)目(gxfxZD2016229)

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