Combinatorial Models for Local Routing of Integrated Circuits

April 22, 2004
1:30 pm - 2:30 pm
Halligan 102

Abstract

To design an integrated circuit, one must determine the positions of the subcircuit components and their interconnecting wires on the chip, subject to optimization objectives like minimizing the chip area or wire length. Local routing problems arise when the exact placement of wires through a specific geometric region of the chip is considered. In this talk we discuss the models used to study the combinatorial structure of local routing problems. As an example of how these models are applied, we consider two specific models and analyze how the choice of models affects an area lower bound for routing.