高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

朱予涵 刘博文 黄兴 刘耿耿

朱予涵, 刘博文, 黄兴, 刘耿耿. 完全可编程阀门阵列生物芯片下容错导向的高阶综合算法[J]. 电子与信息学报. doi: 10.11999/JEIT240049
引用本文: 朱予涵, 刘博文, 黄兴, 刘耿耿. 完全可编程阀门阵列生物芯片下容错导向的高阶综合算法[J]. 电子与信息学报. doi: 10.11999/JEIT240049
ZHU Yuhan, LIU Bowen, HUANG Xing, LIU Genggeng. Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240049
Citation: ZHU Yuhan, LIU Bowen, HUANG Xing, LIU Genggeng. Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240049

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

doi: 10.11999/JEIT240049
基金项目: 福建省杰出青年科学基金(2023J06017)
详细信息
    作者简介:

    朱予涵:女,博士生,研究方向为微流体生物芯片设计自动化

    刘博文:男,博士生,研究方向为微流体生物芯片设计自动化

    黄兴:男,博士,教授,研究方向为微流体生物芯片及超大规模集成电路设计自动化

    刘耿耿:男,博士,教授,研究方向为微流体生物芯片及超大规模集成电路设计自动化

    通讯作者:

    刘耿耿 liugenggeng@fzu.edu.cn

  • 中图分类号: TN402; TP391.41

Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips

Funds: Fujian Science Fund for Distinguished Young Scholars (2023J06017)
  • 摘要: 作为新一代流式微流控生物芯片,完全可编程阀门阵列(FPVA)生物芯片具有更高的灵活性和可编程性,已经成为一种流行的生物化学实验平台。然而,由于环境或人为因素,制造过程中通常存在一些物理故障,如通道阻塞和泄漏,这无疑会影响生化检测的结果。此外,高阶综合作为架构综合的首要阶段,其结果的质量直接影响着后续设计的优劣。因此,该文首次研究了FPVA生物芯片高阶综合过程中的容错问题,提出了单元功能转换方法、双向冗余方法、故障映射方法等动态容错技术,为实现高效的容错设计提供了技术保障。通过将这些技术集成到高阶综合设计中,进一步实现了一种高质量的FPVA生物芯片下容错导向的高阶综合算法,包括故障感知的实时绑定策略和故障感知的优先级调度策略,为实现芯片架构的鲁棒性和检测结果的准确性奠定了良好的基础。实验结果显示,所提算法能够得到一个FPVA生物芯片下高质量且容错的高阶综合方案,为后续实现容错物理设计方案提供了有力保障。
  • 图  1  FPVA架构及其拓扑连接图

    图  2  制造缺陷示例[11]

    图  3  FPVA生物芯片高阶综合示例

    图  4  FPVA下容错导向的高阶综合算法流程图

    图  5  动态容错技术示例

    1  动态容错绑定算法

     输入:FPVA单元集$C$,操作集$O$,组件数量为${N_M}$的组件库$M$,物理故障位置${F_i}$(包括合并单元、故障单元及包含故障连接的单元)
     输出:一个容错的绑定方案
      //初始绑定阶段
      for each operation ${O_i}$ of $O$ do
       Banding(${O_i}$,${M_j}$) = Random(0, ${N_M}$–1);//将操作${O_i}$随机绑定到一个组件${M_j}$
      end for
      for each cell ${C_i}$ of $C$ do
       if ${C_i}$ == ${F_i}$ then
         ${C_i}$_state = –1;//标记为不可用单元
        Continue;
        else
         ${C_i}$_state = 0;//标记为空闲单元
         Continue;
       end if
      end for
      //绑定调整阶段
      for each module ${M_j}$ of M do
       for each cell ${C_k}$ of ${M_j}$ do
        if ${C_k}$_state == –1 then //${C_k}$为不可用单元
         Construct_spare_module(${M_j}$);//根据双向冗余技术从空闲单元中选择备用单元
         Banding(${O_i}$,${M_j}$);
        end if
        if Done(${M_j}$) == True do //组件上的操作已执行完成
          ${C_k}$_state = 0; //根据单元功能转换将组件${M_j}$占据单元转换为空闲单元
         end if
       end for
      end for
    下载: 导出CSV

    2  动态容错调度算法

     输入:FPVA单元集$C$, 操作集$O$,操作间的依赖关系,每个操作执行时间$ {t_{\text{e}}}\left( {{O_j}} \right) $,和输入流体,物理故障位置${F_i}$(包括故障单元以及包含故障连接的单元)
     输出:一个容错的调度方案
     //初始调度顺序生成
      for each operation ${O_i}$ of $O$ do
      ${\text{pri}}\left( {{O_i}} \right) = \displaystyle\sum\nolimits_{{O_j} \in {\text{son}}\left( {{O_i}} \right)} {{t_{\text{e}}}\left( {{O_j}} \right) + {t_{\text{c}}} \times \left| {{\text{son}}\left( {{O_i}} \right) - 1} \right|} $;//计算操作${O_i}$的优先级
      end for
      Sorting($O$);//根据调度优先级由大到小将操作排序
      for each cell ${C_i}$ of $C$ do
       if ${C_i}$ == ${F_i}$ then
        ${C_i}$_state = –1;//标记为不可用单元
        Continue;
       else
        ${C_i}$_state = 0;//标记为空闲单元
        Continue;
       end if
      end for
      //调度顺序调整
       for each operation ${O_i}$ of $O$ do
        for each fluid ${r_j}$ of ${O_i}$ do
         for each cell ${C_k}$ of ${r_j}$ do
         if ${C_k}$_state == –1 then // ${C_k}$为不可用单元
          Construct_spare_path(${r_j}$);//根据双向冗余技术从空闲单元中选择备用单元
         end if
         if Reached (${r_j}$) == True do //输入流体已到达目标组件
          ${C_k}$_state = 0;//根据单元功能转换将流体${r_j}$占据单元转换为空闲单元
         end if
        end for
       end for
      end for
    下载: 导出CSV

    表  1  图3对应的绑定与调度方案

    时间(s) 动作
    $0$–$ {t_{\text{c}}} $ 分别运输输入流体${r_1}$, ${r_3}$, ${r_5}$到
    组件${M_1}$, ${M_2}$, ${M_3}$
    $ {t_{\text{c}}} $–$2{t_{\text{c}}}$ 分别运输输入流体${r_2}$, ${r_4}$到组件${M_1}$, ${M_2}$
    $2{t_{\text{c}}}$–($2{t_{\text{c}}} + 4$) 执行混合操作${O_1}$, ${O_2}$
    $\left( {2{t_{\text{c}}} + 4} \right)$–$\left( {3{t_{\text{c}}} + 4} \right)$ 运输${O_1}$, ${O_2}$的混合产物到混合器${M_3}$
    $\left( {3{t_{\text{c}}} + 4} \right)$–$\left( {3{t_{\text{c}}} + 8} \right)$ 执行混合操作${O_3}$
    下载: 导出CSV

    表  2  策略有效性对比结果

    测试用例 (输入流体数,输出流体数,
    混合操作数)
    FPVA
    尺寸
    生物测定完成时间(s) 流体运输路径总长度(mm)
    基准算法 本文算法 优化(%) 基准算法 本文算法 优化(%)
    PCR (8,1,7) $ \times $$8 \times 8$ 14.5 13.8 4.8 56.9 54.4 4.4
    IVD1 (12,6,6) $8 \times 8$$ \times $ 7.2 6.5 9.7 84.0 82.3 2.0
    IVD2 (18,9,9) $10 \times 10$$ \times $ 8.8 8.4 4.5 174.3 171.3 1.7
    ProteinSplit1 (14,2,12) $10 \times 10$$ \times $ 27.4 26.9 1.8 126.4 122.5 3.1
    ProteinSplit2 (32,4,23) $13 \times 13$ 35.4 33.8 4.5 491.6 486.6 1.0
    Synthetic1 (5,1,4) $8 \times 8$ 13.5 12.8 5.2 37.2 35.8 3.8
    Synthetic2 (13,1,12) $10 \times 10$$ \times $ 22.6 21.8 3.5 121.6 116.8 3.9
    Synthetic3 (18,1,17) $12 \times 12$ 28.1 27.4 2.5 217.6 210.7 3.2
    Synthetic4 (22,1,21) $13 \times 13$ 27.4 26.6 2.9 312.6 305.4 2.3
    Synthetic5 (27,1,26) $13 \times 13$ 29.9 28.7 4.0 386.9 377.2 2.5
    平均值 4.3 2.8
    下载: 导出CSV

    表  3  与RAS-FT[5]的性能对比结果

    测试用例生物测定完成时间(s)流体运输路径总长度(mm)容错成功率(%)
    RAS-FT[5]基于本文算法的
    架构综合算法
    优化(%)RAS-FT[5]基于本文算法的
    架构综合算法
    优化(%)RAS-FT[5]基于本文算法的
    架构综合算法
    优化
    PCR21.213.834.982.854.434.3100.053.047.0
    IVD111.56.543.5121.982.332.5100.040.060.0
    IVD214.38.441.3239.8171.328.6100.038.062.0
    ProteinSplit138.726.930.5173.1122.529.2100.013.087.0
    ProteinSplit250.133.832.5732.0486.633.5100.03.097.0
    Synthetic118.112.829.357.135.837.3100.029.071.0
    Synthetic230.021.827.3181.8116.835.8100.025.075.0
    Synthetic336.427.424.7327.4210.735.6100.016.084.0
    Synthetic435.826.625.7401.6305.424.0100.011.089.0
    Synthetic538.528.725.5505.3377.225.4100.08.092.0
    平均值31.531.676.4
    下载: 导出CSV
  • [1] VERPOORTE E and DE ROOIJ N F. Microfluidics meets MEMS[J]. Proceedings of the IEEE, 2003, 91(6): 930–953. doi: 10.1109/JPROC.2003.813570.
    [2] HU Kai, DINH T A, HO T Y, et al. Control-layer routing and control-pin minimization for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 36(1): 55–68. doi: 10.1109/TCAD.2016.2568198.
    [3] POLLACK M G, SHENDEROV A D, and FAIR R B. Electrowetting-based actuation of droplets for integrated microfluidics[J]. Lab on A Chip, 2002, 2(2): 96–101. doi: 10.1039/b110474h.
    [4] 陈志盛, 朱予涵, 刘耿耿, 等. 考虑流端口数量约束下的连续微流控生物芯片流路径规划算法[J]. 电子与信息学报, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168.

    CHEN Zhisheng, ZHU Yuhan, LIU Genggeng, et al. 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.
    [5] TSENG T M, LI Bing, HO T Y, et al. Reliability-aware synthesis for flow-based microfluidic biochips by dynamic-device mapping[C]. 2015 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6. doi: 10.1145/2744769.2744899.
    [6] 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.
    [7] LI Bing and SCHLICHTMANN U. Reliability-aware synthesis and fault test of fully programmable valve arrays (FPVAs)[C]. 2017 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, Cambridge, UK, 2017: 1–1. doi: 10.1109/DFT.2017.8244449.
    [8] 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 (CSUR), 2022, 54(5): 97. doi: 10.1145/3450504.
    [9] 刘耿耿, 叶正阳, 朱予涵, 等. 连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法[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.
    [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] HU Kai, YU Feiqiao, HO T Y, et al. Testing of flow-based microfluidic biochips: Fault modeling, test generation, and experimental demonstration[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(10): 1463–1475. doi: 10.1109/TCAD.2014.2336215.
    [12] ESKESEN M C, POP P, and POTLURI S. Architecture synthesis for cost-constrained fault-tolerant flow-based biochips[C]. 2016 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2016: 618–623.
    [13] DUBROVA E. Fault-Tolerant Design[M]. New York: Springer, 2013: 185. doi: 10.1007/978-1-4614-2113-9.
    [14] CHOUDHARY G, PAL S, KUNDU D, et al. Transport-free module binding for sample preparation using microfluidic fully programmable valve arrays[C]. 2020 Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, 2020: 1335–1338. doi: 10.23919/DATE48585.2020.9116370.
    [15] 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.
    [16] SU Y S, HO T Y, and LEE D T. A routability-driven flow routing algorithm for programmable microfluidic devices[C]. 2016 21st Asia and South Pacific Design Automation Conference, Macao, China, 2016: 605–610. doi: 10.1109/ASPDAC.2016.7428078.
    [17] LAI Guanru, LIN Chunyu, and HO T Y. Pump-aware flow routing algorithm for programmable microfluidic devices[C]. 2018 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2018: 1405–1410. doi: 10.23919/DATE.2018.8342232.
    [18] YING Shuaijie, ROY S, HUANG J D, et al. Design for restricted-area and fast dilution using programmable microfluidic device based Lab-on-a-Chip[C]. 2021 24th Euromicro Conference on Digital System Design, Palermo, Italy, 2021: 488–494. doi: 10.1109/DSD53832.2021.00079.
    [19] GRIMMER A, KLEPIC B, HO T Y, et al. Sound valve-control for programmable microfluidic devices[C]. 2018 23rd Asia and South Pacific Design Automation Conference, Jeju, Korea (South), 2018: 40–45. doi: 10.1109/ASPDAC.2018.8297280.
    [20] LIN Y H, HO T Y, LI Bing, et al. Block-flushing: A block-based washing algorithm for programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1531–1536. doi: 10.23919/DATE.2019.8715125.
    [21] 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.
    [22] 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.
    [23] LIANG Siyuan, LI Mengchu, TSENG T M, et al. CoMUX: Combinatorial-coding-based high-performance microfluidic control multiplexer design[C]. 2022 IEEE/ACM International Conference on Computer Aided Design, San Diego, USA, 2022: 1–9.
    [24] 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.
    [25] CAI Huayang, LIU Genggeng, GUO Wenzhong, et al. Adaptive control-logic routing for fully programmable valve array biochips using deep reinforcement learning[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 564–569. doi: 10.1109/ASP-DAC58780.2024.10473962.
    [26] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Testing microfluidic fully programmable valve arrays (FPVAs)[C]. Design, Automation & Test in Europe Conference & Exhibition, Lausanne, Switzerland, 2017: 91–96. doi: 10.23919/DATE.2017.7926964.
    [27] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for microfluidic fully programmable valve arrays (FPVAs) with heuristic acceleration[C]. 2018 International Conference on IC Design & Technology, Otranto, Italy, 2018: 97–100. doi: 10.1109/ICICDT.2018.8399765.
    [28] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for flow-based microfluidic biochips with general architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(10): 2530–2543. doi: 10.1109/TCAD.2019.2948904.
    [29] BERNARDINI A, LIU Chunfeng, LI Bing, et al. Efficient spanning-tree-based test pattern generation for programmable microfluidic devices[J]. Microelectronics Journal, 2018, 79: 38–45. doi: 10.1016/j.mejo.2018.06.011.
    [30] BERNARDINI A, LIU Chunfeng, LI Bing, et al. Fault localization in programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1607–1610. doi: 10.23919/DATE.2019.8715023.
    [31] LIU Genggeng, ZENG Yuqin, ZHU Yuhan, et al. Towards automated testing of multiplexers in fully programmable valve array biochips[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 570–575. doi: 10.1109/ASP-DAC58780.2024.10473918.
    [32] LIU Genggeng, ZHU Yuhan, GUO Wenzhong, et al. Fault-tolerance-oriented physical design for fully programmable valve array biochips[C]. 2023 60th ACM/IEEE Design Automation Conference, San Francisco, USA, 2023: 1–6. doi: 10.1109/DAC56929.2023.10247720.
    [33] 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.
  • 加载中
图(5) / 表(5)
计量
  • 文章访问数:  63
  • HTML全文浏览量:  31
  • PDF下载量:  6
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-01-24
  • 修回日期:  2024-09-04
  • 网络出版日期:  2024-09-17

目录

    /

    返回文章
    返回