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

ZHU Yuhan; LIU Bowen; HUANG Xing; LIU Genggeng

doi:10.11999/JEIT240049

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 >

ZHU Yuhan, LIU Bowen, HUANG Xing, LIU Genggeng. Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240049

Citation:

ZHU Yuhan, LIU Bowen, HUANG Xing, LIU Genggeng. Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240049

Citation:

PDF( 3500 KB)

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

doi: 10.11999/JEIT240049

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)

Received Date: 2024-01-24
Rev Recd Date: 2024-09-04

Available Online: 2024-09-17

Abstract

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

FullText(HTML)

References(33)

References

[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.