VLST-CAD中圖形處理算法及其固化技術(shù)研究

本課題研究版圖驗(yàn)證（以DRC為例）的一些主要算法的固化。包括數(shù)據(jù)排隊(duì)算法和圖形的各種邏輯操作算法。主要?jiǎng)?chuàng)新是這些算法用硬件實(shí)現(xiàn)（即所謂固化），這類專用硬件作為主機(jī)的協(xié)處理器工作，本課題所用的硬件是FPGA實(shí)際的結(jié)果表明算法固化后的運(yùn)算速度對(duì)數(shù)據(jù)排隊(duì)算法比軟件實(shí)現(xiàn)快25倍，對(duì)于邏輯操作算法（用線掃描法）固化后的速度比軟件實(shí)現(xiàn)快50倍，其結(jié)果使版圖驗(yàn)證速度大提高，也即可以驗(yàn)證規(guī)模更大的VLS版圖。此外本課題尚做了連機(jī)DRC的系統(tǒng)開發(fā)，該系統(tǒng)做到版圖輸入后能即時(shí)進(jìn)行DRC檢查。 2100433B

DFSA算法可采用各種方法預(yù)測(cè)待識(shí)別的標(biāo)簽數(shù)量，然后動(dòng)態(tài)調(diào)整最優(yōu)幀長(zhǎng)，與FSA相比，系統(tǒng)效率有明顯改善，接近36．8%。但是，當(dāng)標(biāo)簽數(shù)量較多（特別是標(biāo)簽數(shù)量大于500）時(shí)，采用由預(yù)測(cè)標(biāo)簽數(shù)量設(shè)置最優(yōu)幀長(zhǎng)的方案會(huì)使系統(tǒng)效率急劇下降。因此，在標(biāo)簽數(shù)量較多的情況下，為了使系統(tǒng)效率得到提高，EPCClass1Gen2標(biāo)準(zhǔn)中采用了Q值算法，該算法可以實(shí)時(shí)自適應(yīng)地調(diào)整幀長(zhǎng) 。

Q值算法

在Q值算法中，閱讀器首先發(fā)送Query命令，該命令中含有一個(gè)參數(shù)Q（取值范圍0～15），接收到命令的標(biāo)簽可在[0，2Q－1]范圍內(nèi)（稱為幀長(zhǎng)）隨機(jī)選擇時(shí)隙，并將選擇的值存入標(biāo)簽的時(shí)隙計(jì)數(shù)器中，只有計(jì)數(shù)器為0的標(biāo)簽才能響應(yīng)，其余標(biāo)簽保持沉默狀態(tài)。當(dāng)標(biāo)簽接收到閱讀器發(fā)送的QueryRep命令時(shí)，將其時(shí)隙計(jì)數(shù)器減1，若減為0，則給閱讀器發(fā)送一個(gè)應(yīng)答信號(hào)。標(biāo)簽被成功識(shí)別后，退出這輪盤存。當(dāng)有兩個(gè)以上標(biāo)簽的計(jì)數(shù)器都為0時(shí)，它們會(huì)同時(shí)對(duì)閱讀器進(jìn)行應(yīng)答，造成碰撞。閱讀器檢測(cè)到碰撞后，發(fā)出指令將產(chǎn)生碰撞的標(biāo)簽時(shí)隙計(jì)數(shù)器設(shè)為最大值（2Q－1），繼續(xù)留在這一輪盤存周期中，系統(tǒng)繼續(xù)盤存直到所有標(biāo)簽都被查詢過，然后閱讀器發(fā)送重置命令，使碰撞過的標(biāo)簽生成新的隨機(jī)數(shù) 。

根據(jù)上一輪識(shí)別的情況，閱讀器發(fā)送Query－Adjust命令來調(diào)整Q的值，當(dāng)標(biāo)簽接收到Query－Adjust命令時(shí)，先更新Q值，然后在[0，2Q－1]范圍內(nèi)選擇隨機(jī)值。EPCClass1Gen2標(biāo)準(zhǔn)中提供了一種參考算法來確定Q值的范圍.其中：Qfp為浮點(diǎn)數(shù)，其初值一般設(shè)為4．0，對(duì)Qfp四舍五入取整后得到的值即為Q；C為調(diào)整步長(zhǎng)，其典型取值范圍是0．1

該算法在參數(shù)C的輔助下對(duì)Q值進(jìn)行動(dòng)態(tài)調(diào)整，但是C太大會(huì)造成Q值變化過于頻繁，導(dǎo)致幀長(zhǎng)調(diào)整過于頻繁，C太小又不能快速地實(shí)現(xiàn)最優(yōu)幀長(zhǎng)的選擇。因此，研究者們對(duì)Q值的調(diào)整進(jìn)行了各種優(yōu)化 。

基于最大吞吐量調(diào)整Q值的算法

文獻(xiàn)提出一種基于最大吞吐量對(duì)Q值進(jìn)行調(diào)整的算法，其中定義了以下變量：Nt為已識(shí)別的標(biāo)簽個(gè)數(shù)；N為識(shí)別標(biāo)簽所需的總時(shí)隙數(shù)；NC為沖突時(shí)隙的個(gè)數(shù)；nu為上一輪未識(shí)別的標(biāo)簽個(gè)數(shù)；e為沖突時(shí)隙中的平均標(biāo)簽個(gè)數(shù)；PC為沖突時(shí)隙所占的比例 。

這些參數(shù)之間的關(guān)系為PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由于Aloha類算法的最大吞吐量為0．368（e－1）[5]，該算法以此作為調(diào)整Q值的依據(jù)。當(dāng)系統(tǒng)吞吐量達(dá)到或接近0．368時(shí)，閱讀器僅需調(diào)用2Q－1次QueryRep命令，而不需要在接下來的盤存周期中調(diào)整Q值。當(dāng)吞吐量小于0．368時(shí)，根據(jù)未識(shí)別的標(biāo)簽個(gè)數(shù)nu來調(diào)整Q值 .

基于分組的位隙Aloha算法

文獻(xiàn)提出一種基于分組的位隙Aloha算法，該算法采用位隙Aloha算法中的128位預(yù)定序列，代表128個(gè)位隙。若某個(gè)標(biāo)簽選擇了第i個(gè)位隙，則將第i位置1，其余各位都置0。當(dāng)標(biāo)簽數(shù)量為15時(shí)，位隙Aloha算法可獲得最大吞吐率88．38%，但隨著標(biāo)簽數(shù)量的增加，算法性能急劇下降 。

因此，基于分組的位隙Aloha算法通過對(duì)標(biāo)簽進(jìn)行分組來提高算法的性能。該算法在查詢命令中設(shè)置了一個(gè)位隙計(jì)數(shù)器的參數(shù)Q（Q為整數(shù)，且0≤Q≤15），當(dāng)標(biāo)簽收到閱讀器發(fā)送的查詢命令后，在[0，2Q－1]范圍內(nèi)生成一個(gè)隨機(jī)數(shù)，即代表選擇了相應(yīng)的位隙，只有選擇了0的標(biāo)簽才會(huì)立即響應(yīng)。同時(shí)，該算法根據(jù)沖突位隙數(shù)動(dòng)態(tài)地對(duì)Q值進(jìn)行調(diào)整：當(dāng)沖突位隙數(shù)小于11時(shí)，Q減1且最小為0；當(dāng)沖突位隙數(shù)在11～20之間時(shí)，Q保持不變；當(dāng)沖突位隙數(shù)大于20時(shí)，Q加1且最大不超過15 。

綜上所述，基于Aloha的防碰撞算法原理簡(jiǎn)單、容易實(shí)現(xiàn)，對(duì)新到達(dá)的標(biāo)簽具有較好的適應(yīng)性，尤其對(duì)于標(biāo)簽持續(xù)到達(dá)的情況有較好的解決方案，但該類算法存在幾個(gè)明顯的缺點(diǎn)：①響應(yīng)時(shí)間不確定，即同一批標(biāo)簽在不同時(shí)刻進(jìn)行識(shí)別所需要消耗的時(shí)間相差很大；②個(gè)別標(biāo)簽可能永遠(yuǎn)無法被識(shí)別；③Aloha算法達(dá)到最佳吞吐率的條件是其幀長(zhǎng)等于標(biāo)簽數(shù)量，當(dāng)需要識(shí)別的標(biāo)簽數(shù)量較多或選擇的幀長(zhǎng)與實(shí)際待識(shí)別標(biāo)簽數(shù)量不符時(shí)，系統(tǒng)性能將明顯下降。而基于樹的算法則很好地解決了這些問題 。

《智能控制算法及其應(yīng)用》主要介紹各種典型智能控制算法的基本內(nèi)容、設(shè)計(jì)與實(shí)現(xiàn)方法及其在函數(shù)優(yōu)化、電力系統(tǒng)中的應(yīng)用。《智能控制算法及其應(yīng)用》首先闡述智能、智能控制的基本概念，介紹智能控制與傳統(tǒng)的經(jīng)典控制理論、現(xiàn)代控制理論的聯(lián)系和區(qū)別。然后從四種典型智能控制算法（專家系統(tǒng)、模糊控制、神經(jīng)網(wǎng)絡(luò)和進(jìn)化計(jì)算）入手分別闡述它們的發(fā)展歷史、基本內(nèi)容、實(shí)現(xiàn)方法及其應(yīng)用。最后介紹混沌模擬退火動(dòng)態(tài)煙花優(yōu)化算法，并將其用于優(yōu)化離散時(shí)間微分平坦自抗擾控制律的參數(shù)，通過計(jì)算機(jī)仿真和基于智能優(yōu)化算法試驗(yàn)平臺(tái)開展試驗(yàn)以驗(yàn)證該算法的有效性；介紹遞減步長(zhǎng)果蠅優(yōu)化算法，并將其應(yīng)用于風(fēng)電機(jī)組齒輪箱的故障診斷；介紹云粒子群布谷鳥融合算法，通過聯(lián)合循環(huán)發(fā)電機(jī)組典型熱工過程模型參數(shù)辨識(shí)實(shí)例驗(yàn)證該算法的有效性。

《分布并行圖形繪制技術(shù)及其應(yīng)用》系統(tǒng)深入地介紹了分布并行圖形繪制的基礎(chǔ)知識(shí)、體系結(jié)構(gòu)和多種繪制加速算法以及典型的應(yīng)用系統(tǒng)，分為基礎(chǔ)篇、技術(shù)篇和應(yīng)用篇，共15章的內(nèi)容?！斗植疾⑿袌D形繪制技術(shù)及其應(yīng)用》可作為并行圖形繪制、分布式虛擬現(xiàn)實(shí)、高性能圖形繪制等方向的研究生教材以及技術(shù)參考書，同時(shí)可供研究并行繪制技術(shù)和分布式虛擬現(xiàn)實(shí)技術(shù)的師生和從事高性能圖形繪制技術(shù)的研發(fā)人員參考。