I/O placement for FPGAs with multiple I/O standards

ABSTRACT

In this paper, we present the first exact algorithm to solve the constrained I/O placement problem for FPGAs that support multiple I/O standards. We derive a compact integer linear programming formulation for the constrained I/O placement problem. The size of the integer linear program derived is independent of the number of I/O objects to be placed and hence is scalable to very large design instances. For example, for a Xilinx Virtex-E FPGA, the number of integer variables required is never more than 32 and is much smaller for practical design instances. Extensive experimental results using a non-commercial integer linear program solver shows that it only takes seconds to solve the resultant integer linear program in practice.

REFERENCES

• 1: Altera Corp., "Using Selectable I/O Standards in APEX 20KE, APEX 20KC & MAX 7000B Devices", Application Note 117, Dec. 2001.
• 2: Jason Helge Anderson , Jim Saunders , Sudip Nag , Chari Madabhushi , Rajeev Jayaraman, A Placement Algorithm for FPGA Designs with Multiple I/O Standards, Proceedings of the The Roadmap to Reconfigurable Computing, 10th International Workshop on Field-Programmable Logic and Applications, p.211-220, August 27-30, 2000
• 3: M. Berkelaar, lp_solve, available by anonymous ftp from ftp://ftp.es.ele.tue.nl/pub/lp_solve.
• 4: G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, N.J., 1963.
• 5: Hamdy A. Taha, Operations research: an introduction, 4th ed., Macmillan Publishing Co., Inc., Indianapolis, IN, 1987
• 6: Xilinx Inc., "Virtex™ 2.5V Field Programmable Gate Arrays", Product Data Sheet, July 2002.
• 7: Xilinx Inc., "Virtex™-E 1.8V Field Programmable Gate Arrays", Product Data Sheet, July 2002.
• 8: Xilinx Inc., "Virtex-II 1.5V Field Programmable Gate Arrays", Advance Product Specification, July 2002.
• 9: Xilinx Inc., "Virtex-II Pro Field Programmable Gate Arrays", Advance Product Specification, June 2002.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms

Keywords:
I/O placement, I/O standards, field-programmable gate array, placement