Non-Manhattan (Hexagonal) Design

I'm currently interested in non-Manhattan design; this will be a major focus of my post-UCLA research.

Heuristic Optimization

Many of the problems in VLSI CAD are NP-Hard. Because of this, we have to resort to heuristic algorithms (which do not guarantee an optimal solution), or we approximate the real problem with a simple formulation that can be solved optimally.

For example, greedy algorithms, hill-climbing heuristics, genetic algorithms, randomized algorithms, and simulated annealing, are well known approaches to NP-Hard problems. Linear programming (with randomized rounding) or integer linear programming are also well known.

In my work, I've extended the Iterative Deletion approach, allowing it to be more effective on difficult problems. It has a bit in common with greedy algorithms, but allows a more global view of the problem. I've applied this to routing problems, and have had good results; I suspect that it can be applied to a more general class of problems, and that's what I'm looking into now.

MCM and PCB Routing

My current research is on MCM and PCB global routing, as part of the MUMON project. We'll have a paper published in this years Design Automation Conference that details this research; longer versions of this are available as a technical report, or in my PhD dissertation. Our approach is a heirarchical one; my router handles the global routing of ``tiles,'' while the detail routing of individual tiles is handled by others in the group.

Standard Cell Global Routing

Most of the work I've been doing at UCLA is related to standard cell global routing, with the development of the DECIMATE standard cell global router.

The user interface of the global router is implemented with Tcl/Tk, while the back end is written in C. I parse TimberWolf version 6.0 and 7.0 (which is called 1.0 in the commercial version) format input files, and produce version 7.0 output.

I've also been interested in placement, and circuit testing.

If you're doing research in this area, my MCNC benchmark page might be of use to you. I've put up the MCNC place and route benchmarks in TW7.0/1.0 format, and have the placed and routed solutions available as well.

Software Engineering

In order to test out VLSI CAD ideas, they usually have to be implemented, and run on fairly large benchmarks. Thus, in the course of my VLSI CAD research, I've had to write quite a bit of code, and have more than a passing interest in software engineering.

To reduce some of the burden of software development, I've written an editor that was suited to my needs. Check out EDGE, and my released software pages.

Graphics

There are a few areas where the advances in chip design and fabrication will make a large impact. Graphics (and in particular, real-time 3D) is one of those areas. At UCLA, I've been reading up on graphics literature in my spare time.

My startup company, IKM, is where I play around with some of the ideas I've had. After graduation, we may pursue this direction more aggressively.

Back to the top