Circuit synthesis method

Details Circuit synthesis method Circuit synthesis method

2000-11-13

2003-03-11

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06532584

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a circuit synthesis method for an LSI for automatically generating a logic circuit of a register transfer level (RTL) from a behavioral description, and specifically to a high level synthesis method which is especially effective for designing devices which need to be designed within a short period of time such as, for example, ASICs (Application Specific Integrated Circuits).
2. Description of the Related Art
High level synthesis is a technology for automatically generating an RTL logic circuit from a behavioral description which describes only a behavior of calculation processing and does not include information on a hardware structure. High level synthesis is described in detail in Daniel Gajski, Allen Wu, Nikil Dutt and Steve Lin, “High-Level Synthesis” published by Kluwer Academic Publishers, 1992. High level synthesis is also disclosed in Japanese Laid-Open Publication No. 5-101141. High level synthesis will be described briefly below. <Conversion of behavioral description into CDFG>
In high level synthesis, a behavioral description describing only a behavior of calculation processing is analyzed, and then the behavioral description is converted into a model referred to as a control data flowgraph (CDFG) representing the dependency among the calculations, i.e., the execution order of the calculations.
For example, a behavioral description of expression (1) is converted into a CDFG in the following manner.
f
={(
a*b
)+
c
(
b+d)
)}*
e
  (1)
A CDFG is a graph in which calculations, inputs and outputs are represented by nodes, and data dependency (i.e., execution order of calculations, inputs and outputs) is represented by directional edges (data dependency edges; e.g., arrows). For example, in
FIG. 1
, which illustrates a CDFG
100
corresponding to the behavioral description of expression (1), a data dependency edge
14
indicates that an addition
5
is performed after a first multiplication
4
is performed. In the CDFG
100
, inputs “a”, “b”, “c”, “d” and “e” are respectively represented by reference numerals
28
through
32
, and an output “f” is represented by reference numeral
33
. As mentioned above, the first multiplication (“*”) is represented by reference numeral
4
, and first, second and third additions (“+”) are respectively represented by reference numerals
5
,
6
and
7
. A second multiplication (“*”) is represented by reference numeral
8
. In this specification, symbol “*” indicates multiplication.
A data dependency edge from the input “a”
28
to the first multiplication
4
is represented by reference numeral
11
. A data dependency edge from the input “b”
29
to the first multiplication
4
is represented by reference numeral
12
. A data dependency edge from the input “b”
29
to the second addition
6
is represented by reference numeral
13
. A data dependency edge from the first multiplication
4
to the first addition
5
is represented by reference numeral
14
. A data dependency edge from the input “c”
30
to the first addition
5
is represented by reference numeral
15
. A data dependency edge from the input “d”
31
to the second addition
6
is represented by reference numeral
16
. A data dependency edge from the first addition
5
to the third addition
7
is represented by reference numeral
17
. A data dependency edge from the second addition
6
to the third addition
7
is represented by reference numeral
18
. A data dependency edge from the third addition
7
to the second multiplication
8
is represented by reference numeral
19
. A data dependency edge from the input “e”
32
to the second multiplication
8
is represented by reference numeral
20
. A data dependency edge from the second multiplication
8
to the output “f”
33
is represented by reference numeral
21
.
<Scheduling>
After the behavioral description of expression (1) is converted into the CDFG
100
(FIG.
1
), scheduling is performed. Scheduling is processing for assigning the calculations, inputs and the outputs to time slots. (The CDFG
100
(
FIG. 1
) includes only one output.) Each time slot corresponds to a state of a finite state machine and is referred to as a scheduling step.
FIG. 2
shows a scheduling result
110
obtained as a result of scheduling the CDFG
100
(FIG.
1
). In
FIG. 2
, the input “a”
28
and the input “b”
29
are scheduled in scheduling step
0
. The first multiplication
4
, the input “c”
30
, the input “d”
31
, the first addition
5
and the second addition
6
are scheduled in scheduling step
1
. The third addition
7
, the input “e”
32
and the second multiplication
8
are scheduled in scheduling step
2
. Only the output “f”
33
is scheduled in scheduling step
3
.
The same type of calculations scheduled in different scheduling steps can share one calculation device. In
FIG. 2
, the first addition
5
and the third addition
7
are respectively scheduled in scheduling steps
1
and
2
, and therefore can share one calculation device. The second addition
6
and the third addition
7
are also respectively scheduled in scheduling steps
1
and
2
, and therefore can share one calculation device. The first multiplication
4
and the second multiplication
8
are respectively scheduled in scheduling steps
1
and
2
, and therefore can share one calculation device. By scheduling, each of the calculations is assigned to an appropriate scheduling step so as to minimize the cost of the hardware.
In the scheduling result
110
shown in
FIG. 2
, the data dependency edges
11
,
12
and
13
cross the clock boundary between scheduling steps
0
and
1
. The data dependency edges
17
and
18
cross the clock boundary between scheduling steps
1
and
2
. The data dependency edge
21
crosses the clock boundary between scheduling steps
2
and
3
.
<Allocation>
Allocation is processing for allocating calculation devices, registers, and input and output pins required to execute the scheduled CDFG: and assigning the calculations of the CDFG to the calculation devices, assigning the data dependency edges crossing the clock boundaries between two adjacent scheduling steps to the registers, and assigning the inputs and outputs to the input and output pins. (Only one output is necessary for the CDFG
100
in
FIG. 1.
)
FIGS. 3
,
4
and
5
show allocation procedures
120
,
121
and
122
performed on the CDFG
100
(
FIG. 1
) scheduled as shown in FIG.
2
.
FIG. 3
shows an allocation procedure
120
for the calculation devices;
FIG. 4
shows an allocation procedure
121
for the registers; and
FIG. 5
shows an allocation procedure
122
for the inputs and the output.
By the allocation procedure
120
for the calculation devices shown in
FIG. 3
, one multiplier
1
(“mult
1
”), and first and second adders
2
and
3
(“adder
1
” and “adder
2
”) are allocated. The first and second multiplications
4
and
8
scheduled in different scheduling steps are assigned to the multiplier
1
. The first and third additions
5
and
7
scheduled in different scheduling steps are assigned to the first adder
2
. The second adder
6
scheduled in scheduling step
1
is assigned to the second adder
3
.
By the allocation procedure
121
for the registers shown in
FIG. 4
, a first register
41
(“reg
1
”) and a second register
42
(“reg
2
”) are allocated. One of the data dependency edges crossing the clock boundary between scheduling steps
0
and
1
(data dependency edge
11
) and one of the data dependency edges crossing the clock boundary between scheduling steps
1
and
2
(data dependency edge
17
) are assigned to the first register
41
. The other data dependency edge crossing the clock boundary between scheduling steps
0
and
1
(data dependency edge
13
), the other data dependency edge crossing the clock boundary between scheduling steps
1
and
2
(data dependency edge
18
), and the data dependency edge
21
crossing the clock boundary between scheduling steps
2
and
3
ar

Affiliated with

Also associated with

Rating

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

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3005561