随着集成电路和微电子技术的发展,集成电路设计的设计手段和设计工具也取得了很大发展,特别是计算机辅助设计(CAD)和电子设计自动化(EDA)工具。它们应用于集成电路设计的各个环节,这给设计人员带了很大的帮助,极大的提高了设计效率。但是,集成电路芯片的规模日益增大,结构越来越复杂,计算机辅助设计和电子设计自动化软件工具也显得越来越力不从心。在集成电路设计过程中,物理设计是一个重要组成部分,也是一个最耗时的设计过程。它对集成电路的生产成本、设计正确性和产品性能都有非常重大的影响。物理设计的两个最主要的过程是:布局和布线。布线作为物理设计中重要的设计过程,得到了广泛的重视。技术人员对布线已经作了非常深入的研究,提出了很多有效的布线算法,但是集成电路结构日新月异,现有的算法已经远远不能满足电子设计自动化对布线算法的需求。因此需要发展新的算法来实现电子电路布线设计。在当前的集成电路生产中,为了保护芯片,通常要用化学材料对芯片加以封装。近几年出现了一种全新的封装形式:球栅阵列封装(BGA)。这种封装具有数目庞大的输入输出管脚。鉴于球栅阵列封装(BGA)的优点,这种技术成为目前最广泛的封装形式。然而由于球栅阵列封装(BGA)结构的特殊性,对于这种封装上的布线算法不同于普通的布线算法。所以,我们需要重新考虑这种封装下的布线算法。本文主体分为三个部分:(1)包括第一章,介绍了课题研究的背景和意义,以及主要内容。(2)包括第二、三章,介绍了集成电路设计和封装的概念和知识。(3)包括第四、五、六章,详细讨论布线算法的设计和实现,并进行相关实验。本文在深入研究集成电路布图设计理论及现代优化算法理论的基础上,针对球栅阵列封装(BGA)模型,认真分析了该模型的基本结构特点,结合相关数学知识,建立起便于解决问题的数学模型,然后详细介绍了实现自动布线的方法,最后将此算法加以实现,并用接近实际应用的数据对其进行了验证。