M.Sc Thesis

M.Sc StudentShaphir Evgeny
SubjectInterconnect-Driven Cell-Based Migration of Integrated
Circuit Layout
DepartmentDepartment of Computer Science
Supervisors PROF. Ron Pinter
Full Thesis textFull thesis text - English Version


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.