Logic partition orderings for multi-FPGA systems

ABSTRACT

One of the critical issues for multi-FPGA systems is developing software tools for automatically mapping circuits. In this paper we consider one step in this process, partitioning. We described the task of finding partition orderings, i.e., determining the way in which a circuit should be bipartitioned so as to best map it to a multi-FPGA system. This allows multi-FPGA partitioners to harness standard partitioning techniques. We develop an algorithm for finding partition orderings, which includes a method for increasing parallelism in the process, as well as for including multi-sectioning and multi-way partitioning algorithms. This method is very efficient, and capable of handling most of the current multi-FPGA topologies.

REFERENCES

• 1: J. M. Arnold, "The Splash 2 Software Environment", FCCM, pp. 88-93, 1993.
• 2: J. Babb, R. Tessier, A. Agarwal, "Virtual Wires: Overcoming Pin Limitations in FPGA-based Logic Emulators", FCCM, pp. 142-151, 1993.
• 3: S. Bapat , J. P. Cohoon, SHARP-looking geometric partitioning, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 4: L. Barroso, S. Iman, J. Jeong, K. Oner, K. Ramamurthy, M. Dubois, "The U.S.C. Multiprocessor Testbed: Project Overview", USC CENG Technical Report CENG-94-15, August 1994.
• 5: Patrice Bertin , Didier Roncin , Jean Vuillemin, Programmable active memories: a performance assessment, Proceeding of the 1993 symposium on Research on integrated systems, p.88-102, February 1993, Seattle, Washington, United States
• 6: Thang Nguyen Bui , Byung Ro Moon, A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs, Proceedings of the 31st annual conference on Design automation, p.664-669, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196607]
• 7: Pak K. Chan , Martine Schlag , Jason Y. Zien, Spectral k-way ratio-cut partitioning and clustering, Proceeding of the 1993 symposium on Research on integrated systems, p.123-142, February 1993, Seattle, Washington, United States
• 8: P. K. Chan, M. Schlag, M. Martin, "BORG: A Reconfigurable Prototyping Board Using Field-Programmable Gate Arrays", FPGA '92, pp. 47-51, 1992.
• 9: W. E. Donath, "Logic Partitioning", in Physical Design Automation of VLSI Systems, B. Preas, M. Lorenzetti, Editors, Menlo Park, CA: Benjamin/Cummings, pp. 65-86, 1988.
• 10: A. E. Dunlop, B. W. Kernighan, "A Procedure for Placement of Standard-Cell VLSI Circuits", IEEE Trans. on CAD, Vol. CAD-4, No. 1, pp. 92-98, January 1985.
• 11: A. Ferrucci, M. Martin, T. Geocaris, M. Schlag, P. K. Chan, "ACME: A Field-Programmable Gate Array Implementation of a Self-Adapting and Scalable Connectionist Network", FPGA ' 94, 1994.
• 12: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Papers on Twenty-five years of electronic design automation, p.241-247, June 1988 [doi>10.1145/62882.62910]
• 13: Giga Operations Corporation, "G-800 VL-Bus Board", Berkeley, CA, 1994.
• 14: L. Hagen, A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD, Vol. 11, No. 9, pp. 1074-1085, September 1992.
• 15: S. Hauck, G. Borriello, C. Ebeling, "Springbok: A Rapid- Prototyping System for Board-Level Designs", FPGA'94, 1994.
• 16: S. Hauck , G. Borriello, An evaluation of bipartitioning techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.383, March 27-29, 1995
• 17: I-Cube, Inc., "The FPID Family Data Sheet", Santa Clara, CA, February 1994.
• 18: R. A. Keaney, C. H. Lee, D. J. Skellern, J. Vuillemin, M. Shand, "Implementation of Long Constraint Length Viterbi Decoders using Programmable Active Memories", Australian Microelectronics Conference, pp. 52-57, 1993.
• 19: B. W. Kernighan, S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits", Bell Systems Technical Journal, Vol. 49, No. 2, pp. 291- 307, February 1970.
• 20: Gernot Koch , Udo Kebschull , Wolfgang Rosenstiel, A prototyping environment for hardware/software codesign in the COBRA project, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 21: B. Krishnamurthy, "An Improved Min-Cut Algorithm for Partitioning VLSI Networks", IEEE Trans. on Computers, Vol. C-33, No. 5, pp. 438-446, May 1984.
• 22: D. M. Lewis, M. H. van Ierssel, D. H. Wong, "A Field Programmable Accelerator for Compiled-Code Applications", ICCD '93, pp. 491-496, 1993.
• 23: Daniel P. Lopresti, Rapid implementation of a genetic sequence comparator using field-programmable logic arrays, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.138-152, April 1991
• 24: Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196602]
• 25: Kalapi Roy , Carl Sechen, A timing driven N-way chip and multi-chip partitioner, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.240-247, November 07-11, 1993, Santa Clara, California, United States
• 26: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
• 27: P. R. Suaris, G. Kedem, "Standard Cell Placement by Quadrisection", ICCD, pp. 612-615, 1987.
• 28: Douglas A. Thomae , Thomas A. Peterson , David E. Van den Bout, The anyboard rapid prototyping environment, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.356-370, April 1991
• 29: J. Varghese, M. Butts, J. Batcheller, "An Efficient Logic Emulation System", IEEE Trans. on VLSI, Vol. 1, No. 2, pp. 171-174, June 1993.
• 30: G. Vijayan, "Partitioning Logic on Graph Structures to Minimize Routing Cost", IEEE Trans. on CAD, Vol. 9, No. 12, pp. 1326-1334, December 1990.
• 31: M. Wazlowski, L. Agarwal, T. Lee, A. Smith, E. Lam, P. Athanas, H. Silverman, S. Ghosh, "PRISM-II Compiler and Architecture", FCCM, pp. 9-16, 1993.
• 32: Y.-C. Wei, C.-K. Cheng, "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning", ICCAD, pp. 298-301, 1989.
• 33: K. Yamada, H. Nakada, A. Tsutsui, N. Ohta, "High-Speed Emulation of Communication Circuits on a Multiple-FPGA System", FPGA'94, 1994.
• 34: Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States
• 35: Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A probabilistic multicommodity-flow solution to circuit clustering problems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.428-431, November 1992, Santa Clara, California, United States
• 36: Zycad Corporation, "Paradigm RP", Fremont, CA, 1994.

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.6 LOGIC DESIGN
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing

General Terms:
Algorithms, Design, Experimentation