We present a new faster design-style independent iterative placement improvement algorithm. Randomized simulated annealing based algorithms produce good result. But on very large designs, the inherently long run-time makes it prohibitive to use randomized algorithm. On the other hand deterministic improvement methods do not produce as good a result as the simulated annealing based algorithms. Moreover, none of the existing placement improvement techniques addresses the non row-based design style. In this paper, we combine the advantages of both the random and deterministic approach to develop a new faster placement improvement algorithm. Experimental results show that our algorithm performs much better than existing placement improvement algorithm. On some benchmarks, our algorithm is as much as 8/spl times/ faster than that on Domino with a significant reduction in total net length.

We show how tree structures can be embedded in a one-dimensional systolic array to solve a connectivity problem, the UNION-FIND problem, by a single left-to-right pass of the data through the array. A previous solution, which did not use trees, required a left-to-right pass followed by a right-to-left pass through the array, as well as a more complex program for each cell.