Kahng The unifying theme of this research is that the underlying geometries, embedding dimensions and topological representations of CAD designs, together afford a perspective for effective algorithm design. The research is in three areas. 1. Performance-driven synthesis at various levels of design, including clustering for problem decomposition and fast hierarchical placement, and estimation of intrinsic resource requirements via topological criteria. 2. Assessment of design problem complexity based on the interaction between topology of neighborhood structures and scaling geometry in the associated cost surfaces. This includes time-bounded stochastic optimizations, and a non-monotone class of annealing methods. 3. Capturing the underlying physics of high-speed devices and interconnects while maintaining algorithmically tractable formulations. Examples are a unified routing tree optimization and the separation of the interconnect topology from subsequent geometric embedding.
