劉耿耿 葉正陽(yáng) 朱予涵 陳志盛 黃 興 徐 寧

①(福州大學(xué)計(jì)算機(jī)與大數(shù)據(jù)學(xué)院 福州 350116)

②(中國(guó)科學(xué)院計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100190)

③(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 西安 710072)

④(武漢理工大學(xué)信息工程學(xué)院 武漢 430070)

1 引言

連續(xù)微流控生物芯片(Continuous-Flow Microfluidic Biochips, CFMBs)，也稱為片上實(shí)驗(yàn)室，集成了必要的生化功能組件(如混合器、加熱器、過濾器和檢測(cè)器等)[1]，具有許多優(yōu)點(diǎn)，如高精度、高通量、高自動(dòng)化、小型化和低樣品消耗等[2]。因此近些年受到越來(lái)越多的關(guān)注，并被成功地應(yīng)用到核酸提取[3]、快速病原體檢測(cè)[4]和DNA分析[5]等應(yīng)用中。

CFMBs由彈性體材料聚二甲基硅氧烷(Poly-DiMethylSiloxane, PDMS)制造，利用多層軟光刻工藝[6]加工得到其結(jié)構(gòu)，可以集成數(shù)百甚至數(shù)千個(gè)微閥門[7]，并通過組合和控制多個(gè)微閥門的關(guān)閉和開啟，可以建立更為復(fù)雜的操作，如分離、過濾和混合等。

CFMBs具有兩個(gè)物理層：流層和控制層。在CFMBs的流層物理設(shè)計(jì)中，需要對(duì)所有的組件和流通道進(jìn)行布局和布線。由于每增加一個(gè)流通道交叉點(diǎn)，會(huì)增加2～4個(gè)微閥門，用于必要的流體流通控制，不僅使得交叉污染等問題更為復(fù)雜，也顯著增加了控制層的設(shè)計(jì)難度；而更短的流通道長(zhǎng)度不僅能縮減流體運(yùn)輸延遲[8]，且僅需要更小的外部壓力來(lái)傳輸流通道流體，減少通道流體泄露和阻塞等問題的可能性，增強(qiáng)流通道傳輸?shù)目煽啃訹9]；同時(shí)芯片流層整體面積的縮減，有助提升芯片的集成度，降低芯片成本。因此，采用3個(gè)重要的指標(biāo)：流通道交叉點(diǎn)數(shù)量、流通道總長(zhǎng)度和芯片流層整體面積衡量其質(zhì)量。

文獻(xiàn)[9]首次提出一種CFMBs自頂向下的整體設(shè)計(jì)流程。但布局和布線兩個(gè)階段被分開考慮、缺乏交互，導(dǎo)致流層物理設(shè)計(jì)質(zhì)量退化。Wang等人[10]首次提出了協(xié)同設(shè)計(jì)布局和布線，通過迭代的布局調(diào)整，動(dòng)態(tài)地把布線信息反饋到布局中，進(jìn)一步改善了流層物理設(shè)計(jì)的質(zhì)量。該工作的布局階段使用傳統(tǒng)的模擬退火算法；布線階段采用基于協(xié)商的布線算法，并依靠迭代削弱布線順序的影響；針對(duì)組件與流通道產(chǎn)生的擁塞區(qū)，做面積增量布局調(diào)整。在此基礎(chǔ)上，朱予涵等人[11]改進(jìn)了隨機(jī)算法，引入具有良好全局優(yōu)化能力的離散粒子群優(yōu)化算法完成初始布局；布線階段使用基于協(xié)商的布線算法，以組件間曼哈頓距離降序作為布線順序；布局調(diào)整階段取消了擁塞區(qū)的設(shè)置，針對(duì)流通道交叉點(diǎn)，同樣做面積增量布局調(diào)整。該工作在時(shí)間成本與文獻(xiàn)[10]中相近的情況下，一定程度上提升了流層物理設(shè)計(jì)質(zhì)量。考慮到實(shí)際流體傳輸?shù)穆窂揭?guī)劃等問題，Huang等人[12]提出了一種名為PathDriver+的實(shí)用設(shè)計(jì)流程。針對(duì)有限資源下流體的存儲(chǔ)需要，文獻(xiàn)[13]提出了基于存儲(chǔ)和運(yùn)輸兩用的分布式流通道存儲(chǔ)。為了解決不同階段設(shè)計(jì)不同步的問題，文獻(xiàn)[14,15]將所有階段合成為一個(gè)有機(jī)的整體。

針對(duì)當(dāng)前流層物理設(shè)計(jì)質(zhì)量和效率難以同時(shí)兼得的問題，本文提出了一種多階段啟發(fā)式的流層物理協(xié)同設(shè)計(jì)算法，不僅顯著提高了流層物理設(shè)計(jì)的質(zhì)量，同時(shí)使得時(shí)間成本大幅下降，為解決大規(guī)模問題提供了新途徑。本文主要貢獻(xiàn)如下：

(1) 提出了一種新的布局算法：邏輯布局。該算法把每個(gè)組件初始為邏輯空間中的每個(gè)單元，基于組件之間的連接關(guān)系，利用鄰近移動(dòng)和目標(biāo)跳躍兩種交換操作，能夠高效地獲得所有組件的優(yōu)異邏輯位置。

(2) 在布局調(diào)整過程中，不僅考慮到組件對(duì)象，而且首次考慮到組件上具體連通端口的方位，進(jìn)一步縮小粒度，提出考慮組件連接關(guān)系的組件方向布局調(diào)整策略，有效減少了流通道交叉點(diǎn)數(shù)和流通道總長(zhǎng)度。

(3) 基于單個(gè)連通圖內(nèi)部組件之間的連接關(guān)系，提出了一種沿流通道收縮的布局調(diào)整策略，利用已有布線信息，顯著減小了流通道總長(zhǎng)度。

(4) 考慮到存在單連通圖和多連通圖的兩種組件連接關(guān)系，通過多圖收縮策略，對(duì)含有多個(gè)連通圖的測(cè)試用例進(jìn)行新一輪的布局調(diào)整，有效降低了芯片流層整體面積。

(5) 在6個(gè)測(cè)試用例上對(duì)包括以上的主要優(yōu)化策略進(jìn)行實(shí)驗(yàn)分析，同時(shí)與現(xiàn)有的流層物理設(shè)計(jì)協(xié)同算法進(jìn)行最終實(shí)驗(yàn)對(duì)比，驗(yàn)證了本文算法的有效性。

本文的其余部分組織如下。第2節(jié)介紹了問題模型。第3節(jié)介紹了本文方法的算法整體設(shè)計(jì)流程。第4節(jié)詳細(xì)介紹了算法具體細(xì)節(jié)步驟。第5節(jié)介紹和討論了實(shí)驗(yàn)結(jié)果。第6節(jié)總結(jié)了全文。

2 問題模型

由時(shí)序圖和組件列表作為輸入，進(jìn)行高層次綜合[9](即綁定和調(diào)度)后，可以得到組件間連接網(wǎng)。本文的問題模型以組件列表和組件間連接網(wǎng)作為問題輸入，在滿足約束條件前提下，輸出高質(zhì)量的流層物理設(shè)計(jì)解。具體描述如下：

問題輸入：組件列表和組件間連接網(wǎng)。

問題輸出：CFMBs的流層物理設(shè)計(jì)解。

優(yōu)化目標(biāo)：最小化流通道交叉點(diǎn)數(shù)量、流通道總長(zhǎng)度和流層整體面積的權(quán)重和。

約束條件：(1)組件間距最小約束，(2)流通道寬度最小約束，(3)流通道間距最小約束。

3 整體設(shè)計(jì)流程

如圖1中3種顏色的模塊所示，整體設(shè)計(jì)流程主要分為3個(gè)階段，分別為布局預(yù)處理、組件映射和包圍盒間隙布局調(diào)整、收縮布局調(diào)整。主要包括邏輯布局、組件方向布局調(diào)整、包圍盒間隙布局調(diào)整、沿流通道收縮和多圖收縮等策略。

圖1 算法整體設(shè)計(jì)流程

第1階段：布局預(yù)處理。包括邏輯布局和組件方向布局調(diào)整兩種算法，旨在分別實(shí)現(xiàn)組件在邏輯空間中優(yōu)異的邏輯位置和邏輯方向。首先，邏輯布局先初始化邏輯空間，再基于組件間的連接關(guān)系，利用邏輯布局中兩種組件的位置交換操作，使得存在連接關(guān)系組件之間的曼哈頓距離盡可能小，即達(dá)到聚集的效果，以獲得優(yōu)異的邏輯位置。其次，本文進(jìn)一步縮小粒度，設(shè)計(jì)了考慮端口的組件方向布局調(diào)整策略，通過調(diào)整組件的邏輯方向，使得連接組件上連通端口之間的曼哈頓距離盡可能小，以獲得優(yōu)異邏輯方向。兩種算法都能有效減少流通道總長(zhǎng)度和流通道交叉點(diǎn)數(shù)量。

第2階段：組件映射和包圍盒間隙布局調(diào)整。首先，為了將組件從邏輯位置映射到實(shí)際位置，同時(shí)保持第1階段結(jié)束后組件優(yōu)異的邏輯位置和邏輯方向，本文設(shè)計(jì)了包圍盒策略放置組件，即統(tǒng)一用一個(gè)邊長(zhǎng)最小的正方形容器盒包裹所有的組件，再把每個(gè)包圍盒以統(tǒng)一的初始間隙映射到實(shí)際布局布線物理空間中。其次，組件放置完成后，基于流通道兩端組件曼哈頓距離的升序順序，對(duì)所有流通道進(jìn)行布線操作，獲得初始包圍盒間隙下的流層物理設(shè)計(jì)解。最后，為了最大化當(dāng)前流層物理設(shè)計(jì)質(zhì)量，再針對(duì)包圍盒間隙，做增大間隙的布局調(diào)整，并迭代整個(gè)過程，直至達(dá)到設(shè)置的間隙閾值。迭代結(jié)束后，獲得最佳的包圍盒間隙。

第3階段：收縮布局調(diào)整。在利用前一個(gè)階段的最佳包圍盒間隙做完布局布線的基礎(chǔ)上，本文分步實(shí)現(xiàn)兩種基于收縮的布局調(diào)整方法：沿流通道收縮和多圖收縮。首先，為了減少流通道總長(zhǎng)度，考慮到組件的端口數(shù)量較少，可以讓組件從自身端口開始，沿已布線流通道向連接組件端口收縮。其次，若應(yīng)用中存在多個(gè)連通圖，則在沿流通道收縮后，連通圖(包括單個(gè)連通圖內(nèi)所有的組件和流通道)之間可能存在較大的冗余間隙。為了進(jìn)一步優(yōu)化流層整體面積，本文提出了多圖收縮策略，可以有效降低圖與圖之間的面積冗余，使得整體結(jié)構(gòu)更為緊湊。

4 算法具體步驟

(1)布局預(yù)處理

(a)邏輯布局?；谛蛄袑?duì)的布局表示方式，文獻(xiàn)[10,11]運(yùn)用隨機(jī)算法做布局，雖然整體上能夠得到一個(gè)較好的布局解，且直接得到組件的實(shí)際物理布局位置，但布局解質(zhì)量存在波動(dòng)，進(jìn)而使得最終流層物理設(shè)計(jì)質(zhì)量產(chǎn)生不穩(wěn)定的波動(dòng)。同時(shí)兩者的時(shí)間成本隨著問題規(guī)模的增大快速攀升。因此，本文分兩步來(lái)實(shí)現(xiàn)傳統(tǒng)布局的功能，提出了邏輯布局這種新算法，旨在先高效地獲得一個(gè)收斂穩(wěn)定且聚集效果好的高質(zhì)量邏輯布局解，再通過具體組件放置的方法，將組件的邏輯位置映射為實(shí)際物理位置。

如圖2所示，首先，按照組件序號(hào)升序順序，把每個(gè)組件依次放入邏輯空間的每個(gè)單元，組件序號(hào)用正整數(shù)表示，空的邏輯位置用零表示，實(shí)現(xiàn)邏輯空間的初始化。其次，再基于組件之間的連接關(guān)系，通過鄰近移動(dòng)和目標(biāo)跳躍兩種交換操作，以達(dá)到聚集效果，即連通的組件單元在邏輯空間中的曼哈頓距離盡可能小?？梢钥闯?，邏輯布局并不改變邏輯空間的大小。

圖2 邏輯空間初始狀態(tài)

如圖3(a)所示，鄰近交換操作針對(duì)的是與組件6的4個(gè)方向上相鄰的組件，并與其中一個(gè)凈收益最大的組件單元交換邏輯位置，它們之間的曼哈頓距離都僅為1個(gè)單位。凈收益是交換前兩組件與所有連接組件的曼哈頓距離和，再減去交換后兩組件與所有連接組件的曼哈頓距離和的差值。凈收益計(jì)算為

圖3 兩種組件單元交換操作

其中，a為主動(dòng)交換組件，b為被動(dòng)交換鄰近組件；an為與組件a連接組件數(shù)量，bn為與組件b連接組件數(shù)量；o為東西南北4個(gè)方向上的某個(gè)方向，d為兩組件之間的曼哈頓邏輯距離，be代表組件交換之前，af代表組件交換之后。

計(jì)算完所有組件4個(gè)方向上的凈收益后，與最大收益方向上的組件交換邏輯位置，迭代計(jì)算和交換這個(gè)過程，直到所有組件4個(gè)方向的凈收益都小于等于零。如圖3(b)所示，由于計(jì)算的先后順序等，圖中間部分已經(jīng)存在聚集效果很好的組件群，表示為桔黃色的矩形區(qū)域。由于鄰近交換的步長(zhǎng)僅為1，此時(shí)向左移動(dòng)交換的凈收益又小于等于零，通過鄰近交換操作，組件32越不過桔黃色區(qū)域，以靠近與之有連接的目標(biāo)組件6，因此目標(biāo)跳躍這種交換操作被提出。

與鄰近移動(dòng)操作相同，目標(biāo)跳躍操作也是基于連接組件的曼哈頓距離評(píng)估收益。首先，選取曼哈頓距離最大且未鎖定的邊，按照邊兩端組件各自度占兩者度和的概率，分配角色給這兩個(gè)組件，較大概率組件為目標(biāo)組件，另一個(gè)組件為跳躍組件。其次，若目標(biāo)組件周圍存在空的邏輯位置，跳躍組件則直接跳躍到該位置；若目標(biāo)組件的周圍不存在空的邏輯位置，則在周圍8個(gè)組件中隨機(jī)選中一個(gè)組件，用式(2)計(jì)算凈收益

其中，e為邊總數(shù)，式中計(jì)算所有邊兩端組件在跳躍動(dòng)作前后的曼哈頓距離差值。

接著按照順時(shí)針方向遍歷，直至得到第1個(gè)與跳躍組件交換位置，且交換凈收益非負(fù)的組件，執(zhí)行目標(biāo)跳躍操作；若周圍所有組件交換位置的凈收益都為負(fù)，則放棄目標(biāo)跳躍。本輪給該邊上鎖，迭代至所有邊被鎖定，接著解鎖所有邊開始新一輪迭代，重復(fù)這個(gè)過程，直至達(dá)到內(nèi)層迭代閾值或存在式(1)中凈收益為正，如算法1步驟2(3)所示，結(jié)束內(nèi)層目標(biāo)跳躍迭代，進(jìn)入外層鄰近移動(dòng)迭代。目標(biāo)跳躍的直接目標(biāo)是在至少不惡化當(dāng)前布局質(zhì)量的前提下，通過改變當(dāng)前組件邏輯布局結(jié)構(gòu)，以打破鄰近移動(dòng)收益瓶頸，使得存在組件鄰近移動(dòng)的凈收益為正。為了適應(yīng)測(cè)試用例規(guī)模，實(shí)際實(shí)驗(yàn)中外層迭代次數(shù)閾值設(shè)置為500，內(nèi)層迭代次數(shù)閾值設(shè)置為150。

邏輯布局的直接作用是讓存在邊的組件達(dá)到聚集效果。算法1給出了邏輯布局算法的整體流程，主要包括兩層的迭代。外層通過鄰近移動(dòng)來(lái)獲得正的凈收益；內(nèi)層通過目標(biāo)跳躍動(dòng)作，在不惡化整個(gè)邏輯空間布局的前提下，調(diào)整當(dāng)前布局結(jié)構(gòu)，以獲得鄰近方向上正的凈收益。如圖4所示，圖4(a)為初始布局后的布線結(jié)果，圖4(b)為邏輯布局后的布線結(jié)果，深灰色區(qū)域放置與左邊兩個(gè)組件有流通道相連的組件。可以看出，圖4(b)的連接組件之間達(dá)到聚集效果，使得流通道總長(zhǎng)度顯著降低，并且有減少流通道交叉點(diǎn)數(shù)的作用。

圖4 邏輯布局效果示意圖

(b)組件方向布局調(diào)整。文獻(xiàn)[10,11]的工作中忽略了組件上端口的方向。然而，組件間試劑的傳輸需要依靠流通道，流通道的兩端需要具體到組件的對(duì)應(yīng)端口。因此，組件上端口朝向?qū)α魍ǖ啦季€質(zhì)量有著明顯的影響，本文在默認(rèn)組件方向基礎(chǔ)上，提出了組件方向布局調(diào)整這一階段。如圖5所示，每個(gè)組件中的數(shù)字是其序號(hào)，在左右兩圖中，組件的邏輯位置并沒有變化，同時(shí)組件1、組件2和組件25很好地聚集在與它們存在連接的組件19旁邊。然而，圖5(a)中采用組件左邊輸入端口，組件右邊輸出端口的默認(rèn)組件布局方向，與之相比，組件方向布局調(diào)整后的圖5(b)中流通道長(zhǎng)度大大減少，同時(shí)避免出現(xiàn)圖5(a)中標(biāo)記為紅色這種過長(zhǎng)流通道。

圖5 組件方向布局調(diào)整效果示意圖

算法1 邏輯布局算法

該調(diào)整策略計(jì)算組件各個(gè)端口與對(duì)應(yīng)連接組件之間的曼哈頓距離和，以獲得最小距離方向作為組件優(yōu)化后的布局方向。端口的邏輯位置是與端口相鄰的邏輯單元位置相同。組件2唯一輸出端口的邏輯位置與組件19的邏輯位置相等，兩者距離為零。圖5(a)中組件2唯一輸出端口到組件19的距離為兩個(gè)單位。

(2)組件映射和包圍盒間隙布局調(diào)整

(a)包圍盒策略放置組件。在第1階段的工作結(jié)束后，得到了優(yōu)異的組件邏輯位置和邏輯方向，接著需要實(shí)現(xiàn)組件邏輯位置到實(shí)際物理位置的映射，獲得物理布局解。因此，本文采用了包圍盒策略放置組件。

包圍盒策略，即統(tǒng)一使用等面積的最小正方形包圍盒作為容器，包裹每個(gè)組件，其邊長(zhǎng)等于所有組件在兩個(gè)維度上的最大尺寸。

如圖6所示，圖中藍(lán)色帶序號(hào)的矩形塊均為放置組件，9個(gè)大小相等的邊界正方形則為包圍盒，所有組件默認(rèn)放置在包圍盒的左上角，包圍盒之間的初始間距為1個(gè)單位?？梢钥闯觯鼑胁呗猿錾乩^承了第1階段的組件邏輯位置和邏輯方向。

圖6 包圍盒策略放置組件

(b)實(shí)際布線評(píng)估。為了衡量某一包圍盒間隙下的布局質(zhì)量，通過實(shí)際布線評(píng)估布局質(zhì)量，其適應(yīng)度值函數(shù)的計(jì)算式為

其中，C為布局布線工作后的流通道交叉點(diǎn)數(shù)，L為流通道總長(zhǎng)度，A為流層整體面積。α,β,γ為權(quán)重，在實(shí)驗(yàn)中分別為300, 20和1，權(quán)值與文獻(xiàn)[10,11]中一致，之后所有實(shí)驗(yàn)對(duì)比的權(quán)重和也是基于該式計(jì)算。

布線算法上，本文使用兩階段的A*算法對(duì)所有流通道進(jìn)行布線。在第1階段，不允許流通道產(chǎn)生交叉點(diǎn)的前提下，讓盡可能多的流通道成功布線；在第2階段，解除不允許產(chǎn)生流通道交叉點(diǎn)的限制，對(duì)前一階段所有布線失敗的流通道繼續(xù)布線，直到所有流通道布線成功。該算法有利于在一定程度上減少流通道交叉點(diǎn)數(shù)量，也能保證在相對(duì)充裕布線資源情況下，整體流通道的布線成功。本文布線相關(guān)工作都是使用基于該布線順下的兩階段A*布線算法。

(c)針對(duì)包圍盒間隙的布局調(diào)整。首次放置組件后包圍盒之間的初始間距設(shè)置為1個(gè)單位，布線資源可能不足。為了最大化流層物理設(shè)計(jì)質(zhì)量，需要作進(jìn)一步的布局調(diào)整。由于組件間的大小可能存在較大差距，若直接針對(duì)組件間隙做布局調(diào)整工作，則難以保存之前優(yōu)異的組件邏輯位置，讓存在連接關(guān)系的組件很好地聚集在一起。因此，本文提出了針對(duì)包圍盒，做增大包圍間隙的布局調(diào)整。

如圖7所示，實(shí)現(xiàn)從圖7(a)到圖7(b)的包圍盒間隙增大過程，每一輪僅增加一個(gè)單位。為了減少布線資源和計(jì)算資源的浪費(fèi)，迭代中的最大間隙閾值不宜過大，設(shè)置為包圍邊長(zhǎng)的一半并向上取整。當(dāng)達(dá)到最大間隙閾值時(shí)結(jié)束迭代，并保存最佳的包圍盒間隙。最大間隙閾值與應(yīng)用中組件端口數(shù)量呈正相關(guān)關(guān)系。

圖7 包圍盒間隙布局調(diào)整示意圖

(3)收縮布局調(diào)整

(a)沿流通道收縮。第2階段工作結(jié)束后，考慮到之前提到部分組件可能與包圍盒的面積差距較大，包圍盒內(nèi)存在較為充裕的布線空間。同時(shí)在生物芯片的應(yīng)用場(chǎng)景中，組件的端口數(shù)量較小，一般為個(gè)位數(shù)，甚至存在度為1的葉子懸掛點(diǎn)組件，為單個(gè)圖的收縮降低了難度。因此，本文提出了一種新的布局調(diào)整方式：沿流通道收縮。沿流通道收縮是將懸掛點(diǎn)組件沿著與之連通的唯一一條流通道，且滿足約束的前提下，盡可能地縮短該流通道，并移動(dòng)組件到相應(yīng)的新位置。

如圖8所示，圖中有兩個(gè)懸掛點(diǎn)組件發(fā)生了布局調(diào)整。在圖8(a)中，組件默認(rèn)放置于包圍盒的左上角，但實(shí)際物理空間中存在足夠的空間資源，讓懸掛點(diǎn)組件調(diào)整到更好的位置。在圖8(b)中，組件進(jìn)行了沿流通道收縮的操作，與圖8(a)對(duì)比，顯著地減少了流通道長(zhǎng)度，同時(shí)避免了一個(gè)流通道交叉點(diǎn)的產(chǎn)生。

圖8 沿流通道收縮前后示意圖

本文中的沿流通道收縮策略只是針對(duì)懸掛點(diǎn)組件，將來(lái)工作可以進(jìn)一步考慮度大于1組件的多階段收縮操作，在滿足約束的前提下，使得單個(gè)圖的連接結(jié)構(gòu)更為緊湊，面積更小。

(b)多圖收縮。上一階段結(jié)束后，單個(gè)連通圖的連接結(jié)構(gòu)得到了優(yōu)化。然而，若實(shí)例中包含多個(gè)連通圖，則忽略了收縮后圖與圖之間可能存在的可觀面積冗余。因此，在計(jì)算連通圖的個(gè)數(shù)后，本文提出了新的布局調(diào)整方式，以實(shí)現(xiàn)能夠在不改變流通道交叉點(diǎn)數(shù)和流通道總長(zhǎng)度，且滿足約束的條件下，達(dá)到優(yōu)化流層整體面積效果。

多圖收縮的具體策略是把單個(gè)圖中所有的組件和流通道看作同質(zhì)的圖塊，不改變圖塊的形狀和方向，盡可能向物理空間西北方向移動(dòng)靠攏。如圖1所示，若應(yīng)用用例只存在一個(gè)連通圖，則跳過多圖收縮階段，直接輸出最終的流層物理設(shè)計(jì)解；若存在多個(gè)連通圖，則多圖收縮優(yōu)化后，再輸出最終的流層物理設(shè)計(jì)解。

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

本文方法基于C++語(yǔ)言實(shí)現(xiàn)，在3.00 GHz 4核CPU與8 GB內(nèi)存的Windows環(huán)境中單線程執(zhí)行，與文獻(xiàn)[11]保持一致的運(yùn)行環(huán)境，并使用了文獻(xiàn)[11]中的算法原代碼執(zhí)行對(duì)比實(shí)驗(yàn)。

(1)策略有效性驗(yàn)證

為了更好地分析各階段中主要策略對(duì)每個(gè)指標(biāo)的優(yōu)化效果，本文驗(yàn)證3個(gè)階段中5個(gè)主要策略的有效性。

圖9—圖12展示的是3個(gè)階段中5個(gè)主要策略完成后的實(shí)驗(yàn)各指標(biāo)數(shù)據(jù)。其中，橫坐標(biāo)為5個(gè)策略的序號(hào)，1是邏輯布局策略，2是組件方向布局調(diào)整策略，因?yàn)檫@兩個(gè)策略中還未獲得最佳包圍盒間隙，所以實(shí)驗(yàn)中暫設(shè)包圍盒邊長(zhǎng)的1/4并向上取整作為包圍盒間隙，3是包圍盒間隙布局調(diào)整策略，4是沿通道收縮策略，5是多圖收縮策略。縱坐標(biāo)為各指標(biāo)的數(shù)值范圍。

圖9 流層整體面積變化趨勢(shì)

如圖9所示，執(zhí)行5個(gè)策略后，流層整體面積整體上得到了明顯優(yōu)化。由于PCR, ProteinSplit-1和ProteinSplit-2 3個(gè)測(cè)試用例中只存在單個(gè)連通圖，所以面積上保持不變，圖中表現(xiàn)為與x軸平行的線段。

如圖10所示，前4個(gè)策略都使流通道總長(zhǎng)度獲得了明顯優(yōu)化。由于多圖收縮策略不改變流通道總長(zhǎng)度和流通道交叉點(diǎn)數(shù)量，所以在第5個(gè)策略多圖收縮中，6個(gè)測(cè)試用例的流通道總長(zhǎng)度保持不變。

圖10 流通道總長(zhǎng)度變化趨勢(shì)

如圖11所示，流通道交叉點(diǎn)數(shù)量整體保持較低水平。與圖10中原因相同，第5個(gè)策略對(duì)流通道交叉點(diǎn)數(shù)量無(wú)影響?？梢钥闯觯瑘D中3個(gè)測(cè)試用例的流通道交叉點(diǎn)數(shù)量存在一個(gè)V形反彈。這是由于最佳包圍盒間隙小于前兩步中暫設(shè)的包圍盒間隙，而更小包圍盒間隙意味著更少布線資源，可能會(huì)提高流通道交叉點(diǎn)數(shù)量。所以為了最小化權(quán)重和，產(chǎn)生了流通道交叉點(diǎn)數(shù)量反彈上升的現(xiàn)象。

圖11 流通道交叉點(diǎn)數(shù)量變化趨勢(shì)

如圖12所示，前4個(gè)策略使權(quán)重和在6個(gè)測(cè)試用例中都得到了顯著連續(xù)下降。由于多圖收縮不改變流通道交叉點(diǎn)數(shù)量和流通道總長(zhǎng)度，且與圖9中相同原因，PCR, ProteinSplit-1和ProteinSplit-2 3個(gè)測(cè)試用例的流層整體面積也不發(fā)生改變，所以多圖收縮策略對(duì)這3個(gè)測(cè)試用例的權(quán)重和無(wú)影響。

圖12 3個(gè)指標(biāo)權(quán)重和變化趨勢(shì)

(2)與其他算法對(duì)比

為了驗(yàn)證本文算法的性能，將本文算法與文獻(xiàn)[10]、文獻(xiàn)[11]中的算法在5個(gè)指標(biāo)上進(jìn)行了對(duì)比。如表1所示，與文獻(xiàn)[10]中算法對(duì)比，本文的算法在流層整體面積上平均優(yōu)化了24.70%，流通道交叉點(diǎn)數(shù)量上平均優(yōu)化了93.49%，流通道總長(zhǎng)度上平均優(yōu)化了75.70%，整體上獲得了較大提升。因此，如表2所示，3個(gè)指標(biāo)的權(quán)重和也得到了平均66.99%的優(yōu)化效果。時(shí)間上獲得平均151.46的加速比。同時(shí)加速比由ProteinSplit-1的21.90增加到Protein-Split-2的53.41，由InVitro-1的91.20增加到InVitro-3的524.15?？梢钥闯觯S著應(yīng)用規(guī)模的增大，本文算法在時(shí)間成本上的對(duì)比優(yōu)勢(shì)也在擴(kuò)大。

表1 與文獻(xiàn)[10]最終實(shí)驗(yàn)結(jié)果3指標(biāo)對(duì)比

表2 與文獻(xiàn)[10]的最終實(shí)驗(yàn)結(jié)果對(duì)比

如表3所示，與文獻(xiàn)[11]對(duì)比，本文算法在流層整體面積、流通道交叉點(diǎn)數(shù)量和流通道總長(zhǎng)度上分別平均優(yōu)化了20.22%, 54.66%和71.62%。因此，如表4所示，本文算法在3個(gè)指標(biāo)權(quán)重和上平均優(yōu)化了59.83。加速比平均為177.12。同時(shí)也達(dá)到了與文獻(xiàn)[10]對(duì)比時(shí)的效果，應(yīng)用規(guī)模越大，時(shí)間成本上的優(yōu)勢(shì)越大。

表3 與文獻(xiàn)[11]最終實(shí)驗(yàn)結(jié)果3指標(biāo)對(duì)比

表4 與文獻(xiàn)[11]的最終實(shí)驗(yàn)結(jié)果對(duì)比

6 結(jié)論

針對(duì)連續(xù)微流控生物芯片，本文提出了一種多階段啟發(fā)式的流層物理協(xié)同設(shè)計(jì)算法，通過邏輯布局和組件方向布局調(diào)整，高效地獲得優(yōu)質(zhì)的布局預(yù)處理方案，而后基于包圍盒策略進(jìn)行組件布局，實(shí)現(xiàn)組件從邏輯空間到實(shí)際物理空間的映射，并設(shè)計(jì)了包圍盒間隙、沿流通道收縮和多圖收縮3種策略進(jìn)行布局調(diào)整。實(shí)驗(yàn)結(jié)果證明，本文算法不僅在流通道交叉點(diǎn)數(shù)量、流通道總長(zhǎng)度和流層整體面積上獲得顯著提升，而且極大縮減了時(shí)間成本，提升了設(shè)計(jì)效率，為大規(guī)模應(yīng)用設(shè)計(jì)提供了新方案。在未來(lái)工作中，我們致力于將本工作拓展到大規(guī)模且組件更為復(fù)雜的應(yīng)用背景下，同時(shí)考慮布線轉(zhuǎn)角數(shù)量等設(shè)計(jì)目標(biāo)，使已有工作能更加直接高效地映射到實(shí)際應(yīng)用中。