連續微流控生物芯片下一種多階段啟發式的流層物理協同設計算法

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

①(福州大學計算機與大數據學院 福州 350116)

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

③(西北工業大學計算機學院 西安 710072)

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 問題模型

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

問題輸入：組件列表和組件間連接網。

問題輸出：CFMBs的流層物理設計解。

優化目標：最小化流通道交叉點數量、流通道總長度和流層整體面積的權重和。

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

3 整體設計流程

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

圖1 算法整體設計流程

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

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

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

4 算法具體步驟

(1)布局預處理

(a)邏輯布局。基于序列對的布局表示方式，文獻[10,11]運用隨機算法做布局，雖然整體上能夠得到一個較好的布局解，且直接得到組件的實際物理布局位置，但布局解質量存在波動，進而使得最終流層物理設計質量產生不穩定的波動。同時兩者的時間成本隨著問題規模的增大快速攀升。因此，本文分兩步來實現傳統布局的功能，提出了邏輯布局這種新算法，旨在先高效地獲得一個收斂穩定且聚集效果好的高質量邏輯布局解，再通過具體組件放置的方法，將組件的邏輯位置映射為實際物理位置。

如圖2所示，首先，按照組件序號升序順序，把每個組件依次放入邏輯空間的每個單元，組件序號用正整數表示，空的邏輯位置用零表示，實現邏輯空間的初始化。其次，再基于組件之間的連接關系，通過鄰近移動和目標跳躍兩種交換操作，以達到聚集效果，即連通的組件單元在邏輯空間中的曼哈頓距離盡可能小。可以看出，邏輯布局并不改變邏輯空間的大小。

圖2 邏輯空間初始狀態

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

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

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

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

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

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

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

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

圖4 邏輯布局效果示意圖

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

圖5 組件方向布局調整效果示意圖

算法1 邏輯布局算法

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

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

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

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

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

圖6 包圍盒策略放置組件

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

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

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

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

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

圖7 包圍盒間隙布局調整示意圖

(3)收縮布局調整

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

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

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

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

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

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

5 實驗結果分析

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

(1)策略有效性驗證

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

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

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

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

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

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

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

圖11 流通道交叉點數量變化趨勢

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

圖12 3個指標權重和變化趨勢

(2)與其他算法對比

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

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

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

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

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

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

6 結論

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