连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法

刘耿耿 叶正阳 朱予涵 陈志盛 黄 兴 徐 宁

①(福州大学计算机与大数据学院 福州 350116)

②(中国科学院计算机体系结构国家重点实验室 北京 100190)

③(西北工业大学计算机学院 西安 710072)

④(武汉理工大学信息工程学院 武汉 430070)

1 引言

连续微流控生物芯片(Continuous-Flow Microfluidic Biochips, CFMBs)，也称为片上实验室，集成了必要的生化功能组件(如混合器、加热器、过滤器和检测器等)[1]，具有许多优点，如高精度、高通量、高自动化、小型化和低样品消耗等[2]。因此近些年受到越来越多的关注，并被成功地应用到核酸提取[3]、快速病原体检测[4]和DNA分析[5]等应用中。

CFMBs由弹性体材料聚二甲基硅氧烷(Poly-DiMethylSiloxane, PDMS)制造，利用多层软光刻工艺[6]加工得到其结构，可以集成数百甚至数千个微阀门[7]，并通过组合和控制多个微阀门的关闭和开启，可以建立更为复杂的操作，如分离、过滤和混合等。

CFMBs具有两个物理层：流层和控制层。在CFMBs的流层物理设计中，需要对所有的组件和流通道进行布局和布线。由于每增加一个流通道交叉点，会增加2～4个微阀门，用于必要的流体流通控制，不仅使得交叉污染等问题更为复杂，也显著增加了控制层的设计难度；而更短的流通道长度不仅能缩减流体运输延迟[8]，且仅需要更小的外部压力来传输流通道流体，减少通道流体泄露和阻塞等问题的可能性，增强流通道传输的可靠性[9]；同时芯片流层整体面积的缩减，有助提升芯片的集成度，降低芯片成本。因此，采用3个重要的指标：流通道交叉点数量、流通道总长度和芯片流层整体面积衡量其质量。

文献[9]首次提出一种CFMBs自顶向下的整体设计流程。但布局和布线两个阶段被分开考虑、缺乏交互，导致流层物理设计质量退化。Wang等人[10]首次提出了协同设计布局和布线，通过迭代的布局调整，动态地把布线信息反馈到布局中，进一步改善了流层物理设计的质量。该工作的布局阶段使用传统的模拟退火算法；布线阶段采用基于协商的布线算法，并依靠迭代削弱布线顺序的影响；针对组件与流通道产生的拥塞区，做面积增量布局调整。在此基础上，朱予涵等人[11]改进了随机算法，引入具有良好全局优化能力的离散粒子群优化算法完成初始布局；布线阶段使用基于协商的布线算法，以组件间曼哈顿距离降序作为布线顺序；布局调整阶段取消了拥塞区的设置，针对流通道交叉点，同样做面积增量布局调整。该工作在时间成本与文献[10]中相近的情况下，一定程度上提升了流层物理设计质量。考虑到实际流体传输的路径规划等问题，Huang等人[12]提出了一种名为PathDriver+的实用设计流程。针对有限资源下流体的存储需要，文献[13]提出了基于存储和运输两用的分布式流通道存储。为了解决不同阶段设计不同步的问题，文献[14,15]将所有阶段合成为一个有机的整体。

针对当前流层物理设计质量和效率难以同时兼得的问题，本文提出了一种多阶段启发式的流层物理协同设计算法，不仅显著提高了流层物理设计的质量，同时使得时间成本大幅下降，为解决大规模问题提供了新途径。本文主要贡献如下：

(1) 提出了一种新的布局算法：逻辑布局。该算法把每个组件初始为逻辑空间中的每个单元，基于组件之间的连接关系，利用邻近移动和目标跳跃两种交换操作，能够高效地获得所有组件的优异逻辑位置。

(2) 在布局调整过程中，不仅考虑到组件对象，而且首次考虑到组件上具体连通端口的方位，进一步缩小粒度，提出考虑组件连接关系的组件方向布局调整策略，有效减少了流通道交叉点数和流通道总长度。

(3) 基于单个连通图内部组件之间的连接关系，提出了一种沿流通道收缩的布局调整策略，利用已有布线信息，显著减小了流通道总长度。

(4) 考虑到存在单连通图和多连通图的两种组件连接关系，通过多图收缩策略，对含有多个连通图的测试用例进行新一轮的布局调整，有效降低了芯片流层整体面积。

(5) 在6个测试用例上对包括以上的主要优化策略进行实验分析，同时与现有的流层物理设计协同算法进行最终实验对比，验证了本文算法的有效性。

本文的其余部分组织如下。第2节介绍了问题模型。第3节介绍了本文方法的算法整体设计流程。第4节详细介绍了算法具体细节步骤。第5节介绍和讨论了实验结果。第6节总结了全文。

2 问题模型

由时序图和组件列表作为输入，进行高层次综合[9](即绑定和调度)后，可以得到组件间连接网。本文的问题模型以组件列表和组件间连接网作为问题输入，在满足约束条件前提下，输出高质量的流层物理设计解。具体描述如下：

问题输入：组件列表和组件间连接网。

问题输出：CFMBs的流层物理设计解。

优化目标：最小化流通道交叉点数量、流通道总长度和流层整体面积的权重和。

约束条件：(1)组件间距最小约束，(2)流通道宽度最小约束，(3)流通道间距最小约束。

3 整体设计流程

如图1中3种颜色的模块所示，整体设计流程主要分为3个阶段，分别为布局预处理、组件映射和包围盒间隙布局调整、收缩布局调整。主要包括逻辑布局、组件方向布局调整、包围盒间隙布局调整、沿流通道收缩和多图收缩等策略。

图1 算法整体设计流程

第1阶段：布局预处理。包括逻辑布局和组件方向布局调整两种算法，旨在分别实现组件在逻辑空间中优异的逻辑位置和逻辑方向。首先，逻辑布局先初始化逻辑空间，再基于组件间的连接关系，利用逻辑布局中两种组件的位置交换操作，使得存在连接关系组件之间的曼哈顿距离尽可能小，即达到聚集的效果，以获得优异的逻辑位置。其次，本文进一步缩小粒度，设计了考虑端口的组件方向布局调整策略，通过调整组件的逻辑方向，使得连接组件上连通端口之间的曼哈顿距离尽可能小，以获得优异逻辑方向。两种算法都能有效减少流通道总长度和流通道交叉点数量。

第2阶段：组件映射和包围盒间隙布局调整。首先，为了将组件从逻辑位置映射到实际位置，同时保持第1阶段结束后组件优异的逻辑位置和逻辑方向，本文设计了包围盒策略放置组件，即统一用一个边长最小的正方形容器盒包裹所有的组件，再把每个包围盒以统一的初始间隙映射到实际布局布线物理空间中。其次，组件放置完成后，基于流通道两端组件曼哈顿距离的升序顺序，对所有流通道进行布线操作，获得初始包围盒间隙下的流层物理设计解。最后，为了最大化当前流层物理设计质量，再针对包围盒间隙，做增大间隙的布局调整，并迭代整个过程，直至达到设置的间隙阈值。迭代结束后，获得最佳的包围盒间隙。

第3阶段：收缩布局调整。在利用前一个阶段的最佳包围盒间隙做完布局布线的基础上，本文分步实现两种基于收缩的布局调整方法：沿流通道收缩和多图收缩。首先，为了减少流通道总长度，考虑到组件的端口数量较少，可以让组件从自身端口开始，沿已布线流通道向连接组件端口收缩。其次，若应用中存在多个连通图，则在沿流通道收缩后，连通图(包括单个连通图内所有的组件和流通道)之间可能存在较大的冗余间隙。为了进一步优化流层整体面积，本文提出了多图收缩策略，可以有效降低图与图之间的面积冗余，使得整体结构更为紧凑。

4 算法具体步骤

(1)布局预处理

(a)逻辑布局。基于序列对的布局表示方式，文献[10,11]运用随机算法做布局，虽然整体上能够得到一个较好的布局解，且直接得到组件的实际物理布局位置，但布局解质量存在波动，进而使得最终流层物理设计质量产生不稳定的波动。同时两者的时间成本随着问题规模的增大快速攀升。因此，本文分两步来实现传统布局的功能，提出了逻辑布局这种新算法，旨在先高效地获得一个收敛稳定且聚集效果好的高质量逻辑布局解，再通过具体组件放置的方法，将组件的逻辑位置映射为实际物理位置。

如图2所示，首先，按照组件序号升序顺序，把每个组件依次放入逻辑空间的每个单元，组件序号用正整数表示，空的逻辑位置用零表示，实现逻辑空间的初始化。其次，再基于组件之间的连接关系，通过邻近移动和目标跳跃两种交换操作，以达到聚集效果，即连通的组件单元在逻辑空间中的曼哈顿距离尽可能小。可以看出，逻辑布局并不改变逻辑空间的大小。

图2 逻辑空间初始状态

如图3(a)所示，邻近交换操作针对的是与组件6的4个方向上相邻的组件，并与其中一个净收益最大的组件单元交换逻辑位置，它们之间的曼哈顿距离都仅为1个单位。净收益是交换前两组件与所有连接组件的曼哈顿距离和，再减去交换后两组件与所有连接组件的曼哈顿距离和的差值。净收益计算为

图3 两种组件单元交换操作

其中，a为主动交换组件，b为被动交换邻近组件；an为与组件a连接组件数量，bn为与组件b连接组件数量；o为东西南北4个方向上的某个方向，d为两组件之间的曼哈顿逻辑距离，be代表组件交换之前，af代表组件交换之后。

计算完所有组件4个方向上的净收益后，与最大收益方向上的组件交换逻辑位置，迭代计算和交换这个过程，直到所有组件4个方向的净收益都小于等于零。如图3(b)所示，由于计算的先后顺序等，图中间部分已经存在聚集效果很好的组件群，表示为桔黄色的矩形区域。由于邻近交换的步长仅为1，此时向左移动交换的净收益又小于等于零，通过邻近交换操作，组件32越不过桔黄色区域，以靠近与之有连接的目标组件6，因此目标跳跃这种交换操作被提出。

与邻近移动操作相同，目标跳跃操作也是基于连接组件的曼哈顿距离评估收益。首先，选取曼哈顿距离最大且未锁定的边，按照边两端组件各自度占两者度和的概率，分配角色给这两个组件，较大概率组件为目标组件，另一个组件为跳跃组件。其次，若目标组件周围存在空的逻辑位置，跳跃组件则直接跳跃到该位置；若目标组件的周围不存在空的逻辑位置，则在周围8个组件中随机选中一个组件，用式(2)计算净收益

其中，e为边总数，式中计算所有边两端组件在跳跃动作前后的曼哈顿距离差值。

接着按照顺时针方向遍历，直至得到第1个与跳跃组件交换位置，且交换净收益非负的组件，执行目标跳跃操作；若周围所有组件交换位置的净收益都为负，则放弃目标跳跃。本轮给该边上锁，迭代至所有边被锁定，接着解锁所有边开始新一轮迭代，重复这个过程，直至达到内层迭代阈值或存在式(1)中净收益为正，如算法1步骤2(3)所示，结束内层目标跳跃迭代，进入外层邻近移动迭代。目标跳跃的直接目标是在至少不恶化当前布局质量的前提下，通过改变当前组件逻辑布局结构，以打破邻近移动收益瓶颈，使得存在组件邻近移动的净收益为正。为了适应测试用例规模，实际实验中外层迭代次数阈值设置为500，内层迭代次数阈值设置为150。

逻辑布局的直接作用是让存在边的组件达到聚集效果。算法1给出了逻辑布局算法的整体流程，主要包括两层的迭代。外层通过邻近移动来获得正的净收益；内层通过目标跳跃动作，在不恶化整个逻辑空间布局的前提下，调整当前布局结构，以获得邻近方向上正的净收益。如图4所示，图4(a)为初始布局后的布线结果，图4(b)为逻辑布局后的布线结果，深灰色区域放置与左边两个组件有流通道相连的组件。可以看出，图4(b)的连接组件之间达到聚集效果，使得流通道总长度显著降低，并且有减少流通道交叉点数的作用。

图4 逻辑布局效果示意图

(b)组件方向布局调整。文献[10,11]的工作中忽略了组件上端口的方向。然而，组件间试剂的传输需要依靠流通道，流通道的两端需要具体到组件的对应端口。因此，组件上端口朝向对流通道布线质量有着明显的影响，本文在默认组件方向基础上，提出了组件方向布局调整这一阶段。如图5所示，每个组件中的数字是其序号，在左右两图中，组件的逻辑位置并没有变化，同时组件1、组件2和组件25很好地聚集在与它们存在连接的组件19旁边。然而，图5(a)中采用组件左边输入端口，组件右边输出端口的默认组件布局方向，与之相比，组件方向布局调整后的图5(b)中流通道长度大大减少，同时避免出现图5(a)中标记为红色这种过长流通道。

图5 组件方向布局调整效果示意图

算法1 逻辑布局算法

该调整策略计算组件各个端口与对应连接组件之间的曼哈顿距离和，以获得最小距离方向作为组件优化后的布局方向。端口的逻辑位置是与端口相邻的逻辑单元位置相同。组件2唯一输出端口的逻辑位置与组件19的逻辑位置相等，两者距离为零。图5(a)中组件2唯一输出端口到组件19的距离为两个单位。

(2)组件映射和包围盒间隙布局调整

(a)包围盒策略放置组件。在第1阶段的工作结束后，得到了优异的组件逻辑位置和逻辑方向，接着需要实现组件逻辑位置到实际物理位置的映射，获得物理布局解。因此，本文采用了包围盒策略放置组件。

包围盒策略，即统一使用等面积的最小正方形包围盒作为容器，包裹每个组件，其边长等于所有组件在两个维度上的最大尺寸。

如图6所示，图中蓝色带序号的矩形块均为放置组件，9个大小相等的边界正方形则为包围盒，所有组件默认放置在包围盒的左上角，包围盒之间的初始间距为1个单位。可以看出，包围盒策略出色地继承了第1阶段的组件逻辑位置和逻辑方向。

图6 包围盒策略放置组件

(b)实际布线评估。为了衡量某一包围盒间隙下的布局质量，通过实际布线评估布局质量，其适应度值函数的计算式为

其中，C为布局布线工作后的流通道交叉点数，L为流通道总长度，A为流层整体面积。α,β,γ为权重，在实验中分别为300, 20和1，权值与文献[10,11]中一致，之后所有实验对比的权重和也是基于该式计算。

布线算法上，本文使用两阶段的A*算法对所有流通道进行布线。在第1阶段，不允许流通道产生交叉点的前提下，让尽可能多的流通道成功布线；在第2阶段，解除不允许产生流通道交叉点的限制，对前一阶段所有布线失败的流通道继续布线，直到所有流通道布线成功。该算法有利于在一定程度上减少流通道交叉点数量，也能保证在相对充裕布线资源情况下，整体流通道的布线成功。本文布线相关工作都是使用基于该布线顺下的两阶段A*布线算法。

(c)针对包围盒间隙的布局调整。首次放置组件后包围盒之间的初始间距设置为1个单位，布线资源可能不足。为了最大化流层物理设计质量，需要作进一步的布局调整。由于组件间的大小可能存在较大差距，若直接针对组件间隙做布局调整工作，则难以保存之前优异的组件逻辑位置，让存在连接关系的组件很好地聚集在一起。因此，本文提出了针对包围盒，做增大包围间隙的布局调整。

如图7所示，实现从图7(a)到图7(b)的包围盒间隙增大过程，每一轮仅增加一个单位。为了减少布线资源和计算资源的浪费，迭代中的最大间隙阈值不宜过大，设置为包围边长的一半并向上取整。当达到最大间隙阈值时结束迭代，并保存最佳的包围盒间隙。最大间隙阈值与应用中组件端口数量呈正相关关系。

图7 包围盒间隙布局调整示意图

(3)收缩布局调整

(a)沿流通道收缩。第2阶段工作结束后，考虑到之前提到部分组件可能与包围盒的面积差距较大，包围盒内存在较为充裕的布线空间。同时在生物芯片的应用场景中，组件的端口数量较小，一般为个位数，甚至存在度为1的叶子悬挂点组件，为单个图的收缩降低了难度。因此，本文提出了一种新的布局调整方式：沿流通道收缩。沿流通道收缩是将悬挂点组件沿着与之连通的唯一一条流通道，且满足约束的前提下，尽可能地缩短该流通道，并移动组件到相应的新位置。

如图8所示，图中有两个悬挂点组件发生了布局调整。在图8(a)中，组件默认放置于包围盒的左上角，但实际物理空间中存在足够的空间资源，让悬挂点组件调整到更好的位置。在图8(b)中，组件进行了沿流通道收缩的操作，与图8(a)对比，显著地减少了流通道长度，同时避免了一个流通道交叉点的产生。

图8 沿流通道收缩前后示意图

本文中的沿流通道收缩策略只是针对悬挂点组件，将来工作可以进一步考虑度大于1组件的多阶段收缩操作，在满足约束的前提下，使得单个图的连接结构更为紧凑，面积更小。

(b)多图收缩。上一阶段结束后，单个连通图的连接结构得到了优化。然而，若实例中包含多个连通图，则忽略了收缩后图与图之间可能存在的可观面积冗余。因此，在计算连通图的个数后，本文提出了新的布局调整方式，以实现能够在不改变流通道交叉点数和流通道总长度，且满足约束的条件下，达到优化流层整体面积效果。

多图收缩的具体策略是把单个图中所有的组件和流通道看作同质的图块，不改变图块的形状和方向，尽可能向物理空间西北方向移动靠拢。如图1所示，若应用用例只存在一个连通图，则跳过多图收缩阶段，直接输出最终的流层物理设计解；若存在多个连通图，则多图收缩优化后，再输出最终的流层物理设计解。

5 实验结果分析

本文方法基于C++语言实现，在3.00 GHz 4核CPU与8 GB内存的Windows环境中单线程执行，与文献[11]保持一致的运行环境，并使用了文献[11]中的算法原代码执行对比实验。

(1)策略有效性验证

为了更好地分析各阶段中主要策略对每个指标的优化效果，本文验证3个阶段中5个主要策略的有效性。

图9—图12展示的是3个阶段中5个主要策略完成后的实验各指标数据。其中，横坐标为5个策略的序号，1是逻辑布局策略，2是组件方向布局调整策略，因为这两个策略中还未获得最佳包围盒间隙，所以实验中暂设包围盒边长的1/4并向上取整作为包围盒间隙，3是包围盒间隙布局调整策略，4是沿通道收缩策略，5是多图收缩策略。纵坐标为各指标的数值范围。

图9 流层整体面积变化趋势

如图9所示，执行5个策略后，流层整体面积整体上得到了明显优化。由于PCR, ProteinSplit-1和ProteinSplit-2 3个测试用例中只存在单个连通图，所以面积上保持不变，图中表现为与x轴平行的线段。

如图10所示，前4个策略都使流通道总长度获得了明显优化。由于多图收缩策略不改变流通道总长度和流通道交叉点数量，所以在第5个策略多图收缩中，6个测试用例的流通道总长度保持不变。

图10 流通道总长度变化趋势

如图11所示，流通道交叉点数量整体保持较低水平。与图10中原因相同，第5个策略对流通道交叉点数量无影响。可以看出，图中3个测试用例的流通道交叉点数量存在一个V形反弹。这是由于最佳包围盒间隙小于前两步中暂设的包围盒间隙，而更小包围盒间隙意味着更少布线资源，可能会提高流通道交叉点数量。所以为了最小化权重和，产生了流通道交叉点数量反弹上升的现象。

图11 流通道交叉点数量变化趋势

如图12所示，前4个策略使权重和在6个测试用例中都得到了显著连续下降。由于多图收缩不改变流通道交叉点数量和流通道总长度，且与图9中相同原因，PCR, ProteinSplit-1和ProteinSplit-2 3个测试用例的流层整体面积也不发生改变，所以多图收缩策略对这3个测试用例的权重和无影响。

图12 3个指标权重和变化趋势

(2)与其他算法对比

为了验证本文算法的性能，将本文算法与文献[10]、文献[11]中的算法在5个指标上进行了对比。如表1所示，与文献[10]中算法对比，本文的算法在流层整体面积上平均优化了24.70%，流通道交叉点数量上平均优化了93.49%，流通道总长度上平均优化了75.70%，整体上获得了较大提升。因此，如表2所示，3个指标的权重和也得到了平均66.99%的优化效果。时间上获得平均151.46的加速比。同时加速比由ProteinSplit-1的21.90增加到Protein-Split-2的53.41，由InVitro-1的91.20增加到InVitro-3的524.15。可以看出，随着应用规模的增大，本文算法在时间成本上的对比优势也在扩大。

表1 与文献[10]最终实验结果3指标对比

表2 与文献[10]的最终实验结果对比

如表3所示，与文献[11]对比，本文算法在流层整体面积、流通道交叉点数量和流通道总长度上分别平均优化了20.22%, 54.66%和71.62%。因此，如表4所示，本文算法在3个指标权重和上平均优化了59.83。加速比平均为177.12。同时也达到了与文献[10]对比时的效果，应用规模越大，时间成本上的优势越大。

表3 与文献[11]最终实验结果3指标对比

表4 与文献[11]的最终实验结果对比

6 结论

针对连续微流控生物芯片，本文提出了一种多阶段启发式的流层物理协同设计算法，通过逻辑布局和组件方向布局调整，高效地获得优质的布局预处理方案，而后基于包围盒策略进行组件布局，实现组件从逻辑空间到实际物理空间的映射，并设计了包围盒间隙、沿流通道收缩和多图收缩3种策略进行布局调整。实验结果证明，本文算法不仅在流通道交叉点数量、流通道总长度和流层整体面积上获得显著提升，而且极大缩减了时间成本，提升了设计效率，为大规模应用设计提供了新方案。在未来工作中，我们致力于将本工作拓展到大规模且组件更为复杂的应用背景下，同时考虑布线转角数量等设计目标，使已有工作能更加直接高效地映射到实际应用中。