Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!p.cs.uiuc.edu!gillies
From: gillies@p.cs.uiuc.edu
Newsgroups: comp.arch
Subject: Re: What kinds of problems...
Message-ID: <76700080@p.cs.uiuc.edu>
Date: 21 Mar 89 06:38:00 GMT
References: <15943@oberon.USC.EDU>
Lines: 15
Nf-ID: #R:oberon.USC.EDU:15943:p.cs.uiuc.edu:76700080:000:689
Nf-From: p.cs.uiuc.edu!gillies    Mar 21 00:38:00 1989


Optimization in VLSI CAD is also a black-hole for integer CPU cycles.
The problem of translating a logic design into a chip is so
complicated that it has been broken into 6 steps, most/all of which
are NP-Hard.  Some of the algorithms that can really eat your lunch
are:

1.  PLA/Logic minimization (exact solution of NP-Hard problems)
2.  Simulated Annealing / Neural Net optimization of the floorplan
    design, layout, and (global/channel) routing.  Or other types of
    iterative branch & bound algorithms for solving these problems
    optimally or even sub-optimally.

In other words, just about everything having to do with silicon
compiler "optimal chip generation" is expensive.