完全可編程閥門陣列生物芯片下容錯導(dǎo)向的高階綜合算法

朱予涵; 劉博文; 黃興; 劉耿耿

doi:10.11999/JEIT240049

完全可編程閥門陣列生物芯片下容錯導(dǎo)向的高階綜合算法

doi: 10.11999/JEIT240049

朱予涵^{1, 2, 3},
劉博文^{1, 2, 3},
黃興⁴,
劉耿耿^{1, 2, 3, ,}

1.
福州大學(xué)計算機(jī)與大數(shù)據(jù)學(xué)院福州 350116
2.
大數(shù)據(jù)智能教育部工程研究中心福州 350116
3.
福建省網(wǎng)絡(luò)計算與智能信息處理重點(diǎn)實驗室福州 350116
4.
西北工業(yè)大學(xué)計算機(jī)學(xué)院西安 710072

基金項目: 福建省杰出青年科學(xué)基金(2023J06017)

詳細(xì)信息

作者簡介:
朱予涵：女，博士生，研究方向為微流體生物芯片設(shè)計自動化

劉博文：男，博士生，研究方向為微流體生物芯片設(shè)計自動化

黃興：男，博士，教授，研究方向為微流體生物芯片及超大規(guī)模集成電路設(shè)計自動化

劉耿耿：男，博士，教授，研究方向為微流體生物芯片及超大規(guī)模集成電路設(shè)計自動化

通訊作者:
劉耿耿　liugenggeng@fzu.edu.cn

中圖分類號: TN402; TP391.41
計量
- 文章訪問數(shù): 163
- HTML全文瀏覽量: 84
- PDF下載量: 23
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2024-01-24
- 修回日期: 2024-09-04
- 網(wǎng)絡(luò)出版日期: 2024-09-17
- 刊出日期: 2024-11-01

Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips

ZHU Yuhan^{1, 2, 3},
LIU Bowen^{1, 2, 3},
HUANG Xing⁴,
LIU Genggeng^{1, 2, 3
, ,}

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350116, China
2.
Engineering Research Center of Big Data Intelligence, Ministry of Education, Fuzhou 350116, China
3.
Fujian Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou 350116, China
4.
School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China

Funds: Fujian Science Fund for Distinguished Young Scholars (2023J06017)

摘要

摘要: 作為新一代流式微流控生物芯片，完全可編程閥門陣列(FPVA)生物芯片具有更高的靈活性和可編程性，已經(jīng)成為一種流行的生物化學(xué)實驗平臺。然而，由于環(huán)境或人為因素，制造過程中通常存在一些物理故障，如通道阻塞和泄漏，這無疑會影響生化檢測的結(jié)果。此外，高階綜合作為架構(gòu)綜合的首要階段，其結(jié)果的質(zhì)量直接影響著后續(xù)設(shè)計的優(yōu)劣。因此，該文首次研究了FPVA生物芯片高階綜合過程中的容錯問題，提出了單元功能轉(zhuǎn)換方法、雙向冗余方法、故障映射方法等動態(tài)容錯技術(shù)，為實現(xiàn)高效的容錯設(shè)計提供了技術(shù)保障。通過將這些技術(shù)集成到高階綜合設(shè)計中，進(jìn)一步實現(xiàn)了一種高質(zhì)量的FPVA生物芯片下容錯導(dǎo)向的高階綜合算法，包括故障感知的實時綁定策略和故障感知的優(yōu)先級調(diào)度策略，為實現(xiàn)芯片架構(gòu)的魯棒性和檢測結(jié)果的準(zhǔn)確性奠定了良好的基礎(chǔ)。實驗結(jié)果顯示，所提算法能夠得到一個FPVA生物芯片下高質(zhì)量且容錯的高階綜合方案，為后續(xù)實現(xiàn)容錯物理設(shè)計方案提供了有力保障。
- 微流控生物芯片 /
- 完全可編程閥門陣列 /
- 物理故障 /
- 容錯 /
- 高階綜合
Abstract: As a new generation of flow-based microfluidics, Fully Programmable Valve Array (FPVA) biochips have become a popular biochemical experimental platform that provide higher flexibility and programmability. Due to environmental and human factors, however, there are usually some physical faults in the manufacturing process such as channel blockage and leakage, which, undoubtedly, can affect the results of bioassays. In addition, as the primary stage of architecture synthesis, high-level synthesis directly affects the quality of sub-sequent design. The fault tolerance problem in the high-level synthesis stage of FPVA biochips is focused on for the first time in this paper, and dynamic fault-tolerant techniques, including a cell function conversion method, a bidirectional redundancy scheme, and a fault mapping method, are presented, providing technical guarantee for realizing efficient fault-tolerant design. By integrating these techniques into the high-level synthesis stage, a high-quality fault-tolerance-oriented high-level synthesis algorithm for FPVA biochips is further realized in this paper, including a fault-aware real-time binding strategy and a fault-aware priority scheduling strategy, which lays a good foundation for the robustness of chip architecture and the correctness of assay outcomes. Experimental results confirm that a high-quality and fault-tolerant high-level synthesis scheme of FPVA biochips can be obtained by the proposed algorithm, providing a strong guarantee for the subsequent realization of a fault-tolerant physical design scheme.
- Microfluidics biochips /
- Fully Programmable Valve Array (FPVA) /
- Physical faults /
- Fault tolerance /
- High-level synthesis

HTML全文

圖 1 FPVA架構(gòu)及其拓?fù)溥B接圖

下載: 全尺寸圖片幻燈片

圖 2 制造缺陷示例^[11]

下載: 全尺寸圖片幻燈片

圖 3 FPVA生物芯片高階綜合示例

下載: 全尺寸圖片幻燈片

圖 4 FPVA下容錯導(dǎo)向的高階綜合算法流程圖

下載: 全尺寸圖片幻燈片

圖 5 動態(tài)容錯技術(shù)示例

下載: 全尺寸圖片幻燈片

1 動態(tài)容錯綁定算法

輸入：FPVA單元集$C$，操作集$O$，組件數(shù)量為${N_M}$的組件庫$M$，物理故障位置${F_i}$(包括合并單元、故障單元及包含故障連接的單元)
輸出：一個容錯的綁定方案
//初始綁定階段
for each operation ${O_i}$ of $O$ do
Banding(${O_i}$,${M_j}$) = Random(0, ${N_M}$–1)；//將操作${O_i}$隨機(jī)綁定到一個組件${M_j}$
end for
for each cell ${C_i}$ of $C$ do
if ${C_i}$ == ${F_i}$ then
${C_i}$_state = –1；//標(biāo)記為不可用單元
Continue;
else
${C_i}$_state = 0；//標(biāo)記為空閑單元
Continue;
end if
end for
//綁定調(diào)整階段
for each module ${M_j}$ of M do
for each cell ${C_k}$ of ${M_j}$ do
if ${C_k}$_state == –1 then //${C_k}$為不可用單元
Construct_spare_module(${M_j}$)；//根據(jù)雙向冗余技術(shù)從空閑單元中選擇備用單元
Banding(${O_i}$,${M_j}$);
end if
if Done(${M_j}$) == True do //組件上的操作已執(zhí)行完成
${C_k}$_state = 0; //根據(jù)單元功能轉(zhuǎn)換將組件${M_j}$占據(jù)單元轉(zhuǎn)換為空閑單元
end if
end for
end for

下載: 導(dǎo)出CSV

2 動態(tài)容錯調(diào)度算法

輸入：FPVA單元集$C$, 操作集$O$，操作間的依賴關(guān)系，每個操作執(zhí)行時間$ {t_{\text{e}}}\left( {{O_j}} \right) $，和輸入流體，物理故障位置${F_i}$(包括故障單元以及包　含故障連接的單元)
輸出：一個容錯的調(diào)度方案
//初始調(diào)度順序生成
for each operation ${O_i}$ of $O$ do
${\text{pri}}\left( {{O_i}} \right) = \displaystyle\sum\nolimits_{{O_j} \in {\text{son}}\left( {{O_i}} \right)} {{t_{\text{e}}}\left( {{O_j}} \right) + {t_{\text{c}}} \times \left\| {{\text{son}}\left( {{O_i}} \right) - 1} \right\|} $；//計算操作${O_i}$的優(yōu)先級
end for
Sorting($O$)；//根據(jù)調(diào)度優(yōu)先級由大到小將操作排序
for each cell ${C_i}$ of $C$ do
if ${C_i}$ == ${F_i}$ then
${C_i}$_state = –1；//標(biāo)記為不可用單元
Continue;
else
${C_i}$_state = 0；//標(biāo)記為空閑單元
Continue;
end if
end for
//調(diào)度順序調(diào)整
for each operation ${O_i}$ of $O$ do
for each fluid ${r_j}$ of ${O_i}$ do
for each cell ${C_k}$ of ${r_j}$ do
if ${C_k}$_state == –1 then // ${C_k}$為不可用單元
Construct_spare_path(${r_j}$)；//根據(jù)雙向冗余技術(shù)從空閑單元中選擇備用單元
end if
if Reached (${r_j}$) == True do //輸入流體已到達(dá)目標(biāo)組件
${C_k}$_state = 0；//根據(jù)單元功能轉(zhuǎn)換將流體${r_j}$占據(jù)單元轉(zhuǎn)換為空閑單元
end if
end for
end for
end for

下載: 導(dǎo)出CSV

表 1 圖3對應(yīng)的綁定與調(diào)度方案

時間(s)	動作
$0$～$ {t_{\text{c}}} $	分別運(yùn)輸輸入流體${r_1}$, ${r_3}$, ${r_5}$到組件${M_1}$, ${M_2}$, ${M_3}$
$ {t_{\text{c}}} $～$2{t_{\text{c}}}$	分別運(yùn)輸輸入流體${r_2}$, ${r_4}$到組件${M_1}$, ${M_2}$
$2{t_{\text{c}}}$～($2{t_{\text{c}}} + 4$)	執(zhí)行混合操作${O_1}$, ${O_2}$
$\left( {2{t_{\text{c}}} + 4} \right)$～$\left( {3{t_{\text{c}}} + 4} \right)$	運(yùn)輸${O_1}$, ${O_2}$的混合產(chǎn)物到混合器${M_3}$
$\left( {3{t_{\text{c}}} + 4} \right)$～$\left( {3{t_{\text{c}}} + 8} \right)$	執(zhí)行混合操作${O_3}$

下載: 導(dǎo)出CSV

表 2 策略有效性對比結(jié)果

測試用例	(輸入流體數(shù)，輸出流體數(shù)，混合操作數(shù))	FPVA 尺寸	生物測定完成時間(s)			流體運(yùn)輸路徑總長度(mm)
測試用例	(輸入流體數(shù)，輸出流體數(shù)，混合操作數(shù))	FPVA 尺寸	基準(zhǔn)算法	本文算法	優(yōu)化(%)	基準(zhǔn)算法	本文算法	優(yōu)化(%)
PCR	(8,1,7)	$ \times $$8 \times 8$	14.5	13.8	4.8	56.9	54.4	4.4
IVD1	(12,6,6)	$8 \times 8$$ \times $	7.2	6.5	9.7	84.0	82.3	2.0
IVD2	(18,9,9)	$10 \times 10$$ \times $	8.8	8.4	4.5	174.3	171.3	1.7
ProteinSplit1	(14,2,12)	$10 \times 10$$ \times $	27.4	26.9	1.8	126.4	122.5	3.1
ProteinSplit2	(32,4,23)	$13 \times 13$	35.4	33.8	4.5	491.6	486.6	1.0
Synthetic1	(5,1,4)	$8 \times 8$	13.5	12.8	5.2	37.2	35.8	3.8
Synthetic2	(13,1,12)	$10 \times 10$$ \times $	22.6	21.8	3.5	121.6	116.8	3.9
Synthetic3	(18,1,17)	$12 \times 12$	28.1	27.4	2.5	217.6	210.7	3.2
Synthetic4	(22,1,21)	$13 \times 13$	27.4	26.6	2.9	312.6	305.4	2.3
Synthetic5	(27,1,26)	$13 \times 13$	29.9	28.7	4.0	386.9	377.2	2.5
平均值					4.3			2.8

下載: 導(dǎo)出CSV

表 3 與RAS-FT^[5]的性能對比結(jié)果

測試用例	生物測定完成時間(s)			流體運(yùn)輸路徑總長度(mm)			容錯成功率(%)
測試用例	RAS-FT^[5]	基于本文算法的架構(gòu)綜合算法	優(yōu)化(%)	RAS-FT^[5]	基于本文算法的架構(gòu)綜合算法	優(yōu)化(%)	RAS-FT^[5]	基于本文算法的架構(gòu)綜合算法	優(yōu)化
PCR	21.2	13.8	34.9	82.8	54.4	34.3	100.0	53.0	47.0
IVD1	11.5	6.5	43.5	121.9	82.3	32.5	100.0	40.0	60.0
IVD2	14.3	8.4	41.3	239.8	171.3	28.6	100.0	38.0	62.0
ProteinSplit1	38.7	26.9	30.5	173.1	122.5	29.2	100.0	13.0	87.0
ProteinSplit2	50.1	33.8	32.5	732.0	486.6	33.5	100.0	3.0	97.0
Synthetic1	18.1	12.8	29.3	57.1	35.8	37.3	100.0	29.0	71.0
Synthetic2	30.0	21.8	27.3	181.8	116.8	35.8	100.0	25.0	75.0
Synthetic3	36.4	27.4	24.7	327.4	210.7	35.6	100.0	16.0	84.0
Synthetic4	35.8	26.6	25.7	401.6	305.4	24.0	100.0	11.0	89.0
Synthetic5	38.5	28.7	25.5	505.3	377.2	25.4	100.0	8.0	92.0
平均值			31.5			31.6			76.4

下載: 導(dǎo)出CSV

參考文獻(xiàn)(33)

[1]	VERPOORTE E and DE ROOIJ N F. Microfluidics meets MEMS[J]. Proceedings of the IEEE, 2003, 91(6): 930–953. doi: 10.1109/JPROC.2003.813570.
[2]	HU Kai, DINH T A, HO T Y, et al. Control-layer routing and control-pin minimization for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 36(1): 55–68. doi: 10.1109/TCAD.2016.2568198.
[3]	POLLACK M G, SHENDEROV A D, and FAIR R B. Electrowetting-based actuation of droplets for integrated microfluidics[J]. Lab on A Chip, 2002, 2(2): 96–101. doi: 10.1039/b110474h.
[4]	陳志盛, 朱予涵, 劉耿耿, 等. 考慮流端口數(shù)量約束下的連續(xù)微流控生物芯片流路徑規(guī)劃算法[J]. 電子與信息學(xué)報, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168. CHEN Zhisheng, ZHU Yuhan, LIU Genggeng, et al. Flow-path planning algorithm for continuous-flow microfluidic biochips with strictly constrained flow ports[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168.
[5]	TSENG T M, LI Bing, HO T Y, et al. Reliability-aware synthesis for flow-based microfluidic biochips by dynamic-device mapping[C]. 2015 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6. doi: 10.1145/2744769.2744899.
[6]	FIDALGO L M and MAERKL S J. A software-programmable microfluidic device for automated biology[J]. Lab on A Chip, 2011, 11(9): 1612–1619. doi: 10.1039/c0lc00537a.
[7]	LI Bing and SCHLICHTMANN U. Reliability-aware synthesis and fault test of fully programmable valve arrays (FPVAs)[C]. 2017 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, Cambridge, UK, 2017: 1–1. doi: 10.1109/DFT.2017.8244449.
[8]	HUANG Xing, HO T Y, GUO Wenzhong, et al. Computer-aided design techniques for flow-based microfluidic lab-on-a-chip systems[J]. ACM Computing Surveys (CSUR), 2022, 54(5): 97. doi: 10.1145/3450504.
[9]	劉耿耿, 葉正陽, 朱予涵, 等. 連續(xù)微流控生物芯片下一種多階段啟發(fā)式的流層物理協(xié)同設(shè)計算法[J]. 電子與信息學(xué)報, 2023, 45(9): 3401–3409. doi: 10.11999/JEIT221155. LIU Genggeng, YE Zhengyang, ZHU Yuhan, et al. A multi-stage heuristic flow-layer physical codesign algorithm for continuous-flow microfluidic biochips[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3401–3409. doi: 10.11999/JEIT221155.
[10]	朱予涵, 黃鴻斌, 林泓星, 等. 連續(xù)微流控生物芯片下基于序列對的流層物理設(shè)計算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2022, 34(4): 535–544. doi: 10.3724/SP.J.1089.2022.19445. ZHU Yuhan, HUANG Hongbin, LIN Hongxing, et al. Sequence-pair-based flow-layer physical design algorithm for continuous-flow microfluidic biochips[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(4): 535–544. doi: 10.3724/SP.J.1089.2022.19445.
[11]	HU Kai, YU Feiqiao, HO T Y, et al. Testing of flow-based microfluidic biochips: Fault modeling, test generation, and experimental demonstration[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(10): 1463–1475. doi: 10.1109/TCAD.2014.2336215.
[12]	ESKESEN M C, POP P, and POTLURI S. Architecture synthesis for cost-constrained fault-tolerant flow-based biochips[C]. 2016 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2016: 618–623.
[13]	DUBROVA E. Fault-Tolerant Design[M]. New York: Springer, 2013: 185. doi: 10.1007/978-1-4614-2113-9.
[14]	CHOUDHARY G, PAL S, KUNDU D, et al. Transport-free module binding for sample preparation using microfluidic fully programmable valve arrays[C]. 2020 Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, 2020: 1335–1338. doi: 10.23919/DATE48585.2020.9116370.
[15]	KUNDU D, GIRI J, MARUYAMA S, et al. Fluid-to-cell assignment and fluid loading on programmable microfluidic devices for bioprotocol execution[J]. Integration, 2021, 78: 95–109. doi: 10.1016/j.vlsi.2020.12.004.
[16]	SU Y S, HO T Y, and LEE D T. A routability-driven flow routing algorithm for programmable microfluidic devices[C]. 2016 21st Asia and South Pacific Design Automation Conference, Macao, China, 2016: 605–610. doi: 10.1109/ASPDAC.2016.7428078.
[17]	LAI Guanru, LIN Chunyu, and HO T Y. Pump-aware flow routing algorithm for programmable microfluidic devices[C]. 2018 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2018: 1405–1410. doi: 10.23919/DATE.2018.8342232.
[18]	YING Shuaijie, ROY S, HUANG J D, et al. Design for restricted-area and fast dilution using programmable microfluidic device based Lab-on-a-Chip[C]. 2021 24th Euromicro Conference on Digital System Design, Palermo, Italy, 2021: 488–494. doi: 10.1109/DSD53832.2021.00079.
[19]	GRIMMER A, KLEPIC B, HO T Y, et al. Sound valve-control for programmable microfluidic devices[C]. 2018 23rd Asia and South Pacific Design Automation Conference, Jeju, Korea (South), 2018: 40–45. doi: 10.1109/ASPDAC.2018.8297280.
[20]	LIN Y H, HO T Y, LI Bing, et al. Block-flushing: A block-based washing algorithm for programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1531–1536. doi: 10.23919/DATE.2019.8715125.
[21]	YU H C, LIN Y H, CHEN Zhiyang, et al. Contamination-aware synthesis for programmable microfluidic devices[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(11): 5016–5029. doi: 10.1109/TCAD.2021.3134892.
[22]	DATTA P, CHAKRABORTY A, and PAL R K. Design optimization for programmable microfluidic devices integrating contamination removal and capacity-wastage-aware washing[J]. IETE Journal of Research, 2020, 66(6): 781–796. doi: 10.1080/03772063.2020.1811784.
[23]	LIANG Siyuan, LI Mengchu, TSENG T M, et al. CoMUX: Combinatorial-coding-based high-performance microfluidic control multiplexer design[C]. 2022 IEEE/ACM International Conference on Computer Aided Design, San Diego, USA, 2022: 1–9.
[24]	HUANG Xing, CAI Huayang, GUO Wenzhong, et al. Control-logic synthesis of fully programmable valve array using reinforcement learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(1): 277–290. doi: 10.1109/TCAD.2023.3309740.
[25]	CAI Huayang, LIU Genggeng, GUO Wenzhong, et al. Adaptive control-logic routing for fully programmable valve array biochips using deep reinforcement learning[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 564–569. doi: 10.1109/ASP-DAC58780.2024.10473962.
[26]	LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Testing microfluidic fully programmable valve arrays (FPVAs)[C]. Design, Automation & Test in Europe Conference & Exhibition, Lausanne, Switzerland, 2017: 91–96. doi: 10.23919/DATE.2017.7926964.
[27]	LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for microfluidic fully programmable valve arrays (FPVAs) with heuristic acceleration[C]. 2018 International Conference on IC Design & Technology, Otranto, Italy, 2018: 97–100. doi: 10.1109/ICICDT.2018.8399765.
[28]	LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for flow-based microfluidic biochips with general architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(10): 2530–2543. doi: 10.1109/TCAD.2019.2948904.
[29]	BERNARDINI A, LIU Chunfeng, LI Bing, et al. Efficient spanning-tree-based test pattern generation for programmable microfluidic devices[J]. Microelectronics Journal, 2018, 79: 38–45. doi: 10.1016/j.mejo.2018.06.011.
[30]	BERNARDINI A, LIU Chunfeng, LI Bing, et al. Fault localization in programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1607–1610. doi: 10.23919/DATE.2019.8715023.
[31]	LIU Genggeng, ZENG Yuqin, ZHU Yuhan, et al. Towards automated testing of multiplexers in fully programmable valve array biochips[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 570–575. doi: 10.1109/ASP-DAC58780.2024.10473918.
[32]	LIU Genggeng, ZHU Yuhan, GUO Wenzhong, et al. Fault-tolerance-oriented physical design for fully programmable valve array biochips[C]. 2023 60th ACM/IEEE Design Automation Conference, San Francisco, USA, 2023: 1–6. doi: 10.1109/DAC56929.2023.10247720.
[33]	HUANG Xing, GUO Wenzhong, CHEN Zhisheng, et al. Flow-based microfluidic biochips with distributed channel storage: Synthesis, physical design, and wash optimization[J]. IEEE Transactions on Computers, 2022, 71(2): 464–478. doi: 10.1109/TC.2021.3054689.