System and method for using scalable polynomials to translate a look-up table delay model into a memory efficient model

A computer implemented method for generating memory resident timing models comprising the steps of:

• a) accessing a memory resident look-up table data structure for a cell, said memory resident look-up table data structure having timing data points each referenced by first and second input variables, wherein said first input variable is an input transition rate of an input of said cell and wherein said second input variable is an output load capacitance of an output of said cell, wherein said timing data points represent the delay through a timing arc of said cell;
• b) translating said memory resident look-up table data structure into a selected polynomial form having a selected order and a set of coefficients and further having, as input variables, said input transition rate and said output load capacitance, wherein said selected polynomial form is selected out of a predetermined set of scalable polynomial forms, by executing the steps of:
• b1) out of said predetermined set of scalable polynomial forms, selecting a first polynomial form of a first selected order, said first polynomial form having a first set of coefficients;
• b2) determining values for said first set of coefficients by performing a linear least square error curve fitting computation on said timing data points with respect to said first polynomial form;
• b3) performing a Chi-Square computation with respect to said timing data points and said first polynomial form including said values determined at step b2) to obtain a Chi-Square result;
• b4) accepting said first polynomial form including said values determined at step b2) provided said Chi-Square result is greater than a given threshold;
• and
• b5) provided said Chi-Square result is not greater than said given threshold, repeating steps b2)-b4) with respect to a second polynomial form having a second selected order and a second set of coefficients, wherein said second polynomial form is selected out of said predetermined set of scalable polynomial forms;
• c) replacing said memory resident look-up table data structure with said selected polynomial form;
• d) repeating steps a)-c) for a plurality of cells of a technology library stored in said memory;
• and
• e) using each of said selected polynomial forms to estimate timing delays through each said timing arc of said plurality of cells of said technology library.

A computer system comprising a processor coupled to a bus and a memory unit coupled to said bus, said memory unit having stored therein instructions that when executed implement a method for generating memory resident timing models comprising the steps of:

• a) accessing a memory resident look-up table data structure for a cell, said memory resident look-up table data structure having timing data points that are each referenced by an input transition rate input variable and an output load capacitance input variable, wherein said timing points represent the delay through a cell timing arc;
• b) translating said memory resident look-up table data structure into a selected polynomial form having a selected order and a set of coefficients and further having, as input variables, said input transition rate and said output load capacitance, wherein said selected polynomial form is selected out of a predetermined set of scalable polynomial forms, by executing the steps of:
• b1) out of said predetermined set of scalable polynomial forms, selecting a first polynomial form of a first selected order, said first polynomial form having a first set of coefficients;
• b2) determining values for said first set of coefficients by performing a linear least square error curve fitting computation on said timing data points with respect to said first polynomial form;
• b3) performing a Chi-Square computation with respect to said timing data points and said first polynomial form including said values determined at step b2) to obtain a Chi-Square result;
• b4) accepting said first polynomial form including said values determined at step b2) provided said Chi-Square result is greater than a given threshold;
• and
• b5) provided said Chi-Square result is not greater than said given threshold, repeating steps b2)-b4) with respect to a second polynomial form having a second selected order and a second set of coefficients, wherein said second polynomial form is selected out of said predetermined set of scalable polynomial forms;
• c) replacing said memory resident look-up table data structure with said selected polynomial form;
• d) repeating steps a)-c) for a plurality of cells of a technology library stored in said memory resident look-up table data structure;
• and
• e) using each of said selected polynomial forms to estimate timing delays through each said timing arc of said plurality of cells of said technology library.