WO2011134657A1

WO2011134657A1 - Method for inserting repeaters into an integrated circuit

Info

Publication number: WO2011134657A1
Application number: PCT/EP2011/002124
Authority: WO
Inventors: Markus Olbrich; Ole-Hendrik Ohlendorf; Erich Barke
Original assignee: Gottfried Wilhelm Leibniz Universität Hannover
Priority date: 2010-04-30
Filing date: 2011-04-28
Publication date: 2011-11-03
Also published as: DE102010019115A1

Abstract

The present invention relates to a method for designing an integrated circuit, in which, in accordance with a predetermined circuit diagram, components (1, 2, 3) are placed on a circuit surface (8) using a placement algorithm, the placement algorithm containing a plurality of placement steps (23), characterised in that the components (1, 2, 3) are placed by multiple repetition of at least the following steps, wherein the following steps are carried out in the given sequence until the predetermined circuit diagram has been implemented: a) carrying out at least one placement step (23) or a subset of the total number of placement steps (23), b) carrying out a timing analysis (24) for the current placement of the components (1, 2, 3), and c) inserting one or more repeaters (4) into the circuit according to the result of the timing analysis (24). The invention further relates to a data carrier comprising a computer program that is designed to carry out such a method.

Description

description

Method of inserting repeaters in an integrated circuit

The invention relates to a method for inserting repeaters in an integrated circuit according to the preamble of claim 1. The invention further relates to a data carrier with a computer program that is set up to carry out such a method.

Methods for designing integrated circuits are known, for example, from US 2003/0229878 A1, US Pat. No. 6,662,349 B2. Here, starting from a given circuit diagram, components on a circuit surface, for. B. a substrate placed. In the case of highly integrated circuits, such a placement can no longer be done manually for reasons of expense. Therefore, placement by software is automated. In this case, placement algorithms are used which allow an optimized placement of the components. To achieve high processing speeds in such integrated circuits so-called repeaters are inserted in addition to the predetermined by the circuit diagram components at certain points. The repeaters serve as signal amplifiers. Therefore, repeaters z. B. also be referred to as signal regenerators. In previous design methods of integrated circuits, the repeaters are inserted so to speak in the circuit in the supply, for. B. at equidistant intervals. This results in an increased circuit complexity and increased space requirements, as in principle space must be provided for repeaters, even if a final timing analysis shows that not all repeaters are required.

CONFIRMATION COPY The invention is therefore based on the object to provide a method for inserting repeaters in an integrated circuit that uses the existing circuit area more efficiently.

This object is achieved by the method specified in claim 1. The subclaims indicate advantageous embodiments of the invention.

The method specified in claim 1 specifies a new approach for inserting repeaters into an integrated circuit, in which the placement steps, the timing analysis and the insertion of repeaters can be performed virtually simultaneously in small steps. Here, in particular, the insertion of repeaters is performed depending on the result of the timing analysis. This makes it possible to insert repeaters only if and only where an improvement in the timing of the integrated circuit can be expected. In comparison to known methods, therefore, no superfluous repeaters are inserted, so that no placeholders for repeaters must be provided. In contrast to known methods, in which the placement algorithm with all placement steps was initially performed completely and only then z. B. a timing analysis or wiring was performed, hereby an integrated approach is presented, in which these steps are performed nested in small steps. This makes it possible to realize a very precise adaptation of the actual distribution of the repeaters to the actual time behavior of the integrated circuit.

Timing analysis is understood as an analysis of the expected time behavior of the integrated circuit in practical operation. The invention has the advantage that circuit designs are also mastered with a large number of repeaters. Timing information can be considered directly during placement. Overall, repeaters are inserted only where necessary, so no wildcards are required. are dig. In addition, the reduced number of repeaters can be used to realize integrated circuits with lower energy consumption. According to an advantageous development of the invention, a global wiring of the components is carried out in the course of execution of steps a) to c) of claim 1. The global wiring includes a plurality of global wiring steps. In this case, at least one global wiring step can be carried out before step a), if necessary, several global wiring steps can also be carried out. This has the advantage that the wiring is carried out in small steps and quasi simultaneously with the placement of the components and the insertion of the repeaters. As a result, the global wiring is already integrated into the sequence of steps a) to c). This allows for a more realistic estimate of the actual wiring between the devices, which in turn allows for the timing analysis during placement to already consider the influence of the wiring. On the other hand, in known methods, only one wiring has been performed after completing the entire placement of the devices.

According to an advantageous development of the invention, only surface segments of the circuit area reserved for the wiring of the components and the repeaters are reserved during the global wiring. After carrying out the iteration method according to claim 1, a detail wiring of the components and the repeater is performed, are arranged in the electrical connections to the components and / or repeaters within the reserved surface segments. In this way, the influence of the subsequent wiring can be taken into account early during the execution of the placement steps and the timing analysis. The actual wiring, ie the production of electrical connections between the components and / or the repeaters, can then be carried out finally as detailed wiring, wherein the electrical connections in the previously reserved area segments are provided. This can further optimize the design and implementation of integrated circuits.

According to an advantageous embodiment of the invention, the surface segments are arranged only in mutually parallel and orthogonal longitudinal directions. As a result, oblique connections are avoided. This allows for automatic wiring creation through higher efficiency wiring algorithms. Particularly in the case of highly complex integrated circuits, the problem can be minimized that automatic wiring algorithms reach their limits due to line crossings and in the end can not perform complete wiring.

According to an advantageous development of the invention, a global wiring step is carried out only as required and not in each run of the iteration method. The global wiring step or the global wiring steps are thus optional and only performed if necessary.

According to an advantageous embodiment of the invention, a static timing analysis is performed as a timing analysis, with which the critical signal path is determined. In this case, a width search is performed by the signal graph of the circuit. This allows the detection of the critical signal path, which is a measure of the number and placement repeaters to be inserted. By means of a static timing analysis, an analysis of the time behavior of the integrated circuit can be carried out relatively quickly, so that this method is particularly suitable for being carried out many times during the placement of the components in the iteration method according to claim 1. Static Timing Analysis (STA) is a standard technique for studying timing requirements of integrated circuits. So far, static timing analysis has not been performed during placement. In principle, the integration into the placement method is possible due to the low Runtime complexity, which is 0 (v + e), with the number of nodes v and edges e of the timing graph.

The timing information is represented by the Slack As. It is calculated from the difference between the latest arrival time on the path (Latest Arrival Time, LAT) and the required arrival time (RAT): As = RAT - LAT. Negative Slack means that the timing conditions are violated. In other words, the slack provides a certain amount of time in the signal transmission. The insertion of repeaters should cause the slack to increase as a result of shorter delay times between the cells. The output of the implemented static timing analysis is an ascending Slack sorted list of individual timing paths and is used here to insert repeaters at timing critical locations. The path with the least slack is called the critical path.

According to an advantageous development of the invention, a square force-based method is provided as the placement algorithm. Such a method allows space-optimized and time-behavior-optimized placement of the components on the circuit surface.

According to an advantageous development of the invention, a repeater is inserted in step c) only if the timing analysis results in a need for it. In an advantageous embodiment of the invention, the total number of inserted repeaters is limited to one quarter of the number of all cells of the integrated circuit. As cells come z. B. the components of the circuit in question. In an advantageous development of the invention, in each case a plurality of placement steps and / or timing analyzes are carried out before one or more repeaters are inserted into the circuit. For example, repeaters can only be used after about 70 iterations of the placement step be inserted. Advantageously, a repeater is inserted when the timing conditions of the static timing analysis are violated. Advantageously, repeaters are repeatedly inserted at a predetermined distance for each timing-critical connection.

In an advantageous development of the invention, the placement algorithm uses a quadratic force-based method as a basic algorithm, which substantially corresponds to the new version of the placement tool "power plant" (described in: P. Spindler and F. Johannes, Fast and accurate routing demand estimation for efficient routability). DATE '07: Proceedings of the Conference on Design, Automation and Test in Europe, pp. 1226-1231, San Jose, CA, USA, 2007. EDA Consortium). The underlying concept and the characteristics of this placement procedure are briefly presented below.

The placement method is based on the minimization of the square Euclidean distance between the cells to be placed. The cost function r _{cos contains} the sum of all contributions for each two-point connection between two cells. Each of these contributions can be weighted individually. For example, the connection between the two cells i and y ^' with the coordinates (x _j , y _j ) and (Xj, yj) and the weight w _ij leads to the cost cu = ^w u ^■ K ^x ' - * jf ⁺ - yj f \ - The cost function can be written as follows: r _c0 s, = p ^r - C - p + 2 - d ^T - p + r _consl

Placement is described by the vector p = (x _i> ..., x ", y _]> ..., y") ^T , which contains the coordinates of the n cells of the circuit. The In x 2 «matrix C and the 2» -dimensional vector d contain the weighted connection costs between moving and non-moving cells. The constant contribution ^r comi results from connections between non-moving cells (pad cells). The minimization of the cost function leads to the linear system of equations C - p + d = 0. The solution of this system of equations is interpreted as a balance of forces of spring forces F _net (p) = C -j? + c / between the cells. The weights of each cost then correspond to spring constants.

The basic approach of force-based placement is the introduction of additional forces, which cause a distribution of cells on the layout surface. The optimization goal is to minimize the overlaps of the cells. The additional repulsive forces F _e are obtained from a virtual electrical field which is calculated by plotting virtual surface charges in the regions of the cells. After this initial implementation, the forces are summed and iteratively recalculated, resulting in the following equation:

The method proposed here uses the power-based placement approach. After this, the repulsive forces F _{e are} not directly into the

System of equations inserted. Instead, further spring forces F _m are used. So-called target points (or target points) are calculated and connected to each cell. A special spring constant w _{m is} used. The position of the target points is determined from the repulsive forces F _e with a scaling factor _A:, so that: P _{t aiget} (p) = p + k - F _e (p).

The forces F _{m are} calculated to

^F m = C _m - (p + p _{t alget} ). The matrix C _m is a diagonal matrix and contains the entry w _m on the main diagonal. The positions of the target points p _{t argel} are iterated from the

Cell positions calculated. The vector F _m is rewritten for each iteration

Target points determined and applied only for the current iteration. So that the cell positions newly obtained from the force equation are retained, so-called holding forces F _{hold are introduced} according to the following equation:

old (= ^~ het (P = -C - P ^~ d The equation system for the calculation of the placement vector p is obtained from the equilibrium of the three forces F _hold + F _m + F _net = 5. The initial solution results from the original equation system:

C -pW + d = 0 The rule for the iterative determination of the new placement is z> 0:

(+ C J. (p <' ⁺¹ > -) + C _m ^■ P _eligel 0> ^w ) = Ö with

P _ia r _get (P ^{i) ) = P ⁱ + k - F _e (P ^{i)

This new implementation of quadratic force-based placement shows a more favorable convergence behavior. In addition, the use of holding forces allows for consistent insertion of extra cells into the current placement. Connections between cells can be arbitrarily changed during the iterative calculation, without the placement changing abruptly. The basic characteristics of the force-based Placement (weighted mesh forces and repulsive forces) are retained. Thus, this placement method is best suited to insert or remove repeater stages in the course of placement. To estimate the delay time on the lines, z. B. a simple wiring model (wire-load model) with resistance pad R ' _w and capacitance _{pad w} are used. The delay time of the lines is estimated in the approach used with the Elmore delay. This simple estimation is used because the wiring is not yet determined during the placement. For the proposed method of inserting repeaters, other arbitrary calculation methods and models for estimating the delay time on the lines can also be used. The invention further relates to a data carrier with a computer program that is set up to carry out a method of the type described above. The disk may be a conventional commercially available media such. As a floppy disk, a CD or DVD or a memory stick. The disk can also be connected to a network, such. As the Internet, connected computer or a non-networked computer.

The invention will be explained in more detail by means of embodiments using drawings. Show it:

Figure 1 The placement of components on a circuit surface in a schematic representation; and

Figure 2 shows a method for inserting repeaters in an integrated

Circuit.

According to FIG. 1, components 1, 2, 3 are mounted on a circuit surface 8. assigns. The components 1, 2, 3 have been positioned by means of a placement algorithm. As components 1, 2, 3 conventional electronic components may be provided, such. As capacitors, resistors, transistors or standard cells, logic gates, etc.

Between the components 2, 3, a repeater 4 is provided. In order to establish electrical connections between the components 1, 2, 3 and the repeater 4, surface segments 5, 6 were initially provided in the course of the method of designing the integrated circuit in the context of a global wiring. These surface segments 5, 6 represent reservation surfaces for the completion of the creation of the integrated circuit electrical connections 9 between the components 1, 2, 3 and the repeater 4. As can be seen, the surface segments 5, 6 as horizontally extending surface segments 5 and vertically extending surface segments 6 realized so that the surface segments are always parallel to each other or orthogonal in the longitudinal direction. The dashed line shown between the components 1, 2 shows for comparison schematically an electrical connection made in conventional circuit design, which is provided at an angle as a direct connecting line between the components 1, 2.

According to FIG. 2, a method for inserting repeaters in an integrated circuit initially comprises a step 20 of the initial placement. Here, initially, any kind of placement of the components is provided, for. For example, according to their numbering in the circuit diagram. Then, as the first step of an iteration process, a query step 30 follows, in which it is checked whether the execution of an optional global wiring step is required. This allows the global wiring step to be performed only as needed and does not need to be performed every iteration of the iteration process. If a global wiring step is not required, the query step 30 branches directly to a step 23. The steps 21, 22 are skipped. If a global wiring step is required, after the polling step 30, a step 21 is executed in which a wiring topology is set. This is followed by a step 22 in which a wiring model is updated. Steps 21, 22 are parts of a global wiring step. Here, the surface segments 5, 6, as shown in Figure 1, placed. Thereafter, in a step 23, a new placement of the components 1, 2, 3 according to one or more placement steps of the square force-based method used as a placement algorithm and a determination of the basic wiring course. In a subsequent step 24, a timing analysis of the integrated circuit is performed in accordance with the device placement and the global wiring at that time. In a step 25, the timing analysis is evaluated so that it is checked whether a repeater 4 or possibly a plurality of repeaters is required. If repeaters are required, a branch is made directly to a step 26 in which corresponding repeater stages are inserted. Otherwise, the step 26 is skipped and proceeded to a step 27.

In step 27 it is checked whether steps 21 to 26 should be repeated or the loop can be aborted. If it is determined in step 27 that the circuit diagram has not yet been fully implemented, the method branches back to step 21. Otherwise, a step 28 is continued, in which a detailed placement of the components 1, 2, 3 and the repeater 4 is performed. Finally, detailed wiring is performed in a subsequent step 29. In this case, electrical connections between the components 1, 2, 3 and / or the repeaters are arranged within the area segments reserved in steps 21 and 22.

As a result, the method provides a netlist that can be fed directly into an integrated circuit fabricator. Advantageously, the netlist contains, in addition to the components, ie the logic gates of the circuit, the inserted repeater cells. As a result, a Generated network list for an integrated circuit that meets predetermined Timi requirements.

Claims

claims:

A method of inserting repeaters in an integrated circuit, wherein according to a predetermined circuit diagram, devices (1, 2, 3) are placed on a circuit surface (8) with a placement algorithm, the placement algorithm including a plurality of placement steps (23), characterized in that by repeatedly repeating at least the following steps the components (1, 2, 3) are placed, the following steps being carried out in the stated order until the given circuit diagram has been implemented: a) carrying out at least one placement step (23 ) or a subset of the total number of placement steps (23),

b) carrying out a timing analysis (24) for the current placement of the components (1, 2, 3),

c) inserting one or more repeaters (4) into the circuit in dependence on the result of the timing analysis (24).

2. The method according to claim 1, characterized in that in the course of the execution of steps a) to c) a global wiring of the components (1, 2, 3) is performed, wherein the global wiring includes a plurality of Globalververnungsschritten (21, 22) and before the step a) at least one global wiring step (21, 22) can be performed.

3. The method according to claim 2, characterized in that during the global wiring only surface segments (5, 6) of the circuit surface (8) are reserved, which for the wiring of the components (1, 2, 3) and the repeater (4) are provided, and after performing the iteration method according to claim 1, a detailed wiring of the components (1, 2, 3) and the repeaters (4) is performed, in the electrical connections (9) between the components and / or Repeaters within the reserved surface segments (5, 6) are arranged.

A method according to claim 3, characterized in that the surface segments (5, 6) are arranged only in mutually parallel and orthogonal longitudinal directions.

Method according to one of claims 2 to 4, characterized in that a global wiring step (21, 22) is performed in the iteration method according to claim 1 only as needed and not in each run.

Method according to one of the preceding claims, characterized in that as a timing analysis, a static timing analysis (STA) is performed, with which the critical signal path is determined.

Method according to one of the preceding claims, characterized in that a square force-based method is provided as the placement algorithm.

Method according to one of the preceding claims, characterized in that in step c) a repeater (4) is inserted only if the timing analysis (23) results in a need for it.

Data carrier with a computer program, which is set up to carry out a method according to one of the preceding claims.