自1990年代以来，令我惊讶的是，整个数字微电子学的设计都由位于加利福尼亚的两个办事处控制，而这两个办事处相距10分钟车程，这就是Synopsys和Cadence。 当时，世界设计的四分之一是在日本完成的（当时中国大陆还处于原始状态），索尼，日立，富士通和其他巨头都向美国屈服，并为日本设计师当时使用的程序付出了无数的数百万美元。 现在，它继续与三星，华为以及甚至为太空设计微芯片的俄罗斯办事处合作。
俄罗斯的土地成功地使Yandex与Google相比增长了，那么为什么不尝试创建一些设计微芯片的程序呢？ 您可以从小处着手：普及竞赛和黑客马拉松，以开发设计自动化算法（电子设计自动化-EDA）。 这些算法很方便，因为它们具有许多难度级别：学生可以在周末编写最简单的“放置与路线”程序，但是高级程序将需要数十年的工作，需要数百人和数十亿美元的研发资金。
现在在喀山附近的Innopolis，他们正在
以“两周培训+黑客马拉松”的形式为学生做
活动 。 主题之一是传统的EDA任务-将电子电路图放置并追踪到标准单元行中。 看到一个对C ++ / Java / Python有基本了解的小型程序员团队，解析文本的方法，图形算法以及使用GUI可视化数据结构的技能，这将很有趣。
所以-问题的陈述：
该任务包括三个子任务，不同的学生可以处理：
- 解析数字电路图的文本表示。
- 将图形放置在微电路标准单元的行上，并将这些单元与轨迹连接（跟踪）。
- 结果可视化-在电路轨迹和连接的屏幕上显示。
程序的输入是Verilog硬件描述语言的非常有限的子集中的文本文件。 该文件描述了电路的输入和输出（输入，输出），内部连接（电线），并以“类型实例名称（连接列表）”的格式提供了逻辑元素的列表。 可以使用Lex + Yacc或类似程序在C / C ++中解析该文件。
解析文本的结果应该是内存中元素的图形表示。 放置和跟踪算法将使用此视图，然后由另一个结构创建该视图。 如果hackathon团队中有足够的参与者，则可以在hackathon期间将初始解析的结果可视化为一项附加任务。 即使不是很漂亮，大约也可以按照这种精神：
如果在黑客马拉松期间没有足够的参与者，则应保留中间的未放置图形的可视化以供以后使用，并且在黑客马拉松期间，应仅将最终放置位置显示在屏幕上。
通常，解析任务可能会具有多个复杂程度：
- 在最简单的情况下，图的所有节点都是两输入逻辑元素AND和OR以及单输入NOT元素。 在最后放置时，它们是由相同宽度的标准单元实现的。
- 如果有足够的时间进行黑客马拉松，则任务可能会很复杂：
- 引入三输入和四输入单元AND3，OR4等；
- 通过添加具有不同选项（复位，启用）等的NAND，XOR，D触发器（D-Flip-Flop）来扩展节点类型集；
- 制作一个附加的文本文件，在其中设置单元格的宽度和其他参数。
- 在黑客马拉松之后，可以将任务绑定到现实世界，并且不是解析的抽象AND和OR解析，而是文件的格式相同，而是具有28、14或7纳米标准ASIC单元的真实库中的单元，这些单元将提供给EDA开发人员和工厂设计师台积电（台湾半导体制造公司）。
什么是标准单元格？ 这是给定ASIC库的标准高度单元，也就是用于使用某种技术在工厂制造微电路的原始库。 ASIC-专用集成电路。 现在，例如智能手机中的大多数芯片都是ASIC。 ASIC库中的单元具有标准高度，因此可以方便地将它们排列成行以向其供电并有助于跟踪算法。 库中的不同单元不仅可以实现诸如AND和OR之类的原语，还可以实现更为复杂的结构-多路复用器，锁存器，两个或三个逻辑元素的组合（AND-OR）等。
微电路上的电池排成一排（
查尔斯·丹切克的
演讲幻灯片）：
在行之间有连接通过的通道（路由通道）。 如果在连接中形成拥塞，则可以更改通道的宽度。 在行中，您可以在单元格之间留出空隙：
对于黑客马拉松，可以在真空中将任务简化为球形马的水平：
- 限制单元格类型。 对于初学者来说，通常只能放置一个两输入NAND图。
- 考虑所有单元具有相同的宽度。
- 忽略单元物理性质的所有方面，包括信号延迟和功耗。
在这里，“无视”意味着在训练中，您在评估放置和追踪的质量时不会考虑细胞物理学。 首先，仅考虑几何形状就足够了，例如，以最小化接头的总长度和在其上制作接头的层数。 当不可能放置两个导体而不交叉它们时，就需要新的层。
在黑客马拉松比赛中，将标准单元视为“黑匣子”并将其显示在屏幕上就足够了，如上图所示。 或带有逻辑元素的图像，例如
Igor Markov的演讲幻灯片中的幻灯片：
尽管如果在单元格的内部进行显示，则图片更具装饰性。
查尔斯·丹切克（Charles Danchek）的
演讲幻灯片：
来自Internet的另一张图片，其中包含单元内部的放置和跟踪+图片：
但是，如何在行中放置单元格，在行之间扩展和缩小通道，建立连接，引入新层，评估结果的最佳性以及对选项进行排序？ 好吧，这些纯粹是算法和编程任务，在Innopolis中，他们可能会教这些，因此，我不会在树上散布我的想法。 作为跟踪的初步灵感，您可以使用古老的波形跟踪方法，这是
针对RUSNANO中小学生的课程的第三部分 。 尽管此方法不适用于按行排列的标准单元，但适用于组件数量较少的情况（例如，数量较少的情况）：
2.10。 怎么做：波形追踪算法。
使用早期跟踪程序的经典算法之一是波形跟踪，它在1961年由贝尔实验室的研究员Chester Lee进行了描述。 在英语中，Lee算法称为“迷宫路由”，其字面翻译为“迷宫追踪”。 该名称的原因是，除了用于设计电子设备的程序以外，Lee算法还用于游戏程序中以找到迷宫中最短的路径。
Lee算法以有限平面中的图形形式表示需要连接的块，标记为“在框内”。 为了找到从一个块的输出到另一个块的输出的最短路径，Lee算法使用了两次遍历：
- 第一遍称为波传播。 我们用一个单位标记所有“单元格”或第一个输出的单元格。 之后，对于每个标记为N的单元格，我们将所有相邻的未标记自由单元格标记为N +1。重复标记，直到我们到达第二个块的结论或不再有传播“波动”的机会为止。
- 第二遍称为“路径还原”。 如果第二块的单元格被标记，我们将在其邻居中选择一个标记为比当前单元格小1的单元格。 在路径中添加一个相邻单元格，进入该路径并开始查看它的邻居，将其标记为少1个。 我们重复这一过程，直到得出第一个方框的结论。
最初，Lee算法被用于设计印刷电路板的程序中，然后他们开始将其用于设计微电路。 但是，当微电路的尺寸增加时，不可能以其原始形式应用Lee算法，因为它需要大量的内存来存储数据阵列，并且需要大量的时间才能通过该阵列。 尽管事实上现代自动跟踪程序使用其他算法，但是Lee算法对于那些最近精通编程并想自己编写一个小的跟踪程序的人来说仍然是一个极好的练习。
对于更严肃的算法，您可以
在Igor Markov的材料中搜索思想。 但是最好的办法是发挥创造力-如果每天早上想出数以千计的数学算法程序员都没有想出Synopsys和Cadence办公室第101、880和237号高速公路上的交通拥堵的情况该怎么办？在加利福尼亚州桑尼维尔，森尼韦尔和山景城。
参考（从简单到复杂）：
- 关于Innopolis数字设计基础的入门讲座： 1、2 。
- 面向奥林匹克高级型学龄儿童的数字电子和EDA入门课程。 来自RUSNANO： 1、2、3 。
- 教科书哈里斯＆哈里斯 。
- 查尔斯•丹切克（Charles Danchek）的演讲幻灯片 。
- 密歇根大学的Igor Markov课程 。 他在莫斯科国立大学读了这门课。
我希望
Innopolis在算法竞赛中的
主动性能够扩大。 EDA领域在数学上很有趣，而且报酬很高。 Synopsys在亚美尼亚开设了一家分支机构，并成为该地区的主要雇主之一：
“如今，Synopsys是亚美尼亚最大的IT雇主之一，拥有650多名员工（包括600多名工程师）。” 我注意到俄罗斯比亚美尼亚大，并且可以创建自己的Synopsys。 最后，俄罗斯还有许多程序员，还有数学家，Synopsys + Cadence的当前市值大约等于索契奥运会的成本。