Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-02-11
2003-04-29
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06557158
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheduling method for high-level synthesis of a circuit which is represented by an operation description. More particularly, the present invention relates to a scheduling method for assigning a plurality of nodes included in a control flow graph respectively to a plurality of time steps so as to minimize the circuit area.
2. Description of the Related Art
In the prior art, “HIGH-LEVEL SYNTHESIS, Introduction to Chip and System Design (Kluwer Academic Publishers) 1992” describes a force-directed scheduling algorithm for performing a scheduling operation so as to minimize the circuit area. This algorithm calculates, for each time step, the sum of probabilities for a plurality of nodes included in a control flow graph to be assigned to that time step so as to estimate the circuit area (hereinafter, also referred to simply as the “area”) based on the maximum value of the calculated sums.
Japanese Laid-Open Publication No. 9-81605 describes an algorithm which involves an improvement to the above force-directed scheduling algorithm. This algorithm gradually narrows down the scheduling candidates by calculating the estimated.value of the circuit area, for each node (B) having scheduling candidate (A) in the time step for which the sum of probabilities is maximum, with the scheduling candidate (A) having been excluded from a list of one or more scheduling candidates of the node (B), so as to obtain a combination of a node (C) and a scheduling candidate (D) for which the circuit area is maximum, and then excluding the scheduling candidate (D) from a list of one or more scheduling candidates of the node (C). The algorithm described in Japanese Laid-Open Publication No. 9-81605 aims to solve a problem associated with the force-directed scheduling algorithm (i.e., the optimal time step may be excluded from the list of scheduling candidates when a plurality of nodes are assigned to time steps at once, thereby resulting in a local solution). Thus, the algorithm described in Japanese Laid-Open Publication No. 9-81605 gradually narrows down the scheduling candidates, thereby achieving better scheduling results than those obtained with the force-directed scheduling algorithm.
However, the algorithm described in Japanese Laid-Open Publication No. 9-81605 calculates; for each time step, the sum of probabilities for a plurality of nodes to be assigned to that time step, and calculates the estimated value of the circuit area, for each node (B) having scheduling candidate (A) in the time step for which the sum of probabilities is maximum, with the scheduling candidate (A) having been excluded from a list of one or more scheduling candidates of the node (B). Thus, the accuracy of the estimated value may not be sufficient, whereby the optimal time step may be excluded from the list of scheduling candidates, thereby resulting in a local solution.
Moreover, the algorithm described in Japanese Laid-Open Publication No. 9-81605 does not take into consideration the area of registers. Therefore, it is likely that even when the area of operators is reduced, the area of registers increases, thereby increasing the area of the entire circuit.
SUMMARY OF THE INVENTION
According to one aspect of this invention, there is provided a scheduling method for high-level synthesis of a circuit which is represented by an operation description. The method includes the steps of: (a) calculating a probability for each of a plurality of nodes included in a control flow graph to be assigned to a time step; (b) calculating a sum of the probabilities for each time step; (c) calculating, for each node having a scheduling candidate in a time step for which the sum of probabilities is maximum, an estimated value of an area of the circuit with the node having been temporarily assigned to the scheduling candidate; (d) retrieving a combination of a node and a scheduling candidate for which the estimated value is maximum: and (e) narrowing down a list of scheduling candidates of the node in the combination by excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
In one embodiment of the invention, the method further includes the step of determining whether or not there is more than one combination of a node and a scheduling candidate retrieved in the step (d) for which the estimated value is maximum. If it is determined that there is more than one such combination, the step (e) includes the steps of: (e-1) calculating a value of a predetermined evaluation function for each of the combinations; (e-2) retrieving a combination of a node and a scheduling candidate for which the value of the predetermined evaluation function is maximum; and (e-3) excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
In one embodiment of the invention, the evaluation function is represented by ((the number of inputs of the node)−(the number of outputs of the node)×(a time step number of the scheduling candidate).
According to another aspect of this invention, there is provided a computer-readable recording medium having a program recorded thereon for instructing a computer to execute a scheduling method for high-level synthesis of a circuit which is represented by an operation description. The scheduling method includes the steps of: (a) calculating a probability for each of a plurality of nodes included in a control flow graph to be assigned to a time step; (b) calculating a sum of the probabilities for each time step; (c) calculating, for each node having a scheduling candidate in a time step for which the sum of probabilities is maximum, an estimated value of an area of the circuit with the node having been temporarily assigned to the scheduling candidate; (d) retrieving a combination of a node and a scheduling candidate for which the estimated value is maximum; and (e) narrowing down a list of scheduling candidates of the node in the combination by excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
Thus, the invention described herein makes possible the advantage of: (1) providing a scheduling method for high-level synthesis capable of quickly and accurately calculating the estimated value of the circuit area; and (2) providing a scheduling method for fast high-level synthesis which takes into consideration the area of registers.
REFERENCES:
patent: 5487017 (1996-01-01), Prasad et al.
patent: 5502645 (1996-03-01), Guerra et al.
patent: 5513118 (1996-04-01), Dey et al.
patent: 5550749 (1996-08-01), Dey et al.
patent: 5557797 (1996-09-01), Yano
patent: 5706205 (1998-01-01), Masuda et al.
patent: 5787010 (1998-07-01), Schaefer et al.
patent: 2 279 785 (1995-01-01), None
patent: 2 350 914 (2000-12-01), None
patent: 09081605 (1997-03-01), None
P.G. Paulin et al., Force-directed scheduling for the Behavioral Synthesis of ASICs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 661-679, Jun. 1989.*
P.G. Paulin et al., Scheduling and Binding Algorithms for High Level Synthesis, Proceedings of the 1989 26thACM/IEEE Conference on Design Automation, pp. 1-6, 1989.*
R. Cloutier et al., The combination of Scheduling, Allocation, and mapping in A Single Algorithm, 27thACM/IEEE Design Automation Conference, pp. 71-76, 1991.*
P.G. Paulin et al., Force-Directed Scheduling in Automatic Data Path Synthesis, 24thACM/IEEE Design Automation Conference, pp. 195-202, 1987.*
“Force-Directed Heuristic Method”, Daniel D. Gajski, et al.,High-Level Synthesis—Introduction to Chip and System Design, (1992).
Smith Matthew
Thompson A. M.
LandOfFree
Scheduling method for high-level synthesis and recording medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling method for high-level synthesis and recording medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling method for high-level synthesis and recording medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016873