基于核估计的成品率分析算法及其实现

对各参数的样本值进行随机组合，在多维参数空间里形成若干参数向量（即在多维空间里的参数 样本点） 。参数样本点的多少与算法稳定性有很大的关系。如果样本点太少，则导致边界点分布范围过 大，所以造成分析结果不准确。一般形成样本点个数为 104~105。 3.3 密度估计
对样本点的密度估计是算法中的核心部分，它直接决定着算法的准确性及效率。NBA 算法中在密 度估计采用的是最近邻法，通过计算某点的与其最相邻点的距离来估计该点上的密度。在样本点的随 机产生过程中，可能产生个别距离很近的点，造成密度估计上的误差。因此算法中加入一个 K 平滑系 数来减小这种误差，即通过计算某点与其最相邻的 K 个点的平均距离来估计该点上的密度。但是这样 大大增加算法的复杂度。例如：设有 n 个样本点，则寻找最相邻点的算法复杂度为 O (n 2 ) ，而为寻找 K
来估计该点上的密度 f ( x ) ， 其概率性质比较复杂， 在距离的计算方法和 K 平滑系数的选取上比较困难， 特别是在维数较大的情况下，容易产生较大的误差。 核估计法是概率密度估计近年来发展比较成熟的一种方法。其主要思想为：对每个 X 各作一个以 X 为中心的小区间 [X − h, X + h] ，然后以 f ( x ) =# ({ j : 1 ≤ j ≤ n, X − h ≤ Xj ≤ X + h}) / 2hn 作为密度函数。这里 n 为样本点个数， h >0 是一个与 n 有关的、适当选定的常数，称为“窗宽” ，#( ) 为符合条件的样本点 个数。该点的密度估计可表示为： 表 1 通过两种方法估计出
3
基于核估计成品率分析算法的实现
（1 ）数据整理 （2 ）随机组合，形成若干参数向量 （3 ）估计每一个参数点的密度 （4 ）根据参数点的密度进行排序 （5 ）找出候选边界点 （6 ）从候选边界点中找出边界点 （7 ）全电路仿真 （8 ）判断通过率是否达到β （9 ）如没有达到，改进参数后重新开始（转（ 1 ） ） ； 如果是，分析结束，进行下一个设计。
个最相邻点，须在其内部增加一个排序过程，算法复杂度至少为 O (n 3 ) 。由于算法中 n 的值是非常大的 （104~105） ，所以使得算法效率大大降低。同时，最近邻法的距离计算方法及 K 值的选取也是比较困 难的。 通过比较发现，核估计法在多维情况下其误差率和算法复杂度均低于最近邻法。因此对 NBA 算 法进行改进，利用核估计法对样本点进行密度估计，提高了算法的准确性及效率。通过对多种核函数 及窗宽进行比较，发现[2] 提供的公式对本例具有良好的准确性且算法效率高。故采用[2] 提供的公式：
图2
成品率分析流程
第1期
孙玲玲等：基于核估计的成品率分析算法及其实现
147
3.1
数据整理 NBA 算法所需的数据来源主要有两种：测量数据和根据参数模型产生的数据。测量数据即从工艺
线上或一些相关资料上获得的一组真实的参数样本值，在除去测量误差后，它反映的是在实际制造过 程中真实的参数误差分布情况。采用测量数据进行分析在 NBA 算法中被称为 MD 工作模式，在该模 式下可得出的十分可靠的分析结果，而且并可直接得出一组保证成品率最高的最佳参数值。采用参数 模型产生的数据，需要事先假设参数误差的分布，然后根据参数误差的分布产生一组参数样本值。采 用这种数据进行分析在 NBA 算法中被称为 MP 工作模式。在 MP 模式下得到的分析结果相对于 MD 模式误差较大，也不能直接得出一组最佳参数值，但是在测量数据无法或很难获取的情况下，MP 模 式也是一种较实用方法。需要指出，在 NBA 算法中需要大量的样本数据，因为非参数统计方法只有 在大样本的情况下才具有优良的概率性质。在 NBA 算法中需要对各参数进行标准化处理，根据各参 数的样本值范围对各参数赋于不同的权值。这主要是因为 NBA 算法采用最近邻法对参数空间内每个 样本点进行密度估计，如果参数间样本值范围差别较大，将会造成很大的误差。对 NBA 算法进行改 进后，采用核估计法进行密度估计，可以消除参数间样本值范围差别造成的误差，所以在改进算法中 省去了这一步骤。 3.2 随机组合，形成若干参数向量
第9卷
率估计，但是该成品率估计为产品实际成品率的下界，只需执行一次算法即可得到最终结果，这在电 路设计过程中是非常实用的。另外，由于 NBA 算法采用非参数统计方法，对于任何参数误差的分布 都是适用的。 同时，NBA 法也存在一些限制和缺点。首先，它要求在参数空间与电路的响应值空间存在等密度 曲面。其次，电路响应函数必须是大致单调的（大多数电路设计是基本符合这些条件的，即使是在不 符合上述条件的情况下，也可用该方法在参数空间里寻找一个最坏情况下的成品率） [1] 。同时，在对 NBA 算法进行研究时发现， NBA 算法采用了最近邻法估计各样本点上的密度，在参数空间中随着维 数的增加，误差将增大。虽然在算法中也提出利用 K 平滑系数来减小误差，但是这样大大增加了算法 复杂度，而且 K 值较难选取。 概率密度估计是非参数统计学中的一个分支，是古老的直方图方法的发展。二十世纪五六十年代， Rosenblatt 和 Parzen 提出了核估计法（ Kernel Density Estimate ）使得该方法在近几十年有了许多新的 发展， 并得到了广泛的应用。 其主要思想是： 设 X 1 K X n 是从未知概率密度函数 f 的总体中抽出的样本， 依据这些样本对指定的 X，估计该点上的密度 f ( x ) 的值[4]。 概率密度估计方法主要有两种：最近邻估计法（Nearest Neighbor ） 、核估计法（ Kernel Density Estimate ） 。NBA 算法中所使用就是最近邻估计法。该方法主要思想是通过计算点与其最相邻点的距离
为了提高 NBA 方法在多维空间中的密度估计的准确性， 并且降低其算法的复杂性，本文给出了一种改进算法 — 基于 核估计的成品率分析算法。该方法在进行密度估计时利用核 估计法替代了 NBA 法中最近邻法，并且在边界点的选取时， 也通过核估计法对 NBA 法中空间变换算法进行了改进。整 个算法步骤如图 2。
的参数中心值数据
中心值 150.0 132.5 116.8 144.8 20.0 11.3 40.0 38.5 325.0 5.8 NN 152.1 130.2 114.2 146.5 19.2 11.3 39.3 38.1 327.8 5.8 Kernel 150.0 132.5 116.8 144.8 20.0 11.3 40.0 38.5 325.0 5.8
f ( x ) = 1/ 2nh × ∑Φ ( ( x-xi ）／h)
i =1 n
（２） 其中： h 为窗宽， h = 0.9 × min(δ , IRQ / 1.34) × n −1 / 5 ； δ 为均方差； IRQ 为前四分位点与后四分位点之差。 Φ (x ) 为标准正态分布函数。但是该公式为一维公式，为将其应用于多维空间内，对该公式在多维空间 内进行的拓展。为简单起见，假定各参数分布是独立的。由此推出多维公式为： m m m n m （3） f ( x) = 1 2 n ∏ hk × ∑∏ φ (( x − x ik ) / hk ) k =1 i=1 k =1 其中 i = 1K m ； k = 1K n 。ｍ 为参数个数，ｎ 为样本点个数。 利用该公式对参数空间里每一个样本点进行密度估计，其算法复杂度为 O (n 2 ) 。 3.4 排序 按照密度值由大到小，对参数空间里所有样本点进行排序，目的是根据样本点在序列中的位置确
1
导言
在批量制造过程中，集成电路的成品率已成为降低生产成本，提高生产效益的关键因素之一。电
路参数误差的统计分布与产品的成品率密切相关，因此参数设计的合理性是影响成品率的主要因素之 一。目前，电路设计中用于进行成品率分析的传统方法主要是蒙特卡罗（ Monte Carlo ）法。该方法简 单易行，但需要进行仿真的次数较多（一般需要几百次） 。而且，使用该方法需首先假定参数误差符合 一定的分布，如高斯分布。但这在应用过程中并不一定符合实际情况。另外，蒙特卡罗法提供的是一 个成品率的确定值，多次执行算法得出的结果不一定相同，需要对多个结果进行分析，以确定最终结 果。近年来，虽然蒙特卡罗方法有了许多改进，如：系统抽样法、重要抽样法等，这些方法在速度和 准确性上有了较大的提高，但算法的效率仍比较低。1999 年，Stoneking Dan 提出了基于非参数统计的 成品率分析方法—NBA（Non-parametric Boundary Analysis ）法，开辟了利用非参数统计方法进行快速 成品率分析的新途径。利用该方法对于电路中符合任何分布的参数误差，仅用几十次全电路仿真便可 得到电路的成品率及使成品率最大的一组最佳参数值。而且它提供了一个成品率的下界，仅需执行一 次算法，便可得到最终结果。该方法较好地弥补了蒙特卡罗方法的不足，大大提高了成品率的分析速 度[1]。目前，该方法已经获得美国专利，并且已集成于 ICCAP5.0 软件中。 但是，NBA 算法采用了最近邻估计法（ Nearest Neighbor）对各参数样本点进行密度估计，随着参 数空间维数的增加，将会导致算法误差增大，而且算法复杂度较大。因此，本文在 NBA 算法基础上 给出了一种改进算法—基于核估计的成品率分析方法。该方法在进行概率密度估计时，采用非参数统 计学中的核估计法（ Kernel Density Estimate ）替代 NBA 算法中的最近邻法（ Nearest Neighbor） ，有效 地提高了原方法在多维空间内进行密度估计的准确性，并且降低了算法的复杂度，在应用中取得了较 好的效果。
2
NBA 算法及概率密度估计简介
NBA 算法是基于非参数统计学中的概率密度估计方法的。 其主要思
想是在多维参数空间里，根据样本点的实际分布状况，通过分析位于分 布尾部的点， 得出产品成品率。 算法要求用户首先指定一个目标成品率， 由此在参数空间里形成了一个闭合的区域，然后找出这个区域的相应的
图1
二维边界点分布图