Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-12-05
2001-05-22
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06237125
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a high-level synthesis method for synthesizing a logic circuit from an operation string expressing an operation specification, and more particularly to a high-level synthesis method including a processing for optimizing the arithmetic sequence of an operation string.
2. Description of the Related Art
Procedure of synthesizing a logic circuit from operation specification conventionally employed (The High-level Synthesis of Digital System: MICHAEL C. McFARLAND, ALICE C. PARKER, PAUL CAMPOSANO: Proceeding of the IEEE, Vol. 78, No.2, 1990) is shown in FIG.
1
.
According to the conventional procedure, an operation string is first extracted from the operation specification (Steps S
101
and S
103
), scheduling is performed (Step S
105
) for the extracted operation string, hardware location (Step S
107
) is executed thereby roughly adapting a logic circuit, and finally a logic synthesis (Step S
109
) is performed in which circuit elements are allocated to the operation based on the results of the hardware allocation. Here, the Step S
101
to Step S
107
are the processing called “High-Level Synthesis.”
By the scheduling in the Step S
105
, the corresponding relation between the operations and the duration of use of each arithmetic unit is determined so as to quicken the execution of the operation string under the restricted number of the arithmetic units which can be used simultaneously. For example, if the operation string extracted in the Step S
103
is Z=H+((E+F)+(A−B+C+D+)+G)−I, then a logic circuit as shown in
FIG. 2
was synthesized by the conventional procedure.
However, in the conventional High-level Synthesis, the linkage with the allocation of circuit elements are not considered sufficiently in the scheduling, and the optimization of the operation string is not performed even though the allocation of the circuit elements can be performed to the optimum in some cases by replacing the arithmetic sequence of the operation string. Because of this, there are shortcomings such as the scale of synthesized logic circuit is too large or the processing speed is not high.
Also, the scheduling is performed only based on the restricted number of the arithmetic units that can be used; and scheduling based on the information of initial circuit construction such as connecting relations between the arithmetic units is not performed. Because of this, the optimization of the operation string suited to the initial circuit construction has not been a performed and thus the conventional procedure has shortcomings of unutilizing the execution performance based on the initial circuit construction.
SUMMARY OF THE INVENTION
The present invention is conceived to overcome the conventional problems stated above and its object is to provide a high-level synthesis method capable of synthesizing a small-scale logic circuit having a high processing speed by performing the optimization of extracted operation string before scheduling after extracting the operation string. In a case where the information of the initial circuit construction is given, another object is to provide a high-level synthesis method capable of enhancing the execution performance based on the initial circuit construction by performing the optimization of the operation string suited to the initial circuit construction.
To achieve the objects stated above, there is provided a high-level synthesis method for synthesizing a logic circuit by optimizing the arithmetic sequence of an operation string expressing an operation specification, the high-level synthesis method comprising: a step of analyzing the operation string expressing the operation specification based on coupling rules of operations and a dependent relation of data and extracting a dependent relation of operations, a step of preparing conversion rules applicable to the dependent relation of operations as new conversion rules out of basic conversion rules of operation order, a step of optimizing the dependent relation of operations by applying the prepared new conversion rules to the dependent relation of operations, and a step of preparing an optimized operation string from the optimized dependent relation of operations.
In a preferred embodiment of the present invention, the basic conversion rules are conversion rules for operation order of four fundamental rules of arithmetics, the conversion rules including at least a conversion rule from A+B to B+A, a conversion rule from A+B−C to A−C+B, and a conversion rule from A+(B+C) to A+B+C.
In a preferred embodiment of the present invention, the step of preparing the new conversion rules prepares arithmetic rules which at least do not increase the number of operation stages out of the fundamental arithmetic rules as the new arithmetic rules.
According to the present invention, the operation order is unified, so that the construction of the logic circuit synthesized can be simplified. Also, a dependent relation of operations which was in serial construction is changed to a timber construction, the processing speed of the operation can be improved. As a result, the scale of synthesized logic circuit is reduced and the processing speed is increased.
To achieve the objects stated above, there is provided a high-level synthesis method for synthesizing a logic circuit by optimizing the arithmetic sequence of an operation string expressing an operation specification, the high-level synthesis method comprising: a step of analyzing the operation string expressing the operation specification based on coupling rules of operations and a dependent relation of data and extracting a first dependent relation of operations, a step of extracting, from an initial circuit construction of a logic circuit executing the operation string, connecting relations between arithmetic units constituting the initial circuit construction, a step of creating a second dependent relation of operations from the extracted connecting relations between the arithmetic units, a step of applying basic conversion rules for operation order to the second dependent relation of operations to prepare new conversion rules, a step of applying the new conversion rules to the second dependent relation of operations to optimize the second dependent relation of operations, and a step of preparing an optimized operation string from the second optimized dependent relation of operations.
In a preferred embodiment of the present invention, the initial circuit construction has an output of a first adder to which a second adder and a subtracter are connected in parallel, registers being connected to outputs of the second adder and the subtracter respectively, outputs of the registers being connected to two inputs of the first adder respectively; the connecting relations between the arithmetic units being a connecting relation between the first adder and the second adder and a connecting relation between the first adder and the subtracter; the basic conversion rules including at least a conversion rule from A+B to B+A, a conversion rule from A+B−C to A−C+B, and conversion rule from A+(B+C) to A+B+C; and the new conversion rules including at least a conversion rule from A+B+C to A+(B+C), a conversion rule from B+A+C to A+(B+C), a conversion rule from B+C+A to A+(B+C), a conversion rule from B+A−C to A+B−C, a conversion rule from A−C+B to A+B−C, and a conversion rule from B+(A−C) to A+B−C.
According to the present invention, the operation order is optimized so as to suit to the initial circuit construction, and therefore the improvement of execution performance based on the initial circuit construction and the synthesis of logic circuit along the initial circuit construction can be performed.
The nature, principle and utility of
Masuda Atsushi
Shigeta Yoshinori
Foley & Lardner
Kabushiki Kaisha Toshiba
Siek Vuthe
Smith Matthew
LandOfFree
High-level synthesis method including processing for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-level synthesis method including processing for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-level synthesis method including processing for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2561025