Component Placement Algorithm Considering Reagent Type Differences in Cell Reuse for FPVA Biochips

XU Yanbo; ZHU Yuhan; HUANG Xing; LIU Genggeng

doi:10.11999/JEIT250731

Article Contents

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

XU Yanbo, ZHU Yuhan, HUANG Xing, LIU Genggeng. Component Placement Algorithm Considering Reagent Type Differences in Cell Reuse for FPVA Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250731

Citation:

XU Yanbo, ZHU Yuhan, HUANG Xing, LIU Genggeng. Component Placement Algorithm Considering Reagent Type Differences in Cell Reuse for FPVA Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250731

Citation:

PDF( 2021 KB)

Component Placement Algorithm Considering Reagent Type Differences in Cell Reuse for FPVA Biochips

doi: 10.11999/JEIT250731 cstr: 32379.14.JEIT250731

XU Yanbo^{1, 2, 3},
ZHU Yuhan^{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: The National Natural Science Foundation of China(62372109, 62572396), The Fujian Science Fund for Distinguished Young Scholars(2023J06017)

Received Date: 2025-08-07
Accepted Date: 2026-01-12
Rev Recd Date: 2026-01-08

Available Online: 2026-01-27

Abstract

Abstract

Objective Fully Programmable Valve Array (FPVA) biochips, a recent type of flow-based microfluidic biochip, offer high flexibility and programmability, which enables them to meet different and complex experimental needs. Component placement is a critical stage in FPVA architectural synthesis because it affects several performance metrics, including assay completion time, total fluid-transport length, and cross-contamination. Cell reuse, an essential feature of FPVA programmability, requires special consideration during placement. However, existing studies have largely ignored the effect of reagent type differences in cell reuse on these metrics Methods This study presents a component placement algorithm for FPVA biochips that accounts for reagent type differences during cell reuse. The algorithm first introduces a cell reuse complexity metric that quantifies reuse complexity by considering the effects of reagent-type differences and component overlap on cross-contamination. It then integrates constraints, including placement-area limits and non-overlapping conditions for concurrent components, to ensure valid placement. The reward function is optimized to minimize reuse complexity and reduce the distance between components that use the same reagent type. The goal is to lower cross-contamination, total fluid-transport length, and assay completion time. Results and Discussions The algorithm is evaluated on benchmark FPVA instances with different chip sizes and functional requirements and compared with related methods. It reduces cell reuse complexity by 34.2%, assay completion time by 2.8%, and total fluid-transport length by 9.2% on average (Table 2). It also reduces the reagent-aware distance metric by 29.9% on average (Fig. 6). The learning agent’s decision trajectories show clear spatial structure, which reflects global placement awareness. Conclusions This study is the first to investigate FPVA component placement with attention to reagent type differences in cell reuse. The main contributions are as follows: (1) a cell reuse complexity metric is proposed to assess reuse intensity in placement, (2) the FPVA placement problem is modeled as a Markov decision process to enable the use of double deep Q-networks for safe and efficient placement policy learning, and (3) compared with existing work, the model improves FPVA biochemical assay performance and reliability.
- Microfluidic biochip,
- Fully Programmable Valve Array(FPVA),
- Cell reuse,
- Reagent type,
- Component placement

FullText(HTML)

References(24)

References

[1]	MINHASS W H, POP P, MADSEN J, et al. Architectural synthesis of flow-based microfluidic large-scale integration biochips[C]. The International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Tampere, Finland, 2012: 181–190. doi: 10.1145/2380403.2380437.
[2]	MINHASS W H, POP P, and MADSEN J. Synthesis of biochemical applications on flow-based microfluidic biochips using constraint programming[C]. The Symposium on Design, Test, Integration and Packaging of MEMS/MOEMS, Cannes, France, 2012: 37–41.
[3]	朱予涵, 刘博文, 黄兴, 等. 完全可编程阀门阵列生物芯片下容错导向的高阶综合算法[J]. 电子与信息学报, 2024, 46(11): 4141–4150. doi: 10.11999/JEIT240049. ZHU Yuhan, LIU Bowen, HUANG Xing, et al. Fault-tolerance-oriented high-level synthesis algorithm for fully programmable valve array biochips[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4141–4150. doi: 10.11999/JEIT240049.
[4]	MCDANIEL J, PARKER B, and BRISK P. Simulatedannealing-based placement for microfluidic large scaleintegration (mLSI) chips[C]. The 22nd International Conference on Very Large Scale Integration, Playa delCarmen, Mexico, 2014: 1–6. doi: 10.1109/VLSI-SoC.2014.7004170.
[5]	HU Kai, HO T Y, and CHAKRABARTY K. Wash optimization and analysis for cross-contamination removal under physical constraints in flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(4): 559–572. doi: 10.1109/TCAD.2015.2488485.
[6]	GRIMMER A, WANG Qin, YAO Hailong, et al. Close-to-optimal placement and routing for continuous-flow microfluidic biochips[C]. The 22nd Asia and South Pacific Design Automation Conference, Chiba, Japan, 2017: 530–535. doi: 10.1109/ASPDAC.2017.7858377.
[7]	CRITES B, KONG K, and BRISK P. Diagonal component expansion for flow-layer placement of flow-based microfluidic biochips[J]. ACM Transactions on Embedded Computing Systems, 2017, 16(5s): 126. doi: 10.1145/3126529.
[8]	CHEN Zhisheng, HUANG Xing, GUO Wenzhong, et al. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage[C]. The Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1525–1530. doi: 10.23919/DATE.2019.8715269.
[9]	王钦. 微流控生物芯片流体与控制协同物理设计算法研究[D]. [博士论文], 清华大学, 2018. doi: 10.27266/d.cnki.gqhau.2018.000723. WANG Qin. Research on control-fluidic physical CoDesign algorithm for microfluidic biochips[D]. [Ph. D. dissertation], Tsinghua University, 2018. doi: 10.27266/d.cnki.gqhau.2018.000723.
[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]	刘耿耿, 叶正阳, 朱予涵, 等. 连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法[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.
[12]	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.
[13]	TSENG T M, LI Bing, HO T Y, et al. Reliability-aware synthesis for flow-based microfluidic biochips by dynamic-device mapping[C]. The 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6. doi: 10.1145/2744769.2744899.
[14]	TSENG T M, LI Bing, LI Mengchu, et al. Reliability-aware synthesis with dynamic device mapping and fluid routing for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(12): 1981–1994. doi: 10.1109/TCAD.2016.2547902.
[15]	CHOUDHARY G, PAL S, KUNDU D, et al. Transport-free module binding for sample preparation using microfluidic fully programmable valve arrays[C]. The Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, 2020: 1335–1338. doi: 10.23919/DATE48585.2020.9116370.
[16]	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.
[17]	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.
[18]	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.
[19]	LIU Genggeng, ZHU Yuhan, GUO Wenzhong, et al. Fault-tolerance-oriented physical design for fully programmable valve array biochips[C]. The 60th ACM/IEEE Design Automation Conference, San Francisco, USA, 2023: 1–6. doi: 10.1109/DAC56929.2023.10247720.
[20]	KUMAR M, KHAN A K, ROY S, et al. Accelerating fluid loading in sample preparation with fully programmable valve arrays[C]. The 37th International Conference on VLSI Design and 23rd International Conference on Embedded Systems (VLSID), Kolkata, India, 2024: 402–407. doi: 10.1109/VLSID60093.2024.00073.
[21]	ZHU Yuhan, LIU Genggeng, GUO Wenzhong, et al. FTCD: Fault-tolerant co-design of flow and control layers for fully programmable valve array biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2025, 44(7): 2669–2682. doi: 10.1109/TCAD.2025.3525615.
[22]	CAI Huayang, LIU Genggeng, GUO Wenzhong, et al. Adaptive control-logic routing for fully programmable valve array biochips using deep reinforcement learning[C]. The 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 564–569. doi: 10.1109/ASP-DAC58780.2024.10473962.
[23]	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.
[24]	MNIH V, KAVUKCUOGLU K, SILVER D, et al. Playing Atari with deep reinforcement learning[J]. arXiv preprint arXiv: 1312.5602, 2013. doi: 10.48550/arXiv.1312.5602.