随着芯片制造技术的不断发展和人们对于电子产品需求的不断提高,现在的芯片变得越来越复杂。集成在同一块芯片上的晶体管的数目通常都会达到上亿数量级。芯片的复杂性导致芯片的设计也变得更加复杂,要求更长的设计周期和更多的设计时间。在电子产品竞争白热化的今天,芯片更新换代的周期越来越短。芯片设计推向市场的周期不断被压缩。在短时间内快速设计出,复杂且工作正常的芯片变得越来越难。设计中不可避免会出现很多问题。新工艺的不断涌现和更小制程的出现,使得移植已有设计到最新的技术变得越来越平常。在电子设计自动化(EDA)软件中,布局、布线等常用算法都是NP算法。使用一次这些功能通常需要消耗数小时或者数天时间,这也对短时间内设计出工作正常的芯片提出很大的挑战。对物理版图的分析能够为定位芯片后端设计中遇到的问题提供很重要的帮助。对于芯片设计中碰到的问题,通常的方法是在EDA软件中查看可能发生问题的区域,然后执行布局、布线等算法来尝试解决问题。通常需要经过多次迭代才能最终解决问题。人工分析包含千万物理元素的整幅物理版图很容易出错。大量的时间被用于执行布局布线算法来验证分析的正确性。本论文提出了通过自动化地整幅或者部分地快速地比较两幅相似的物理版图或者同一幅物理版图的不同版本,为芯片设计人员发现两幅物理版图之间的差异,并提供用于消除两幅版图差异的脚本。对于两幅物理元素为千万级的复杂物理版图,运行整个物理版图的比较能够在数分钟内完成。设计人员对产生的差异进行分析,找到产生问题的原因,然后运行布局布线工具或者消除差异的脚本来修复错误。不同于传统方法,设计人员只需要对两幅版图的差异而不是整幅物理版图进行分析,极大地降低了需要分析的数据规模,减少运行布局、布线的次数和定位问题所需的迭代次数。设计人员可以通过设定比较算法运行在感兴趣的某一特定区域内或者某些物理元素上,使得产生的差异数量更少,分析更加有针对性。在本论文中,首先通过名字匹配的方法,进行逻辑比较,确定逻辑上等价的逻辑元素,然后进行物理版图的比较。在物理版图比较的第一步,首先按照物理属性把物理元素分类存储在自定义的树状数据结构中。通过对目标物理版图的树状结构深度遍历,对输入物理版图的树状结构进行查找,确定两幅物理版图中物理属性相同的物理元素。在物理版图比较的第二步,按照物理元素的坐标进行几何属性的比较。对于比较算法,本论文提出了在输入物理版图的树状结构中缓存搜索路径和为树状结构和物理元素指定不同的内存池两种优化方法。