二維重構(gòu)數(shù)字微流控生物芯片的架構(gòu)級布局設(shè)計及調(diào)度優(yōu)化

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

0 引言

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

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

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

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

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

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

圖2 片上液滴存儲器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這里假設(shè)液滴加載操作和液滴混合操作的完成時間分別為2秒和6秒，而液滴輸運時間極短，忽略不計。因此，一個單位時隙長度即為2秒。注意，通常在生化檢驗中，液滴混合操作之后往往都要進(jìn)行液滴分離操作，因此這里液滴混合操作的完成時間已包含液滴分離操作的時間。根據(jù)圖3所示的分區(qū)圖以及圖5數(shù)據(jù)流圖中所表達(dá)的各操作之間的依賴性，可以得到與之對應(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個混合器）的PCR操作調(diào)度方案1

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

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

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

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

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

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

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

為了優(yōu)化操作調(diào)度方案，重新生成兩個分區(qū)圖（如圖6和圖8所示），分別帶有兩個和三個液滴混合器，圖7表示與圖6含有兩個液滴混合器的分區(qū)圖相對應(yīng)的數(shù)據(jù)流圖。根據(jù)圖6和圖7，得到與其對應(yīng)的PCR反應(yīng)操作調(diào)度方案2，如表2所示，其對應(yīng)的液滴輸運路徑分別為：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可知，利用兩個液滴混合器來實施PCR反應(yīng)所需完成時間只有32s，與調(diào)度方案1相比，完成時間縮短了30.4%。同樣方法分析圖8帶有三個液滴混合器的分區(qū)圖，可得PCR反應(yīng)的完成時間也是32s，因此，對于10×10的數(shù)字微流控電極陣列來說，兩個液滴混合器已經(jīng)可以實現(xiàn)PCR反應(yīng)中最大程度的并行性，完成時間也達(dá)到最短。

4 結(jié)論

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

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