• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線新算法

    2014-08-05 04:28:46廖海濤
    計(jì)算機(jī)工程 2014年5期
    關(guān)鍵詞:端點(diǎn)布線迷宮

    廖海濤,史 崢,張 騰

    (浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所,杭州 310027)

    基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線新算法

    廖海濤,史 崢,張 騰

    (浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所,杭州 310027)

    在超大規(guī)模集成電路設(shè)計(jì)中,全局布線是非常重要的步驟。工業(yè)界普遍采用經(jīng)典的迷宮算法及其改進(jìn)算法解決全局布線問題。隨著工藝節(jié)點(diǎn)的減小,傳統(tǒng)迷宮算法復(fù)雜度高的缺點(diǎn)越來越明顯。針對(duì)傳統(tǒng)迷宮算法的復(fù)雜度會(huì)隨著布線規(guī)模的擴(kuò)大而迅速增加的問題,借助于邊界擴(kuò)張的概念,提出一種新的點(diǎn)對(duì)點(diǎn)布線路徑的搜索算法。摒棄了迷宮算法低效率的逐個(gè)節(jié)點(diǎn)擴(kuò)張的思想,通過自由節(jié)點(diǎn)的定義對(duì)節(jié)點(diǎn)邊界進(jìn)行迅速擴(kuò)張并不斷地找到新的自由節(jié)點(diǎn),直到找出路徑或確定無解時(shí)結(jié)束。將該算法與經(jīng)典的布線算法進(jìn)行理論和實(shí)驗(yàn)比較,結(jié)果表明在大多數(shù)情況下該算法使用經(jīng)典算法7%~14%的運(yùn)行時(shí)間即可完成路徑搜索。

    超大規(guī)模集成電路;全局布線;迷宮算法;點(diǎn)對(duì)點(diǎn)布線;邊界擴(kuò)張;自由節(jié)點(diǎn)

    1 概述

    全局布線是物理設(shè)計(jì)中布局之后的重要步驟,布局確定了模塊在芯片上的位置以及模塊上各引腳的分布,并通過網(wǎng)表提供了各引腳間的互連信息。布線過程就是實(shí)現(xiàn)各模塊間的連接。全局布線作為布線過程的第一步,目的就是把每條線網(wǎng)的各個(gè)部分合理地分配到各個(gè)布線通道中去,為之后的詳細(xì)布線提供初始布線走向,這一階段布線結(jié)構(gòu)的好壞決定芯片的整體性能。

    現(xiàn)有超大規(guī)模集成(Very Large Scale Inte grated, VLSI)電路計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)大多是基于統(tǒng)一標(biāo)準(zhǔn)的網(wǎng)格模型。這種模型的布線算法大致分為2類:迷宮算法和線搜索算法[1]。迷宮算法常見的是窮舉回溯的深度優(yōu)先搜索方法和層層推進(jìn)式的廣度優(yōu)先搜索方法。文獻(xiàn)[2]算法作為最原始的迷宮算法,采用的就是廣度優(yōu)先搜索方法。這類算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單,并且總能夠保證找到最短路徑,而缺點(diǎn)在于其時(shí)間和空間復(fù)雜度都比較高[3]。為了降低復(fù)雜度,出現(xiàn)了許多改進(jìn)版本[4-6],其中,A*[6]算法是目前工業(yè)界普遍使用的啟發(fā)式搜索算法,它通過選擇合適的啟發(fā)函數(shù),使其尋找最優(yōu)路徑的搜索范圍比原始算法更小。國內(nèi)關(guān)于迷宮算法的研究[7-9]主要是針對(duì)原始迷宮算法加入啟發(fā)條件來改進(jìn)搜索效率。這些改進(jìn)算法并沒有改變傳統(tǒng)迷宮算法逐個(gè)節(jié)點(diǎn)的搜索方式,只是通過加入啟發(fā)條件來縮小搜索范圍,并沒有從根本上改變迷宮算法的復(fù)雜度。

    為擺脫逐個(gè)節(jié)點(diǎn)搜索的限制,人們提出了線搜索算法?;舅枷胧菢?gòu)造一個(gè)比原始網(wǎng)格更加稀疏的子圖,通過在子圖中尋找最短路徑得到原格點(diǎn)中的路徑。較早的線搜索算法[10]被提出后,又有學(xué)者引入了新的連接圖來代替原始網(wǎng)格[11-12],甚至有學(xué)者引入了一種新的迷宮驅(qū)動(dòng)型線搜索算法[13]。這些算法在理論上都比原始的迷宮算法復(fù)雜度要低,然而實(shí)際應(yīng)用中由于集成電路規(guī)模巨大,構(gòu)造這種子圖的時(shí)間代價(jià)往往非常大,因此這類算法并沒有被普遍采用,而只是在設(shè)計(jì)初期障礙數(shù)目較少時(shí)使用;此外一些線搜索算法甚至還無法保證搜索到布線路徑,即使這條路徑的確是存在的。國內(nèi)學(xué)者受到線搜索法的啟發(fā)也相應(yīng)提出用于VLSI二維布線的新方法[14],也有學(xué)者將線搜索法與迷宮算法結(jié)合并將其應(yīng)用于三維電氣網(wǎng)絡(luò)的自動(dòng)布線中[15]。

    本文提出一種新的算法,與線搜索算法類似,沒有使用逐個(gè)節(jié)點(diǎn)擴(kuò)散的搜索方式,而是給出了一種新的搜索方式。

    2 基本概念和定義

    2.1 網(wǎng)格模型

    一般來講,全局布線問題可以建模為一個(gè)網(wǎng)格圖G=(V, E),如圖1所示,圖中位于每個(gè)網(wǎng)格中心的點(diǎn)(用黑色圓點(diǎn)表示)V( vi, vj)={(vi, vj)|0≤i<m∩0≤j<n}就對(duì)應(yīng)代表了這個(gè)網(wǎng)格,而兩點(diǎn)之間的虛線則對(duì)應(yīng)代表了2個(gè)網(wǎng)格之間所夾的邊緣。

    圖1 劃分成m×n的版圖和與之對(duì)應(yīng)的網(wǎng)格模型

    2.2 自由節(jié)點(diǎn)的邊界

    定義1(自由節(jié)點(diǎn)的邊和邊界) 如圖2所示,假設(shè)點(diǎn)A為自由節(jié)點(diǎn),以A為原點(diǎn)向4個(gè)方向作垂線,遇到第1個(gè)障礙物時(shí)到達(dá)的節(jié)點(diǎn)為垂足,則與每條垂線垂直且經(jīng)過對(duì)應(yīng)垂足點(diǎn)的連續(xù)障礙節(jié)點(diǎn)構(gòu)成的線段稱為節(jié)點(diǎn)在該方向上的一條邊;以這4條邊確定的矩形區(qū)域稱為自由節(jié)點(diǎn)A的邊界。圖2中的加粗實(shí)線表示自由節(jié)點(diǎn)的邊界,加粗虛線表示自由節(jié)點(diǎn)到相應(yīng)方向邊上的垂線。

    定義2(節(jié)點(diǎn)相對(duì)于邊界的內(nèi)與外) 是指該節(jié)點(diǎn)與另外某節(jié)點(diǎn)邊界的相對(duì)位置。如圖2所示,P1位于A點(diǎn)的邊界內(nèi)部,而P2與P3位于A點(diǎn)的邊界外部。

    圖2 自由節(jié)點(diǎn)A的邊界示意圖

    2.3 閉合邊、半開放邊與開放邊

    定義3(閉合邊、半開放邊與開放邊) 本文提到的3種邊都是相對(duì)于某個(gè)節(jié)點(diǎn)而言的,同樣提到某條邊是閉合或者開放時(shí),也是相對(duì)于某個(gè)確定節(jié)點(diǎn)而言的。圖3中點(diǎn)A的右側(cè)邊與點(diǎn)B的左側(cè)邊均為邊CD,但是C點(diǎn)左側(cè)有障礙點(diǎn)存在,形成一個(gè)向左下方向的直角(如圖中C點(diǎn)區(qū)域內(nèi)的拐角線標(biāo)注)這2條以點(diǎn)C為端點(diǎn)和射線構(gòu)成的區(qū)域把點(diǎn)A包含在內(nèi),因此定義邊CD的上部端點(diǎn)C相對(duì)于點(diǎn)A來說是閉合的,但是相對(duì)于點(diǎn)B是開放的;同理邊CD的下部端點(diǎn)D相對(duì)于點(diǎn)A是開放的,但相對(duì)于點(diǎn)B卻是閉合的。然而無論是對(duì)點(diǎn)A還是點(diǎn)B,都只有一個(gè)開放端點(diǎn)和一個(gè)閉合端點(diǎn),這種一個(gè)端點(diǎn)開放而另一個(gè)端點(diǎn)閉合的情況稱此邊為半開放邊。節(jié)點(diǎn)B的右邊界FG的2個(gè)端點(diǎn)旁邊都沒有其他的障礙點(diǎn)與之構(gòu)成能夠包含節(jié)點(diǎn)B的直角,它們相對(duì)于節(jié)點(diǎn)B都是開放的。這種2個(gè)端點(diǎn)相對(duì)于該節(jié)點(diǎn)都開放的邊稱作開放邊。同樣可以分析,節(jié)點(diǎn)A的上邊界EC 的2個(gè)端點(diǎn)相對(duì)于節(jié)點(diǎn)A都是閉合的。這種2個(gè)端點(diǎn)都閉合的邊稱作閉合邊。圖3中的加粗實(shí)線表示自由節(jié)點(diǎn)邊界上的拐角,加粗虛線表示自由節(jié)點(diǎn)到相應(yīng)方向邊上的垂線。

    圖3 3種不同類型的邊

    性質(zhì)1整個(gè)網(wǎng)格模型的4條邊框中的每一條對(duì)任意節(jié)點(diǎn)都是閉合的。這是由任何節(jié)點(diǎn)(包括空白節(jié)點(diǎn)和障礙節(jié)點(diǎn))都必須在網(wǎng)格內(nèi)部決定的。

    定義4(邊的有效長度) 是指一條邊的非閉合部分長度。

    定義5(開放端點(diǎn)) 開放邊與半開放邊中非閉合一端的端點(diǎn)稱為開放端點(diǎn)。一條開放邊有2個(gè)開放端點(diǎn),而半開放邊只有1個(gè)開放端點(diǎn)。

    定義6(完全閉合) 是指一個(gè)自由節(jié)點(diǎn)的4條邊界均為閉合邊。

    2.4 自由節(jié)點(diǎn)

    定義7(自由節(jié)點(diǎn)) 是指可以逃離邊界的點(diǎn)。自由節(jié)點(diǎn)必須同時(shí)滿足以下2點(diǎn):(1)必須是在前一級(jí)自由節(jié)點(diǎn)的邊界外部且與邊界鄰接;(2)必須是前一級(jí)自由節(jié)點(diǎn)的開放邊端點(diǎn)的鄰近點(diǎn)。一個(gè)實(shí)例如圖4所示,節(jié)點(diǎn)P1和P2即為新的自由節(jié)點(diǎn)。圖中的加粗實(shí)線表示自由節(jié)點(diǎn)的邊界,加粗虛線表示自由節(jié)點(diǎn)2個(gè)自由節(jié)點(diǎn)間的連接線。

    圖4 節(jié)點(diǎn)P1與P2為新的自由節(jié)點(diǎn)實(shí)例

    性質(zhì)2自由節(jié)點(diǎn)與它對(duì)應(yīng)的上一級(jí)自由節(jié)點(diǎn)之間可以通過一條固定路徑的Z型路徑或者L型路徑相連。

    證明:以圖4中的節(jié)點(diǎn)P2和它的上一級(jí)節(jié)點(diǎn)A來證明。設(shè)A點(diǎn)坐標(biāo)為(x1,y1),P2點(diǎn)坐標(biāo)為(x2,y2)。由于P2點(diǎn)處于A點(diǎn)的邊界鄰接位置,則可以找到這樣一點(diǎn)N(x3,y3),使得N與P2可以直接以直線相連。

    下面證明點(diǎn)N與點(diǎn)A可以簡單連接(反證法):由于點(diǎn)N處于邊P1P2的端點(diǎn)處,假設(shè)點(diǎn)N與點(diǎn)A之間不能簡單連接,則必然有一個(gè)障礙存在于A到邊P1P2之間或者A到該邊的垂足與點(diǎn)N之間,若該障礙存在于A到邊P1P2之間,則A點(diǎn)下邊界將會(huì)改變而不再是P1P2,與已知條件沖突;若該障礙存在于A到該邊的垂足與點(diǎn)N之間,則A點(diǎn)下邊界的右端點(diǎn)將不再是開放邊,也與已知條件沖突。故假設(shè)不成立,即點(diǎn)N與點(diǎn)A可以簡單連接。同樣對(duì)于點(diǎn)A處于下邊界的位置時(shí),點(diǎn)N與點(diǎn)A可以直接進(jìn)行簡單連接。

    由以上2點(diǎn)可知,節(jié)點(diǎn)P2和它的上一級(jí)節(jié)點(diǎn)A之間可以通過一條固定路徑的Z型路徑或者L型路徑相連,證畢。

    定義8(簡單連接) 如果兩點(diǎn)之間可以通過直線或L型路徑相連,即2個(gè)節(jié)點(diǎn)具有相同的橫坐標(biāo)或縱坐標(biāo)且與該節(jié)點(diǎn)之間沒有障礙,或者可以找到一個(gè)新的節(jié)點(diǎn),使得該節(jié)點(diǎn)分別與2個(gè)原來的節(jié)點(diǎn)有相同的橫坐標(biāo)和縱坐標(biāo)且與該節(jié)點(diǎn)之間都沒有障礙。定義兩點(diǎn)之間的這種連接為簡單連接。如圖5中的2幅圖,節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的連接都屬于簡單連接。

    圖5 2種簡單連接

    3 算法的基本思想、實(shí)現(xiàn)與分析

    3.1 算法的基本思想

    對(duì)于兩點(diǎn)間布線路徑查找問題,本文算法的基本指導(dǎo)思想是從源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)開始,通過節(jié)點(diǎn)的邊界找到新的下一級(jí)節(jié)點(diǎn),再通過下一級(jí)節(jié)點(diǎn)的邊界擴(kuò)張找到新的子節(jié)點(diǎn),直到從源節(jié)點(diǎn)擴(kuò)散出的子節(jié)點(diǎn)與從目標(biāo)節(jié)點(diǎn)擴(kuò)散出的子節(jié)點(diǎn)可以通過簡單連接實(shí)現(xiàn)互連為止。

    可以將本文算法思想抽象理解為樹的結(jié)構(gòu),如圖6所示,源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)T分別是2棵樹的根節(jié)點(diǎn),讓這2棵樹不斷向下生長直到2棵樹的葉節(jié)點(diǎn)有相交部分為止。圖中所示為通過節(jié)點(diǎn)Sm與節(jié)點(diǎn)Tn的連接找到了布線路徑。

    圖6 算法的抽象樹示意圖

    每當(dāng)一個(gè)父親節(jié)點(diǎn)產(chǎn)生新的子節(jié)點(diǎn)時(shí),就表明通過自由節(jié)點(diǎn)的邊界擴(kuò)張找到了新的自由節(jié)點(diǎn)。樹的高度相當(dāng)于節(jié)點(diǎn)擴(kuò)散的效率,高度越大說明迷宮地形越復(fù)雜。在每一級(jí)父親節(jié)點(diǎn)產(chǎn)生子節(jié)點(diǎn)之前都會(huì)對(duì)2棵樹進(jìn)行比較,取節(jié)點(diǎn)較少的樹進(jìn)行生長以保證查找效率。

    3.2 算法的實(shí)現(xiàn)

    給定網(wǎng)格G=(V, E)及源節(jié)點(diǎn)S=(Si, Sj)和目的節(jié)點(diǎn)T=(Ti,Tj),增加集合FREEPOINTSA與FREEPOINTB分別存放起點(diǎn)和終點(diǎn)引出的最新的自由節(jié)點(diǎn);增加標(biāo)志位DETOUR表示是否存在迂回節(jié)點(diǎn);用四點(diǎn)集合CLOSED表示發(fā)生完全閉合時(shí)自由節(jié)點(diǎn)的邊界范圍。

    算法1基于邊界擴(kuò)張的點(diǎn)對(duì)點(diǎn)布線算法

    步驟1初始化,令FREEPOINTSA={S}, FREEPOINTSB= {T},迂回標(biāo)志位DETOUR=0,集合CLOSED={0,0,0,0},并以FREEPOINTSA為起始集合進(jìn)入步驟2。

    步驟2從傳入此步驟的集合(以下稱為起始集合,而另一個(gè)集合則稱作目標(biāo)集合)開始,對(duì)集合中的每個(gè)自由節(jié)點(diǎn)進(jìn)行邊界擴(kuò)張,獲取新的自由節(jié)點(diǎn),直到算法終止。

    (1)判斷起始集合與目標(biāo)集合中是否有節(jié)點(diǎn)可以通過直線或者L型路徑進(jìn)行簡單連接,若有,則轉(zhuǎn)步驟3。

    (2)從起始集合開始,利用算法2檢測(cè)每個(gè)節(jié)點(diǎn)的4個(gè)邊界,獲取4條邊的有效長度,對(duì)開放邊和半開放邊,記下開放端點(diǎn)的標(biāo)記位,保證每個(gè)開放邊只有一個(gè)自由節(jié)點(diǎn)。

    (3)判斷目標(biāo)集合中是否有自由節(jié)點(diǎn)存在于起始集合自由節(jié)點(diǎn)的邊界內(nèi)部。若不存在,以起始集合為輸入轉(zhuǎn)步驟(4);若存在,以目標(biāo)集合為輸入轉(zhuǎn)步驟(4)。

    (4)判斷傳入的起始集合中每個(gè)自由節(jié)點(diǎn)的邊界是否為完全閉合,若是完全閉合,判斷閉合原因,如果是障礙引起的完全閉合,則轉(zhuǎn)移節(jié)點(diǎn)到可以使邊界改變的邊,刪掉原節(jié)點(diǎn),增加符合條件的新節(jié)點(diǎn);若是由前一級(jí)節(jié)點(diǎn)的邊界引起的完全閉合,則利用算法2重新計(jì)算該節(jié)點(diǎn)的邊界。

    (5)記下此時(shí)的邊界4點(diǎn)值并與CLOSED中的4個(gè)值相比較,若相同,說明發(fā)生循環(huán),此節(jié)點(diǎn)無法通過新的自由節(jié)點(diǎn)逃離邊界。若起始集合每個(gè)自由節(jié)點(diǎn)均無法逃離,則無路可走,算法結(jié)束;否則將DETOUR置1,并以目標(biāo)集合為輸入轉(zhuǎn)步驟(1)。

    (6)獲取起始集合中新的自由節(jié)點(diǎn),更新起始集合,并讓集合中的每個(gè)自由節(jié)點(diǎn)通過指針指向能夠得到該節(jié)點(diǎn)的前一級(jí)自由節(jié)點(diǎn)。例如,若自由節(jié)點(diǎn)P1通過邊界擴(kuò)張得到了新的自由節(jié)點(diǎn)P2,則通過指針讓P2指向P1(即P2→P1),目的是在后面的布線步驟中可以直接找到前一節(jié)點(diǎn)。

    (7)判斷起始集合與目標(biāo)集合中自由節(jié)點(diǎn)的數(shù)量,從節(jié)點(diǎn)數(shù)目少的集合作為起始集合轉(zhuǎn)到步驟(1)。

    步驟3這里的輸入是分別來自2個(gè)集合中的某個(gè)自由節(jié)點(diǎn),進(jìn)入此步說明已經(jīng)找到通路,2個(gè)集合中的自由節(jié)點(diǎn)可以由一條直線或者L型路徑相連。這一步的主要工作便是布線與迂回處理。

    (1)用直線或者L型路徑連接這2個(gè)自由節(jié)點(diǎn)。

    (2)對(duì)每個(gè)集合中的自由節(jié)點(diǎn),通過步驟2中的指針連接前一級(jí)自由節(jié)點(diǎn),直到到達(dá)S或T為止。

    (3)檢測(cè)DETOUR的值,若DETOUR=1,使用算法3消除迂回路徑,算法結(jié)束;若DETOUR=0,算法結(jié)束。

    算法2獲取自由節(jié)點(diǎn)的邊界算法

    (1)檢查該自由節(jié)點(diǎn)是否是節(jié)點(diǎn)S或者節(jié)點(diǎn)T,若是,則轉(zhuǎn)步驟(2);若不是,則轉(zhuǎn)步驟(3)。

    (2)以自由節(jié)點(diǎn)為中心向4個(gè)方向延伸檢測(cè),遇到障礙物時(shí)停止,記下該障礙的位置,4個(gè)方向的障礙邊圍成的邊界即為該節(jié)點(diǎn)的邊界。

    (3)以節(jié)點(diǎn)為中心向4個(gè)方向延伸檢測(cè),遇到障礙物或前一級(jí)節(jié)點(diǎn)的邊界時(shí)停止,記下該障礙或邊界的位置,4個(gè)方向的障礙或邊圍成的邊界即為該節(jié)點(diǎn)的邊界。

    算法3消除迂回路徑算法

    對(duì)已經(jīng)布線的所有非起始自由節(jié)點(diǎn)(即,除了點(diǎn)S與點(diǎn)T之外的自由節(jié)點(diǎn))進(jìn)行檢查,一個(gè)正常的自由節(jié)點(diǎn)會(huì)有2條相互垂直的布線路徑,而迂回節(jié)點(diǎn)則只有一條。對(duì)于每個(gè)迂回節(jié)點(diǎn):

    (1)將此節(jié)點(diǎn)移動(dòng)到布線路徑方向的相鄰節(jié)點(diǎn),并刪除與原節(jié)點(diǎn)間的路徑。

    (2)對(duì)新節(jié)點(diǎn)進(jìn)行檢查是否為迂回節(jié)點(diǎn),若是迂回節(jié)點(diǎn),則轉(zhuǎn)步驟(1);若不是,算法結(jié)束。

    消除迂回路徑算法的示意圖如圖7所示,圖中X標(biāo)記的部分將被消除,P2會(huì)移動(dòng)到?jīng)]有迂回路徑的節(jié)點(diǎn)。

    圖7 迂回路徑的消除

    3.3 算法的復(fù)雜度分析

    由于本文算法從2個(gè)需要連線的起點(diǎn)開始以邊界向外擴(kuò)張,因此算法的復(fù)雜度與障礙物的分布和障礙物的邊長有關(guān),整個(gè)算法有2個(gè)主要耗時(shí)部分:第1部分是邊界擴(kuò)張和查找新的自由節(jié)點(diǎn);第2部分是每次邊界擴(kuò)張之前進(jìn)行的自由節(jié)點(diǎn)間是否可以由簡單路徑相連的判斷。

    先分析第1部分的復(fù)雜度:假設(shè)整個(gè)搜索路徑的過程中所使用到的開放端點(diǎn)數(shù)為e(并不是所有的開放端點(diǎn)都會(huì)被使用到),這些開放端點(diǎn)都是自由節(jié)點(diǎn);且與每一個(gè)使用到的開放端點(diǎn)iP對(duì)應(yīng)的邊界周長為Ci,該節(jié)點(diǎn)邊界所在的4條邊在邊界內(nèi)部的有效長度之和為Si,該節(jié)點(diǎn)邊界所在的4條邊的實(shí)際長度之和為Li那么有Si≤Li,且整個(gè)算法過程中搜索的節(jié)點(diǎn)總數(shù)為:自由節(jié)點(diǎn)的4條邊界長度與其實(shí)際長度不一定相等,方便起見取兩者近似相等,有ii

    L?C,于是式(1)可得到:

    在最壞的情況下,需要把所有遇到的障礙邊都搜索到而且每條障礙邊都會(huì)被它兩側(cè)的自由節(jié)點(diǎn)搜索一遍,也就是說每條障礙邊都會(huì)被搜索2次。假設(shè)所遇到的障礙物邊的總長度為L,于是有:

    由式(2)與式(3)可以知道:T=3L,即該算法的邊界擴(kuò)張部分的時(shí)間復(fù)雜度為O( L)。

    第2部分的復(fù)雜度主要是由2個(gè)源節(jié)點(diǎn)擴(kuò)散出來的新的自由節(jié)點(diǎn)間是否可以通過簡單路徑相連,這里所有判斷的2個(gè)節(jié)點(diǎn)都是確定位置的,而且簡單路徑的路徑判斷也最多只有2種情況,所需要的時(shí)間也與2個(gè)節(jié)點(diǎn)的位置有關(guān)。取最壞的情況來分析,假設(shè)所有自由節(jié)點(diǎn)都存在于整個(gè)網(wǎng)格G的對(duì)角上(實(shí)際當(dāng)然不可能如此,但這2個(gè)節(jié)點(diǎn)必定位于網(wǎng)格G中且距離不可能比對(duì)角距離更遠(yuǎn)),那么對(duì)于一般情況而言,必然存在一個(gè)值k∈(0,1],使得對(duì)于所有e個(gè)自由節(jié)點(diǎn)進(jìn)行判斷花費(fèi)的時(shí)間為ke( m+n)2,那么對(duì)于整個(gè)算法中所有自由節(jié)點(diǎn)間是否可以用簡單路徑相連判斷的復(fù)雜度就是O( e( m+n))。

    綜上所述,該算法總的時(shí)間復(fù)雜度為O( L+e( m+n)),由于僅需要保存新的自由節(jié)點(diǎn),算法空間復(fù)雜度為O( e)。

    4 實(shí)驗(yàn)結(jié)果與分析

    將本文算法與經(jīng)典迷宮算法和A*算法應(yīng)用于具體實(shí)例中,其中A*算法使用當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的Manhattan距離作為啟發(fā)條件,迷宮由隨機(jī)產(chǎn)生障礙節(jié)點(diǎn)的程序隨機(jī)生成。針對(duì)不同規(guī)模的迷宮,對(duì)3種算法獲取布線路徑所需要時(shí)間和與經(jīng)典算法運(yùn)行時(shí)間之比分別作統(tǒng)計(jì),見表1。

    表1 3種算法的實(shí)驗(yàn)比較

    從表中數(shù)據(jù)可以看出,A*算法與本文算法都能夠明顯減少運(yùn)行時(shí)間。在規(guī)模最小的8×8迷宮中,A*算法使用了經(jīng)典算法64.7%的運(yùn)行時(shí)間,本文算法則使用了41.2%;在其他5組較大規(guī)模的迷宮中,A*算法使用的時(shí)間在經(jīng)典算法的36%~60%之間,而本文算法則僅僅使用了7%~14%的時(shí)間,可見本文算法要明顯優(yōu)于另外2種算法。在相同疏密度(即障礙與路徑比)的迷宮中,隨著迷宮規(guī)模的增大,經(jīng)典迷宮算法需要查找的節(jié)點(diǎn)成倍增加,導(dǎo)致運(yùn)行時(shí)間迅速增長;A*算法的性能略有提升,說明加入啟發(fā)條件之后對(duì)于大規(guī)模迷宮查找路徑確實(shí)有一定的指導(dǎo)作用;而本文算法的運(yùn)行時(shí)間相比于迷宮規(guī)模的增長速度來看相對(duì)穩(wěn)定,線性效果明顯,因此,在規(guī)模較大的迷宮中運(yùn)行的整體效率比規(guī)模較小的迷宮有所提高。

    由第3節(jié)中得出的時(shí)間復(fù)雜度可以看出,本文算法的復(fù)雜度與障礙物的數(shù)量和分布相關(guān)。在迷宮的疏密度較低時(shí),后續(xù)實(shí)驗(yàn)表明運(yùn)行時(shí)間可以進(jìn)一步減少到5%甚至更低,然而在迷宮的疏密度較高且障礙分布雜亂時(shí)算法的效率會(huì)隨之降低,說明在迷宮的疏密度很高并且障礙分布雜亂時(shí)算法的效率會(huì)比較低。這是因?yàn)楸疚乃惴ǖ闹笇?dǎo)思想是讓拐線盡量少來快速地找到路徑,障礙分布雜亂時(shí)產(chǎn)生的新自由節(jié)點(diǎn)會(huì)更多,復(fù)雜度隨之增加。

    5 結(jié)束語

    本文提出一種新的點(diǎn)對(duì)點(diǎn)布線的算法,算法的創(chuàng)新點(diǎn)在于:(1)提出了自由節(jié)點(diǎn)和節(jié)點(diǎn)邊界等新的概念,每一個(gè)自由節(jié)點(diǎn)的出現(xiàn)都以逃離與它對(duì)應(yīng)的上一級(jí)自由節(jié)點(diǎn)的邊界為目的。(2)算法通過節(jié)點(diǎn)邊界的擴(kuò)張實(shí)現(xiàn)自由節(jié)點(diǎn)的轉(zhuǎn)移,從而快速地從源節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)擴(kuò)散,大大提高了搜索效率。該算法的優(yōu)點(diǎn)是既克服了傳統(tǒng)迷宮算法基于遍歷網(wǎng)格的高復(fù)雜度的缺點(diǎn),也無需在龐大的網(wǎng)格中搜索障礙構(gòu)造子圖。通過對(duì)自由節(jié)點(diǎn)邊界的擴(kuò)張不斷搜索路徑,理論分析和實(shí)驗(yàn)結(jié)果表明,該算法可以很好地解決點(diǎn)對(duì)點(diǎn)的布線問題且復(fù)雜度較低。以后的工作可考慮加入啟發(fā)條件,以降低迷宮疏密度較高的特殊情況出現(xiàn)時(shí)算法的復(fù)雜度。

    [1] Alpert C J, Mehta D P, Sapatneka r S S. Handbook of Algorithms for Physical Design A utomation[M]. [S. l.]: Auerbach Publications, 2009.

    [2] Lee C Y. A n Algorithm for Path Connection and Its Applications[J]. IRE Transactions on Electronic Computers, 1961, 10(3): 346-365.

    [3] 周 智, 蔣承東. Ma nhattan空間有障礙的最短路徑和3-Steiner樹算法[J]. 軟件學(xué)報(bào), 2003, 14(9): 1503-1514.

    [4] Akers S. A Modification of Lee’s Path Connection Algorithm[J]. IEEE Transactions on Electronic Computers, 1967, 16(2): 97- 98. [5] Soukup J. Fast Maze Router[C]//Proc. of t he 15th Design Automation Conference. Piscataway, USA: IEEE Press, 1978: 100-102.

    [6] Hart P E. A Formal B asis for the H euristic Determination o f Minimum Cost Paths in Graphs[J]. IEEE T rans. on Systems Science and Cybernetics, 1968, 4(2): 100-107.

    [7] 胡湘萍, 陳利軍. 迷宮算法的改進(jìn)與動(dòng)態(tài)實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù), 2007, 2(8): 490-491.

    [8] 陳傳波, 胡誼東, 何 力, 等. 目標(biāo)驅(qū)動(dòng)的迷宮布線算法及優(yōu)化[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2004, 32(1): 49-51.

    [9] 權(quán)建洲, 韓明晶, 李 智. 基于改進(jìn)A*算法的電子制造裝備布線方法研究[J]. 中國科技論文在線, 2009, 4(8): 555-559.

    [10] Hightower D W. A Solution to Line-routing Problems on the Continuous Plane[C]//Proc. of the 6th Annual Conference on Design Automation. New York, USA: ACM Press, 1969: 1-24.

    [11] Zheng Siqing, Lim J S. Finding Obstacle- avoiding Shortest Paths Using Implicit Connection Graphs[J]. IE EE Transactions on Computer Aided Design, 1996, 15(1): 103-110.

    [12] Wu Y F, Widmayer P. Rectilinear Shortest Paths and Minimum Spanning Trees i n the Presence of Rectilinear O bstacles[J]. IEEE Transactions on Computers, 1987, 36(3): 321-331.

    [13] Zheng Siqing, Lim J S, Iyengar S S. Efficient Maze-running and Line-search Algorithms for VLSI Layout[C]//Proc. of Southeastcon’93. Charlotte, USA: IEEE Press, 1993: 275-282.

    [14] 楊瑞元. 無網(wǎng)格線探索布線算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1998, 10(3): 200-207.

    [15] 蔡 毅, 王彥偉, 黃正東. 基于UG的三維電氣自動(dòng)布線技術(shù)研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(8): 68-72.

    編輯 顧逸斐

    New Algorithm for Point-to-Point Wiring Based on Boundary Expansion

    LIAO Hai-tao, SHI Zheng, ZHANG Teng

    (Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China)

    Global wiring is a very important step in the Very Large Scale Inte grated(VLSI) cir cuits design. Cla ssic maze routing algorithm and its improved versions are widely used to deal with global routing pr oblems in the in dustrial sector. With the dec reasing process node, the shortcoming of the high complexity of the maze routing algorithm becomes increasi ngly evident. By means of a new concept boundary expansion, this paper presents a new point-to-point wiring path search algorithm to solve the high complexity problem of rapidly increase with the expansion of the scale of routing. With the definition of free node, the new algorithm abandons the inefficient node by node expansion method. Instead, this algorithm expands the bo undary and finds ne w free nodes and will not terminat e until find out a path or determine that no solution is available. The theoretical and experimental comparisons are conducted between the proposed algorithm and classic routing algorithms. Experimental results show that the proposed algorithm can complete the routing wit h the runtime of 7%~14% of the classic algorithm in most cases.

    Very Large Scale Integrated(VLSI) circuits; global wiring; maze routing algorithm; point-to-point wiring; boundary expansion; free node

    10.3969/j.issn.1000-3428.2014.05.062

    國家自然科學(xué)基金資助項(xiàng)目(61204111)。

    廖海濤(1988-),男,碩士研究生,主研方向:超大規(guī)模集成電路,計(jì)算機(jī)輔助設(shè)計(jì);史 崢,副研究員、博士;張 騰,碩士研究生。

    2013-04-15

    2013-05-14E-mail:liaoht@vlsi.zju.edu.cn

    1000-3428(2014)05-0299-05

    A

    TP312

    猜你喜歡
    端點(diǎn)布線迷宮
    非特征端點(diǎn)條件下PM函數(shù)的迭代根
    擺脫繁瑣布線,重定義家庭影院 Klipsch Reference Wireless 5.1
    不等式求解過程中端點(diǎn)的確定
    面向目標(biāo)的主動(dòng)繞障PCB布線算法
    電子布線系統(tǒng)在工程中的應(yīng)用
    參數(shù)型Marcinkiewicz積分算子及其交換子的加權(quán)端點(diǎn)估計(jì)
    大迷宮
    迷宮
    基丁能雖匹配延拓法LMD端點(diǎn)效應(yīng)處理
    捕網(wǎng)迷宮
    久久午夜亚洲精品久久| 精品少妇一区二区三区视频日本电影| 亚洲成人久久爱视频| 国产精品亚洲av一区麻豆| 熟女少妇亚洲综合色aaa.| 久久久久精品国产欧美久久久| 脱女人内裤的视频| 国产精品亚洲一级av第二区| 97碰自拍视频| 女人高潮潮喷娇喘18禁视频| 成人国产一区最新在线观看| 国产成年人精品一区二区| 久久久精品欧美日韩精品| 国产精品自产拍在线观看55亚洲| 欧美日韩亚洲综合一区二区三区_| 国产精华一区二区三区| 国产精品久久电影中文字幕| 久久人妻av系列| 不卡av一区二区三区| 丝袜在线中文字幕| 搡老岳熟女国产| 视频区欧美日本亚洲| 免费人成视频x8x8入口观看| 可以在线观看的亚洲视频| 成年免费大片在线观看| 中文在线观看免费www的网站 | 久久久久久亚洲精品国产蜜桃av| 欧美日韩亚洲国产一区二区在线观看| 看免费av毛片| 国产精品一区二区精品视频观看| 久久国产精品男人的天堂亚洲| АⅤ资源中文在线天堂| 一个人观看的视频www高清免费观看 | 成人免费观看视频高清| 精品久久久久久久末码| 欧美国产日韩亚洲一区| 中文字幕精品免费在线观看视频| 久久久久久九九精品二区国产 | 99国产综合亚洲精品| av超薄肉色丝袜交足视频| 亚洲成人久久爱视频| 久久青草综合色| 欧美性长视频在线观看| 久久久久久九九精品二区国产 | 成人国产一区最新在线观看| 99热只有精品国产| 黄片大片在线免费观看| 国产激情久久老熟女| 丁香六月欧美| 日韩精品青青久久久久久| 国产主播在线观看一区二区| 满18在线观看网站| 亚洲成国产人片在线观看| 最近最新中文字幕大全电影3 | 黄色女人牲交| 欧美成人性av电影在线观看| av福利片在线| 国产片内射在线| 久久久久免费精品人妻一区二区 | 亚洲 欧美 日韩 在线 免费| 男女下面进入的视频免费午夜 | 可以免费在线观看a视频的电影网站| 怎么达到女性高潮| ponron亚洲| 一区福利在线观看| 日本免费a在线| 亚洲黑人精品在线| 亚洲欧美精品综合久久99| 亚洲欧洲精品一区二区精品久久久| 啦啦啦观看免费观看视频高清| 两性午夜刺激爽爽歪歪视频在线观看 | 欧美最黄视频在线播放免费| 久久久久免费精品人妻一区二区 | 国产91精品成人一区二区三区| 男女之事视频高清在线观看| 亚洲成人久久爱视频| 黄色丝袜av网址大全| 免费无遮挡裸体视频| 婷婷精品国产亚洲av在线| 久久精品国产清高在天天线| 男人的好看免费观看在线视频 | 国产成人av激情在线播放| 国产精品免费视频内射| 午夜福利18| 黄片小视频在线播放| 这个男人来自地球电影免费观看| 观看免费一级毛片| 黄色 视频免费看| 国产欧美日韩一区二区三| 日本免费a在线| 免费看日本二区| 99国产精品99久久久久| 女人爽到高潮嗷嗷叫在线视频| 日韩精品青青久久久久久| 国产精品久久久久久精品电影 | 亚洲av成人一区二区三| 18禁观看日本| 国产精品久久久av美女十八| a级毛片a级免费在线| 午夜福利视频1000在线观看| 淫妇啪啪啪对白视频| av免费在线观看网站| 午夜免费成人在线视频| 久久久久久久精品吃奶| 欧美成人免费av一区二区三区| 一本大道久久a久久精品| 麻豆久久精品国产亚洲av| 免费av毛片视频| 欧美成人一区二区免费高清观看 | av超薄肉色丝袜交足视频| 国产v大片淫在线免费观看| 国产免费男女视频| 手机成人av网站| 日韩欧美国产一区二区入口| 国产欧美日韩一区二区三| 听说在线观看完整版免费高清| 麻豆国产av国片精品| 成人18禁高潮啪啪吃奶动态图| 白带黄色成豆腐渣| 久热这里只有精品99| 麻豆av在线久日| 久久久久亚洲av毛片大全| 久久国产乱子伦精品免费另类| 免费高清视频大片| 欧美在线一区亚洲| 观看免费一级毛片| 动漫黄色视频在线观看| 黑丝袜美女国产一区| 日韩有码中文字幕| 国产1区2区3区精品| 自线自在国产av| 美女高潮喷水抽搐中文字幕| 性色av乱码一区二区三区2| 色综合欧美亚洲国产小说| 亚洲午夜理论影院| 午夜福利18| 国内毛片毛片毛片毛片毛片| 热99re8久久精品国产| 精品一区二区三区av网在线观看| 久久久久久久久中文| 麻豆成人av在线观看| 欧美一区二区精品小视频在线| 精品国产美女av久久久久小说| 亚洲熟妇熟女久久| 99国产精品一区二区蜜桃av| 欧美色欧美亚洲另类二区| 搡老熟女国产l中国老女人| 亚洲国产高清在线一区二区三 | 男女做爰动态图高潮gif福利片| 精品国产一区二区三区四区第35| 久久久久久国产a免费观看| 欧美在线一区亚洲| tocl精华| 婷婷丁香在线五月| 国产又黄又爽又无遮挡在线| 中文字幕精品免费在线观看视频| av免费在线观看网站| 亚洲精品一卡2卡三卡4卡5卡| 在线十欧美十亚洲十日本专区| 中文字幕久久专区| 亚洲男人的天堂狠狠| 中文字幕精品亚洲无线码一区 | 狠狠狠狠99中文字幕| 99精品欧美一区二区三区四区| 久久久久久久午夜电影| av在线天堂中文字幕| 亚洲五月天丁香| 制服诱惑二区| 三级毛片av免费| 久久草成人影院| 国产区一区二久久| 国产日本99.免费观看| netflix在线观看网站| 午夜福利在线在线| 一本久久中文字幕| 老司机午夜十八禁免费视频| 韩国av一区二区三区四区| 亚洲精品在线观看二区| 免费看十八禁软件| 久久久久久久久免费视频了| 日本五十路高清| 久久精品91无色码中文字幕| 天堂影院成人在线观看| 久久婷婷成人综合色麻豆| 久久婷婷人人爽人人干人人爱| 亚洲人成77777在线视频| av福利片在线| 麻豆成人av在线观看| 日韩欧美三级三区| 久久草成人影院| 手机成人av网站| 美女免费视频网站| 母亲3免费完整高清在线观看| 国产av一区在线观看免费| 在线观看免费视频日本深夜| 午夜福利免费观看在线| 老司机福利观看| 亚洲中文字幕日韩| 中文字幕人妻丝袜一区二区| 一级作爱视频免费观看| 超碰成人久久| 国内揄拍国产精品人妻在线 | 免费在线观看黄色视频的| 香蕉久久夜色| 国产一区在线观看成人免费| 亚洲精品久久国产高清桃花| 久久久久免费精品人妻一区二区 | 免费女性裸体啪啪无遮挡网站| 国产v大片淫在线免费观看| 亚洲欧美精品综合一区二区三区| 久久久精品欧美日韩精品| 99久久综合精品五月天人人| 久久精品91蜜桃| 久久中文字幕一级| 亚洲av电影不卡..在线观看| 老汉色∧v一级毛片| 日本免费a在线| 国产成人啪精品午夜网站| 黑人操中国人逼视频| 国产欧美日韩一区二区三| 禁无遮挡网站| 人人妻人人看人人澡| 国产不卡一卡二| 人成视频在线观看免费观看| 日本一本二区三区精品| 亚洲一区二区三区色噜噜| 国产黄色小视频在线观看| 99热这里只有精品一区 | 日韩欧美免费精品| 在线av久久热| 亚洲av成人不卡在线观看播放网| 99久久无色码亚洲精品果冻| 成人永久免费在线观看视频| 中文字幕人妻丝袜一区二区| 成人亚洲精品av一区二区| 午夜两性在线视频| 叶爱在线成人免费视频播放| 精品久久久久久成人av| 国产99白浆流出| 亚洲av第一区精品v没综合| 色尼玛亚洲综合影院| 999久久久精品免费观看国产| 琪琪午夜伦伦电影理论片6080| 国产成人一区二区三区免费视频网站| 精品少妇一区二区三区视频日本电影| av有码第一页| 天堂影院成人在线观看| 亚洲成人久久性| 99在线人妻在线中文字幕| 成熟少妇高潮喷水视频| 久久国产精品影院| 婷婷六月久久综合丁香| 久久香蕉激情| 少妇熟女aⅴ在线视频| 免费在线观看完整版高清| 人人妻人人澡人人看| 超碰成人久久| 亚洲国产欧洲综合997久久, | 波多野结衣av一区二区av| 麻豆av在线久日| 亚洲国产欧美网| 美女免费视频网站| 亚洲成av人片免费观看| 欧美日韩瑟瑟在线播放| 波多野结衣高清作品| www国产在线视频色| 在线观看66精品国产| 香蕉av资源在线| e午夜精品久久久久久久| 欧美乱色亚洲激情| 亚洲国产精品sss在线观看| 一区二区三区精品91| 男男h啪啪无遮挡| 18禁黄网站禁片免费观看直播| 母亲3免费完整高清在线观看| 亚洲在线自拍视频| 日韩 欧美 亚洲 中文字幕| 日韩高清综合在线| 国产成人精品久久二区二区免费| 欧美激情 高清一区二区三区| 国产国语露脸激情在线看| 亚洲成人免费电影在线观看| 国产亚洲欧美在线一区二区| 少妇的丰满在线观看| 女同久久另类99精品国产91| a级毛片a级免费在线| 我的亚洲天堂| 美女午夜性视频免费| 18禁黄网站禁片午夜丰满| 亚洲va日本ⅴa欧美va伊人久久| 免费在线观看完整版高清| bbb黄色大片| 欧美性长视频在线观看| 在线天堂中文资源库| 日本撒尿小便嘘嘘汇集6| 在线观看免费视频日本深夜| 午夜亚洲福利在线播放| 级片在线观看| 成人三级黄色视频| 欧美成狂野欧美在线观看| 黄色成人免费大全| 成在线人永久免费视频| 国产1区2区3区精品| 久久国产精品男人的天堂亚洲| 操出白浆在线播放| 国产伦一二天堂av在线观看| 日本精品一区二区三区蜜桃| 亚洲男人的天堂狠狠| 黄色 视频免费看| 99riav亚洲国产免费| 欧美乱码精品一区二区三区| 身体一侧抽搐| a在线观看视频网站| 国产亚洲精品综合一区在线观看 | 91字幕亚洲| 香蕉国产在线看| 无限看片的www在线观看| 久久久国产精品麻豆| 精品午夜福利视频在线观看一区| 首页视频小说图片口味搜索| 久久久久亚洲av毛片大全| 亚洲一卡2卡3卡4卡5卡精品中文| 身体一侧抽搐| 大型av网站在线播放| 亚洲一区二区三区不卡视频| 亚洲国产欧洲综合997久久, | 亚洲国产毛片av蜜桃av| 很黄的视频免费| 国产精品98久久久久久宅男小说| а√天堂www在线а√下载| 精品国产乱子伦一区二区三区| 每晚都被弄得嗷嗷叫到高潮| 欧美乱妇无乱码| 免费无遮挡裸体视频| 亚洲七黄色美女视频| 脱女人内裤的视频| 亚洲av成人av| 国产久久久一区二区三区| 侵犯人妻中文字幕一二三四区| 精品久久久久久,| 狠狠狠狠99中文字幕| 久久人妻av系列| 美女免费视频网站| 亚洲人成伊人成综合网2020| 日韩免费av在线播放| cao死你这个sao货| 激情在线观看视频在线高清| 国产一区二区三区在线臀色熟女| 国产av一区在线观看免费| 男女下面进入的视频免费午夜 | 美女国产高潮福利片在线看| 久久久久久国产a免费观看| 久久青草综合色| 亚洲片人在线观看| 99久久国产精品久久久| 好男人电影高清在线观看| 在线观看午夜福利视频| 国产精品一区二区精品视频观看| a级毛片a级免费在线| 一级毛片女人18水好多| www日本黄色视频网| 别揉我奶头~嗯~啊~动态视频| 国产免费男女视频| 久久久久久大精品| 成人18禁高潮啪啪吃奶动态图| 国产精品98久久久久久宅男小说| 精品久久久久久久末码| 欧美乱色亚洲激情| 俄罗斯特黄特色一大片| 亚洲av中文字字幕乱码综合 | 日本一本二区三区精品| 精品国产国语对白av| 色在线成人网| 18禁黄网站禁片午夜丰满| 女同久久另类99精品国产91| 成人亚洲精品一区在线观看| 一级毛片高清免费大全| 一二三四社区在线视频社区8| 黄片播放在线免费| 草草在线视频免费看| 中出人妻视频一区二区| 久久久国产欧美日韩av| 大型av网站在线播放| 国产伦在线观看视频一区| 啦啦啦 在线观看视频| 高潮久久久久久久久久久不卡| 两个人免费观看高清视频| 色尼玛亚洲综合影院| 日韩成人在线观看一区二区三区| 久久久久国产一级毛片高清牌| 亚洲中文字幕一区二区三区有码在线看 | 久久精品国产清高在天天线| 欧美久久黑人一区二区| 99热只有精品国产| 日日爽夜夜爽网站| 免费电影在线观看免费观看| 人妻丰满熟妇av一区二区三区| 一a级毛片在线观看| 99久久国产精品久久久| 色婷婷久久久亚洲欧美| 亚洲激情在线av| 99久久精品国产亚洲精品| 999久久久精品免费观看国产| 后天国语完整版免费观看| 变态另类成人亚洲欧美熟女| 免费看美女性在线毛片视频| 黑人操中国人逼视频| 亚洲国产欧洲综合997久久, | 在线观看一区二区三区| 欧美另类亚洲清纯唯美| 99re在线观看精品视频| 国产片内射在线| 亚洲国产看品久久| 日本三级黄在线观看| 亚洲片人在线观看| 久久人妻av系列| 日韩欧美一区二区三区在线观看| 国产片内射在线| 亚洲精品久久成人aⅴ小说| 久久香蕉激情| 神马国产精品三级电影在线观看 | 精品无人区乱码1区二区| 999精品在线视频| 99国产精品一区二区蜜桃av| 色婷婷久久久亚洲欧美| 国产一区二区三区在线臀色熟女| 在线国产一区二区在线| 久久精品国产亚洲av高清一级| 女人爽到高潮嗷嗷叫在线视频| 男女之事视频高清在线观看| 日韩国内少妇激情av| 日韩三级视频一区二区三区| 黄色a级毛片大全视频| 欧美黑人欧美精品刺激| 亚洲色图av天堂| 国产精品爽爽va在线观看网站 | 国产色视频综合| 天天一区二区日本电影三级| 亚洲国产欧美一区二区综合| 日韩精品中文字幕看吧| 1024视频免费在线观看| 精品少妇一区二区三区视频日本电影| 久9热在线精品视频| 欧美三级亚洲精品| 亚洲一卡2卡3卡4卡5卡精品中文| 亚洲精品国产区一区二| 精品无人区乱码1区二区| 男人舔女人的私密视频| 欧美丝袜亚洲另类 | 狂野欧美激情性xxxx| avwww免费| 精品欧美一区二区三区在线| 国产一卡二卡三卡精品| 国产又黄又爽又无遮挡在线| 欧美激情极品国产一区二区三区| 窝窝影院91人妻| 免费看美女性在线毛片视频| 无限看片的www在线观看| 亚洲精品粉嫩美女一区| 亚洲一区二区三区不卡视频| 色精品久久人妻99蜜桃| 欧美一区二区精品小视频在线| 日韩大码丰满熟妇| 亚洲熟女毛片儿| 中文字幕人妻熟女乱码| 久久久久久人人人人人| 十分钟在线观看高清视频www| 久久精品夜夜夜夜夜久久蜜豆 | 一卡2卡三卡四卡精品乱码亚洲| 成人三级黄色视频| 级片在线观看| 18禁黄网站禁片免费观看直播| 精品一区二区三区四区五区乱码| 日韩 欧美 亚洲 中文字幕| 欧美成人免费av一区二区三区| 国产私拍福利视频在线观看| 久久热在线av| 天天添夜夜摸| 91在线观看av| a级毛片在线看网站| 国语自产精品视频在线第100页| 香蕉国产在线看| 亚洲精品中文字幕在线视频| 国产区一区二久久| 97碰自拍视频| tocl精华| 女性被躁到高潮视频| 国产精品久久久久久人妻精品电影| 91九色精品人成在线观看| 亚洲国产欧美一区二区综合| 黑人巨大精品欧美一区二区mp4| 日韩有码中文字幕| 波多野结衣高清无吗| 亚洲avbb在线观看| 久久婷婷人人爽人人干人人爱| 成人一区二区视频在线观看| 国产三级黄色录像| 天天一区二区日本电影三级| 啪啪无遮挡十八禁网站| 成人av一区二区三区在线看| bbb黄色大片| 久久狼人影院| 国产av一区在线观看免费| 女生性感内裤真人,穿戴方法视频| 日日爽夜夜爽网站| 亚洲一码二码三码区别大吗| 国产精品一区二区精品视频观看| 中文字幕人妻熟女乱码| 国产精品影院久久| www.精华液| 国产免费av片在线观看野外av| 国产激情欧美一区二区| or卡值多少钱| 侵犯人妻中文字幕一二三四区| 一本久久中文字幕| 最好的美女福利视频网| 久久久久国产一级毛片高清牌| 欧美黄色片欧美黄色片| 成人欧美大片| 日韩欧美免费精品| 黄色丝袜av网址大全| 午夜免费成人在线视频| 久久伊人香网站| 亚洲成人国产一区在线观看| 9191精品国产免费久久| 日本a在线网址| 国产午夜福利久久久久久| 麻豆国产av国片精品| 18禁黄网站禁片免费观看直播| 午夜久久久在线观看| 99在线人妻在线中文字幕| 99国产精品99久久久久| 人妻丰满熟妇av一区二区三区| 国产私拍福利视频在线观看| 亚洲国产精品久久男人天堂| 国产精品亚洲美女久久久| 中文字幕另类日韩欧美亚洲嫩草| 亚洲专区国产一区二区| 禁无遮挡网站| 97人妻精品一区二区三区麻豆 | 精品福利观看| 免费在线观看黄色视频的| 日韩精品青青久久久久久| 日本三级黄在线观看| 亚洲男人天堂网一区| 国产成+人综合+亚洲专区| 国产成人精品无人区| 欧美一区二区精品小视频在线| 老司机午夜十八禁免费视频| 久久天堂一区二区三区四区| 高潮久久久久久久久久久不卡| а√天堂www在线а√下载| 国产亚洲av高清不卡| 别揉我奶头~嗯~啊~动态视频| av中文乱码字幕在线| 欧美中文日本在线观看视频| 亚洲熟妇中文字幕五十中出| 脱女人内裤的视频| 一个人观看的视频www高清免费观看 | 免费无遮挡裸体视频| 久99久视频精品免费| 人人妻人人澡欧美一区二区| 91老司机精品| 成人免费观看视频高清| 女同久久另类99精品国产91| 亚洲精品久久国产高清桃花| 神马国产精品三级电影在线观看 | 桃色一区二区三区在线观看| 亚洲av美国av| 一级毛片高清免费大全| 又大又爽又粗| 午夜两性在线视频| 国产亚洲欧美98| 亚洲精品色激情综合| netflix在线观看网站| 国产亚洲av嫩草精品影院| 久久久久久人人人人人| www.熟女人妻精品国产| 亚洲,欧美精品.| 欧美性长视频在线观看| 亚洲 欧美 日韩 在线 免费| 国产单亲对白刺激| 在线天堂中文资源库| 国产精品1区2区在线观看.| av片东京热男人的天堂| 88av欧美| 老司机在亚洲福利影院| 国产国语露脸激情在线看| 欧美av亚洲av综合av国产av| 日韩大尺度精品在线看网址| 一二三四社区在线视频社区8| 欧美日韩瑟瑟在线播放| 国产麻豆成人av免费视频| 国产真人三级小视频在线观看| 波多野结衣巨乳人妻| 91成年电影在线观看| 久热爱精品视频在线9| 母亲3免费完整高清在线观看| 亚洲精品一卡2卡三卡4卡5卡| 国产区一区二久久| 国产精品久久久久久精品电影 | 在线天堂中文资源库| 婷婷精品国产亚洲av| 这个男人来自地球电影免费观看| 亚洲国产精品sss在线观看| 国产久久久一区二区三区| 日韩欧美免费精品| 一区二区三区高清视频在线| 久久久久国产一级毛片高清牌| 视频区欧美日本亚洲| 亚洲最大成人中文| 久久久精品国产亚洲av高清涩受| 一a级毛片在线观看| 91九色精品人成在线观看| 国产精品久久视频播放|