Circuit synthesis method

Details Circuit synthesis method Circuit synthesis method

2000-12-04

2003-01-07

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06505340

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 Deniel 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+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
15
indicates that an addition
5
is performed after a 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 multiplication (“*”) is represented by reference numeral
4
, and additions (“+”) are represented by reference numerals
5
and
6
. A division (“/”) is represented by reference numeral
7
. In this specification, symbol “*” indicates multiplication.
A data dependency edge from the input “a”
28
to the multiplication
4
is represented by reference numeral
13
. A data dependency edge from the input “b”
29
to the amultiplication
4
is represented by reference numeral
14
. A data dependency edge from the multiplication
4
to the addition
5
is represented by reference numeral
15
. A data dependency edge from the input “c”
30
to the addition
5
is represented by reference numeral
16
. A data dependency edge from the addition
5
to the addition
6
is represented by reference numeral
17
. A data dependency edge from the input “d”
31
to the addition
6
is represented by reference numeral
18
. A data dependency edge from the addition
6
to the division
7
is represented by reference numeral
19
. A data dependency edge from the input “e”
32
to the division
7
is represented by reference numeral
20
. A data dependency edge from the division
7
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 each of the calculations, inputs and the output to a time slot. (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
). Here, a delay time period determined by the multiplication
4
is 50 ns, a delay time period determined by each of the additions
5
and
6
is 10 ns, a delay time period determined by the division
7
is 60 ns, and a clock cycle in each scheduling step is 100 ns.
Scheduling is performed so that the total of the delay time periods of the calculations, which are connected by data dependency edges and scheduled in one scheduling step, does not exceed one clock cycle. For example, in
FIG. 2
, the total of the delay time periods determined by the multiplication
4
, the additions
5
and
6
, and the division
7
is 50+10+10+60=130 ns. Accordingly, these four calculations cannot be scheduled in one scheduling step.
In
FIG. 2
, the input “a”
28
and the input “b”
29
are scheduled in scheduling step
0
. The multiplication
4
, the input “c”
30
, the addition
5
and the input “d”
31
are scheduled in scheduling step
1
. The addition
6
, the input “e”
32
and the division
7
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 addition
5
and the addition
6
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
13
and
14
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
8
(“mult 1”), one adder
9
(“adder 1”), and one divider
10
(“div 1”) are allocated. The multiplication
4
in the CDFG
100
is assigned to the multiplier
8
. The additions
5
and
6
scheduled in different scheduling steps are assigned to the one adder
9
. The division
7
is assigned to the divider
10
.
By the allocation procedure
121
for the registers shown in
FIG. 4
, a first register
11
(“reg 1”) and a second register
12
(“reg 2”) are allocated. One of the data dependency edges crossing the clock boundary between scheduling steps
0
and
1
(data dependency edge
13
), one of the data dependency edges crossing the clock boundary between scheduling steps
1
and
2
(data dependency edge
17
), and the data dependency edge
21
crossing the clock boundary between scheduling steps
2
and
3
are assigned to the first register
11
. The other data dependency edge crossing the clock boundary between scheduling steps
0
and
1
(data dependency edge
14
) and the other data dependency edge crossing the clock boundary between scheduling steps
1
and
2
(data dependency edge
18
) are assigned to the second register
12
.
By the allocation procedure
122
for the inputs and output shown in
FIG. 5
, five input pins “a”
22
, “b”
23
, “c”
24
, “d”
25
, and “e”

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-3069363