完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

朱予涵; 刘博文; 黄兴; 刘耿耿

doi:10.11999/JEIT240049

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

doi: 10.11999/JEIT240049

朱予涵^{1, 2, 3},
刘博文^{1, 2, 3},
黄兴⁴,
刘耿耿^{1, 2, 3, ,}

1.
福州大学计算机与大数据学院福州 350116
2.
大数据智能教育部工程研究中心福州 350116
3.
福建省网络计算与智能信息处理重点实验室福州 350116
4.
西北工业大学计算机学院西安 710072

基金项目: 福建省杰出青年科学基金(2023J06017)

详细信息

作者简介:
朱予涵：女，博士生，研究方向为微流体生物芯片设计自动化

刘博文：男，博士生，研究方向为微流体生物芯片设计自动化

黄兴：男，博士，教授，研究方向为微流体生物芯片及超大规模集成电路设计自动化

刘耿耿：男，博士，教授，研究方向为微流体生物芯片及超大规模集成电路设计自动化

通讯作者:
刘耿耿　liugenggeng@fzu.edu.cn

中图分类号: TN402; TP391.41
计量
- 文章访问数: 99
- HTML全文浏览量: 46
- PDF下载量: 10
- 被引次数: 0
出版历程
- 收稿日期: 2024-01-24
- 修回日期: 2024-09-04
- 网络出版日期: 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)生物芯片具有更高的灵活性和可编程性，已经成为一种流行的生物化学实验平台。然而，由于环境或人为因素，制造过程中通常存在一些物理故障，如通道阻塞和泄漏，这无疑会影响生化检测的结果。此外，高阶综合作为架构综合的首要阶段，其结果的质量直接影响着后续设计的优劣。因此，该文首次研究了FPVA生物芯片高阶综合过程中的容错问题，提出了单元功能转换方法、双向冗余方法、故障映射方法等动态容错技术，为实现高效的容错设计提供了技术保障。通过将这些技术集成到高阶综合设计中，进一步实现了一种高质量的FPVA生物芯片下容错导向的高阶综合算法，包括故障感知的实时绑定策略和故障感知的优先级调度策略，为实现芯片架构的鲁棒性和检测结果的准确性奠定了良好的基础。实验结果显示，所提算法能够得到一个FPVA生物芯片下高质量且容错的高阶综合方案，为后续实现容错物理设计方案提供了有力保障。
- 微流控生物芯片 /
- 完全可编程阀门阵列 /
- 物理故障 /
- 容错 /
- 高阶综合
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架构及其拓扑连接图

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 3 FPVA生物芯片高阶综合示例

下载: 全尺寸图片幻灯片

图 4 FPVA下容错导向的高阶综合算法流程图

下载: 全尺寸图片幻灯片

图 5 动态容错技术示例

下载: 全尺寸图片幻灯片

1 动态容错绑定算法

输入：FPVA单元集$C$，操作集$O$，组件数量为${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}$随机绑定到一个组件${M_j}$
end for
for each cell ${C_i}$ of $C$ do
if ${C_i}$ == ${F_i}$ then
${C_i}$_state = –1；//标记为不可用单元
Continue;
else
${C_i}$_state = 0；//标记为空闲单元
Continue;
end if
end for
//绑定调整阶段
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}$)；//根据双向冗余技术从空闲单元中选择备用单元
Banding(${O_i}$,${M_j}$);
end if
if Done(${M_j}$) == True do //组件上的操作已执行完成
${C_k}$_state = 0; //根据单元功能转换将组件${M_j}$占据单元转换为空闲单元
end if
end for
end for

下载: 导出CSV

2 动态容错调度算法

输入：FPVA单元集$C$, 操作集$O$，操作间的依赖关系，每个操作执行时间$ {t_{\text{e}}}\left( {{O_j}} \right) $，和输入流体，物理故障位置${F_i}$(包括故障单元以及包　含故障连接的单元)
输出：一个容错的调度方案
//初始调度顺序生成
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}$的优先级
end for
Sorting($O$)；//根据调度优先级由大到小将操作排序
for each cell ${C_i}$ of $C$ do
if ${C_i}$ == ${F_i}$ then
${C_i}$_state = –1；//标记为不可用单元
Continue;
else
${C_i}$_state = 0；//标记为空闲单元
Continue;
end if
end for
//调度顺序调整
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}$)；//根据双向冗余技术从空闲单元中选择备用单元
end if
if Reached (${r_j}$) == True do //输入流体已到达目标组件
${C_k}$_state = 0；//根据单元功能转换将流体${r_j}$占据单元转换为空闲单元
end if
end for
end for
end for

下载: 导出CSV

表 1 图3对应的绑定与调度方案

时间(s)	动作
$0$～$ {t_{\text{c}}} $	分别运输输入流体${r_1}$, ${r_3}$, ${r_5}$到组件${M_1}$, ${M_2}$, ${M_3}$
$ {t_{\text{c}}} $～$2{t_{\text{c}}}$	分别运输输入流体${r_2}$, ${r_4}$到组件${M_1}$, ${M_2}$
$2{t_{\text{c}}}$～($2{t_{\text{c}}} + 4$)	执行混合操作${O_1}$, ${O_2}$
$\left( {2{t_{\text{c}}} + 4} \right)$～$\left( {3{t_{\text{c}}} + 4} \right)$	运输${O_1}$, ${O_2}$的混合产物到混合器${M_3}$
$\left( {3{t_{\text{c}}} + 4} \right)$～$\left( {3{t_{\text{c}}} + 8} \right)$	执行混合操作${O_3}$

下载: 导出CSV

表 2 策略有效性对比结果

测试用例	(输入流体数，输出流体数，混合操作数)	FPVA 尺寸	生物测定完成时间(s)			流体运输路径总长度(mm)
测试用例	(输入流体数，输出流体数，混合操作数)	FPVA 尺寸	基准算法	本文算法	优化(%)	基准算法	本文算法	优化(%)
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

下载: 导出CSV

表 3 与RAS-FT^[5]的性能对比结果

测试用例	生物测定完成时间(s)			流体运输路径总长度(mm)			容错成功率(%)
测试用例	RAS-FT^[5]	基于本文算法的架构综合算法	优化(%)	RAS-FT^[5]	基于本文算法的架构综合算法	优化(%)	RAS-FT^[5]	基于本文算法的架构综合算法	优化
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

下载: 导出CSV

参考文献(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]	陈志盛, 朱予涵, 刘耿耿, 等. 考虑流端口数量约束下的连续微流控生物芯片流路径规划算法[J]. 电子与信息学报, 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]	刘耿耿, 叶正阳, 朱予涵, 等. 连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法[J]. 电子与信息学报, 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]	朱予涵, 黄鸿斌, 林泓星, 等. 连续微流控生物芯片下基于序列对的流层物理设计算法[J]. 计算机辅助设计与图形学学报, 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.