Abstract | ||
---|---|---|
Abstract In many application in VLSI CAD, a given netlist has to be partitioned into smaller sub-designs which can be han- dled much,better. In this paper we present a new recur- sive bi-partitioning algorithm that is especially applicable, if a large number of final partitions, e.g. more than 1000, has to be computed. The algorithm consists of two steps. Based on recursive splits the problem is divided into several sub-problems, but with increasing recursion depth more run time is invested. By this an initial solution is determined very fast. The core of the method is a second step, where a very powerful greedy algorithm is applied to refine the par- titions. Experimental results are given that compare the new approach to state-of-the-art tools. The experiments show that the new approach outperforms the standard techniques with respect to run time and quality. Furthermore, the mem- ory usage is very low and is reduced in comparison to other methods by more than a factor of four. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S1383-7621(03)00093-6 | Euromicro Symposium on Digital Systems Design |
Keywords | Field | DocType |
field programmable gate arrays,design automation,vlsi,application software,computer science,routing,algorithm design and analysis,greedy algorithms,design optimization,very large scale integration,greedy algorithm | Netlist,Vlsi cad,Recursion (computer science),Computer science,Parallel computing,Computer Aided Design,Algorithm,Greedy algorithm,Algorithm theory,Very-large-scale integration,Recursion | Journal |
Volume | Issue | ISSN |
49 | 12 | Journal of Systems Architecture |
ISBN | Citations | PageRank |
0-7695-1790-0 | 6 | 0.51 |
References | Authors | |
19 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rolf Drechsler | 1 | 3707 | 351.36 |
Wolfgang Günther | 2 | 6 | 0.51 |
Thomas Eschbach | 3 | 33 | 4.00 |
Lothar Linhard | 4 | 6 | 0.51 |
Gerhard Angst | 5 | 6 | 0.51 |