連續(xù)微流控生物芯片下一種多階段啟發(fā)式的流層物理協(xié)同設(shè)計算法

劉耿耿 葉正陽 朱予涵 陳志盛 黃 興 徐 寧

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

②(中國科學(xué)院計算機體系結(jié)構(gòu)國家重點實驗室 北京 100190)

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 問題模型

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

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

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

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

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

3 整體設(shè)計流程

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

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

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

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

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

4 算法具體步驟

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

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

如圖2所示，首先，按照組件序號升序順序，把每個組件依次放入邏輯空間的每個單元，組件序號用正整數(shù)表示，空的邏輯位置用零表示，實現(xiàn)邏輯空間的初始化。其次，再基于組件之間的連接關(guān)系，通過鄰近移動和目標跳躍兩種交換操作，以達到聚集效果，即連通的組件單元在邏輯空間中的曼哈頓距離盡可能小?？梢钥闯觯壿嫴季植⒉桓淖冞壿嬁臻g的大小。

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

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

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

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

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

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

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

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

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

圖4 邏輯布局效果示意圖

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

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

算法1 邏輯布局算法

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

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

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

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

如圖6所示，圖中藍色帶序號的矩形塊均為放置組件，9個大小相等的邊界正方形則為包圍盒，所有組件默認放置在包圍盒的左上角，包圍盒之間的初始間距為1個單位?？梢钥闯?，包圍盒策略出色地繼承了第1階段的組件邏輯位置和邏輯方向。

圖6 包圍盒策略放置組件

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗結(jié)果分析

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

(1)策略有效性驗證

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

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

圖9 流層整體面積變化趨勢

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

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

圖10 流通道總長度變化趨勢

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

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

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

圖12 3個指標權(quán)重和變化趨勢

(2)與其他算法對比

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

表1 與文獻[10]最終實驗結(jié)果3指標對比

表2 與文獻[10]的最終實驗結(jié)果對比

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

表3 與文獻[11]最終實驗結(jié)果3指標對比

表4 與文獻[11]的最終實驗結(jié)果對比

6 結(jié)論

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