Multimode delay analysis for simplifying integrated circuit design timing models

A method of analyzing multimode delay in an integrated circuit design to produce a timing model for the integrated circuit design, by inputting a net list, IO arc delays, interconnection arc delays, and constant nets with assigned Boolean functions for the integrated circuit design, propagating the constant nets and assigning Boolean conditions to the IO arc delays and the interconnection arc delays, evaluating timing path delays and conditions for the integrated circuit design, creating the integrated circuit design timing model parameters, and outputting the integrated circuit design timing model. The method is especially desirable for netlists with very complicated mixing logics that include muxing of clocks. In particular, RRAMs are such netlists.

FIELD

This invention relates to the field of integrated circuit fabrication. More particularly, this invention relates to mathematical modeling of integrated circuits during the design process.

BACKGROUND

Integrated circuits are often formed using an application specific integrated circuit architecture, which tends to reduce the design costs of the integrated circuit by mixing and matching pre-designed functional blocks in a somewhat customized arrangement to produce an integrated circuit according to a customer's specifications. One functional block of such a customizable integrated circuit design is referred to as Reconfigurable RAM, or RRAM for short.

RRAM contains sets of memories of the same type that are placed compactly within a memory matrix. An RRAM, as the term is used herein, is a mega cell that can be considered as a set of memories with built-in self testing and built-in self correction.

During the design phase of integrated circuits, a delay analysis is typically performed, where the delays of the nets within the integrated circuit are characterized. For some integrated circuit designs this is not such a difficult problem. However, for very complex circuits, such as RRAMs, there may be on the order of about twenty thousand different nets to investigate. The repeated and separate consideration of each one of these nets for each change that is made to the design can place a serious burden on the delay analysis tool.

What is needed, therefore, is a system that enables more accurate and timely mathematical modeling for the design of RRAM.

SUMMARY

The above and other needs are met by a method of analyzing multimode delay in an integrated circuit design to produce a timing model for the integrated circuit design, by inputting a net list, IO arc delays, interconnection arc delays, and constant nets with assigned Boolean functions for the integrated circuit design, propagating the constant nets and assigning Boolean conditions to the IO arc delays and the interconnection arc delays, evaluating timing path delays and conditions for the integrated circuit design, creating the integrated circuit design timing model parameters, and outputting the integrated circuit design timing model.

DETAILED DESCRIPTION

The multimode delay analyzer according to a preferred embodiment of the present invention analyzes RRAMs and builds timing models for these mega cells. Although this tool is suited for usage in the design of an RRAM, it also can be used for timing analysis of any other mega cell.

RRAMs are defined by net lists with prepared placement and routing. The net list typically contains cells of the following types: memories, flip flops, latches, and logical cells. The delays of the IO timing arcs of the RRAM cells (called IO arcs) and the delays of the interconnections of the RRAM cells (called interconnection arcs) are preferably evaluated by some other tool and defined as the input of the delay analyzer. The delay analyzer considers the IO arcs and the interconnection arcs and generates the timing model for the RRAM mega cell as a library cell. This timing model includes IO arcs that connect inputs and outputs of the RRAM mega cell and timing restrictions (setup and hold times, recoveries and skews, clock minimal widths and periods).

The problem solved by a delay analyzer according to a preferred embodiment of the present invention is a well-know problem that is solved in many other tools, but these tools do not take into account some special features that are particular for the RRAM net lists. The RRAM net lists contain a lot of muxing logics. At least some of the muxing logics work “constantly,” meaning that the control signals of the muxing logics do not change their values during operation of the RRAM. This fact makes it possible to not completely recompute many of the IO arcs and interconnection arcs of the muxing logics during iterations of the delay analysis. This is a basic principle of the multimode delay analyzer described herein. An example that validates this base principle is given below.

Proof of Concept

The net list TEST contains mux ins1 for muxing data D1 and D2, mux ins2 for muxing clocks CP1 and CP2 and flip flop ins3. Let all interconnection arcs delays be zeroes (ins1.Z->ins3.D, ins2.Z->ins3.CP). Assume the delays of IO arcs as given below:ins1.A->ins1.Z−0.05ins1.B->ins1.Z−0.1ins1.S->ins1.Z−0.1ins2.A->ins2.Z−0.05ins2.B->ins2.Z−0.1ins2.S->ins2.Z−0.1ins3.CP->ins3.Q−0.15.

Let the flip flop ins3 have the timing restriction: SETUP D CP 0.07.

If we know nothing about the values of the inputs SD and SCP (which are the values of the control inputs of muxes), then we obtain the following timing for the mega cell TEST:IO path CP1->Q=0.05+0.15=0.2IO path CP2->Q=0.1+0.15=0.25SETUP D1 CP1=0.07+0.05−0.05=0.07SETUP D1 CP2=0.07+0.05−1.0=0.02SETUP D2 CP1=0.07+0.1−0.05=0.12SETUP D2 CP2=0.07+0.1−0.1=0.07.

If we know that the input SD has the constant value 0, and the input SCP has the constant value 1, then the IO path CP1 approaches Q and the SETUPs (D1, CP1), (D2, CP1), (D2, CP2) are disabled. If we know that the inputs SD and SCP are constant and have equal values (even if we don't know whether the value is zero or one) than the SETUPs (D1, CP2) and (D2, CP1) are disabled.

Construction of Delay Analyzer

The example above shows that the analysis of the constant nets of the net list (especially if these nets are connected to muxes) may sufficiently change the timing model of the mega cell. It allows us to reduce the number of timing IO arcs and timing restrictions, and decrease the values of arc delays. According to the present invention, we describe herein a multimode delay analyzer that considers the constant nets. The proposed delay analyzer deals not only with constant nets with known values (power 1 or ground 0), but also with constant nets with unknown values (we know that the net does not change its value, but we don't know exactly if it is a power net or ground net).

Let X be a set of Boolean variables X={x1, x2, . . . }. To each constant net of the net list we assign some Boolean function that depends on the Boolean variables X. The meaning of this Boolean function is the value of this constant net. This function may be constant 0 or 1. In this case the corresponding constant net is a net with known value. Otherwise the constant net is a net with unknown value defined by the Boolean function. In our example TEST as given above, if we want to set the inputs SD and SCP to have equal, unknown values, then we should assign the same Boolean function F=x1 to each of the nets SD and SCP.

By varying the values (0 or 1) of the Boolean variables X, we can obtain the different values of the constant nets as far as these values are Boolean functions of variables X. Each set of constant net values defines some mode of net list work. That is why the delay analyzer according to a preferred embodiment of the present invention is called a multimode delay analyzer.

RRAM mega cells with memory built in self repair support have a large number of different sets of constant net values. For example, if a given RRAM contains fifty memories, and the RRAM can repair three memories, than the number of the different repairing modes of the RRAM is (48*49*50)/(2*3)=19,600, which is the number of triples of faulted memories. The consideration of all these modes separately becomes too expensive, because consideration of each mode requires a mathematical routine to work on the description of the false paths that appear in that mode. The delay analyzer according to the present invention is capable of analyzing all possible built in self repair modes in parallel, as described below.

Let Y be a set of some auxiliary Boolean variables Y={y1, y2, . . . }. We will use these variables in the embodiment of the invention described herein. The multimode delay analyzer procedure10according to the preferred embodiment is given below and generally depicted inFIG. 1:1. Input the RRAM net list, IO arc delays, interconnection arc delays, and the constant nets with assigned Boolean functions, as given in block12.2. Make the constant net propagations and assign Boolean conditions to IO arc delays and interconnection arc delays, as given in block14.3. Evaluate timing path delays and conditions, as given in block16.4. Create RRAM timing model parameters, as given in block18.5. Output RRAM timing model, as given in block20.

Steps 2, 3, and 4 of the multimode delay analyzer as given above are now explained in greater detail.

2. Constant Net Propagation and Boolean Assignment

Step 2 as given above and as depicted inFIG. 1as block14is described in more detail in regard to routine14depicted inFIG. 2.

2.1. Initially, we assign the Boolean condition (Boolean condition is some Boolean function that depends on Boolean variables X) to be equal to 1 for any IO arc and interconnection arc of the net list, as given in block22.

2.2. For each constant net we assign the Boolean condition 0 to each arc that has a beginning or an end at some pin connected to the net NET, as given in block24. Denote FUNC(NET) to be a Boolean function assigned to the constant net NET.

2.3. Examine all the logical cells of the RRAM net list, as given in block26, and for each logical cell CELL perform the following steps 2.3.1-2.3.5, as labeled routine100and depicted inFIG. 3.

2.3.1. Let K be a number of inputs of the cell CELL, let Q be a number of outputs of the cell CELL. Let IN—1, IN—2, . . . , IN_K be input pins of the cell CELL. Let OUT—1, OUT—2, . . . OUT_Q be the output pins of the cell CELL, as given in block32.

2.3.2. For each input pin IN_i (i=1, 2, . . . . K) define Boolean function FUNC(IN_i) as follows. If the pin IN_i is connected to a constant net, then the FUNC(IN_i) equals the Boolean function assigned to this constant net. Otherwise FUNC(IN_i)=yi, as given in block34.

2.3.3. For each output OUT_j (j=1, 2, . . . Q), let the Boolean function LOG_F_j(IN—1, IN—2, . . . IN_K) be a logical function of the output OUT_j of the logical cell CELL, as given in block36.

2.3.5. For each pair of input IN_i and output OUT_j (i=1, 2, . . . K, j=1, 2, . . . Q), we evaluate the Boolean function F_i, j=LOG_F_j(FUNC(IN—1), . . . , FUNC(IN_(i−1)), 0, FUNC(IN_(i+1)), . . . FUNC(IN_K)) ^ LOG_F_j(FUNC(IN—1), . . . , FUNC(IN_(i−1)), 1, FUNC(IN_(i+1)), . . . FUNC(IN_K)). If the Boolean function F_i, j does not depend on any Boolean variable yi of the set Y, and the Boolean function COND is the current Boolean condition of the IO arc CELL.IN_i->CELL.OUT_j, then we assign the new Boolean condition to this arc: (COND & F_i, j), as given in block40.

2.4. If during the step 2.3 a new constant net was found, then return to step 2.3 (block26ofFIG. 2), as given in block28. If no new constant net was found, then finish the assignment of Boolean conditions (routine14) as given in block30, and return to block16ofFIG. 1.

3. Evaluation of Path Delays and Conditions

The goal of the given procedure is to evaluate the maximal and minimal delays of paths that connect net list pins with net list inputs and to obtain Boolean conditions of these paths. The path delay evaluation is a well-known problem. The Boolean condition of the path is the conjunction of the Boolean conditions of the IO arcs and the interconnection arcs that are included in this path. In this part of the description we describe a way to rapidly evaluate path delays and conditions that reduces the time required for the process. The proposed procedure has an important advantage in speed when applied to an RRAM net list or any other net list with many muxing logics. This part of the method is depicted in routine16ofFIG. 4, which is an expansion of block16ofFIG. 1.

For each pin PIN we denote the list PATH_LIST(PIN) of paths that begin on some input of the RRAM and end on the given pin PIN. Each path PATH of the list PATH_LIST(PIN) preferably has four parameters: START(PATH) is some input of the net list that is the beginning of the delay path, COND(PATH) is a Boolean condition of the delay path, and MIN_DEL(PATH) and MAX_DEL(PATH) are minimal and maximal values of the path PATH delay, respectively.

3.1. All the pins of the net list are sorted in the topological order, as given in block42. The topological order is such that for each IO arc or interconnection arc PIN1 to PIN2, the pin PIN1 is placed in the order earlier than the pin PIN2.

3.2. Initially, assume the set PATH_LIST(PIN) to be empty for each pin PIN of the net list.

3.3. For each pin PIN of the net list connected to some net list input INP, we add the following path PATH to the list PATH_LIST(PIN), as given in block44:START(PATH)=INP,COND(PATH)=1,MIN_DEL(PATH)=MAX_DEL(PATH)=0.

3.4. Examine all the pins of the net list in the topological order. For each examined pin PIN, take the following step 3.4.1, as given in block46.

3.4.1. Examine all the IO arcs and interconnection arcs that are ended on the pin PIN. For each examined arc ARC, take the following step 3.4.1.1.

3.4.1.1. Let ARC_DEL be the delay of the arc ARC. Let pin BEG_PIN be the beginning of the arc ARC. Examine all the paths of the set PATH_LIST(BEG_PIN). For each examined path BEG_PATH, take the following steps 3.4.1.1.1-3.4.1.1.3, as given in block48.

3.4.1.1.1. Assume the Boolean function TOTAL_COND=0.

3.4.1.1.2. Examine all the paths PATH of the set PATH_LIST(PIN) such that START(PATH)=START(BEG_PATH). For each examined path PATH, take the following steps 3.4.1.1.2.1-3.4.1.1.2.3.

If NEW_COND!=0, then we insert a new path NEW_PATH to the set PATH_LIST(PIN) such that:START(NEW_PATH)=START(PATH),COND(NEW_PATH)=NEW_COND,MIN_DEL(NEW_PATH)=min(MIN_DEL(PATH),MIN_DEL(BEG_PATH)+ARC_DEL),MAX_DEL(NEW_PATH)=max(MAX_DEL(PATH),MAX_DEL(BEG_PATH)+ARC_DEL).

If NEW_COND!=0, then we replace the Boolean condition of the path PATH with the NEW_COND, otherwise we remove the path PATH from the set PATH_LIST(PIN).

3.4.1.1.3. Evaluate the Boolean function, as given in block50:NEW_COND=(˜TOTAL_COND)&COND(BEG_PATH).

If NEW_COND!=0, then we insert a new path NEW_PATH to the set PATH_LIST(PIN) such that:START(NEW_PATH)=START(BEG_PATH),COND(NEW_PATH)=NEW_COND,MIN_DEL(NEW_PATH)=MIN_DEL(BEG_PATH)+ARC_DEL, andMAX_DEL(NEW_PATH)=MAX_DEL(BEG_PATH)+ARC_DEL.
4. Creation of RRAM Timing Model Parameters

To obtain the IO arcs of the RRAM mega cell, we examine the pins PIN that are connected to some output OUT of the RRAM. Then we examine all the paths PATH of the set PATH_LIST(PIN). For each PATH we can generate the IO arc from the input START(PATH) to the output OUT with Boolean condition COND(PATH) and minimal and maximal delay values MIN_DEL(PATH) and MAX_DEL(PATH).

To obtain all timing restrictions, we examine all the timing restrictions of the cells of the RRAM net list. Timing restrictions such as SETUP, HOLD, RECOVERY, or SKEW are defined by a pair of cell input pins PIN1 and PIN2 (one of these pins is usually—but not always—a clock pin). Then we preferably examine all the pairs PATH1 and PATH2 of paths that belong to the sets PATH_LIST(PIN1) and PATH_LIST(PIN2) correspondingly. If COND(PATH1)&COND(PATH2)!=0, then we generate the corresponding timing restriction for the pair of mega cell inputs START(PATH1) and START(PATH2), where the value of this restriction depends on the value of the considered cell timing restriction and the values MIN_DEL(PATH1), MIN_DEL(PATH2), MAX_DEL(PATH1) and MAX_DEL(PATH2).