CN101101610A - Large scale integrated circuit division method based on multi-level division method - Google Patents

Abstract

The invention relates to a large-scale integrated circuit division method based on a multi-level division method. The division method improves the multi-level division method, realizes the conversion of a circuit line network into an undirected graph, and saves it as an undirected graph with weights. graph file, and then start the undirected graph multi-level division program to divide the generated undirected weighted graph. Adopting the division method of the present invention not only effectively improves the efficiency of circuit division, but also remarkably improves the performance of circuit division, and has better practicability.

Description

Large scale integrated circuit division method based on multi-level division method

Technical field:

The invention relates to a large-scale integrated circuit division method based on a multi-level division method for designing large-scale integrated circuits.

Background technique:

Circuit division plays an important role in the design of large-scale integrated circuits using hardware description languages. With the rapid development of integration technology, it has become a reality to integrate hundreds of thousands or even millions of gate circuits on a chip. Therefore, the use of circuit division in large-scale integrated circuit design effectively reduces the need for simulation or synthesis of integrated circuits. complexity and other requirements. Circuit division is also an important part of hierarchical design thinking. Circuits can be divided at different levels: system-level division divides a system into a group of printed circuit boards, and board-level division divides circuits on printed circuit boards into one Group chips, and perform chip-level division to divide the circuits in the chip into smaller circuits. Another important reason for circuit division is to meet the packaging requirements. The relationship between the number of gates in the circuit and the number of input and output pins is constrained by the Rent rule. The number of output pins on each chip and the number of gate circuits cannot Unlimited increase, coupled with the encapsulation requirements for large-scale integrated circuits, so large-scale integrated circuits must be divided. To study a good circuit division method is a necessary condition to improve the performance of LSI division system.

See also shown in Fig. 1, the circuit division method in the circuit division system of prior art, the first step, describe the divided circuit 101 with hardware description language, obtain circuit source code 102; The second step, the source code of lexical analysis circuit , to obtain the corresponding word symbol 103; the third step is to perform grammatical analysis on the basis of lexical analysis to obtain the corresponding grammatical phrase 104; the fourth step is to perform semantic analysis on the basis of grammatical analysis to obtain the corresponding type information 105; the fifth Step 1, generate intermediate codes based on semantic analysis, and construct corresponding circuit nets 106; Step 6, call division program 109 to divide the circuits according to the nets generated by the intermediate codes; Step 7, modify the corresponding circuit nets according to the division results The net is to obtain the modified net 107; the eighth step is to perform circuit output on the modified net to obtain the divided circuit description source code 108.

There are several division methods of logic circuits in the circuit division system of the prior art. These division methods are realized from different aspects such as the minimum number of interconnection lines and the uniform distribution of the number of logic units in the circuit subset after division, wherein:

A partitioning method based on migration, firstly, a random initial partition of the circuit is generated, and the same circuit logic unit cannot belong to two circuit subsets at the same time. In the migration optimization stage, the division method selects one circuit logic unit in each of the two circuit subsets for pair-wise exchange. process to maximize the quality of circuit partitioning. In this process, the division method records the circuit division results at the moment when the cutting reaches the minimum value, and once the two selected circuit logic units are exchanged, in the remaining optimization and improvement of the entire migration process, the two circuit logic units are locked so that They are no longer selected, and the above process is repeated until all possible circuit logic units have been migrated, and then rolled back to the moment when the cumulative benefit is the largest, that is, the cutting minimum value. The circuit division results obtained by this program are unstable and highly discrete, which limits the scale of the problem that can be solved by this division method.

Another horizontal nesting division method, first, select a circuit logic unit, mark this circuit logic unit with 0, then mark those circuit logic units connected to this circuit logic unit with 1, and then for those that have not been marked number, but the circuit logic unit adjacent to the numbered circuit logic unit is labeled as the number of the connected circuit logic unit plus 1; until half of the circuit logic unit is marked with a number, the labeling process is just over. Those sets of circuit logic units marked with numbers are set as a circuit subset, and other circuit logic units are another circuit subset. Only when the selected initial circuit logic unit is close to the periphery of this division method, the obtained circuit division result is relatively good, so the obtained circuit division result is also unstable.

There is also a multi-level division method. First, random matching is used to combine some circuit logic units together to obtain a roughened circuit diagram of the next level. This process is repeated until the roughened circuit diagram is small enough to obtain a minimum circuit diagram. Then, the minimal circuit diagram is bisected by the partition method to obtain an initial two-partition. After that, after projecting from the minimum circuit diagram back to the initial circuit diagram, in the refined circuit division of each horizontal layer, the circuit logic unit with the largest profit value is selected according to the greedy principle for migration optimization, and the final circuit division result is obtained. Compared with the above two methods, this division method is more suitable for VLSI division. However, due to the random strategy for matching and the greedy principle for optimization, the ability to escape from local optimum is limited.

Invention content:

The purpose of the present invention is to provide an improved LSI division method based on the multi-level division method to improve the efficiency and performance of LSI division in view of the deficiencies in the prior art. For achieving the above object, design of the present invention is as follows:

Realize the conversion of the circuit line network into the undirected graph, and save it as an undirected graph file with weights, and then start the multi-level division program of the undirected graph to divide the generated weighted undirected graph.

In the coarsening stage of the multi-level partition method, by sorting the kernel values of all nodes in the weighted undirected graph for the node attributes, based on the non-strict descending order of the node kernel values, access the unmatched state according to this order. Nodes are matched according to certain rules, so that nodes with good connectivity are merged together.

In the optimization stage of the multi-level partition method, the immune cloning optimization program is used to improve the local search method of the greedy principle, and the partition of the map projection at each level is optimized. The clone selection operation enables the improved method to search the potential solution space more freely while using the heuristic information to search for the local optimal solution, increasing the global search ability.

According to the above-mentioned inventive concept, the technical solution of the present invention is realized as follows: a large-scale integrated circuit division method based on multi-level division method, characterized in that, the specific steps are as follows,

Step 1, describe the circuit with a hardware description language, and generate the source code of the circuit;

Step 2, lexical analysis, reads the source code of the circuit one by one from left to right, scans and decomposes the character stream constituting the source code, so as to identify each word;

Step 3, grammatical analysis, decomposes the word sequence into various grammatical phrases on the basis of lexical analysis, and determines whether the entire character stream constitutes a grammatically correct program according to the grammatical rules of the hardware description language;

Step 4, semantic analysis, check whether the source code has semantic errors on the basis of grammatical analysis, and collect type information for the intermediate code generation stage;

Step 5, intermediate code generation, on the basis of syntax analysis and semantic analysis, generate intermediate code from the source code, and express it in an internal intermediate format;

Step 6, generate an undirected graph file with weights, construct the network corresponding to the circuit described in the text based on the intermediate code, and save it as an undirected graph file with weights after converting the circuit network to an undirected graph;

Step 7, divide the undirected graph, start the multi-level division program of the undirected graph, read the undirected graph file with weights, divide the generated weighted graph, and store the final division result in the undirected graph division file middle;

Step 8, modifying the network, after detecting that the undirected graph division program has completed the division, reading the corresponding division result from the undirected graph division file, and modifying the corresponding network of the circuit according to the division information;

Step 9, outputting the circuit, traversing the modified net, and storing the obtained circuit division results in the circuit description file in a hardware description language.

The operation procedure of the above step 6 is:

6.1 Construct the circuit source code based on the intermediate code to describe the network corresponding to the circuit, and generate a complete circuit network; a complete circuit network is regarded as a root module, which is composed of hierarchical sub-module instances and circuit logic units through signal interconnection , and each sub-module is composed of ports, circuit logic units, and instances of nested sub-modules through signal connections;

6.2 Traverse the complete circuit network, and name the identification number of the basic circuit logic unit in the circuit; establish the signal connection mode between each logic unit, and realize the conversion to the undirected graph. The point V _i is represented, and the signal in the figure is represented by the side E _j ; the weight of the node V _i represents the size of the logic unit of the basic circuit, and the weight of the side E _j represents the weight of the signal connection conversion between the logic units of the basic circuit ;

6.3 Save the converted undirected graph as an undirected graph file with weights.

The operation procedure of the above-mentioned step 7 is:

7.1 Read the undirected graph file with weights, and store the graph in a compressed storage format;

7.2 Enter the coarsening stage of the multi-level partition method, use the matching program to combine some nodes together to obtain the coarsening graph of the next level, repeat this process until the coarsening graph is small enough, that is, a minimum graph is obtained ;

7.3 Enter the initial division stage of the multi-level division method, initialize the antibody population, wherein each antibody in the antibody population uses the division procedure to obtain an initial two-division, and uses the immunization operation to optimize the initial two-division;

7.4 Enter the optimization stage of the multi-level partition method, project from the minimum map back to the initial map, set the clone scale parameters in the detailed map of each horizontal layer, and use the immune cloning optimization program to optimize the partition;

7.5 Store the final division result in the undirected graph division file.

In the above step 7.2, the matching procedure is:

7.2.1 All nodes in the annotation graph are in an unmatched state;

7.2.2 Solve the kernel value of all nodes in the graph based on node attributes;

7.2.3 Perform a non-strict descending sort according to the core value of the node, and visit the node v in the unmatched state according to this order; if the node v has unmatched adjacent nodes, then select the unmatched state and the weight The adjacent node u and node v of the side with the largest value match, and mark these two nodes as the matching state; if all the adjacent matching nodes of node v are in the matching state, then the node v is still in the unmatched state. During the coarsening process, it is directly copied to the coarsening map of the next horizontal layer;

7.2.4 Repeat the previous step until the visit ends.

In the above-mentioned step 7.4, the immune cloning optimization procedure described is:

7.4.1 Project the optimized division of the antibody population in the coarsened map of the previous level back to the refined map of the current layer as the initial division of the antibody population in the current layer;

7.4.2 Set the optimal division in the initial division of the antibody population as the optimal division of the population BEST, and set the cycle counter COUNTER of the immune cloning program to zero;

7.4.3 Calculate the affinity of the antibody population, and perform cloning operations, cloning mutation operations, immunization operations, and clone selection operations for each antibody in the antibody population according to the set antibody cloning scale parameters;

7.4.4 If the optimal division in the new antibody population is better than the optimal division BEST of the population, update the optimal division BEST of the population;

7.4.5 Add one to the loop counter COUNTER;

7.4.6 Repeat steps 7.4.3, 7.4.4, 7.4.5 until the loop counter COUNTER reaches the given upper limit.

The operation procedure of the above-mentioned step 8 is:

8.1 Read the corresponding division results stored in the undirected graph division file;

8.2 By modifying the network corresponding to the circuit, the basic circuit logic unit corresponding to the division result is moved to the specified module.

Compared with the prior art, the present invention has the following obvious outstanding substantive features and significant advantages:

1. Improve the efficiency of circuit division

The method for dividing large-scale integrated circuits based on the multi-level division method of the present invention realizes the conversion from the circuit line network to the undirected graph file with weights, and then starts the multi-level division program of the undirected graph to carry out the weighted undirected graph generated Division, thus avoiding the division method to directly divide the circuit network, and after obtaining a better division result by setting the parameters of the division method, modify the circuit network, thereby effectively improving the efficiency of circuit division.

2. Improved the performance of circuit division

The large-scale integrated circuit division method based on the multi-level division method of the present invention, because in the coarsening stage of the multi-level division method, the node attributes are used to match according to certain rules, so that the nodes with good connectivity are combined to maximize Reduce the number of edges and the sum of edge weights, which is conducive to obtaining a good initial division in the initial division stage, and optimizing the projection of the initial division in the optimization phase. The present invention is based on the large-scale integrated circuit division method of the multi-level division method. In the optimization stage of the multi-level division method, the immune cloning optimization program is used to improve the local search method of the greedy principle, and the division of the map projection of each level is optimized, which is effective. Find better circuit division results than the existing technology, and finally significantly improve the performance of circuit division.

Description of drawings:

Through the following description of the large-scale integrated circuit division method based on the multi-level division method in conjunction with the accompanying drawings, the purpose, specific structural features and advantages of the present invention can be further understood.

FIG. 1 is a program block diagram of a circuit division method in a prior art circuit division system.

Fig. 2 is a program block diagram of the large-scale integrated circuit division method based on the multi-level division method of the present invention.

Fig. 3 is a program block diagram of the compressed storage format for storing the weighted undirected graph file in the present invention.

Figure 4 is a flow chart of the matching procedure implemented in the coarsening phase of the present invention.

Fig. 5 is a flow chart of the immune cloning optimization program implemented in the optimization phase of the present invention.

Fig. 6 is a flow chart of the operation of implementing the immunization vaccine of the present invention.

Fig. 7 is a table of experimental results comparing the present invention with the prior art undirected graph partition program MeTiS based on the multi-level partition method.

Detailed ways:

In order to understand more clearly the technical content of the large-scale integrated circuit division method based on the multi-level division method of the present invention, the following examples are given in detail.

Please refer to shown in Figure 2, describe the divided circuit 201 with a hardware description language, and obtain the circuit source code 202; lexically analyze the source code of the circuit to obtain the corresponding word symbol 203; perform grammatical analysis on the basis of the lexical analysis to obtain the corresponding Grammatical phrase 204; perform semantic analysis on the basis of grammatical analysis to obtain corresponding type information 205; construct corresponding internal intermediate code 206 on the basis of semantic analysis; construct a line network 207 corresponding to a circuit described in text based on internal intermediate code, and pass After the conversion of the circuit line network to the undirected graph, save it as an undirected graph file 210 with weights; start the undirected graph multi-level division program 216, read the undirected graph file with weights, and obtain the compressed storage format storage Figure 212 of the multi-level division method; enter the coarsening stage of the multi-level division method, call the matching program 217, combine some graph nodes together, and obtain the coarser diagram 213 of each horizontal layer; enter the initial division of the multi-level division method stage, call the division program 218 to divide the minimum graph into two parts, and obtain the initial two-partition 214 of the minimum graph; enter the optimization stage of the multi-level partition method, project the minimum graph back to the initial graph, and in the refinement graph of each horizontal layer, Call the optimization program 219 to optimize the division, and obtain the optimized division 215 of each horizontal layer refinement graph; store the final initial graph division result as an undirected graph division file 211; after detecting that the undirected graph division program completes the division , read the corresponding division result from the undirected graph division file, modify the network corresponding to the circuit according to the division information, and obtain the modified network 208 corresponding to the division result; traverse the modified network, and obtain the circuit division result as The hardware description language is stored as a circuit description file 209 .

For the weighted undirected graph file of the multi-level division method, the compressed storage format of this embodiment is shown in FIG. 3 . The storage structure uses the xadj array 303 to store node information, and uses the adjncy array 302 to store adjacent node information. Assuming that the array address starts from zero, and the node number starts from zero, then the adjacent node list of the i-th node is stored in the array adjncy, and the position is from the array adjncy[xadj[i]] to adjncy[xadj[i+1] -1]. The legend 301 contains a total of 7 nodes and 12 edges, and the adjncy array 302 stores the list of adjacent nodes of each node, so the size is 24. The xadj array 303 specifies the start and end positions of each node corresponding to the adjacent node list, and the start position of the i-th node is the end position of the i-1-th node, so the size is 8. When the graph is an undirected graph with weights, the compressed storage structure uses the vwgt array 305 to store the weight information of the nodes, whose size is the number of nodes; uses the adjwgt array 304 to store the information of the edge weights, whose size is the number of edges twice, and used in conjunction with the array adjncy that stores adjacent node information. The weight of the i-th node is stored in vwgt[i], and the weight information of the edge between the i-th node and the adjacent node adjncy[j] is stored in adjwgt[j].

For the coarsening stage of the multi-level division method, the specific flow of the matching program in this embodiment is shown in Figure 4, and the steps are as follows:

A01: All nodes in the annotation graph are in an unmatched state;

A02: Solve the kernel values of all nodes in the graph based on node attributes. The attributes of nodes can be the in-degree, out-degree, degree, sum of node edge weights, and the largest node edge weight. value etc;

A03: Sort in non-strict descending order according to the core value of the node;

A04: According to this order, whether the visit to the unmatched nodes is finished; if the visit is not finished, that is, there is a node v that has not been visited, then go to step A05; otherwise, the visit ends, and the matching procedure ends;

A05: Whether all the adjacent nodes of node v are in the matching state; if there are adjacent nodes that are not matched, go to step A06; otherwise, all the adjacent nodes of node v are in the matching state, go to step A11;

A06: Select the adjacent node that is in the non-matching state and has the largest weight as the candidate node;

A07: If there are multiple candidate nodes, go to step A08, otherwise there is only a single candidate adjacent node, go to step A10;

A08: Select the adjacent node u with the larger kernel value among multiple candidate nodes;

A09: The node v and the adjacent node u are matched and merged. The weight of the merged node is the sum of the weight of the node v and the adjacent node u. The edge of the merged node is the node v and the adjacent node. Merge of side u, go to step A04;

A10: Select a single candidate adjacent node u, go to step A09;

A11: The node v is still in the unmatched state, and it is directly copied to the coarsening graph during the coarsening process, and then go to step A04.

For the optimization stage of the multi-level division method, the specific flow of the immune cloning optimization program in this embodiment is shown in Figure 5, and the steps are as follows:

B01: Project the optimized division of the antibody population in the coarsening map of the previous level back to the refined map of the current layer as the initial division of the antibody population in the current layer;

B02: Set the optimal division in the initial division of the antibody population as the optimal division of the population BEST;

B03: The cycle counter COUNTER of the immune cloning program is set to zero;

B04: If the loop counter COUNTER reaches the given upper limit, the optimization program ends, otherwise go to step B05;

B05: Calculate the affinity of the antibody population;

B06: Perform cloning operation on each antibody in the antibody population according to the set antibody cloning scale parameters;

B07: Perform clonal mutation operation for each antibody in the antibody population;

B08: Each antibody in the antibody population is immunized with vaccines;

B09: The antibody population is cloned and selected according to the principle of optimal division;

B10: If the optimal division in the new antibody population is better than the optimal division BEST of the population, then go to step B11, otherwise go to step B12;

B15: Update the optimal division of the population BEST to the optimal division in the new antibody population;

B16: Add one to the loop counter COUNTER, go to step B06;

A calculation formula that can be used for reference when calculating the similarity between the two antibodies in step B05 is as follows:

${\mathrm{D.}}_{A_1{\mathrm{<figure-callout\; id="2"\; label="A"\; filenames="A20071004376500161.png"\; state="\{\{state\}\}">A</figure-callout>}}_2}=2*(0.5+|\frac{\underset{v\&Element;V}{\mathrm{\&Sigma;}}{S}_{A_1{A}_2}\left(V\right)}{\left|V\right|}-0.5\left|\right)+1$ in $S_{A_1{A}_2}\left(V\right)=\left\{\begin{array}{c}1,P_{A1}\left[V\right]=P_{A2}\left[V\right]\\ 0,\mathrm{otherwise}\end{array}\right.$

In the above formula, D _A1A2 represents the similarity between antibodies A ₁ and A ₂ , V represents the node set of the undirected graph, and P _A1 and P _A2 represent the storage division of antibodies A ₁ and A ₂ respectively;

When the k-th generation cloning operation is performed on each individual in the antibody population in step B06, a calculation formula for the cloning scale q _i (k) of the antibody A _i can be referred to as follows:

${\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; Int</span>}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\frac{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}{\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; \&Theta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ]</span>$

In the above formula, q _i (k) represents the cloning scale of the kth generation antibody A _i , n _c represents the setting value related to the cloning scale, and f(A _i (k)) represents the antigen affinity of the antibody A _i . _i stores and divides the cut value calculation;

Θ _i represents the affinity between antibody A _i and other antibodies, and Int(x) represents the smallest integer greater than x.

For the initial division phase and optimization phase of the multi-level division method, the antibody inoculation immunization vaccine operation in this embodiment, by analyzing the characteristic information based on the current division, that is, the income value of the boundary node, is made and vaccinated according to the principle of greed, so that in the vaccination The quality of the new antibody after the immunization vaccine operation is improved. A specific implementation method for reference is shown in Figure 6. The steps are as follows:

C01: Use the currently saved division of the antibody as the initial division P;

C02: Set the antibody optimal division GOOD to the initial division P and set the cycle counter I to zero;

C03: Based on the given initial partition P, calculate the degree of in-connection and out-of-connection of all nodes;

C04: Calculate the migration income value of all boundary nodes;

C05: Insert the revenue values of all boundary nodes into the hash data structures of the two node subsets;

C06: If the loop counter I reaches the given upper limit, the program ends, otherwise go to step C07;

C07: Enter the migration process, and the migration direction is from the heavy side to the light side of the sum of the node subsets in the division;

C08: From the hash data structure on the side where the starting point of the current migration direction is located, select the node with the largest profit value as the migrated node according to the greedy principle;

C09: Migrate the node v and calculate the cut of the new division;

C10: Recalculate the in-connection degree and out-of-connection degree of adjacent nodes of node v;

C12: Update the income value of adjacent nodes in the hash structure; if the adjacent node u becomes a boundary node due to the migration of node v, then insert the income value into the hash structure of the node subset where node u is located ; If node u becomes a non-boundary node due to the migration of node v, then delete the income value from the node subset hash structure where node u is located; if node u is always a boundary node before and after migration, then only need Update the revenue value in the hash structure;

C14: If the current division is better than the antibody optimal division GOOD, then go to step C15, otherwise go to step C16;

C15: Update the antibody optimal division GOOD to the current division;

C16: add one to the loop counter 1, turn to step C06;

In this embodiment, the large-scale integrated circuit division method based on the multi-level division method is realized by using ANSIC, the operating system is WIN2000, runs on the 1800MHZ AMD Althon2200 chip, and the memory is 512M. The test reference circuit used in the experimental program is the 18-group circuit test reference ISPD98 given by Professor Alpert of IBM's Austin Research Laboratory in 1998. ISPD98 is obtained through conversion based on a series of internal electronic products given by IBM's Austin, Burlington, and Rochester design departments, including bus arbitrators, bus bridge chips, memory and peripheral component expansion bus interfaces, communication adapters, memory controllers, processing and graphics adapters, etc. The existing comparative technology for evaluating the present invention is the well-known undirected graph partition program MeTiS based on the multi-level partition method, provided by Professor Karypis of the University of Minnesota. In order to ensure the repeatability and impartiality of the experimental results, 20 comparative example verifications were carried out on each set of circuit test benchmark diagrams, and random number seeds and immune cloning optimization program parameters were fixedly selected. The population size was 8, and the cloning The coefficient of variation is 0.3, and the clone scale parameter is 24, that is, each antibody is cloned an average of 3 times. Since the collection of characteristic information and other calculations in the antibody vaccination operation is relatively large, in order to obtain the optimal approximate division within a reasonable time, the number of iterations is set to 15. For the experimental results, the evaluation indicators we use are the minimum value of the division cut (MinCut) and the average value of the division cut (AveCut) obtained in 20 instance verifications. In the table of FIG. 7, "node" is the number of basic circuit logic units in the test reference circuit, and "side" is the accumulation of signal weights. Experimental results have shown the good performance of the large-scale integrated circuit division method based on the multi-level division method of the present invention. Compared with MeTiS, the minimum value of division and division has been improved by 35.0%, and the average value of division and division has been improved by 55.1%. .

Claims (6)

1. a method for dividing large-scale integrated circuits based on multi-level division method, is characterized in that, concrete steps are as follows: Step 1, describe the circuit with a hardware description language, and generate the source code of the circuit; Step 2, lexical analysis, reads the source code of the circuit one by one from left to right, scans and decomposes the character stream constituting the source code, so as to identify each word; Step 3, grammatical analysis, decomposes the word sequence into various grammatical phrases on the basis of lexical analysis, and determines whether the entire character stream constitutes a grammatically correct program according to the grammatical rules of the hardware description language; Step 4, semantic analysis, check whether the source code has semantic errors on the basis of grammatical analysis, and collect type information for the intermediate code generation stage; Step 5, intermediate code generation, on the basis of syntax analysis and semantic analysis, generate intermediate code from the source code, and express it in an internal intermediate format; Step 6, generate an undirected graph file with weights, construct the network corresponding to the circuit described in the text based on the intermediate code, and save it as an undirected graph file with weights after converting the circuit network to an undirected graph; Step 7, divide the undirected graph, start the multi-level division program of the undirected graph, read the undirected graph file with weights, divide the generated weighted graph, and store the final division result in the undirected graph division file middle; Step 8, modifying the network, after detecting that the undirected graph division program has completed the division, reading the corresponding division result from the undirected graph division file, and modifying the corresponding network of the circuit according to the division information; Step 9, outputting the circuit, traversing the modified net, and storing the obtained circuit division results in the circuit description file in a hardware description language. 2. by the method for dividing the large-scale integrated circuit based on the multilevel division method described in claim 1, it is characterized in that, the operating procedure in described step 6 is: 6.1 Construct the circuit source code based on the intermediate code to describe the network corresponding to the circuit, and generate a complete circuit network; a complete circuit network is regarded as a root module, which is composed of hierarchical sub-module instances and circuit logic units through signal interconnection , and each sub-module is composed of ports, circuit logic units, and instances of nested sub-modules through signal connections; 6.2 Traverse the complete circuit network, and name the identification number of the basic circuit logic unit in the circuit; establish the signal connection mode between each logic unit, and realize the conversion to an undirected graph. _i represents that the signal in this figure is represented by a side E _j ; the weight of the node V _i represents the size of the logic unit, and the weight of the side E _j represents the weight of the signal connection conversion between the logic units; 6.3 Save the converted undirected graph as an undirected graph file with weights. 3. by the method for dividing the large-scale integrated circuit based on the multi-level division method described in claim 1, it is characterized in that, the operating procedure in described step 7 is: 7.1 Read the undirected graph file with weights, and store the graph in a compressed storage format; 7.2 Enter the coarsening stage of the multi-level partition method, use the matching program to combine some nodes together to obtain the coarsening graph of the next level, repeat this process until the coarsening graph is small enough, that is, a minimum graph is obtained ; 7.3 Enter the initial division stage of the multi-level division method, initialize the antibody population, wherein each antibody in the antibody population uses the division procedure to obtain an initial two-division, and uses the immunization operation to optimize the initial two-division; 7.4 Enter the optimization stage of the multi-level partition method, project from the minimum map back to the initial map, set the clone scale parameters in the detailed map of each horizontal layer, and use the immune cloning optimization program to optimize the partition; 7.5 Store the final division result in the undirected graph division file. 4. by the method for dividing the large-scale integrated circuit based on the multilevel division method described in claim 1, it is characterized in that, the operating procedure in described step 8 is: 8.1 Read the corresponding division results stored in the undirected graph division file; 8.2 By modifying the network corresponding to the circuit, the basic circuit logic unit corresponding to the division result is moved to the designated module. 5. by the method for dividing the large-scale integrated circuit based on multilevel division method described in claim 3, it is characterized in that, the matching program in described step 7.2 is: 7.2.1 All nodes in the annotation graph are in an unmatched state; 7.2.2 Solve the kernel value of all nodes in the graph based on node attributes; 7.2.3 Perform a non-strict descending sort according to the core value of the node, and visit the node v in the unmatched state according to this order; if the node v has unmatched adjacent nodes, then select the unmatched state and the weight The adjacent node u and node v of the side with the largest value match, and mark these two nodes as the matching state; if all the adjacent matching nodes of node v are in the matching state, then the node v is still in the unmatched state. During the coarsening process, it is directly copied to the coarsening map of the next horizontal layer; 7.2.4 Repeat the previous step until the visit ends. 6. by the method for dividing the large-scale integrated circuit based on the multilevel division method described in claim 3, it is characterized in that, the immune cloning optimization program in described step 7.4 is: 7.4.1 Project the optimized division of the antibody population in the coarsened map of the previous level back to the refined map of the current layer as the initial division of the antibody population in the current layer; 7.4.2 Set the optimal division in the initial division of the antibody population as the optimal division of the population BEST, and set the cycle counter COUNTER of the immune cloning program to zero; 7.4.3 Calculate the affinity of the antibody population, and perform cloning operations, cloning mutation operations, immunization operations, and clone selection operations for each antibody in the antibody population according to the set antibody cloning scale parameters; 7.4.4 If the optimal division in the new antibody population is better than the optimal division BEST of the population, update the optimal division BEST of the population; 7.4.5 Add one to the loop counter COUNTER; 7.4.6 Repeat steps 7.4.3, 7.4.4, 7.4.5 until the loop counter COUNTER reaches the given upper limit.

Images