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

就像我说的,第1部分这个话题,它真是一如既往地让我吃惊有多少混乱和误解时多模式(MP)分解和检查。整个第一篇文章只集中在典型的主题我已经与客户讨论关于double-patterning (DP)。我必须告诉你,在部署triple-patterning (TP)和quadruple-patterning (QP) 10 nm节点,混淆和误解的水平已经大幅升级。这并不奇怪,我想,在实际的软件和算法的困难TP和QP vs DP不仅仅是线性更加困难,但实际上指数更加难以解决。鉴于这样的技术困难工具开发的挑战,这是不足为奇的铸造厂是更加困难的概念,设计师掌握和处理。

结束的时候第一篇文章,我提供了一个总结列表描述期望你应该把DP的类型。同样适用于TP和QP预期。但TP和QP还引入新的挑战和约束,创建额外的限制,你必须实现这些技术时做好准备。你准备好了吗?就让我们一探究竟吧…

上次,我开始通过描述如何布局,设计师将转换为虚拟图,可以处理的EDA工具来确定布局可以合法地分解,如果是这样,找到一个法律着色的解决方案。第一步为TP和QP都是相同的。在图1中,有一组简单的7个多边形绘制布局。多边形之间的间距测量执行,以确定是否有任何相邻的多边形将打破间隔约束,如果他们被放置在相同的面具。所有的多边形,违反这些间距约束(在这个例子中,所有七)然后被捕获在一个虚拟图内的EDA工具和分析来确定面具作业为每个多边形(或识别缺乏一个合法的着色方案)。每个多边形表示为图中的一个节点,每个间隔约束表示为图的边缘。

图1:翻译的布局为议员虚拟图分析。

注意,虚拟图(即不包含空间信息。大小或形状的多边形,多边形在空间的相对位置或彼此)。这个翻译从布局到虚拟图有效地处理信息来确定着色的关键。一组给定的多边形形成一个互动图表被称为连接组件。一个典型的布局可能形成数百、数千甚至数百万的连接部件,所有的相互独立的。每个连接组件单独也许是似是而非的法律,但法律着色必须找到他们所有人找一个合法的色素对整个芯片。到目前为止还好。就像迪拜。然而,一旦你尝试颜色图表,一切都变了。

图2演示了一个TP分析虚拟图,从图1。显然,有三个颜色选择TP,与DP的两个颜色的选择。这似乎是一件好事从表面上看,因为你有更多的选项,得到良好的结果。然而,数量的增加会导致瘟疫的算法问题的选项一个实际的EDA软件解决方案,让你夜不能寐。

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

在本例中,我选择一个任意起点(最左边的节点),和一个三色选项(蓝色)。有两个节点连接到原始节点。每个人必须是一个颜色而不是蓝色。没有信息在这一点上帮助下一个颜色分配,所以选择是随机的。我选择了绿色的顶级节点,粉红色为底部节点。事实证明,有一个分隔符(间距约束)连接这两个节点。幸运对我来说,我选择了两个不同的颜色为这两个节点,所以他们都尊敬颜色交替要求从第一个节点,并从对方。

从这两个节点,我继续尽管图,颜色我遇到的下一个节点(图3),在迪拜,我只能选择下一个节点相反的颜色之前的节点,但在TP,我为每个节点有两个颜色选择,颜色选择和任何信息。最后,我达到一个点,最后两个节点连接到蓝色节点左边和右边的粉红色的节点同时进行。因为分隔符,我只有这两个nodes-green一种颜色选择。但是他们之间还有一个分离器的要求,形成颜色错误。所以,这是否意味着图是不合法的似是而非的呢?

图3:任意TP颜色选择以一个颜色错误。

在DP,是的,这意味着图不似是而非的结果。在DP的每一步,只有一个选择,所以回去,其他的东西都是没有价值的。你总是得到相同的结果。一个通过节点为您提供了一个结论性的答案。然而,在TP,不止一个颜色选择每一步直到最后一个,所以我可以让不同的颜色决定。图4显示了另一种结果的结果改变一些早期的颜色决定。

图4:替代法律虚拟TP图着色的解决方案。

在TP,你不能保证找到一个正确的解决方案与一个通过图。在最坏的情况,如果只有一个解存在,你可能会尝试所有可能的组合的颜色来找到解决方案。这种算法的运行时将O (3 ^ n)与O (n)的DP算法。从本质上讲,这意味着运行时的DP图中线性增长更多的节点,而TP和QP运行时增加指数级的更多的节点。这对于软件开发人员来说无疑是个坏消息。典型的议员布局包括连接组件创建图表包含成百上千的节点,甚至更多。实际上,运行时将是无限的。这更像是不切实际的条款。没有人愿意永远使用软件工具。

然而,让我们澄清一个典型的困惑我通常遇到在这个谈话。这并不意味着每一个大型图表将一直运行下去试图找到一个合法的着色。事实上,一个非常大的图可能会发现颜色解决方案的速度比一个较小的图在任何给定的实验。什么?如何?记住,结果取决于选择。可以做出“幸运”的选择。你可能只发生在选择一组颜色在每一步,在一个通过提供一个正确的颜色。哇!你为什么不做,每次吗? Well, because you don’t have any way to know ahead of time what choices will work out. There is always an element of trial and error.

从算法上,就像这样:

•它是快速和容易产生的一组颜色。
•它是快速和容易确定的颜色是合法的。

所以,如果你的第一个试验产生的法律结果,一切发生的很快。问题发生在审判的结果是不合法的。然后您必须运行附加试验使用不同的决策。取决于有多少试验需要找到一个解决方案,运行时可能会很长…假设,当然,即使存在法律解决方案。

Whaaat吗?想象一个布局的情况没有一个合法的着色方案。你如何证明结果吗?唯一的保证证明它的方法是尝试每一个颜色组合和证明他们都是非法的。这种技术将永远需要最大的运行时。如果任何特定的图连接组件是大,运行时将几乎是无限的。即使每个连接组件是相当小,如果有成千上万的个人连接组件图,然后累计运行时间仍有可能很长时间。

是一个勤奋的设计师做什么?TP和QP是一个棘手的多模式解决方案吗?在一般情况下,是的,实际上,它是。但工作作为一个团队(EDA、铸造、设计师),有些事情我们可以做分析可行的用于高级节点的过程。

首先是减少软件技巧称为图。事实证明,在任何给定的图形组件,如果你仔细观察你会发现颜色图的某些部分是微不足道的要求如果组件的其他部分已经彩色。让我们走进一个例子。

在图5中,提取部分的布局图组件显示在左边。右边的图是另一种,简单的表示相同的组件。注意到两个节点和边缘已被移除。每个节点有两个分隔符将不同节点在更大的图。在TP应用程序中,只有三种可能的颜色。一旦确定的其他两个节点的颜色连接其中一个节点,该节点是保证法律的颜色选择。它连接的其他节点只能使用两个可能的三种颜色,所以总会有至少一个颜色了。减少图允许您删除这些节点和工作简单图,知道一旦你找到一个图的解决方案,您可以很容易地找到一个解决方案最初的图。

图5:减少二次图。

我们把这个想法进一步在图6所示。如果我们看看我们之前的图,我们现在发现一个非常有趣的一个节点的情况下在中间,几乎似乎分裂图的上半部分的下半部分。如果你重复这个节点,然后把图像分割成两个独立的图右边(如图所示),可以作为两个独立的解决这个问题,小问题。如果你能找到一个合法的着色的上半部分,下半部分和一个合法的着色,你所要做的下一个是旋转直到颜色复制节点的颜色是相同的。现在你可以重组这两个图有一个统一的法律着色的解决方案。非常酷!这叫做bi-connected组件(BCC)清晰度。

图6:BCC清晰度图像分割。

接下来,让我们继续将这些过程,看看会发生什么在图7中。我们可以应用二次减少到每个图6的两个独立的部分,然后应用BCC清晰度分裂的结果。在这一点上,剩下三个很小的图形组件,可以不再被这两个技术减少或分裂。这些图太小,即使你不得不尝试每一个颜色组合找到一个合法的解决方案,你可以在一个合理的运行时。一旦你找到一个合法的颜色对于每一个小的图,你可以“放松”通过减少和分裂的过程得到法律着色原大型图形组件。

图7:再申请二次还原和BCC清晰度图像分割。

幸运的是,有合理的算法可以减少运行时,分裂,颜色,和放松我们的结果,这意味着一个连接组件,最初可能没有被运行时现在或许是合理的解决。这可能是我们的长处使TP和QP-except您必须确保任何大型图连接组件中创建一个布局将可约成足够小的子组件。这就是团队合作。

作为EDA工具提供者,导师已增添了新的检查功能TP和QP工具保护工具从这些情况会导致极端的运行时。这类检查新的东西,设计师在DP没有处理。在DP,只有两种可能的检查结果:不干净的(通过),或似是而非的(失败)。失败,各种调试输出,像错误和警告环和锚路径生成,帮助设计师解决这些故障。

在TP和QP,还有第三个可能的结果,一个特定组件的着色合法性是不确定的。是的,你没听错:待定。我们称之为复杂性检查失败。从本质上讲,工具减少所有的图和分割技术适用于每一个组件,然后运行一个查看复杂的剩下的子组件。的复杂性是一个函数的节点数量的减少子组件。如果复杂性太高,那么有一些概率子组件可以产生不切实际的运行时。再一次,这可能不会,因为任何特定的运行结果是基于颜色的“运气”的选择,但它可能。唯一可靠的方法保证设计师不会遇到过长运行时是不允许部分布局。的工具那么突出部分布局复杂故障,要求设计师修改它,以改善其如何减少。图8显示了一个示例的一个组件不能使用两个图还原技术进一步降低。

图8:复杂性检查失败。

刚果民主共和国规则和设计方法对于这些高级节点必须限制设计师创建的布局,这样减少EDA图技术可以减少组件足够使TP / QP问题可控的算法。因为一些设计灵活性必须牺牲使这个过程工作,设计师必须期望一些相当大幅限制他们可以吸引这些节点。

你可能认为这很奇怪。然而,如果你曾经使用一个路由器,你可能与这种情况。找到一个合法途径也是一个很复杂的布局算法复杂的问题与潜在指数运行时。很容易产生尝试路线,容易检查这条路线是合法的。但这也是一种试错的问题。路由器让受过教育的猜测,如果这些失败,尝试替代方案。试验的数量可能需要找到一个合法的路由需要一个不合理的运行时。证明一个布局的唯一方法不能路由就是尝试每个可能的路由,基本上这将一直运行下去。因此,路由器做出最大的努力,如果他们没有实现一个解决方案在一个给定的时间,他们永远放弃以避免运行。我确信你们中的一些人有一个路由器不能找到一个解决方案,只有找到解决自己的右手提出路由器尝试不同的选择,使其能够找到一个解决方案在接下来的运行。 The only alternative is to constrain the layout such that the number of routing trials needed would always be constrained to a reasonable number, with a check to flag layouts that are too complex to try and route. Hmmm, that sounds familiar…The problem with routing is that the constraints would be too restrictive to make it viable, so the industry has decided to live with routers that don’t always find an answer.

这是一个可能的方法来TP和QP。可以忽略的复杂性检查工具,希望找到一个着色的解决方案。但是在采取这种方法,你必须忍受的情况下没有找到一个。我们相信可以应用合理的刚果民主共和国和设计方法的限制,使大多数设计通过检查的复杂性,因此,保证至少一个通过/失败染色的结果。即使部分布局的复杂性检查失败,我们相信,设计师可以学会修改这些部分解决复杂性问题,就像他们已经学会修改布局允许路由器查找路由解决方案。另一种颜色是你的设计,就像在路由选择是其路由。可能会有一次性的有意义的情况下,但总的来说,我认为一个精心设计的EDA工具,在一个精心制作的使用模式,手中的受过教育的设计师,永远提供最好的整体解决方案。

这是一个额外的总结对TP的期望和QP可以添加到DP从上一篇文章的列表:

•与DP算法要求检查TP的可分解性和QP潜力指数运行时间。
•显著限制之间的权衡布局或非确定自动染色结果是不可避免的。
•期待更多复杂的规则限制类型的布局结构允许使用这些先进的多模式技术层。
•需要彻底的教育在这些先进的多模式技术比以往任何时候都要高,因为它需要更多的知识比之前节点布局和错误调试技术。

我希望这有助于澄清一些更复杂的(没有双关)TP和QP分解。在我的下一篇博客中,我将回答一些典型问题设计在全彩流。特别是,权衡利弊的部分布局时颜色在你的设计流程来获得最好的效率。