A fast circuit similarity-based placement engine for field programmable gate arrays

• Author / Creator

  Shi, Xiaoyu

• This thesis work presents a novel and efficient circuit similarity algorithm to detect topological similarity between two circuits. Targeting placement, our proposed circuit similarity algorithm, namely CSBP, is able to significantly accelerate placement based on this similarity. Moreover, circuit similarity can also be applied to other CAD phases, such as routing and verification. We have applied CSBP to incremental design for FPGAs and design space exploration for FPGAs, respectively. For incremental design, experimental results show CSBP is averaged 31X faster than the state-of-the-art Versatile Place and Route with comparable wire length and estimated critical delay. For design space exploration, experimental results show CSBP accurately depicts the ''shape'' of a design space and pinpoints the optimal designs at both logic level and algorithm level. Moreover, a turbo version of CSBP performs an average of 30X (up to 100X) faster than VPR's while still achieving comparable placement results.

• Subjects / Keywords

  • FPGA
  • Circuit similarity
  • Placement

• Graduation date

  Fall 2011

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3FD82

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.