面向量子可逆邏輯自動(dòng)綜合的多目標(biāo)進(jìn)化算法研究.pdf

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

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

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

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

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

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

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

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

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

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

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