Minimum Area Retiming

NU 2007-163

Inventors

Jia Wang

Hai Zhou*

Short Description

An application for EDA software that minimizes register area in large VLSI circuits without changing circuit timing or functionality.

Abstract

Northwestern researchers have developed an application for EDA software that minimizes register area in large VLSI circuits without changing circuit timing or functionality.  It effectively and optimally solves the minimum area retiming problem with minimal runtime and memory usage.  Current solutions to this long-standing problem require a dense flow network to be constructed prior to solving the minimum-cost network flow problem.  This approach may become prohibitive for large VLSI circuits because of the huge runtime and overhead storage.  While incremental retiming algorithms have also been proposed and tested, they produce suboptimal solutions.  This new technology from Northwestern solves the minimum area retiming problem incrementally, optimally, and efficiently.  Instead of attacking the minimum 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.  For example, the researchers were able to successfully solve a problem in less than one minute using 65 MB memory for a circuit with more than 180k gates.  This is in stark contrast to another algorithm that failed to solve the problem after running for 2 hours and using up 2 GB memory. 

Application

• EDA Software

Advantages

• Solves the Minimum Area Retiming Problem efficiently, optimally and incrementally
• Works well on large VLSI circuits—60 fold faster than existing solutions

IP Status

Issued US Patent No. 8,813,001