Incremental Placement and Routing Algorithms for FPGA and VLSI Circuits

这项研究致力于创建有效的算法，用于增量地替换和重新布线VLSI电路的一小部分，以纠正已经通过模拟在其中发现的诸如信号完整性、速度和高热密度的问题。挑战是快速地重新布局电路的受影响部分，同时最小化电路中较大的未受影响部分的任何布局改变，以便充分利用芯片物理设计上已经花费的巨大资源和时间，保持设计的已经优化的特征，并满足上市时间的要求。对于增量布局问题，研究了一种同时使用确定性和概率边成本的基于最小费用网络流的算法。在增量布线领域，正在研究以下领域：(A)用于约束驱动的“凹凸并改装”的算法(这允许探索具有不同约束集的解空间，例如关于净长度和/或延迟、过孔数量和串扰耦合的上界)。(2)在一个统一的框架内进行增量全局布线和详细布线，以获得更好的优化布线。(3)增量可满足性方法及其在增量路由中的应用。(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.