Patent US5854929A successfully refreshed from Google Patents.
US5854929A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of generating code for programmable processors, code generator and application thereof
Assignee: Imec
•
Filing: 1996-11-18
•
Granted: 1998-12-29
•
Expires: 2016-11-18
Abstract
Abstract The present invention concerns a method of generating code for a programmable processor and comprises several steps. The first step is representing the processor as a directed bipartite graph with first and second sets of vertices and with edges, the graph comprising essentially all information about an instruction set and hardware of the processor, the first set of vertices representing storage elements in the processor, and the second set of vertices representing operations in the processor. The second step includes linking the graph to tools and libraries required for generating code for the processor. The last step is executing the required code generation phases, whereby the required information about the processor is extracted from the graph. The present invention also concerns the application of this method.
Inventors
- 👤 Johan Roland Van Praet
- 👤 Dirk Lanneer
- 👤 Werner Gustaaf Theresia Geurts
- 👤 Gert Lodewijk Huibrecht Goossens
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 21:02
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F30/00; G06F30/30
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
113 words
A method of generating code for a programmable processor being implemented in hardware and having an instruction set, said method comprising the steps of; representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor, linking said graph to tools and libraries required for generating code for said processor, and executing the required code generation phases whereby the required information about said processor is extracted from said graph.
Claim 2
Independent Claim
113 words
A method of generating code for a programmable processor being implemented in hardware and having an instruction set, said method comprising the steps of; representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor, linking said graph to tools and libraries required for generating code for said processor, and executing the required code generation phases whereby the required information about said processor is extracted from said graph.
Claim 3
Dependent Claim
29 words
The method as defined in claim 1 wherein, said edges represent valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor.
Claim 4
Dependent Claim
112 words
The method as defined in claim 1 wherein said code generator evaluates the optimization space of generating code for an application algorithm, further comprising the step of building a decision tree with vertices and branches wherein: vertices of said decision tree represent primitive operations, whereby said application algorithm contains instances of said primitive operations; said branches represent possible transformations of said primitive operations according to alternative mapping possibilities in said optimization space, and wherein, the set of vertices of said decision tree comprises vertices representing patterns of other vertices of said set, said patterns being defined during said code generation phases, and the second set of vertices representing micro-operations of said processor.
Claim 5
Dependent Claim
67 words
The method as defined in claim 1, further comprising the steps of: representing hardware conflicts in said processor as access conflicts on said vertices representing said storage elements; and annotating each vertex of said second set of vertices representing micro-operations with an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.
Claim 6
Dependent Claim
63 words
The method as defined in claim 4 wherein, said method determines valid partial instructions, said method further comprising the steps of: selecting a subset of said second set of vertices representing micro-operations; verifying that the intersection of the enabling conditions of all micro-operations of said subset is not empty; and verifying that said subset is free of access conflicts on said storage elements.
Claim 7
Dependent Claim
42 words
The method as defined in claim 1 wherein, said storage elements are static and transitory storage elements, said method further comprising the step of representing all hardware conflicts in said processor as access conflicts on said vertices representing said transitory storage elements.
Claim 8
Dependent Claim
60 words
The method as defined in claim 1 wherein, data-types supported by a storage element are specified, said method further comprising the steps of: specifying different vertices representing one storage element; annotating each of said different vertices with a data type supported by said one storage element, and specifying an alias relationship between said different vertices representing said one storage element.
Claim 9
Dependent Claim
62 words
The method as defined in claim 1 adapted for representing record storage elements, said method further comprising the steps of: specifying a vertex representing the concatenation of several storage elements; annotating said vertex with a data type being a record of the data types of said storage elements; specifying a structural relationship between said vertex and the vertices representing said storage elements.
Claim 10
Dependent Claim
111 words
The method as defined in claim 1, adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of: specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition; specifying in said subset a vertex; specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition has a specific value.
Claim 11
Dependent Claim
74 words
The method as defined in claim 4 wherein, execution times of micro-operations are modeled, said method further comprising the steps of: annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said micro-operation; annotating said operation with the time steps relative to the start of said micro-operation at which said operation accesses the input and output storage elements of said micro-operation.
Claim 12
Dependent Claim
46 words
The method as defined in claim 1 wherein, said method represents a functional unit in said processor, said method further comprising the steps of specifying a subset of said second set of vertices representing operations wherein, all vertices in said subset execute on said functional unit.
Claim 13
Dependent Claim
32 words
The method as defined in claim 1 wherein, said processor includes a controller unit, and micro-operations modeling said controller unit are represented as vertices of said second set of vertices representing micro-operations.
Claim 14
Dependent Claim
29 words
The method as defined in claim 1 wherein, said processor has an architecture and instruction set designed for a specific class of algorithms such as digital signal processing algorithms.
Claim 15
Dependent Claim
17 words
The method as defined in claim 13 wherein, said processor is integrated in an application-specific integrated circuit.
Claim 16
Dependent Claim
140 words
A retargetable code generator for generating code for programmable processors being embedded in an electronic system comprising: an electronic system with an embedded programmable processor, first tools to build a directed bipartite graph with vertices and edges which internally represents said programmable processor, said graph comprising essentially all information about the instruction set and the hardware of said processor and having first and second sets of vertices, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor, said edges represent valid connections between said micro-operations and said storage elements, second tools and libraries required to generate code for said processor, and means to link said graph to said second tools and said libraries, whereby the information about said processor required during code generation is extracted from said graph.
Claim 17
Dependent Claim
140 words
A retargetable code generator for generating code for programmable processors being embedded in an electronic system comprising: an electronic system with an embedded programmable processor, first tools to build a directed bipartite graph with vertices and edges which internally represents said programmable processor, said graph comprising essentially all information about the instruction set and the hardware of said processor and having first and second sets of vertices, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor, said edges represent valid connections between said micro-operations and said storage elements, second tools and libraries required to generate code for said processor, and means to link said graph to said second tools and said libraries, whereby the information about said processor required during code generation is extracted from said graph.
Claim 18
Dependent Claim
68 words
A retargetable code generator as defined in claim 15 wherein said first tools: represent hardware conflicts in said processor as access conflicts on said vertices representing said storage elements; and annotate each vertex of said second set of vertices representing micro-operations with their enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the operation represented by said vertex.
Claim 19
Dependent Claim
60 words
A retargetable code generator as defined in claim 16 wherein said second tools determine valid partial instructions by; selecting a subset of said second set of vertices representing micro-operations; verifying that the intersection of the enabling conditions of all micro-operations of said subset is not empty; and verifying that said subset is free of access conflicts on said storage elements.
Claim 20
Independent Claim
130 words
A method of simulating the execution of code on a programmable processor, being implemented in hardware and having an instruction set, said method comprising the steps of: representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, said second set of vertices representing micro-operations in said processor; said edges representing valid connections between micro-operations and said storage elements, and said connections modeling the data flow in said processor, linking said graph to tools and libraries requited for said simulation, and executing said simulation whereby the required information about said processor is extracted from said graph.
Claim 21
Independent Claim
130 words
A method of simulating the execution of code on a programmable processor, being implemented in hardware and having an instruction set, said method comprising the steps of: representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, said second set of vertices representing micro-operations in said processor; said edges representing valid connections between micro-operations and said storage elements, and said connections modeling the data flow in said processor, linking said graph to tools and libraries requited for said simulation, and executing said simulation whereby the required information about said processor is extracted from said graph.
Claim 22
Dependent Claim
27 words
The method as defined in claim 18 further comprising the step of representing hardware conflicts in said processor as access conflicts on said vertices representing storage elements.
Claim 23
Dependent Claim
38 words
The method as defined in claim 18 wherein, said storage elements are static and transitory storage elements and wherein all hardware conflicts in said processor are represented as access conflicts on said vertices representing said transitory storage elements.
Claim 24
Dependent Claim
47 words
The method as defined in claim 18 wherein, each vertex of said second set of vertices representing s is annotated wit an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.
Claim 25
Dependent Claim
60 words
The method as defined in claim 18 wherein data-types supported by a storage element are specified, said method further comprising the steps of: specifying different vertices representing one storage element; annotating each of said different vertices with a data type supported by said one storage element, and specifying an alias relationship between said different vertices representing said one storage element.
Claim 26
Dependent Claim
62 words
The method as defined in claim 18 adapted for representing record storage elements, said method further comprising the steps of: specifying a vertex representing the concatenation of several storage elements; annotating said vertex with a data type being a record of the data types of said storage elements; specifying a structural relationship between said vertex and the vertices representing said storage elements.
Claim 27
Dependent Claim
111 words
The method as defined in claim 18 adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of: specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition; specifying in said subset a vertex; specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition bas a specific value.
Claim 28
Dependent Claim
75 words
The method as defined in claim 18 wherein, the execution times of micro-operations are modeled, said method further comprising the steps of: annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said operation; annotating said micro-operation with the time steps relative to the start of said micro-operation at which said micro-operation accesses the input and output storage elements of said micro-operation.
Claim 29
Dependent Claim
48 words
The method as defined in claim 18 wherein, said method represents a functional unit in said processor, said method further comprising the step of specifying a subset of said second set of vertices representing micro-operations characterized in that all vertices in said subset execute on said functional unit.
Claim 30
Dependent Claim
30 words
The method as defined in claim 18 wherein said processor includes a controller unit, and said controller unit are represented as vertices of said second set of vertices representing micro-operations.
Claim 31
Dependent Claim
128 words
A retargetable simulator that performs the simulation of the execution of code on a programmable processor being embedded in an electronic system comprising: an electronic system with an embedded programmable processor, first tools to build a directed bipartite graph which internally represents said programmable processor with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor; second tools and libraries required for simulating said processor, and means to link said graph to said second tools and libraries whereby the information about said processor required during simulation is extracted from said graph.
Claim 32
Dependent Claim
128 words
A retargetable simulator that performs the simulation of the execution of code on a programmable processor being embedded in an electronic system comprising: an electronic system with an embedded programmable processor, first tools to build a directed bipartite graph which internally represents said programmable processor with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor; second tools and libraries required for simulating said processor, and means to link said graph to said second tools and libraries whereby the information about said processor required during simulation is extracted from said graph.
Claim 33
Independent Claim
118 words
A method of synthesizing a programmable processor being implemented in hardware, comprising the steps of: representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor; said second set of vertices representing micro-operations in said processor; said edges representing valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor; linking said graph to tools and libraries required for generating a netlist of hardware building blocks; implementing said processor as a hardware device according to said netlist.
Claim 34
Independent Claim
118 words
A method of synthesizing a programmable processor being implemented in hardware, comprising the steps of: representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor; said second set of vertices representing micro-operations in said processor; said edges representing valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor; linking said graph to tools and libraries required for generating a netlist of hardware building blocks; implementing said processor as a hardware device according to said netlist.
Claim 35
Independent Claim
97 words
A method of modeling a programmable processor being implemented in hardware adapted for use in an automatic retargetable code generator and in an instruction set simulator, said method comprising the steps of: identifying storage elements and micro-operations in said processor; and representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor.
Claim 36
Independent Claim
97 words
A method of modeling a programmable processor being implemented in hardware adapted for use in an automatic retargetable code generator and in an instruction set simulator, said method comprising the steps of: identifying storage elements and micro-operations in said processor; and representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor.
Claim 37
Dependent Claim
29 words
The method as defined in claim 30, wherein said edges represent valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor.
Claim 38
Dependent Claim
44 words
The method as defined in claim 30, further comprising the step of constructing said graph, said constructing step including the further steps of: parsing a textual specification of said processor described in a high-level language; and transforming said parsed textual specification into said graph.
Claim 39
Dependent Claim
17 words
The method as defined in claim 32, wherein said high-level language is an nML processor description language.
Claim 40
Dependent Claim
47 words
The method as defined in claim 30, wherein each vertex of said second set of vertices representing -operations is annotated with an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.
Claim 41
Dependent Claim
27 words
The method as defined in claim 30, further comprising the step of representing hardware conflicts in said processor as access conflicts on said vertices representing storage elements.
Claim 42
Dependent Claim
42 words
The method as defined in claim 30, wherein said storage elements are static and transitory storage elements, said method further comprising the step of representing all hardware conflicts in said processor as access conflicts on said vertices representing said transitory storage elements.
Claim 43
Dependent Claim
60 words
The method as defined in claim 30, wherein data types supported by a storage element are specified, said method further comprising the steps of: specifying different vertices representing one storage element; annotating each of said different vertices with a data type supported by said one storage element; and specifying an alias relationship between said different vertices representing said storage element.
Claim 44
Dependent Claim
63 words
The method as defined in claim 30, adapted for representing record storage elements, said method further comprising the steps of: specifying a vertex representing the concatenation of several storage elements; annotating said vertex with a data type being a record of the data types of said storage elements; and specifying a structural relationship between said vertex and the vertices representing said storage elements.
Claim 45
Dependent Claim
111 words
The method as defined in claim 30, adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of: specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition; specifying in said subset a vertex; specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition has a specific value.
Claim 46
Dependent Claim
75 words
The method as defined in claim 30, wherein execution times of micro-operations are modeled, said method further comprising the steps of annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said micro-operation; and annotating said micro-operation with the time steps relative to the start of said micro-operation at which said micro-operation accesses the input and output storage elements of said micro-operation.
Claim 47
Dependent Claim
46 words
The method as defined in claim 30, wherein said method represents a functional unit in said processor, said method further comprising the steps of specifying a subset of said second set of vertices representing micro-operations, wherein all vertices in said subset execute on said functional unit.
Claim 48
Dependent Claim
33 words
The method as defined in claim 30, wherein said processor includes a controller unit, and micro -operations modeling said controller unit are represented as vertices of said second set of vertices representing micro-operations.
Claim 49
Dependent Claim
29 words
The method as defined in claim 30, wherein said processor has an architecture and instruction set designed for a specific class of algorithms such as digital signal processing algorithms.
Claim 50
Dependent Claim
17 words
The method as defined in claim 30, wherein said processor is integrated in an application-specific integrated circuit.
References Cited (Backward Citations)
US5163016A
Cited
US5168441A
Cited
US5522063A
Cited
US5568396A
Cited
US5513122A
Cited
US5568636A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-28 | 2002-06-29 | 2002-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-28 | 2006-06-29 | 2006-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-28 | 2010-06-29 | 2010-12-29 | $7700.00 | Window Closed / Lapsed |