石運琪，王英志，唐雁峰

（長春理工大學(xué)電子信息工程學(xué)院，吉林 長春 130022）

0 引 言

連續(xù)流微流控生物芯片被稱為片上實驗室（lab on chip，LOC），有著小型化、自動化、高通量、檢測試劑消耗少等優(yōu)點，有利于生物檢測、化學(xué)實驗的快速性和準確性。在應(yīng)用方面，微流控芯片可以進行免疫測定、臨床病理、快速測定原型、DNA提取和測序［1］等重要工作。微流控芯片的主體結(jié)構(gòu)由上、下2 層片基組成聚甲基丙烯酸甲酯（polymethyl methacrylate，PMMA）、聚二甲基硅氧烷（polydimethylsiloxane，PDMS）、玻璃等材料，包括微通道、混合器件、微閥、反應(yīng)器、進出口等結(jié)構(gòu)，其中，微閥不僅可以在微流道交叉點處控制實驗試劑的通過與停止，更決定著整體芯片的制造成本，精密的微流控芯片可能包含成百上千個微閥。

微流控芯片的設(shè)計具有極強的復(fù)雜性和易錯性，傳統(tǒng)設(shè)計幾乎都是技術(shù)人員手動完成，過程繁瑣且復(fù)雜，這一過程耗時耗力，極大影響了微流控芯片技術(shù)的發(fā)展，芯片布局自動化設(shè)計尤為重要。文獻［2］中所提出的算法收斂速度過慢，且器件放置方法單一，過程冗余，無法適應(yīng)布局條件過于龐大的設(shè)計；文獻［3］中在布局布線時沒有考慮流道交叉點的重要性，建模時基于基點設(shè)計沒有以芯片面積為前提，降低了算法發(fā)現(xiàn)更有效器件放置的可能性；文獻［4］中將器件放置和流道布線視為相互獨立的設(shè)計，且過程復(fù)雜度過大，損害了芯片設(shè)計的質(zhì)量；文獻［5］采用的是普遍的啟發(fā)式技術(shù)，通常以任意方式便利搜索空間，不能保證根據(jù)不同質(zhì)量標準確定好的設(shè)計，并且算法只最小化了所構(gòu)造的steiner樹直徑，可能導(dǎo)致芯片設(shè)計失?。晃⒘骺匦酒O(shè)計中，芯片面積是主要權(quán)重之一，文獻［6］中沒有對其考慮，提高了芯片布局方案的缺陷；文獻［7］中忽略了器件布局的關(guān)鍵性，在芯片自動化設(shè)計中只進行了流道布線，造成了算法整體運行時間過長的不足。

本文在考慮器件布局和流道布線的基礎(chǔ)上，以芯片總面積、總流道長度、流道交叉點為維度，對微流控芯片進行自動化設(shè)計，當生物檢測實驗過于復(fù)雜時，本文通過快速序列對（fast sequence pair，F(xiàn)ast SP）算法進行器件初始布局，再結(jié)合改進的模擬退火（simulated annealing，SA）算法進行芯片布圖設(shè)計。

1 微流控芯片工作原理

微流控芯片通過半導(dǎo)體的加工技術(shù)來構(gòu)建整體流道系統(tǒng)，將生物實驗和分析過程從實驗室轉(zhuǎn)移到由眾多反應(yīng)器件和流道構(gòu)成的微小芯片上，加入反應(yīng)試劑，通過外部硬件設(shè)施（微機械泵、電水力泵）驅(qū)動，試劑為連續(xù)流體，于芯片上形成反應(yīng)，如圖1所示。

圖1 工作原理示意

2 微流控芯片的結(jié)構(gòu)設(shè)計算法

2.1 結(jié)構(gòu)設(shè)計

結(jié)構(gòu)設(shè)計建模如圖2所示，其流程主要包括：1）生成生化實驗的流程；2）進行器件整理匯總；3）器件布局；4）流道布線；5）確定微閥數(shù)量、流道總長度、芯片總面積。

圖2 微流控芯片結(jié)構(gòu)設(shè)計建模

通過本文算法，將器件的集合、器件的連接關(guān)系、器件管道之間的約束作為前提條件，在一定工作時間內(nèi)達到微流控芯片總面積、微流道總長度的解相對優(yōu)秀的同時，減少微流道的交叉數(shù)量（減少芯片微流道、混合器件、反應(yīng)器件等結(jié)構(gòu)內(nèi)的微閥數(shù)量），實驗最終目的是降低微流控芯片設(shè)計的實驗復(fù)雜度，提高芯片質(zhì)量，同時降低芯片制造成本。

2.2 算法設(shè)計

本文使用Fast SP算法［8］表示器件布局的初始方案，根據(jù)前提約束條件，通過SA 算法調(diào)節(jié)器件之間間距，采用Dijkstra算法布線。在布局的初始階段，如果直接進行微通道布線，會導(dǎo)致實驗冗余，繼而可能引起實驗失敗，芯片制造質(zhì)量下降等問題，因此，本文算法在得到器件初始布局后即計算芯片總面積，根據(jù)前提條件中的器件連接關(guān)系進行連接，算出器件之間的曼哈頓距離，將其作為流道總長度的權(quán)值，再計算出器件連接后線段的交叉點數(shù)量作為最終布線后交叉點的權(quán)值。

2.3 Fast SP

Fast SP算法相比于傳統(tǒng)的序列對算法降低了解碼時間的復(fù)雜度，在融合了最長公共子序列（longest common subsequence，LCS）算法［9］后，加快了評估序列對布局的時間，LCS算法有巨大的實用性［10～12］。從序列對到1 個布圖，給出1個序列對，需要得到：1）布圖的起始點，2）每個器件的寬和高，3）布圖的布局方向；才可以生成1 個布圖。起始點是指開始的位置，即第一個器件放置的位置，計算器件之間相對位置時，需要器件的尺寸，布局方向能將芯片面積達到最小化。本文中，采用從左下到右上的布局方案。

從序列對生成布圖和尋找2個序列中的最長加權(quán)公共子序列是相關(guān)的，每一個器件的x坐標就相當于計算LCS（S+，S-），確定每個器件的y坐標就相當于計算LCS（，S-），為S+的逆序列。

器件約束關(guān)系：序列對（S+，S-）中的每個序列單元表示每一個器件，給定2個器件a和器件b。在序列S+和序列S-中，如果a 均在b 之前，則a 在b 左邊；若在序列S+中，a在b之前，在序列S-中，a在b之后，則a在b的上面。

序列對計算算法：

輸入：序列對＜S+，S-＞，n個器件的寬度（長度）widths［n］（heights［n］）

輸出：x（y）坐標xcoords（ycoords），布圖結(jié)果的W×H尺寸

1）for（i＝1 ton）

2）weights［i］＝widths［i］∥器件寬度的權(quán)重

3）（xcoords，W）＝LCS（S+，S-，weights） ∥x坐標，總寬度W

4）for（i＝1 ton）

5）weights［i］＝heights［i］∥器件高度的權(quán)重

7）（ycoords，H）＝LCS（，S-，weights）∥y坐標，總高度H步驟1，2 對n個器件的寬度進行初始化weights。步驟3尋找S+和S-的最長加權(quán)公共子序列，計算每個器件的x坐標。步驟4，5對n個器件的高度進行初始化heights。步驟6得到S+的逆序列。步驟7 根據(jù)得到與S-的加權(quán)最長加權(quán)公共子序列算法計算每個器件的y坐標。

LCS算法：

輸入：序列S1和S2，n個器件的權(quán)重weights［n］

輸出：每個模塊的位置positions，總長度L

1）計算2個序列S1和S2的加權(quán)LCS 的寬度，利用矢量block_order記錄每個器件在S2中的索引。

2）將矢量lengths初始化為0，儲存每個器件的最大量（長或?qū)挘?/p>

3）定義變量block為S1中的當前器件，index是當前器件在S2中的索引。所有在block左邊的快都被安排到長度為lengths［block］區(qū)間內(nèi)，而block隨后放置。

4）更新布局的總長度lengths，lengths［n］表示n個器件都被確定后的總長度。

5）如果lengths［j］超過當前長度，則更新。

提取S1＝S+，S2＝S-，weights ＝widths 時的LCS 算法，定義布圖的x坐標。提取S1＝SR+，S2＝S-，weights ＝heights時的LCS算法，定義布圖的y坐標。

例子：從序列對到一個布圖

輸入：1）隨機給出序列對S+＝＜acdbe ＞，S-＝＜cdaeb ＞；2）布局方向：自左下開始；3）布局起點（0，0）；4）器件abcde。

求解過程：widths［a b c d e］＝［8 4 4 4 4］

heights［a b c d e］＝［4 3 5 5 6］

求出x的坐標：

S1＝S+＝＜acdbe ＞，S2＝S-＝＜cdaeb ＞

weights［a b c d e］＝widths［a b c d e］＝［8 4 4 4 4］

block_order［a b c d e］＝［3 5 1 2 4］

lenghts ＝［0 0 0 0 0］

步驟（1）迭代i＝1：block ＝a

index ＝block_order［a］＝3

positions［a］＝length［index］＝lengths［3］＝0 ∥（計算當前器件位置）

t_span ＝positions［a］+weight［a］＝0 +8 ＝8 ∥（確定當前器件長度）

從index ＝3到n＝5 更新lengths矢量；lengths ＝［0 0 8 8 8］。步驟（2）～步驟（5）迭代開始，重復(fù)上述操作，x坐標：positions［a b c d e］＝［0 8 0 4 8］，求得布圖的寬度W＝lengths［5］＝12

求出y坐標：

S1＝SR+＝＜ebdca ＞，S2＝S-＝＜cdaeb ＞

weights［a b c d e］＝heights［a b c d e］＝［4 3 5 5 6］

block_order［a b c d e］＝［3 5 1 2 4］

lenghts ＝［0 0 0 0 0］。步驟（1）～步驟（5）依照尋找x坐標的方式迭代5次，布圖的高度H＝lengths［5］＝9

輸出：布圖面積大小為：W＝12 ×9。各器件左下角坐標為：a（0，5）b（8，6）c（0，0）d（4，0）e（8，0），結(jié)果如圖3。

圖3 器件示例布局結(jié)果

2.4 改進SA算法

本文對SA算法進行改進也是從這2個方面入手［13～16］。

1）SA在溫度冷卻控制方法主要分2種：快速降溫方式（RSA）：T＝T0／log（1 +N）；一般降溫方式（CSA）：T＝qT0+k。針對傳統(tǒng)SA起始降溫速度過快，不能得到全局最優(yōu)解的缺點，本文所提出的改進SA 算法從降溫速率上進行改進，降溫速率函數(shù)如下

式中T0為初始溫度，N為外循環(huán)迭代次數(shù)，T為當前溫度。

由圖4可知，在迭代過程中，本文所提出的改進SA 算法在高溫階段下降緩慢，實現(xiàn)了算法的全局搜索，有利于最優(yōu)解的產(chǎn)生。

圖4 3 種降溫函數(shù)曲線

2）降溫速度慢易造成全局收斂速度緩慢，利用Fast SP算法優(yōu)先提出方案與SA 算法相結(jié)合的方法進行融合改進，加快收斂速度，對Fast SP算法方法改進如下：利用逆轉(zhuǎn)變換，選擇2個器件單元后，逆轉(zhuǎn)這2個單元之間所有的單元；選擇3個器件單元，將2個器件單元之間的單元調(diào)換到第3個單元后面。

改進SA 算法流程：利用器件的集合和器件連接關(guān)系為前提，以Fast SP算法求得的器件布局方案為輸入，為達到良好布局布線結(jié)果，將器件mi 與它右側(cè)或上方的器件mj之間的距離定義為rx和ax。將所有器件集合間距的寬和高定義為WX和HY。集合WX和HY之間元素的約束條件為［emin，emax］。WX和HY構(gòu)成初始解S。繼而進行SA算法環(huán)節(jié)，需要設(shè)置的主要控制參數(shù)有初始溫度為T、外循環(huán)次數(shù)N、結(jié)束溫度Tend、當前溫度T0、以及鏈長L（每個T時的迭代次數(shù)）。

以上述已知條件為前提：1）初始化WX和HY，emin＜rx，rx＜emax。2）設(shè)置狀態(tài)變量S＝（S+，S-，WX，HY），設(shè)置初始溫度T，當初始溫度大于最低溫度時，迭代開始。3）調(diào)節(jié)狀態(tài)變量S→S′，隨機生成變量，生成和，與emin，emax進行比較，當＜emin時，令emin＝；當＞emax時，令emax＝。同理求得。4）利用Metropolis 準則df＝E（S′）-E（S），如果df＜0，則概率1接受新的布局，否則概率exp（-df／T）接受新的布局。5）利用新的降溫速率函數(shù)進行降溫，若T0小于結(jié)束溫度，則停止迭代輸出當前結(jié)果。

對SA處理器件布局進行仿真實驗，如圖5，實驗樣本來自現(xiàn)有算法［17］。

圖5 2 種算法下器件布局設(shè)計的平均收斂速度

本文提出改進SA算法不但收斂性快，相較于傳統(tǒng)SA算法，且在面臨較多器件時，仍能得到較優(yōu)的解。

本文設(shè)置參數(shù)：emin＝2，emax＝4，T＝1 200，Tend＝10-4，L＝100。評估芯片布局質(zhì)量函數(shù)

式中A為布局后芯片面積，B為流道交叉點數(shù)量，C為流道線段長度，C2為總線段的平方。將α的權(quán)重值定為2，將β的權(quán)重值定位200，將γ的權(quán)重值定位40。

利用Dijkstra 算法［18，19］找出布局后的最短路徑，算法的輸入主要包括：1）非負邊權(quán)重圖G（WX，HY）。2）一個開始源節(jié)點s。3）一個目標結(jié)束節(jié)點t。引入2個集合：M（包含已求得最短路徑的點和最短路徑長度），N（未求出的最短路徑的點和該點到源節(jié)點距離）。初始化2個集合，從N集合中找出路徑最短的點，加入M集合，更新N集合中器件，循環(huán)迭代，直至遍歷結(jié)束，找到微流控芯片最佳布線結(jié)果。

3 實驗結(jié)果與分析

本文選取6組測試實例，實驗結(jié)果表明，本文的綜合算法明顯優(yōu)于手工布局的方法，與現(xiàn)有算法［17］進行實驗結(jié)果時，芯片總面積平均減小19.7 %，流道總長度平均減小14.1%，流道交叉點數(shù)量平均減少25.8%。由于芯片布局問題屬于非確定性多項式（non-deterministic polynomial，NP）完全問題，是多項式復(fù)雜程度的非確定性問題，在器件達到一定數(shù)量時，無法得到最優(yōu)解，由表1 可看出，本文的綜合算法可以在一定時間內(nèi)得到較高質(zhì)量的解，從而滿足設(shè)計需要。

4 結(jié) 論

根據(jù)實驗結(jié)果表明，本文所提出的算法可以滿足微流控生物芯片的自動化設(shè)計需求，通過芯片面積的減少、流道的縮短、交叉點數(shù)量的下降，驗證了本文方法在微流控芯片在結(jié)構(gòu)設(shè)計上的有效性和優(yōu)越性。