Path: utzoo!attcan!uunet!aplcen!samsung!cs.utexas.edu!sun-barr!olivea!orc!inews!cmdnfs!bhoughto
From: bhoughto@cmdnfs.intel.com (Blair P. Houghton)
Newsgroups: comp.lsi.cad
Subject: Re: VLSI Technology place and route tools for gate arrays
Message-ID: <148@inews.intel.com>
Date: 20 Sep 90 15:54:08 GMT
References: <4470@optilink.UUCP> <1990Sep18.151012.1177@arnor.uucp>
Sender: news@inews.intel.com
Organization: Intel Corp, Chandler, AZ
Lines: 32

In article <1990Sep18.151012.1177@arnor.uucp> dgreen@cs.ucla.edu writes:
>manley@optilink.UUCP (Dave Manley) writes:
>|> Do (can) the placement tools use the hierarchical netlist to obtain a
>|> better placement than is available from the flattened netlist?  I
>|> assume the extra information in the hierarchical netlist could be
>|> used to do this?
>
>However, it isn't all that clear that using the hierarchy necessarily
>helps.  In some cases, yes.  In others, no.

It helps.  The least it does is improve critical-path; often it also
aids the place-n-route tool by removing a big chunk of its placement
choices.

[Dan's ref:]
>  J. Rose, W. Klebsch and J. Wolf, Temperature Measurements and
>  Equilibrium Dynamics of Simulated Annealing Placements, IEEE 
>  Transactions on CAD, v 9, n 3 (March 1990) p 253-259.
>
>Dan Greening		12 Foster Court			NY (914) 784-7861
>dgreen@cs.ucla.edu	Croton-on-Hudson, NY 10520	CA (213) 825-2266

Check out also
    Fiduccia, C. M., and Mattheyses, R. M., "A Linear-Time Heuristic
    for Improving Network Partitions", Proc 19th IEEE Design Automation
    Conference (DAC), 1982, pp175ff.

The references in that paper cite some stuff Kernighan and Lin did
at Bell Labs in the very early '70s.

				--Blair
				  "...bigger, stronger, faster."