大规模集成电路Very Large Scale Integration（VLSI）

用半导体工艺技术将电子电路的电子元器件（电阻、电容、电感、晶体管、二极管、传感器等）在一块半导体材料（硅、砷化镓）芯片上，互连成有独立功能的电路和系统。亦称为“芯片”（Chip）。

集成电路产业包括设计、芯片制造、封装检测三大部分。可形象地比喻为写书、印刷、装订。显然，设计最具原创性。“863”、“973”，及国家重大专项都把集成电路设计列入其中。

集成电路设计所依赖的关键软件EDA (Electronic Design Automation), 基本上全是进口。 (EDA软件的研制涉及大量的图论和组合优化问题.)

芯片版图设计三个主要部分：电路划分、布图、布线涉及大量图论问题

电路划分是大规模集成电路设计的关键一步，其结果会影响后续的布局、布线等过程。由于需要布局的电路太大，需要将整个电路划分成若干模块，要考虑模块的大小、模块间的连线等。

它是一个多约束、多目标的优化问题。它的理论抽象是图论中的点集划分（Vertex Partition）问题:

给定一个图G 及边集E(G)上的一个权函数w. 对正整数 k ≤ t，求点集V(G)的一个划分(A₁, A₂, ..., A_m) 使得 k ≤ |A_i|≤ t，1≤ i≤ m，且∑_i<j w(A_i, A_j) 尽可能小。

在完成电路划分之后，通过布局规划（floorplanning）把模块安置在芯片的适当位置上，并满足一定的要求，如面积最小、模块间的连线最短且容易布通等。由于模块间连线要占用芯片面积，布局时要为后一步的布线留下必要的布线通道。

模块间的互连，且满足一定的要求，如减小连线总长度，减轻走线拥挤度，减少层间通孔数等。布线分为总体布线和详细布线。

最小斯坦纳树(Minimum Steiner Tree)问题：

给定一个赋权图G 及点集 V(G)的一个子集S，求G 中一个连结S 的所有点的最小权树。

S 中的点对应模块，通过添加斯坦纳点构造斯坦纳树，减小连线总长度。

总体布线中的数学问题

详细布线中的数学问题

在完成总体布线后，进行详细布线。可转化为在图中找一组路连接指定点集且满足若干条件，如要求每条边不能被太多路共同使用。图的边对应于布线通道，也即要求该通道不能太拥挤。

详细布线的一个主要问题就是用图的某些参数给出通道宽度（线槽数）的估计。

研究大规模集成电路设计中的电路划分、布图、布线等问题。以图论、组合优化、算法设计为主，为研制具有自主知识产权的大规模集成电路设计应用软件提供理论支持，提高我国在 EDA（Electronic Design Automation）工具研制这一领域的基础理论研究水平。

德国波恩(Bonn)大学离散数学研究所Research Institute for Discrete Mathematics

n 自主开发了一套EDA工具—BonnTools（最小特征尺寸为90nm）

n 1987年开始与IBM合作，已有上千款IBM

芯片的设计用了BonnTools

n 2005年开始与Magma合作，现今

BonnTools已成为Magma产品的一部分