Open AccessAlgorithms for Access Point Selection at Pre-Routing Stage
Author(s) -
Marcelo Danigno,
Mateus Fogaça,
Eder Monteiro,
Jorge Ferreira,
André Oliveira,
Ricardo Reis,
Paulo F. Butzen
Publication year - 2021
Publication title -
jics. journal of integrated circuits and systems
Language(s) - English
Resource type - Journals
eISSN - 1872-0234
pISSN - 1807-1953
DOI - 10.29292/jics.v16i2.128
Subject(s) - computer science , routing (electronic design automation) , router , pessimism , physical design , design flow , heuristics , point (geometry) , selection (genetic algorithm) , false positive paradox , network routing , distributed computing , computer network , embedded system , machine learning , circuit design , philosophy , geometry , mathematics , epistemology , operating system
Pin accessibility has arisen as a major issue for detailed routing due to the increased number of design rules and higher pin density of modern technology nodes. The existing literature tackles this problem across many stages of the design flow: standard-cell layout, placement optimization and routing. In our present work, we cope with the pin accessibility challenge as a pre-processing step for detailed routing. We devise five techniques to find on-track locations in which the router can access I/O pins of standard cell instances without causing design rule violations (DRVs.) We provide the algorithm complexity analyses for each of our techniques. Some of our methods tackle the complexity of checking the design rules using pessimism (i.e., they are subject to false positives). We also study the cases in which our methods are overly pessimistic and ways to overcome pessimism. Finally, we validate our techniques using the 45 and 32 nanometer designs from the ISPD 2018 contest on initial detailed routing and show that our most robust technique can find DRV-free access points for more than 99\% of the pins of the test cases in less than 5 minutes.