考虑流端口数量约束下的连续微流控生物芯片流路径规划算法

陈志盛; 朱予涵; 刘耿耿; 黄兴; 徐宁

doi:10.11999/JEIT221168

考虑流端口数量约束下的连续微流控生物芯片流路径规划算法

doi: 10.11999/JEIT221168

陈志盛¹,
朱予涵¹,
刘耿耿^{1, 2, ,},
黄兴³,
徐宁⁴

1.
福州大学计算机与大数据学院福州 350116
2.
中国科学院计算机体系结构国家重点实验室北京 100190
3.
西北工业大学计算机科学学院西安 710072
4.
武汉理工大学信息工程学院武汉 430070

基金项目: 国家自然科学基金(61877010)，国家重点基础研究发展计划(2011CB808003)，计算机体系结构国家重点实验室开放课题(CARCHB202014)

详细信息

作者简介:
陈志盛：男，博士生，研究方向为微流控生物芯片及VLSI设计自动化

朱予涵：女，博士生，研究方向为微流控生物芯片及VLSI设计自动化

刘耿耿：男，博士，副教授，研究方向为微流控生物芯片及VLSI设计自动化

黄兴：男，博士，教授，研究方向为微流控生物芯片及VLSI设计自动化

徐宁：男，博士，教授，研究方向为电子设计自动化、计算机软件与系统

通讯作者:
刘耿耿　liugenggeng@fzu.edu.cn

中图分类号: TN47; TP391.41
计量
- 文章访问数: 309
- HTML全文浏览量: 145
- PDF下载量: 64
- 被引次数: 0
出版历程
- 收稿日期: 2022-09-07
- 修回日期: 2023-03-01
- 网络出版日期: 2023-03-03
- 刊出日期: 2023-09-27

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

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)

摘要

摘要: 连续微流控生物芯片通常需要构建复杂交错的流路径来支持样本/试剂的运输，也需要大量的流端口来推动液体的有序流动，这阻碍了生物芯片的进一步发展。因此，该文考虑了有限流端口驱动下的流路径规划问题，并提出一个流路径驱动下的连续微流控生物芯片的架构综合设计流程。首先采用基于列表调度算法实现操作的绑定与调度，通过时间窗对调度进行调整，从而满足给定的流端口数量约束；然后采用基于序列对表示的遗传算法求得芯片的布局设计，通过考虑并行任务之间的冲突以及组件之间的连接关系，进一步优化了布局解的质量；最后采用基于A*寻路的优化布线算法规划所需的流路径，以有效减少流通道总长度和交叉点数量，生成具有高执行效率的芯片架构。实验结果表明，该方法在严格满足给定的流端口数量约束条件下，极大地避免了各种液体运输任务的冲突，同时也优化了流通道的总长度以及交叉点的数量，降低了芯片的构造成本。
- 连续微流控生物芯片 /
- 高层次综合 /
- 流层物理设计
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

HTML全文

图 1 连续微流控生物芯片示意图

下载: 全尺寸图片幻灯片

图 2 混合操作^[5]

下载: 全尺寸图片幻灯片

图 3 生化反应的序列图

下载: 全尺寸图片幻灯片

图 4 根据图3的生化反应产生的两种不同的调度方案

下载: 全尺寸图片幻灯片

图 5 根据图4(a)的调度方案生成的两种布局和布线方案

下载: 全尺寸图片幻灯片

图 6 构建的绕障生成图

下载: 全尺寸图片幻灯片

图 7 本文布线算法与文献[10]的冲突任务数结果对比

下载: 全尺寸图片幻灯片

图 8 本文布线算法与文献[10]的交叉点数量结果对比

下载: 全尺寸图片幻灯片

图 9 本文布线算法与文献[10]的通道总长度结果对比

下载: 全尺寸图片幻灯片

表 1 测试数据集

IVD	PCR	ProteinSplit	RA10	RA20	RA30	RA40
12/(3,0,0,0,3)/4	7/(4,0,0,0,0)/4	14/(4,0,0,3,3)/4	10/(4,2,3,0,2)/6	20/(3,3,2,0,1)/5	30/(5,2,2,0,2)/8	40/(6,4,4,0,2)/8

下载: 导出CSV

表 2 参数设置值

参数	值	参数	值
α	0.8	Item	100
β	0.2	p_c	0.98
λ 0.4	0.4	p_m	0.1
γ	0.6	t_c	2
N	150	c_p	10

下载: 导出CSV

表 3 高层次综合和流层物理设计的结果

测试用例	高层次综合		流层物理设计
测试用例	反应时间(s)	流路径数量(条)	冲突任务数(个)	交叉点数量(个)	流通道总长度(mm)
IVD	29	12	2	55	1493
PCR	20	10	1	21	663
ProteinSplit	39	16	3	47	1413
RA10	43	19	0	30	1299
RA20	38	31	2	63	1768
RA30	48	47	16	128	2831
RA40	45	75	6	224	4419

下载: 导出CSV

参考文献(23)

[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