Technical Report MSC-2009-11

Title: Interconnect-driven Cell-based Migration of Integrated Circuit Layout
Authors: Evgeny Shaphir
Supervisors: Shmuel Wimer, Ron Y. Pinter
Abstract: Time to market and cost are primary drivers to preserve designs of integrated circuits, calling for effective migration methods. Moreover, it is desirable to maintain the hierarchical nature of a design for performance, use of libraries, and maintainability. Thus, flattening a layout for migration is inappropriate both due to the huge data structures that might arise as well as the loss of the hierarchical information. We provide a novel, cell-based method for migrating hierarchical designs, while meeting performance constraints imposed on the signals goals such as delay, power and signal integrity. Our algorithm separates the placement and interconnect considerations in a clear and effective manner. It supports a bottom-up flow with emphasis on efficient interconnect migration, thus addressing the most difficult challenge in cell-based compaction. The algorithm's input is a source layout, a target layout sizing together with a placement, the target's manufacturing technology design rules, and target design performance specifications; it uses a hierarchy of directed graphs to represent the constraints of the interconnect layout in a non-redundant fashion. The complete solution is derived top-down, formulating and solving a Linear Programming problem, treating a single level of the hierarchy at the time. It satisfies the new design rules, a good starting point for convergence, preserving hierarchies and wires' order. We prove that the algorithm either returns a legal routing or manifests contradictory constraints. Finally, we have implemented our method and applied it to a number of microprocessor designs, demonstrating a significant reduction of time complexity without sacrificing the quality of the resulting layout.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2009
To the main CS technical reports page

Computer science department, Technion