Innovation Sphere

Projects Sharing Researchers

Communicate

Details

Project TitleMinimum Area Retiming
Track Code2007-163
Short Description

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

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.

 
Tagssoftware: optimization, SOFTWARE: data mining
 
Posted DateApr 12, 2011 4:40 PM

Inventor(s)

Jia Wang

Hai Zhou*

Applications

  • 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

A patent application has been filed.

Contact Information

Arjan Quist, PhD

Invention Manager

(p) 847-467-0305

(e) arjan.quist@northwestern.edu