Patent Publication Number: US-5835891-A

Title: Device modeling using non-parametric statistical determination of boundary data vectors

Description:
BACKGROUND 
     The present invention concerns the designing and testing of integrated circuits or other electronics and pertains particularly to device modeling using non-parametric statistical determination of boundary (worst-case) data vectors. 
     During the course of manufacturing integrated circuits or other electronics, various circuitry is tested to determine performance of individual circuit components. The results are often quantified in order to be used in models which predict the performance of circuits which use the tested circuit components. 
     Even among circuit components manufactured on the same wafer using identical processing steps, there is a statistical variation of performance. Therefore, when attempting to accurately model circuitry, statistical variations in the performance of the circuit components are considered. 
     Generally, when determining nominal and worst-case performance for an individual circuit component, measured results are analyzed as if these form a Gaussian distribution. However, the actual distribution of measured results is often not Gaussian, but follows some other statistical pattern. It is desirable, therefore, to develop a more versatile approach to determine nominal and worst-case performance for circuit components. 
     SUMMARY OF THE INVENTION 
     In accordance with the preferred embodiment of the present invention, boundary vectors are selected from a plurality of data vectors. The data vectors are generated, for example by measuring actual performance of an electronic component. 
     A density estimate is calculated for each data vector in the plurality of data vectors. For example, the density estimate is calculated by first calculating an average distance from the current data vector to each of the all the other data vectors. Alternatively, the average distance from the current data vector to a subset of a preselected number of the all the other data vectors may be used. A density estimate is estimated for the current data vector as one divided by the average distance calculated. 
     In order to make more accurate the calculation of the density estimate, vector components for all data vectors within the plurality of data vectors can be scaled so that the plurality of data vectors are bounded by a unit hypercube. This is done, for example, before calculating the average distances. 
     A selected number of the data vectors are partitioned from the plurality of data vectors into a partitioned group. The partitioned group includes the data vectors from the plurality of data vectors with greatest density estimates. From the data vectors in the partitioned group, candidates for boundary vectors are selected. The candidates for boundary vectors have the lowest density estimates within the partitioned group. 
     In one embodiment, all the candidates for boundary vectors are actually used as boundary vectors. However, to abate clustering, the candidates for boundary vectors can include an oversample. In this case, for example, candidates are eliminated as follows. For all possible pairings of the candidates for boundary vectors, a pairing of candidates which are closest together is located. The candidate from the located pairing of candidates which has the higher density estimate is removed as a candidate. This process is repeated until the number of remaining candidates is equal to the desired number of boundary vectors. 
     Values for boundary model parameter vectors which model the electronic component can be calculated from the boundary vectors. 
     In the preferred embodiment, a nominal data vector is also selected. For example, the nominal data vector is selected as the data vector from the plurality of data vectors which has the highest density estimate. A nominal model parameter vector may be calculated from the nominal data vector. 
     The present invention is especially useful when a data set consists of data vectors which are not distributed in a Gaussian pattern. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a material and information flow diagram for nominal and worst-case measurement selection in accordance with a preferred embodiment of the present invention. 
     FIG. 2 is a material and information flow diagram for nominal and worst-case measurement selection in accordance with an alternative preferred embodiment of the present invention. 
     FIG. 3 is a flowchart which shows main functionality of nominal and worst-case data vector analysis in accordance with a preferred embodiment of the present invention. 
     FIG. 4 is a flowchart which demonstrates normalization of a data set range to a unit hypercube in accordance with a preferred embodiment of the present invention. 
     FIG. 5 is a flowchart which illustrates density estimation in accordance with a preferred embodiment of the present invention. 
     FIG. 6 is a flowchart which illustrates the choosing of nominal and boundary points in accordance with a preferred embodiment of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     FIG. 1 shows material and information flow diagram for nominal and boundary (worst-case) measurement selection in accordance with a preferred embodiment of the present invention. A device under test (DUT) 11, a DUT 12, a DUT 13 and a DUT 14 represent circuit components which are to be modeled. For example, each of DUT 11 through 14 is an active device such as a bipolar transistor, metal oxide semiconductor field effect transistor (MOSFET) or some other type of transistor. Alternatively, each of DUT 11 through 14 could be any type of electronic or integrated circuit component which has potential variation in performance. 
     During the course of testing, each DUT is connected to one or more measurement instruments. For example, in FIG. 1, DUT 14 is shown to be electrically connected to a measurement instrument 15 and a measurement instrument 16. For example, if DUT is on an integrated circuit, measurement instrument 15 and a measurement instrument 16 may be electrically connected to DUT 14 using probes placed on pads within DUT 14. The measurement instruments may be any type of electrical equipment. For example, one or more of measurement instrument 14 and measurement instrument 15 may be a parametric tester, a network analyzer or a curve tracer. Depending upon the type of measurement instrument used, the measurement instrument typically measures such things as current-voltage characteristics, output power, reflected power, various power ratios, and so on. 
     A measurement instrument controller 17 is used to control measurement instrument 15 and measurement instrument 16. Measurement instrument controller 17 is responsive to user inputs 20 which provide user control over the measurement process. 
     Also in accordance with user inputs 20, data from measurement instruments 15 and 16 are, for example, in a block 18, collected and/or concatenated. When indicated by user inputs, outlier screening is performed. Additional manipulations of the data also may be performed in accordance with user inputs 20. 
     As a result of concatenation, collection, outlier screen and/or user manipulation, a measurement data set 19 is produced. The data set includes a series of data vectors. For example, each data vector is a concatenation of data values from each measurement instrument. For example, if a first measurement instrument produces the following vector components: 5.62498, 95.8734, -2.964, 0.18436, 6.16035, 7.66075, -5.1199 and 20.0258; a second instrument produces the following vector component 1.13238; a third instrument produces the following vector components: 109.83, 4.59603, 8.90571, 9.4781, 0.0079 and 200.445; and a fourth instrument produces the following vector components: 33.153, 48.0487, 17.9629 and 4.33053; then the data vector could be, for example, a concatenation of these vector components as follows: 5.62498, 95.8734, -2.964, 0.18436, 6.16035, 7.66075, -5.1199, 20.0258, 1.13238, 109.83, 4.59603, 8.90571, 9.4781, 0.0079, 200.445, 33.153, 48.0487, 17.9629, 4.33053. For example, there may be many hundreds or even thousands of data vectors produced for each type of circuit component. 
     A non-parametric nominal and worst-case data vector selection block 21 is used to select nominal and boundary (worst-case) data vectors. Non-parametric nominal and worst-case data vector selection block 21 produces a nominal aggregate measurement vector 22 and worst-case aggregate measurement vectors 23. Non-parametric nominal and worst-case data vector selection block 21 operates under various constraints. For example, the number of worst-case aggregate measurement vectors 23 is based on user inputs 20. 
     A DUT model parameter extraction algorithm 24 utilizes nominal aggregate measurement vector 22 and worst-case aggregate measurement vectors 23 to produce nominal DUT model parameter vector 25 and worst-case DUT model parameter vectors 26. The parameter vectors are parameters used to model the various DUTs. 
     Since it is resource intensive to convert aggregate measurement vectors into model parameter vectors, the design shown in FIG. 1 has the advantage of utilizing non-parametric nominal and worst-case data vector selection block 21 to minimize the number of aggregate measurement vectors before converting the aggregate measurement vectors into model parameter vectors. However, in an alternative preferred embodiment of the present invention, the aggregate measurement vectors can be converted into model parameter vectors and a non-parametric nominal and worst-case data vector selection block can then be used to extract nominal and worst-case DUT model parameter vectors. This is illustrated, for example, by FIG. 2. 
     In FIG. 2, a device under test (DUT) 31, a DUT 32, a DUT 33 and a DUT 34 represent circuit components which are to modeled. For example, each of DUT 31 through 34 is an active device such as a bipolar transistor, metal oxide semiconductor field effect transistor (MOSFET) or some other type of transistor. Alternatively, each of DUT 31 through 34 could be any type of electronic or integrated circuit component which has potential variation in performance. 
     During testing, each DUT is connected to one or more measurement instruments. For example, DUT 34 is shown to be electrically connected to a measurement instrument 35 and a measurement instrument 36. For example, if DUT is on an integrated circuit, measurement instrument 35 and a measurement instrument 36 may be electrically connected to DUT 34 using probes placed on pads within DUT 34. The measurement instruments may be any type of electrical equipment, as discussed above. 
     A measurement instrument controller 37 is used to control measurement instrument 35 and measurement instrument 36. Measurement instrument controller 37 is responsive to user inputs 40 which provide user control over the measurement process. 
     Also in accordance with user inputs 40, data from measurement instruments 35 and 36 are, for example, in a block 38, collected and/or concatenated. When indicated by user inputs, outlier screening is performed. Additional manipulations of the data also may be performed in accordance with user inputs 40. 
     A measurement data set produced, for example, as a result of concatenation, collection, outlier screen and/or user manipulation is received by a DUT model parameter extraction algorithm 44. DUT model parameter extraction algorithm 44 utilizes the measurement data set to produce a DUT model parameter data set 39, in accordance with user inputs 40. 
     A non-parametric nominal and worst-case data vector selection block 41 is used to select nominal and boundary (worst-case) data vectors. Non-parametric nominal and worst-case data vector selection block 41 produces a nominal DUT model parameter vector 45 and worst-case DUT model parameter vectors 46. The parameter vectors are parameters used to model the various DUTs. 
     FIG. 3 is a flowchart which shows main functionality of nominal and worst-case data vector analysis in accordance with a preferred embodiment of the present invention. That is, the flowchart illustrates how non-parametric nominal and worst-case data vector selection block 21 and non-parametric nominal and worst-case data vector selection block 41 function. 
     The nominal and worst-case data vector analysis is started in a step 51. In a step 52, data is scaled into a unit hypercube. This means that all the corresponding vector components for each data vector are scaled so that the spread of values for the corresponding vector components for each data vector are in a common range, for example, the range of 0 to 1. This gives equal weight to each vector component when calculating distances between data vectors. Step 52 is further expanded in FIG. 4. 
     In a step 53, density estimate estimates are calculated for all data vectors. That is, at the location of each data vector, a density estimate taking into account the location of all other data vectors is calculated. An example process for performing this is set out in FIG. 5. 
     In a step 54, a nominal data vector and boundary (worst-case) data vectors are chosen. The nominal data vector is the data vector with the highest density estimate, as calculated in step 53. The boundary (worst-case) data vectors are those data vectors which define a boundary of constant estimated density. For example, if the user wants the density boundaries to encompass 75% of the data vectors, then boundary data vectors are chosen so that 75% of the data vectors with the highest density estimate, as calculated within step 53, are within the boundaries delineated by the boundary data vectors. An example process for performing this is set out in FIG. 6. 
     In a step 55, the nominal data vector and the boundary (worst-case) vectors are returned. In a step 56, the nominal and worst-case data vector analysis is complete. 
     FIG. 4 is a flowchart which presents an example of how to perform normalization of a data set of data vectors to fall within a unit hypercube. The normalization is begun in step 61. 
     In a step 62, for each vector component (I), the minimum value (min i ) and the maximum value (max i ) of the vector component across all the data vectors is calculated. 
     In a step 63, for each vector component (I), an axis shift (shift i ) and a scaling factor (scale i ) are calculated in accordance with Equation 1 below: 
     
         shift.sub.i =min.sub.i scale.sub.i =1/(max.sub.i -min.sub.i) Equation 1 
    
     In a step 64, all vector components of all data vectors are normalized to lie in the same range. In the present example, the range is chosen to be between 0 and 1, however, any range may be chosen. For the range of  0,1!, Equation 2 below may be used to perform a normalization of each original vector component (orig --  component i ) of each data vector to produce a scaled vector component (scale --  component i ): 
     
         scale.sub.-- component.sub.i =scale.sub.i *(orig.sub.-- component.sub.i -shift.sub.i)                                             Equation 2 
    
     In a step 65, the normalization of a data set range to a unit hypercube is complete. 
     FIG. 5 is a flowchart which presents an example of how to perform density estimation. The density estimation is begun in a step 71. 
     In a step 72, the data set of data vectors with normalized vector components is sorted into a K-D tree for nearest neighbor retrieval. For information about using a K-D tree structure, see Jerome H. Friedman, et al, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software, Vol. 3, No. 3, September 1977, pp. 209-226. 
     In a step 73, a check is made to see if a density estimate has been made for every data vector. If not, in a step 74, one of the remaining data vectors is selected as a current sample. For the current sample a specified number of the nearest neighbors is found. In the preferred embodiment, the specified number is the entire data set of data vectors with the exception of the current sample. 
     In a step 75, distances between the current sample and all of its nearest neighbors is computed. In a step 76, an average distance (average --  distance) is computed to all of the nearest neighbors. 
     In a step 77, average density is estimated. This may be done by any known method of estimating or calculating density. In the preferred embodiment of the present invention, Equation 3 below is used to estimate density (Density): 
     
         Density=1/(average.sub.-- distance)                        Equation 3 
    
     In a step 78, the estimated density for the current sample (data vector)is associated with the data vector. Then step 73 is again performed. If in step 73, it is determined that a density estimate has been made for every data vector, in a step 79, data vectors with associated density estimates serve as output from the density estimation. In a step 80, the density estimation is complete. 
     FIG. 6 is a flowchart which presents an example of how to perform the choosing of nominal and boundary points. The choosing of nominal and boundary points is begun in a step 91. 
     In a step 92, the data set of data vectors with associated density estimates is sorted into a ranked order from the data vector with the highest density estimate to the data vector with the lowest density estimate. The density estimate for each data vector remains associated with the data vector. 
     In a step 93, the data vector with the maximum density estimate is selected as the nominal data vector. 
     In a step 94, the data vectors are partitioned to form an enclosed partition of a specified percentage of the data vectors with the highest density estimates. The specified percentage is user variable to allow customization to a particular application. Typically, the percentage is in a range from 75% to 99%. 
     In a step 94, in the preferred embodiment of the present invention, it is determined a number of data vectors which will be initially used as candidates for boundary vectors. In the preferred embodiment, as set out in a step 95, the number of candidate boundary vectors (NCBV) is equal to the number of boundary vectors (NBV) which are to be used times a spatial diversity oversampling factor (SDOSF). This is reflected in Equation 4 below: 
     
         NCBV=NBV*SDOSF                                             Equation 4 
    
     In the preferred embodiment, both the number of boundary vectors (NBV) and the spatial diversity oversampling factor (SDOSF) are user chosen. The spatial diversity oversampling factor (SDOSF) can be selected, for example, based on the propensity of the data vectors to cluster. If the data vectors are particularly well distributed, then the spatial diversity oversampling factor (SDOSF) may be one, i.e., there is no oversampling done and just the boundary vectors are returned without further processing. 
     In a step 96, for the case where there is oversampling, a K-D tree is formed. In the K-D tree is placed the candidate boundary vectors. There are NCBV data vectors in the K-D tree. These NCBV data vectors are the NCBV data vectors within the enclosed partition (formed in step 94) which have the lowest density estimate. 
     In a step 97, a check is made to determine whether the remaining data vectors in the K-D tree is equal to the number of boundary vectors (NBV). If not, in a step 98, for all possible pairs within the K-D tree, the pair which is the closest distance together is found. 
     In a step 99, the data vector with the highest density estimate from the pair found in step 98 is discarded from the K-D tree. Then, returning to step 97, another check is made to determine whether the number of remaining data vectors in the K-D tree is equal to the number of boundary vectors (NBV). If the remaining data vectors in the K-D tree is equal to the number of boundary vectors (NBV), in a step 100, the nominal data vector and the boundary data vectors are constructed. The nominal vector is the data vector selected in step 93. The boundary vectors are the data vectors remaining in (i.e., not discarded from) the K-D tree. In a step 101, the selection of a nominal vector and boundary vectors is complete. 
     The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.