Hardware synthesis method, hardware synthesis device, and...

Details Hardware synthesis method, hardware synthesis device, and... Hardware synthesis method, hardware synthesis device, and...

1999-02-23

2002-03-19

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06360355

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a high-level synthesis technique for an LSI circuit, for automatically synthesizing a hardwired logic digital circuit from a behavioral description.
BACKGROUND OF THE INVENTION
Conventionally, a high-level synthesis technique has been known as a technique which is particularly effective for designing in a short time, for example, designing an ASIC (Application Specific Integrated Circuit).
High-level synthesis is a technique for automatically synthesizing a circuit from a behavioral description describing only algorithms for processing, without containing information relating to the structure of hardware. One example of documents which describe the details of conventional high-level synthesis techniques is “High-Level Synthesis”, Kluwer Academic Publishers.
The following description will briefly explain processes of automatically synthesizing a circuit from a behavioral description, using a conventional high-level synthesis technique.
[1. Conversion of Behavioral Description into CFG]
In high-level synthesis, first, a flow of control (control flow) of execution of a behavioral description is analyzed, and the behavioral description is converted into a model called a control flow graph (CFG) expressing the control flow of execution.
The CFG is a graph similar to a flow chart of a program. For example, the behavioral description shown in FIG.
23
(
a
) is converted into the CFG shown in FIG.
23
(
b
).
The CFG represents sequences (
1
), (
2
), (
3
), (
4
) of behavior containing no conditional branch in the behavioral description shown in FIG.
23
(
a
) by partial behavioral nodes (
5
), (
6
), (
7
), (
8
) as shown in FIG.
23
(
b
).
Moreover, the CFG represents a conditional statement (
9
) of the behavioral description shown in FIG.
23
(
a
) by a branch node (
10
) and a merge node (
11
) as shown in FIG.
23
(
b
), and the control flow of execution by control flow branches (
12
) through (
19
).
A conditional expression of the conditional statement (
9
) corresponds to the branch node (
10
). When the condition is satisfied, the control moves to an output (
14
) on the true side of the branch node (
10
). When the condition is not satisfied, the control moves to an output (
15
) on the false side of the branch node (
10
).
It is said that, when the condition is satisfied, a control flow branch connected to the output on the true side of the branch node becomes active. Similarly, it is said that, when the condition is not satisfied, a control flow branch connected to the output on the false side of the branch node becomes active.
In the CFG shown in FIG.
23
(
b
), one of the outputs (
14
), (
15
) of the branch node (
10
), which is marked with a black circle, represents the output on the true side. Similarly, in other CFGs later described, an output marked with a black circle in each branch node is the output on the true side.
[2. Conversion of CFG into CDFG]
After the conversion of a behavioral description into a CFG is performed as described above, the data dependence (data flow) of the CFG is analyzed, and then the CFG is converted into a model called control data flow graph (CDFG) expressing the dependence in the execution sequence between operations.
For example, the CFG shown in FIG.
23
(
b
) is converted into the CDFG shown in FIG.
24
.
The CDFG is a graph expressing the data dependence and the control dependence by branches by representing operations (
20
) through (
25
) and a selector (
26
) as nodes. Here, the operations (
20
) through (
24
) are arithmetic operations, and the operation (
25
) is a conditional operation.
The operation (
25
) as a conditional operation outputs a control signal (
27
) representing whether a conditional decision is true or false. The selector (
26
) selects one of two inputs according to the value of the control signal (
27
), and outputs the selected input.
Since the multiplication of b=a*d at the partial behavioral node (
5
) in the CFG shown in FIG.
23
(
b
) depends on the result of the operation of a=b*c, a branch representing data dependence is present between the operations (
20
) and (
21
) in the CDFG.
Since no data dependence exists between the operations (
21
) and (
22
), they can be executed parallel. On the other hand, since data dependence exists between the operations (
20
) and (
21
), they cannot be executed parallel.
The reason for converting a behavioral description into a CDFG in high-level synthesis is that the CDFG is a behavioral expression which not only ensures the behavior described by the behavioral description, but also allows generation of hardware that achieves parallel processing.
[3. Scheduling]
When the conversion of CFG into CDFG has been completed, scheduling is performed. Scheduling is a process of determining relative times at which input/output, operations, and selection by the selector in the CDFG are to be executed on a circuit.
FIG. 25
shows the result of scheduling the CDFG shown in FIG.
24
. According to the result of scheduling, inputs b, c, e, f, output a, and operations (
30
), (
31
), (
35
) are executed in step s
1
, and input d, outputs b, d, g, operations (
32
), (
33
), (
36
), and selection (
34
) by the selector are executed in step s
2
.
[4. Allocation]
Allocation is a process of synthesizing a circuit by allocating arithmetic units to the operation nodes in the CDFG upon receipt of the result of scheduling, generating multiplexers for data selection, registers for data storage and a controller for controlling those and connecting them to each other.
FIG. 26
shows a circuit synthesized by the allocation according to the result of scheduling shown in FIG.
25
.
[5. Behavioral Description Language for High-Level Synthesis]
For behavioral descriptions for high-level synthesis, procedure-oriented languages as well as many programming languages are usually used because the human's thinking is consecutive and a behavior described by a procedure-oriented language is easily understood by the human. A typical example of procedure-oriented behavioral description languages is a VHDL language. Many of conventional synthesis tools adopt the VHDL language as the behavioral description language.
However, the VHDL language has not spread widely compared with usual programming languages. Therefore, when hardware is to be designed by an engineer who is unfamiliar with the VHDL language, he/she must learn the VHDL language, irrespective of whether he/she understands other programming languages.
Besides, hardware is designed by a method in which an algorithm is first verified by software and then hardware is realized by a behavioral description language. Namely, in such a method, rewriting from a programming language as a software description language to the VHDL language needs to be performed by an operator.
A typical example of the procedure-oriented programming languages is C language. The C language has been widely used as a language for describing software, and many engineers have already understood the C language. It is thus considered that the C language is suitably used as a behavioral description language for high-level synthesis.
If the C language is used as a behavioral description language for high-level synthesis, the C language used for verifying the algorithm by software can be used directly as an input for high-level synthesis. Hence, rewriting from the programming language into the VHDL language by the operator is not required.
A characteristic of the C language, which is not possessed by the VHDL language, is that the C language supports goto statements and switch statements for dispersing control of execution to another location in the description.
The goto statement is a command which instructs a jump to a description section labelled with the same label as a jump destination label given as an argument of the goto statement. The goto statement can be used as a jump command according to a condition by using it as a subordinate statement of an if sta

Affiliated with

Also associated with

Rating

Hardware synthesis method, hardware synthesis device, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hardware synthesis method, hardware synthesis device, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware synthesis method, hardware synthesis device, and... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2877577