CN103366029A - On-site programmable gate array chip layout method - Google Patents

Abstract

The invention provides a field programmable gate array chip layout method, which provides the structural information of the logic unit of the field programmable gate array chip and the netlist information of the logic module generated after packaging; Wiring resource map; according to the netlist information and the wiring resource map, the layout of the field programmable gate array chip is carried out, and the fast wiring is carried out at the same time. The invention performs fast wiring according to the wiring resource map in the layout process, closely combines the layout and wiring process, improves the success rate of wiring, reduces the delay of the circuit at the same time, and improves the utilization rate of wiring resources.

Description

A Field Programmable Gate Array Chip Layout Method

technical field

The invention relates to the fields of integrated circuit design and electronic design automation, in particular to a field programmable gate array chip layout method.

Background technique

FPGA (Field-Programmable Gate Array, Field Programmable Gate Array) chip is a programmable device widely used in the market, which has the advantages of short development cycle and low cost. Through the layout of logic modules and the wiring of interconnection lines between logic modules, FPGA chips can realize various applications. Therefore, in the software flow of FPGA design, layout and wiring are crucial steps. The layout determines the position of each logic module required to realize the circuit function in the FPGA chip, and the logic modules are connected by the wiring of the interconnection line. The optimization goal of the layout is to place the connected logic modules close to minimize the required At the same time, it is also necessary to balance the wiring density and circuit delay in the FPGA chip. After the layout of the FPGA chip is completed, the router can open appropriate programmable switches to connect the input and output pins of all logic modules required by the circuit, and complete the layout and wiring of the FPGA chip.

In an FPGA chip, the area of wiring accounts for more than 50% of the total area of the chip, and the delay of the wiring channel on the critical path after wiring is several to dozens of times larger than the logic delay of the logic module, which fully proves that in FPGA chips The importance of wiring. In most layout and routing tool software, the relationship between layout and routing is too loose. Usually, the interconnection lines used in the wiring stage cannot be predicted during layout, so the delay caused by the interconnection lines cannot be predicted, which eventually leads to FPGA chips. Latency increases.

At present, the best solution to reduce the delay of FPGA chips is to perform layout and routing at the same time. However, when the layout and routing are performed at the same time, the running time of the placement and routing tool software will increase by more than ten times, which seriously affects the placement and routing time of the FPGA chip. .

Contents of the invention

The object of the present invention is to provide a field programmable gate array chip layout method, realize the fast layout of the field programmable gate array chip and reduce the circuit delay.

The invention provides a field programmable gate array chip layout method, comprising steps:

Provide the structural information of the logic unit of the field programmable gate array chip and the netlist information of the logic module generated after packaging;

Establishing a wiring resource map according to the structural information of the logic unit of the chip;

According to the net list information and the wiring resource map, the layout of the field programmable gate array chip is carried out, and the fast wiring is carried out at the same time.

Preferably, said carrying out the layout of field programmable gate array chip according to said netlist information and wiring resource map, carry out fast wiring simultaneously, comprise the step:

random layout of the logic modules and fast pre-wiring, and setting the layout temperature, and storing the total number of times the interconnection lines are occupied in a data structure;

moving or exchanging the logic modules according to the netlist information for layout;

calculating a cost value for moving or swapping logic modules based on the layout temperature;

Perform fast local wiring on the moving or switching logic module according to the wiring resource map, and update the number of times interconnection lines are occupied in the data structure;

Calculating the cost value after the fast local wiring, and judging whether the move or exchange is accepted according to the change of the cost value;

Judging whether the layout temperature satisfies the set condition, if not, updating the layout temperature, performing the step of moving or exchanging the logic module according to the netlist information for layout; if yes, ending the layout.

Preferably, a path search algorithm is used for fast pre-wiring.

Preferably, the step of moving or exchanging the logic module according to the netlist information is:

Select the first module and the first module coordinates in the netlist information, wherein the first module is not constrained to a fixed position, the position of the first module is not in the first module coordinates, the type of the first module is consistent with the first module coordinates The module types at the coordinates of the first module mentioned above are the same;

If the coordinates of the first module are not occupied, move the first module to the coordinates of the first module; if the coordinates of the first module are occupied by the second module, the second module is not constrained to the first module coordinates, swap the first module and the second module.

Preferably, the step of calculating the cost value of moving or exchanging the logic module is:

A simulated annealing algorithm is used to calculate the cost value of moving or exchanging the logic module.

Preferably, performing fast local wiring on the moving or switching logic module according to the wiring resource map, specifically:

The wire nets used by the moved or swapped logic modules are traversed, and each wire net is quickly wired using a routing algorithm, and the routing algorithm is a path search algorithm.

Preferably, said providing the structural information of the logic unit of the field programmable gate array chip includes:

Provides the location of various types of logic cell blocks, pin names of logic cell blocks, pin positions, delays from input pins to output pins of logic cell blocks, width of routing channels, distribution and delay of interconnection segments And the position, type and delay of the wiring switch.

Preferably, the netlist information of the logic module generated after the logic unit of the field programmable gate array chip is packaged includes:

Provide the name and type of the logic module generated after the logic unit is packaged, the pins of the used logic unit block, and the source and drain terminals of all nets.

Preferably, the establishment of the wiring resource map according to the structural information of the logic unit of the chip includes:

According to the structural information of the logic unit of the chip, the connection relationship between the source end of the logic unit and the output pin of the logic module, the connection relationship between the drain end of the logic unit and the input pin of the logic module, and the connection between the input and output pins of the logic module and the interconnection line are established. Connection relationship, connection relationship between interconnection lines, connection relationship of logic units inside the same logic module, and connection relationship between other modules and interconnection lines.

Compared with prior art, method of the present invention has following advantage:

The FPGA chip layout method of the present invention provides the structure information of the logic unit of the field programmable gate array chip and the netlist information of the logic module generated after packaging; establishes a wiring resource map according to the structure information of the logic unit of the chip; The layout of the field programmable gate array chip is carried out according to the netlist information and the wiring resource map, and the fast wiring is carried out at the same time. The invention performs fast wiring according to the wiring resource map in the layout process, closely combines the layout and wiring process, improves the success rate of wiring, reduces the delay of the circuit at the same time, and improves the utilization rate of wiring resources.

Description of drawings

The above and other objects, features and advantages of the present invention will be more clearly illustrated by the accompanying drawings. Like reference numerals designate like parts throughout the drawings. The drawings are not intentionally scaled according to the actual size, and the emphasis is on illustrating the gist of the present invention.

Fig. 1 is FPGA chip layout method flowchart of the present invention;

FIG. 2 is a schematic diagram of a wiring resource map established according to FPGA chip structure information;

Fig. 3 is the layout flowchart of carrying out FPGA chip according to netlist information and wiring resource map;

Figure 4 and Figure 5 are schematic diagrams of the positions of the mobile and exchange modules in the layout.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the drawings in the embodiments of the present invention. Apparently, the described embodiments are only some of the embodiments of the present invention, but not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Secondly, the present invention is described in detail with reference to the schematic diagrams. When describing the embodiments of the present invention in detail, for the convenience of explanation, the schematic diagrams are only examples, which should not limit the protection scope of the present invention.

As mentioned in the background technology, in most of the layout and routing tool software, the relationship between placement and routing is too loose. Usually, the interconnection lines used in the routing stage cannot be predicted during layout, so the delay caused by the interconnection lines cannot be predicted. , eventually causing the delay of the FPGA chip to increase. The best solution to reduce FPGA chip delay is to perform layout and routing at the same time. However, when layout and routing are performed at the same time, the running time of the placement and routing tool software will increase by more than ten times, which seriously affects the placement and routing time of the FPGA chip.

In order to quickly solve the problem of FPGA chip layout and wiring delay, the present invention provides a FPGA chip layout method. When the method is in the FPGA chip layout, the initial layout of the logic module is first carried out, and at the same time, local fast pre-wiring is performed, and the simulated annealing algorithm is used to calculate The cost value of logical module movement or exchange during layout is used to determine whether the logical module movement or exchange is accepted, and then determine whether to end the layout according to the layout temperature. The FPGA chip layout method of the invention closely combines the layout process and the wiring process, effectively reduces the delay of interconnection lines, and improves the utilization rate of wiring resources.

Refer to Fig. 1 for the flow chart of field programmable gate array chip layout method of the present invention, comprise steps:

Step S1, providing the structure information of the logic unit of the field programmable gate array chip and the netlist information of the logic module generated after packing.

FPGA chip structure information usually includes the position of various types of logic unit blocks in the chip, the pin name and pin position of the logic unit block, the delay from the input pin to the output pin of the logic unit block, the width of the wiring channel, the interconnection The distribution and delay of the connection segment and the position, type and delay of the wiring switch.

The logic unit of the FPGA chip is packaged to generate a logic module after process mapping. The logic module is composed of several logic units and local interconnect lines. The source of the logic unit is connected to the output pin of the logic module through the local interconnect line. The drain of the cell is connected to the input pin of the logic module through the local interconnect line.

The netlist information of the logic module generated after packaging includes the name and type of the logic module generated after packaging, the pins of the used logic unit block, and the source and drain terminals of all nets.

Step S2, establishing a wiring resource map according to the structure information of the logic unit of the chip.

The interconnection wiring resources connect all logic units inside the FPGA, and the length and process of the interconnection determine the driving capability and transmission speed of the signal on the connection.

As shown in Figure 2, the wiring resource diagram includes: the connection relationship between the source terminal of the logic unit and the output pin of the logic module, the connection relationship between the drain terminal of the logic unit and the input pin of the logic module; the connection relationship between the input and output pins of the logic module and the interconnection line Connection relationship; the connection relationship between interconnection lines, such as the connection relationship between interconnection line 1, interconnection line 2 and interconnection line 3; the connection relationship between logic units within the same logic module, and other modules and interconnection lines connection relationship.

In step S3, the layout of the FPGA chip is performed according to the netlist information and the wiring resource map, and fast wiring is performed at the same time.

In the FPGA chip layout method of the present invention, referring to Fig. 3, the specific layout process can include:

Step S31 , randomly layout the logic modules and fast pre-wiring, set the layout temperature, and store the total number of times the interconnect lines are occupied in a data structure.

Randomly place the logic modules required by the circuit on various positions of the FPGA chip, complete the initial layout, set the layout temperature, and quickly route the interconnection lines for the initial layout.

The fast routing of interconnection lines can use the path search algorithm (PathFinder). When routing, it is assumed that each interconnection line is critical, and the problem of repeated occupation of wiring resources is not remembered. The number of times each interconnection line is occupied is counted, and the interconnection The number of occupied times of all interconnect lines in the channel is superimposed and stored in the data structure congestion.

Step S32, moving or exchanging the logic modules according to the netlist information for layout.

Referring to Figure 4 and Figure 5, the logic module movement or exchange process in the layout is as follows:

The first module A is randomly selected in the netlist information, and the first module coordinate B is randomly selected, wherein the first module A is not constrained to a fixed position, the position of the first module A is not at the first module coordinate B, and The type of a module A is the same as the module type at the first module coordinate B; if the first module coordinate B is occupied by a module, this module is not constrained to a fixed position.

When the above conditions are met, if position B is not occupied, as shown in Figure 4, module A moves to module coordinate B; if position B is occupied by module C, as shown in Figure 5, then module A and module C exchange positions.

Wherein, the type of the module may be a logic module, an input/output module, and the like.

Step S33, calculating the cost value of moving or exchanging the logic module according to the layout temperature.

Calculate the cost value of moving or exchanging logic modules during the layout process, using simulated annealing algorithm (SA, Simulated Annealing). Simulated annealing algorithm is an annealing process that mimics the gradual cooling of molten metal to create metallic materials. The pseudocode of the annealing algorithm is as follows:

Among them, bb_cost is the line network bounding box value, which represents the distance between logic modules, and timing_cost is the delay value between logic modules.

Step S34 , performing fast local routing on the moving or switching logic module according to the routing resource map, and updating the number of times interconnection lines are occupied in the data structure.

When the module is moved or exchanged, release the interconnection line originally occupied by the network, count the network used by the moved or exchanged logic module, traverse the network used by the moved or exchanged logic module, and use each network The routing algorithm performs fast routing. The routing algorithm is a path search algorithm. When routing, it does not consider whether the interconnection line is occupied, but counts the number of times the interconnection line is occupied, and calculates the number of times the interconnection line is occupied in the entire interconnection channel. Stored in the data structure congestion.

Step S35, calculating the cost value after the rapid local routing, and judging whether the move or exchange is accepted according to the change of the cost value.

Calculate the cost value, add a constraint Afac*congestion to the cost value Cost (S) formula in step S33 to describe the degree of congestion of the interconnection channel, the formula is as follows:

Cost(S)=(1-timing_tradeoff-Afac)*bb_cost+timing_tradeoff*timing_cost+Afac*congestion; the congestion item in the newly added constraint item represents whether the number of interconnection lines used in the interconnection channel exceeds the number of interconnection lines in the interconnection channel The number of interconnection lines, if it exceeds the congestion value is 1, otherwise it is 0;

Calculate IC=Cost(S _new )-Cost(S); and r=random(0,1);

If r< holds true, then the module move or exchange is accepted, otherwise it is rejected.

Step S36, judging whether the layout temperature of the FPGA chip satisfies the set condition, if not, updating the layout temperature, and executing step S32; if yes, ending the layout.

The setting condition that the layout temperature satisfies is the temperature condition, and the setting condition is related to the number of wire nets occupied, and is usually set to a relatively small value. If the layout temperature does not meet the set conditions, that is, when the layout temperature is relatively high, after the layout temperature is updated, step S32 is performed, and the logic module is moved or exchanged according to the netlist information for layout, and the cycle is performed until the layout temperature of the FPGA chip is reached. If the set conditions are met, the layout ends and the layout result is obtained.

The FPGA chip layout method of the present invention is used for layout, fast pre-wiring is carried out in the layout process, the layout and wiring processes are effectively combined, the success rate of wiring can be improved, the utilization rate of wiring resources can be improved, and the delay of circuits can be reduced.

The above descriptions are only preferred embodiments of the present invention, and do not limit the present invention in any form. Any person familiar with the art, without departing from the scope of the technical solution of the present invention, can use the methods and technical content disclosed above to make many possible changes and modifications to the technical solution of the present invention, or modify it into an equivalent implementation of equivalent changes example. Therefore, any simple modifications, equivalent changes and modifications made to the above embodiments according to the technical essence of the present invention, which do not deviate from the content of the technical solution of the present invention, still belong to the scope of protection of the technical solution of the present invention.

Claims (9)

1. A field programmable gate array chip layout method, is characterized in that, comprises steps: Provide the structural information of the logic unit of the field programmable gate array chip and the netlist information of the logic module generated after packaging; Establishing a wiring resource map according to the structural information of the logic unit of the chip; According to the net list information and the wiring resource map, the layout of the field programmable gate array chip is carried out, and the fast wiring is carried out at the same time. 2. method according to claim 1, it is characterized in that, described according to described netlist information and wiring resource map, carry out the layout of field programmable gate array chip, carry out fast wiring simultaneously, comprise step: random layout of the logic modules and fast pre-wiring, and setting the layout temperature, and storing the total number of times the interconnection lines are occupied in a data structure; moving or exchanging the logic modules according to the netlist information for layout; calculating a cost value for moving or swapping logic modules based on the layout temperature; Perform fast local wiring on the moving or switching logic module according to the wiring resource map, and update the number of times interconnection lines are occupied in the data structure; Calculating the cost value after the fast local wiring, and judging whether the move or exchange is accepted according to the change of the cost value; Judging whether the layout temperature satisfies the set condition, if not, updating the layout temperature, performing the step of moving or exchanging the logic module according to the netlist information for layout; if yes, ending the layout. 3. The method according to claim 2, characterized in that a path search algorithm is used for fast pre-wiring. 4. method according to claim 2, is characterized in that, described moving or exchanging described logic module according to described net list information and carrying out layout step is: Select the first module and the first module coordinates in the netlist information, wherein the first module is not constrained to a fixed position, the position of the first module is not in the first module coordinates, the type of the first module is consistent with the first module coordinates The module types at the coordinates of the first module mentioned above are the same; If the coordinates of the first module are not occupied, move the first module to the coordinates of the first module; if the coordinates of the first module are occupied by the second module, the second module is not constrained to the first module coordinates, swap the first module and the second module. 5. The method according to claim 2, wherein the step of calculating the cost of moving or exchanging the logic module is: A simulated annealing algorithm is used to calculate the cost value of moving or exchanging the logic module. 6. The method according to claim 2, characterized in that, performing fast local wiring on the moving or switching logic module according to the wiring resource map, specifically: The wire nets used by the moved or swapped logic modules are traversed, and each wire net is quickly wired using a routing algorithm, and the routing algorithm is a path search algorithm. 7. according to the method described in any one of claim 1-6, it is characterized in that, the structural information of the logical unit of described provision field programmable gate array chip, comprises: Provides the location of various types of logic cell blocks, pin names of logic cell blocks, pin positions, delays from input pins to output pins of logic cell blocks, width of routing channels, distribution and delay of interconnection segments And the position, type and delay of the wiring switch. 8. according to the method described in any one of claim 1-6, it is characterized in that, the netlist information of the logic module that generates after the logic unit of described field programmable gate array chip is packed includes: Provide the name and type of the logic module generated after the logic unit is packaged, the pins of the used logic unit block, and the source and drain terminals of all nets. 9. The method according to any one of claims 1-6, wherein the establishment of a wiring resource map according to the structural information of the logic unit of the chip comprises: According to the structural information of the logic unit of the chip, the connection relationship between the source end of the logic unit and the output pin of the logic module, the connection relationship between the drain end of the logic unit and the input pin of the logic module, and the connection between the input and output pins of the logic module and the interconnection line are established. Connection relationship, connection relationship between interconnection lines, connection relationship of logic units inside the same logic module, and connection relationship between other modules and interconnection lines.

Images