LRoute: a delay minimal router for hierarchical CPLDs

ABSTRACT

This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.

REFERENCES

• 1: Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, Performance-oriented placement and routing for field-programmable gate arrays, Proceedings of the conference on European design automation, p.80-85, September 18-22, 1995, Brighton, England
• 2: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 3: S. Brown, J. Rose, and Z. G. Vranesic. A Detailed Router for Field-Programmable Gate Arrays". IEEE Trans. CAD, 11(5):620-628, 1992.
• 4: D. Bursky. High-Density PLD Family Combines Best of FPGAs and CPLDs". Electronic Design, pp. 42-57, May 1999.
• 5: P. K. Chan , M. D. F. Schlag, Acceleration of an FPGA router, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.175, April 16-18, 1997
• 6: P. K. Chan, M. Schlag, C. Ebeling, and L. Mc- Murchie. Distributed-Memory Parallel Routing for Field-Programmable Gate Arrays". Proc. FPGA, 2000.
• 7: Y. W. Chang, D. F. Wong, and C. K. Wong. Programmble Logic Devices". Encyclopedia of Electrical and Electronics Engineering, 1999.
• 8: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 9: C. Y. Lee. An Algorithm for Path Connections and its Applications". In IRE Trans. Electron. Comput., volume EC=10, pp. 346-365, 1961.
• 10: G. G. F. Lemieux, S. Brown, and D. Vranesic. On Two-Step Routing for FPGAs". In ACM Physical Design Workshop, pp. 215-226, 1993.
• 11: Guy G. F. Lemieux , Stephen D. Brown , Daniel Vranesic, On two-step routing for FPGAS, Proceedings of the 1997 international symposium on Physical design, p.60-66, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267682]
• 12: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 13: Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for row-based FPGAs, Proceedings of the 31st annual conference on Design automation, p.301-307, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196387]
• 14: Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for island-style FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.332-338, November 05-09, 1995, San Jose, California, United States
• 15: S. K. Nag and R. A. Rutenbar. Performance-Driven Simultaneous Placement and Routing for FPGAs". In IEEE Trans. CAD, Jun. 1998.
• 16: M. Palczewski, Plane parallel a maze router and its application to FPGAs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.691-697, June 08-12, 1992, Anaheim, California, United States
• 17: Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
• 18: R. Tessier. Negotiated A" Routing for FPGAs". 5th Canadian Workshop on FPDs, 1998.
• 19: Vantis. Mach Data Book". Vantis, Jan. 1997.
• 20: Yu-Liang Wu , Malgorzata Marek-Sadowska, Orthogonal greedy coupling: a new optimization approach to 2-D FPGA routing, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.568-573, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217591]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Design, Experimentation, Verification

Keywords:
Lagrangian relaxation, complex programmable logic devices, hierarchical model, routing