Method for Minimum Area Retiming (27163)
The invention can be practically implemented in EDA software to efficiently produce minimized register area in large VLSI circuits without changing circuit timing or functionality. It can achieve this, because it solves the minimum area retiming problem efficiently and optimally with minimal runtime and memory usage. For a circuit with more than 180k gates, the best known currently available algorithm failed to solve the problem after running for 2 hours and using up 2GB memory, while the invention successfully solved the same problem in less than one (1) minute using only 65MB memory.Existing algorithms that optimally solve the minimum area retiming problem require a dense flow network to be constructed prior to solving the minimum-cost network flow problem. This approach can become prohibitive for large VLSI circuits, because of the huge runtime and storage overhead. To mitigate this problem, incremental retiming algorithms have been proposed and tested, but these will produce suboptimal solutions. The invention fills a gap, solving the min-area retiming problem incrementally, optimally, and efficiently. Instead of attacking the min-area retiming problem by solving a minimum-cost network flow problem on a dense flow network, the invention generates active timing constraints dynamically, and maintains them in a special data structure to enable efficient incremental minimum area retiming while guaranteeing optimality.
PROOF OF CONCEPT: The inventors employed three benchmark suites to test the invention against the best known currently available algorithm for VLSI circuits with 4-180k gates. The speedup on the total runtime for all the benchmarks is at least 60x. On a design with 180k gates, while the best known currently available algorithm failed to solve the problem after running for 2 hours and using up 2GB memory, the invention solved the same problem in less than one (1) minute using only 65MB memory.
FIELD OF APPLICATION: EDA Software
STAGE OF DEVELOPMENT: Northwestern seeks a licensing partner to commercialize this invention.
Inventor(s): Jia Wang and Hai Zhou
Type of Offer: Licensing
« More Software Patents