CN102419789B - High-level synthesis method and system - Google Patents
High-level synthesis method and system Download PDFInfo
- Publication number
- CN102419789B CN102419789B CN 201110423313 CN201110423313A CN102419789B CN 102419789 B CN102419789 B CN 102419789B CN 201110423313 CN201110423313 CN 201110423313 CN 201110423313 A CN201110423313 A CN 201110423313A CN 102419789 B CN102419789 B CN 102419789B
- Authority
- CN
- China
- Prior art keywords
- compatible
- resource
- node
- limit
- data flow
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000001308 synthesis method Methods 0.000 title claims abstract description 11
- 238000010586 diagram Methods 0.000 claims abstract description 33
- 238000000034 method Methods 0.000 claims abstract description 16
- 238000013468 resource allocation Methods 0.000 claims abstract description 12
- 230000015572 biosynthetic process Effects 0.000 claims description 7
- 238000003786 synthesis reaction Methods 0.000 claims description 7
- 238000004364 calculation method Methods 0.000 claims description 4
- 230000009286 beneficial effect Effects 0.000 description 2
- 238000000638 solvent extraction Methods 0.000 description 1
Images
Landscapes
- Design And Manufacture Of Integrated Circuits (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本发明公开了一种高层次综合方法以及系统，该系统包括数据流图生成单元、预分配单元、调度单元、资源分配单元以及电路生成单元。该方法是，首先获取数字电路行为描述，进而生成数据流图，然后进行硬件资源预分配，进而生成资源约束列表，跟着进行调度以及资源分配，最后生成硬件电路结构。通过使用本发明，在执行调度时不仅包括硬件资源数目信息，还包括硬件互连的信息，而且能够免除人工确定调度约束，因此，这样能够更加快速地生成硬件电路结构，而且有效地减少了硬件电路结构中的互连开销。本发明作为一种高层次综合方法以及系统广泛应用在设计硬件电路结构领域中。
The invention discloses a high-level synthesis method and system. The system includes a data flow diagram generation unit, a pre-allocation unit, a scheduling unit, a resource allocation unit and a circuit generation unit. The method is to first obtain the behavior description of the digital circuit, and then generate a data flow diagram, then perform hardware resource pre-allocation, and then generate a resource constraint list, then perform scheduling and resource allocation, and finally generate a hardware circuit structure. By using the present invention, not only information on the number of hardware resources but also hardware interconnection information is included when scheduling is performed, and manual determination of scheduling constraints can be avoided. Therefore, the hardware circuit structure can be generated more quickly, and the hardware circuit structure can be effectively reduced. Interconnect overhead in circuit structures. As a high-level synthesis method and system, the invention is widely used in the field of designing hardware circuit structures.
Description
Technical field
The present invention relates to a kind of method and system that designs hardware circuit, especially a kind of scheduling and resource based on compatible figure distributed high-level synthesis method and the system that combines.
Background technology
Scheduling and resource allocation algorithm flow process are the focuses in the research in the High Level Synthesis field.
Dispatching algorithm is classified according to its implementation, mainly can be divided into structured approach, converter technique and integral linear programming method.Described structured approach is to select first an operation at every turn, select again a suitable control step, then in this operation scheduling being gone on foot to selected control, until all being scheduled, all operations finish, yet, the key of structured approach is next step scheduling operation of How to choose, and the suitable control of How to choose goes on foot to place selected operation; Described converter technique is at first to select the dispatching algorithm (for example ASAP) that is simple and easy to realize to obtain an initial scheduling scheme, then this scheduling scheme is carried out iterated transform, is used for obtaining optimum scheduling result; Described integral linear programming (ILP) method is scheduling problem to be converted into the integral linear programming problem find the solution.And distribution can adopt the methods such as graph-theoretical algorithm, integral linear programming to solve for the resource in the High Level Synthesis.This is similar with the method that solves scheduling.Described graph-theoretical algorithm mainly comprises clique partitioning algorithm, weight bipartite graph algorithm, compatible nomography etc.
Conventional High Level Synthesis system dispatches respectively with resource to distribute.; because in the process of operation dispatching; its design constraint normally determine to produce according to artificial experience; it generally includes only the hardware resource information of number; and do not comprise the hardware interconnect information; therefore, by the circuit structure that this system produces, it often can not satisfy the design requirement of area optimum.
Summary of the invention
In order to solve the technical matters of above-mentioned existence, the purpose of this invention is to provide a kind of high-level synthesis method of satisfied design hardware circuit area optimum.
Another object of the present invention provides a kind of High Level Synthesis system of satisfied design hardware circuit area optimum.
The technical solution used in the present invention is: a kind of high-level synthesis method, and described method step comprises:
A, obtain the digital circuit behavior description, and then the generated data flow graph;
B, according to data flow diagram, carry out hardware resource predistribution, and then generate the resource constraint tabulation;
C, according to resource constraint tabulation and data flow diagram, dispatch;
D, carry out resource according to the result of scheduling and distribute;
E, generate hardware circuit according to resource allocation result and scheduling result.
Further, described step B adopts compatible nomography to carry out predistribution.
Further, described step B comprises:
B1, make up compatible figure according to data flow diagram, and set up the resource constraint tabulation;
B2, search longest path according to compatible figure;
The longest path that B3, basis are searched is put into the resource constraint tabulation successively with each node that described longest path relates to;
The longest path that B4, basis are searched is deleted node and the limit that relates in the described longest path in compatible figure, and the weight on remaining each limit among the compatible figure is recomputated;
B5, judge whether also there is node among the compatible figure, if exist, return execution in step B2; If do not exist, generate the resource constraint tabulation, step B finishes.
Further, described step B2 adopts longest path algorithm to search longest path.
Further, described step B1 makes up the weight on the limit and each limit that comprise the node that makes up compatible figure, compatible figure among the compatible figure.
Further, whether the limit of described compatible figure is according to existing data dependence relation or common input end mouth to make up between two nodes.
Further, the computing method that make up each limit weight are:
W
i,j=（α*dependency
i,j+β*NIN
i,j）
Wherein α, β are coefficient, dependency
I, jBe Boolean, i and j are any two nodes, if node i and j have data dependence relation, and dependency then
I, jBeing 1, then is not 0; NIN
I, jBe integer, the input port number that representation node i and j are common.
Another technical solution used in the present invention is: a kind of High Level Synthesis system comprises:
The data flow diagram generation unit is used for obtaining the digital circuit behavior description, and then the generated data flow graph;
The predistribution unit is used for according to data flow diagram, carries out hardware resource predistribution, and then generates the resource constraint tabulation;
Scheduling unit is used for dispatching according to resource constraint tabulation and data flow diagram;
Resource allocation unit is used for carrying out the resource distribution according to the result of scheduling;
The circuit evolving unit is used for generating hardware circuit according to resource allocation result and scheduling result.
Further, described predistribution unit comprises:
Composition table module is used for making up compatible figure according to data flow diagram, and sets up the resource constraint tabulation;
Search module, be used for searching longest path according to compatible figure;
Modified module, be used for according to the longest path of searching, each node that longest path relates to is put into the resource constraint tabulation successively, and in compatible figure, delete node and the limit that relates in the longest path, and the weight on remaining each limit among the compatible figure is recomputated;
Judge execution module, be used for judging whether compatible figure also exists node, if exist, return and search module; If do not exist, generate the resource constraint tabulation, and provide resource constraint to tabulate to scheduling unit.
The invention has the beneficial effects as follows: the application of the invention, when operation dispatching, not only comprise the hardware resource information of number, the information that also comprises the hardware interconnection, and the operation of resource constraint in the scheduling is determined in rejecting by artificial experience, therefore, can generate more rapidly hardware circuit like this, and effectively reduce the interconnection expense in the hardware circuit.
Another beneficial effect of the present invention is: the application of the invention, when operation dispatching, not only comprise the hardware resource information of number, the information that also comprises the hardware interconnection, and the operation of resource constraint in the scheduling is determined in rejecting by artificial experience, therefore, can generate more rapidly hardware circuit like this, and effectively reduce the interconnection expense in the hardware circuit.
Description of drawings
Below in conjunction with accompanying drawing the specific embodiment of the present invention is described further:
Fig. 1 is flow chart of steps of the present invention;
Fig. 2 is the substep process flow diagram of step B of the present invention;
Fig. 3 is data flow diagram schematic diagram of the present invention;
Fig. 4 is compatible figure schematic diagram of the present invention;
Fig. 5 is the longest path schematic diagram of compatible figure in the predistribution of the present invention;
Fig. 6 is the resource constraint tabulation schematic diagram that generates in the predistribution of the present invention;
Fig. 7 is system chart of the present invention;
Fig. 8 is the subsystem diagram of predistribution of the present invention unit.
Embodiment
By Fig. 1 and Fig. 2 as can be known, a kind of high-level synthesis method, described method step comprises:
A, obtain the digital circuit behavior description, and then the generated data flow graph;
B, according to data flow diagram, carry out hardware resource predistribution, and then generate the resource constraint tabulation;
C, according to resource constraint tabulation and data flow diagram, dispatch;
D, carry out resource according to the result of scheduling and distribute;
E, generate hardware circuit according to resource allocation result and scheduling result.
Above-mentioned data flow diagram as shown in Figure 3, node represents dissimilar operation among the figure, arrow represents the direction of data stream, namely each the operation between data dependence relation; Described scheduling be will operation allotment to the process in each control step, it is corresponding functional unit to be distributed in operation calculate, variable is distributed to that specific functional unit is stored and interconnection line distributed to the process that the interconnect resource such as Port Multiplier, bus communicate that described resource is distributed.
Be further used as preferred embodiment, described step B adopts compatible nomography to carry out predistribution.
Be further used as preferred embodiment, described step B comprises:
B1, make up compatible figure according to data flow diagram, and set up the resource constraint tabulation;
B2, search longest path according to compatible figure;
The longest path that B3, basis are searched is put into the resource constraint tabulation successively with each node that described longest path relates to;
The longest path that B4, basis are searched is deleted node and the limit that relates in the described longest path in compatible figure, and the weight on remaining each limit among the compatible figure is recomputated;
B5, judge whether also there is node among the compatible figure, if exist, return execution in step B2; If do not exist, represent that namely all nodes all have been placed in the resource constraint tabulation among the compatible figure, generate the resource constraint tabulation, step B finishes, and represents that namely predistribution finishes.
Be further used as preferred embodiment, described step B2 adopts longest path algorithm to search longest path.
Be further used as preferred embodiment, described step B1 makes up the weight on the limit and each limit that comprise the node that makes up compatible figure, compatible figure among the compatible figure.The node of described compatible figure is the same with the node of described data flow diagram, all represents dissimilar operation.
Be further used as preferred embodiment, whether the limit of described compatible figure is according to existing data dependence relation or common input end mouth to make up between two nodes.
Be further used as preferred embodiment, the computing method that make up each limit weight are:
W=（α*dependency
i,j+β*NIN
i,j）
Wherein α, β are coefficient, dependency
I, jBe Boolean, i and j are any two nodes, if node i and j have data dependence relation, and dependency then
I, jBeing 1, then is not 0; NIN
I, jBe integer, the input port number that representation node i and j are common.
For example, as shown in Figure 4, step B is the predistribution of carrying out about add operation, and the node among the compatible figure represents an add operation, and every limit represents two operations and has the possibility of sharing same hardware resource.Therefore, have as seen from the figure four add operations, correspond respectively to the node (n1, n2, n3 and n5) among the compatible figure.In addition, operation n1, n2 and n3 and operation n5 have data dependence relation, and operation n2 and n3 have common input port, so utilize the limit that above-mentioned relation is showed.Next need to calculate the weight on every limit, take limit n2 → n3 as example, because there is not data dependence relation between them, so dependency
N2, n3Be 0, again because have a common input port in_3 between them, so NIN
N2, n3Be 1.Choose α=1 here, β=2, therefore, the weight of limit n2 → n3 is W
N2, n3=(α * dependency
N2, n3+ β * NIN
N2, n3)=(1 * 0+2 * 1)=2.
As shown in Figure 5, it is the longest path schematic diagram of compatible figure in the predistribution.It is according to compatibility figure shown in Figure 4, longest path n2 → n3 that employing longest path algorithm (The Longest Path Algorithm) is searched in compatible figure → n5.
Resource constraint tabulation as shown in Figure 6, it represents all add operations among the compatible figure, and namely all nodes need to use two totalizers, wherein operate n2, n3 and n5 and share a totalizer, and operation n1 uses a totalizer.
By Fig. 7 and Fig. 8 as can be known, a kind of High Level Synthesis system comprises:
The data flow diagram generation unit is used for obtaining the digital circuit behavior description, and then the generated data flow graph;
The predistribution unit is used for according to data flow diagram, carries out hardware resource predistribution, and then generates the resource constraint tabulation;
Scheduling unit is used for dispatching according to resource constraint tabulation and data flow diagram;
Resource allocation unit is used for carrying out the resource distribution according to the result of scheduling;
The circuit evolving unit is used for generating hardware circuit according to resource allocation result and scheduling result.
Be further used as preferred embodiment, described predistribution unit comprises:
Composition table module is used for making up compatible figure according to data flow diagram, and sets up the resource constraint tabulation;
Search module, be used for searching longest path according to compatible figure;
Modified module, be used for according to the longest path of searching, each node that longest path relates to is put into the resource constraint tabulation successively, and in compatible figure, delete node and the limit that relates in the longest path, and the weight on remaining each limit among the compatible figure is recomputated;
Judge execution module, be used for judging whether compatible figure also exists node, if exist, return and search module; If do not exist, generate the resource constraint tabulation, and provide resource constraint to tabulate to scheduling unit.
More than be that better enforcement of the present invention is specified, but the invention is not limited to described embodiment, those of ordinary skill in the art make all equivalent variations or replacement also can doing under the prerequisite of spirit of the present invention, the distortion that these are equal to or replace all is included in the application's claim limited range.
Claims (4)
1. high-level synthesis method, it is characterized in that: the method step comprises:
A, obtain the digital circuit behavior description, and then the generated data flow graph;
B, according to data flow diagram, carry out hardware resource predistribution, and then generate the resource constraint tabulation;
C, according to resource constraint tabulation and data flow diagram, dispatch;
D, carry out resource according to the result of scheduling and distribute;
E, generate hardware circuit according to resource allocation result and scheduling result;
Described step B adopts compatible nomography to carry out predistribution;
Described step B comprises:
B1, make up compatible figure according to data flow diagram, and set up the resource constraint tabulation;
B2, search longest path according to compatible figure;
The longest path that B3, basis are searched is put into the resource constraint tabulation successively with each node that described longest path relates to;
The longest path that B4, basis are searched is deleted node and the limit that relates in the described longest path in compatible figure, and the weight on remaining each limit among the compatible figure is recomputated;
B5, judge whether also there is node among the compatible figure, if exist, return execution in step B2; If do not exist, generate the resource constraint tabulation, step B finishes;
Described step B1 makes up the weight on the limit and each limit that comprise the node that makes up compatible figure, compatible figure among the compatible figure;
The computing method that make up each limit weight are:
W
i,j=（α*?dependency
i,j+β*NIN
i,j）
Wherein α, β are coefficient, dependency
I, jBe Boolean, i and j are any two nodes, if node i and j have data dependence relation, and dependency then
I, jBeing 1, then is not 0; NIN
I, jBe integer, the input port number that representation node i and j are common.
2. a kind of high-level synthesis method according to claim 1 is characterized in that: described step B2 adopts longest path algorithm to search longest path.
3. described a kind of high-level synthesis method according to claim 1, it is characterized in that: whether the limit of described compatible figure is according to existing data dependence relation or common input end mouth to make up between any two nodes.
4. High Level Synthesis system, it is characterized in that: described system comprises:
The data flow diagram generation unit is used for obtaining the digital circuit behavior description, and then the generated data flow graph;
The predistribution unit is used for according to data flow diagram, carries out hardware resource predistribution, and then generates the resource constraint tabulation;
Scheduling unit is used for dispatching according to resource constraint tabulation and data flow diagram;
Resource allocation unit is used for carrying out the resource distribution according to the result of scheduling;
The circuit evolving unit is used for generating hardware circuit according to resource allocation result and scheduling result;
Described predistribution unit comprises:
Composition table module is used for making up compatible figure according to data flow diagram, and sets up the resource constraint tabulation;
Search module, be used for searching longest path according to compatible figure;
Modified module, be used for according to the longest path of searching, each node that longest path relates to is put into the resource constraint tabulation successively, and in compatible figure, delete node and the limit that relates in the longest path, and the weight on remaining each limit among the compatible figure is recomputated;
Judge execution module, be used for judging whether compatible figure also exists node, if exist, return and search module; If do not exist, generate the resource constraint tabulation, and provide resource constraint to tabulate to scheduling unit;
Make up the weight on the limit and each limit that comprise the node that makes up compatible figure, compatible figure among the compatible figure, the computing method that make up each limit weight are:
W
i,j=（α*?dependency
i,j+β*NIN
i,j）
Wherein α, β are coefficient, dependency
I, jBe Boolean, i and j are any two nodes, if node i and j have data dependence relation, and dependency then
I, jBeing 1, then is not 0; NIN
I, jBe integer, the input port number that representation node i and j are common.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 201110423313 CN102419789B (en) | 2011-12-16 | 2011-12-16 | High-level synthesis method and system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 201110423313 CN102419789B (en) | 2011-12-16 | 2011-12-16 | High-level synthesis method and system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102419789A CN102419789A (en) | 2012-04-18 |
| CN102419789B true CN102419789B (en) | 2013-05-01 |
Family
ID=45944200
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN 201110423313 Expired - Fee Related CN102419789B (en) | 2011-12-16 | 2011-12-16 | High-level synthesis method and system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102419789B (en) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102722460B (en) * | 2012-05-02 | 2015-02-04 | 中山大学 | Nonequilibrium multiplexer in high-level synthesis and construction method thereof |
| CN103077283B (en) * | 2013-01-16 | 2016-05-18 | 清华大学 | The C-to-RTL integrated approach of optimizing based on VFI |
| CN104408232B (en) * | 2014-10-30 | 2017-12-05 | 中山大学 | A kind of combinatory logic optimization method and system in High Level Synthesis |
| CN104360906B (en) * | 2014-10-31 | 2017-10-13 | 中山大学 | A kind of High Level Synthesis dispatching method based on difference constrained system Yu iteration mould |
| CN105005638B (en) * | 2015-06-04 | 2018-06-26 | 广东顺德中山大学卡内基梅隆大学国际联合研究院 | A kind of High Level Synthesis dispatching method based on linear delay model |
| CN115422876A (en) * | 2022-08-29 | 2022-12-02 | 中山大学 | High-Level Synthesis Process Layout Method |
| CN115526135A (en) * | 2022-10-09 | 2022-12-27 | 中山大学 | High-level comprehensive tool optimization method and system based on differential constraint system |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5502645A (en) * | 1993-11-05 | 1996-03-26 | Nec Usa, Inc. | Behavioral synthesis for reconfigurable datapath structures |
| US6925628B2 (en) * | 2002-10-22 | 2005-08-02 | Matsushita Electric Industrial Co., Ltd. | High-level synthesis method |
| WO2005114499A1 (en) * | 2004-05-24 | 2005-12-01 | Matsushita Electric Industrial Co., Ltd | Method and apparatus for allocating data paths |
| JP4397744B2 (en) * | 2004-06-25 | 2010-01-13 | パナソニック株式会社 | Method for high-level synthesis of semiconductor integrated circuit |
| JP2009157440A (en) * | 2007-12-25 | 2009-07-16 | Toshiba Corp | High level synthesizer, high level synthesizing system, and high level synthesizing method |
| CN102043886B (en) * | 2010-12-31 | 2012-10-24 | 北京大学深圳研究生院 | Underlying hardware mapping method for integrated circuit as well as time sequence constraint method and device for data control flow |
-
2011
- 2011-12-16 CN CN 201110423313 patent/CN102419789B/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN102419789A (en) | 2012-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102419789B (en) | High-level synthesis method and system | |
| Basanta-Val et al. | Improving the predictability of distributed stream processors | |
| Zhu et al. | New stability criteria for continuous-time systems with interval time-varying delay | |
| US20200097487A1 (en) | Novel olap pre-calculation model and modeling method | |
| WO2021159929A1 (en) | Topology diagram conversion system and method | |
| Vydyanathan et al. | Optimizing latency and throughput of application workflows on clusters | |
| Zhang et al. | A customized two-stage parallel computing algorithm for solving the combined modal split and traffic assignment problem | |
| Menard et al. | High‐Level Synthesis under Fixed‐Point Accuracy Constraint | |
| CN106682258A (en) | Method and system for multi-operand addition optimization in high-level synthesis tool | |
| Guarneri et al. | Optimization of nonhierarchically decomposed problems | |
| JP2009211614A (en) | Behavioral synthesis device, behavioral synthesis method, and program | |
| CN104168325A (en) | Distributed Web service selection method with self-maintenance function | |
| Jun et al. | Topology synthesis of cascaded crossbar switches | |
| Kim et al. | Adjustable delay buffer allocation under useful clock skew scheduling | |
| Ewetz et al. | Fast clock scheduling and an application to clock tree synthesis | |
| CN103164230A (en) | Requirement modeling method based on new characteristic model and model transformation method | |
| US20070250803A1 (en) | High-level synthesis method and high-level synthesis system | |
| Vydyanathan et al. | An approach for optimizing latency under throughput constraints for application workflows on clusters | |
| Mittal et al. | Design exploration and implementation of simplex algorithm over reconfigurable computing platforms | |
| Benoit et al. | Computing the throughput of replicated workflows on heterogeneous platforms | |
| Sinha et al. | Dataflow graph partitioning for high level synthesis | |
| CN119149241B (en) | Data processing method, device, equipment and readable storage medium | |
| CN113221250B (en) | Efficient data scheduling method suitable for remote sensing image ship on-orbit detection system | |
| Gao et al. | On the power of combiner optimizations in mapreduce over MPI workflows | |
| Zhu | Work-in-progress: equivalence of transformations of synchronous data flow graphs |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20130501 Termination date: 20151216 |
|
| EXPY | Termination of patent right or utility model |