Incremental Placement and Routing Algorithms for FPGA and VLSI Circuits

本研究解决了高效算法的创建，用于增量替换和重新路由VLSI电路的小部分，以纠正通过仿真发现的信号完整性，速度和高热密度等问题。挑战在于快速重新布局电路中受影响的部分，同时最大限度地减少电路中较大的未受影响部分的布局变化，以便利用已经花费在芯片物理设计上的巨大资源和时间，保留已经优化的设计特征，并满足上市时间要求。该项目正在解决常规VLSI芯片和现场可编程门阵列（fpga）的算法。对于增量布局问题，研究了基于确定性和概率边缘成本的最小成本网络流算法。在增量路由领域，正在研究以下领域：(a)约束驱动的“碰撞和改装”算法（这允许探索具有不同约束集的解空间，如净长度和/或延迟增加的上界，过孔数量和串扰耦合）。(2)在一个统一的框架中进行增量的全局和详细路由，以获得更好的优化路由。(3)增量可满足性（SAT）方法及其在增量路由中的应用。(4) VLSI电路增量路由所需的各种附加问题和解决技术。

This research addresses the creation of efficient algorithms for incrementally re-placing and re-routing small portions of a VLSI circuit to correct problems such as signal integrity, speed and high heat density that have been discovered therein via simulation. The challenge is to quickly re-layout only the affected portion of the circuit, while minimizing any layout changes of the much larger unaffected part of the circuit in order to capitalize on the enormous resources and time already spent on the physical design of the chip, to retain the already optimized features of the design, and to meet time-to-market requirements.Algorithms for both regular VLSI chips and field-programmable gate arrays (FPGAs) are being addressed in this project. For the incremental placement problem, a min-cost network-flow based algorithm is being investigated using both deterministic and probabilistic edge costs. In the incremental routing realm, the following areas are being researched: (a) Algorithms for constraint-driven "bump-and-refit" (this allows exploration of solution spaces with different sets of constraints like upper bounds on the increase in net lengths and/or delays, on the number of vias, and on crosstalk coupling). (2) Performing incremental global and detailed routing in one consolidated framework in order to obtain better optimized routings. (3) Incremental Satisfiability (SAT) methods and their application to incremental routing. (4) Various additional issues and solution techniques needed for incremental routing of VLSI circuits.