基于字級(jí)求解的電路錯(cuò)誤自動(dòng)定位方法研究

針對(duì)VLSI芯片的設(shè)計(jì)與驗(yàn)證流程中，診斷與定位錯(cuò)誤依賴于手工勞動(dòng)且效率低下的問(wèn)題，項(xiàng)目重點(diǎn)研究如何自動(dòng)、高效地定位RTL級(jí)和行為級(jí)電路描述中的錯(cuò)誤，通過(guò)設(shè)計(jì)與實(shí)現(xiàn)一系列形式化方法與技術(shù)，大大提高錯(cuò)誤定位的效率與精度，從而加速芯片的設(shè)計(jì)與驗(yàn)證流程。項(xiàng)目的主要研究成果包括： （1）針對(duì)近年來(lái)出現(xiàn)的許多電路錯(cuò)誤定位方法，深入研究與分析了基于位級(jí)與字級(jí)的錯(cuò)誤定位方法的基本原理，并對(duì)各種算法進(jìn)行了評(píng)估與分析；并針對(duì)不可滿足子式能夠顯著提高錯(cuò)誤定位效率與精度進(jìn)行了深入分析。 （2）針對(duì)求解不可滿足子式可以顯著提高電路定位錯(cuò)誤的效率，提出了悖論證明與悖論解析樹(shù)的概念，并提出一種啟發(fā)式局部搜索算法，從布爾公式的悖論證明中求解不可滿足子式?；趯?shí)際測(cè)試集進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明該算法優(yōu)于同類最優(yōu)算法。 （3）針對(duì)布爾不可滿足子式能夠幫助自動(dòng)化工具迅速定位電路錯(cuò)誤，提出了求解布爾不可滿足子式的消解悖論算法。它屬于一種非完全算法，對(duì)于業(yè)界常見(jiàn)的3-SAT和2-SAT問(wèn)題非常高效?；陔S機(jī)測(cè)試集進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明消解悖論算法優(yōu)于其他同類算法。 （4）隨著硬件設(shè)計(jì)與驗(yàn)證的抽象層次越來(lái)越高，基于一階邏輯的可滿足性模逐漸成為研究熱點(diǎn)。針對(duì)極小可滿足性模的不可滿足子式的求解問(wèn)題，提出了基于深度優(yōu)先搜索與增量式求解的算法。與目前最優(yōu)算法對(duì)比，該算法能夠有效地求解極小不可滿足子式，并且隨著公式的規(guī)模增大，算法更加高效。 （5）高速緩沖存儲(chǔ)器（Cache）的錯(cuò)誤定位是驗(yàn)證領(lǐng)域的研究熱點(diǎn)與難點(diǎn)，對(duì)此提出了一種面向Cache的可綜合偽隨機(jī)驗(yàn)證與錯(cuò)誤定位方法。與業(yè)界常用的方法對(duì)比，該方法的處理速度快約3個(gè)數(shù)量級(jí)，并且能夠精確地定位更多的功能錯(cuò)誤。 （6）謂詞抽象技術(shù)是解決錯(cuò)誤定位中狀態(tài)空間組合爆炸問(wèn)題的重要途徑，而不可滿足子式能夠減少謂詞抽象過(guò)程中精化迭代的次數(shù)。因此將兩種最小不可滿足子式的求解算法進(jìn)行了集成與對(duì)比，并深入分析了不可滿足子式在硬件謂詞抽象中的作用，以及如何加速電路的錯(cuò)誤定位過(guò)程。

隨著VLSI芯片功能越來(lái)越復(fù)雜，大量的時(shí)間消耗在功能驗(yàn)證上，而目前錯(cuò)誤定位仍主要依賴于手工勞動(dòng)，效率低下且易于引入新的錯(cuò)誤，因此錯(cuò)誤自動(dòng)定位方法成為新的研究熱點(diǎn)。但是現(xiàn)有方法存在抽象層次低、運(yùn)算復(fù)雜度高、處理電路規(guī)模有限等問(wèn)題。.針對(duì)這些問(wèn)題，研究基于字級(jí)求解的電路錯(cuò)誤自動(dòng)定位理論與方法；研究基于約束依賴圖的高層HDL程序切片算法，以抽取有效電路；研究基于等價(jià)約簡(jiǎn)與蘊(yùn)含消除的斷言精化方法，以減小斷言規(guī)模；研究融合字級(jí)不可滿足子式與Craig插值的錯(cuò)誤蹤跡優(yōu)化方法，以提高定位精度；研究基于否證分析與增量式求解的錯(cuò)誤敏感向量壓縮方法，以剔除冗余輸入；面向RTL級(jí)和行為級(jí)電路描述，設(shè)計(jì)實(shí)現(xiàn)錯(cuò)誤自動(dòng)定位的原型系統(tǒng)。.本項(xiàng)目的研究成果，能夠顯著提高VLSI芯片驗(yàn)證的效率，有助于縮短設(shè)計(jì)周期，突破制約芯片驗(yàn)證的瓶頸，具有重要理論意義與實(shí)際應(yīng)用價(jià)值。

1、捕獲型錯(cuò)誤：我們?cè)噲D偏離熟悉環(huán)境中的常規(guī)活動(dòng)，但在應(yīng)當(dāng)偏離的那一點(diǎn)上我們沒(méi)能注意并進(jìn)行控制加工，因此，自動(dòng)加工捕獲了行為，我們最終沒(méi)能夠偏離常規(guī)。

2、忽略型錯(cuò)誤：例行活動(dòng)的中斷可能會(huì)使我們跳過(guò)一兩步來(lái)執(zhí)行余下部分。

3、固著型錯(cuò)誤：自動(dòng)加工步驟完成之后，一個(gè)或幾個(gè)步驟可能被重復(fù)。

4、描述性錯(cuò)誤：所意圖的行為的內(nèi)部描述導(dǎo)致在錯(cuò)誤的對(duì)象上執(zhí)行正確的行動(dòng)。

5、數(shù)據(jù)驅(qū)動(dòng)錯(cuò)誤：面前涌入的感覺(jué)信息在自動(dòng)行動(dòng)序列中干擾了意圖變量。

6、聯(lián)想激活錯(cuò)誤：強(qiáng)烈的聯(lián)想可能引發(fā)錯(cuò)誤的自動(dòng)加工。

7、例行任務(wù)的激活不足以徹底完成該任務(wù)。2100433B

基于物理模型的三維織物模擬引擎，是三維動(dòng)畫、服裝CAD試衣模塊的基礎(chǔ)關(guān)鍵性研究。由于織物的大變形和服裝材料屬性，需要力學(xué)、科學(xué)計(jì)算、藝術(shù)等多方面知識(shí)，使其有深度的交叉學(xué)科。本項(xiàng)目針對(duì)模擬引擎中屈曲（褶皺產(chǎn)生過(guò)程），動(dòng)態(tài)碰撞處理，高性能求解計(jì)算等模擬引擎的關(guān)鍵問(wèn)題進(jìn)行研究。通過(guò)能量準(zhǔn)則和質(zhì)量矩陣約束方法獲得屈曲過(guò)程，從而可以構(gòu)建具有理論依據(jù)的褶皺形成過(guò)程。采用結(jié)合稀疏矩陣求解器的隱式碰撞處理來(lái)解決服裝的大規(guī)模碰撞問(wèn)題，將檢測(cè)到的碰撞采用全局方式加入隱式方程，而不是傳統(tǒng)的局部響應(yīng)方程。采用并行化方法，結(jié)合稀疏矩陣求解器進(jìn)行研究，從而解決阻礙大規(guī)模應(yīng)用的根本效率問(wèn)題。深入探索新型無(wú)網(wǎng)格模型布類的模擬，加強(qiáng)真實(shí)感。本研究可以為解決當(dāng)前三維服裝動(dòng)畫效果僵硬以及三維服裝CAD的真實(shí)感試衣到虛擬服裝展示中最有難度的問(wèn)題提供新方法和理論依據(jù)，促進(jìn)三維原創(chuàng)動(dòng)畫發(fā)展和中國(guó)傳統(tǒng)服裝行業(yè)信息化進(jìn)程。

室內(nèi)定位技術(shù)的研究發(fā)展近年來(lái)呈現(xiàn)出“定位更精準(zhǔn)”與“部署更簡(jiǎn)單”的趨勢(shì)。從“定位更精準(zhǔn)”角度進(jìn)行的技術(shù)研究已經(jīng)較為成熟；而從“部署更簡(jiǎn)單”角度進(jìn)行的技術(shù)研究才剛剛起步。現(xiàn)有室內(nèi)定位技術(shù)往往對(duì)定位精準(zhǔn)度給予了足夠的關(guān)注，然而僅有部分近期的工作研究如何降低系統(tǒng)開(kāi)銷，更鮮有工作能夠系統(tǒng)性地在兩者間進(jìn)行權(quán)衡。在很多現(xiàn)實(shí)生活的應(yīng)用場(chǎng)景，現(xiàn)有室內(nèi)定位系統(tǒng)的部署代價(jià)仍然過(guò)高而難以適用。本項(xiàng)目針對(duì)低代價(jià)的室內(nèi)定位該較新的研究領(lǐng)域中亟需解決的理論和關(guān)鍵技術(shù)問(wèn)題，研究基于WiFi 環(huán)境的用戶自激發(fā)式弱定位方法、與結(jié)合傳感器信息的用戶自激發(fā)式若定位優(yōu)化方法。現(xiàn)有的室內(nèi)定位指紋技術(shù)，為現(xiàn)有的WLAN基礎(chǔ)設(shè)施提供了增值的本地化服務(wù)，而不需要任何專門的硬件?；谥讣y定位系統(tǒng)的部署需要對(duì)接收到的信號(hào)強(qiáng)度信息進(jìn)行大量的測(cè)量，以生成位置指紋數(shù)據(jù)庫(kù)。然而，這一要求在大多數(shù)室內(nèi)環(huán)境中很少能得到滿足。在這個(gè)項(xiàng)目中，我們針對(duì)上述普遍存在的問(wèn)題，即當(dāng)收集到的測(cè)量信號(hào)強(qiáng)度信息不足時(shí)，論證了現(xiàn)有的位置指紋方法在處理不足的位置指紋的局限性。本項(xiàng)目研究了一種基于最大似然估計(jì)的接收信號(hào)強(qiáng)度測(cè)量中降低噪聲的新方法，并利用隨機(jī)梯度下降算法計(jì)算位置指紋不足的位置。實(shí)驗(yàn)結(jié)果表明，即使只有少量的RSS測(cè)量數(shù)據(jù)，該方法也能獲得較好的定位性能。特別是當(dāng)每個(gè)位置的觀測(cè)值較少時(shí)，該方法在定位精度上具有明顯的優(yōu)越性。現(xiàn)有的室內(nèi)導(dǎo)航系統(tǒng)，大部分依賴于足夠的無(wú)線信號(hào)和信號(hào)源。盡管如此，部署這樣一個(gè)系統(tǒng)需要定期進(jìn)行現(xiàn)場(chǎng)調(diào)查，這是一項(xiàng)耗時(shí)和勞動(dòng)密集的工作。為了解決這個(gè)問(wèn)題，在這個(gè)項(xiàng)目中，我們提出了“獨(dú)木舟”（Canoe），一個(gè)考慮購(gòu)物中心場(chǎng)景的室內(nèi)導(dǎo)航系統(tǒng)。在Canoe系統(tǒng)中，我們不假設(shè)任何先驗(yàn)知識(shí)，例如樓層平面圖或店鋪位置、接入點(diǎn)位置或電源設(shè)置、歷史RSS測(cè)量或指紋等，Canoe只要求店主在其店鋪的入口處收集并發(fā)布RSS值，并且可以通過(guò)比較觀察到的RSS值將消費(fèi)者引導(dǎo)到這些店鋪中的任何一個(gè)。消費(fèi)者和商店的位置估計(jì)最大似然估計(jì)。這樣，可以精確計(jì)算目標(biāo)商店相對(duì)于消費(fèi)者當(dāng)前方向的方向，從而確定消費(fèi)者應(yīng)該移動(dòng)的方向。我們使用真實(shí)世界的數(shù)據(jù)集進(jìn)行了廣泛的模擬。我們?cè)谝粋€(gè)真實(shí)的購(gòu)物中心進(jìn)行的實(shí)驗(yàn)表明，如果50%的商店發(fā)布RSS值，Canoe可以在30秒內(nèi)精確地導(dǎo)航消費(fèi)者，錯(cuò)誤率低于9%。 2100433B