A comparative study of two Boolean formulations of FPGA detailed routing constraints

Gi Joon Nam, Fadi Aloul, Karem A. Sakallah, Rob A. Rutenbar

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents empirical analyses of two Boolean Satisfiability (SAT) formulations of FPGA (Field Programmable Gate Array) detailed routing constraints. Boolean SAT-based routing transforms a routing problem into a Boolean SAT instance by rendering geometric routing constraints as an atomic Boolean function. The generated Boolean function is satisfiable if and only if the corresponding routing is possible. Two different Boolean SAT-based routing models are analyzed: the track-based and the route-based routing constraint model. The track-based routing model transforms a routing task into a net-to-track assignment problem, whereas the route-based routing model reduces it into a routability-checking problem with explicitly enumerated set of detailed routes for nets. In both models, routing constraints are represented as CNF Boolean Satisfiability clauses. Through comparative experiments, we demonstrate that the route-based formulation yields an easier-to-evaluate and more scalable routability Boolean function than the track-based method. This is empirical evidence that a smart/efficient Boolean formulation can achieve significant performance improvement in real-world applications.

Original languageEnglish (US)
Pages (from-to)688-696
Number of pages9
JournalIEEE Transactions on Computers
Volume53
Issue number6
DOIs
StatePublished - Jun 2004

Keywords

  • Boolean satisfiability
  • FPGAs
  • Physical design
  • Routing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A comparative study of two Boolean formulations of FPGA detailed routing constraints'. Together they form a unique fingerprint.

Cite this