路覆盖与超大规模集成电路设计中的布线拥挤问题

以大规模集成电路为基础的电子信息产业的发展，对我国国民经济的发展、对产业技术创新能力的提高及对现代国防建设都具有极其重要的作用。国内在该方面的研究水平与国际上先进国家相比尚有很大差距。《国家中长期科学和技术发展规划纲要》确定了16个重大专项作为我国科技发展的重中之重。其中与集成电路有关的占了两项，位列16个重大专项之首。目前世界上大规模集成电路正朝着系统集成（SOC）、高速和低功耗的方向发展。随着集成芯片上晶体管数量的增长，布图过程中的布线问题，尤其是布线拥挤问题，越显重要。加强对布线拥挤区域的预测、避开拥挤区域是布图设计中亟待解决的关键问题。布线的拥挤度抽象为数学问题就是图论中的路覆盖问题。本项目拟以路覆盖为研究对象，提出有效的算法，从而预测布线区域的拥挤度。