现场可编程门阵列(FPGA)能够减少电子系统的开发风险和开发成本，缩短上市时间，降低维护升级成本，故广泛地应用在电子系统中。最新的FPGA都采用了层次化的布线资源结构，与以前的结构发生了很大的变化。由于FPGA布线资源的固定性和有限性，因此需要开发适用于这种层次化的FPGA结构并提高布线资源有效利用率的布线算法。同时由于晶体管尺寸的不断减小，有必要在FPGA布线算法中考虑功耗和时序问题。 本论文所作的研究工作主要包括：提出一种基于Tile的FPGA结构描述方法，对FPGA功耗模型和时序模型进行了研究，实现了考虑FPGA功耗、布线资源利用率的布线算法。 在FPGA结构描述方面，本文在分析现代商用FPGA层次化结构及学术上对FPGA描述方法的基础上，提出一种基于Tile的FPGA结构描述。由于基本Tile的重复性，采用该方法可以简化FPGA结构的描述，同时由于该方法是以硬件结构为根据，为FPGA软硬件提供了简单而灵活的接口，该方法在原型系统中测试证明是正确的。 在FPGA功耗模型方面，本文研究了ASIC中关于电路功耗计算的基本方法，并将其应用到FPGA功耗分析中。在模型中的采用了混合的功耗模型，包括动态功耗模型和静态功耗模型。动态功耗的计算采用基于节点状态转换率的开关级动态功耗计算和逻辑块宏模型，静态功耗则采用基于公式计算的晶体管漏电功耗模型和逻辑块基于仿真的LUT/MUX表达式计算模型。这些功耗模型将运用到我们后面的功耗计算和基于功耗驱动的布线算法中。 在FPGA布线算法研究和实现方面，本文在介绍基本的搜索算法之后，介绍了将FPGA硬件结构转变为FPGA布线程序可识别的布线资源图的方法，并将基本的搜索算法运用的FPGA布线资源图上，实现FPGA的基于布通率的布线算法。在此基础上，借鉴了FPGA时序分析方法，将时序分析作为布线算法的一子模块，对基于时序的布线算法进行了研究；同时采用了FPGA功耗模型，在布线算法实现中考虑了动态功耗的问题。最后在布线算法中实现两种启发式策略以提高可布线资源有效利用率。
