（河南工程學(xué)院 機(jī)械工程學(xué)院，鄭州 451191）

0 引言

由微機(jī)電系統(tǒng)和微電子流體系統(tǒng)組成的復(fù)合微系統(tǒng)已逐漸成為新型的系統(tǒng)芯片設(shè)計(jì)[1]。這些系統(tǒng)結(jié)合了微觀結(jié)構(gòu)和固態(tài)電子來(lái)集成多種能量域，如電、機(jī)械和流體等。微結(jié)構(gòu)和微電子的結(jié)合使得新一代的集成系統(tǒng)瞄準(zhǔn)了環(huán)境感應(yīng)、生化分析、試劑檢測(cè)以及精確流體分配等方面。而數(shù)字微流控芯片正屬于這樣的集成系統(tǒng)[2]。它的出現(xiàn)革新了生物化學(xué)和生物醫(yī)學(xué)的諸多領(lǐng)域，使我們能夠精準(zhǔn)地控制少量流體用于精密分配，并能減少試劑消耗，以便進(jìn)行在線生物化學(xué)分析、床邊檢測(cè)和實(shí)施過(guò)程監(jiān)測(cè)[3,4]。

介電濕潤(rùn)是數(shù)字微流控技術(shù)中最常見(jiàn)的一種液滴驅(qū)動(dòng)方式[5]。通過(guò)按次序地對(duì)電極施加電壓，液滴可以自由地在2D數(shù)字微流控芯片上移動(dòng)并到達(dá)任意位置，以完成相應(yīng)的基本操作，如液滴分配、分離、混合和儲(chǔ)存，具體結(jié)構(gòu)如圖1所示。雖然基于介電濕潤(rùn)的數(shù)字微流控技術(shù)非常適用于生化分析、臨床診斷、食品安全和環(huán)境監(jiān)測(cè)等領(lǐng)域，但這些都需要建立在系統(tǒng)級(jí)別的設(shè)計(jì)方法的基礎(chǔ)上來(lái)實(shí)現(xiàn)的。

圖1 數(shù)字微流控芯片結(jié)構(gòu)

隨著數(shù)字微流控生物芯片的應(yīng)用越來(lái)越廣泛，往往需要在同一個(gè)芯片上實(shí)現(xiàn)不同種類的生化分析操作的協(xié)同運(yùn)作，這極大地增加了芯片的結(jié)構(gòu)復(fù)雜性。傳統(tǒng)數(shù)字微流控生物芯片所采用的全定制設(shè)計(jì)制作技術(shù)擴(kuò)展性差，而且2D電極陣列的尺寸限制了片上并行操作的數(shù)量，同時(shí)，生化檢驗(yàn)中各操作之間的功能依賴性在很大程度上也限制了操作的并行性。以上各種問(wèn)題的出現(xiàn)使得傳統(tǒng)數(shù)字微流控生物芯片的全定制設(shè)計(jì)技術(shù)已經(jīng)遠(yuǎn)不適用于大規(guī)模的生化分析。因此，迫切需要計(jì)算機(jī)輔助設(shè)計(jì)來(lái)優(yōu)化數(shù)字微流控生物芯片的結(jié)構(gòu)，減少人為干預(yù)，提高芯片的利用率及效率[6～8]?，F(xiàn)場(chǎng)可編程控門(mén)陣列[9]（field-programmable gate array, FPGA）是一種高密度的電子可編程邏輯器件，具有用戶可重復(fù)定義的邏輯功能，即具有動(dòng)態(tài)重構(gòu)的特點(diǎn)。受數(shù)字微流控芯片本身尺寸的限制，為使其能夠完成較為復(fù)雜的生化分析，數(shù)字微流控芯片需要具有動(dòng)態(tài)重構(gòu)特性，即在不同的時(shí)間范圍內(nèi)可以共用一塊相同的微流控電極陣列區(qū)域以完成多種不同的任務(wù)。正是由于這一特性的存在，數(shù)字微流控芯片的陣列結(jié)構(gòu)得以重新調(diào)整，以便滿足不同的生化分析檢驗(yàn)要求，進(jìn)而降低芯片設(shè)計(jì)及使用成本，提高芯片使用效率，因此這一特性對(duì)于可重復(fù)使用的生物芯片來(lái)說(shuō)至關(guān)重要。通過(guò)微控制器編程，可以在任意時(shí)刻獨(dú)立地控制任一液滴在芯片上移動(dòng)至指定位置，因此數(shù)字微流控生物芯片與FPGA在動(dòng)態(tài)重構(gòu)方面不僅具有許多相似之處，而且前者比后者具有更為顯著的可編程能力。這是因?yàn)镕PGA在互連以及邏輯塊方面的可編程能力是受限的，而數(shù)字微流控電極陣列單元應(yīng)該不僅可以用來(lái)儲(chǔ)存液滴、完成相應(yīng)的基本操作（如液滴輸運(yùn)、混合及分離等），而且片上的存儲(chǔ)單元、液滴混合器和分離器可以隨時(shí)創(chuàng)建、刪除并重置，這會(huì)使我們能夠創(chuàng)建極其靈活高效的生化分析系統(tǒng)。因此，如何利用計(jì)算機(jī)輔助設(shè)計(jì)來(lái)實(shí)現(xiàn)片上系統(tǒng)分區(qū)、資源配置以及調(diào)度是面向生化分析等應(yīng)用的數(shù)字微流控芯片系統(tǒng)級(jí)設(shè)計(jì)亟需解決的一大問(wèn)題。因此，受FPGA思想的啟發(fā)，針對(duì)2D介電濕潤(rùn)的數(shù)字微流控生物芯片，本文提出了一種架構(gòu)級(jí)結(jié)構(gòu)布局綜合設(shè)計(jì)優(yōu)化算法用于解決資源受限的項(xiàng)目調(diào)度問(wèn)題。

1 片上系統(tǒng)分區(qū)

實(shí)現(xiàn)數(shù)字微流控生物芯片的架構(gòu)級(jí)布局綜合設(shè)計(jì)的前提是對(duì)芯片電極陣列進(jìn)行分區(qū)并生成分區(qū)圖。所謂分區(qū)，就是對(duì)芯片電極陣列進(jìn)行功能區(qū)域劃分，不同區(qū)域用來(lái)完成不同的液滴操作。而分區(qū)圖是一個(gè)虛擬地圖，是片上不同功能區(qū)域（如混合區(qū)域，或稱為混合器）隨時(shí)序變化的位置，由設(shè)計(jì)者生成并預(yù)先加載到微控制器中，而每個(gè)液滴起點(diǎn)、終點(diǎn)以及兩者間路徑也被編程輸入到微控制器中。微控制器可根據(jù)分區(qū)圖按次序地為電極施加電壓以驅(qū)動(dòng)液滴在其對(duì)應(yīng)的路徑上完成相應(yīng)的操作。圖2顯示了一個(gè)片上液滴存儲(chǔ)區(qū)域，即存儲(chǔ)器。其中一個(gè)單元格表示一個(gè)電極；藍(lán)色代表該存儲(chǔ)器儲(chǔ)存的液滴，為避免其他液滴與該液滴發(fā)生不必要的混合，液滴之間應(yīng)該至少相隔一個(gè)電極，因此深黑色方框內(nèi)部區(qū)域?qū)儆诟綦x區(qū)域，將該液滴與其他液滴隔離，其他液滴只能沿圖2所示點(diǎn)劃線（通訊路徑）在該液滴周圍輸運(yùn)。該存儲(chǔ)器只是數(shù)字微流控生物芯片上的一個(gè)分區(qū)。隨著時(shí)間的延續(xù)，當(dāng)有新的分區(qū)圖被加載到微控制器中，該數(shù)字微流控芯片就會(huì)發(fā)生重構(gòu)。圖3顯示了10×10數(shù)字微流控電極陣列的一種分區(qū)圖，包含兩個(gè)存儲(chǔ)器、一個(gè)混合器、一個(gè)液滴加載區(qū)和一個(gè)廢液回收區(qū)。

圖2 片上液滴存儲(chǔ)器

圖3 分區(qū)圖（含有兩個(gè)存儲(chǔ)器、一個(gè)混合器、一個(gè)液滴加載區(qū)和一個(gè)廢液回收區(qū)）

在生化分析檢驗(yàn)中，往往需要多個(gè)連續(xù)液滴完成相應(yīng)的功能操作。如果幾個(gè)連續(xù)液滴的路徑不交疊，那么這些路徑就被稱之為兼容路徑。液滴在兼容路徑上的操作就可以并行進(jìn)行；反之，如果路徑不兼容，相應(yīng)的液滴操作就必須依次進(jìn)行。一個(gè)數(shù)字微流控芯片上的分區(qū)圖不同，完成同一生化檢驗(yàn)的時(shí)間也不同。因此，本文的目的在于在資源受限和操作依賴性的約束下，選擇一種架構(gòu)級(jí)布局設(shè)計(jì)方案，對(duì)檢測(cè)操作進(jìn)行調(diào)度并將其綁定到指定數(shù)量的片上資源上，最大限度地對(duì)這些檢測(cè)操作進(jìn)行并行處理，以最小化生化檢驗(yàn)的完成時(shí)間。在液滴的所有基本操作中，液滴混合和分離操作耗時(shí)較長(zhǎng)，而液滴輸運(yùn)耗時(shí)極短，在此忽略液滴輸運(yùn)時(shí)間，只考慮液滴加載、混合和分離時(shí)間。同時(shí)，我們將兩個(gè)連續(xù)重構(gòu)之間的時(shí)間跨度分割成多個(gè)相同長(zhǎng)度的時(shí)隙。每個(gè)時(shí)隙的長(zhǎng)度均等于一個(gè)生化檢驗(yàn)中各操作所需時(shí)間的最大公約數(shù)。例如，如果液滴加載時(shí)間為2秒，液滴混合操作的時(shí)間為5秒，而液滴分離操作的時(shí)間為3秒的話，那么設(shè)置時(shí)隙大小為1秒。因此，液滴加載需要2個(gè)時(shí)隙，液滴混合需要5個(gè)時(shí)隙，液滴分離需要3個(gè)時(shí)隙。通過(guò)這種方式，我們將連續(xù)的液滴操作數(shù)字化，微控制器在每個(gè)時(shí)隙結(jié)束時(shí)會(huì)啟動(dòng)或完成某個(gè)操作。

2 構(gòu)架級(jí)調(diào)度模型的建立

本文采用數(shù)據(jù)流圖來(lái)表達(dá)數(shù)字微流控生物芯片上生化檢測(cè)的調(diào)度問(wèn)題，并建立該問(wèn)題的數(shù)學(xué)模型。生化分析檢驗(yàn)中每一步都可以用單個(gè)或一組基本液滴操作表示，而這樣的一個(gè)基本操作對(duì)應(yīng)數(shù)據(jù)流圖中的一個(gè)節(jié)點(diǎn)。由節(jié)點(diǎn)u到節(jié)點(diǎn)v的有向邊則表示與節(jié)點(diǎn)u和v相對(duì)應(yīng)的操作之間的依賴關(guān)系，即與u對(duì)應(yīng)的操作必須在與v對(duì)應(yīng)的操作之前執(zhí)行。圖4給出了含有7個(gè)基本操作的數(shù)據(jù)流圖，這7個(gè)操作分別是4個(gè)液滴加載操作和3個(gè)液滴混合操作。

圖4 數(shù)據(jù)流圖

生化檢測(cè)調(diào)度問(wèn)題可以看做是0-1整數(shù)線性規(guī)劃問(wèn)題，因此，具體分析過(guò)程如下所示：

設(shè)xi,j為二進(jìn)制變量，則：

其中，1≤i≤N，N表示生化檢驗(yàn)中的液滴操作總數(shù)（即數(shù)據(jù)流圖中的節(jié)點(diǎn)數(shù)）；1≤j≤M，M表示松弛時(shí)間因子，即為所有操作時(shí)隙數(shù)量總和。由于每個(gè)檢測(cè)操作只能被調(diào)度一次，因此：

操作i的開(kāi)始時(shí)間Si可以用一個(gè)變量集{xi1, xi2,···,xim,}表示。假設(shè)每個(gè)時(shí)隙的長(zhǎng)度為一個(gè)單位，那么操作i的開(kāi)始時(shí)間為：

若操作i的持續(xù)時(shí)間為di，且操作i和i+1之間存在依賴關(guān)系，那么：

對(duì)于數(shù)字微流控生物芯片來(lái)說(shuō)，除了上述的各操作間的依賴性這一約束以外，還有受芯片電極陣列尺寸限制的資源約束。假設(shè)nk為由分區(qū)圖所確定的同一時(shí)隙內(nèi)k型操作數(shù)量的最大值，則k型操作的資源約束表達(dá)為：

所謂生化檢驗(yàn)操作調(diào)度優(yōu)化的目標(biāo)就是確定每一個(gè)檢測(cè)操作的開(kāi)始時(shí)間，以使所有操作的完成總時(shí)間達(dá)到最短。因此：

在最大限度地利用并行性來(lái)完成生化檢測(cè)的基礎(chǔ)上，上述優(yōu)化目標(biāo)可轉(zhuǎn)化為最小化最后一組并行操作中持續(xù)時(shí)間最長(zhǎng)的那個(gè)操作的完成時(shí)間。假設(shè)最后一組有l(wèi)（1≤l≤N）個(gè)液滴操作并行執(zhí)行，這l個(gè)操作中的持續(xù)時(shí)間最長(zhǎng)的那個(gè)操作的完成時(shí)間為T(mén)l，則優(yōu)化目標(biāo)轉(zhuǎn)化為：

其中，nl表示最后一組基本操作數(shù)。

3 操作調(diào)度優(yōu)化

以聚合酶鏈?zhǔn)椒磻?yīng)（PCR）為例，研究數(shù)字微流控生物芯片的操作調(diào)度問(wèn)題，并利用整數(shù)線性規(guī)劃法來(lái)解決及優(yōu)化該問(wèn)題。

PCR主要包含8種樣本試劑，分別為T(mén)ris-HCl、KCl、MgCl、明膠（gelatin）、三磷酸脫氧核苷酸混合液（dNTP）、引物、DNA模板以及Taq DNA聚合酶。PCR在數(shù)字微流控生物芯片上實(shí)施，要執(zhí)行三大步驟，分別為樣本試劑加載、樣本混合（包含樣本液滴輸運(yùn)、混合和分離三個(gè)基本操作）和樣本混合物移出芯片以便完成后續(xù)加熱操作，其具體實(shí)施步驟如下所示：

1）加入Tris-HCl；2）加入KCl，并與Tris-HCl充分混合；3）加入MgCl，并至充分混合；4）加入明膠，并至充分混合；5）三磷酸脫氧核苷酸混合液（dNTP），并至充分混合；6）加入引物，并至充分混合；7）加入DNA模板，并至充分混合；8）加入Taq DNA聚合酶，并至充分混合。

如果圖3即為實(shí)施PCR的數(shù)字微流控生物芯片的分區(qū)圖的話，其對(duì)應(yīng)的數(shù)據(jù)流圖如圖5所示。

圖5 與圖3分區(qū)圖對(duì)應(yīng)的數(shù)據(jù)流圖

這里假設(shè)液滴加載操作和液滴混合操作的完成時(shí)間分別為2秒和6秒，而液滴輸運(yùn)時(shí)間極短，忽略不計(jì)。因此，一個(gè)單位時(shí)隙長(zhǎng)度即為2秒。注意，通常在生化檢驗(yàn)中，液滴混合操作之后往往都要進(jìn)行液滴分離操作，因此這里液滴混合操作的完成時(shí)間已包含液滴分離操作的時(shí)間。根據(jù)圖3所示的分區(qū)圖以及圖5數(shù)據(jù)流圖中所表達(dá)的各操作之間的依賴性，可以得到與之對(duì)應(yīng)的操作調(diào)度方案，如表1所示。從圖3中可以定義7條基本操作路徑，分別為：1）路徑1：A-E-H-J-D1；2）路徑2：A-EH-K-D2；3）路徑3：A-E-F-B；4）路徑4：A-E-G-C；5）路徑5：B-P-J-H-K-D2；6）路徑6：C-Q-K-D2；7）路徑7：D2-K-Q-L。

表1 基于圖3和圖5（1個(gè)混合器）的PCR操作調(diào)度方案1

表1中各時(shí)間表示從第一步開(kāi)始到所在步驟完成時(shí)所消耗的時(shí)間。根據(jù)圖3分區(qū)圖以及圖5數(shù)據(jù)流圖，表1得到的PCR反應(yīng)操作調(diào)度方案1的完成時(shí)間為46s，而總操作數(shù)為15個(gè)，包含8個(gè)樣本加載操作和7個(gè)液滴混合操作。對(duì)應(yīng)的一個(gè)單位時(shí)隙長(zhǎng)度為2秒，因此，需要23個(gè)時(shí)隙用于該P(yáng)CR操作調(diào)度方案的完成。那么，該方案對(duì)應(yīng)的整數(shù)線性規(guī)劃模型將x1,j，x2,j，…，x15,j來(lái)表示決策變量，其中j=1,2,…,23。因此，15個(gè)操作的開(kāi)始時(shí)間分別為：

另外，根據(jù)圖5數(shù)據(jù)流圖中各操作之間的依賴關(guān)系，應(yīng)有：

其中，d1=d2=…d8=2s，d9=d10=…d15=6s。

這種操作調(diào)度方案對(duì)應(yīng)的資源約束表達(dá)為：

圖6 兩個(gè)混合器的分區(qū)圖

圖7 圖6分區(qū)圖對(duì)應(yīng)的數(shù)據(jù)流圖

圖8 三個(gè)混合器的分區(qū)圖

為了優(yōu)化操作調(diào)度方案，重新生成兩個(gè)分區(qū)圖（如圖6和圖8所示），分別帶有兩個(gè)和三個(gè)液滴混合器，圖7表示與圖6含有兩個(gè)液滴混合器的分區(qū)圖相對(duì)應(yīng)的數(shù)據(jù)流圖。根據(jù)圖6和圖7，得到與其對(duì)應(yīng)的PCR反應(yīng)操作調(diào)度方案2，如表2所示，其對(duì)應(yīng)的液滴輸運(yùn)路徑分別為：1）路徑1：A-E-P-Q-J-D1；2）路徑2：A-E-P-Q-K-D2；3）路徑3：A-E-F-B1；4）路徑4：A-E-G-B2；5）路徑5：B1-J-K-D2；6）路徑6：B2-K-Q-L；7）路徑7：D2-KQ-L。

由表2可知，利用兩個(gè)液滴混合器來(lái)實(shí)施PCR反應(yīng)所需完成時(shí)間只有32s，與調(diào)度方案1相比，完成時(shí)間縮短了30.4%。同樣方法分析圖8帶有三個(gè)液滴混合器的分區(qū)圖，可得PCR反應(yīng)的完成時(shí)間也是32s，因此，對(duì)于10×10的數(shù)字微流控電極陣列來(lái)說(shuō)，兩個(gè)液滴混合器已經(jīng)可以實(shí)現(xiàn)PCR反應(yīng)中最大程度的并行性，完成時(shí)間也達(dá)到最短。

4 結(jié)論

針對(duì)二維數(shù)字微流控生物芯片，本文提出了一種架構(gòu)級(jí)結(jié)構(gòu)布局設(shè)計(jì)以及操作調(diào)度優(yōu)化方案。采用與FPGA類似的方法，對(duì)芯片進(jìn)行系統(tǒng)分區(qū)、資源配置以及操作調(diào)度。利用0～1整數(shù)線性規(guī)劃法建立生化檢驗(yàn)?zāi)Ｐ?，通過(guò)將不同的系統(tǒng)分區(qū)圖輸入微控制器，自動(dòng)且最大程度地實(shí)現(xiàn)了并行性，大大縮短了生化檢驗(yàn)的完成時(shí)間，優(yōu)化了聚合酶鏈?zhǔn)椒磻?yīng)操作調(diào)度方案。

表2 基于圖6和圖7（兩個(gè)混合器）的PCR操作調(diào)度方案2