Spectral-based multi-way FPGA partitioning

ABSTRACT

Recent research on FPGA partitioning has focussed on finding minimum cuts between partitions without regard to the routability of the partitioned subcircuits. In this paper we develop a spectral approach to multi-way partitioning in which the primary goal is to produce routable subcircuits while maximizing FPGA device utilization. To assist the partitioner in assessing the routability of the partitioned subcircuits, we have developed a theory to predict the routability of the partitioned subcircuits prior to partitioning. Advancement over the current work is evidenced by results of experiments on the standard MCNC benchmarks.

REFERENCES

• 1: XILINX: The Programmable Gate Array Data Book. 2100 logic Drive, San Jose, CA 95124,1993.
• 2: C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196603]
• 3: Narasimha B. Bhat , Dwight D. Hill, Routable Technologie Mapping for LUT FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.95-98, October 11-14, 1992
• 4: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
• 5: P. K. Chan, M. Schlag, and J. Zien. Spectral k-way ratio-cut partitioning and clustering. IEEE Trans. CAD, pg. 1088-1096, Sept. 1994.
• 6: 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]
• 7: W. Donath and A. Hoffman. Lower bounds for the partitioning of graphs. IBM J. R U D, pg. 420-425, 1973.
• 8: A. E1 Gamal. Two-Dimensional Stochastic Model for Interconnections in Master Slice Integrated Circuits. IEEE Trans. on CAS, pg. 127-138, Feb. 1981.
• 9: J. Frankle and R. M. K arp. Circuit placements and cost bounds by eigenvector decomposition. IEEE ICCAD-$6, pg.. 414-417,F Santa Clara, CA, Nov 1986.
• 10: Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164910]
• 11: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 12: ~1(3):430-452~1990. . Rendl and ... Wolkowicz. A projection technique for partitioning the nodes of a graph. Tech. report, University of Waterloo, Apr. 1991.
• 13: Steven Trimberger , Mon-Ren Chene, Placement-Based Partitioning for Lookup-Table-Based FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.91-94, October 11-14, 1992
• 14: Nam Sung Woo , Jaeseok Kim, An efficient method of partitioning circuits for multiple-FPGA implementation., Proceedings of the 30th international conference on Design automation, p.202-207, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164669]

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Algorithms, Design, Experimentation, Performance, Theory