Partitioning using second-order information and stochastic-gain functions

Citation
S. Dutt et al., Partitioning using second-order information and stochastic-gain functions, IEEE COMP A, 18(4), 1999, pp. 421-435
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
ISSN journal
0278-0070 → ACNP
Volume
18
Issue
4
Year of publication
1999
Pages
421 - 435
Database
ISI
SICI code
0278-0070(199904)18:4<421:PUSIAS>2.0.ZU;2-L
Abstract
A probability-based partitioning algorithm, PROP, was introduced in [8] tha t achieved large improvements over traditional "deterministic" iterative-im provement techniques like Fidducia-Mattheyses (FM) [10] and Krishnamurthy's look-ahead (LA) algorithm [13], While PROP's gain function has a greater f uturistic component than FM or LA, it incorporates spatially local informat ion-only information on the removal probabilities of adjacent nets of a cel l is used in its gain computation. This prevents a higher-level view of non local structures. Also, giving uniform weights to all nets, results in an i nability to differentiate between the futuristic benefit of removing one ne t from another. This paper investigates for the first time the issues of us ing nonlocal structural information in gain functions and variable net weig hts based on the futuristic (stochastic) benefit of moving them from the cu tset, The result is a more sophisticated partitioner DEEP-PROP that perform s better for circuits with large complexities by incorporating more nonloca l (second-order) structural information than PROP, The second-order informa tion is incorporated into cell gains as well as variable net weights-the la tter helps to focus future cell moves in the "right" cluster around the cur rently moved cell and, thus, better utilizes the information that led to it s selection as the best move. A lower-complexity version, variable weight P ROP (VAR-PROP), that also uses dynamically assigned variable net weights, b ut based on first-order information, has also been developed, Both versions yield significant improvements over PROP on the ACM/SIGDA benchmark suite. DEEP-PROP yields mincut improvements of as much as 39% and an average of 2 0% for large circuits (10-K to 25-K cells) and an average of 14% over all c ircuits. DEEP-PROP is about a factor of 2.8 times slower than PROP, which i s very fast. VAR-PROP, which has a much lower computational complexity than DEEP-PROP, yields for large circuits, maximum and average mincut improveme nts over PROP of 27% and 18%, respectively, and an average of 12.6% improve ment over all circuits, It is only about 14% slower than PROP. For the only very large circuit golem3 in the suite (>100-K cells), the improvements pr oduced by DEEP-PROP and VAR-PROP over PROP are 15.6% and 11.5%, respectivel y. We also compare DEEP-PROP to FM, PROP and hMetis [14] for a subset of th e newer ISPD98 benchmark circuits [1], and demonstrate significant improvem ents over FM and PROP, and comparable mincuts (within 2%) to hMetis, one of the best multilevel partitioners.