[發明專利]基于人工蜂群的軟硬件劃分方法

有效

• 申請號: 201310012918.3
• 申請日: 2013-01-14
• 公開（公告）號: CN103116693A
• 公開（公告）日: 2013-05-22
• 發明（設計）人: 張濤;全浩軍;韓宏業;蔡曉;王贊
• 申請（專利權）人: 天津大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 杜文茹

技術領域

本發明涉及一種軟硬件劃分的方法。特別是涉及一種針對一個嵌入式系統實現復雜任務的基于人工蜂群的軟硬件劃分方法。

背景技術

1、蜂群算法簡介

蜂群算法（ABC?algorithm）是建立在蜜蜂和蜜蜂群體群居行為的模型上。蜂群主要的行為包括搜索食物源、為食物源招募跟隨蜂和放棄食物源。蜜蜂具有很強的群體適應能力，群體中的個體通過氣味、舞蹈等信息交互的方式進行個體和群體的協同，進而完成比較復雜的任務，如：覓食、繁衍后代等。

蜂群算法中的蜂群包含引領蜂（employed?bees）、跟隨蜂（onlookers）和偵察蜂（scouts）。在每一次循環中，引領蜂和偵察蜂的數目相同，當找到較好的食物源后，這個食物源處留一只蜜蜂，其他的偵察蜂重新偵查新的食物源。引領蜂和跟隨蜂負責食物的開采，偵察蜂負責執行對食物源的尋找工作，通過三種蜂的協調完成蜂群對食物源的探索和開采，具有較快的收斂速度，能夠達到較好的平衡，尋找到最佳的食物源。蜜蜂采蜜的過程相當于尋找最優解的過程，最終的最優解對應的編碼信息即為系統任務劃分的最佳方案。

2、軟硬件劃分原理

假設待劃分系統由N個結點構成，每個結點既可以用軟件實現（用0表示），也可以用硬件實現（用1表示），這樣N個結點的軟硬件劃分構成了一個N維空間，將每一種劃分方案看作一個食物源位置等信息。根據此映射關系，將蜂群算法中的所有的食物源映射到N維空間中，我們要從所有的食物源中找到最優的食物源，而每一個食物源位置等信息可以被看作一個N維的編碼信息，與編碼信息對應的方案即為實現任務的軟硬件劃分的方案。

我們將一個系統的任務分為若干個子任務來執行，這些任務可以由硬件（用1表示）和軟件（用0表示）的結合來完成，這些任務的執行順序對應的編碼可以看做一組有序的二進制數。抽象為數學中的一個可行解。

顯然，從數學角度來講，結點數越多，其對應的不同的任務軟硬件劃分方案越多，并且其數目成指數增長。對于一個由N個結點組成的DAG圖，我們將第i個結點任務用硬件執行，其它結點任務用軟件執行所對應的序列看作由)組成了集合Keys，其數學表達式如式1.1所示：

Keys:＝{ξ_i}(i:＝1,2,...,N)?????1.1

由Keys生成的解空間用spanKeys來表示，spanKeys的數學表達式如式1.2所示：

我們將