作为电子信息产业发展的核心和基础,集成电路技术正迅速向着更高集成度,超小型化,高性能、高可靠性的方向发展。随着系统芯片(SOC)设计方法和知识产权(IP)模块技术在集成电路设计中的不断发展和应用,布图规划和布局日渐成为超大规模集成(VLSI)电路与系统物理设计的关键环节。布图规划和布局的主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置,使得芯片的面积以及模块之间的互连线总长最小。由于布图规划和布局是芯片物理设计的第一个重要步骤,其结果将影响芯片的最终性能。在VLSI设计流程中,物理设计是既关键又复杂的一步,而布局又是物理设计中最重要的一步,布局的诸多问题都是NP完全问题,需要启发式算法来求解。随着VLSI集成度的迅猛提高,寻求有效的优化算法应用于布局问题,以提高布局质量和速度已成为当务之急;同时如何高效地表示布局结构,从而提高布局质量成为物理设计中的一个国际研究热点。本文正是在这样的背景下,对VLSI物理设计中的关键环节——布局,展开了一些研究工作。本文概括地介绍了布局结构表示研究的进展。针对不可二划分的BBL布局问题,近年来国内外涌现出如:CBL、BSG、SP、O-tree等优秀的布局结构表示方法,但它们在解空间的大小、编码的费用、编码与布局之间的转换时间等方面各有差异。本文提出了一种求解VLSI布局问题的启发式算法。该算法通过设计模块的优先顺序进行合理的布局,再辅助于边界矩形来减少边界浪费,对于模块布局放置的多个可能位置进行比较,并将其放置在优先度最高的适当区域。同时本文阐述了一种布局表示方法,在这种表示方法中尽量先用更受限制的资源,而尽量后用“一般”的资源,一般有更多机会满足匹配来解决问题。