Loading...
Please wait, while we are loading the content...
Similar Documents
FPGA Placement by Graph Isomorphism
| Content Provider | Semantic Scholar |
|---|---|
| Author | Savarbaghi, Hossein Omidian Bazargan, Kia |
| Copyright Year | 2011 |
| Abstract | FPGA placement and routing are still challenging problems. Given the increased diversity of logic and routing resources on FPGA chips, it seems appropriate to tackle the placement problem as a mapping between the nodes and edges in a circuit graph to compatible resources in the architecture graph. We explore utilizing graph isomorphism algorithms to perform FPGA placement. We use a hierarchical approach in which the circuit and architecture graphs are simultaneously clustered to reduce the size of the search space, and then a novel reductive graph product method is used to solve the isomorphism problem. The graph product algorithm is called reductive as it eliminates a linear number of candidates at every step of the search process, reducing the number of candidate nodes by approximately 1/3. Compared to the annealing-based placement tool VPR 5.0, we achieve approximately 40% improvement in placement runtime, while improving the critical path delay by about 7% and wire length by 5%, while demanding 1.3% more channels on average. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ece.ubc.ca/~hosseino/publication/hossein-isomorphism.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
