Virtual interconnections for reconfigurable logic systems

Details Virtual interconnections for reconfigurable logic systems Virtual interconnections for reconfigurable logic systems

1995-09-28

1998-06-02

Louis-Jacques, Jacques

Boots, shoes, and leggings

364488, 364489, G06F 1750

Patent

active

057614849

DESCRIPTION:

BRIEF SUMMARY
RELATED APPLICATIONS

This application is the U.S. National phase of International Application No. PCT/US94/03620, filed Apr. 1, 1994 which claimed priority to U.S. Ser. No. 08/042,151, filed Apr. 2, 1993, now U.S. Pat. No. 5,596,742; the teachings of which are incorporated herein by reference in their entirety.


BACKGROUND OF THE INVENTION

Field Programmable Gate Array (FPGA) based logic emulators are capable of emulating complex logic designs at clock speeds four to six orders of magnitude faster than even an accelerated software simulator. Once configured, an FPGA-based emulator is a heterogeneous network of special purpose processors, each FPGA processor being specifically designed to cooperatively execute a partition of the overall simulated circuit. As parallel processors, these emulators are characterized by their interconnection topology (network), target FPGA (processor), and supporting software (compiler). The interconnection topology describes the arrangement of FPGA devices and routing resources (i.e. full crossbar, two dimension mesh, etc). Important target FPGA properties include gate count (computational resources), pin count (communication resources), and mapping efficiency. Supporting software is extensive, combining netlist translators, logic optimizers, technology mappers, global and FPGA-specific partitioners, placers, and routers.
FPGA-based logic emulation systems have been developed for design complexity ranging from several thousand to several million gates. Typically, the software for these system is considered the most complex component. Emulation systems have been developed that interconnect FPGAs in a two-dimensional mesh and in a partial crossbar topology. In addition, a hierarchical approach to interconnection has been developed. Another approach uses a combination of nearest neighbor and crossbar interconnections. Logic partitions are typically hardwired to FPGAs following partition placement.
Statically routed networks can be used whenever communication can be predetermined. Static refers to the fact that all data movement can be determined and optimized at compile-time. This mechanism has been used in scheduling real-time communication in a multiprocessor environment. Other related uses of static routing include FPGA-based systolic arrays and in the very large simulation subsystem (VLSS), a massively parallel simulation engine which uses time-division multiplexing to stagger logic evaluation.
In prior systems, circuit switching techniques are used to provide output signals from one chip to another chip. A given output pin of one chip can be directly connected to a given input pin of another chip or provided during a dedicated time slot over a bus. The entire path of the signal through the bus is dedicated, using assigned bus pins and time slots to provide a direct connection during any time slot. A full resource is thus used to transmit the signal from the output chip to the input chip. An example of such a prior art system is discussed in Van Den Bout, AnyBoard: An FPGA-Based Reconfigurable System, IEEE Design and Test of Computers (Sept. 1992), pps. 21-30.


SUMMARY OF THE INVENTION

Existing FPGA-based logic emulators suffer from limited inter-chip communication bandwidth, resulting in low gate utilization (10 to 20 percent). This resource imbalance increases the number of chips needed to emulate a particular logic design and thereby decreases emulation speed, because signals must cross more chip boundaries, and increases system cost. Prior art emulators only use a fraction of potential communication bandwidth because the prior art emulators dedicate each FPGA pin (physical wire) to a single emulated signal (logical wire). These logical wires are not active simultaneously and are only switched at emulation clock speeds.
A preferred embodiment of the invention presents a compilation technique to overcome device pin limitations using virtual interconnections. This method can be applied to any topology and FPGA device, although some benefit substantially more than others.

REFERENCES:
patent: 4495590 (1985-01-01), Mitchell, Jr.
patent: 4506341 (1985-03-01), Kalter et al.
patent: 4697241 (1987-09-01), Lavi
patent: 4901259 (1990-02-01), Watkins
patent: 5109353 (1992-04-01), Sample et al.
patent: 5283900 (1994-02-01), Frankel et al.
patent: 5442306 (1995-08-01), Woo
patent: 5444394 (1995-08-01), Watson et al.
patent: 5452231 (1995-09-01), Butts et al.
patent: 5473266 (1995-12-01), Ahanin et al.
patent: 5475830 (1995-12-01), Chen et al.
patent: 5483178 (1996-01-01), Costello et al.
patent: 5485103 (1996-01-01), Pedersen et al.
patent: 5513338 (1996-04-01), Alexander et al.
patent: 5572710 (1996-11-01), Asano et al.
patent: 5596742 (1997-01-01), Agrawal et al.
Murgai et al., "Logic Synthesis for Programmable Gate Arrays," IEEE 27th ACM/IEEE Design Automation Conference, (1990) pp. 620-625.
Singh et al, "Optimization of Field-Programmable Gate Array Logic Block Architecture for Speed," IEEE 1991 Custom Integrated Circuits Conference, (1991), pp. 6.1.1-6.1.6.
Witienberg, R.C., "Three Newcomers Stir Up Hardware Accelerator Market, " Electronic Design, Dec. 29, 1986, pp. 22-23.
Bursky, D., "Fast simulator expands to mimic 4 million gates," Electronic Design, pp. 1-5, (Dec. 1986).
Lavi, Y., "The Supersim--An Ultrafast Hardware Logic Simulator," IFIP Workshop on CAD Engines, Tokyo (Jun. 6-9, 1987). No Page #s.
Bertsekas, D., et al., Data Networks, pp. 8-14, 91-95 and 403-405 (Prentice Hall 1987).
Rose, J., et al., "Architecture of Field-Programmable Gate Arrays: The Effect of Logic Block Functionality on Area Efficiency," IEEE Journal of Solid State Circuits, No. 5, (Oct. 1990), pp. 1217-1225.
Babb, J., et al., "Virtual Wires: Overcoming Pin Limitations in FPGA-based Logic Emulators," Proceedings IEEE Workshop on FPGAs for Custom Computing Machines, (Apr. 5, 1993), pp. 142-151.
Hey, A., "Supercomputing with Transputers--Past, Present and Future," Computer Architecture News, vol. 18, No. 3, (Sep. 1990), pp. 479-489.
Agrawal, O., "Filed Programmable Gate Arrays (FPGAs) Provide ASIC System Designers Control of Their Design Destiny," Electro Conference Record, vol. 15, (May 1990), pp. 353-161.
Van Den Bout, D.E., et al., AnyBoard: An FPGA-Based Reconfigurable System IEEE Computer Society, (Sep. 1992), pp. 21-30.
XILINX: The Programmable Gate Array Design Handbook, (1986), pp. 1-9 to 1-14.
Wei, Yen-Chuen, et al., "Multiple-Level Partitioning: An Application to the Very Large-Scale Hardware Simulator," IEEE, vol. 26, No. 5, (May 1991), pp. 706-716.
Dally, "Virtual-Channel Flow Control," IEEE Transactions on Parallel and Distributed Systems, vol. 3, No. 2 (Mar. 1992), pp. 194-205.
Bursky, "Using Antifuse Programming For Gate-Arrayed Density and Flexibility, An FPGAs Family Also Delivers Masked-Array Performance. FPGAs Mirror Masked Gate-Array Architecture," Electronic Design, (Nov. 21, 1991), pp. 63-70.
Kermani et al., "Virtual Cut-Through: A New Computer Communication Switching Technique," Computer Networks, vol. 3, (Oct. 1979), pp. 267-286.
Khan, et al., "FPGA Architectures for ASIC Hardware Emulators," 1993 ASIC Conference and Exhibit, pp. 336-340.
Walters, "Reprogrammable Hardware Emulation for ASICs Makes Thorough Design Verification Practical," Compcon Spring '90, pp. 484-486.
Deiss, Stephen, R., "Connectionism without the Connections," IEEE, (1984), pp. 1217-1221.
Dominguez-Castro, R., et al., "Architectures and Building Blocks for CMOS VLSI Analog Neural Programmable Optimizers," IEEE, (1992), pp. 1525-1528.
Fornaciari, William, et al., "An Automatic VLSI Implementation of Hopfield ANNs," IEEE, (1995), pp. 499-502.
Bailey, Jim, et al., "Why VLSI Implementations of Associative VLCNs Require Connection Multiplexing," pp. II-173-II-180. No Date.

Affiliated with

Also associated with

Rating

Virtual interconnections for reconfigurable logic systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Virtual interconnections for reconfigurable logic systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual interconnections for reconfigurable logic systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1472355