考虑体积管理与通道存储的微流控生物芯片物理设计方法

1.本发明属于计算机辅助设计技术领域，具体涉及一种微流控生物芯片物理设计方法。


背景技术：

2.近年来，研究人员先后提出了一些微流控芯片架构设计方法来不断提高芯片性能并降低制造成本。wajid hassan minhass提出了一种自顶向下的设计流程来构建cfmbs流体层架构，同时最大程度地减少生化反应的执行时间。qin wang提出了一种基于序列对的物理设计方法，在布局阶段采用模拟退火算法来迭代调整布局的结果，布线阶段则采用基于协商的方法，统筹考虑物理设计的两个阶段。chun-xun lin引入了集成电路中的绕障直角斯坦纳树模型来降低芯片内的通道长度。kailin yang使用了任意弯曲角度的布线策略来代替具有90
°
拐角的传统曼哈顿通道，显著提高了布线的灵活性。huang x和xing huang把实际流体运输考虑在设计流程内，以实现cfmbs的设计自动化。xing huang提出了一种名为minicontrol的设计流程来系统地考虑了控制端口数量最小化。然而，上述的工作均是在具有专用存储器的传统芯片架构下实现的，并未考虑通道在流体存储方面的巨大潜力。
3.chunfeng liu首次提出了分布式通道存储架构体系(dcsa)，在此基础上引入了流体端口，进一步完善流通道存储的功能，xing huang将清洗任务融入到dcsa的高阶综合以及物理设计过程，最终生成一个基于分布式通道存储的物理设计方案。zhisheng chen首次提出了基于dcsa的流层物理设计问题，并提出了自顶向下综合算法来生成高效的解决方案。然而，上述工作均未考虑实际流体操作所引发的体积管理问题。
4.连续微流控生物芯片cfmbs由于其高效率、高精度、高吞吐量等优势，为生化检测的执行带来了革命性改变。目前，cfmbs已广泛地应用于生物化学和生物医学领域。如图1所示，cfmbs由流层和控制层两个物理层组成，其中流层中的通道被称为流通道，在外部压力源的推动下，生化样品和试剂便可在流通道中进行运输。控制层中的通道被称为控制通道，其与连通外部压力源的控制端口相连，用于控制流层与控制层衔接除放置的微阀门的开或关。在cfmbs中，通过微阀门的组合还可以建立专用存储器用于存储在生化反应执行过程中产生的中间流体，但这种存储方式存在以下几个限制：1)存储单元的容量有限；2)确定存储器位置后无法移动；3)存储器需占用较大的芯片面积；4)存储带宽有限。因此，为了解决上述诸多限制，dcsa允许每个组件在生化反应执行过程中产生的中间流体都可以在该组件附近的流通道内进行存储，这样就使得流通道可以根据实际需求在存储和传输两个功能间任意切换。而在dcsa下，由于每一段流通道的容积是有限的，如果需要存储的流体体积大于所选通道所能容纳的容积会导致有部分流体占用其他流通道，若去除这部分流体，可能会导致后续其他流体操作的流体输入体积不足，使得最终实验无法正常完成。反之，就可能会推迟其他流处理任务的执行，最终导致生化反应总完成时间大大延后。但目前尚未针对dcsa下的实际体积管理提出任何物理设计算法，因此，在物理设计阶段，详细考虑dcsa下流路径的规划，避免不同流处理任务之间产生资源冲突以及合理考虑流通道的容积约束对保证
cfmbs的正常执行起着至关重要的作用。


技术实现要素：

5.为了克服现有技术的不足，本发明提供了一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，在模拟退火的迭代过程开始前，预先设计了一个可行的初始解，初始解包括初始布局以及初始布线两个阶段；对于当前解的调整，提出了三种调整策略：1)平移组件或存储通道；2)旋转组件或存储通道；3)交换两组件的位置；在选择好某一调成策略后，需要拆除相关组件的布线，在执行完调整策略后进行布线重绕；最后，为了避免因调整策略而引发的冲突问题，本发明通过重调度技术对流处理任务的执行时间进行调整，从而使得每个调整后的解都是无冲突的。本发明将布局与布线通判考虑，有效地降低生化反应完成时间、流通道长度以及交叉点数量，大大提高布局布线的质量。
6.本发明解决其技术问题所采用的技术方案包括如下步骤：
7.步骤1：初始解布局阶段；
8.设置一个组件密集扩张区c于芯片中间用于将未放置的组件约束在c内；
9.而后计算每一个组件dm∈d'的优先级，计算公式如下所示：
[0010][0011]
其中，y
m,n
表示组件dm与组件dn之间的连接次数，y
k,m
表示组件dk与组件dm之间的连接次数，d'表示已分配的组件库；
[0012]
将所有的组件插入到优先队列中，并依次出队放置在c内，若c内没有空间放置下当前组件，则需扩大c直至符合放置条件为止；
[0013]
步骤2：初始解布线阶段；
[0014]
步骤2-1：设置流处理任务包括流体输入任务、多余流体移除任务、废余流体移除任务、源输入任务、流体存储任务、流体取出任务；
[0015]
步骤2-2：构造存储通道，先依据流处理任务的结束时间升序排序；采用扫描线算法将流处理任务进行分组，同一分组内的流处理任务并行执行；分组完毕后，对每个分组内的流处理任务依次布线，在本组任务布线前，降低之前已经布线过的网格单元代价，而后先判断流处理任务中绑定的流端口或废液端口是否已放置在端口层上，若未放置，则在端口层上选择一个可用位置使得该流端口或废液端口距离其绑定的流处理任务的组件距离最近，最后，根据流处理任务的类型使用a*算法构造相应的流通道，在构建流通道的过程中，a*算法会不断选择布线代价最小的网格单元进行布线，当前流处理任务t的流路径所对应的流通道到单元网格i的代价函数c
t
(i)计算如下：
[0016]ct
(i)＝g
t
(i)+h(i)
ꢀꢀꢀꢀꢀꢀ
(2)
[0017][0018]
其中，公式(2)中，h(i)为i到目标位置的曼哈顿距离与起始位置到i的曼哈顿距离之和；公式(3)中，g
t
(i)为t在布线时i当前的代价，init(i)为i的初始代价，δ为一个0-1变量；为目前所有布线过的流处理任务中，流路径经过i的任务数量；为经过i的存储
通道数量；inf为一无穷大量；
[0019]gt
(i)的大小会根据i上的布线情况而动态调整，情况1：若i上未有流路径布线于此，则g
t
(i)为init(i)；情况2：在同组流处理任务中，为了避免同组内并行的流处理任务产生资源冲突，一个流处理任务布线完毕后需要将其布线过的网格单元代价设为∞即δ＝1，否则，g
t
(i)会根据i上所布置的流通道数量以及存储通道数量来动态调整g
t
(i)；
[0020]
步骤3：生成临近解；
[0021]
在完成初始解后，该初始解被定义为curr_sol0，以此参与后续临近解的生成；
[0022]
通过以下三个调整策略来改变当前的布局布线解，策略一：随机选择一个组件改变其位置；策略二：随机选择一个组件顺时针旋转90
°
；策略三：随机选择两个组件交换其位置；
[0023]
将存储通道抽象为一个长度为n个单位、宽度为1个单位的组件并参与策略一和策略二；临近解的产生被定义为new_soli＝generate_neighbor(curr_sol
i-1
)，等概率选择一种调整策略并进行相应调整；
[0024]
在执行调整策略前，拆除被选中组件的流路径以及与这些流路径有交叉的其他流路径；在执行完调成策略后根据存储驱动的流路径规划算法来重新对拆除掉的流路径进行布线；
[0025]
步骤4：重调度；
[0026]
依据时序图确定各个流处理任务的前置任务，即当前流处理任务需要所有前置任务完成后才可能被执行；计算完前置任务后，需重新计算各个流处理任务的实际完成时间；若当前流处理任务task
curr
的开始时间早于所有前置任务的最大结束时间则需将该任务的开始时间延后到之后；而后对于与task
curr
的流路径有重叠的任务，为避免产生资源冲突，则需延后它们的开始时间至后；对于task
curr
的结束时间其计算公式如下：
[0027][0028][0029]
其中，为task
curr
的执行时间，volume(task
curr
)为task
curr
的流体体积，cv为流通道的单位体积，lengthc表示task
curr
的流通道长度，vc表示流体在流通道中的流速；
[0030]
步骤5：代价函数；
[0031]
在执行完重调度后，则需要比较new_soli与curr_sol
i-1
的质量，通过以下公式作为解的评估函数：
[0032]
costi＝α
×
timei+β
×
lengthi+γ
×
cross_numiꢀꢀꢀꢀꢀꢀ
(6)
[0033]
其中，timei为当前临近解的生化反应完成时间，lengthi为流通道总长度，cross_numi为交叉点数量，α,β,γ为三个给定的常数；
[0034]
若new_soli具有比curr_sol
i-1
更低的代价值，即
△
cost《0，则接受该解；在生成临近解的过程中，可能会使new_soli具有更高的代价值，即
△
cost》0,为了增强全局搜索能力
而避免陷入局部最优，模拟退火算法须以概率p来接受较差解，其中
[0035]
优选地，所述组件密集扩张区的初始面积为w和h为芯片的长度以及宽度，μ和η为大于1的整数。
[0036]
本发明的有益效果如下：
[0037]
本发明将布局与布线通判考虑，有效地降低生化反应完成时间、流通道长度以及交叉点数量，大大提高布局布线的质量。
附图说明
[0038]
图1为cfmb结构示意图。
[0039]
图2为本发明方法流程图。
具体实施方式
[0040]
下面结合附图和实施例对本发明进一步说明。
[0041]
本发明的目的是设计一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，从而得到优化了实际调度时间、流通道长度以及交叉点数量的物理设计解方案。
[0042]
本发明采用以下方案实现：一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，该方法流程图如图2所示，左侧列出了各阶段涉及的策略，右侧为所提方法的主要步骤。本发明通过模拟退火(simulated annealing,sa)算法将布局与布线通判考虑，有效地降低生化反应完成时间、流通道长度以及交叉点数量，大大提高布局布线的质量。
[0043]
本发明具体包括以下步骤：
[0044]
1.初始解的构造：在模拟退火的迭代过程开始前，预先设计了一个可行的初始解，初始解包括初始布局以及初始布线两个阶段，在布局方面，本发明提出了基于区域扩展与组件连接优先权的算法来生成初始布局。此外，布线的构造是后续迭代过程调整解的重要手段，因此，本发明提出了通道存储驱动的流路径规划来生成布线结果，从而获得一个无冲突的可行的物理设计解方案。
[0045]
2.模拟退火的迭代：首先，对于当前解的调整，本发明提出了三种调整策略：1)平移组件或存储通道；2)旋转组件或存储通道；3)交换两组件的位置。其次，在选择好某一调成策略后，需要拆除相关组件的布线，在执行完调整策略后进行布线重绕。最后，为了避免因调整策略而引发的冲突问题，本发明通过重调度技术对流处理任务的执行时间进行调整，从而使得每个调整后的解都是无冲突的。
[0046][0047]
1.初始解布局阶段
[0048]
本发明在布局阶段，设置一个初始面积为的组件密集扩张区c于芯片中间用于将未放置的组件约束在c内，其中，w和h为芯片的长度以及宽度，μ和η为大于1的整数，而后计算了每一个组件dm∈d'计算其优先级，计算公式如下所示：
[0049][0050]
之后将所有的组件插入到优先队列中，并依次出队放置在c内，若c内没有空间放置下当前组件，则需扩大c(即缩小μ和η)直至符合放置条件为止。
[0051]
2.初始解布线阶段
[0052]
首先，为避免流通道内的多余流体以及组件内的废液流体对实验结果的影响，还需考虑流体移除任务，因此，实际的流处理任务包括流体输入任务、多余流体移除任务、废余流体移除以及源输入任务、流体存储任务、流体取出任务。
[0053]
其次，本发明考虑优先构造存储通道，使得整体线长更短，流通道利用率更高。在构建完存储通道后，先依据流处理任务的结束时间升序排序，之后为了避免资源冲突问题，本发明采用一种高效的扫描线算法将流处理任务进行分组，同一分组内的流处理任务并行执行。分组完毕后，对每个分组内的流处理任务依次布线，为了能更好地复用已经布线过的流通道，在本组任务布线前，降低之前已经布线过的网格单元代价，而后先判断流处理任务中绑定的流端口或废液端口是否已放置在端口层上，若未放置，则在端口层上选择一个可用位置使得该流端口或废液端口距离其绑定的流处理任务的组件距离最近，最后，根据流处理任务的类型使用a*算法构造相应的流通道，在构建流通道的过程中，a*算法会不断选择布线代价最小的网格单元进行布线，当前流处理任务t的流路径所对应的流通道到单元网格i的代价函数c
t
(i)计算如下：
[0054]ct
(i)＝g
t
(i)+h(i)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
[0055][0056]
其中，公式(2)中，h(i)为i到目标位置的曼哈顿距离与起始位置到i的曼哈顿距离之和，公式(3)中，g
t
(i)为t在布线时i当前的代价，init(i)为i的初始代价，δ为一个0-1变量，为目前所有布线过的流处理任务中，流路径经过i的任务数量，为经过i的存储通道数量，inf为一无穷大量，g
t
(i)的大小会根据i上的布线情况而动态调整，情况1：若i上未有流路径布线于此，则g
t
(i)为init(i)；情况2：在同组流处理任务中，为了避免同组内并行的流处理任务产生资源冲突，一个流处理任务布线完毕后需要将其布线过的网格单元代价设为∞即δ＝1，否则，为了更好的实现通道复用，g
t
(i)会根据i上所布置的流通道数量以及存储通道数量来动态调整g
t
(i)。
[0057]
3.生成临近解
[0058]
在完成初始解后，该初始解被定义为curr_sol0，以此参与后续临近解的生成。本阶段将通过以下三个调整策略来改变当前的布局布线解，策略一：随机选择一个组件改变其位置；策略二：随机选择一个组件顺时针旋转90
°
；策略三：随机选择两个组件交换其位置。在dcsa下，存储通道的位置对流体存储任务以及流体取出任务的流路径长度有着至关重要的影响，同时存储通道的容积也直接决定了存储通道的长度，若其位置选择不当，其他流处理任务的流路径可能因此而受到阻碍进而被迫选择更长的路径。因此，本发明将存储通道抽象为一个长度为n个单位，宽度为1个单位的组件并参与上述前两种调整策略。临近解的产生被定义为new_soli＝generate_neighbor(curr_sol
i-1
)，其会等概率选择一种调
整策略并进行相应调整。
[0059]
在执行调整策略前，应当拆除被选中组件的流路径以及与这些流路径有交叉的其他流路径。而组件的移动、交换或旋转可能会导致与其他组件重叠而产生无效的生成解，这种方案需要被剔除。在执行完调成策略后需根据存储驱动的流路径规划算法来重新对拆除掉的流路径进行布线。
[0060]
4.重调度
[0061]
在生成new_soli的过程中，拆除了部分流路径后进行调整策略，而后又重新布置这些流路径可能会引发资源冲突问题，此外，实际的生化反应的总完成时间需要计算各个流处理任务的开始时间以及完成时间来确定，因此上述问题需要在重调度阶段得以解决。
[0062]
本发明算法在重调度阶段会依据时序图确定各个流处理任务的前置任务，即当前流处理任务需要所有前置任务完成后才可能被执行。计算完前置任务后，需重新计算各个流处理任务的实际完成时间。若当前流处理任务task
curr
的开始时间早于所有前置任务的最大结束时间则需将该任务的开始时间延后到之后。而后对于与task
curr
的流路径有重叠的任务，为避免产生资源冲突，则需延后它们的开始时间至后。对于task
curr
的结束时间其计算公式如下：
[0063][0064][0065]
其中，为task
curr
的执行时间，volume(task
curr
)为task
curr
的流体体积，cv为流通道的单位体积，lengthc表示task
curr
的流通道长度，vc表示流体在流通道中的流速。
[0066]
5.代价函数
[0067]
在执行完重调度后，则需要比较new_soli与curr_sol
i-1
的质量，对于解的优劣，本发明通过以下公式作为解的评估函数：
[0068]
costi＝α
×
timei+β
×
lengthi+γ
×
cross_numiꢀꢀꢀꢀꢀꢀꢀ
(6)
[0069]
其中，timei为当前临近解的生化反应完成时间，lengthi为流通道总长度，cross_numi为交叉点数量，α,β,γ为三个给定的常数。
[0070]
若new_soli具有比curr_sol
i-1
更低的代价值，即
△
cost《0，则接受该解。在生成临近解的过程中，可能会使new_soli具有更高的代价值，即
△
cost》0,为了增强全局搜索能力而避免陷入局部最优，模拟退火算法须以概率p来接受较差解，其中
[0071]
本发明利用现实生化反应的4个基准测试以及5个合成的基准测试的结果来验证所提出的算法。表1展示了上述基准测试的基本信息，其中第2列表示每个基准测试包含的操作数，第3列表示每个基准测试所分配的组件，其格式为(混合器，加热器，过滤器，检测器，分离器)，第4列和第5列分别表示每个基准测试下所需的最大存储体积以及存储次数，第6列表示各个基准测试在高层次综合下的完成时间，第7列表示了各基准测试所需的芯片面积。
[0072]
表1所使用的基准测试详细信息
[0073][0074]
对比文献实现了针对分布式通道存储的cfmbs架构，但并未考虑到实际流体体积管理，为了验证本发明算法的有效性，本发明在基于对比文献的算法思想上引入了实际流体体积管理进行对比。
[0075]
表2显示了本发明与修改后的对比文献所提方法在流通道长度和交叉点数量上的比较结果，可以看出，本发明的方法在流通道长度上平均优化了21.57％，其中在基准测试实例synthetic5上可以最大优化32.35％。在交叉点数量方面，本发明的方法平均优化了33.12％，其中在基准测试实例ivd1上，可以最大优化40.00％，这种优化是统筹考虑了布局以及布线的结果，使得芯片架构更加紧凑。此外还得益于初始解的精心考虑以及将存储通道抽象为组件进行调整策略。
[0076]
表2与对比文献在流通道长度和交叉点数量的比较结果
[0077][0078]
因此，为了验证上述初始解布线阶段中介绍的存储驱动的流路径规划算法对最终结果的影响，在本发明的方法基础上设计了不考虑存储优先的布线方案，表3显示了本发明方法与不考虑存储优先的布线顺序在相同参数以及迭代次数下的对比，由于ivd1、ivd2、ivd3三个基准测试用例不涉及存储，故在此仅对比其余6个基准测试用例。由此可见，本发明的存储优先布线算法对最终结果有平均18.96％的流通道长度优化以及12.35％的交叉点数量优化。
[0079]
表3与不考虑存储优先的布线算法在流通道长度和交叉点数量的比较结果
[0080][0081]
在存储通道方面，为了说明存储通道的位置对流通道长度以及交叉点数量的影响，本发明的方法在模拟退火生成解阶段将存储通道抽象为组件，使其在退火过程中不断旋转、平移来优化最终结果，表4展示了本发明的方法与不考虑存储通道参与调整策略的对比，实验结果表明，本发明的方法在流通道长度上平均优化9.58％，在交叉点数量上平均优化14.99％。特别地，在存储次数较多的基准测试实例中，例如synthetic3以及synthetic5，本发明的方法可以达到20.00％以及12.21％的交叉点数量优化。
[0082]
表4与不考虑存储通道调整策略在流通道长度和交叉点数量的比较结果
[0083][0084]
本发明的方法在模拟退火过程中也将生化反应的完成时间作为评价物理设计结果的一项重要指标，因此，表5-表7分别展示了在生化反应完成时间上与修改后的对比文献方法、不考虑存储驱动的流路径规划算法以及不考虑存储通道调整的对比，从中可看出本发明的方法在与上述三者的对比中，分别取得平均20.33％、16.49％以及8.75％的优化。
[0085]
表5与修改后的对比文献在生化反应完成时间的比较结果
[0086][0087]
表6与不考虑存储驱动的流路径规划算法在生化反应完成时间的比较结果
[0088][0089]
表7与不考虑存储通道调整在生化反应完成时间的比较结果
[0090]

技术特征：
1.一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，其特征在于，包括如下步骤：步骤1：初始解布局阶段；设置一个组件密集扩张区c于芯片中间用于将未放置的组件约束在c内；而后计算每一个组件d
m
∈d'的优先级，计算公式如下所示：其中，y
m,n
表示组件d
m
与组件d
n
之间的连接次数，y
k,m
表示组件d
k
与组件d
m
之间的连接次数，d'表示已分配的组件库；将所有的组件插入到优先队列中，并依次出队放置在c内，若c内没有空间放置下当前组件，则需扩大c直至符合放置条件为止；步骤2：初始解布线阶段；步骤2-1：设置流处理任务包括流体输入任务、多余流体移除任务、废余流体移除任务、源输入任务、流体存储任务、流体取出任务；步骤2-2：构造存储通道，先依据流处理任务的结束时间升序排序；采用扫描线算法将流处理任务进行分组，同一分组内的流处理任务并行执行；分组完毕后，对每个分组内的流处理任务依次布线，在本组任务布线前，降低之前已经布线过的网格单元代价，而后先判断流处理任务中绑定的流端口或废液端口是否已放置在端口层上，若未放置，则在端口层上选择一个可用位置使得该流端口或废液端口距离其绑定的流处理任务的组件距离最近，最后，根据流处理任务的类型使用a*算法构造相应的流通道，在构建流通道的过程中，a*算法会不断选择布线代价最小的网格单元进行布线，当前流处理任务t的流路径所对应的流通道到单元网格i的代价函数c
t
(i)计算如下：c
t
(i)＝g
t
(i)+h(i)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)其中，公式(2)中，h(i)为i到目标位置的曼哈顿距离与起始位置到i的曼哈顿距离之和；公式(3)中，g
t
(i)为t在布线时i当前的代价，init(i)为i的初始代价，δ为一个0-1变量；为目前所有布线过的流处理任务中，流路径经过i的任务数量；为经过i的存储通道数量；inf为一无穷大量；g
t
(i)的大小会根据i上的布线情况而动态调整，情况1：若i上未有流路径布线于此，则g
t
(i)为init(i)；情况2：在同组流处理任务中，为了避免同组内并行的流处理任务产生资源冲突，一个流处理任务布线完毕后需要将其布线过的网格单元代价设为∞即δ＝1，否则，g
t
(i)会根据i上所布置的流通道数量以及存储通道数量来动态调整g
t
(i)；步骤3：生成临近解；在完成初始解后，该初始解被定义为curr_sol0，以此参与后续临近解的生成；通过以下三个调整策略来改变当前的布局布线解，策略一：随机选择一个组件改变其位置；策略二：随机选择一个组件顺时针旋转90
°
；策略三：随机选择两个组件交换其位置；将存储通道抽象为一个长度为n个单位、宽度为1个单位的组件并参与策略一和策略
二；临近解的产生被定义为new_sol
i
＝generate_neighbor(curr_sol
i-1
)，等概率选择一种调整策略并进行相应调整；在执行调整策略前，拆除被选中组件的流路径以及与这些流路径有交叉的其他流路径；在执行完调成策略后根据存储驱动的流路径规划算法来重新对拆除掉的流路径进行布线；步骤4：重调度；依据时序图确定各个流处理任务的前置任务，即当前流处理任务需要所有前置任务完成后才可能被执行；计算完前置任务后，需重新计算各个流处理任务的实际完成时间；若当前流处理任务task
curr
的开始时间早于所有前置任务的最大结束时间则需将该任务的开始时间延后到之后；而后对于与task
curr
的流路径有重叠的任务，为避免产生资源冲突，则需延后它们的开始时间至后；对于task
curr
的结束时间其计算公式如下：算公式如下：其中，为task
curr
的执行时间，volume(task
curr
)为task
curr
的流体体积，c
v
为流通道的单位体积，length
c
表示task
curr
的流通道长度，v
c
表示流体在流通道中的流速；步骤5：代价函数；在执行完重调度后，则需要比较new_sol
i
与curr_sol
i-1
的质量，通过以下公式作为解的评估函数：其中，time
i
为当前临近解的生化反应完成时间，length
i
为流通道总长度，cross
_
num
i
为交叉点数量，α,β,γ为三个给定的常数；若new_sol
i
具有比curr_sol
i-1
更低的代价值，即
△
cost<0，则接受该解；在生成临近解的过程中，可能会使new_sol
i
具有更高的代价值，即
△
cost>0,为了增强全局搜索能力而避免陷入局部最优，模拟退火算法须以概率p来接受较差解，其中2.根据权利要求1所述的一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，其特征在于，所述组件密集扩张区的初始面积为w和h为芯片的长度以及宽度，μ和η为大于1的整数。

技术总结
本发明公开了一种考虑体积管理与通道存储的微流控生物芯片物理设计方法，在模拟退火的迭代过程开始前，预先设计了一个可行的初始解，初始解包括初始布局以及初始布线两个阶段；对于当前解的调整，提出了三种调整策略：1)平移组件或存储通道；2)旋转组件或存储通道；3)交换两组件的位置；在选择好某一调成策略后，需要拆除相关组件的布线，在执行完调整策略后进行布线重绕；最后，为了避免因调整策略而引发的冲突问题，本发明通过重调度技术对流处理任务的执行时间进行调整，从而使得每个调整后的解都是无冲突的。本发明将布局与布线通判考虑，有效地降低生化反应完成时间、流通道长度以及交叉点数量，大大提高布局布线的质量。量。量。


技术研发人员：黄兴 於志文 郭斌 刘耿耿 陈正阳 刘辉 何宗易
受保护的技术使用者：西北工业大学
技术研发日：2023.05.16
技术公布日：2023/9/5