EEPW论坛

一、早期阶段（1964-1978年）

EDA的基础在这一时期奠定。一些开创性论文至今仍有深刻影响的。这个时期的基础性的成果可以集中到六个方面：电路仿真、逻辑仿真与测试、MOS时序仿真、PCB版图系统（PCB layoutsystems）、布线（wire routing），以及规则阵列（regular arrays）。  

（1）电路仿真

电路仿真是EDA中的一个非常重要的课题，尤其是在IC设计方面。历史上，电路仿真在IC设计这一重要领域中的成功，是EDA这一产业诞生的决定性因素。那些年间，IBM的科研人员是该领域的重要力量：Frank Branin是电路仿真的先驱，他确定了电路仿真的架构。Brayton、Hachtel以及其他在约克镇（Yorktown）的IBM T. J. Watson研究中心的同事们，也对这一领域做出了基础性、革命性的贡献；是他们提出了电路仿真背后的所有算法——从我们今天所知的稀疏矩阵（sparse matrices）到向后微分公式（backward differentiation formulae）等。

他们也推动了两个重要的项目——IBM的ASTAP和Berkeley的SPICE的发展。其中，在SPICE项目早期，Ron Rohrer和Don Pederson做了极其重要的工作，使得SPICE在多年来一直是电路仿真领域的主力军。

（2）逻辑仿真与测试

在设计自动化会议DAC开始之前，人们就已经在使用逻辑仿真了。诸如IBM和CDC等计算机公司们依靠这项技术，来对它们的逻辑设计进行调试。对这一领域做出贡献者数不胜数。

该领域的创立者们在自动测试生成（automatic test pattern generation）与故障仿真（fault simulation）的发展中也扮演了基础性的角色。如Michigan的Hayes和Ulrich、USC的Breuer、UT Austin的Szygenda等等，他们都发挥了难以估量的作用。由Tom Williams及其同事发明的LSSD方法，以及随后由IBM的Paul Roth开发的D-算法，改变了计算机硬件的设计方式和测试模式（test pattern）的生成方式。

（3）MOS时序仿真

利用MOS晶体管的准单向（quasi-unidirectional）特性来加速电路仿真这一想法，首次出现在1975年Bell实验室的Hermann Gummel及其同事的工作中。Gummel的直觉是用基于松弛法（relaxation-based）的快速启发式算法来近似求解电路微分方程。他洞察到，当分析数字电路的时序时，只要开关事件能被正确地放在时间序列中，那么有没有精确的波形都是无关紧要的。现今的快速电路仿真仍然是基于这一思想。

（4）布线

今天我们在用的工具中用到的大部分技术都是源于这一时期取得的成果。Lee maze布线器（router）于1961年出现——比首届设计自动化会议（DAC）还早，它并不知名，却仍是今天我们使用的大部分布线器的基础。Hightower line extension算法可以追溯到1969年，而通道布线（channel routing）的想法出现于1971年Hashimoto和Stevens的工作中。

（5）规则阵列

随着大规模集成电路的出现，那些能减少设计时间的规则版图样式的吸引力无疑是巨大的。于是，人们开发出了门阵列（Gate-array，IBM称为主片（master slices））和标准单元（standard cell，IBM称为主映像（master images）），来替代原本的定制版图。

在这一时期的IBM和Bell实验室中，采用这种设计方式的自动电路版图集成工具被广泛使用。当年，最早的一个门阵列集成电路只有四个逻辑门，当时一位来自Schlumberger的研究人员讨论了用自动化工具来优化电路。现在回头看看人们已经走过的路程：在40年里，从最初的四个逻辑门，到如今一块芯片上数以十亿计的逻辑门电路，进步是巨大的。

CAD被认为对于电子系统行业，尤其是其中的计算机行业，具有战略性的价值。IBM以及其他涉及计算机设计的大公司都非常重视它，并在这方面投入了大量资金和资源。这些公司内部的CAD部门的工程能力都非常强大。再来看看DAC会议论文集，可以注意到，日本的计算机和通信系统行业发表了很多论文，这些论文描述了一些用工具进行系统设计的统一方法。由此可见CAD技术在世界范围内的战略价值。

这一时期，第一代CAD公司成立了。Applicon成立于1969年，Calma成立于1970年，Computer Vision成立于1972年。他们都支持几乎相同的设计工作：在定制工作站上进行艺术作品编辑。它们商业模式的中心是工作站的销售；而软件则只被认为是硬件的附属物。这些初代CAD公司没有一家存活到了今天。对于它们的衰亡，我们可以找到这么一些原因：

它们产品的体系结构：定制化的硬件，附带着复杂的、大部分是用汇编代码写的软件。这导致它们很难跟上技术进步，因为这样的工作站在软件的可移植性上存在严重的问题，设计新的工作站需要大量的投资，然而它们的销售量又十分有限，难以支撑这样的投资。

能让人感知到的产品附加值小，导致消费者的忠诚度有限。

对市场变化和消费者需求的了解有限。

这些因素导致了它们完全缺乏创新能力，导致了它们最终的消亡。

二、黄金时代（1979-1993年）

在1979到1993年间，EDA领域的各个方面都出现了爆发式的增长。从物理验证到版图综合（layout synthesis），从逻辑综合到形式验证，从系统级设计到硬件加速，EDA的各个层面都出现了大量重要成果。技术领域（technical community）一直扩展到了非线性和组合优化、控制、人工智能、逻辑等领域。那些最成功的EDA公司也在这些年里成立了。那些最杰出的研究小组招募了大量EDA的博士；还有大量的学生想要进入这一领域。

（1）验证与测试

这一领域中有两条研究主线：其中一条聚焦于让电路仿真速度更快——比SPICE快好几个数量级，另一条则聚焦于形式化技术（formal techniques），以证明电路会以正确的功能工作。在前一个领域，Lelarasmee Newton、Ruehli以及Sangiovanni–Vincentelli本人研究了基于松弛法（relaxation-based）的技术和混合模式仿真，并在1980年左右得出成果，为现在的快速MOS仿真器奠定了基础。在这段时期之后，Jacob White完全地描述了波形松弛算法（waveform-relaxation algorithm），还研究了加速技术，使这一方法成了被研究得最多的方法之一——甚至是在数值分析界也是如此。

数字电路仿真的精度落在电路仿真和逻辑仿真能够达到的精度之间，但是它比SPICE快两个数量级以上——于是有了1980年Randy Bryant在MOSSIM上的成果。随着几何尺度的缩小，互连线（interconnects）的效应开始显现了出来。由Penfield和Rubinstein在1981年提出的互连线延迟模型（interconnect delay model）被人们广泛使用。CMU的Pileggi和Rohrer用他们在渐进波形估计（AWE，asymptotic waveform evaluation）方面取得的成果，于1988年解决了互连线仿真的问题。形式化技术（Formal techniques）最初的目标是回答这么一个问题：两个不同的门电路网络是否有相同的布尔（Boolean）函数。

在发展早期，还是在IBM，Bahnsen首次使用了形式验证。1986年，Randy Bryant在二元决策图（Binary Decision Diagrams）方面所做的开创性工作彻底改变了这一领域，他引进了布尔函数的标准型（canonical form）和非常快速的运行算法。Coudert和Madre用BDD在有限状态机等价方面做出的成果，以及90年代Ed Clarke、Joseph Sifakis、Ken McMillan、Dave Dill和Bob Kurshan在模型检测方面的工作，都将形式验证推上了更高的抽象水平。

他们解决了验证一个用有限状态机(FSM)表示的时序系统是否满足一定性质的问题——这里的性质由定义在状态和转换上的逻辑命题描述。在测试领域，1981年，在IBM的Prabhu Goel的指导下，著名的基于D-算法的PODEM-X项目也见到了曙光。

(2)版图

在表示与基本操作层面，类似艺术作品编辑出现了根本性的改变。在以前，设计人员对每一个设计步骤都使用不同的数据存储库，这就带来了大量繁琐的数据格式转换工作。80年代早期，由于Berkeley的Newton在Squid、Oct、VEM上的研究工作，以及Ousterhout在Magic systems上的工作，这一时期这一领域发生了革命性的变化，他们的工作成果表明，人们可以拥有一个统一的数据库和图形用户界面。这些研究工作的重要性再怎么强调也不过分。SI2开放数据计划（SI2 Open Access initiative）就是基于Newton的研究成果；一些先进的物理设计的数据表示则基于由Ousterhout提出的角勾链（cornerstitching）数据结构。

另一个革命性的想法出现在关于硅编译（silicon compilation）和版图语言（layout languages）的研究中，这些工作大约也在相同的时期开展，分别在MIT（John Battali）、CalTech（Carver Mead团队和他们的Bristle Block硅编译器）以及Bell实验室（Hermann Gummel及其同事、Misha Buric及同事以及他们的L版图语言）。当时的想法是要将计算机科学中的一些思想注入到IC设计中。不过，虽然这种方法在理论上很优美、很强大，但是当今我们所使用的工具中几乎已经不再使用它了。Kirkpatrick和Gelatt是两位物理学家，他们把自旋系统（spin systems）的知识用到了这一领域中。

1980年，他们在IBM提出了模拟退火法（simulated annealing），以此来解决门阵列版图的问题。这一方法一经公开，立刻就涌现出了大量关于该算法的高效实现和理论性质的研究。经过定制的算法被用在了标准单元、宏单元版图以及全局布线上。大部分大公司——从Intel到DEC、从Motorola到TI，都使用了由Sechen写的TimberWolf系统，用于标准单元版图以及宏单元版图。在那些年里，Fabio Romeo、Debasis Mitra、Sangiovanni–Vincentelli，以及最重要的Greg Sorkin与其开创性的论文，提升了人们对于模拟退火算法的数学性质的理解，超越了对自旋系统的类比，也奠定了统计优化技术（statistical optimization techniques）的基础。

这些年里，我们还注意到，一些理论计算机科学家对于版图设计中的组合方面抱有很大的兴趣。比如，MIT的Rivest和Pinter在布线方面的成果，以及Berkeley的Karp及其学生在版图和布线方面的工作，都是很好的例子；能够吸引来自其他学术领域的研究贡献，可见EDA领域的成功。另外，Berkeley的葛守仁（Kuh）的研究产生了用于宏单元设计的集成版图系统，以及用于布局和布线的点工具（point tools），也对整个领域有着重要的影响。

（3）逻辑综合

逻辑综合（Logic synthesis）一词于1979年出现在EDA的词汇中，它来自于Darringer、Joyner和Trevillyan的一篇重要论文。在这篇论文中，他们使用了基于peephole rule的优化方法，来产生门电路级的高效设计表示。就在这一成果出现之后不久，IBM也在一定程度上独立地研究出了另一种Boolean优化方法，它由Brayton和Hachtel与Berkeley的Newton和Sangiovanni–Vincentelli合作完成，由此产生了二级逻辑优化器（two-level logic optimizer）ESPRESSO，以及多级逻辑优化器Yorktown Silicon Compiler和MIS系统。

这项工作由DARPA（美国国防部高级研究计划局）支持，历时逾十年时间。在MIS的发展早期，首先是一个工艺无关（technologyindependent）阶段，在这一阶段中Boolean函数被不断调整和优化，随后紧接着的是工艺映射（technology-mapping）阶段，在这一步中人们把经过优化的Boolean函数映射到门电路库；包括Intel、ST、TI、Motorola、Honeywell、DEC和Philips等在内的所有大公司都采用了这样的步骤。关于其中的第二阶段，通常采用的方法是使用基于规则的（rule-based）技术，比如GE的Aart  De Geus及其同事开发的SOCRATES系统就是如此。

1982年，当时Sangiovanni–Vincentelli在Princeton的一场讨论中遇见Kurt Keutzer时，后者向Sangiovanni–Vincentelli展示了Aho和Ullman在编译方面的研究成果的应用——非常高效的工艺映射（technology mapping）。其中采用的想法是，把原问题表示为一个树覆盖（tree-covering）问题，然后用动态规划法来解决它；这是一个非常伟大的想法，目前的绝大多数逻辑综合系统都是基于这一想法。在IBM的Darringer的原始工作的基础上，日本的Fujitsu、NTT以及NEC等公司进行了卓有成效的研究工作，产生了可实际工作的逻辑综合系统。

逻辑综合对于EDA设计领域来说是一个伟大的成就，它产生了大量的论文，吸引了来自其他相关领域的兴趣。在Keutzer、Devadas、Malik、McGeer、Saldanha与Brayton、Newton以及Sangiovanni–Vincentelli协作进行的研究工作中，他们使用逻辑综合技术展示了大量关于冗余去除（redundancy removal）和延迟测试（delay testing）的结果。V. Agrawal、Tim Cheng以及其他人又提出了一些新的测试算法，体现了逻辑综合与测试两个领域之间的交叉。

在逻辑综合的成熟期，Coudert和Madre通过使用BDD，非常可观地加速了基于Boolean函数CNF表示的逻辑综合算法。

（4）硬件描述语言

那些当时已经被归为逻辑综合的技术工作，其实归类到逻辑优化更加合适，这是因为，其中的算法所做的事情，就是把一个数字电路的Boolean表示变换为另一个最优化的等价表示。综合代表着两层抽象之间的桥梁。为了比Boolean函数更高效、更简洁地表述硬件，硬件描述语言就应运而生了。这么一来，综合要做的实际工作就是将HDL（Hardware Description Language）描述映射到门电路网络列表（netlist）。

不幸的是，最初HDL的发展是独立于逻辑优化的工作而进行的。这就意味着，不是所有的HDL（比如由Moorby和其同事提出的Verilog）和VHDL的结构都可以用逻辑综合算法来处理。于是，当时的研究者就不得不把这些语言的使用限定在所谓的“可综合子集”（synthesizable subset）中。尽管HDL确实是一个巨大的进步，它通过在设计周期的早期引入验证，缩短了设计时间，但是，这种需要“取子集”的特点说明，这些语言在语义方面还是存在一些问题。

HDL之战，是那些年中非常有意思的一件事情：Verilog是一种专有的语言（Gateway Design销售Verilog仿真器并授权该语言的使用），而VHDL属于VHSIC计划，由DARPA支持，从诞生以来就是一种开放的标准。关于这两种语言谁更有优越性，当时曾经在DAC上进行过无数次辩论。而当Verilog也变为公开之后，在这两者之间就只有一些表面上的差异了，当然了，你仍可以看到一些人强烈支持其中一个而反对另一个——这只是各人的口味不同罢了。Joe Costello在1991年设计自动化会议（Design Automation Conference）的主题演讲中非常雄辩地指出，对于单一的任务采用两种标准一般而言是一个坏的想法：

“……VHDL的采用是设计自动化历史上最大的错误之一，它致使用户和EDA供应商浪费了大量的金钱……”

转帖自网络