High-level synthesis method and storage medium storing the same

Details High-level synthesis method and storage medium storing the same High-level synthesis method and storage medium storing the same

2000-12-21

2003-08-05

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06604232

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a high-level synthesis method for automatically synthesizing a digital circuit based on an operating description of an LSI, and a storage medium storing the method.
2. Description of the Related Art
Conventionally, high-level synthesis methods are known as techniques which are particularly effective in designing application-specific integrated circuits (ASIC) and the like where a short period of time is required for designing.
The high-level synthesis is a technique for automatically synthesizing a circuit based only on an operating description of a processing algorithm without information on hardware structure. The high-level synthesis technique is described in detail in “High-level Synthesis” (Kluwer Academic Publishers).
Hereinafter, for example, a method for high-level synthesizing a circuit automatically based on an operating description represented by the following expression (1), will be described:
x
=(
a+b
)*(
b+c
)  (1)
A typical high-level synthesis method is performed in accordance with a flowchart shown in FIG.
1
. In the high-level synthesis method, control and data flow in executing an operating description are initially analyzed and converted to a model called a control data flow graph (CDFG) (see step S
1
in FIG.
1
). A CDFG is a graph similar to a flowchart. A CDFG is comprised of nodes and input/output (I/O) branches. The I/O branches indicate the flow of data or control signals. Nodes indicate operations. Inputs and outputs of the operations correspond to I/O branches of the nodes.
For example, an operating description shown in
FIG. 1
is represented by a CDFG shown in FIG.
2
. The CDFG of
FIG. 2
includes first and second addition nodes
11
and
12
each representing an addition operation and a multiplication node
13
representing a multiplication operation. In the CDFG of
FIG. 2
, an input “a” and an input “b” are added together, an input “b” and an input “c” are added together, and the results of both addition operations are multiplied together, the result of the multiplication operation being represented by an output “x”.
After the operating description represented by expression (1) has been converted to the CDFG shown in
FIG. 2
, scheduling is performed (see step S
2
in FIG.
1
). Scheduling determines the timings of executing operations corresponding to the nodes of a CDFG, i.e., to determine in which clock step each operation corresponding to a node of a CDFG is executed. In this case, operations at all of the nodes need to be completed in a clock period, taking into account the operating time of each operation.
FIG. 3
shows an example of scheduling the CDFG of FIG.
2
. In
FIG. 3
, two addition operations and one multiplication operation are scheduled to be executed within a clock step (step
1
). In this case, the scheduling is performed in such a manner that the total of the operating times of such arithmetic executions does not exceed the period of one clock step. For example, when the operating times of an adder and a multiplier are 5 nsec and 60 nsec, respectively, and the clock period is 65 nsec or more, all of the operations can be scheduled within one clock step (step
1
) as shown in FIG.
3
.
Identical operations which are scheduled in different clock steps can be executed in a single operator. For this reason, as shown in
FIG. 5
, a first addition node
11
representing a first addition and a second addition node
12
representing a second addition are scheduled to be performed in different steps
1
and
2
, respectively, so that both the operations can be executed in a single adder. In this case, if the clock period is 65 nsec or more, the second addition whose operating time is 5 nsec and a multiplication whose operating time is 60 nsec can be scheduled to be performed in a second clock (clock step
2
).
After an operating description has been scheduled, allocation is performed (see step
3
in FIG.
1
). Allocation generates operators, registers and the like required for executing a scheduled CDFG. For example, in an allocation, operators are allocated as operations of a CDFG, and registers, selectors and the like are allocated as I/O branches across borders between adjacent clock steps. By allocation, a circuit for executing the operating description represented by expression (1) is generated (see step
4
in FIG.
1
).
FIG. 4
shows the result of the scheduling in FIG.
3
. In
FIG. 4
, first and second adders
14
and
15
corresponding to the first and second addition operations, respectively, are generated and allocated as the first and second addition nodes
11
and
12
, and a multiplier
16
corresponding to the multiplication operation is generated and allocated as the multiplication node
13
. In this case, no register or selector is generated since there is no branch across a border between adjacent clock steps.
FIG. 6
shows the result of the scheduling in FIG.
5
. In
FIG. 6
, the first and second addition nodes
11
and
12
corresponding to the first and second addition operations are scheduled to be performed in different steps
1
and
2
. Therefore, only one adder
14
is generated for the addition nodes
11
and
12
. There are I/O branches
21
and
22
(
FIG. 5
) across a border between clock steps
1
and
2
. Therefore, a selector
23
(indicated by “sel” in
FIG. 6
) and a register
24
(indicated by “reg” in
FIG. 6
) are generated for the I/O branches
21
and
22
, respectively.
In the circuit shown in
FIG. 6
, inputs “a” and “c” are supplied to the selector
23
, and the output of the selector
23
is input to the adder
14
. Input “b” is also supplied to the adder
14
. The output of the adder
14
is input to the register
24
and the multiplier
16
. In this case, a controller
25
(indicated by “Controller” in
FIG. 6
) which produces control signals for each of the generated selector
23
and register
24
is generated. The controller
25
outputs a select signal k
1
to the selector
23
. The selector
23
outputs input “a” when the select signal k
1
is “1”, or outputs input “c” when the select signal k
1
is “0”. The controller
25
also outputs an enable signal k
2
to the register
24
. The register
24
stores an input value at the rising of a clock signal when the enable signal k
2
is “1”, or maintains a stored value and outputs the stored value when the enable signal k
2
is “0”.
The operation of the circuit shown in
FIG. 6
will be described. In clock step
1
, the select signal k
1
and the enable signal k
2
are both “1”, and the selector
23
selects input “a” and outputs it to the adder
14
. Then, the adder
14
outputs a value “a+b”, resulting from an addition of “a” and “b”, to the register
24
. The register
24
stores “a+b” output from the adder
14
since the enable signal k
2
is “1”.
In clock step
2
, the select signal k
1
and the enable signal k
2
are both “0”, and the selector
23
selects the input value “c” and outputs it to the adder
14
. Then, the adder
14
outputs a value “c+b”, resulting from an addition of “c” and “b”, to the multiplier
16
. The stored value “a+b” is output to the multiplier
16
since the enable signal k
2
is “0”. The multiplier
16
multiplies the input value “c+b” by the input value “a+b”, and outputs the resultant product as “x”.
In the circuit shown in
FIG. 4
, the operating description is completed in one clock step (for example, within 100 nsec), but two adders
14
and
15
are required. In contrast, in the circuit shown in
FIG. 6
, two clock steps (for example, 200 nsec) are required, but only one adder
14
is used. In such a high-level synthesis method, the circuit of
FIG. 4
is generated when a high-speed circuit is required, while the circuit of
FIG. 6
is generated when a circuit having a small area is required.
As is understood from the scheduling result shown in
FIG. 5
, two addition operations can be performed using a single adder. However, when the number of operatio

Affiliated with

Also associated with

Rating

High-level synthesis method and storage medium storing the same 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 and storage medium storing the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-level synthesis method and storage medium storing the same will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3127899