基于桶的跟踪算法

摘要

基于桶的跟踪算法属于集成电路计算机辅助设计领域，尤其涉及版图验证领域。通常采用的划分算法是Gemini/GeminiII，即对Layout和Schematic两个图中的Instances和Nets进行签名，如果不能区分，则通常采用“引入签名半径”的方法，但这种方法的缺点是对签名函数要求很高且计算量大，另外在签名时须记录每个Instance/Net的“波前”，故空间复杂度高。本发明利用已有跟踪算法和划分算法的基本原理，将跟踪算法基于匹配点跟踪扩展到基于桶跟踪，将跟踪算法从匹配点出发找唯一性的结点扩展到从桶出发按Instance的类型或Net的度和签名值相等的原则分组生成新的桶，不仅可以完成跟踪的功能而且可以完成划分的功能，集跟踪与划分于一体。

主权项

1.一种基于桶的跟踪算法，其特征在于包括以下步骤：①调用初始划分算法生成初始桶集；②从初始桶集中取出一个桶开始局部划分：若有未用且不包含错误的桶，则从这些桶出发调用BucketTraceWithoutError算法进行划分；若无未用且不包含错误的桶，但有未用且包含错误的桶，则从这些桶出发调用BucketTraceWithError算法进行划分；重复执行②直至初始桶集为空。