A Multi-Stage Heuristic Flow-Layer Physical Codesign Algorithm for Continuous-Flow Microfluidic Biochips

LIU Genggeng; YE Zhengyang; ZHU Yuhan; CHEN Zhisheng; HUANG Xing; XU Ning

doi:10.11999/JEIT221155

Volume 45 Issue 9

Sep. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(9): 3401-3409

LIU Genggeng, YE Zhengyang, ZHU Yuhan, CHEN Zhisheng, HUANG Xing, XU Ning. 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

Citation:

LIU Genggeng, YE Zhengyang, ZHU Yuhan, CHEN Zhisheng, HUANG Xing, XU Ning. 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

Citation:

LIU Genggeng, YE Zhengyang, ZHU Yuhan, CHEN Zhisheng, HUANG Xing, XU Ning. 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

PDF( 2229 KB)

A Multi-Stage Heuristic Flow-Layer Physical Codesign Algorithm for Continuous-Flow Microfluidic Biochips

doi: 10.11999/JEIT221155

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350116, China
2.
State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
3.
School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China
4.
Information Engineering, Wuhan University of Technology, Wuhan 430070, China

Funds: The National Natural Science Foundation of China (61877010)

Received Date: 2022-09-05
Accepted Date: 2022-12-20
Rev Recd Date: 2022-12-18

Available Online: 2022-12-23

Publish Date: 2023-09-27

Abstract

Abstract

In order to improve the quality and efficiency of flow-layer physical co-design in Continuous-Flow Microfluidic Biochips (CFMBs), placement and routing co-design is implemented in three stages. (1) Placement preprocessing stage: Through the logic placement and component orientation placement adjustment method, the excellent logical position and logical orientation of components are obtained. (2) Component mapping and bounding-box gap placement adjustment stage: Based on the bounding-box strategy, the placement preprocessing result is mapped into the actual physical design space, and the optimal bounding-box gap is obtained after the placement adjustment of bounding-box. (3) Shrinking placement adjustment stage: Based on the connected graph relationship among components, two original placement adjustment methods, shrinking along the flow channel and multi-graph shrinking, are proposed. The experimental results show that, compared with the existing best heuristic algorithm, the algorithm in this paper optimize the chip flow-layer integral area, the number of flow channel intersections and the total length of flow channel by 20.22%, 54.66% and 71.62%, respectively, and the speedup ratio is 177.12, which improves significantly the design quality and efficiency.
- Continuous-Flow Microfluidic Biochips (CFMBs),
- Flow-layer physical design,
- Logic placement,
- Bounding-box strategy,
- Shrinking placement adjustment

FullText(HTML)

References(15)

References

[1]	MELIN J and QUAKE S R. Microfluidic large-scale integration: The evolution of design rules for biological automation[J]. Annual Review of Biophysics and Biomolecular Structure, 2007, 36: 213–231. doi: 10.1146/annurev.biophys.36.040306.132646
[2]	HONG J W and QUAKE S R. Integrated nanoliter systems[J]. Nature Biotechnology, 2003, 21(10): 1179–1183. doi: 10.1038/nbt871
[3]	HUANG T W, HO T Y, and CHAKRABARTY K. Reliability-oriented broadcast electrode-addressing for pin-constrained digital microfluidic biochips[C]. 2011 IEEE/ACM International Conference on Computer-Aided Design, San Jose, USA, 2011: 448–455.
[4]	MAIRHOFER J, ROPPERT K, and ERTL P. Microfluidic systems for pathogen sensing: A review[J]. Sensors, 2009, 9(6): 4804–4823. doi: 10.3390/s90604804
[5]	CHOU H P, UNGER M A, SCHERER A, et al. Integrated elastomer fluidic lab-on-a-chip-surface patterning and DNA diagnostics[C]. Solid-State Sensors, Actuators, and Microsystems Workshop, Hilton Head Island, USA, 2000: 4.
[6]	ROGERS J A and NUZZO R G. Recent progress in soft lithography[J]. Materials Today, 2005, 8(2): 50–56. doi: 10.1016/s1369-7021(05)00702-9
[7]	POL R, CÉSPEDES F, GABRIEL D, et al. Microfluidic lab-on-a-chip platforms for environmental monitoring[J]. TrAC Trends in Analytical Chemistry, 2017, 95: 62–68. doi: 10.1016/j.trac.2017.08.001
[8]	TSENG K H, YOU Shengchi, LIOU J Y, et al. A top-down synthesis methodology for flow-based microfluidic biochips considering valve-switching minimization[C]. 2013 ACM International Symposium on Physical Design, Stateline, USA, 2013: 123–129.
[9]	MINHASS W H, POP P, MADSEN J, et al. Architectural synthesis of flow-based microfluidic large-scale integration biochips[C]. 2012 International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Tampere, Finland, 2012: 181–190.
[10]	WANG Qin, RU Yizhong, YAO Hailong, et al. Sequence-pair-based placement and routing for flow-based microfluidic biochips[C]. The 21st Asia and South Pacific Design Automation Conference, Macao, China, 2016: 587–592.
[11]	朱予涵, 黄鸿斌, 林泓星, 等. 连续微流控生物芯片下基于序列对的流层物理设计算法[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
[12]	HUANG Xing, PAN Youlin, ZHANG G L, et al. PathDriver+: Enhanced path-driven architecture design for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(7): 2185–2198. doi: 10.1109/TCAD.2021.3103832
[13]	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
[14]	HUANG Xing, PAN Youlin, CHEN Zhen, et al. BigIntegr: One-pass architectural synthesis for continuous-flow microfluidic lab-on-a-chip systems[C]. 2021 IEEE/ACM International Conference on Computer Aided Design, Munich, Germany, 2021: 1–8.
[15]	HUANG Xing, PAN Youlin, CHEN Zhen, et al. Design automation for continuous-flow lab-on-a-chip systems: A one-pass paradigm[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(1): 327–331. doi: 10.1109/TCAD.2022.3166105