Efficient routability check algorithms for segmented channel routing

ABSTRACT

The segmented channel-routing problem arises in the context of row-based field programmable gate arrays (FPGAs). Since the K-segment channel-routing problem is NP-complete for K ≥ 2, an efficient algorithm using the weighted bipartite-matching approach is developed for this problem. Connections that;form a maximum clique are chosen first to be routed to the segmented channel. Then, another maximum clique of the remained connections is routed until all connections have been processed. In addition, a powerful “unroutability check” algorithm is uniquely proposed to tell whether the horizontal switches in an interval of the segmented channel are sufficient for routing or not. Hence, we can precisely discriminate the routable and the unroutable ones from all the test cases. As shown in the experiments, average discrimination ratios of 98.8% and 99.4% are obtained for the 2-segmentation and 3-segmentation models, respectively. Moreover, when applying our routing algorithm to the analyzed nonunroutable cases, a routing failure ratio of 1.5% is reported for the 2-segmentation model, compared to Zhu and Wong's 5.9%; also, a routing failure ratio of 0.8% (less than their 4.7%) is obtained for the 3-segmentation model. In total, the routing failure ratio of our routing algorithm is less than 21% of Zhu and Wong's.

REFERENCES

• 1: ACTEL CORP. 1991. ACT Family FPGA Databook.
• 2: Surendra Burman , Chandar Kamalanathan , Naveed Sherwani, New channel segmentation model and associated routing algorithm for high performance FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.22-25, November 1992, Santa Clara, California, United States
• 3: Abbas El Gamal , Jonathan Greene , Vwani Roychowdhury, Segmented channel routing in nearly as efficient as channel routing (and just as hard), Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.192-211, April 1991
• 4: EL GAMAL, A., GREENE, J., REYNARI, J., ROGOYSKI, E., EL AYAT, K. A., AND MOHSEN, A. 1989. An architecture for electrically configurable gate arrays. IEEE J. Solid-State Circuits 24, 2 (Apr.), 394-398.
• 5: 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
• 6: Jonathan Greene , Vwani Roychowdhury , Sinan Kaptanoglu , Abbas El Gamal, Segmented channel routing, Proceedings of the 27th ACM/IEEE conference on Design automation, p.567-572, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123405]
• 7: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 8: PEDRAM, M., NOBANDEGANI, B. S., AND PREAS, B. T. 1994. Design and analysis of segmented routing channels for row-based FPGA's. IEEE Trans. Comput.-Aided Des. 13, 12 (Dec.), 1470-1479.
• 9: RHEINBOLDT, W. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, Inc., New York, NY.
• 10: RoY, K. 1993. A bounded search algorithm for segmented channel routing for FPGA's and associated channel architecture issues. IEEE Trans. Comput.-Aided Des. 12, 11, 1695-1705.
• 11: ROYCHOWDHURY, V. P., GREENE, J., AND EL GAMAL, A. 1993. Segmented channel routing. IEEE Trans. Comput.-Aided Des. 12, 1, 79-95.
• 12: Kai Zhu , D. F. Wong, On channel segmentation design for row-based FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.26-29, November 1992, Santa Clara, California, United States

INDEX TERMS

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

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

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
field programmable gate arryas (FPGAs), routing, segmented channel