连续微流控生物芯片下存储最小化的高级综合设计方法

摘要

本发明涉及一种连续微流控生物芯片下存储最小化的高级综合设计方法，基于路径调度算法,其特征在于，包括以下步骤：步骤S1:根据给定时序图，遍历计算所有操作的优先权，确定操作的调度顺序；步骤S2:优先调度具有较小优先权的操作，计算特定组件的准备时间，选择准备时间最早的组件，绑定并执行所调度的操作；步骤S3:调度该操作优先权最小且就绪的子操作，进行绑定；步骤S4:调度执行给定时序图中所有的操作，得到一组绑定和调度解，以及组件之间的流体运输任务，完成高级综合设计。本发明能获得具有较少存储次数的连续微流控生物芯片的高级综合设计方案。

权利要求

1.一种连续微流控生物芯片下存储最小化的高级综合设计方法，基于路径调度算法,其特征在于，包括以下步骤：步骤S1:根据给定时序图，遍历计算所有操作的优先权，确定操作的调度优先权顺序；

步骤S2:优先调度所有操作中具有优先权小的操作，计算特定组件的准备时间，选择准备时间最早的组件，绑定并执行所调度的操作；

步骤S3:调度该操作优先权最小且就绪的子操作，进行绑定；

步骤S4:调度执行给定时序图中所有的操作，得到一组绑定和调度解，以及组件之间的流体运输任务，完成高级综合设计；

所述所有操作均具有两级优先权，将所有操作节点的第一级优先权设置为独立路径优先权，即该操作节点到收集槽的路径数量；所有操作节点的第二级优先权为关键路径优先权，该优先权为时序图中该操作节点到收集槽的最长路径的长度。

2.根据权利要求1所述的连续微流控生物芯片下存储最小化的高级综合设计方法，其特征在于，所述步骤S3具体为：优先调度所有操作中优先权小的操作，计算特定组件的准备时间，选择准备时间最早的特定组件，将操作绑定至该组件并执行，完成该操作；然后绑定和调度该操作优先权最小且就绪的子操作。

3.根据权利要求2所述的连续微流控生物芯片下存储最小化的高级综合设计方法，其特征在于，每一个组件ci∈C的准备时间tready(ci)，表示组件ci可用，其计算公式如公式(1)所示：tready(ci)＝tremove(oj)    (1)

其中，操作oj为先前绑定在组件ci的操作，tremove(oj)是操作oj从组件ci输出的时间点。

说明书

连续微流控生物芯片下存储最小化的高级综合设计方法

技术领域

[0001] 本发明属于微流控生物芯片设计技术领域，具体涉及一种连续微流控生物芯片下存储最小化的高级综合设计方法。

背景技术

[0002] 连续微流控生物芯片将样品和试剂的消耗量从毫升降至微升，甚至纳升级别，可以有效降低实验成本。随着制造工艺的不断进步，可以在单一芯片中集成数千个阀门和大规模的微通道网络，甚至更多，使得连续微流控生物芯片具有微型化、集成化等优点。同时，随着连续微流控生物芯片的集成度和设计复杂性的提高,最初的设计方法出现了新的难点，即使是使用现有的计算机辅助设计和电子设计自动化工具都很难应付。

[0003] 因此，研究人员提出了连续微流控生物芯片自上而下的自动化体系架构综合设计方法，将其分成流层物理设计与控制层物理设计。在连续微流控生物芯片的流层物理设计中，包括两个主要设计阶段：(1)高级综合阶段，将生化操作序列图中的操作按照特定的调度顺序绑定到组件库中对应的组件上执行，以确定所需的组件以及组件之间的流体运输任务。(2)物理设计阶段，将分配的组件布置到生物芯片中的确切位置，同时通过流通道在组件之间建立有效的连接。

[0004] 在整个连续微流控生物芯片的流层物理设计阶段中，研究人员需要预先知道所需要的组件以及组件之间的流体运输任务，以最大化连续微流控生物芯片的执行效率，因此高级综合阶段成为了整个流层物理设计中极其重要的一个环节。高级综合阶段需要完成以下两个目标：(1)寻找一个绑定函数，将每一个生化反应操作绑定到特定的组件上执行。(2)生成一个调度方案，使得时序图中所有的生化反应操作都能执行。高级综合阶段的结果将决定后续连续微流控生物芯片的物理设计难度，进而影响到整个物理设计的结果。因此，高级综合阶段是生物芯片流层物理设计过程中非常关键的阶段。

[0005] 在连续微流控生物芯片的流层上，有一种特殊的组件，即专用存储器(如图2所示)，用于存储暂时不需要进行生化反应操作的中间流体。由于生物芯片面积有限，可能会出现芯片上专用存储器内存储单元的数量少于需要同时存储的中间流体数量的情况，进而影响芯片的执行效率。因此，如果可以减少高级综合阶段中的存储次数和所需要的存储单元，则可以将图2(b)所示的专用存储器放置在生物芯片上，进而减少生物芯片的面积和流通道总长度。

发明内容

[0006] 有鉴于此，本发明的目的在于提供一种连续微流控生物芯片下存储最小化的高级综合设计方法，以减少存储次数、减少存储单元为目标，最终可得到较好的高级综合结果。

[0007] 为实现上述目的，本发明采用如下技术方案：

[0008] 一种连续微流控生物芯片下存储最小化的高级综合设计方法，基于路径调度算法,其特征在于，包括以下步骤：

[0009] 步骤S1:根据给定时序图，遍历计算所有操作的优先权，确定操作的调度顺序；

[0010] 步骤S2:优先调度具有较小优先权的操作，计算特定组件的准备时间，选择准备时间最早的组件，绑定并执行所调度的操作；

[0011] 步骤S3:调度该操作优先权最小且就绪的子操作，进行绑定；

[0012] 步骤S4:调度执行给定时序图中所有的操作，得到一组绑定和调度解，以及组件之间的流体运输任务，完成高级综合设计。

[0013] 进一步的，所述每一个操作均具有两级优先权，将每一个操作节点的第一级优先权设置为独立路径优先权，即该操作节点到收集槽的路径数量；每一操作节点的第二级优先权为关键路径优先权，该优先权为时序图中该操作节点到收集槽的最长路径的长度。

[0014] 进一步的，所述步骤S3具体为：优先调度优先权较小的操作，计算特定组件的准备时间，选择准备时间最早的特定组件，将操作绑定至该组件并执行，完成该操作。然后绑定和调度该操作优先权最小且就绪的子操作。

[0015] 进一步的，所述每一个组件ci∈C的准备时间tready(ci)，表示组件ci可用，其计算公式如公式(1)所示：

[0016] tready(ci)＝tremove(oj)   (1)

[0017] 其中，操作oj为先前绑定在组件ci的操作，tremove(oj)是操作oj从组件ci输出的时间点。

[0018] 本发明与现有技术相比具有以下有益效果：

[0019] 本发明每一个操作都有两级优先权，第一级为独立路径优先权，第二级为关键路径优先权；其次优先调度具有较小优先权的操作，将其绑定到特定的组件上，然后调度该操作优先权最小且就绪的子操作，进行绑定；最终得到一组绑定和调度解，获得具有较少存储次数的连续微流控生物芯片的高级综合设计方案。

附图说明

[0020] 图1是本发明一实施例中存储最小化高级综合设计方法流程图；

[0021] 图2是本发明一实施例中专用存储器示例图；

[0022] 图3是本发明一实施例中生化操作时序图；

[0023] 图4是本发明一实施例中两种高级综合设计方案结果对比图。

具体实施方式

[0024] 下面结合附图及实施例对本发明做进一步说明。

[0025] 请参照图1，本发明提供一种连续微流控生物芯片下存储最小化的高级综合设计方法，基于路径调度算法,其特征在于，包括以下步骤：

[0026] 步骤S1:根据给定时序图，遍历计算所有操作的优先权，确定操作的调度顺序；

[0027] 本实施例中，时序图中每一个操作都有两级优先权。将每一个操作节点的第一级优先权设置为独立路径优先权，即该操作节点到收集槽的路径数量；每一操作节点的第二级优先权为关键路径优先权，该优先权为时序图中该操作节点到收集槽的最长路径的长度。通过优先权来确认时序图中操作调度的前后顺序，以确保可以执行所有的操作；

[0028] 步骤S2:优先调度具有较小优先权的操作，计算特定组件的准备时间，选择准备时间最早的组件，绑定并执行所调度的操作；

[0029] 步骤S3:调度该操作优先权最小且就绪的子操作，进行绑定；

[0030] 步骤S4:调度执行给定时序图中所有的操作，得到一组绑定和调度解，以及组件之间的流体运输任务，完成高级综合设计。

[0031] 在本实施例中，所述步骤S3具体为：优先调度优先权较小的操作，计算特定组件的准备时间，选择准备时间最早的特定组件，将操作绑定至该组件并执行，完成该操作。然后绑定和调度该操作优先权最小且就绪的子操作。

[0032] 优选的，每一个组件ci∈C的准备时间tready(ci)，表示组件ci可用，其计算公式如公式(1)所示：

[0033] tready(ci)＝tremove(oj)   (1)

[0034] 其中，操作oj为先前绑定在组件ci的操作，tremove(oj)是操作oj从组件ci输出的时间点。

[0035] 实施例1：

[0036] 本实施例，以图3的时序图为例，图4显示了两种高级综合设计方案，分配了五个组件(包括一个混合器、一个加热器、一个过滤器、一个检测器、一个存储器)来执行该生化反应。图4(a)的调度顺序为o3→o1→o2→o4→o5→o6→o7→o8，当操作o3执行完成后，其生成的中间流体会被传输到专用存储器中，以空出加热器来执行操作o1。同时操作o2和操作o3的生成的中间流体需要同时存储在专用存储器，因此，需要2个存储单元。图4(b)为本实施例方法的调度结果，其调度顺序为o2→o1→o4→o6→o3→o5→o7→o8，该调度顺序并不产生存储操作。因此，在后续的流层物理设计中，不需要考虑在生物芯片上放置专用存储器，从而减少生物芯片的面积和流通道的总长度。

[0037] 算法采用C++编写，并在CPU为3.00GHz和RAM为8.00GB的Windows 10环境执行。

[0038] 本实施例用三个实际生化反应基准测试和四个合成基准测试(P.Pop,W.H.Minhass and J.Madsen,“Microfluidic Very Large‑Scale Integration(VLSI).”Springer International Publishing,2016.)作为测试用例用以验证所提出算法的有效性。表1显示了测试用例的详细信息，其中第2列是每个用例中包含的操作数，第3列为每个用例中包含的边数，第4列表示了以下格式的已分配组件列表：(混合器，加热器，过滤器，探测器，存储器)。

[0039] 为了验证本文高级综合设计算法的优越性，将本发明方法跟文献(W.H.Minhass,P.Pop and J.Madsen,"System‑level modeling and synthesis of flow‑based microfluidic biochips,"2011Proceedings of the14th International Conference on Compilers,Architectures and Synthesis for Embedded Systems(CASES).2011,pp.225‑233.)提出的高级综合算法(LS)进行对比，用以验证所提算法的有效性。结果如表2所示。以存储次数和存储单元为优化目标，我们的方法在每个测试用例在存储次数和存储单元方面都有较大的优化，分别优化了74.7％和61.4％的存储次数和存储单元。可见我们算法对最小化存储次数和存储单元十分有效。

[0040] 表1测试实例的详细信息

[0041]测试用例 操作数 边数 组件数
PCR 7 15 (2,0,0,0,1)
IVD 12 24 (2,0,0,2,1)
CPA 55 110 (4,0,0,2,1)
Synthetic1 20 33 (2,1,1,1,1)
Synthetic2 30 48 (2,2,2,2,1)
Synthetic3 40 62 (4,2,2,3,1)
Synthetic4 50 77 (5,3,3,2,1)

[0042] 表2本发明方法与LS[文献1]的实验结果对比情况

[0043]

[0044] 以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。