一种应用于二次布局的有效划分方法

提出了一种基于二次布局的结合MFFC结群和h METIS划分的算法.实验表明:这种方法能得到很好的布局结果,但是运行消耗的时间比较长.为了缩短划分在二次布局中运行的时间,提出了一种改进的结群算法IMF-FC,用它在二次布局中做划分.与前者相比较,这种方法虽然布局质量稍差,但速度更快.     

微电子学、集成电路

TN4 2005010494一种应用于二次布局的有效划分方法/吕勇强,洪先龙,侯文婷.昊为民,蔡鼓慈(清华大学)“半导体学报一2004,25(3).一272-278提出了一种基于二次布局的结合M FFC结群和hMETIS划分的算法.实验表明:这种方法能得到很好的布局结果,但是运行消耗的时间比较长.为了缩短划分在二次布局中运行的时间.提出了一种改进的结群算法IMFFC,用它在二次布局中做划分.与前者相比较,这种方祛虽然布局质量稍差,但速度更快.图4表3参g(木)TN4 2005010497中、低能离子注人中的剂且效应及模拟方法/施小康,于民,石浩,黄如,张兴(北京大学微电子所)1…     

面向甚大规模集成电路的时延驱动布局方法

本文针对甚大规模集成电路的时延驱动布局问题提出了一个新的解决途径,其策略是将结群技术应用于二次规划布局过程中.结群的作用是可大幅度地降低布局部件的数量.本文设计了一个高效的结群算法CARGO,其优点是具有全局最优性并且运行速度很快.采用了一个基于路径的时延驱动二次规划布局算法对结群后的电路完成布局过程.由于二次规划布局算法能够在很短时间内寻找到全局最优解,故本文的算法更有希望彻底解决甚大规模电路的布局问题.在一组MCMC标准测试电路上对算法进行了测试,得到了满意的结果.     

一种新的基于结群的混合模式划分方法

提出一种专用于带有预设计模块的混合模式布局的划分算法.它基于扩展的MFFC结群算法,结合自下而上的结群和自上而下的划分为一体进行混和模式下的划分.这样不仅可以使划分能够考虑电路本身的逻辑依赖,而且可以得到很好的"最小割"划分结果.实验结果表明,这种划分算法在层次式混合模式布局流程里起到了显著的作用.将此算法和当今国际上著名的划分包HMETIS 进行比较,结果表明此算法有一定的优势.     

标准单元布局中的高效结群算法

本文提出了一个高效的结群算法,用以解决在超大规模条件下标准单元模式集成电路的布局问题.与传统结群算法相比,本算法的特色在于在结群之前,建立和组织了表示所有单元之间连接关系的信息库,使得结群算法具有全局优化性和无冗余计算的特点.本结群算法已应用于二次规划布局过程中.实验结果表明,本算法无论在结群质量和结群速度方面都非常理想,从而成功地解决了超大规模电路的布局问题.     

基于划分的力矢量布局算法

提出了一个全新的基于划分的力矢量布局算法.针对大规模集成电路的布局问题,采用基于并行结群技术的递归划分方法进行分解解决,并结合改进的力矢量算法对划分所得的子电路进行迭代布局优化.通过对MCNC标准单元测试电路的实验,与FengShui布局工具相比,该布局算法在花费稍长一点的时间内获得了平均减少12%布局总线长度的良好效果.     

基于划分的力矢量布局算法

提出了一个全新的基于划分的力矢量布局算法．针对大规模集成电路的布局问题，采用基于并行结群技术的递归划分方法进行分解解决，并结合改进的力矢量算法对划分所得的子电路进行迭代布局优化．通过对MCNC标准单元测试电路的实验，与FengShui布局工具相比，该布局算法在花费稍长一点的时间内获得了平均减少12%布局总线长度的良好效果．     

基于群法的BBL布局算法研究

本文对BBL结群及其在布局中的应用进行了研究。提出了表示群内单元位置关系的点结构模型、扩展的点结构模型、图模型及方位树模型;导出了计算单元数为n的群的全部点结构(或方位树)数及布局方式数的公式;证明了(扩展的)点结构模型与(扩展的)方位树模型的一一对应关系;提出了适用于Floor Plan及自顶向下布局法的限定高度的结群算法及适用于自底向上等布局法的最小冗余比结群法,并提出了递归结群法。本布局法可产生Slicing及Nonslicing二种布局结构。以上算法均已在UNIVAC 1100/10机上用Fortran 77实现,结果是令人满意的。     

一种新的标准单元增量式布局算法

提出了一种新的增量式布局方法W-ECOP来满足快速调整布局方案的要求.与以前的以单元为中心的算法不同,算法基于单元行划分来进行单元的插入和位置调整,在此过程中使对原布局方案的影响最小,并且尽可能优化线长.一组从美国工业界的测试例子表明,该算法运行速度快,调整后的布局效果好.     

一种新的标准单元增量式布局算法

提出了一种新的增量式布局方法W-ECOP来满足快速调整布局方案的要求.与以前的以单元为中心的算法不同,算法基于单元行划分来进行单元的插入和位置调整,在此过程中使对原布局方案的影响最小,并且尽可能优化线长.一组从美国工业界的测试例子表明,该算法运行速度快,调整后的布局效果好.     

结合模糊聚类与区域合并的彩色图像分割方法

提出了一种结合模糊聚类与区域合并的无监督彩色图像分割方法.首先,根据彩色图像建立对应的三维直方图,运用爬山法得到初始聚类中心和聚类数;然后,运用基于空间邻域像素的模糊均值聚类算法对图像在颜色空间进行聚类,得到初始分割结果;最后,应用提出的区域合并算法合并图像初始分割结果得到最终分割图像.仿真结果表明,算法的分割结果与人的主观视觉也有较好的一致性.     

A connectivity based clustering algorithm with application to VLSI circuit partitioning

Circuit partitioning is a fundamental problem in very large-scale integration (VLSI) physical design automation. In this brief, we present a new connectivity-based clustering algorithm for VLSI circuit partitioning. The proposed clustering method focuses on capturing natural clusters in a circuit, i.e., the groups of cells that are highly interconnected in a circuit. Therefore, the proposed clustering method can reduce the size of large-scale partitioning problems without losing partitioning solution qualities. The performance of the proposed clustering algorithm is evaluated on a standard set of partitioning benchmarks-ISPD98 benchmark suite. The experimental results show that by applying the proposed clustering algorithm, the previously reported best partitioning solutions from state-of-the-art partitioners are further improved.     

3D human posture segmentation by spectral clustering with surface normal constraint

In this paper, we propose a new algorithm for partitioning human posture represented by 3D point clouds sampled from the surface of human body. The algorithm is formed as a constrained extension of the recently developed segmentation method, spectral clustering (SC). Two folds of merits are offered by the algorithm: (1) as a nonlinear method, it is able to deal with the situation that data (point cloud) are sampled from a manifold (the surface of human body) rather than the embedded entire 3D space; (2) by using constraints, it facilitates the integration of multiple similarities for human posture partitioning, and it also helps to reduce the limitations of spectral clustering. We show that the constrained spectral clustering (CSC) still can be solved by generalized eigen-decomposition. Experimental results confirm the effectiveness of the proposed algorithm.     

A Novel Integrated Path Planning Algorithm for Warehouse AGVs

We propose an integrated path planning method for multiple automated guided vehicles performing logistics delivery within a real-world warehouse environ-ment considering obstacles. By applying it on each vehicle, this proposed method enables the vehicle the vehicles have the capabilities for autonomous path planning. The path planning consists of three parts, K-means algorithm based task points clustering, genetic algorithm based task points ordering, and the probabilistic road map based best path search. Vehicle conflict resolution is depending on implementing the probabilistic road map construction considering the realistic map with obstacles. The simulations result validate that the clustering and ordering are necessary for the path planning, both the path planning time and the Automated guided vehicles (AGVs) running time can be dramatically reduced.     

一种基于概率统计的自适应网格聚类算法

针对固定网格划分技术存在的维度可扩展性差,而自适应网格划分技术未充分考虑数据集分布特征等问题,提出了一种基于概率统计理论的自适应网格聚类算法.采用概率统计和图覆盖技术,且能识别任意形状和大小的聚类,时间复杂度是数据集大小和数据维度的线性函数.实验结果表明该聚类是有效的.     

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.     

基于改进指纹聚类的WLAN定位优化方法

将K-means聚类算法应用到无线局域网（WLAN）位置指纹定位中,虽然可以缩短定位时间,但是容易降低定位精度。为了解决此问题,提出了基于改进指纹聚类的WLAN定位优化方法。首先根据接收信号强度标准差来优化初始聚类中心的选取,然后对指纹数据进行聚类处理,最后进行在线定位。实验结果表明,与传统的WLAN位置指纹定位方法和K-means聚类定位方法相比,基于改进指纹聚类的定位优化方法不仅缩短了定位时间,还能有效提高定位精度。     

无线传感网中基于DPAM-MD算法的恶意节点识别研究

随着无线传感器网络的不断发展,恶意节点对其安全造成了极大的威胁。传统的基于信誉阈值的模型无法准确的识别亚攻击性等恶意节点,而且会出现低识别率和高误判率等问题。为了解决这些问题,引入了基于DPAM-MD算法的新型恶意节点识别方法,在传统信誉阈值判断模型的基础上,通过结合曼哈顿度量和DPAM算法识别出亚攻击性节点。算法中提出一种新型的基于密度的聚类算法,并结合簇间和簇内距离均衡化的目标函数,将所有的节点进行分类。该算法可以提高聚类质量,有效缩短聚类时间,提高了恶意节点识别的效率。经仿真实验结果验证,改进后的算法对识别特征不明显的恶意节点效果十分显著。     

基于二叉树锚点的高光谱快速聚类算法

高光谱图像聚类问题一直是图像处理领域的研究热点。谱聚类算法是最流行的聚类算法之一,但其计算复杂度较大,难以处理大规模的高光谱图像数据。由于二叉树能够较快地选取锚点,因此基于二叉树锚点图,充分利用高光谱图像的光谱和空间特性,可保证聚类性能并降低计算复杂度。然而,该聚类算法一般采用有核的聚类方法,因此不可避免地引入了参数调节。在二叉树锚点选取的基础上,提出了一种基于二叉树锚点的高光谱快速聚类算法,该算法创新性地将二叉树锚点选取和无核聚类方法应用于高光谱图像中。首先,利用二叉树从高光谱数据中选取一些具有代表性的锚点;紧接着构造基于锚点的无核相似图,有效避免了通过人为调节热核参数来构造相似图;然后进行谱聚类分析获得聚类结果;最后,将该算法应用到高光谱图像聚类中。该算法不仅提高了聚类速度,还减少了原有热核参数调节。实验结果表明,与传统的聚类算法相比,所提算法能够在较短的时间内获得更佳的聚类精度。