Flow-path Planning Algorithm for Continuous-flow Microfluidic Biochips with Strictly Constrained Flow Ports

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

doi:10.11999/JEIT221168

Volume 45 Issue 9

Sep. 2023

Turn off MathJax

Article Contents

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

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

Citation:

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

Citation:

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

PDF( 4197 KB)

Flow-path Planning Algorithm for Continuous-flow Microfluidic Biochips with Strictly Constrained Flow Ports

doi: 10.11999/JEIT221168

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.
School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China

Funds: The National Natural Science Foundation of China (61877010), The Key Project of Chinese National Programs for Fundamental Research and Development (2011CB808003), The State Key Laboratory of Computer Architecture Open Project (CARCHB202014)

Received Date: 2022-09-07
Rev Recd Date: 2023-03-01

Available Online: 2023-03-03

Publish Date: 2023-09-27

Abstract

Abstract

Continuous-flow microfluidic biochips need usually to construct complex and interlaced flow paths to support the transportation of sample/reagent, and also require a large number of flow ports to promote the orderly fluids flow, thereby hinders the further development of the biochips. Therefore, the flow-path planning problem under strict constraints of flow ports is formulated, and a path-driven architecture synthesis flow for continuous-flow microfluidic biochips is proposed. Firstly, the list scheduling algorithm is used to realize the binding and scheduling of operations. To satisfy the constraints of a limited number of flow ports, a time window can be applied to adjust the final scheduling result. Then, the flow-layer placement is obtained by genetic algorithm based on sequence pair representation, and the quality of the layout solution is further optimized by considering the conflicts between parallel tasks and the connections between components. Finally, an A*-based routing method is used to complete flow-path planning for reducing effectively the total flow-channel length and the number of intersections, thereby generating a biochip layout with high execution efficiency. The experimental results show that the proposed method greatly avoids the conflicts of various fluid transportation tasks under the condition of satisfying the given flow port constraints strictly, and optimizes the total length of flow channels and the number of intersections, thereby reducing the manufacturing cost of the chip.
- Continuous-flow microfluidic biochips,
- High-level synthesis,
- Flow-layer physical design

FullText(HTML)

References(23)

References

[1]	ZHENG Bo, ROACH L S, and ISMAGILOV R F. Screening of protein crystallization conditions on a microfluidic chip using nanoliter-size droplets[J]. Journal of the American Chemical Society, 2003, 125(37): 11170–11171. doi: 10.1021/ja037166v
[2]	HUNG L H, CHOI K M, TSENG W Y, et al. Alternating droplet generation and controlled dynamic droplet fusion in microfluidic device for CdS nanoparticle synthesis[J]. Lab on a Chip, 2006, 6(2): 174–178. doi: 10.1039/b513908b
[3]	HAMIDOVIĆ M, HASELMAYR W, GRIMMER A, et al. Passive droplet control in microfluidic networks: A survey and new perspectives on their practical realization[J]. Nano Communication Networks, 2019, 19: 33–46. doi: 10.1016/j.nancom.2018.10.002
[4]	THORSEN T, MAERKL S J, and QUAKE S R. Microfluidic large-scale integration[J]. Science, 2002, 298(5593): 580–584. doi: 10.1126/science.1076996
[5]	Stanford microfluidic foundry: Basic design rules[EB/OL]. http://www.stanford.edu/group/foundry/Basic%20Design%20Rules.html.
[6]	LIU Genggeng, HUANG Hongbin, CHEN Zhisheng, et al. Design automation for continuous-flow microfluidic biochips: A comprehensive review[J]. Integration, 2022, 82: 48–66. doi: 10.1016/j.vlsi.2021.09.002
[7]	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, 2021, 54(5): 97. doi: 10.1145/3450504
[8]	LIU Chunfeng, LI Bing, YAO Hailong, et al. Transport or store?: Synthesizing flow-based microfluidic biochips using distributed channel storage[C]. The 54th Annual Design Automation Conference, Austin, USA, 2017: 49.
[9]	LIU Chunfeng, HUANG Xing, LI Bing, et al. DCSA: Distributed channel-storage architecture for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(1): 115–128. doi: 10.1109/TCAD.2020.2994267
[10]	CHEN Zhisheng, HUANG Xing, GUO Wenzhong, et al. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage[C]. The 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1525–1530.
[11]	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
[12]	HUANG Xing, PAN Youling, ZHANG G L, et al. PathDriver: A path-driven architectural synthesis flow for continuous-flow microfluidic biochips[C]. The 2020 IEEE/ACM International Conference on Computer Aided Design, San Diego, USA, 2020: 1–8.
[13]	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
[14]	YANG Kailin, YAO Hailong, HO T Y, et al. AARF: Any-angle routing for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(12): 3042–3055. doi: 10.1109/TCAD.2018.2789356
[15]	HUANG Xing, HO T Y, GUO Wenzhong, et al. MiniControl: Synthesis of continuous-flow microfluidics with strictly constrained control ports[C]. The 56th Annual Design Automation Conference, Las Vegas, USA, 2019: 145.
[16]	HUANG Xing, Ho T Y, LI Zepeng, et al. MiniControl 2.0: Co-synthesis of flow and control layers for microfluidic biochips with strictly constrained control ports[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(12): 5449–5463. doi: 10.1109/TCAD.2022.3157691
[17]	HUANG Xing, PAN Youlin, CHEN Zhen, et al. BigIntegr: One-pass architectural synthesis for continuous-flow microfluidic lab-on-a-chip systems[C]. The 2021 IEEE/ACM International Conference on Computer Aided Design, Munich, Germany, 2021: 1–8.
[18]	DATTA P, CHAKRABORTY A, and PAL R K. An integrated co-design of flow-based biochips considering flow-control design issues and objectives[J/OL]. IETE Journal of Research, 2021: 1–18. https://www.tandfonline.com/doi/abs/10.1080/03772063.2021.1919220?journalCode=tijr20, 2021
[19]	ULLMAN J D. NP-complete scheduling problems[J]. Journal of Computer and System Sciences, 1975, 10(3): 384–393. doi: 10.1016/S0022-0000(75)80008-0
[20]	DE MICHELI G. Synthesis and Optimization of Digital Circuits[M]. New York: McGraw-Hill Higher Education, 1994.
[21]	陈国良, 王熙法, 庄镇泉, 等. 遗传算法及其应用[M]. 北京: 人民邮电出版社, 1996. CHEN Guoliang, WANG Xifa, ZHUANG Zhenquan, et al. Genetic Algorithm and Its Application[M]. Beijing: People's Posts and Telecommunications Publishing House, 1996.
[22]	刘锐, 洪先龙, 董社勤, 等. 基于序列对表示的对齐约束模块布局算法[J]. 软件学报, 2003, 14(8): 1418–1424. doi: 10.13328/j.cnki.jos.2003.08.010 LIU Rui, HONG Xianlong, DONG Sheqin, et al. A block placement algorithm with predefined coordinate alignment constraint based on sequence pair representation[J]. Journal of Software, 2003, 14(8): 1418–1424. doi: 10.13328/j.cnki.jos.2003.08.010
[23]	DRAKIDIS A, MACK R J, and MASSARA R E. Packing-based VLSI module placement using genetic algorithm with sequence-pair representation[J]. IEE Proceedings-Circuits, Devices and Systems, 2006, 153(6): 545–551. doi: 10.1049/ip-cds:20050134