最小布尔不可满足子式的求解算法

 解释布尔公式不可满足的原因在众多领域都具有非常重要的理论与应用价值,而最小不可满足子公式能够为公式不可满足的原因提供精确的解释,帮助自动化工具迅速定位错误,诊断问题失败的缘由.针对最小不可满足子式的求解问题,提出并证明了布尔公式最小不可满足性与极大可满足性之间的关系.基于二者的关系,提出了求解最小布尔不可满足子式的贪心遗传算法与蚁群算法,并且通过实验与当前最好的方法分支-限界算法进行了对比,结果表明:两种算法在运算效率以及单位时间内剔除的短句数上都显著优于分支-限界算法,而贪心遗传算法优于蚁群算法.     

利用HOP模型提高布线速度

随着FPGA规模的不断扩大,基于千万门级FPGA芯片开发的用户设计,如何快速有效地完成布线,提高布线效率是一个关键问题。该文在探路算法的基础上利用HOP模型来提高布线速度,减少了布线运行时间。     

考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

一种带权动态调整的总体布线算法及其实现

本文对现有的总体布线方法及宏单元阵列总体布线问题进行了详细分析,提出了一种基于带权动态调整思想的适合于宏单元阵列一层半和双层版图模式的总体布线算法,其目标是合理地利用已确定的布线区域,使各线网均匀地分布在芯片上,获得尽可能高的布通率。     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

反熔丝FPGA布局布线算法研究

介绍了反熔丝FPGA及其布局布线算法的研究现状,讨论了目前最为流行的FPGA布局布线的基本原理与实现方式.针对反熔丝FPGA的结构对布局布线算法进行了改进,并在CAD实验平台上实现了改进算法.为了验证改进算法的性能,提出一种常见结构的反熔丝FPGA,并针对几个典型电路进行布局布线.实验结果表明,改进算法可以提高反熔丝FPGA布局布线的效率以及电路速度.     

基于动态网格的135度PCB区域布线算法

由于不断增长的芯片引脚数量、极高的引脚密度和独特的物理限制,印刷电路板(Printed Circuit Board,PCB)的手动布线已成为一项耗时的任务。近年来,高效率的自动化布线技术得到了广泛的研究。区域布线是PCB设计的一个重要组成部分。针对基于静态网格区域布线的方案,布线拥塞、布通率低等问题,本文提出了一套基于动态网格的135度区域布线算法,主要包括以下技术:(1)对当前布线采用实时扩展动态网格;(2)135度布线角度节点调整算法;(3)基于拥塞控制的改进A^*算法;(4)有效的拆线重布机制。实验结果表明,该算法对于所有工业界布线测试用例布通率都达到100%,并且运行时间方面优于工业布线器Free Routing和Allegro。     

一种改进的子集可满足性算法用于FPGA布线

介绍了用布尔可满足性(SAT)和子集可满足性(sub-SAT)算法解决FPGA的详细布线问题。在布线资源固定的FPGA布线环境中,布尔公式可以证明所给电路的不可布通性,这一点要优于典型的one-net-at-a-time方法。子集可满足性方法把一个有N个约束的"严格的"SAT问题转换成一个新的"松弛的"SAT问题,仅当在原始问题中变量的不可满足个数不超过阈值k(kN)时,这一问题是可满足的。它改进了布尔可满足性,但是却产生了很多额外的变量和子句。针对这一问题,提出了用伪布尔可满足性(PBS)来消除子集可满足性公式带来的缺点。初步的实验结果表明,把这个方法加入子集可满足性方法中可以减少变量和子句数量,并显著减少运行时间。     

一种新的基于知识的四边通道布线算法

本文提出了一种新的基于知识的双层四边通道布线算法,该算法对四边通道的布线是通过以下四步完成的。首先,对四边通道的四个角布线,其次,对关键线网优先布线,接下来,利用线网间相互制约关系进行同步增长布线;最后,对仍然没有完成连接的线网,用李氏算法布线。由于使用了启发式规则,使得该算法具有较高的布通率和布线效率。     

单主干权重排序布线算法

随着集成电路的发展,芯片的特征尺寸变得越来越小,模拟电路中的电流也变得越来越大,因大电流使互连线出现短路或开路的现象称为电迁移现象。针对电迁移现象,本文提出了一种单主干权重排序布线算法,它根据各端点电流值的大小将端点的布线顺序进行排序,使电流较大的线网先完成布线,以达到缩小布线面积的目标。这种算法满足了布线设计当中的基尔霍夫电流定律,最小设计规则以及避开障碍物等约束条件,最终实现多源多漏的线网拓扑结构。