US5519627A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Datapath synthesis method and apparatus utilizing a structured cell library
Assignee: NXP BV
•
Filing: 1994-11-15
•
Granted: 1996-05-21
•
Expires: 2014-11-15
Abstract
Abstract A datapath circuit synthesizer converts an HDL circuit specification into a circuit netlist. The behavioral description of the specified circuit is divided into two distinct parts: datapath logic and control logic. The control logic is implemented in standard cells or gate arrays using a logic synthesizer. The datapath logic is optimally synthesized using a datapath synthesizer having a library of datapath elements, including both structural components and computational components, where some of the computational components are complex circuits having multiple, parallel outputs. Each computational component has associated therewith a set of one or more datapath expressions performed thereby. The received HDL circuit specification is converted into circuit data structures representing the circuit's datapath expressions and structural components. The datapath synthesizer locates all datapath elements in said library matching each such datapath expression and structural component. Then an optimizer determines which datapath expressions can be "combined", or performed by a single library element, so as to reduce the circuit layout area used. The optimizer can combine multiple datapath expressions so as to use datapath circuit elements having multiple parallel outputs. Finally, one library element is selected for each datapath expression, or combined expression, on the basis of circuit area, speed, power or other optimization criteria. Then the connections between the selected circuit components are computed and the resulting circuit is output in the form of a circuit netlist.
Inventors
- 👤 Mossaddeq Mahmood
- 👤 Balmukund K. Sharma
- 👤 Christopher H. Kingsley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 13:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
320 words
A method executed by a computer under the control of a program, said computer including a memory for storing said program, said method comprising the steps of: receiving in said computer a hardware description language description of an electronic circuit, said hardware description language description of said electronic circuit including circuit element descriptions and circuit connection descriptions, said circuit element descriptions defining datapath functions performed by said electronic circuit; storing in said memory a library with a plurality of hardware description language datapath library elements that perform specified datapath operations; parsing said circuit element descriptions of said hardware description language description of said electronic circuit into circuit element intermediate register transfer level (RTL) descriptions, each of said circuit element intermediate RTL descriptions including a first list of pointers to data structures with multiple input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, and said hardware description language datapath library elements into datapath library element intermediate RTL descriptions, each of said datapath library element intermediate RTL descriptions including a first list of pointers to data structures representing input and output ports and a second list of pointers to data structures representing logical or mathematical expressions; transforming each of said circuit element intermediate RTL descriptions into a corresponding circuit element directed acyclic graph, thereby generating a set of circuit element directed acyclic graphs, each of said dampath library element intermediate RTL descriptions into a corresponding datapath library element directed acyclic graph, thereby generating a set of datapath library element directed acyclic graphs; synthesizing a datapath structure representing said electronic circuit, said synthesizing step including the step of matching said circuit element directed acyclic graphs with said datapath library element directed acyclic graphs to identify matched datapath library elements which perform said datapath functions defined by said circuit element descriptions; and generating a netlist of circuit elements selected from said matched datapath library elements.
Claim 2
Independent Claim
320 words
A method executed by a computer under the control of a program, said computer including a memory for storing said program, said method comprising the steps of: receiving in said computer a hardware description language description of an electronic circuit, said hardware description language description of said electronic circuit including circuit element descriptions and circuit connection descriptions, said circuit element descriptions defining datapath functions performed by said electronic circuit; storing in said memory a library with a plurality of hardware description language datapath library elements that perform specified datapath operations; parsing said circuit element descriptions of said hardware description language description of said electronic circuit into circuit element intermediate register transfer level (RTL) descriptions, each of said circuit element intermediate RTL descriptions including a first list of pointers to data structures with multiple input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, and said hardware description language datapath library elements into datapath library element intermediate RTL descriptions, each of said datapath library element intermediate RTL descriptions including a first list of pointers to data structures representing input and output ports and a second list of pointers to data structures representing logical or mathematical expressions; transforming each of said circuit element intermediate RTL descriptions into a corresponding circuit element directed acyclic graph, thereby generating a set of circuit element directed acyclic graphs, each of said dampath library element intermediate RTL descriptions into a corresponding datapath library element directed acyclic graph, thereby generating a set of datapath library element directed acyclic graphs; synthesizing a datapath structure representing said electronic circuit, said synthesizing step including the step of matching said circuit element directed acyclic graphs with said datapath library element directed acyclic graphs to identify matched datapath library elements which perform said datapath functions defined by said circuit element descriptions; and generating a netlist of circuit elements selected from said matched datapath library elements.
Claim 3
Dependent Claim
72 words
The method of claim 1 wherein said matching step includes the steps of identifying a circuit element directed acyclic graph that cannot be matched with said datapath library element directed acyclic graphs and thereby forms an unmatched directed acyclic graph; transforming said unmatched directed acyclic graph into an algebraically equivalent substitute directed acyclic graph; and matching said algebraically equivalent substitute directed acyclic graph with a corresponding dampath library element directed acyclic graph.
Claim 4
Dependent Claim
79 words
The method of claim 1 wherein said synthesizing step includes the steps of: receiving a spacial area value associated with each of several predefined multiplexers having different numbers of ports; representing multiplexers utilized in said synthesized datapath structure; and transforming a multiple port multiplexer into an equivalent tree structure of multiplexers in said synthesized datapath structure, said tree structure of multiplexers having an associated circuit layout area which is smaller than said multiple port multiplexer's associated circuit layout area.
Claim 5
Dependent Claim
51 words
The method of claim 1 further including the step of merging selected ones of said circuit element descriptions defining said datapath functions into combined functions in accordance with predefined optimization criteria, wherein each combined function is performed by at least one of said plurality of hardware description language datapath library elements.
Claim 6
Dependent Claim
29 words
The method of claim 4 wherein said merging step includes the step of merging single output datapath functions defined by said circuit element descriptions into multiple output datapath functions.
Claim 7
Dependent Claim
300 words
A computer readable memory that can be used to direct a computer to function in a specified manner, comprising: circuit data stored in said memory, said circuit data including: a hardware description language description of an electronic circuit, said hardware description language description of said electronic circuit including circuit element descriptions and circuit connection descriptions, and a library of hardware description language dampath circuit elements that perform specified datapath operations; and executable instructions stored in said memory, said executable instructions including: instructions to parse said circuit element descriptions of said hardware description language of said electronic circuit into circuit element intermediate register transfer level (RTL) descriptions, each of said circuit element intermediate RTL descriptions including a first list of pointers to data structures with multiple input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, instructions to parse said hardware description language datapath circuit elements into datapath library element intermediate RTL descriptions, each of said datapath library element intermediate RTL descriptions including a first list of pointers to data structures representing input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, instructions to transform each of said circuit element intermediate RTL descriptions into a corresponding circuit element directed acyclic graph, thereby generating a set of circuit element directed acyclic graphs, instructions to transform each of said datapath library element intermediate RTL descriptions into a corresponding datapath library element directed acyclic graph, thereby generating a set of datapath library element directed acyclic graphs, instructions to match said circuit element directed acyclic graphs with said datapath library element directed acyclic graphs to produce matched datapath library elements, and instructions to synthesize a datapath circuit netlist having datapath library elements corresponding to said matched datapath library elements.
Claim 8
Dependent Claim
300 words
A computer readable memory that can be used to direct a computer to function in a specified manner, comprising: circuit data stored in said memory, said circuit data including: a hardware description language description of an electronic circuit, said hardware description language description of said electronic circuit including circuit element descriptions and circuit connection descriptions, and a library of hardware description language dampath circuit elements that perform specified datapath operations; and executable instructions stored in said memory, said executable instructions including: instructions to parse said circuit element descriptions of said hardware description language of said electronic circuit into circuit element intermediate register transfer level (RTL) descriptions, each of said circuit element intermediate RTL descriptions including a first list of pointers to data structures with multiple input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, instructions to parse said hardware description language datapath circuit elements into datapath library element intermediate RTL descriptions, each of said datapath library element intermediate RTL descriptions including a first list of pointers to data structures representing input and output ports and a second list of pointers to data structures representing logical or mathematical expressions, instructions to transform each of said circuit element intermediate RTL descriptions into a corresponding circuit element directed acyclic graph, thereby generating a set of circuit element directed acyclic graphs, instructions to transform each of said datapath library element intermediate RTL descriptions into a corresponding datapath library element directed acyclic graph, thereby generating a set of datapath library element directed acyclic graphs, instructions to match said circuit element directed acyclic graphs with said datapath library element directed acyclic graphs to produce matched datapath library elements, and instructions to synthesize a datapath circuit netlist having datapath library elements corresponding to said matched datapath library elements.
References Cited (Backward Citations)
US4703435A
Cited
US4831543A
Cited
US5150308A
Cited
US5267175A
Cited
US5212650A
Cited
US5257201A
Cited
US4870598A
Cited
US5146583A
Cited
US5197016A
Cited
US4922432A
Cited
US5005136A
Cited
US5003487A
Cited
US5222030A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-21 | 1999-11-20 | 2000-05-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-21 | 2003-11-20 | 2004-05-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-21 | 2007-11-20 | 2008-05-21 | $7700.00 | Window Closed / Lapsed |