的麻烦Triples-Part 1

如果你是一个真正的极客像我一样,你可能还记得《星际迷航》“毛球族的麻烦”可爱的毛茸茸的小外星人的咕噜声,当你的宠物。他们看起来很好和友好的表面上,但最后,他们成为了贪婪的怪兽的指数增长的质量,几乎坏了船和消费粮食仓库,旨在为行星提供人道主义救援。

三重模式(TP),不幸的是,有点像毛球族。目前的从事20 nm或16/14nm设计有一些经验与双模式(DP)可能会认为自己,“我们知道如何使用两个面具,可以三个口罩有多难?“立根,从外面看起来无害的,但潜在的混乱是内。这个问题在本文中我将重点放在与试图建立一个EDA软件的复杂性算法的分解(着色),检查自动化使用TP一层。
要理解这个TP问题,首先让我们来看另一个快速DP分解和检查。我们已经讨论过很多次在我过去的文章,但是这一次,让我们来看看这个问题从EDA软件算法的角度试图决定如何颜色布局。

任何软件解决方案首先需要的是一种翻译的规则的多边形布局和颜色变成一种算法可以处理。图1演示了这一需求的典型方法。

图1:样本DP布局和设计规则的翻译成一个算法图。

第一张图片显示了一个多边形的布局层必须分解成两种颜色。第二幅图显示了运行的结果对这组多边形间距检查。基于DP间距检查配置设计规则定义多边形必须分开多远是允许在同一个面具(最低面具间距相同)。无论这个间隔是违反,你看到蓝色的标记。违反这两个多边形创建这些间距必须分配“DP法律相反的颜色。“第三张照片显示这个非常特殊的身体构造是如何抽象成一个虚拟表示形式(称为“图”),可以处理在一个算法。的多边形布局图中表示为“节点”。间隔约束布局图中表示为“边缘”。这些节点和边不捕捉任何空间信息(坐标、大小、距离等)。他们只代表是如何“连接”到对方的要求备选颜色。

现在我们有一个布局的计算机表示和规则,让我们走过的过程中试图将这个图分解成两种颜色。图2给出一个示例的这个过程。

图2:自动DP分解算法的例子。

让我们从第一个节点开始在左边的图。不管哪个节点开始;结果将在本质上是相同的。同样,选择哪一种颜色/掩码分配初始节点是完全任意的。只有两个选择。在这个例子中,我们选择了蓝色。自从第一个节点是蓝色的,和有一个边缘连接到第二个节点,然后第二个节点必须是绿色的。边告诉我们,它必须是一个不同的颜色比第一个节点,和唯一的其他选择DP的颜色是绿色的。这个过程继续通过其他节点,直到最后的最后全着色结果正确的图片。你可以看到最后两个形状被迫是蓝色,但他们也有优势联系他们,要求他们是不同的颜色。 This conflict results in an error. Our example algorithm would report that this layout is not legally colorable by highlighting the violated edge (edge connecting two nodes of the same color) in the graph.

不同的首选会改变结果吗?如果你做了第一个节点绿色,那么最右边两个节点也会是绿色的,你会有同样的问题。如果你试图改变节点绿色解决冲突,只需移动节点和之间的冲突的一个直接下来了。没有水平的“回溯”或“上色”找到一个合法的着色。唯一的区别,改变颜色在一个特定的节点的选择是违反边缘发生的地方。关键是没有染色的解决方案存在,你可以知道这肯定使用单一通过查看图形。

此布局包含一个“奇怪的循环”,通过定义在DP不是似是而非的。如果一个分离边缘有最后两个节点之间不存在,然后布局是合法的似是而非的,这个“算法”会发现一个合法的解决方案。如果我们推断从这个简单的例子,你可以想象,这种方法的运行时间随着节点数的增加,增加的顺序

DP x的值是1,所以解决DP的问题所需要的计算工作量增加线性涉及的元素数量。这是好消息,如果你想建立一个DP的EDA解决方案,如果你是一个设计师想要运行的解决方案,希望它将完成在合理的时间内可靠的结果。
现在让我们回到TP,看着它以同样的方式。我们来看另一个简单的布局和穿过一个概念性的“算法”试图找到一个着色的解决方案。图3显示了示例虚拟映射的物理布局和TP的规则。

图3:样本翻译TP的布局和设计规则算法图。

到目前为止事情本质上相同的DP的例子。多边形表示为节点图,和间隔约束,要求某些多边形图中不同的颜色表示为边缘。与DP一样,你选择一个节点和一个颜色的选择,这两种本质上是任意的。TP最大的区别在于,当你移动到下一个节点图中通过跟踪每条边,你现在有两个颜色选项可供选择为特定节点,而不是只有两个。具体选择下一个节点的颜色也有些武断。图4展示了不同。

图4:自动TP分解算法的例子。

在这个例子中,我们选择的节点,右侧的第一个绿色和节点,向右是粉红色的。这将是同样有效的扭转,任务。你不能让他们两个绿色或粉红色,然而,因为他们之间有优势。在这种情况下,有三种颜色是有利与DP相比,在第一个“奇数周期”在TP有效的着色方案,它不会在迪拜。到目前为止还好。

我们继续进行下一组节点图。从上面的绿色节点向右移动,下一个节点可以是粉红色或蓝色。我们没有任何理由去选择一个,所以我们选择粉红色。从前面的粉红色低节点移动,我们可以选择下一个节点的蓝色或绿色。再一次,我们没有任何理由去喜欢一个,所以我们选择蓝色。
现在,我们只是从粉色和蓝色节点颜色的两个左,我们遇到一个问题。因为蓝色节点,没有剩余的两个节点可以是蓝色的,因为粉红色的节点,也可以是粉红色的。只有绿色,让我们让他们两个绿色。然而,他们有一个边缘连接,这使得这种颜色选择无效并产生一个违反边缘在第三照片(如图所示)。

这是正确的答案吗?这张图真的不似是而非的三种颜色吗?马上,你问问你自己,“如果我有什么做不同的颜色决定的前一个节点,我有不止一个选择吗?“看,这是TP与DP的主要区别。因为有两个以上的选择颜色,一路上有很多地方可以做其他选择。让我们后退几步,看看会发生什么,如果我们改变我们的选择(图5)。

图5:交替颜色的选择。

嗯,看那!如果我们回去在右边,一步,改变节点的选择最远的从粉色到右边蓝色,我们可以重新着色其余节点TP法律布局。粉色和蓝色都是完全有效的选择,考虑到之前的节点上是绿色的,但如果没有预知将会发生什么,我们没有理由选择一种颜色,和任意选择粉红色。现在已经取代了粉色和蓝色,剩下的最后两个节点可以绿色和粉红色。选择哪一个是绿色和粉色是任意的,哪一个是作品。所以事实证明这种布局是似是而非的三个颜色,我们只是第一次得到了“错误”的答案。

您可能已经注意到现在,增加更多的颜色选择意味着你可能不得不遍历许多不同颜色的“试验”,确保你做出正确的决定是否一个布局是似是而非的,找到一个有效的着色。正因为如此,一个通用的算法的运行时间对于这样一个问题的形式

注意变量“节点”已经从尾数指数的表达式。“x”的价值通常是< 3,为每个节点最多有三个颜色的选择。这个表达式的显而易见的问题是,运行时的数量呈指数增长的多边形布局增加。坚持住!“指数”是一个四个字母的单词,当你开始谈论软件和运行时。正如毛球族生育指数当你喂它们,那么通用TP算法的运行时间在设计时增加大小。

现在在你去跑步的运输车或寻找一个移相器,你还没有失去一切。虽然这个指数运行时是不可避免的事实的“一般情况”三个颜色,这个噩梦的答案在于避免“一般情况。“明智地限制“类型”或“品种”的布局结构,设计师可以画画,可以包含一定程度的形势“复杂性”的启发式可以开发一个定制的软件,可以保证一个有效的解决方案或识别的发现真正的颜色误差在合理的运行时。所有这一切都归结到伙伴关系。

幸运的是,与我们的客户合作是我们擅长在导师图形。放心,我们没有在过去的几年里隐藏在Ceti星αV,哭的事实TP天生”指数。”我们一直在狂热地与各种铸造厂(成功)的发现和达成一致的设计原则和设计方法的限制,将使TP的工作。作为一个设计师,你可以看到一些额外的约束布局你可以画10纳米技术,但我们一直在努力使这些约束尽可能最小,同时也确保一个有效的EDA的解决方案可以提供给你检查和自动分解你的布局分为三个颜色。

当你开始移动到10纳米,开始与您的代工合作伙伴讨论相关的设计准则和设计方法与使用三层模式,是开放的你可能会看到一些新的约束,和理解,他们最终是为了你的利益(理智)。没有人想要按下按钮在任何EDA工具,它永远运行”。EDA行业“我们知道,这就是为什么我们辛辛苦苦找到合理的限制,这将使一切工作。请与我们的合作伙伴和你铸造我们部署的实际答案not-so-practical跟上摩尔定律有关的问题。

我们会看一些其他的挑战与三重模式在我的下一篇博客中文章。首先,我有一个小问题称为小林丸照顾…

注。,所有计算机科学类型的观众,这个问题属于一般类“P与NP”的问题。如果你想要更多的学术、详细和准确的治疗的问题,你可能要花一些时间进一步研究这个主题。这是一个好的开始:P_versus_NP_problem。

最大功率。,在最近的一次事件的新福尔摩斯家电视剧“小学”(名为“解出X,”播出10月10月3日,2013),几个数学家被杀害,因为他们的边缘发现一个方程,将所有这些“NP”问题转化为“P”的问题,和其他数学家想偷他们的想法。从本质上讲,新数学方程式可以删除“指数”运行时问题的软件问题像TP。不用说,这样的一个方程将价值数百万或数十亿美元,但是到目前为止,没有这样的方程存在。然而,如果我们找到一个总有一天,你一定会希望你有更多的导师图形股票!