（微電子學與固體電子學專業(yè)論文）基于fpga的可進化系統(tǒng)的設(shè)計與研究.pdf

摘要 摘要 可進化硬件 e h w e v o l v a b l eh a r d w a r e 是指在與外部環(huán)境相互作用時 能夠自主 動態(tài)地改變其自身結(jié)構(gòu)和行為的硬件電路 可進化硬件的基本特征是 具有自組織 自適應 自修復的能力 在智能化通信網(wǎng)絡 智能感知 模式識別 與人工智能等方面有廣泛的應用前景 由于可編程器件f p g a f i e l dp r o g r a m m a b l eg a t ea r r a y 的電路功能可以通 過對其底層結(jié)構(gòu)加載不同的配置位串而靈活地改變 因此 早在1 9 9 2 年 國際 人工智能專家h u g od eg a r i s 博士就提出基于f p g a 的e h w 這一概念 3 1 當前 基于f p g a 的建立的可進化硬件系統(tǒng)已經(jīng)成為了可進化硬件研究的主要方法 本文介紹了可進化硬件的基本概念 分析了基于f p g a 的可進化系統(tǒng)的研究 現(xiàn)狀 從可進化系統(tǒng)的基本組成部分 可重構(gòu)電路模型 基因算法 可重構(gòu)電路 部分配置等方面 提出了優(yōu)化和改進基于f p g a 的可進化系統(tǒng)的方法 設(shè)計并驗 證了基于f p g a 的完整的可進化系統(tǒng) 首先本文對于當前主流的基于f p g a 的可進化硬件實現(xiàn)方法 虛擬可重構(gòu)電 路模型 v r c v i r t u a lr e c o n f i g u r a b l ec i r c u i t 進行了介紹和分析 從電路功能單 元以及互連等方面提出并驗證了基于3 輸入l u t 的直接互連線型的v r c 結(jié)構(gòu)模 型 并且在a l t e r a d e 2 開發(fā)板上進行了可進化實驗 證實了該模型 其次 針對于可進化系統(tǒng)的基本組成部分 基因算法 電路配置兩方面進行 了分析 參與設(shè)計驗證了適合于進化的c p u f p g a 可重構(gòu)系統(tǒng)芯片 f d p 2 0 0 9 2 s o p c 該芯片從3 個方面優(yōu)化了可進化系統(tǒng)的實現(xiàn) 第一 專門設(shè)計f p g a 配置控 制接v i 可以實現(xiàn)通過c p u 對f p g a 進行快速部分配置 實現(xiàn)單芯片 o nc h i p 硬件進化 第二是針對進化過程中每次只有少量位流改變的情況 f p g a 的位 流配置結(jié)構(gòu)采用了行列雙譯碼方式 可以以1 數(shù)據(jù)字為單位對f p g a 進行配置讀 寫 提高了部分重配置速度 第三 針對基因算法的特點 專門設(shè)計基因算法加 速器 改善基因算法的實現(xiàn)時間 最后基于上述可重構(gòu)系統(tǒng)芯片 我們建立了完整的芯片級可進化系統(tǒng) 實現(xiàn) 了完整的單芯片可進化流程 并在此基礎(chǔ)上驗證了基因算法加速器以及部分配置 等硬件部分對于片上可進化系統(tǒng)的改進程度 關(guān)鍵詞 進化硬件 虛擬可重構(gòu)電路模型 芯片級進化系統(tǒng) f p g a 進化加速 器 部分配置 中圖分類號 t n 4 7 a b s t r a c t a b s t r a c t e v o v a b l eh a r d w a r ei st h eh a r d w a r et h a t c a nd y n a m i c a l l ya n di n d e p e n d e n t l y c h a n g ei t ss t m c t u r ea n db e h a v i o u rw h e ni n t e r a c t sw i t ht h ee n v i o r e m e n t t h e b a s i c c 1 a r a c t e ro fe h wi s s e l f o r g n i z a t i o n s e l f a d a p t i o n s e l f r e s t o r e t h e r e a r ew i d e p r o s p e c to fe h w i ni n t e l l i g e n tc o m m u n i c a t i o nn e t w o r k i n t e l l i g e n ts e n s o r p a t t e r n r e c o g n i t i o na n da r t i f i c i a li n t e l l i g e n c e f o rt 1 1 ef p g ac a nc h a n g ei t sf u n c t i o nc o n v e n i e n t l yt h r o u g h d i f f e r e n t c o n f i g u r a t i o nb i ts t r e a m e a r l yi n19 9 2i n t e r n a t i o n a le x p e r t si na r t i f i c i a li n t e l l i g e n c ed r h u g od eg a f f sp r o p o s e dt h ec o n c e p to fe h w b a s e do nf p g a c u r r e n t l y e h wb a s e do n f p g ah a sb e c o m et h em o s tp o p u l a rw a yi nt h ee v o l v a b l eh a r d w a r er e s e a r c h i nt h i sp a p e r t h ec o n c e p to fe h wi si n t r o d u c e d a n dt h er e c e n tr e s e a r c ho fe h w b a s e do nf p g ai sa n a l y s e d f r o ma n a l y s i so ft h eb a s i cp a r to fe h w r e c o n f i g u r a b l e c i r c u i tm o d e l g e n e t i ca l g o r i t h m a n dc o n f i g u r a t i o no fr e c o n f i g u r a b l ec i r c u i t t h e s o l u t i o nt oi m p r o v ee h wb a s e do nf p g ai sp r o p o s e da n dc o m p l e t ee v o l u t i o ns y s t e m b a s e df p g ai sd e s i g n e da n dv e r i f i e d f i r s t t h em a i n s t r e a mi m p l e m e n t a t i o no fe h wb a s e d o nf p g a v i r t u a l r e c o n f i g u r a b l ec i r c u i tm o d e l v r c i si n t r d u c e da n da n a l y s e di nt h i sp a p e r o n ev r c m o d e lb a s e do n3 i n p u tl u tw i t hd i r e c tc o n n e c t i o ni sp r o p o s e df r o mt h ev i e wo f f u n c t i o nc e l la n di n t e r c o n n e c t i o n a n dt h i sm o d e li sv e r i f i e dt h r o u g ht h ee v o l u t i o n e c p e r i m e n to n a l t e r ad e 2 p l a t f o r m s e c o n d a n a l y s et h e b a s i cp a r t so fe h w g e n e t i ca l g o r i t h m a n dc i r c u i t c o n f i g u r a t i o n a n dp a r t i c i p a t e i n d e s i g n a n dv e r i f i c a t i o no ft h ec p u f p g a r e c o n f i g u r a b l es y s t e mc h i pf d p 2 0 0 9 2 s o p c t h i sc h i pi m p r o v et h ei m p l e m e n t a t i o no fe v o l u t i o ns y s t e mf r o m3a s p e c t s o n ei s t h es p e c i a lc o n f i g u r a t i o np o r to ff p g aw h i c hc a ni m p l e m e n tf a s tp a r t i a lc o n f i g u r a t i o n t of p g at h r o u g hc p u c a nr e a l i z eo n c h i pe v o l u t i o n t h es e c o n do n ei s c o n f i g u r a t i o n o ff p g ai no r l ew o r dc a nb ei m p l e m e n t e dw h e nf e wb i t s t r e a mi sc h a n g e di ne v e r y i n t e r a t i o no fe v o l u t i o n f o rr o w c o l u m nd e c o d e ri nb i t s r e a ms t r c t u r eo ff p g a i tc a n i m p r o v et h et i m e o fp a r t i a lc o n f i g u r a t i o n t h el a s to n ei st h eg e n e t i ca l g o r i t h m a c c e l e r a t o rd e s i g n e df o rc h a r a c r t e r i s t i c o fg e n e t i c a l g o r i t h m t h ea c c e l e r a t o rc a n i m p r o v et h ei m p l e m e n t a t i o nt i m eo fg e n e t i ca l g o r i t h m a tl a s t o n ec o m p l e t e o n c h i p e v o l u t i o n s y s t e m i sb u i l tb a s e do nt h e i i a b s t r a c t r e c o n f i g u r a b l es y s t e mc h i pa b o v e a n dt h ee x p e r i m e n t st ov e r i f yt h ei m p r o v e m e n to f e v o l u t i o ns y s t e mc a u s e db yg e n e t i ca c c e r l e r a t o ra n dp a r t i a lr e c o n f i g u r a t i o na r ed i d k e y w o r d e h w v r c o n c h i pe v o l u t i o ns y s t e m f p g a g e n e t i ca l g o r i t h m a c c e r l e r a t o r p a r t i a lc o n f i g u r a t i o n i i i 第l 章緒論 1 1 可進化硬件 第1 章緒論 隨著電路系統(tǒng)所要求解決的問題日趨復雜 而復雜性的提高導致了電路系統(tǒng) 穩(wěn)定性和可靠性的降低 傳統(tǒng)的硬件電路設(shè)計方法由于是一種自上而下的設(shè)計方 法 即必須先有該類電路的理論 設(shè)計方法 才能進行具體設(shè)計 嚴重依賴于設(shè) 計者的經(jīng)驗和固定的設(shè)計方法 影響了電路設(shè)計的效率和實現(xiàn)能力 不能解決日 趨復雜的電路系統(tǒng)設(shè)計問題 而通過硬件進化設(shè)計硬件則是一種自下而上的方法 將基因算法應用到硬件 電路設(shè)計的產(chǎn)品 不依賴于先驗知識 能處理傳統(tǒng)方法難以勝任的復雜電路設(shè)計 問題且能根據(jù)環(huán)境變化進行動態(tài)調(diào)整 這種方法自動化程度較高 可顯著降低設(shè) 計成本 還可以開拓設(shè)計思路 找到很多人類難以通過正向思維方法得到的設(shè)計 方案n 兒刳 提供了解決上述問題的有效途徑 因此基于硬件進化的電路設(shè)計方法 是一種在設(shè)計成本 設(shè)計思路等多方面優(yōu)于傳統(tǒng)電路設(shè)計方法的新型電路設(shè)計技 術(shù) 而硬件進化的研究正是這種設(shè)計方法的基礎(chǔ) 進化硬件d 兒釘 也稱演化硬件 的起源最早可追溯到上世紀五十年代 計算 機之父首先提出了研制具有自繁殖與自修復能力的機器的設(shè)想 但是由于當時技 術(shù)條件的限制使這一設(shè)想未能實現(xiàn) 直到基因算法和大規(guī)?？删幊唐骷某霈F(xiàn) 這一設(shè)想才成為可能 基于基因算法和大規(guī)?？删幊唐骷某霈F(xiàn) 進化硬件將基因算法與電子學有 效的結(jié)合在一起 理想的可進化硬件不但具有自我診斷能力 能夠通過自我的重 構(gòu)來消除錯誤 而且可以在設(shè)計要求或系統(tǒng)工作環(huán)境發(fā)生變化的情況下 還可以 通過自我重構(gòu)來使電路適應這種變化而繼續(xù)正常工作 目前進化硬件主要應用領(lǐng) 域巧3 包含有 1 電路設(shè)計 2 容錯系統(tǒng) 自適應和自修復系統(tǒng) 3 自動控制系統(tǒng) 4 智能機器人 5 模式識別與人工智能等 而主要的研究方向可以分為著重點在 數(shù)字電路的硬件進化和著重于模擬電路的硬件進化 在進化硬件領(lǐng)域中 數(shù)字電路的硬件進化作為其中的一個主要的研究方向 早在在1 9 9 2 年t e t s u y ah i g u c h i 和h u g od eg a r i s 就開始致力于實現(xiàn)數(shù)字電路 的硬件進化障 7 并提出了使用基因算法重新配置硬件結(jié)構(gòu)實現(xiàn)進化的方法 其 后在大規(guī)模可編程邏輯器件的基礎(chǔ)上 數(shù)字電路進化的研究領(lǐng)域越來越廣泛 s e k a n i n a 等人則致力于函數(shù)級的數(shù)字電路進化 如濾波器嘲 并表明這些濾波器 在多種濾波的情況下比傳統(tǒng)的濾波器表現(xiàn)更好 而g a r v i e 等人實現(xiàn)了一些基本 邏輯功能如加法器 乘法器的數(shù)字電路 并表明在資源占用上更有優(yōu)勢 1 如下 第l 章緒論 圖1 1 數(shù)字硬件進化結(jié)果 2 b i t 乘法器 上圖1 1 是g a r v i e 等人通過硬件進化的方法得到的2 b i t 乘法器 其中 a 0 b 0 a l b 1 是乘法器的輸入 而x 0 一x 3 是乘法器的輸出端 實驗結(jié)果證明該乘 法器消耗的資源比人工直接設(shè)計的乘法器更少 除了數(shù)字電路進化 進化硬件另一大領(lǐng)域是模擬進化硬件 在模擬進化領(lǐng)域 中 很多有效的應用研究也在進行中 比如z e b u k u m n 陽等人在f p t a f i e l d p r o g r a m m a b l et r a s n s i s t o ra r r a y 的可重構(gòu)平臺上實現(xiàn)了信號的分離 k a s a i 等人u 則展示了基于f t p a 以及基因算法完成的自適應型波形的控制 s e k a n i n a 則基于該平臺實現(xiàn)了振蕩器n 引 其中f p t a 平臺如下圖 圈圖 圈圖 圈圈 國圖 圈圈 圈圖 圈圈 囹圇 圈圇 囡國 圇囡 圖圖 圖圈 囂 圖圖 圖囹 曩圈 圈囡 圇圈 圖圇 園圈 圖圈 圈囝 圖 圈囝 圈圇 圈 圉 圖1 2 模擬硬件進化平臺f p t a 上圖中f p t a 是由多個基本單元組成的 其中基本單元的結(jié)構(gòu)如上圖右所示 是由多個可以改變參數(shù)的m o s 管組成的 1 2 進化硬件原理 進化硬件主要由3 部分組成n 引 可重構(gòu)的硬件 基因算法 電路的評估部分 如上圖所示 第1 章緒論 圖1 3 硬件進化的組成 基因算法是進化硬件中的核心部分n4 也是硬件進化的初始步驟 在算法中 電路的結(jié)構(gòu)和參數(shù)等配置信息在編碼后作為算法中的染色體 一個個體的染色體 則對應一種具體的配置信息 可重構(gòu)硬件負責接收基因算法給予的染色體 并且 根據(jù)染色體改變自身的結(jié)構(gòu)和功能 而電路評估部分則是根據(jù)進化的目標對可重 構(gòu)硬件部分進行評估 得到當前染色體配置情況下可重構(gòu)硬件與進化目標的符合 程度 給予相應的評估結(jié)果 這個評估結(jié)果就是適應度 而整個進化的過程正如上圖所示 是由這三個部分組成的循環(huán)迭代過程構(gòu) 成 1 從基因算法部分開始 首先根據(jù)設(shè)計的目的 產(chǎn)生初步的方案 包括設(shè) 定基因算法的中種群大小 基因操作的概率 染色體數(shù)目等具體參數(shù) 并將每個 染色體作為一個個體 而每個個體表示的是設(shè)計的一部分 在確定了基因算法的 各個具體參數(shù)后 基因算法開始初始化 產(chǎn)生多個包含染色體的個體 即產(chǎn)生了 多組可重構(gòu)硬件的配置信息 2 可重構(gòu)硬件接收染色體轉(zhuǎn)化成的控制數(shù)據(jù)流 從而確定可重構(gòu)硬件內(nèi) 部各單元的聯(lián)結(jié)和功能 形成了初步的硬件系統(tǒng) 其中用來設(shè)計進化硬件的可重 構(gòu)器件應該可以接受任意組合的數(shù)據(jù)流下載 而不會導致器件的損害 3 電路的評估部分將設(shè)計結(jié)果與進化目標的要求進行比較 并根據(jù)適應度 的衡量準則計算該個體的適應度 并將適應度信息傳遞給基因算法 其中實現(xiàn)適 應度的評估需要一定的檢測手段和評估軟件的支持 4 基因算法根據(jù)適應度再對新的個體組進行統(tǒng)計 并根據(jù)統(tǒng)計結(jié)果挑選一 些個體 基因算法根據(jù)這些個體的適應度進行相應的修改 如進行基因操作 產(chǎn) 生新一代染色體 基因操作的目的是為了產(chǎn)生更具適應性的下一代 5 重復上述2 4 步驟 這三個組成部分輪流工作 并且不斷地產(chǎn)生新的數(shù) 代個體 直到新的個體表示的設(shè)計方案表現(xiàn)出接近要求的適應能力為止 第l 章緒論 一般來說通過基因算法 可重構(gòu)硬件 以及電路評估這三部分的協(xié)作 最后 會得到一個或數(shù)個設(shè)計結(jié)果 最后設(shè)計方案具有對設(shè)計要求和系統(tǒng)工作環(huán)境的最 佳適應性 這一過程即上文提到的內(nèi)部進化或硬件進化 1 3 本文重點 本文簡要的概述了進化硬件的研究背景 對于當前基于f p g a 的進化硬件的 多個方面的研究進行了分析 并且提出了相應的解決方法 本文的工作重點如下 1 介紹進化硬件的基本概念 以及硬件進化的基本原理 2 針對于當前主流的數(shù)字電路的硬件進化研究進行了介紹 并針對于該研 究領(lǐng)域 如可重構(gòu)電路模型 芯片級進化 以及基因算法等多個問題進 行了分析 3 基于當前的基于f p g a 的可重構(gòu)電路模型研究 提出了在a l t e r a d e 2 平 臺上進行可重構(gòu)電路模型的互連的探討 比較了當前可重構(gòu)電路模型中 主流的兩種互連的在一般規(guī)模的組合邏輯進化時的硬件進化速度 4 基于當前數(shù)字電路硬件進化的主要問題 參與了項目組自主設(shè)計的 f d p 2 0 0 9 2 一s o p c 芯片中適合于進化的基因算法加速器 自配置 部分 配置等模塊的設(shè)計和驗證工作 該芯片經(jīng)過流片測試功能正常 5 基于f d p 2 0 0 9 2 s o p c 芯片搭建了芯片級進化進化流程 芯片級進化的 硬件平臺 并在該平臺上進行了芯片級進化系統(tǒng)的研究 測試和驗證了 f d p 2 0 0 9 2 s o p c 芯片中針對硬件進化的各個模塊 并在芯片級進化中 測試了這些模塊對于芯片級進化速度的影響 6 在以上芯片級進化系統(tǒng)的實現(xiàn)和研究后 對于芯片級進化的發(fā)展進行了 展望和總結(jié) 1 4 文章結(jié)構(gòu) 本文共分為6 個章節(jié) 其中第2 章介紹了數(shù)字電路的硬件進化的研究現(xiàn)況 并根據(jù)當前數(shù)字電路硬件進化的研究提出了針對于當前芯片級進化的優(yōu)化和改 進 諸如 基因算法加速 自配置 部分配置等方面 第3 章介紹了當前基于 f p g a 的可重構(gòu)電路模型的研究狀況 并且基于a l t e r ad e 2 的開發(fā)板實現(xiàn)了基于 可重構(gòu)電路模型的進化系統(tǒng) 針對于可重構(gòu)電路模型的互連方面進行深一步的研 究 第4 章詳細介紹了課題組自主設(shè)計的片上系統(tǒng)芯片f d p 2 0 0 9 2 s o p c 的架構(gòu) 以及f d p 2 0 0 9 2 s o p c 芯片中適合于硬件進化的多個模塊 基因算法加速器 編 4 第1 章緒論 程下載 以及p o w e r p c 與f p g a 的通信接口 并且介紹了在系統(tǒng)芯片中這些部 分的測試方法和結(jié)果 第5 章在f d p 2 0 0 9 2 s o p c 芯片的基礎(chǔ)上搭建了芯片級進 化的流程 以及芯片級進化的硬件平臺 并基于該進化平臺和進化流程針對 f d p 2 0 0 9 2 一s o p c 芯片中適合于進化硬件的部分在芯片級進化中的作用進行了測 試 第6 章總結(jié)了本論文的研究成果并對基于芯片級進化實驗和測試對于芯片級 進化進行了總結(jié)和展望 第2 章數(shù)字進化硬件的研究 2 1 數(shù)字可進化硬件分類 第2 章數(shù)字進化硬件的研究 當前進化硬件研究方向廣泛 本文主要著重于數(shù)字電路進化硬件 其中數(shù)字 進化硬件涉及到基因算法 可重構(gòu)硬件 實現(xiàn)優(yōu)化等研究方面 數(shù)字進化硬件按 照進化硬件中基本組成 可重構(gòu)硬件 基因算法 電路評估等部分的不同實現(xiàn)方 式就可以有不同的分類 如下所示 1 按照硬件實驗方式可以分為兩種 一種是外部進化 1 5 e x t r i n s i c e v o l v a b l e 也被稱為離線進化 另一種是內(nèi)部進化 1 6 i n t r i n s i ce v o l v a b l e 也稱在線進化 這種分類方法被普遍認可 并對進化電路的評估方法起著重要的 作用 外部進化是通過建立電子器件的模型 將由基因算法產(chǎn)生的染色體在模型上 進行評價 當達到預期目標時 再將這組染色體下載到重構(gòu)硬件中去 這種方法 進化過程都在計算機內(nèi)通過軟件完成 雖然靈活方便 可以簡單快捷的修改進化 模型 評估函數(shù)等 但是計算機通過仿真的速度慢 如果進化模型比較復雜 則 很難建模 內(nèi)部進化是將基因算法每一代產(chǎn)生的每一條染色體都實際下載到可重構(gòu)器 件中去 并對每一種電路結(jié)構(gòu)的輸出直接進行評價 它對硬件本身有很高的要求 由于早期演化硬件的研究中 用到的是結(jié)構(gòu)比較簡單的p a l 或g a l 等p l d 器件 這些器件不能無限次編程 配置時間也較長 結(jié)構(gòu)簡單 因此在早期通常 采用外部進化方式 但它只能實現(xiàn)較小規(guī)模的電路 在工程應用中限制較大 當 出現(xiàn)f p g a 以后 由于器件結(jié)構(gòu)和功能比先前有了很大的改進和提高 且f p g a 本身有其獨有的特性 如有可無限次重復編程 可重構(gòu)功能 這些特性都為實現(xiàn) 內(nèi)部進化提供了很有利的條件 2 按照可進化平臺中使用的芯片分類 硬件進化可以分為專用芯片 專 用系統(tǒng) f p g a 等 專用芯片指的是針對進化目標專門設(shè)計的一種芯片 這樣可 以達到比較高的進化速度 但是這樣的芯片設(shè)計比較復雜 相應的成本也高 而 并且只能針對專用領(lǐng)域 如在m o r e n o 等人設(shè)想的p o e t i c 平臺上 1 7 b a r k e r 等 人在針對容錯硬件時就需要重新設(shè)計專用的p o e t i c t l 8 專用系統(tǒng)則是則指根據(jù) 進化目標而設(shè)計的復雜的板級系統(tǒng) 該系統(tǒng)一般是由很多的c p u d s p f p g a 等可編程芯片構(gòu)成 如a n d r e w 的r i s a 平刨1 9 等 但在上述平臺中 研究最多 的還是基于f p g a 的進化硬件研究 2 0 1 一方面f p g a 擁有大量的邏輯資源 能 第2 章數(shù)字進化硬件的研究 夠?qū)崿F(xiàn)較復雜的功能電路 另一方面f p g a 可以無限次地重新編程 通過重新編 程改變原有的功能 這一部分在2 4 節(jié)將著重介紹 基于上述的分類 本文的研究重點依次屬于上述分類中的 1 內(nèi)部進化 3 基于f p g a 實驗平臺的進化 在內(nèi)部進化的研究中 可重構(gòu)電路模型一直是區(qū)別 內(nèi)部進化和外部進化的標志 本文將針對基于f p g a 的可重構(gòu)電路模型進行進一 步的研究 除此之外 本文還將針對基于f p g a 的實驗平臺的單芯片進化進行進 一步的分析 2 2 虛擬可重構(gòu)電路模型 在內(nèi)部進化硬件的研究中 大部分研究是基于f p g a 實現(xiàn)的 f p g a 邏輯資 源十分豐富 配置位串高達數(shù)百萬位 可以在不同的配置位串的控制下實現(xiàn)不同 的功能 但是一般由于其商業(yè)秘密其底層結(jié)構(gòu)往往不予公開 用戶很難直接操縱 底層邏輯資源 因此 當前主流的可進化硬件研究中可重構(gòu)電路部分一般是使用 虛擬的可重構(gòu)電路模型的實現(xiàn)方法 v i r t u a lr e c o n f i g u r a b l ec i r c u i t 即v r c 2 1 1 v r c 作為主流的可進化硬件研究的實現(xiàn)方式 至今為止很多的進化硬件研 究中使用了多種v r c 下面將基于一個簡單的實例介紹v r c 的組成 j u l i a nf m i l l e r 在研究2 位乘法器實現(xiàn)中的邏輯門級的v r c 實例 2 2 1 如下圖所示 f 0 0 0 0 x y f 1 0 0 l x n y f 2 0 1 0 x f 3 0 1 l x l y f 4 1 0 0 1 f 5 1 0 1 y l f 6 1 1 0x y f 7 1 1 lx k 一 圖2 1 j u l i a nfm i l l e rv r c 模型 在圖中 可以看到虛擬電路模型一般是由多個功能單元以及功能單元的互連 資源組成的 該模型中有1 9 共9 個功能單元 每個功能單元有兩個輸入和兩個 輸出 可以選擇上圖中的8 種基本的門級邏輯函數(shù)之一 而單元之間的互連是固 定的 是每個功能單元的輸出連接到向右和向上的功能單元 該v r c 的實現(xiàn)方法是通過 1 通過高層語言如 v h d l 等 在邏輯門級 函數(shù)級建立電路模型 即上述的邏輯函數(shù)陣列 2 將該電路模型綜合為f p g a 上的配置位串 并兩層的f p g a 結(jié)構(gòu)建模的方法來實現(xiàn)的 如圖所示 7 第2 章數(shù)字進化硬件的研究 圖2 2 兩層建模方法 而包含該v r c 模型的整個進化的系統(tǒng)則如下所示 o 函 圖2 3 基于v r c 的進化系統(tǒng) 如上圖 v r c 模型和電路評估部分均通過配置f p g a 的邏輯資源實現(xiàn) 這 種實現(xiàn)方法不但降低了在進化時f p g a 的資源利用率和進化速度 同時由于v r c 模型中基本單元通常是針對一個具體目標來選擇一系列基本邏輯函數(shù) 如 與 或 非等 作為進化的基本單元 比如上面j u l i a nf m i l l e r 在2 位乘法器作為進 化目標時選擇的基本邏輯功能的集合 因此 傳統(tǒng)的v r c 模型的通用性和靈活 性比較差 2 3 基于f p g a 的可進化硬件 由于可編程門陣列 f p g a 的電路結(jié)構(gòu)可動態(tài)進行配置和改變 因此可編 程門陣列 f p g a 以其獨有的優(yōu)點為國外多數(shù)研究人員用作硬件進化和可重構(gòu) 第2 章數(shù)字進化硬件的研究 研究的平臺 早在1 9 9 2 年 國際人工智能專家h u g od eg a f f s 博士就提出基于 f p g a 的e h w 這一概念 6 1 f p g a 屬于高容量的 可編程性的邏輯器件 依據(jù)當前的制造工藝 主要可 分為s r a m f l a s h 以及反熔絲三種類型 而基于s r a m 的f p g a 是當代最主流 應用最廣泛的的類型 一方面是因為基于s r a m 的f p g a 在配置速度上快 另 一方面則是因為其可重構(gòu)的編程能力 基于f p g a 的e h w 一般就是利用f p g a 的在線可編程技術(shù)及其可重構(gòu)技 術(shù) 將f p g a 的配置信息作為染色體 并通過基因算法 g e n e t i ca l g o r i t h m 對 其進行反復的基因算法的操作 最終得出符合環(huán)境要求的個體 這個個體就對應 著相應的正確的電路配置 從而使電路適合環(huán)境的變化 當所使用的環(huán)境發(fā)生變 化時 或被放置于未知的環(huán)境中時 這種基于f p g a 的e h w 就會自動地再次啟 動基因算法 調(diào)整電路配置 將f p g a 重構(gòu)為在當前環(huán)境下能夠符合要求的功能 當前基于f p g a 的e h w 研究根據(jù)其實現(xiàn)方式 又可以分為板問 i n t e r b o a r d f p g a 進化 板級芯片間 i n t e r c h i p f p g a 進化 芯片級 o nc h i p f p g a 進 化 2 3 基于f p g a 的板間進化t z 4 j 女l l 下圖所示 計算機來實現(xiàn)基因算法 并通過配 置接口板給f p g a 芯片配置 通過數(shù)據(jù)接口進行適應度和染色體數(shù)據(jù)等大量數(shù)據(jù) 的通信 這種方法優(yōu)點是實現(xiàn)簡單 靈活 缺點是平臺要求高 需要p c 機的支 持 在傳輸大量數(shù)據(jù)時速度會變慢 板間f p g a 進化 平臺 圖2 4 板間進化 而板級芯片間f p g a l 2 5 進化則使用芯片代替了計算機 降低了平臺要求 但 是損失了基因算法的運行性能 并沒有改善大量數(shù)據(jù)傳輸?shù)乃俣葐栴} 板級f p g a 進化 平臺 圖2 5 板級進化 下面將舉例說明一種板問進化系統(tǒng) s e k a n i n a 在 o nr o u t i n ei m p l e m e n t a t i o n o f v i r t u a le v o l v a b l ed e v i c e su s i n gc o m b 0 6 2 6 1 中使用的板間進化實例 9 第2 章數(shù)字進化硬件的研究 圖2 6 板問進化系統(tǒng) 從上圖 可以看到s e k a n i n a 實現(xiàn)的板間進化由三大部分組成 處理器 x i n l i n x s p a r t a n i i 芯片 以及v i r t e x i i 芯片 該進化系統(tǒng)未使用p c 機或者嵌入式c p u 芯片來實現(xiàn)基因算法 這樣一方面不能使用復雜的基因算法 另一方面在基因算 法的性能上也受了限制 除此以外 需要使用處理器來實現(xiàn)j b i t s 2 7 工具進行 f p g a 的配置位串的轉(zhuǎn)換 并且通過r i b b o nc a b l e 傳輸大量的數(shù)據(jù) 因此需要額 外耗費大量的時間在不同模塊的通信上 我們可以看到板間f p g a 進化需要外部的控制和配置 在平臺要求上比較高 耗費的資源也較多 而芯片級進化 2 9 1 貝4 是通過嵌入式c p u 電路來實現(xiàn)基因算法 控制芯片內(nèi)部的f p g a 的可重構(gòu)部分完成進化流程 如下圖 在這樣的可重構(gòu)電 路和c p u 電路組成的可進化系統(tǒng)芯片平臺上 硬件進化時不再需要外界的控制 和數(shù)據(jù)通信 能夠在單芯片上完成進化流程 在平臺要求上均優(yōu)于另外兩種平臺 而且節(jié)省了大量數(shù)據(jù)通信所耗費的時間 在速度上不再受限于數(shù)據(jù)通信 因此芯 片級的進化系統(tǒng)是可進化系統(tǒng)的趨勢 芯片級f p g a 進化平臺 圖2 7 芯片級進化 但是芯片級進化系統(tǒng)在進化速度上仍然有所欠缺 如基于嵌入式c p u 實現(xiàn) 的基因算法速度問題 以及基因算法對于可重構(gòu)電路的配置速度 這些方面將在 下面詳細介紹 1 0 第2 章數(shù)字進化硬件的研究 2 3 1 基因算法 基因算法作為進化硬件的核心部分 貫穿了整個的硬件進化的流程 基因算 法是模仿生物進化機制而發(fā)展出來的集合了隨機全局搜索以及優(yōu)化的一種算法 這種算法作為一種高效搜索 全局搜索的方法 能夠在眾多的解決方案中選擇搜 索解決方案 并且自主地產(chǎn)生新的解決方案 逐次產(chǎn)生越來越接近于最優(yōu)結(jié)果的 方案 最終得到近視最優(yōu)解 當前基因算法在速度上急需優(yōu)化 至今為止已經(jīng)有眾多針對基因算法的速度 研究 如 e m a n u e l es t o m e o 針對3 輸入5 輸出的邏輯函數(shù) 2 9 1 通過調(diào)整基因算 法的參數(shù)對基因算法迭代代數(shù)改進了接近4 0 而k o n s t a n t i nm o v s o v i c 針對2 b i t 乘法器作為進化目標的變異概率進行分析 3 0 將5 0 0 0 代內(nèi)成功進化的概率提升 1 2 但是這些措施均依賴于具體的進化目標 在進化目標改變時均需要進行相 應的更改 缺乏通用性 為了更加有通用性的優(yōu)化基因算法的速度 下面將針對于基因算法流程的進行分 析 一 圖2 8 基因算法流程 如上圖2 8 所示 基本的基因算法分為以下步驟 1 初始化 在初始化的過程中通過對于隨機數(shù)的判斷 逐位得出染色體的每一 位 最終得到一個包含有多個個體的種群 第2 章數(shù)字進化硬件的研究 2 3 1 基因算法 基因算法作為進化硬件的核心部分 貫穿了整個的硬件進化的流程 基因算 法是模仿生物進化機制而發(fā)展出來的集合了隨機全局搜索以及優(yōu)化的一種算法 這種算法作為一種高效搜索 全局搜索的方法 能夠在眾多的解決方案中選擇搜 索解決方案 并且自主地產(chǎn)生新的解決方案 逐次產(chǎn)生越來越接近于最優(yōu)結(jié)果的 方案 最終得到近視最優(yōu)解 當前基因算法在速度上急需優(yōu)化 至今為止已經(jīng)有眾多針對基因算法的速度 研究 如 e m a n u e l es t o m e o 針對3 輸入5 輸出的邏輯函數(shù) 2 9 1 通過調(diào)整基因算 法的參數(shù)對基因算法迭代代數(shù)改進了接近4 0 而k o n s t a n t i nm o v s o v i c 針對2 b i t 乘法器作為進化目標的變異概率進行分析 3 0 將5 0 0 0 代內(nèi)成功進化的概率提升 1 2 但是這些措施均依賴于具體的進化目標 在進化目標改變時均需要進行相 應的更改 缺乏通用性 為了更加有通用性的優(yōu)化基因算法的速度 下面將針對于基因算法流程的進行分 析 一 圖2 8 基因算法流程 如上圖2 8 所示 基本的基因算法分為以下步驟 1 初始化 在初始化的過程中通過對于隨機數(shù)的判斷 逐位得出染色體的每一 位 最終得到一個包含有多個個體的種群 第2 章數(shù)字進化硬件的研究 2 選擇個體 在初始化完成后 基因算法從種群中選擇兩個個體作為父代染色 體 其中個體選擇是采用輪盤賭的方式 即適應度越高 被選到的幾率越大 3 基因操作 在選擇了兩個個體后 基因算法根據(jù)這兩個染色體的適應度執(zhí)行 基本的基因操作 交叉和變異操作 其中交叉操作根據(jù)當前交叉概率p 對于兩個父代染色體中的每一位生成一 個0 1 之間的隨機數(shù)m 若m p 則交叉模板中該位為1 相應的兩個父代 染色體的這一位執(zhí)行交換操作 交叉模板 玉 i 亙 i 玉 二 i 雯 圖2 9 交叉操作 變異操作根據(jù)當前變異概率q 分別針對由交叉操作產(chǎn)生的兩個染色體的每 一位生成0 1 之間的隨機數(shù)m 若m 根據(jù)染色體的配置位流對應在f p g a 中的具體位置 將f p g a 中 邏輯資源按照配置的單位劃分為多個部分 針對這些部分單獨進行 配置 在配置位流中添加針對于f p g a 中的不同部分進行部分配 置的配置命令 配置位置等信息 在染色體對應的配置位流的基礎(chǔ)上 填充原有f p g a 其他部分的 配置位流 組合成f p g a 的整體位流 即針對于f p g a 整體進行 重新配置 3 使用f p g a 支持的配置方式 根據(jù)上一步生成的配置命令和配置位流對 f p g a 進行配置 在上述流程中 我們可以看到影響配置速度的有兩個方面 a 從染色體到配置位流的轉(zhuǎn)換 b 配置方式 如 部分配置 劃分時配置的單位 以及全部配置 當前基于f p g a 的可進化硬件研究大部分是使用商用f p g a 進行的研究 由于商業(yè)限制 無法得到f p g a 的具體底層配置位流和結(jié)構(gòu) 不能自主地產(chǎn)生 和改變配置位流 必須借助于比如j b i t s i c c a p 等間接手段實現(xiàn)對f p g a 的位流 的轉(zhuǎn)換 則耗費了大量的時間來轉(zhuǎn)換和產(chǎn)生位流 如果能實現(xiàn)芯片內(nèi)部對于 f p g a 的自主配置 則可以節(jié)省上述基于j b i t s 等軟件工具所需要的時間 另一方面由于商用f p g a 在配置方式的限制 可進化硬件研究中無法針對 于底層細粒度的配置位流進行有效的部分配置 在目前主流的f p g a 廠商的產(chǎn) 品如x i n l i n x 的v i r t e x 2 v i r t e x 4 3 4 等中的f p g a 的配置部分均實現(xiàn)了以數(shù)據(jù)幀 為單元的局部配置功能 而在實際的進化流程中可重構(gòu)電路需要重新配置的部 分并不一定是完整的一個數(shù)據(jù)幀 可能是1 個數(shù)據(jù)字 3 2 位的編程點單位 甚至單獨的一個編程點 如圖所示 第2 章數(shù)字進化硬件的研究 需要修改 編程點信 圖2 1 3 可重構(gòu)電路的部分配置 在這種情況下 以一個數(shù)據(jù)幀為基本單位就不夠靈活 花費了很多時間來重新配 置一些并不需要配置的部分 急需一種更小的配置單位來實現(xiàn)更加靈活的部分配 置 從以上的分析 這兩個方面均影響了配置的速度 需要在自主配置 以及 配置單位方面來優(yōu)化進化系統(tǒng) 2 4 小結(jié) 本章介紹了數(shù)字電路的硬件進化的研究現(xiàn)況 其中包括當前的v r c 模型 以及v r c 模型的實現(xiàn)方式 并對當前v r c 模型進行了分析 其次根據(jù)當前數(shù)字 電路硬件進化的研究中的必要組成部分 基因算法 對可重構(gòu)電路的重新配置等 方面分別進行了詳細的介紹 針對于當前芯片級進化中基因算法的現(xiàn)狀提出了從 硬件角度優(yōu)化基因算法的實現(xiàn) 并且提出了從自主配置 以及部分配置兩方面優(yōu) 化芯片進化中對可重構(gòu)電路的配置過程 1 6 第3 章虛擬f p g a 結(jié)構(gòu)模型 第3 章虛擬f p g a 結(jié)構(gòu)模型 3 1 虛擬f p g a 結(jié)構(gòu)模型的研究 虛擬可重構(gòu)電路模型 vrc 一般是由兩部分組成的 基本功能單元 以及功能單元之間的互連 其中基本功能單元一般可以包含有很多種功能 可以 根據(jù)基因算法對與可重構(gòu)電路陣列的配置相應地選擇其功能 基本單元之間的互 連則在基因算法的配置下 負責連接不同的功能單元 形成一條從輸入到輸出的 數(shù)據(jù)通道 這兩部分均是v1 tc 模型的必要組成部分 缺一不可 下面將先介紹基于f p g a 的v r c 虛擬f p g a 結(jié)構(gòu)模型 的基本功能單元 的研究 對比于門級的傳統(tǒng)虛擬可重構(gòu)電路 v r c 3 5 的基本功能單元均是由基本 的邏輯門構(gòu)成的 虛擬f p g a 結(jié)構(gòu)模型的基本功能單元是由n 輸入的l u t 組成 的 其中基于f p g a 的vrc 3 6 中基本功能單元的設(shè)計主要是為了考慮在有限 的r l 輸入的情況下各種功能的實現(xiàn) 在n 變量輸入的情況下 最小項的集合包含 了所有2 2 種邏輯函數(shù) 從這個意義上講 最小項表達形式是最有效率的編碼方 式 因此在選擇可進化基本功能單元時 直接使用查找表是合理而有效率的 虛擬f p g a 結(jié)構(gòu)模型的基本陣列結(jié)構(gòu)如下圖3 1 所示 涸l 泗佃l 泗 駟i 洄 圖3 1 虛擬f p g a 結(jié)構(gòu)模型 如上圖3 1 所示 虛擬f p g a 結(jié)構(gòu)模型中 基本功能單元是n 輸入的lu t 而陣列中互連為 每一個基本單元的輸入都是上一列所有基本單元的輸出經(jīng)過選 擇器 m u x 選擇所得到的結(jié)果 這n 個的輸入端對應著n 個4 選1 的m i y x 而這r 1 個m u x 的4 個輸入端均對應上一列所有基本單元的輸出 虛擬f p g a 結(jié)構(gòu)模型研究表明 在基于以上的vrc 基本結(jié)構(gòu)下 對比于基 第3 章虛擬f p g a 結(jié)構(gòu)模型 于2 5 輸入lut 的可進化電路模型和以基本邏輯門為基本功能單元的可進 化電路模型 在以任意3 輸入到5 輸入的組合邏輯函數(shù)為進化目標時 3 輸入l ut 的可進化電路模型是最有效率的 在適應度上均優(yōu)于其他模型 其中比門級 模型平均高出8 0 3 如下圖所示 一5 0 0os o o1 0 0 01 5 0 02 0 0 02 5 0 d 3 0 0 03 5 0 04 0 0 0 4 5 0 0 時鐘屜 圖3 2 v r c 模型進化過程 上圖中橫軸為可進化系統(tǒng)運行的時間 縱軸為適應度值脯意的適應度值 由 于針對于組合邏輯的進化在2 0 萬代時就已經(jīng)能看出明顯的差異 圖中所有的 v r c 模型均停止在2 0 萬代 這些v r c 模型中 2 l u t 3 l u t 4 l u t 5 l u t 均為基于不同輸入的l u t 的虛 擬f p g a 結(jié)構(gòu)模型 而v r c l v r c 2 中互連結(jié)構(gòu)是與基于l u t 的v r c 模型相 同的 功能單元實現(xiàn)的是從八種基本門邏輯中選擇一種功能 下面分別是 v r c t 3 7 1 v r c 2 1 2 2 1 中基本功能單元包含的八種功能 v r c s 邏輯函數(shù)集合 v r c l s i n m a n 1 a a a b a l b a b v a b a 陋 v r c 2 s e k a n i n a a b a b a l b a b a b a b 表3 1v r c l 與v r c 2 的基本功能單元 3 2 虛擬f i g a 結(jié)構(gòu)模型的互連研究 在上述虛擬f p g a 結(jié)構(gòu)模型研究中 為了便于研究 互連結(jié)構(gòu)為每一個基本 單元的輸入都是上一列所有基本單元的輸出經(jīng)過選擇器 m l 選擇所得到的 結(jié)果 該模型并沒有深入的研究虛擬f p g a 結(jié)構(gòu)模型的互連情況 本文針對于vrc 模型中常見的互連結(jié)構(gòu)進行了分析 當前大部分互連 2 6 第3 章虛擬f p g a 結(jié)構(gòu)模型 分為兩種 1 固定連接型互連 2 任意連接型互連 圖3 3 固定型互連 圖3 4 任意型互連 上面兩圖分別是固定型互連和任意連接型互連的實例 其中功能單元均為l 輸入1 輸出的基本單元 在固定型互連中每一個功能單元的輸出是連接到固定的 單元上的 而任意性互連則給予了更大的自由度 每一個功能單元的輸出屬于互 連線的集合 可以連接到任意單元的輸入端 這兩種互連各有優(yōu)勢 固定性互連在染色體的復雜度上低于任意型互連 對 于基因算法來講需要搜索的解空間更小 但是能夠完成的功能受固定互連的限制 也比較少 而任意性互連由于功能上的自由性比較高 能夠完成的功能比較多 但是染色體復雜度高 基因算法中解空間大 下面我們將比較這兩種互連的優(yōu)劣 本文將依次描述不同互連的虛擬f p g a 結(jié)構(gòu)模型及包含有這些模型的完整進化平臺的實現(xiàn)和實驗 3 2 1 不同互連的虛擬f p g a 結(jié)構(gòu)模型 首先兩種互連的v r c 模型分別如下圖所示 1 9 第3 章虛擬f p g a 結(jié)構(gòu)模型 分為兩種 1 固定連接型互連 2 任意連接型互連 圖3 3 固定型互連 圖3 4 任意型互連 上面兩圖分別是固定型互連和任意連接型互連的實例 其中功能單元均為l 輸入1 輸出