Buffer minimization and time-multiplexed I/O on dynamically reconfigurable FPGAs

ABSTRACT

We investigate the hardware implications when combinational logic is implemented on Dynamically Reconfigurable FPGAs (DRFPGAs). We first investigate the number of communication buffers needed by a DRFPGA. These buffers are needed because the time-multiplexednature of DRFPGAs means that only a portion of the circuit implemented on the chip is present at any given time instance. Thus there is a need to store OT buffer signals until they are no longer needed. The hardware cost in a DRFPGA is the maximum number of buffers (plus associated routing) needed at any given time. We show experimentally that this number is almost as large as the number of computation nodes needed at any given time, and in some circuits twice as large. We also give a heuristic algorithm based on rescheduling nodes that reduces the number of buffers needed by 23%. Next we investigate time-multiplexed I/0 on a DRFPGA. We show that by using time-multiplexed 1/0pins, the number of physical I/0pins needed can be reduced by up to 83%.

REFERENCES

• 1: Narasimha B. Bhaqt , Kamal Chaudary , Ernest S. Kuh, Performance-Oriented Fully Routable Dynamic Architecture for a Field, University of California at Berkeley, Berkeley, CA, 1993
• 2: Jeremy Brown, Derrick Chen, et al. DELTA: Prototype for a first-generation dynamically programmable gate array. Transit Note 112, Massachusett Institute of Technology, 1995.
• 3: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 4: :J. Cong and Y. Ding. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on Computer-Aided Design, 13(1):1-12, :January 1994.
• 5: Andre DeHon. DPGA-coupled microprocessors: Commodity ICs for the early 21st century. In IEEE Workshop on FPGAs for Custom Computing Machines, pages 31-39, 1994.
• 6: André DeHon, DPGA utilization and application, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.115-121, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228387]
• 7: Hesham El-Rewini , Theodore G. Lewis , Hesham H. Ali, Task scheduling in parallel and distributed systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 8: Michael Hutton , J. P. Grossman , Jonathan Rose , Derek Corneil, Characterization and parameterized random generation of digital circuits, Proceedings of the 33rd annual conference on Design automation, p.94-99, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240537]
• 9: D. :Jones and D. M. Lewis. A time-multiplexed FPGA architecture for logic emulation. In IEEE Custom Integrated Circuits Conference, pages 24.2.1-24.2.4, 1995.
• 10: W. H. Kohler. A preliminary evaluation of the crltical path method for scheduling tasks on multiprocessot systems. IEEE Transactions on Computers, pages 1235-1238, December 1975.
• 11: E. M. $entovich, K. :J. $ingh, et al. SIS: A system for sequential circuit synthesis. Report M92/41, University of California, Berkeley, 1992.
• 12: :J. D. UUman. NP-complete scheduling problems. J. Comput. System Sci., 10:384-393, 1975.
• 13: Xilinx. The Programmable Logic Data Book, 3~d cdition, 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.6.1 Design Styles
          Subjects: Combinational logic

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Experimentation, Performance