Computer readable medium and a method for representing an electronic circuit as a routing-resource graph

• US 6,738,961 B2
• Filed: 02/28/2002
• Issued: 05/18/2004
• Est. Priority Date: 02/28/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Snider, Gregory Stuart
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US10/084,383
• Publication Number:
  US 20030163796A1
• Time in Patent Office: 810 Days
• Field of Search: 716/16, 716/18, 716/13, 716/14, 713/2, 713/100, 707/101, 707/102, 709/221, 709/222, 703/16
• US Class Current: 716/128
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computer readable medium containing a computer program for representing an electronic circuit, which has been segmented into plurality blocks, as a routing-resource graph includes a first wiring data structure with first switch information and a first wire identity information to identify a first wire across a first plurality of blocks, a second wiring data structure with the first switch information and a second wire identity information to identify a second wire across a second plurality of blocks, and a first switch data structure having wire information and associated with the first and second wiring data structures for identifying a third wire connected to the first wire with a switch as a function of the first wire identity information and wire information from the first switch data structure.

Claims

1. A method for reducing apace for holding a representation of a routing network, comprising the steps of:

generating a shared data structure for representing a group of elements in the routing network;

generating a set of unshared data structures each for representing a corresponding element in the routing network that is not included in the group;

storing a set of state information into each unshared data structure such that the state information enables the shared data structure to represent all of the elements in the group.

2. The method of claim 1, wherein the step of generating a shared data structure comprises the step of generating a shared data structure for representing a group of switches in the routing network.

3. The method of claim 2, wherein the step of generating a set of unshared data structures comprises the step of generating a set of unshared data structures each for representing a corresponding wire in the routing network.

4. The method of claim 3, wherein the step of storing a set of state information into each unshared data structure comprises the step of storing a set of state information that identifies a switch location in the routing network for the corresponding wire.

5. The method of claim 2, further comprising the step of determining the group of switches by detecting a pattern of switches along a wire of the routing network.

6. The method of claim 5, wherein the step of generating a shared data structure comprises the step of generating an array of switch data structures each corresponding to a location in the pattern.

7. The method of claim 2, further comprising the step of providing a method for determining a location in the routing network for each switch in response to the shared data structure and the state information.

8. The method of claim 1, wherein the routing network pertains to a field programmable gate array.

9. The method of claim 1, further comprising the step of constructing a routing-resource graph in response to the shared and unshared data structures.

10. A computer-readable storage medium that contains a program that when executed generates a representation of a routing network by:

generating a shared data structure for representing a group of elements in the routing network;

generating a set of unshared data structures each for representing a corresponding element in the routing network that is not included in the group;

storing a set of state information into each unshared data structure such that the state information enables the shared data structure to represent all of the elements in the group.

11. The computer-readable storage medium of claim 10, wherein generating a shared data structure comprises generating a shared data structure for representing a group of switches in the routing network.

12. The computer-readable storage medium of claim 11, wherein generating a set of unshared data structures comprises generating a set of unshared data structures each for representing a corresponding wire in the routing network.

13. The computer-readable storage medium of claim 11, wherein storing a set of state information into each unshared data structure comprises storing a set of state information that identifies a switch location in the routing network for the corresponding wire.

14. The computer-readable storage medium of claim 11, further comprising determining the group of switches by detecting a pattern of switches along a wire of the routing network.

15. The computer-readable storage medium of claim 14, wherein generating a shared data structure comprises generating an array of switch data structures each corresponding to a location in the pattern.

16. The computer-readable storage medium of claim 11, further comprising determining a location in the routing network for each switch in response to the shared data structure and the state information.

17. The computer-readable storage medium of claim 10, wherein the routing network pertains to a field programmable gate array.

18. The computer-readable storage medium of claim 10, further comprising constructing a routing-resource graph in response to the shared and unshared data structures.