Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-04-12
2002-09-10
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06449763
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a high-level synthesis apparatus and method for use in the designing of logical circuits in an LSI, the apparatus and method being used for synthesizing circuits whose operations are expressed by operational descriptions (e.g., instructions, functions, procedures); and a recording medium carrying a program for implementing the high-level synthesis method.
2. Description of the Related Art
Conventionally, methods for synthesizing a circuit from operational descriptions which express operations of threads that operate in parallel and which express synchronous data communication between such threads are disclosed, for example, in Japanese Laid-Open Publication No. 10-116302, which has been filed by the Applicant.
The aforementioned conventional method is illustrated in FIG.
1
. First, operational descriptions
1
are read, and the order of executing the arithmetic operations included therein is determined by a scheduler
3
. Then, a circuit element allocator
5
allocates arithmetic operations and the like to elements (e.g., arithmetic logic units, registers, etc.) in the data path. Then, a control circuit is generated which generates signals controlling the data path such that it executes the arithmetic operations and the like in the order determined by the scheduler
3
. Thus, a product circuit
7
is synthesized by this conventional synthesis method.
According to this conventional synthesis method, instructions (e.g., “send”, “receive”) are provided in an input language for defining a communication procedure (commonly known as a “protocol”) such that data between two threads are transferred in a synchronous manner, i.e., a data transfer between a data-transmitting end and a data-receiving end can begin only after both ends become ready to commence data transfer. Thus, an instruction for sending data (“send”) and an instruction for receiving data (“receive”) are simply described in the input language. A product circuit is synthesized by additionally generating handshaking circuits for the respective threads for achieving handshaking there between. Thus, the product circuit guarantees synchronous communication between the threads.
However, a circuit which is generated by the aforementioned conventional synthesis method has a problem in that the communication slows down when a series of consecutive communication instructions are executed because such communication instructions are executed in a sequential manner.
For example, consider the two “SEND” instructions in a thread
15
included in a set of operational descriptions shown in FIG.
2
. In this case, a circuit which is synthesized by the aforementioned conventional synthesis method can execute the communication described as SEND (CH
2
, D
2
) only after the communication described as SEND (CH
1
, D
1
) occurs. As a result, when handshaking communication is performed in synchronization with a clock signal, the execution of these two “SEND instructions” requires four clock cycles, as shown in FIG.
3
.
SUMMARY OF THE INVENTION
According to the present invention, there is provided a high-level synthesis apparatus for receiving operational descriptions including synchronous communication instructions between threads which operate in parallel, and for synthesizing a product circuit based on the received operational descriptions, the high-level synthesis apparatus including: an extractor for analyzing the received operational descriptions and extracting consecutive synchronous communication instructions which are of the same kind from among the received operational descriptions; a scheduler for generating scheduling for each thread by bundling together the extracted synchronous communication instructions into one arithmetic operation; and a circuit generator for generating the product circuit based on results of the scheduling, the product circuit being capable of commencing the bundled synchronous communication instructions with the same level of priority based on handshaking.
In one embodiment of the invention the circuit generator includes: a data path element allocation section for, based on the results of the scheduling, selecting and allocating circuit elements which are necessary for constructing a data path; a handshaking circuit addition section for adding a handshaking circuit for each of input/output ports of the data path; a queuing state generation section for adding a queuing state to the results of the scheduling; and a control circuit generation section for generating a control circuit for performing control based on the results of the scheduling with the queuing state added thereto.
In another aspect of the invention, there is provided a high-level synthesis method for receiving operational descriptions including synchronous communication instructions between threads which operate in parallel, and for synthesizing a product circuit based on the received operational descriptions, the method including the steps of: analyzing the received operational descriptions and extracting consecutive synchronous communication instructions which are of the same kind from among the received operational descriptions; generating scheduling for each thread by bundling together the extracted synchronous communication instructions into one arithmetic operation; and generating the product circuit based on results of the scheduling, the product circuit being capable of commencing the bundled synchronous communication instructions with the same level of priority based on handshaking.
In still another aspect of the invention, there is provided a recording medium carrying a program for implementing the aforementioned high-level synthesis method.
Hereinafter, the effects of the present invention will be described.
According to the present invention, operational descriptions including synchronous communications between threads which operate in parallel are analyzed, and any number of consecutive synchronous communications which are of the same kind are extracted. Then, the scheduling for each thread is generated by bundling together the extracted synchronous communications into one arithmetic operation. Based on such scheduling results, the circuit generated by the method of the present invention can commence the bundled synchronous communications with the same level of priority (e.g., at the same time) during a synchronous communication process via handshaking circuits. As a result, the circuit generated by the method of the present invention is capable of operating at a higher speed than conventional circuits in which such synchronous communication instructions are executed in a consecutive manner.
For example, in the set of operational descriptions illustrated in
FIG. 2
, the two synchronous communications “SEND (CH
1
, D
1
)” and “SEND (CH
2
, D
2
)”, which are consecutively described and are of the same kind, have no data dependency on each other. Therefore, it is possible to simultaneously commence the two communications and complete the communications within two clock cycles (see the description of the embodiment of the invention with reference to
FIG. 13
for more detailed explanation).
As used herein, two instructions are said to have “data dependency” on each other if the two instructions can be illustrated as two nodes that are connected to each other by an arrow in a control data flow graph (“CDFG”) (e.g., FIG.
5
). The control data flow graph of
FIG. 5
corresponds to the operational descriptions shown in FIG.
2
. For example, the communication instructions “SEND (CH
1
, D
1
)” and “SEND (CH
2
, D
2
)” shown in
FIG. 2
correspond to the nodes denoted as “CH
1
W” and “CH
2
W” of
FIG. 5
, respectively. Since the nodes CH
1
W and CH
2
W are not connected to each other by an arrow, the two communication instructions “SEND (CH
1
, D
1
)” and “SEND (CH
2
, D
2
)” do not have any ‘data dependency’ on each other.
Even if two synchronous communication instructions interpose a process which is not a synchronous communication instruction descri
Nishida Koichi
Yamada Akihisa
Levin Naum
Smith Matthew
LandOfFree
High-level synthesis apparatus, high level 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 High-level synthesis apparatus, high level synthesis method,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-level synthesis apparatus, high level synthesis method,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2873918