考慮流端口數(shù)量約束下的連續(xù)微流控生物芯片流路徑規(guī)劃算法

陳志盛 朱予涵 劉耿耿*② 黃 興 徐 寧

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

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

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

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

1 引言

連續(xù)微流控生物芯片可以應用于生物、醫(yī)學以及化學領域，如蛋白質結晶[1]、納米顆粒合成[2]和藥物篩選[3]等實際應用?；镜倪B續(xù)微流控生物芯片結構由兩個彈性層組成，一層是流層，另一層是控制層。如圖1(a)，藍色表示的是流層，黃色表示的是控制層。流通道用于運輸反應樣品/試劑，控制通道用于傳導氣壓。通道由彈性材料制成，雙層通道的交叉位置便充當閥門的作用。雙層通道都需要連接到外部壓力源。在控制層，外部壓力由控制端口導入，壓迫閥門處薄膜向下擠壓，使得該通道段阻塞而不能運輸液體，而當撤掉壓力，薄膜便依靠自身彈性力恢復到初始位置。在流層，液體需靠由流端口導入的壓力推動運輸。

圖1 連續(xù)微流控生物芯片示意圖

閥門是芯片結構中最基本的控制模塊，它可以組合成更復雜的組件，如蠕動泵、開關以及混合器等[4]。如圖1(b)所示，組件通過流通道相連接而形成流層運輸網(wǎng)絡來執(zhí)行各種生化反應。當樣品和試劑需要定向地在組件之間通過流通道傳輸時，就需要先找到這條定向的路徑并打開路徑中對應的閥門，而后從流端口注入氣壓來進行驅動。如果先前已經有氣壓或者液體在該路徑中，必須先將其排出芯片，否則累積的壓力會使芯片損壞。因此，每條流路徑都是起始于輸入端口且終止于輸出端口的完整通道路徑。

對于流通道網(wǎng)絡的優(yōu)化可為生物芯片帶來巨大的潛力，使得硬幣大小的微流控平臺上同時執(zhí)行更多的流體運輸任務以提高生化反應的執(zhí)行效率，但這就需要大量的流端口來完成更多運輸任務的驅動。越來越多的流端口使得生物芯片產生一些問題：(1)1個流端口占用多達4 mm2的芯片面積[5]；(2)流端口需在由彈性材料制成的芯片上打孔，所以具有大量流端口的生物芯片物理性能更脆弱且易損壞；(3)流端口需連接到外部壓力源，越多流端口就增加了芯片制造成本。這些問題使得生物芯片難以被廣泛運用。因此，為了克服這些問題，本文提出具有嚴格約束流端口數(shù)量的生物芯片結構，同時確保片上資源能在有限端口驅動下合理分配給流體運輸任務。

如果輸入組件的流體體積超過了組件特定的最大容積，就會有一部分流體不能被組件接收。這部分廢液需要立即排出以避免污染后續(xù)操作的流體。例如，在圖2(a)中，第1種流體輸入至混合器的下半部分；在圖2(b)中，第2種流體輸入至混合器的上半部分，此時混合器的兩端存在著多余廢液；在圖2(c)中，兩種流體開始進行混合操作；在圖2(d)中，將混合后的流體運送出該混合器，并正在移除多余的廢液。因此，本文在該生物芯片的系統(tǒng)設計階段需要同時考慮流體的運輸和移除，以生成執(zhí)行效率高的芯片架構。而考慮實際流體在有限的端口驅動下進行運輸與移除，也使得流通道網(wǎng)絡的設計變得更加復雜和具有挑戰(zhàn)性。

圖2 混合操作[5]

此外，由于兩種流體不能在同一時間經過相同的流通道，當存在沖突時，需要將其中一個運輸任務延后，直到另一個運輸任務完成后才能進行。沖突越多，延后的運輸任務越多，則導致生化反應總時間越長。在流端口數(shù)量的約束條件下進行完整的流體運輸與移除操作且盡可能地避免沖突，不僅能構建完整且高效的生物芯片體系，使生化反應更為流暢快速，也能降低其生產成本，提高生物芯片的應用廣泛程度。

針對連續(xù)微流控生物芯片架構已經提出了許多自動化的設計方法[6,7]，用以系統(tǒng)地解決生物芯片設計問題。文獻[8]通過移除傳統(tǒng)的特定存儲器，提出了分布式流通道存儲架構的概念，進一步提高了生物芯片的性能。文獻[9]將流路徑規(guī)劃整合到文獻[8]的方法中，以生成具有完整流路徑的芯片架構。而文獻[10]提出了一種有效的快速啟發(fā)式方法得出優(yōu)化后的分布式通道存儲架構。并且，文獻[11]將清洗優(yōu)化以及高效的清洗路徑計算流融合到文獻[10]的方法中，以生成各種流處理任務的實際調度過程。文獻[12]提出了一種名為PathDriver的設計流程。它將輸入流體的體積控制約束表述為整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)模型，從而生成具有體積管理的芯片架構。而文獻[13]將調度重計算以及對角線布線策略融合到文獻[12]的ILP模型當中，以進一步降低芯片構建代價以及提高芯片的執(zhí)行效率。文獻[14]提出了專門處理流通道布線問題的方法，從而最小化流通道總長度。文獻[15]提出了一種名為MiniControl的設計流程。通過在流層物理設計階段考慮了控制端口數(shù)量的最小化，從而有效地降低控制層設計的復雜度以及提高芯片的可靠性。文獻[16]在文獻[15]的方法下，進一步考慮控制層的設計優(yōu)化，以生成具有閥門同步性的控制系統(tǒng)。文獻[17]提出了一步合成的流層物理設計流程，能有效解決高層次綜合與物理設計之間的設計鴻溝問題，以生成高效的芯片架構。文獻[18]考慮了流層與控制層的協(xié)同設計問題，以生成具有最小化生化反應執(zhí)行總時間、總的端口數(shù)量、控制通道總長度、壓力時延以及控制通道壓力傳播偏差的雙層芯片架構。這些工作主要考慮了優(yōu)化芯片的成本和執(zhí)行效率，然而，它們忽略了在流端口數(shù)量約束下完整且具有運輸沖突感知的流路徑規(guī)劃問題。因此，本文考慮到流端口數(shù)量嚴格約束下流路徑優(yōu)化的重要性，主要研究了連續(xù)微流控生物芯片架構設計問題。本文主要貢獻如下：

(1)分析了流端口數(shù)量增加對生物芯片性能的影響，從而生成在更加實際的情況下流體如何有序地在給定的流端口約束下完成運輸與移除的芯片架構。

(2)提出了連續(xù)微流控生物芯片的流路徑規(guī)劃問題，對提高端口約束下的芯片執(zhí)行效率具有重要意義。

(3)考慮在有限端口驅動下從高層次綜合到流層物理設計的流程，從而可以協(xié)調實際的流體運輸與移除操作，產生具有高執(zhí)行效率的芯片架構。

(4)使用7個測試用例來評估所提出的優(yōu)化算法，結果驗證了所提算法的有效性。

2 問題描述

如圖3，生化反應可建模為一個有向無環(huán)序列圖G(O,E)， 其中頂點oi ∈O表示操作，并關聯(lián)一個參數(shù)te(oi)來 表示對應的執(zhí)行時間。邊集E定義了操作間的依賴性關系。oi的 輸入和輸出分別由in(oi)和o ut(oi)來表示。連續(xù)微流控生物芯片架構設計流程包括高層次綜合和流層物理設計兩個主要階段，每個階段都對最終的流通道網(wǎng)絡的復雜性具有重大影響。在高層次綜合中，操作被綁定到特定的組件上，并順序執(zhí)行。然而，不同的綁定與調度方案會產生不同的流體驅動要求。例如，圖4顯示了同一生化反應對應的兩個不同綁定與調度結果，其中紅色矩形框代表移除組件兩側廢液的操作?？偣灿?個組件用于執(zhí)行該生化反應，并且其中混合器、加熱器、過濾器和檢測器的體積分別為4.0 nl,3.5 nl, 3.0 nl和2.5 nl。在圖4(a)中，需要同時驅動進行o1,o2和o3的輸入操作。由于同一輸入端口在同一時間只能輸入一種流體，因此需要分配3個輸入端口來同時完成3個流體的輸入操作。但如圖3所示，其中加權路徑最大的是o2→o5→o7→o8→o9→o10→匯點，o1和o3的提前完成并不能有效地加速反應的完成。所以在圖4(b)中，延遲執(zhí)行操作o1和o3的輸入，這樣不僅反應的總執(zhí)行時間不會增加，通過異步地進行3個輸入操作，還能將輸入端口的數(shù)量減少至1個。而是否需要排出多余的廢液取決于輸入流體的總體積和組件的容積。因此，高層次綜合的任務即是生成一個調度時間表，在不超過最大端口數(shù)限制下優(yōu)化反應的總執(zhí)行時間。

圖3 生化反應的序列圖

圖4 根據(jù)圖3的生化反應產生的兩種不同的調度方案

流層物理設計需要求得組件和流端口的位置以及流通道的布線。由于未經優(yōu)化的方案可能會引入不必要的環(huán)形路線和不同流路徑之間頻繁的沖突，所以需要構建合適的流通道網(wǎng)絡來正確有效地運輸液體以及移除廢液，本文在考慮移除廢液的情況下盡可能地優(yōu)化布局和布線方案來避免沖突。例如圖5顯示了圖4(a)中調度方案對應的兩種布局和布線結果。圖5(a)是一個由傳統(tǒng)設計方法生成的解決方案，雖然其最小化了流通道的交叉和通道長度，但由于沒有考慮廢液的排出，會導致完整的調度過程的執(zhí)行失敗。例如探測器的左側如果堆積了廢液將無法在適當?shù)臅r候排出芯片。為了進行比較，圖5(b)構建了一個完整的流通道網(wǎng)絡，在這樣的生物芯片中，所有指定的運輸和移除任務都可以進行，確保了生化反應的正確性。因此，流層物理設計的任務是找到一種布局布線解，以優(yōu)化流通道的總長度，同時避免流體運輸和移除時發(fā)生沖突。

圖5 根據(jù)圖4(a)的調度方案生成的兩種布局和布線方案

綜上所述，高層次綜合和流層物理設計都會影響最終的流通道網(wǎng)絡。為了考慮流端口數(shù)量和滿足所有運輸及移除任務的流路徑，本文在兩階段分別引入新的約束條件。因此，構建問題模型為：

輸入：表示生化反應的序列圖G(O,E)，組件庫C并且指定相應的類型和體積，每種類型中所允許的最大組件數(shù)量以及最大流端口數(shù)量Nf。

輸出：操作綁定與調度解和流層布局布線解。

目標：在流端口數(shù)量不超過Nf的限制條件下，(1)減少生化反應所需完成時間，(2)減少任務沖突數(shù)，(3)減少交叉點數(shù)量，(4)減少流通道總長度。

3 本文算法

3.1 高層次綜合

在高層次綜合階段中，主要有兩個目標：(1)找到一個組件綁定方案，將操作O綁定到組件C；(2)找到一個調度方案，使所有的操作都可以依次執(zhí)行并同時滿足對應的依賴性和端口約束。然而，調度問題是一個多項式復雜程度的非確定性(Nondeterministic Polynomial, NP)問題[19]，且流端口數(shù)量約束進一步增加了問題的復雜性。為了解決上述問題，本文提出一種基于列表調度[20]且考慮端口約束的綁定與調度方法。

在此方法中，本文將每個操作oi ∈O的時間參數(shù)定義為預備時間tready(ai) 、開始時間tstart(oi)和結束時間tend(oi)， 其中tready(ai) 是 操作oi的所有父操作的最晚執(zhí)行完成時間，從此時起該操作oi允許被調度，tstart(oi)和tend(oi)分 別是操作oi執(zhí)行開始時間和結束時間。序列圖中操作間的依賴性ej,k ∈E被定義為一個運輸任務。由于流體的運輸時間取決于流通道的長度，但在此階段流通道的布線尚未完成，還不能確定其長度，無法得知流體確切的運輸時間，所以可以定義一個常數(shù)tc來代表組件間的運輸時間。

同時，每個操作oi還 需計算各自的優(yōu)先級值p r(oi)。操作優(yōu)先級的計算基于兩個因素：臨界因子cf(oi)和移動因子m f(oi)。 c f(oi)定義為序列圖中從當前操作oi到匯點的最大加權路徑的權重值，表示為

其中，Pi是oi到 匯點的所有路徑的集合，ej,k是路徑pt中 的邊，M ax(·)是一個求最大值的函數(shù)。此公式求出了oi到匯點的最大權重路徑的執(zhí)行總時間?？倳r間越長，說明此操作對后繼操作的影響越大，其關鍵程度就越高，越需要被優(yōu)先調度。參數(shù)mf(oi)可通過緊前調度算法(As-Soon-As-Possible, ASAP)和緊后調度算法(As-Last-As-Possible, ALAP)來計算得到，它體現(xiàn)了每個操作是否可以在不同時間被調度的靈活性。其中，a s(oi)和 a l(oi)分別表示基于ASAP和ALAP的調度時間。 a s(oi) 和a l(oi)差值越大，說明操作的可執(zhí)行區(qū)間越靈活。因此，mf(oi)表示為

再由c f(oi) 和m f(oi)的 加權和來確定操作oi的優(yōu)先級值p r(oi)為

其中，α和β是兩個加權因子。α和β作為公式中比例分配的值，它們的和為1。例如在圖3的序列圖中，從o3起始的最大加權路徑是o3→o7→o8→o9→o10→匯點。 當tc設置為2時，計算得出cf(o3)為33(4+7+3+6+3+2×5=33)。并且，o3的最早可執(zhí)行時間為2 s，即輸入液體運輸至加熱器時可立馬執(zhí)行，因此a s(o3)為 2。而由于o7最晚可執(zhí)行時間為22 s，o3的輸出液體需要在20 s的時候到達混合器并作為o7的 輸入液體，則o3的最晚可執(zhí)行時間為14(20–2–4=14)，即 a l(o3)為14。在每次調度選擇時，優(yōu)先對擁有最高優(yōu)先級的操作進行調度處理。因此，根據(jù)以上算法，將最先執(zhí)行主導生化反應完成時間的操作。

在調度過程中，每個組件ck ∈C都有自己對應的預備時間tready(ci) 來 表示組件ck可用的時間點。tready (ci)由式(4)得出

其中，oj是最近的在ck上執(zhí)行的操作，tremove(oj)是將操作oj產生的流體out(oj)徹底從ck移除的時間點。當oj與后續(xù)的操作oi存在流體依賴關系時，tready(oj)即是操作oj完成的時間tend(oj)。當不存在流體依賴關系時，需將操作oj的 輸出out(oj)完全移出ck才能在ck上進行下一個操作。對于即將調度的操作oi，通常本文直接選擇與oi操作所需的組件類型相符的、同時預備時間最早的組件，即tready(ci)值最小的組件。

由于生物芯片所需的流端口數(shù)量取決于同一時間并行運輸任務的最大數(shù)量，本文采用一種基于時間窗的方法來進行運輸任務的調度。當執(zhí)行一個運輸任務時，可以用時間窗來記錄運輸任務精確的執(zhí)行時間段。一個時間窗(ws,we)代 表了運輸任務從ws開始至we結束，時間窗的跨度u=ws-we即是任務的執(zhí)行時間。根據(jù)此定義，只有時間窗(ws,we)重疊的運輸任務才會影響流端口的調度。因此，通過時間窗的分析可以消除流端口的沖突。本文定義一個計數(shù)器tslot來記錄任意時間段內流端口的驅動需求，并初始化tslot=0。每當有一個運輸任務進行時，在此時間段內產生一個流端口需求，這段時間的tslot增加1，直到運輸任務結束再釋放tslot至執(zhí)行運輸任務前的數(shù)值。

在將操作oi綁定到選定的組件之后，根據(jù)序列圖中的每個流體依賴關系ek,i ∈E，將o ut(ok)運輸?shù)剿x的組件中。當所有所需流體都完成輸入到選定的組件中時，即可開始執(zhí)行oi。同時也需要考慮輸入流體的總體積與組件cj的容積，來判斷是否需要移除廢液，如果輸入流體的總體積超過了組件cj的容積，則需將多余液體從生物芯片中移除。在生成綁定與調度方案之后，可求得所需的流端口數(shù)量以及組件與流端口之間的互連關系，即布線網(wǎng)絡Nr。

3.2 流層物理設計

3.2.1 布局階段

本文提出一種基于遺傳算法[21]的布局算法，并用序列對來表示組件的位置關系[22,23]。序列對由n個表示組件列表的元素構成，并且可將其轉換為組件的布局解，其對應轉換的規(guī)則為：(1)(...ci...cj...),(...ci...cj)→cj在cj的上邊；(2)(...ci...cj...),(...cj...ci)→ci在cj的上邊。根據(jù)此位置關系的轉換，可以分別構造左右位置關系和上下位置關系的兩個有向無環(huán)圖，即水平約束圖和垂直約束圖。通過兩個約束圖，就可以確定組件的布局[23]。

基于序列對表示，首先隨機生成具有N個個體的種群。每個個體ni=(s,,Oi)(1≤i≤N)都可以轉換為n個組件的位置，其中(,)表示序列對，Oi=(,...,)表示每個組件方向(0?或轉動9 0?)的2元向量。對每一次進化迭代(包括i tem次的遺傳算子)，N個父代在一定概率下被選擇、重組和變異，然后生成下一代。當最優(yōu)個體的適應度值不再改變時，算法結束。

芯片的邊界框在兩個約束圖中已經得出，所以端口在此時可以直接放置在芯片矩形框的邊界上。由于端口的位置會極大地影響最終流通道構造網(wǎng)絡的復雜程度，本文考慮了設計的目標函數(shù)中流端口和組件之間的連通關系。端口 ptg可以是一個輸入端口或者是組件的出口， ptk可以是一個輸出端口或者是組件的入口。因此，組件位置結果的評價的目標函數(shù)為

其中，A(pi)表 示芯片面積，d ist(j,k)是 端口p tg和ptk之間的曼哈頓距離，c p(j,k)是線網(wǎng)nj,k的連接優(yōu)先級。 O bj(pi)的值越小，則此評價越優(yōu)。高連接優(yōu)先級的組件由于涉及的運輸任務更多，對整個布局的影響更大。如果兩個組件之間的線網(wǎng)具有較大的連接優(yōu)先級，則它們有更大的概率位置相近。當連接優(yōu)先級大的組件距離遠時，其 O bj(pi)值會過大而被舍棄。而當連接優(yōu)先級小時，由于其對布局影響不大，組件之間距離的遠近不需要很敏感，其要求就比較寬松，遠距離的結果也可能被保留。

本文將 ptg和p tk之間的運輸任務定義為一個使用nj3,路 徑的運輸操作，連接優(yōu)先級c p(j,k)定義為與端口 ptg和p tk之間的運輸任務數(shù)量成正比以提高生化反應的執(zhí)行效率，運輸任務數(shù)量越多，連接優(yōu)先級越高。不僅如此，為了減少流通道之間的運輸沖突，如果端口 ptg和p tk之間的運輸任務與其他運輸任務同時執(zhí)行，則將 cp(j,k)設置為一個極大值以盡可能地排除掉此種結果。因此，cp(j,k)被定義為

其中，p=1, 2, ···, ntj,k, n tj,k是調度時端口p tg和ptk之 間的運輸任務總數(shù)，tp是端口p tg和p tk之間第p個運輸任務，c tp是與tp執(zhí)行時間段重疊的運輸任務數(shù)量，λ和γ是加權因子?？梢钥闯?，如果存在時間并行的運輸任務產生沖突，c p(j,k)的值會極大，使得 O bj(pi)值極大，于是此種結果很大可能被排除。最后，本文根據(jù)適度值函數(shù)值fi來最終評估單個ni，fi定義為

其中，O bj_Max是所有個體中最大的目標函數(shù)值，Obj(pi)是 當前個體ni的目標函數(shù)值。在遺傳過程中，具有較高適應度值fi的個體將被保留，用以進行下一代的遺傳。

對于每次遺傳操作，本文首先基于輪盤賭的方法選擇兩個父代個體nf1和nf2，一個個體被選中的概率為

可以看出，適應度值fi越高的個體越有可能被選中。因此，累積概率c pi為

然后，在0～1隨機生成一個數(shù)字r， 如果r≤cp1，則選擇n1，如果c pi-1≤r ≤cpi(i>1)，則選擇ni。父代個體選擇完畢后，即可開始進行遺傳過程的交叉或者變異操作。

遺傳算法的性能很大程度上取決于交叉算子的有效性，它提供了搜索過程中主要的探索機制。如果0～1生成的隨機數(shù)小于交叉概率pc，則對兩個選定的父代個體nf1和nf2執(zhí) 行交叉操作。本文將nf1和nf2的第1序列設置為主序列對，第2序列設置為副序列對。序列對進行交叉重組后形成子代ns1和ns2。交叉重組的過程中，首先隨機選擇一個區(qū)域作為交叉匹配區(qū)域，將匹配區(qū)域中的子序列放置于子代的開頭部分。將nf2的第1序列中匹配區(qū)域的子序列刪除重復的元素后，作為ns1后 續(xù)的子序列。ns1的其余元素按照nf1中相同元素的順序進行填充。其他的子代序列也用同樣的方法產生。

如果0～1生成的隨機數(shù)小于變異概率pm，則對所選的父代nf1執(zhí)行變異操作。以相同的概率選擇nf1的第1或者第2序列，隨機選擇該序列中的兩個元素交換位置產生子代ns3?；蛘咭部梢噪S機選擇一個組件來改變其方向生成子代ns3。

最后，當經過若干次交叉與變異操作后，子代個體的fi值不再改變，視為找到最優(yōu)解，對應的組件位置生成布局結果。布局執(zhí)行完畢后，可知組件和流端口的確定布局位置并且開始流通道的布線過程。

3.2.2 布線階段

本文提出一種路徑驅動的布線算法來構建可執(zhí)行的、總長度較短的流通道網(wǎng)絡。首先構造了一個將組件視為障礙物的生成圖作為后續(xù)過程的布線圖，其構造方法如下：首先從組件的4個角點、組件的輸入輸出端口以及流端口出發(fā)，向4個正交方向出發(fā)畫線，當線接觸到芯片面積的邊界時結束，最后刪去線在組件內部的線段。組件的邊界以及芯片的邊界也可以進行布線。圖的節(jié)點由線的所有交點組成，節(jié)點之間的線段構成邊。圖6顯示了構建的繞障生成圖，圓圈表示所有需要出發(fā)畫線的起點。在此生成圖的基礎上進行構造調度方案中所需的所有流路徑。流路徑在生成圖的線網(wǎng)中進行選擇，如果一條線段被任意路徑選中并使用，則在最終的布線圖中對其進行保留，最終生成完整流通道網(wǎng)絡。

圖6 構建的繞障生成圖

在算法中，首先初始化每條邊r ei,j的 權重W(rei,j)為0，當邊ri,s用于構造{第k}次運輸任務的流路徑時，將其放入集合Mi,j=u來進行標記。隨后根據(jù)所有運輸任務的開始時間，按照非遞減的順序進行排序，并使用改進的A*算法為每個運輸任務找到一條布線路徑。A*算法的優(yōu)勢在于不同于傳統(tǒng)尋路算法的盲目搜索，通過引入啟發(fā)函數(shù)，對每條邊進行評估，使其朝著目標點更有方向性地進行路線規(guī)劃，從而提升算法效率。同時，本文根據(jù)避免沖突及路徑復用的思想，引入一個新的邊權重計算方式。在為任務構建流路徑之前，設定了一個集合 Ptk為調度方案中指定任務相對應的并行任務集，并計算每個布線邊的權重值為

其中，Cp是一個用戶自定義的參數(shù)。通過式(10)的權重設定，當一條通道正在進行運輸任務時，同時間并行的其他運輸任務如再次選擇此路徑，則會受到高權重的懲罰，從而避開選擇此條正在進行運輸任務的通道，來避免沖突的發(fā)生；而當一條路徑曾經使用過但現(xiàn)在空閑時，低權重使得后續(xù)運輸任務優(yōu)先選擇此類通道來進行不同任務之間的路徑共享，以減少流路徑的總長度。在評判完不同通道的權重之后，本文使用A*路徑搜索算法來為任務建立一個有效的流路徑。在此過程中，綜合考量對于任務t askk當前搜索邊的布線成本為

其中，H(pti,nodep)表示邊r ep,q從源端口p ti到 起點nodep的路徑長度，E(nodep,ptj)為從終點nodep到目標端口點 ptg的預估路徑長度。在使用A*尋路時，優(yōu)先選擇Cost(rep,q)k值小的邊。

4 實驗結果及分析

本文使用3種實際應用的生化反應和4種合成的測試用例來進行算法的實驗。其中實際應用的生化反應是體外診斷(In-Vitro Diagnostics, IVD)、聚合酶鏈式反應(Polymerase Chain Reaction,PCR)以及蛋白質分離(ProteinSplit)，其他為合成的測試用例。4個合成的測試用例是采用隨機算法生成的序列圖，生化反應操作的數(shù)量從10～40遞增，分別為RA10, RA20, RA30, RA40生成的序列圖的操作多樣性以及連接關系的復雜性依次增加。同時3個實際應用的生化實驗是具有規(guī)則且并行的操作流程，如PCR用例是由7個混合操作構成的混合樹。表1給出了測試用例的相關信息，其中|O|表示序列圖中操作的數(shù)量，隨后分別給出混合器、加熱器、過濾器、分離器以及探測器的數(shù)量，最后Nf表示流端口的最大數(shù)量。并且，表2還給出了本文中所提到參數(shù)的數(shù)值。

表1 測試數(shù)據(jù)集

表2 參數(shù)設置值

表3展示了本文所提算法的實驗結果。其中反應時間為高層次綜合結果的生化反應完成總時間，流路徑數(shù)量為高層次綜合結果中總的流體運輸任務數(shù)。而在流層物理設計中，本文使用3個值作為布線結果的評判標準，分別是沖突任務數(shù)、流通道的交叉點數(shù)以及流通道總長度。

表3 高層次綜合和流層物理設計的結果

文獻[10]提出了一種基于清洗感知的A*布線算法，但沒有考慮到多余液體的移除問題。文獻[10]采用的A*搜索考慮了不同路徑之間的交叉污染問題，即并行任務不共享路徑，非并行任務可共享路徑，但布線代價與液體的清洗時間相關。當去除了清洗約束，并將廢液移除任務加入到布線的過程中時，文獻[10]中的布線仍可以根據(jù)任務的并行情況進行路徑搜索。因此我們修改了文獻[10]中方法，再與之生成的結果進行對比。圖7、圖8和圖9分別展示了本文所提布線算法與基于文獻[10]修改后的布線算法的對比結果。從實驗的結果可以看出，本文算法在沖突任務數(shù)、交叉點數(shù)量、總的流通道長度都取得明顯的減少。特別地，本文沖突任務數(shù)、交叉點數(shù)量和總的流通道長度分別取得了34%, 11%以及7%的優(yōu)化效果。這證明了本文所提布線算法的有效性。這主要是得益于本文對所有流路徑進行了細致的規(guī)劃，針對并行任務，所提算法能盡量減少流路徑的復用，從而減少沖突的產生以及交叉點數(shù)量的增多；針對非并行任務，算法優(yōu)先沿著之前的流通道進行路徑規(guī)劃，從而減少流通道的總長度。

圖7 本文布線算法與文獻[10]的沖突任務數(shù)結果對比

圖8 本文布線算法與文獻[10]的交叉點數(shù)量結果對比

圖9 本文布線算法與文獻[10]的通道總長度結果對比

5 結論

本文考慮流端口數(shù)量對于生物芯片設計及性能的影響，提出基于嚴格約束流端口數(shù)量的連續(xù)微流控生物芯片的路徑驅動物理設計問題。流端口數(shù)量越多，則芯片制造的成本越高。為了使得完成生化反應的時間更短、芯片設計更高效，本文在給定流端口數(shù)量的條件下，考慮盡可能地避免任務之間的運輸沖突，并進一步對交叉點數(shù)量和流通道總長度進行優(yōu)化。通過7個基準測試驗證了此方法的有效性，實驗結果表明，本算法可使沖突任務數(shù)少的同時優(yōu)化交叉點數(shù)量及通道總長度，使得芯片執(zhí)行效率更高。