Optimization of FPGA Routing Algorithms

Optimization of FPGA Routing Algorithms : 

Optimization of FPGA Routing Algorithms By: Liat Shalev Housfater EE8120 Professor K. Raahemifar October 25, 2009

Outline : 

Outline Introduction Application Motivation FPGA Overview FPGA Routing Configuration Theory FPGA Routing Methods Geometric Routing Algorithm Boolean-based Routing Algorithm VPR Future Works References

Introduction : 

Introduction A Field Programmable Gate Array (FPGA) consists of an array of prefabricated logic blocks and wiring resources which can be easily configured by end users. Motivation Reduce area Reduce design time Reduce cost

Introduction FPGA Architecture[5] : 

Introduction FPGA Architecture[5]

Introduction FPGA Design Flow : 

Introduction FPGA Design Flow

TheoryFPGA Routing Methods : 

TheoryFPGA Routing Methods Boolean-based Routing Algorithm Transforms the geometric FPGA routing task into a single, large Boolean equation. Uses direct SAT solver PROS: Formulation considers all nets simultaneously. CONS: SAT formulations either satisfy, or not; there are no partial solutions.

Theory Boolean-based Routing Algorithm : 

Theory Boolean-based Routing Algorithm Track-based routing constraint model [5] Net-to-track assignment problem Constraints: connectivity constraints Exclusivity constraints Route-based routing constraint model [5] “Routability checking” problem Constraints: Liveness constraints Exclusivity constraints

TheoryFPGA Routing Methods : 

TheoryFPGA Routing Methods Geometric Routing Algorithm Based on rip-up and re-route routing algorithm VPR (Versatile Placer and Router) PROS: Allows to easily describe the targeting architecture CONS: has difficulty achieving routing solution convergence

TheoryFPGA Routing Methods : 

TheoryFPGA Routing Methods Rip-up and Re-route Phase I checking for routing-resource violations Phase II checking for timing-violations Wiring delay, net delay, net slack

TheoryGeometric Routing Algorithm : 

TheoryGeometric Routing Algorithm Maze Router Exhaustive breadth-first (BFS) search Optimization criteria: minimize the total wire length Cost function is biased towards distance A* Search Exhaustive depth-first search (DFS) algorithm Cost function is biased toward congestion and distance Figure 1 - [3]

TheoryVPR : 

TheoryVPR Pathfinder based algorithm (Dijkstra) Two phases: Initial routing Rip-up and rerouting

TheoryVPR [7] : 

TheoryVPR [7]

TheoryVPR [6] : 

TheoryVPR [6] Cost function: Cost(n) = b(n).h(n).p(n) b(n) = base cost h(n) = historical congestion p(n) = present congestion penalty Congestion depends on occupancy and capacity

Future Work : 

Future Work Implementation VPR Purpose optimization of area and time by modification of various parameters (I.e. channel width, # of tracks, wire length, etc.)

References : 

References [1] Yulan Tang, Hao Gao, Zongguang Yu, "Solution and Optimization of FPGA Routing Algorithm," icfn, pp.79-82, 2009 International Conference on Future Networks, 2009 [2] Hui Xu, Rob A. Rutenbar, sub-SAT: A Formulation for Relaxed Boolean Satisfiability with Applications in Routing [C], Proc. ISPD’02, April 7-10, 2002, 182-187. [3] Zhan Liu, Zongguang Yu, Xiaofeng Gu, A New and Efficient Algorithm for FPGA Routing [C], the 2nd IEEE Conference on Industrial Electronics and Applications, 2007, 1431-1436. [4]Alastair M. Smith, George A. Constantinides, Peter Y. K. Cheung, “Area estimation and optimization of FPGA routing fabrics,” in Field Programmable Logic and Applications, 2009. FPL 2009. International Conference on Aug. 31 2009-Sept. 2 2009 Page(s):256 - 261 [5] G.-J. Nam, F. Aloul, K. Sakallah, and R.A. Rutenbar, A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints [C], Proc. ACM Int’l Symposium on Physical Design (ISPD’01), vol. 53, no. 6, June 2004. [6] Samy M. Boshra, Hazem M. Abbas, Ahmed M. Darwish, Ihab E. Talkhan. “Performance and routability improvements for routability-driven FPGA router,” Circuits and Systems, 2006. ISCAS 2006. Proceedings. 2006 IEEE International Symposium. pp. 537 - 540. [7] V. Betz and J. Rose, “VPR: A New Packing, Placement and Routing Tool for FPGA Research,” Seventh International Workshop on Field-Programmable Logic and Applications, 1997, pp. 213 -222.

Thank You! : 

Thank You! Contact: lshalevh@ee.ryerson.ca