Date: Tue, 10 Dec 1996 03:20:31 GMT Server: NCSA/1.4.2 Content-type: text/html Multi-FPGA Systems & Rapid-Prototyping

Rapid-Prototyping & Multi-FPGA Systems


Springbok is a rapid-prototyping system for board-level designs. The idea is to extend the orders of magnitude speed increase in ASIC logic emulation achieved by systems like Quickturn to the board level. Instead of mapping all logic to FPGAs, the system includes the actual chips into the mapping. The Springbok hardware includes baseplates that can be connected to form an arbitrarily large prototyping substrate. Daughter cards, with FPGAs on one side and arbitrary devices on the other, embed the user-specified devices into an FPGA-based routing structure. Extender cards are placed between the daughter cards and the substrate to add functionality and fix resource problems.

As part of developing the Springbok system, we have examined several issues related to multi-FPGA systems. In "Mesh Routing Topologies for Multi-FPGA Systems" we have done a quantitative study of nearest-neighbor routing topologies, and developed structures that greatly improve inter-FPGA routing efficiency.

In "Pin Assignment for Multi-FPGA Systems" we examined the problems of global routing in multi-FPGA systems, and proposed an algorithm for pin assignment for arbitrary FPGA topologies. The problem is that the global routing of FPGA systems will in general occur before the mappings in individual FPGAs have been placed. This means that the exact start and finish locations for inter-FPGA signals aren't fixed, and complete routing cannot be done by standard algorithms. The process of choosing intermediate FPGAs to route through can be handled by standard algorithms, so we concern ourselves in the paper with the issue of pin assignment - choosing what exact pins the routes will use. This is handled by placing all FPGAs simultaneously via force-directed placement, though spring-simplification rules based on physical laws make the problem manageable.

We have also considered the problem of partitioning for multi-FPGA systems. Two issues have been covered. First of all, there are a huge number of techniques that have been considered for partitioning. We performed a survey of many of them, primarily those that build from the Kernighan-Lin, Fiduccia-Mattheyses bipartitioning algorithm. The results of this survey is in "An Evaluation of Bipartitioning Techniques". We also considered the problem of how to apply bipartitioning iteratively to multi-FPGA systems. Specifically, it is important to figure out what order of cuts in the logic correspond to what locations in the multi-FPGA system, so we both know how many I/O resources are available, as well as picking the best order to optimize for locality, thus minimizing the length and amount of inter-FPGA routing. This work can be found in "Logic Partition Orderings for Multi-FPGA Systems".


Springbok:

1.) A small brown and white gazelle of southern Africa, that is capable of leaping high in the air.

2.) A popular jigsaw-puzzle company.


Researchers

Faculty

o Gaetano Borriello
o Carl Ebeling

Graduate Students

o Scott Hauck

Related Work

o Triptych/Montage FPGA Architectures
Development of the Triptych and Montage FPGA architectures, architectures with improved densities over current commercial FPGAs.

Primary References

S. Hauck, G. Borriello, C. Ebeling. "Achieving High-Latency, Low-Bandwidth Communication: Logic Emulation Interfaces", submitted to IEEE Symposium on FPGAs for Custom Computing Machines, April, 1995.

S. Hauck, G. Borriello. "Pin Assignment for Multi-FPGA Systems", University of Washington, Dept. of C.S.&E. TR #94-04-01, 1994.

S. Hauck, G. Borriello. "An Evaluation of Bipartitioning Techniques", to appear in Chapel Hill Conference on Advanced Research in VLSI, March, 1995.

S. Hauck, G. Borriello. "Logic Partition Orderings for Multi-FPGA Systems", to appear in ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, CA, February, 1995.

S. Hauck, G. Borriello, C. Ebeling. "Mesh Routing Topologies for Multi-FPGA Systems", ICCD, 1994.

S. Hauck, G. Borriello, C. Ebeling. "Springbok: A Rapid-Prototyping System for Board-Level Design", FPGA'94, Berkeley, February, 1994.

Secondary References

S. Hauck, G. Borriello. "Pin Assignment for Multi-FPGA Systems (Extended Abstract)", IEEE Workshop on FPGAs for Custom Computing Machines, April, 1994.

S. Hauck, G. Borriello, C. Ebeling. "Mesh Routing Topologies for FPGA Arrays", FPGA'94, Berkeley, February, 1994.

o Arpa Test