随着集成电路更小型化、更高带宽和更低功耗的要求加速,三维集成电路作为传统的晶体管尺寸下降的补充,能够使得设计者将多层芯片垂直堆叠,或者在硅中阶层上进行并列的“2.5D”配置,达到更高的集成度。三维集成电路通过硅通孔技术和传统的倒装芯片封装有可能超越摩尔定律的发展。硅通孔会穿透硅片,提供垂直方向的电气连接,一般采用铜进行填充。与引线键合的系统级封装相比,硅通孔能够大量减少电阻、电感和电容的寄生参数,提供更高的性能,节省更多的功耗和进行更高密度的集成。与基于硅中介层的集成方法相比,垂直三维芯片堆叠能够提供更高的集成度,更小的形状系数和更快的设计周期。这样的技术出现是非常吸引人的,但是仍处于起步阶段。目前,集成电路供应链生态系统对此仍然比较模糊,还没有统一的标准。设计、验证和测试仍存在着诸多需要解决的挑战。从电子设计自动化的角度来讲,好消息是不需要完全重新开发三维集成电路的工具。但是以硅通孔为主导的新的设计能力仍然是需要的,比如结构化分析、平面布图、布局布线、热分析、时序、信号完整性、寄生参数提取、芯片／封装协同设计和测试等等。其中有一些目前已经存在,其他的则在发展当中。在本论文中,我们对集成电路物理设计步骤中的三维集成电路硅通孔匹配和倒装芯片布线问题进行了研究。针对三维集成电路硅通孔匹配问题,我们提出了一个实际的三维线网的硅通孔匹配模型和一种集成化的匹配算法。首先证明了在一般情况下,大于两层芯片的预先布局的三维集成电路硅通孔匹配问题是NP完全问题。随后,我们提出并详细描述了一种集成化的匹配算法,包含了最短路径搜索、二分匹配、最小费用最大流的计算和后处理。算法第一步是寻找每条三维线网匹配的最短路径,从而得到总的匹配结果的一个下边界。这个初始的解很有可能是非法的,因为多条线网会占用同一个硅通孔或者微凸块。接着应用二分匹配和最小费用最大流的计算,将共用硅通孔的线网加以分离,来获得一个合理的匹配解。最后,可以选择性地进行后处理步骤来进一步优化硅通孔的匹配结果。我们也对所提出的算法进行了扩展,以处理多端口线网的匹配问题。同时在最短路径搜索和最小费用最大流的计算当中也引入了一些启发式的加速策略。以实际的工业数据进行测试,表明了我们的算法流程与已有算法相比能够在合理的时间内得到高质量的匹配结果。针对倒装芯片布线问题,我们给出了倒装芯片输入／输出线网全局布线和轨迹匹配的一个求解框架。我们采用维诺图理论去构建全局布线通道图。布线通道图的布线容量可以通过布线方向和通道宽度来计算。随后,根据全局布线通道图构建了一个流网络,应用最小费用最大流的计算来获得全局布线的最优解。全局布线之后,我们提出了一种轨迹匹配算法来细化全局布线拓扑路径,同时避免布线的交叉。在所提算法的基础上,一些直接的改进也被提出来并加以讨论。以实际的工业设计用例为基础,实验表明了与一款EDA商业软件中的实现相比,我们的算法和实现能够在布通率和总线长上都有所提升。