一種基于改進蟻群優化算法的軟硬件劃分方法

胡 偉

?

一種基于改進蟻群優化算法的軟硬件劃分方法

胡 偉

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

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

嵌入式系統；軟硬件協同設計；軟硬件劃分；蟻群優化算法

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

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

1 問題描述

1.1 軟硬件劃分功能

軟硬件劃分算法要求在滿足預定的系統約束的前提下實現系統性能的最優化，通常將算法優化的起始點設置為系統功能的全軟件實現﹒

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

軟硬件劃分算法決定硬件和軟件可分別實現哪些節點﹒軟硬件劃分后，所有任務都能被映射到一個劃分后的分組中，且對劃分結果進行評估，當劃分結果在速度、功耗、面積與性能等方面均達到一個很好的平衡時結束算法，否則繼續執行算法來產生新的劃分，并對其進行新的評價﹒

圖1 節點系統任務的有向無環圖

1.2 軟硬件劃分模型

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

圖2 體系結構模型

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

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

系統總的功耗可以描述為：

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

1.3 改進蟻群優化算法在軟硬件劃分上的研究

1.3.1 蟻群優化算法

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

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

1.3.2 算法設置

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

表1 參數設置

1.3.3 解的構造

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

1.3.4 局部搜索

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

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

1.3.5 信息素更新

2 算法實現

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

3 實驗

3.1 實驗環境

目前國際上還沒有在嵌入式系統的軟硬件劃分領域發布標準測試集，故可用工具隨機生成給定參數的有向無環圖，并對節點與節點邊賦屬性值的方式來構建測試集﹒TGFF工具是一款應用于任務劃分及調度等方面研究的有向無環圖生成工具﹒利用TGFF工具生成25、50、75、100和125個節點的5個有向無環圖，其參數見表2﹒

表2 DAG的數據參數

3.2 結果與分析

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

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

圖3 3種算法的速度比

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

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

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

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

表3 實驗結果比較

4 結論

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

[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.

(責任編校：龔倫峰)

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

安徽省高校優秀中青年骨干人才國內外訪學研修重點項目(gxfxZD2016229)

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