FPGA detailed routing problem is an interesting problem in VLSI field because of the limited routing resources in island style FPGA architectures. In this paper, the effectiveness of various switch boxes (Subset, Wilton and Universal) in FPGA detailed routing has been tested using a Boolean satisfiability (SAT) based approach. A SAT instance is formulated for each routing problem and routability is tested using a back-end SAT solver. The performances of different switches have been tested and compared in terms of routability and minimum channel width.

1. Arslan, H. and Dutt, S. 2003. Road: An order-impervious optimal detailed router for FPGAs. In 21st International Conference on Computer Design (ICCD 2003), VLSI in Computers and Processors, 13-15 October 2003, San Jose, CA, USA, Proceedings, pages 350–356. IEEE Computer Society.
2. Arslan, H. and Dutt, S. , 2004. An effective hop-based detailed router for FPGAs for optimizing track usage and circuit performance. In Proceedings of the 14th ACM Great Lakes Symposium on VLSI 2004, Boston, MA, USA, April 26-28, 2004, pages 208–213. ACM.
3. Betz, V. and Rose, J. 1997. Vpr: A new packing and placement and routing tool for FPGA research. In Proceeding of 7th Annual Workshop Field Programmable Logic and Applications, pages 213–222.
4. Bryant, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, C-35(8):677–691, August.
5. Devadas, S. 1989. Optimal layout via Boolean satisfiability. In Proceeding of the International Conference on Computer-Aided Design (ICCAD), pages 294–297. ACM/IEEE, November.
6. http://www. eecg. toronto. edu/~vaughn/challenge/challenge. html.
7. Hung, W. N. N, Song, X. , Aboulhamid, E. M. , Kennings, A. and Coppola, A. 2004. Segmented channel routability via satisfiability. ACM Transactions on Design Automation of Electronic Systems (TODAES), 9(4).
8. Bayardo Jr. , R. and Schrag, R. 1997. Using csp look-back techniques to solve real world sat instances. In Proceeding of the 14th International Conference on Artificial Intelligence, pages 203–208.
9. Karro, J. and Cohoon, J. 2002. Gambit: A tool for the simultaneous placement and detailed routing of gate arrays. In Proceeding of FPL 2001, LNCS 2147, pages 243–253, Berlin Heidelberg, Springer-Verlag.
10. Marques-Silva, J. P. and Sakallah, K. 1999. Grasp: A search algorithm for propositional satisfiability. IEEE Trans. Computers, 48(5).
11. McMurchie, L. E. and Ebeling, C. 1995. Pathfinder: A negotiation-based path-driven router for FPGAs In Proceeding of the International Symphosium on FPGAs. ACM/IEEE, Feb.
12. Nam, G. , Aloul, F. , Sakallah, K. and Rutenbar, R. 2004. A comparative study of two Boolean formulations of FPGA detailed routing constraints. IEEE Trans. Computers, 53(6), June.
13. http://www. eecg. toronto. edu/~lemieux/sega/sega. html.
14. Song, X. Hung, N. N. , Mishchenko, A. , Chrzanowska-Jeske, M. , Kennings, A. , and Coppola, A. 2003. Board-level multiterminal net assignment for the partial cross-bar architecture. IEEE Trans. Very Large Scale Integr. Syst. , 11:511–514, June.
15. Velev, M. N. and Gao, P. 2008. Comparison of boolean satisfiability encodings on FPGA detailed routing problems. In Proceedings of the conference on Design automation and test in Europe, DATE '08, pages 1268–1273, New York, NY, USA, ACM.
16. Chang, Y. , Wong, D. F. and Wong, C. K. 1996. Universal switch modules for FPGA design. ACM Trans. Design Automation of Electronic Systems, 1:80–101.
17. Wood, R. G. and Rutenbar, R. A. 1998. FPGA routing and routability estimationvia Boolean satisfiabily. IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 6(2):222–231, June.
18. http://www. xilinx. com/products/xc4000e. htm.
19. http://www. princeton. edu/~chaff/zChaff. html.
20. Zhang, H. 1997. Sato: An efficient propositional prover. In Proceeding of the International Conference on Automated Deduction, pages 272–275.

Fpga Switch Box Detailed Routing Satisfiability