高级检索

连续微流控生物芯片下基于序列对的流层物理设计算法

Sequence-Pair-Based Flow-Layer Physical Design Algorithm for Continuous-Flow Microfluidic Biochips

  • 摘要: 针对流层物理设计的2个阶段,即组件布局与布线通常被分开考虑,忽略了它们之间的交互作用,从而导致设计质量以及生物芯片执行效率下降的问题,提出一种有效的连续微流控生物芯片下基于序列对的流层物理设计算法.首先基于可以快速对布局方案进行枚举和计算的序列对表示方法,通过具有更高求解效率的离散粒子群优化算法得到组件布局解,进一步提高布局解的质量;然后在布线阶段将组件对之间的曼哈顿距离作为布线顺序的考虑依据,并通过基于协商布线算法进行布线,有效地减少流通道交叉点数量;最后考虑布局和布线的交互作用,根据布线的反馈信息进行针对流通道交叉点区域的布局调整,从而衔接组件布局与流通道布线阶段.采用实际生化应用反应与合成的基准测试集,复现基于模拟退火布局和协商布线的流层物理设计算法作为对比算法进行实验,结果表明,所提算法的流通道交叉点数量优化了74.94%,芯片面积优化了5.04%,流通道总长度优化了16.88%,得到高质量流层物理设计方案.

     

    Abstract: To address the problem that the two phases of flow-level physical design, i.e., component placement and routing, are usually considered separately and their interaction is neglected, resulting in the degradation of design quality and biochip execution efficiency, an effective sequence-pair-based flow-level physical design algorithm for continuous-flow microfluidic biochips is proposed. Firstly, based on the sequence-pair representation method which can quickly enumerate and calculate the placement solution, the component placement solution is obtained by the discrete particle swarm optimization algorithm with higher solving efficiency to further improve the quality of the placement solution. Then, the Manhattan distance between component pairs is considered as the basis for routing order in the routing stage, and the routing is performed by the negotiation-based routing algorithm to effectively reduce the number of crossings in the flow channel. Finally, the interaction between placement and routing is considered, and the placement is adjusted according to the feedback information of routing, thus bridging the component placement and routing phases. The benchmark test set of actual biochemical application reaction and synthesis is adopted, and the flow-level physical design algorithm based on simulated annealing placement and negotiated routing is reproduced as the comparison algorithm for the experiment. The experimental results show that the proposed algorithm optimizes the number of flow path intersections by 74.94%, the chip area by 5.04%, and the total flow path length by 16.88%, resulting in a high-quality flow path physical design solution.

     

/

返回文章
返回