Board-level multiterminal net assignment

ABSTRACT

The paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in Clos-Folded FPGA based logic emulation systems. The approach transforms the FPGA board-level routing task into a single, large Boolean equation with the property that any assignment of input variables that satis¿fies the equation specifies a valid routing. The approach considers all nets simultaneously and the absence of a satisfying assignment implies that the layout is unroutable. We use two of the fastest SAT solvers: Chaff and DLM to perform our experiments. Empirical re¿sults show that the method is time-efficient and applicable to large layout problem instances.

REFERENCES

• 1: Mohammed A. S. Khalid , Jonathan Rose, A hybrid complete-graph partial-crossbar routing architecture for multi-FPGA systems, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.45-54, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275119]
• 2: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 3: J. Varghese, M. Butts, and J. Baatcheller, "An efficient logic emulation system," IEEE Trans. VLSI Systems, Vol. 1(2), pp. 171- 174, 1993.
• 4: M. Slimane-Kadi, D. Brasen, and G. Saucier, "A fast FPGA prototyping system that uses inexpensive high-performance FPIC," Proc. ACM/SIGDA Int. Workshop FPGAs, 1994.
• 5: L. Maliniak, "Multiplexing enhances hardware emulation," Electronic Design, pp. 76-78, 1992.
• 6: Stephen Walters, Computer-Aided Prototyping for ASIC-Based Systems, IEEE Design & Test, v.8 n.2, p.4-10, April 1991 [doi>10.1109/54.82034]
• 7: K. Yamada, H. Nakada, A. Tsutsui, and N. Ohta, "High-speed emulation of communication circuits on a multiple-FPGA system," Proc. ACM/SIGDA Int. Workshop FPGAs, 1994.
• 8: Wai-Kei Mak , D. F. Wong, Board-level multi-terminal net routing for FPGA-based logic emulation, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.339-344, November 05-09, 1995, San Jose, California, United States
• 9: W.K. Mak and D.F. Wong, "On optimal board-level routing for FPGA-based logic emulation," IEEE Trans. CAD, Vol. 16(3), 1997.
• 10: S. Lin, Y. Lin, and T. Hwang, "Net Assignment for the FPGA- Based Logic Emulation System in the Folded-Clos Network Structure," IEEE Trans. CAD, Vol. 16(3), 1997.
• 11: Performance-Driven Board-Level Routing for FPGA-based Logic Emulation, Proceedings of the International Conference on Computer Design, p.199, October 05-05, 1998
• 12: Nan-Chi Chou , Lung-Tien Liu , Chung-Kuan Cheng , Wei-Jin Dai , Rodney Lindelof, Circuit partitioning for huge logic emulation systems, Proceedings of the 31st annual conference on Design automation, p.244-249, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196365]
• 13: P.K. Chan, and M.D.F. Schlag, "Architectural Trade-offs in Field-Programmable-Device Based Computing Systems," Proc. IEEE Workshop on FPGAs for Custom Computing Machines,pp. 138-141, April 1993.
• 14: S. Devadas, "Optimal layout via Boolean Satisfiability," Proc. ACM/IEEE ICCAD, 1989, pp. 294-297.
• 15: Maya Gokhale , William Holmes , Andrew Kopser , Sara Lucas , Ronald Minnich , Douglas Sweely , Daniel Lopresti, Building and Using a Highly Parallel Programmable Logic Array, Computer, v.24 n.1, p.81-89, January 1991 [doi>10.1109/2.67197]
• 16: P. Berlin, D. Roncin, and J. Vuillemin, "Programmable active memories: A performance assessment," Proc. 1st International Workshop on FPGAs, Feb. 1992, pp. 57-59.
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Gi-Joon Nam , Karem A. Sakallah , Rob A. Rutenbar, Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.167-175, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296450]
• 19: Gi-Joon Nam , Fadi Aloul , Karem Sakallah , Rob Rutenbar, A comparative study of two Boolean formulations of FPGA detailed routing constraints, Proceedings of the 2001 international symposium on Physical design, p.222-227, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369777]
• 20: Yi Shang , Benjamin W. Wah, A Discrete Lagrangian-Based Global-SearchMethod for Solving Satisfiability Problems, Journal of Global Optimization, v.12 n.1, p.61-99, January 1998 [doi>10.1023/A:1008287028851]
• 21: Miroslav N. Velev , Randal E. Bryant, Effective use of boolean satisfiability procedures in the formal verification of superscalar and VLIW, Proceedings of the 38th conference on Design automation, p.226-231, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378469]
• 22: Lintao Zhang , Conor F. Madigan , Matthew H. Moskewicz , Sharad Malik, Efficient conflict driven learning in a boolean satisfiability solver, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 23: Abdel Ejnioui , N. Ranganathan, Multi-terminal net routing for partial crossbar-based multi-FPGA systems, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.176-185, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296454]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Measurement, Verification