Method of using electronically reconfigurable logic circuits

• US 5,036,473 A
• Filed: 10/04/1989
• Issued: 07/30/1991
• Est. Priority Date: 10/05/1988
• Status: Expired due to Term

• Current Assignee: Quickturn Design Systems Incorporated (Cadence Group)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Butts, Michael R., Batcheller, Jon A.
• Primary Examiner(s): LALL, PARSHOTAM S
• Application Number:
  US07/417,196
• Time in Patent Office: 664 Days
• Field of Search: 364/488, 364/489, 364/490, 364/578, 364/491, 307/440, 307/465, 340/825.83, 340/825.86, 340/825.87, 371/23
• US Class Current: 703/23
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 30/331 with hardware acceleration, e.g. by using field programmable gate array [FPGA] or emulation
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

A plurality of electronically reconfigurable gate array (ERCGA) logic chips are interconnected via a reconfigurable interconnect, and electronic representations of large digital networks are converted to take temporary actual operating hardware form on the interconnected chips. The reconfigurable interconnect permits the digital network realized on the interconnected chips to be changed at will, making the system well suited for a variety of purposes including simulation, prototyping, execution and computing. The reconfigurable interconnect may comprise a partial crossbar that is formed of ERCGA chips dedicated to interconnection functions, wherein each such interconnect ERCGA is connected to at least one, but not all of the pins of a plurality of the logic chips. Other reconfigurable interconnect topologies are also detailed.

Claims

1. A method comprising the steps:

providing first and second electrically reconfigurable logic circuits (ERCLCs);

providing first input data representative of a first digital logic network, said input data including primitives comprised of boolean logic gates, and nets interconnecting said primitives;

automatically partitioning said first input data into first and second portions;

providing the first portion of the partitioned first data to the first ERCLC so a first portion of the first digital logic network represented thereby takes actual operating form on the first ERCLC;

providing the second portion of the partitioned first data to the second ERCLC so a second portion of the first digital logic network represented thereby takes actual operating form on the second ERCLC;

interconnecting the first and second ERCLCs so that at least one net specified in the first input data extends between the first and second ERCLCs;

providing second input data representative of a second digital logic network entirely unrelated to the first digital logic network except that both include primitives comprised of boolean logic gates, and nets interconnecting said primitives, and both are to take actual operating form on the same ERCLCs;

automatically partitioning said second input data into first and second portions;

providing the first portion of the partitioned second data to the first ERCLC so a first portion of the second digital logic network represented thereby takes actual operating form on the first ERCLC;

providing the second portion of the partitioned second data to the second ERCLC so a second portion of the second digital logic network represented thereby takes actual operating form on the second ERCLC;

interconnecting the first and second ERCLCs so that at least one net specified in the second input data extends between the first and second ERCLCs.

2. A simulation method according to claim 1 comprising the steps:

defining a first digital logic network to be simulated;

generating first input data representative of said first digital logic network;

partitioning said first input data into first and second portions;

providing the first portion of the partitioned first data to the first ERCLC so a first portion of the first digital logic network represented thereby takes actual operating form on the first ERCLC;

providing the second portion of the partitioned first data to the second ERCLC so a second portion of the first digital logic network represented thereby takes actual operating form on the second ERCLC;

interconnecting the first and second ERCLCs so that at least one net specified in the first input data extends between the first and second ERCLCs;

defining in software a set of first stimulus for use in a first simulation;

converting said first software defined stimulus into first electrical signals;

applying said first electrical signals as input to the first and second interconnected ERCLCs;

receiving first output electrical signals from the first and second interconnected ERCLCs; and

converting said first electrical output signals into software form; and

repeating the aforesaid steps for a second digital logic network different than the first.

3. A computing method according to claim 1 comprising the steps:

using a synthesis tool to convert a first computer program into a set of first input data representative of a first digital logic network that operates in accordance with an algorithm expressed by the first program;

partitioning said first input data into first and second portions;

providing the first portion of the partitioned first data to the first ERCLC so a first portion of the first digital logic network represented thereby takes actual operating form on the first ERCLC;

providing the second portion of the partitioned first data to the second ERCLC so a second portion of the first digital logic network represented thereby takes actual operating form on the second ERCLC;

interconnecting the first and second ERCLCs so that at least one net specified in the first input data extends between the first and second ERCLCs;

generating first stimulus signals, said first stimulus signals corresponding to input data for the first program;

applying said first stimulus signals as input to the first and second interconnected ERCLCs; and

receiving first output electrical signals from the first and second interconnected ERCLCs, said output signals corresponding to output data for the first program; and

repeating the aforesaid steps with a second program different than the first.

4. The method of claim 3 in which the using step comprises:

using a design synthesis tool to convert the first computer program into a representation of a system comprised of datapaths and finite-state machine controllers that operates according to an algorithm expressed by the first program; and

using a logic synthesis tool to convert the representation of datapaths and finite-state machine controllers provided by the design synthesis tool into a set of first input data.

5. The method of claim 1 in which the ERCLCs each include a plurality of pins, and in which the interconnecting steps include:

providing at least one reconfigurable interconnect; and

connecting each of said reconfigurable interconnects to at least one but not all of the pins of the first and second ERCLCs.

6. The method of claim 1 which further includes:

(a) providing N ERCLCs;

(b) partitioning the first input data into N portions;

(c) providing each portion of the partitioned data to the ERCLC to which it corresponds, so the portion of the digital logic network represented thereby takes actual operating form on said ERCLC;

(d) interconnecting the N ERCLCs so that each of the ERCLCs is connected to at least one other of the ERCLCs and so that each of the nets specified in the input data is implemented; and

(e) repeating steps (b) through (d) for the second input data.

7. The method of claim 6 in which the ERCLCs each include a plurality of pins, and in which the interconnecting steps include:

providing at least one reconfigurable interconnect; and

connecting each of said reconfigurable interconnects to at least one but not all of the pins of a plurality of said N ERCLCs.

8. The method of claim 7 which further includes:

connecting each of said reconfigurable interconnect ERCLC(s) to at least one but not all of the pins of each of said N ERCLCs.

9. The method of claim 8 which further includes:

performing in a single process, rather than seriatim, the steps of;

partitioning the input data; and

discerning a feature of the interconnects correspondingly required thereby;

whereby the input data can be partitioned in such a fashion as to simplify the correspondingly required interconnects.

10. The method of claim 9 which further includes the steps:

partitioning the input data by establishing a seed primitive and adding other primitives thereto, thereby building a cluster of primitives;

each of said primitives including a number of pins;

the building of said clusters including the step of evaluating an advantage function for each primitive unassigned to a cluster;

said advantage function including a term which gives a primitive with a greatest number of pins a greatest initial advantage.

11. The method of claim 9 which further includes the steps:

partitioning the input data by establishing a seed primitive and adding other primitives thereto, thereby building a cluster of primitives;

said partitioning step including adding primitives to a cluster beyond an interconnection limit; and

removing primitives from the cluster until the interconnection limit is met.

12. The method of claim 9 in which the interconnecting steps further include:

for a net extending between two ERCLCs;

examining a plurality of candidate reconfigurable interconnect ERCLCs through which the net may be routed; and

evaluating the suitability of routing through each such interconnect ERCLC based, at least in part, on a degree of utilization to which the ERCLC is already put.

13. The method of claim 1 which further includes:

(a) providing N ERCLCs;

(b) topologically arranging said N ERCLCs in a regular multi-dimensional array, thereby establishing relatively neighboring ERCLCs;

(c) directly interconnecting neighboring ERCLCs;

(d) partitioning the first input data into N portions;

(e) providing each portion of the partitioned data to the ERCLC to which it corresponds, so the portion of the digital logic network represented thereby takes actual operating form on said ERCLC;

(f) interconnecting the N ERCLCs as required to implement the nets specified in the first data, said interconnecting including interconnecting non-neighboring ERCLCs by establishing interconnections through ERCLCs that intervene between said non-neighboring ERCLCs; and

(g) repeating steps (d) through (f) for the second input data.

14. The method of claim 13 which further includes determining which intervening ERCLCs and pins to use to interconnect non-neighboring ERCLCs by use of an automatic routing methodology.

15. A fault simulator method according to claim 1 which further includes simulating faults by including the faults in the digital logic networks represented by the input data.

16. The method of claim 1 which further comprises operating the interconnected ERCLCs in conjunction with an electronic design automation system.

17. The method of claim 1 which further comprises coupling the interconnected ERCLCs to memory circuits and operating the interconnected ERCLCs in conjuction with said circuits.

18. The method of claim 1 which further comprises interconnecting a bidirectional net by:

converting the bidirectional net into a sum of products using a unidirectional interconnection.

19. The method of claim 1 which further includes summing products in the ERCLCs.