Algorithms for Access Point Selection at Pre-Routing Stage

  • Marcelo Freire Danigno Federal University of Rio Grande (FURG) - Brazil https://orcid.org/0000-0003-0099-5813
  • Mateus Fogaça Federal University of Rio Grande do Sul (UFRGS) - Brazil
  • Eder Monteiro Federal University of Rio Grande do Sul (UFRGS) - Brazil
  • Jorge Ferreira Federal University of Rio Grande do Sul (UFRGS) - Brazil
  • André Oliveira Federal University of Rio Grande do Sul (UFRGS) - Brazil
  • Ricardo Reis Federal University of Rio Grande do Sul (UFRGS) - Brazil
  • Paulo Butzen Federal University of Rio Grande do Sul (UFRGS) - Brazil
Keywords: Eletronic Design Automation, Physical Design, Detailed Routing, Pin Access

Abstract

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.

Published
2021-08-15