A Multi-Stage Heuristic Flow-Layer Physical Codesign Algorithm for Continuous-Flow Microfluidic Biochips
-
摘要: 为了提高连续微流控生物芯片(CFMBs)中的流层物理协同设计质量和效率，该文分3阶段实现布局布线协同设计。(1) 布局预处理阶段：通过提出的逻辑布局和组件方向布局调整方法，得到组件优异的逻辑位置和逻辑方向。(2) 组件映射和包围盒间隙布局调整阶段：基于包围盒策略，把布局预处理结果映射到实际物理设计空间中，并通过包围盒间隙布局调整，获得最佳包围盒间隙。(3) 收缩布局调整阶段：基于组件间的连通图关系，提出了沿流通道收缩和多图收缩两种新的布局调整方法。实验结果表明，与现有最佳的启发式算法对比，该文算法在芯片流层整体面积、流通道交叉点数和流通道总长度上分别优化20.22%, 54.66%和71.62%，加速比为177.12，显著提升了设计质量和效率。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.
-
算法1 逻辑布局算法 输入：所有组件和连接网。 输出：优化后的逻辑布局结果。 1 初始化逻辑空间。 2 若小于外层迭代次数阈值且邻近交换最大收益maxBenefit为正，则进入循环。 (1) 根据式(1)计算所有组件在邻近4个方向的净收益并更新maxBenefit。 (2) 选择收益等于maxBenefit的组件进行邻近移动。 (3) 如小于内层迭代次数阈值且由式(1)更新的maxBenefit小于等于零，则进入循环。 (a) 遍历找出边未被锁定且边两端曼哈顿距离最大的两组件，并分配目标组件和跳跃组件角色。 (b) 根据式(2)顺时针方向在目标组件周围寻找第1个净收益非负的交换组件。 (c) 若存在净收益非负的交换组件，则进行目标跳跃；否则跳过，并锁定该边。 (d) 锁定该边，并更新maxBenefit。 (e) 如果所有的边都被锁定，则解锁所有的边。 3 循环结束，输出优化后的逻辑布局结果。 
下载: 导出CSV
表 1 与文献[10]最终实验结果3指标对比
测试用例 组件
数量(个)宽度(mm) 高度(mm) 流层整体面积(mm2) 流通道交叉点数量(个) 流通道总长度(mm) 文献[10] 本文 文献[10] 本文 文献[10] 本文 优化比例
(%)文献[10] 本文 优化比例
(%)文献[10] 本文 优化比例
(%)PCR 16 58 51 49 54 2842 2754 3.10 2 0 100.00 454 157 65.42 ProteinSplit-1 30 66 72 70 67 4620 4818 –4.29 10 1 90.00 956 339 64.54 ProteinSplit-2 66 121 108 115 103 13915 11124 20.06 55 16 70.91 2519 1146 54.51 InVitro-1 30 73 44 58 60 4234 2640 37.65 3 0 100.00 740 52 92.97 InVitro-2 45 80 65 83 54 6640 3510 47.14 7 0 100.00 1053 123 88.32 InVitro-3 60 115 75 82 83 9430 5229 44.55 10 0 100.00 1644 190 88.44 平均 24.70 93.49 75.70
下载: 导出CSV
表 3 与文献[11]最终实验结果3指标对比
测试用例 组件
数量(个)宽度(mm) 高度(mm) 流层整体面积(mm2) 流通道交叉点数量(个) 流通道总长度(mm) 文献[11] 本文 文献[11] 本文 文献[11] 本文 优化比例
(%)文献[11] 本文 优化比例
(%)文献[11] 本文 优化比例
(%)PCR 16 55 51 52 54 2860 2754 3.71 0 0 / 435 157 63.91 ProteinSplit-1 30 83 72 52 67 4316 4818 –11.63 4 1 75.00 757 339 55.22 ProteinSplit-2 66 118 108 100 103 11800 11124 5.73 34 16 52.94 2277 1146 49.67 InVitro-1 30 53 44 79 60 4187 2640 36.95 0 0 / 526 52 90.11 InVitro-2 45 70 65 83 54 5810 3510 39.59 2 0 100.00 798 123 84.59 InVitro-3 60 88 75 112 83 9856 5229 46.95 2 0 100.00 1421 190 86.21 平均 20.22 54.66 71.62
下载: 导出CSV
-
[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.19445ZHU 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 -
下载:
点击查看大图
图(12) / 表(5)
计量
- 文章访问数: 254
- HTML全文浏览量: 152
- PDF下载量: 53
- 被引次数: 0
