重置预期在多模式分解和检查

它从来没有停止让我有多少混乱和误解时多模式(MP)分解和检查。我有时会忘记新的主题在我们的行业。因为这短暂的历史,和有限的时间内设计师不得不获得任何详细的对其复杂性的理解,似乎有一些严重的脱节在EDA供应商之间的预期国会议员工具和使用它们的设计者和铸造厂。所以,我想花一些时间复习一些基本概念基本的两倍,三倍,四倍模式(DP, TP, QP),以及我们如何基于这些概念都认为改变我们的预期。

让我们从头开始。在DP过程中,这个想法是一个设计层分解为两个独立的面具。从本质上说,一些画形状将被放置在一个面具和其余的面具。这就是所谓的分解或着色。这听起来很简单,但我们都知道,有时候最简单的概念是最难实现的。首先,你不能任意选择绘制形状将这面具。设计规则间距约束限制距离形状相同的面具,所以你必须指定两个面具的形状,任何两个形状相同的面具不太接近对方。

图1显示了一个简单的例子,如何布局和设计规则捕获软件启用自动议员工具来完成这项任务。有一组6个多边形绘制布局。多边形之间的间距测量执行找出相邻多边形是否会打破空间限制,如果他们被放置在相同的面具。这些颜色交替需求通常称为分隔符。这些多边形和分隔符然后被捕获在一个虚拟图,该议员工具分析来确定是否有合法的方式把多边形之间的两个面具,面具和如果是这样的话,应该把每个多边形。每个多边形表示为图中的一个节点,而每个分隔符表示为图的边缘。注意,虚拟图(即不包含空间信息。大小或形状的多边形,多边形在空间的相对位置或彼此)。这个翻译从布局到虚拟图是至关重要的信息来确定色素进行有效的处理。

图1:翻译软件分析的布局在一个虚拟的图。

图2演示了一个示例DP检查这张图的分析。确定一个图是似是而非的DP相对简单,一个错误被定义为任何奇怪的循环图的连通性。在这个例子中,有一个奇怪的循环的三个节点图,由一个简单的计数检测算法。同样,应用着色图是相对简单的,因为相邻节点不能是相同的颜色和只有两个颜色的选择。开始在任何特定点,工具选择其中一个颜色,然后交替颜色从节点到节点移动时。一个简单的O (n)的算法可以完成这个(其中n是图中节点的数目)。这种类型的算法,运行时基本上是线性增长的尺寸图。

图2。色素分析的虚拟图。

如果你认为布局图分解成大量的小的组件(比如这个例子中,您可能期望分析广泛分布,导致很好的运行时。这是第一个误解,需要清理。在实践中,典型的设计往往形成少,非常大的DP组件,使得它难以分配处理大量的cpu。

还有另一个重要的一点注意到在这个例子。如您所见,它演示了两种可能的颜色输出,根据起点。你可能会问为什么选择一个不同的起点吗?这就是下一个误解。当我给一个例子这样的图在一张纸上,我得把它画平面和选择一个特定的安排和节点和边的方向。事实上,这张图是生成并存储在内存中没有物理定位作为一个层次结构。每个节点添加到图是遇到等级通过扫描线解析输入层。议员工具开始着色从层次结构中的第一个(最低),所以起点随不同的层次结构。

大多数人没有意识到有多少会影响DP着色过程的细节。EDA工具不仅仅是把画的层次结构,因为它出现在layout-they“优化”的层次,使数据处理更有效率。这个修改取决于输入层次结构,软件的版本,使用的运行模式,使用的数量和类型的硬件,等等。你可以很容易地得到不同的颜色每次运行议员工具,即使输入布局是一样的。始终得到相同的结果,你必须平数据,这将大大增加运行时和扁平产生的彩色输出(下游加工的损害)。

这可能会冲击你,大多数人把着色领域的设计规则检查(DRC)。这是另一个巨大的误解,需要澄清。刚果民主共和国的作用是告诉你如果你设计符合一组预定义的规则。在这个例子中,确定一个奇怪的循环是呈现在原始的布局,或萎靡不振的,两个相邻节点在一个彩色的布局有相同的颜色,适合刚果民主共和国的定义。然而,一层在布局和创建两个新色层的不符合刚果民主共和国的定义。它更适合自动化的定义布局generation-something更多的地点和路线(不)或虚填满的一代。随着这些应用程序,设计师们正熟悉和适应变化在每次运行的结果或版本。我们都知道,有一个以上的一块“正确”的方法途径。我们都知道,有超过一个“正确”的方式将假填写一个布局。我们需要熟悉和舒适,也有不止一个“正确”的颜色布局方式。 We also have to learn to expect that there is no way to guarantee that you will always get a particular result over and over again.

在这一点上,你可能在你的椅子有点局促不安,但你可能不太吓坏了。好吧,我给你一个更不舒服,通过展示如何染色结果的变化也会导致一个合法的变化在刚果民主共和国的结果。

在图3中,一个相对简单的图有两个奇怪的周期(红色所示)。一个是一个奇怪的循环三个节点,另一个是一个奇怪的循环五个节点。他们共同的两个节点和边缘图。有三种可能的色素产生的三种可能的起点。给定一个通过图形应用交替的颜色(基于我们O (n)的算法),这三个颜色的结果是完全合理的。然而,你可以看到他们产生三种不同的刚果民主共和国的结果当您运行间隔检查结果的节点。考虑到两个奇数周期,所有这三个post-coloring违反集也是完全合理的。

图3。刚果民主共和国的变化颜色的DP图组件的例子。

我知道,我知道…你想问,为什么不找一个总是产生色素的方法显示在中间,所以违反间隔只有一个,而不是其他色素产生两个间距违规?这就是预期和现实的碰撞。你看,保证工具总是发现特定的颜色生产的最小数量post-color间距违反意味着它可能会尝试所有可能的颜色组合。一个算法,尝试所有可能的颜色组合是O (2 ^ n)。相比与O (n)的算法,和知道随着n的增加,运行时呈指数增加,很明显这个算法会可怕的运行时。事实上,如果n变得大,它可能会运行几天,几周,年,甚至一生。你想要吗?当然不是。这就是为什么不要这样做的工具。

之前你都很激动,让我正确看待它。你持有同样的期望一个路由器吗?有很多次你运行一个路由器和最后一堆错误,因为路由器不能找到一种方法来路线一切。我保证你能找到一个替代的路线会产生更少的侵犯。事实上,在许多情况下,一个人可以找到一个路由,没有错误。在路由器的情况下,设计师甚至没有期望它会找到一个法律路由如果存在的话。他们只是希望它接近。为什么这样一个不同的期望一个同样具有挑战性的问题时喜欢布局分解吗?至少在DP的情况下,我们保证议员工具会发现至少有一个合法的着色,如果一个人的存在。

让我们看看布局分解的另一个方面,设计师通常有不切实际的expectations-preserving层次和密度平衡。每个人都知道,拥有良好的层次结构在下游数据会导致更好的运行时操作。所以设计者期望EDA工具的颜色设计尽可能的层级结构。转化为试图颜色形状在层次结构的最低水平,这意味着所有植入的细胞有相同的颜色。一旦彩色设计,设计师希望会有一个漂亮的制服颜色的变更设计,因为工厂刚果民主共和国限制密度平衡(统一的颜色密度在每一个面具,每个面具之间的比率在一个给定的地区)。鉴于这些期望,让我们来看一个例子。

在图4中,有两种细胞分层放置一个细胞。细胞包含一系列平行的多边形之间有足够的空间,他们的颜色是任意的(也就是说,任何颜色的组合将是合法的)。然而,从密度平衡的观点,交流他们的颜色将是首选,因为会出密度在两个面具。B细胞在同一层包含一个多边形的多边形细胞存在。计算单元B放置一次每个多边形细胞(总共6次)。保持完整,层次的多边形单元B需要同样的颜色在每个位置。但是因为它的多边形重叠细胞,所有的多边形细胞必须是相同的颜色,导致面具之间的不均匀密度。你必须牺牲层次或牺牲密度平衡。

图4:层次结构与密度平衡取舍。

让我们回顾一下适当的预期DP过程和结果:

• 你画的布局将抽象为一个虚拟图有效地分析着色的约束。
• 这些虚拟图形没有空间或定位信息。
• 虽然存在有效的算法来处理这个图表信息,远程DP交互的本质在一个典型的布局限制分布式处理的有效性。
• 层次生成、存储和处理这些图表意味着各种颜色的结果是可能的在相同的布局,和一个特定的结果在不同的操作条件下不一定是可重复的。
• 这个颜色的变化结果会导致post-coloring刚果民主共和国的变化结果,和不同的结果同样被认为是正确的。
• 找到一个一致的颜色需要运行平,这是不实际的。
• 找到一个特定的颜色(例如,最小化post-coloring错误数)需要算法和指数运行时,也是不实际的。
• 颜色应该被更像不具有或虚填满,而不是刚果民主共和国。
• 等级保护和密度平衡直接冲突,因此你不一定都在任何给定的情况下。

理解这些DP过程,其局限性和权衡,应该帮助你重置你的期望更好地匹配经验,希望减轻一些困惑沮丧你已经处理。

但是等等!TP和QP吗?好吧,我只是说你已经看出了一些端倪。下次我们会看到其他期望得到什么在TP和QP吹走。把你的防弹衣…和一个开放的头脑。