Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips
-
摘要: 作为新一代流式微流控生物芯片,完全可编程阀门阵列(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.
-
图 2 制造缺陷示例[11]
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 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 表 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}$ 表 2 策略有效性对比结果
测试用例 (输入流体数,输出流体数,
混合操作数)FPVA
尺寸生物测定完成时间(s) 流体运输路径总长度(mm) 基准算法 本文算法 优化(%) 基准算法 本文算法 优化(%) 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 表 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 -
[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.