面向量子可逆邏輯自動綜合的多目標進化算法研究.pdf

1、隨著科學技術和計算機產(chǎn)業(yè)的不斷發(fā)展，集成電路(Integrated Circuits，IC)正在進入以極大規(guī)模、極高密度、系統(tǒng)集成等為特征的SOC(System-on-a-chip)時代。計算機芯片的集成度正遵循著摩爾定律(Moore's Law)不斷地提高，更快、更小、更復雜的系統(tǒng)級芯片已經(jīng)開始量產(chǎn)。若摩爾定律繼續(xù)適用，計算機芯片的線寬將很快達到原子水平。集成度的提高可使計算機的性能得到大幅提升，但也不可避免的導致以下兩大問題:第一，

2、隨著時鐘頻率的增加和封裝在芯片中晶體管數(shù)目的增多，計算機芯片的能耗將不斷增大，發(fā)熱成為一大難題;第二，隨著計算機制程的不斷發(fā)展，晶體二極管的尺寸將達到原子水平，而由于電子的“波粒二象性”使其顯現(xiàn)出量子效應，導致經(jīng)典物理定律失效的窘境。上述問題是IC發(fā)展所面臨的共性問題，它們也都清楚地表明，現(xiàn)行的計算機制造方法在提高集成度方面已顯得越來越力不從心。
　　 可逆邏輯電路(Reversible Logic Circuits)以可逆方式

3、進行邏輯運算、不丟失輸入信息，是一種可避免信息損失和相應能量損耗的新型電路，因而可有效降低能耗甚至達到零損耗，使其成為未來進一步降低IC功耗的必由之路。同時，量子計算機遵循量子力學規(guī)律，天生服從量子物理定律?？衫昧孔舆壿嬮T級聯(lián)( Cascade)實現(xiàn)不存在熱耗散且滿足指定可逆操作的量子電路，進而構成計算能力較經(jīng)典計算機有巨大提高的量子計算機，因此可逆計算是量子計算(Quantum Computing)的核心問題，可逆邏輯電路以量子實現(xiàn)

4、形式為佳，而可逆邏輯綜合(Synthesis of Reversible Logic)則是實現(xiàn)量子計算機的關鍵技術。綜上所述，可逆性將成為未來電路設計的基本要求，基于量子實現(xiàn)的可逆邏輯電路將成為進一步降低IC功耗的重要手段，是實現(xiàn)量子計算機的必備條件。因此，研究和解決量子可逆邏輯綜合問題將有望推動超低功耗IC設計和量子計算（機）等相關領域的發(fā)展，因而成為了國際性的研究熱點。
　　 由于量子可逆邏輯電路和常見的不可逆電路存在較大差

5、異，因此其綜合方法截然不同于現(xiàn)行的非可逆邏輯電路，生成與優(yōu)化的難度均更大。目前常規(guī)的量子可逆邏輯綜合方法普遍不夠成熟、自動化程度不高以及缺乏實用性，究其原因主要是由于量子可逆邏輯綜合實際上是一種帶有強約束且缺乏領域知識的多目標優(yōu)化問題(Multi-objective Optimization Problems)。如何顯著地提高量子可逆邏輯綜合的速度、規(guī)模、自動化和實用化程度等，目前仍是極具挑戰(zhàn)的開放性問題。而進化設計(Evolution

6、ary Design)是利用進化計算(Evolutionary Computation)的高效自動求解能力，尋求不依賴于先驗知識和人工干預，通過人工進化(Artificial Evolution)來獲得具備預期功能的設計結果，故可探索更為廣闊的設計空間，解決常規(guī)方法因知識、經(jīng)驗缺乏而無法勝任的復雜問題，實現(xiàn)相關系統(tǒng)的自動設計，因此進化設計是解決量子可逆邏輯綜合復雜性問題的有效途徑。
　　 本文在系統(tǒng)地論述量子可逆邏輯綜合的基本原

7、理、技術特點和研究現(xiàn)狀的基礎上，將進化設計技術應用于量子可逆邏輯綜合，以提高綜合水平和實用化程度為目標，尋求以較少的運算量和人工參與，可自動地生成和優(yōu)化量子可逆邏輯電路的自動綜合方法。主要從進化算法、編解碼方案、多目標評估方法和自動化簡與修復策略等方面入手，對有關設計理論和實驗方法進行了較為全面和深入的研究，獲得了一些關鍵性的研究成果，可主要概括為以下幾個方面:
　　 (1)通過討論進化算法的分類和特點，為克服現(xiàn)有遺傳算法存在的

8、局部搜索能力差、早熟收斂、隨機漫游以及最終解精度不高等主要缺陷，詳細地討論了通過引入有性繁殖、Baldwin效應以及自適應機制來提高進化速度和收斂概率的生物學機理與一般方法，并針對量子可逆邏輯自動綜合的特點，提出了一種基于Baldwin效應的自適應有性繁殖混合遺傳算法(BSAGA)，并對算法進行了收斂性分析。
　　 (2)在分析和比較已有算法的基礎上，根據(jù)量子可逆邏輯自動綜合的進化設計需要，研究了一種基于進化計算新的重要分支——

9、差分進化(DifferentialEvolution)的自適應離散差分進化策略，并結合Pareto快速分層排序策略和基于聚集密度的按層修剪操作，提出了一種基于Pareto最優(yōu)的多目標自適應離散差分進化算法( MDDE)，其特點是利用差分進化增強算法的全局搜索能力以獲得更優(yōu)的Pareto近似解，利用Pareto快速分層排序策略和基于聚集密度的按層修剪操作對進化種群進行更新與維護以保持Pareto解集的良好分布性與多樣性。
　　 (

10、3)根據(jù)文獻資料和相關仿真結果，分析、比較常用的量子邏輯門，從中選取最為適用者，構建了用于可逆邏輯自動綜合的通用且完備的量子邏輯門級器件庫——NCT庫?；谏鲜銎骷?，研究了支持量子可逆邏輯電路結構自動生成的高效編解碼方案（即:基于量子可逆邏輯門級進化陣列模型的網(wǎng)表級編碼方案）、實用的綜合子目標、高效的適應度評估方法（包括:多目標動態(tài)評估方法和基于Pareto最優(yōu)的評估方法）以及自動化簡與修復策略（即:“前位優(yōu)先”修復機制和基于知識的局

11、部轉換策略）等。
　　 (4)面向量子可逆邏輯自動綜合問題，分別以基于Baldwin效應的自適應有性繁殖混合遺傳算法(BSAGA)和基于Pareto最優(yōu)的多目標自適應離散差分進化算法( MDDE)為進化設計的基礎，同時兼顧功能、實現(xiàn)代價和資源利用率等多個綜合目標，并結合上述編解碼方案、評估方法和自動化簡與修復策略，提出并研究了兩種量子可逆邏輯自動綜合方法:基于動態(tài)多目標評估的量子可逆邏輯自動綜合方法、基于Pareto最優(yōu)的多目標