无线Ad Hoc网络Steiner树实现协议研究

针对无线Ad hoc网络多跳,拓扑结构随时可能动态变化,协作节点间数据传输需实时性强等问题,利用Netlog语言宣告声明最小Steiner树协议的构造算法方法适应解决。协议可快速构造一棵近似最小的Steiner树,每个节点独立运行声明Steiner树协议,构造Steiner节点间的虚拟全联通网络,在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边,继续构造最小代价生成树,最后将此树上的非Steiner节点的叶子节点删除,近似得到最小代价Steiner树,该方法在实验平台上得以验证,为无线移动网络中资源的选择利用提供了一种新的可尝试性的新方法。     

VLSI总体布线算法研究与实现

总体布线是布图设计中一个极为重要的设计环节。本文提出了基于可分离最小生成树(SMST)的优化L形直角斯坦(Steiner)树(L_RST)和优化Z_RST的算法。该算法实现上绕开计算重合度问题，以新的角度计算代价。利用基于tile的结构，实现了伪管脚(pseudo pin)的分配，适用于现代多层布线需求。最后文章研究了同时考虑串扰和时延的综合性能驱动的总体布线算法改进。     

加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要.本文提出了加权的基于多播节点的多播路由算法（WDDMC算法）.由于改变了DDMC（Destination-Driven routing for low-cost Multicast ）算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树.在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法.该算法的复杂度与DDMC算法完全相同.     

一种改进的Steiner树启发式算法

最小Steiner树问题是NP完全问题，关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在MPH算法基础上，对于经过某些关键节点的短路径优先考虑，提出了KBMPH算法，从而实现更多链路的共享。在随机网络上的仿真结果表明，极大多数情况下，在准Steiner树的网络费用KBMPH算法优于MPH算法，KBMPH算法的复杂度为O（n^3）。     

多材料Terminal Steiner树拼接问题的近似算法研究

在赋权连通网络下,给定多种材料及每种材料的费用和拼接费用,以便寻找赋权网络中的一棵Terminal Steiner树,并用给定材料连接此树,使得总费用及材料根数达到最小,记此问题为多材料Terminal Steiner树拼接问题。为了解决Terminal Steiner树拼接问题,首先分析Terminal Steiner树拼接问题是NP问题,不存在多项式时间算法;然后基于Steiner树问题和变尺寸装箱问题的近似算法及算法复杂度,给出多材料的Terminal Steiner树拼接问题的一个近似算法;最后证明算法的近似值及近似算法的时间复杂度。     

基于满Steiner树问题的水下无线传感器网络拓扑愈合算法研究

建立了水下无线传感器网络模型,对拓扑愈合问题进行了形式化描述,该问题最终映射到数学上的满Steiner树问题.针对满Steiner树问题设计了一种近似的拓扑愈合算法,通过把自移动节点迁移至合适位置,不仅使拓扑得以愈合,还能够改善时延和能耗指标.仿真实验结果表明,该算法能愈合通信拓扑至较优状态,降低了传输时延和能耗,并能有效地延长水下传感器网络生命期.     

层次化片上网络结构的簇生成算法

半导体工艺的发展及嵌入式电子产品复杂度的不断增长,系统芯片互连结构的吞吐量、功耗、信号完整性、延迟以及时钟同步等问题更加复杂.基于总线的片上通信结构不足以提供良好的通信能力,出现了以片上网络为核心的通信结构.本文提出了层次化片上网络设计中,根据实现工艺和应用需求,进行层次划分的簇生成算法.实验表明,通过使用该算法,能够有效的分配系统芯片的内部通信,提高系统性能,降低硬件实现开销,同时满足一定的服务质量需求.     

IC设计技术中的IP核互连

随着IC设计复杂度的不断提高,在SoC中集成的IP核越来越多,基于片上总线的SOC设计技术解决了大规模集成电路的设计难点,但是片上总线的应用带来了可扩展性差、平均通信效率低等问题。近几年来,将英特网络中分层互连的思想引入到SOC设计中IP核的互连上来,提出了全新的集成电路体系结构——片上网络（NOC）,NOC从多处理体系结构、消除时钟树以节省资源、实现并行通信等几个方面,展示了优于总线结构的本质和特性,成功地解决了SOC设计中存在的问题。     

基于高维空间典型样本Steiner最小树覆盖模型的一类分类算法

最小生成树数据描述方法在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供同类样本分布描述,这种描述存在分支多覆盖模型复杂,且局部覆盖不够合理的问题。针对该问题,依据特征空间中同类样本分布的连续性规律,提出基于高维空间典型样本Steiner最小树覆盖模型的一类分类算法,该算法首先对目标类训练集进行样本修剪,去除冗余信息和噪声信息,选择最具代表性的样本作为训练集,然后对保留的典型样本构建Steiner最小树覆盖模型。算法分析和仿真实验结果表明,相比最小生成树数据描述,文中提出的方法能在较低覆盖模型复杂度的前提下更合理的描述目标类样本空间分布,构建更合理的覆盖模型,在分类正确率和适用样本规模上都表现出一定的优越性。      

N个城市间的最经济的网络建设

N个城市闾有多种的网络建设方案,本文使用最小支撑树的原理,运用算法中的普林算法进行运算。褥到的最小生成树使n个城市闻的连接是连通的,而且是最经济的在各种网络建设方案中。     

A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles

The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a hot topic in very-large-scale integration physical design. In practice, most of the obstacles occupy the device layer and certain lower metal layers. Therefore, we can place wires on top of the obstacles. To maximize routing resources over obstacles, we propose a heuristic for constructing a rectilinear Steiner tree with slew constraints. Our algorithm adopts an extended rectilinear full Steiner tree grid as the routing graph. We mark two types of Steiner point candidates, which are used for constructing Steiner trees and refining solutions. A shortest path heuristic variant is designed for constructing Steiner trees and it takes into account slew constraint by inhibiting growth. Furthermore, we use a pre-computed strategy to avoid calculating slew rate repeatedly. Experimental results show that our algorithm maximizes routing resources over obstacles and saves routing resources outside obstacles. Compared with the conventional OARSMT algorithm, our algorithm reduces the wire length outside obstacles by as much as 18.74% and total wire length by as much as 6.03%. Our algorithm improves the latest related algorithm by approximately 2% in terms of wire length within a reasonable running time. Additionally, calculating the slew rate only accounts for approximately 15% of the total runing time.     

Destination-driven routing for low-cost multicast

We present a destination-driven algorithm that optimizes for applications, such as group video or teleconferencing, that require multicast trees with low total cost. The destination-driven algorithm uses a greedy strategy based on shortest-path trees and minimal spanning trees but biases routes through destinations. The performance of the algorithm is analyzed through extensive simulation and compared with several Steiner tree heuristics and the popular shortest-path tree (SPT) method. The algorithm is found to produce trees with significantly lower overall cost than the SPT while maintaining reasonable per-destination performance. Its performance also compares well with other known Steiner heuristics. Moreover, the algorithm does not suffer from high complexity common to most Steiner tree heuristics and builds a route by querying only incident links for cost information     

Obstacle-avoiding rectilinear minimum-delay Steiner tree construction toward IP-block-based SOC design

With system-on-chip design, IP blocks form routing obstacles that deteriorate global interconnect delay. In this paper, we present a new approach for obstacle-avoiding rectilinear minimal delay Steiner tree (OARMDST) construction. We formalize the solving of minimum delay tree through the concept of an extended minimization function, and trade the objective into a top-down recursion, which wisely produces delay minimization from source to critical sinks. We analyze the topology generation with treatment of obstacles and exploit the connection flexibilities. To our knowledge, this is the first in-depth study of OARMDST problem based on topological construction. Experimental results are given to demonstrate the efficiency of the algorithm.     

A full-scale solution to the rectilinear obstacle-avoiding Steiner problem

Routing is one of the important steps in very/ultra large-scale integration (VLSI/ULSI) physical design. Rectilinear Steiner minimal tree (RSMT) construction is an essential part of routing. Macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. However, OARSMT algorithms for multi-terminal net routing still cannot meet the requirements of practical applications. This paper focuses on the OARSMT problem and gives a solution to full-scale nets based on two algorithms, namely An-OARSMan and FORSTer. (1) Based on ant colony optimization (ACO), An-OARSMan can be used for common scale nets with less than 100 terminals in a circuit. An heuristic, greedy obstacle penalty distance (OP-distance), is used in the algorithm and performed on the track graph. (2) FORSTer is a three-step heuristic used for large-scale nets with more than 100 terminals in a circuit. In Step 1, it first partitions all terminals into some subsets in the presence of obstacles. In Step 2, it then connects terminals in each connected graph with one or more trees, respectively. In Step 3, it finally connects the forest consisting of trees constructed in Step 2 into a complete Steiner tree spanning all terminals while avoiding all obstacles. (3) These two graph-based algorithms have been implemented and tested on different kinds of cases. Experimental results show that An-OARSMan can handle both convex and concave polygon obstacles with short wire length. It achieves the optimal solution in the cases with no more than seven terminals. The experimental results also show that FORSTer has short running time, which is suitable for routing large-scale nets among obstacles, even for routing a net with one thousand terminals in the presence of 100 rectangular obstacles.     

A Simple BCH Decoder for NoC Interconnects and SoC Buses

Network on a chip (NoC) uses packet-switched network to implement interconnections in System on chip (SoC). In SoC design, performance and energy efficiency are respectively the first and second priorities, and optimal on-chip communication should decrease the power consumption and area overhead. In this work, a simplified BCH codec is proposed for reliable communication in NoC and SoC. It performs BCH error corrections without Berlekamp's algorithm, only using reduced syndrome bits to determine error patterns. The error locations can be found by looking up tables, by which the possible errors are directly corrected. Only one matrix product and one ROM access are required in the BCH decoder. The proposed (20, 8, 2) and (31, 16, 3) decoders in the paper can be easily applied for error corrections of interconnects and buses for NoC and SoC. It is also beneficial to correct data lines without length definition and controllines without storage.     

Multicast tree generation in networks with asymmetric links

We formulate the problem of multicast tree generation as one of computing a directed Steiner tree of minimal cost. In this context, we present a polynomial-time algorithm that provides for trade-off selection, using a single parameter κ, between the tree-cost (Steiner cost) and the run time efficiency. Further, the same algorithm may be used for delay optimization or tree-cost minimization simply by configuring the value of κ appropriately. We present theoretical and experimental analysis characterizing the problem and the performance of our algorithm. Theoretically, we show that it is highly unlikely that there exists a polynomial-time algorithm with a performance guarantee of constant times optimum cost, introduce metrics for measuring the asymmetry of graphs, and show that the worst-case cost of the tree produced by our algorithm is, at most, twice the optimum cost times the asymmetry, for two of these asymmetry metrics. For graphs with bounded asymmetry, this gives constant times optimum performance guarantee. We also show that three well-known algorithms for (undirected) Steiner trees are but particular cases of our algorithm. Our experimental study shows that operating at a low κ gives nearly best possible expected tree cost while maintaining acceptable run-time efficiency     

基于统计的高效决策树分组分类算法

基于决策树的分组分类算法因易于实现和高效性,在快速分组分类中广泛使用。决策树算法的基本目标是构造一棵存储高效且查找时间复杂度低的决策树。设计了一种基于规则集统计特性和评价指标的决策树算法——HyperEC 算法。HyperEC算法避免了在构建决策树过程中决策树高度过高和存储空间膨胀的问题。HyperEC算法对IP地址长度不敏感,同样适用于IPv6的多维分组分类。实验证明,HyperEC算法当规则数量较少时,与HyperCuts基本相同,但随着规则数量的增加,该算法在决策树高度、存储空间占用和查找性能方面都明显优于经典的决策树算法。     

考虑光学邻近效应的详细布线算法

提出了一种考虑光学邻近效应的详细布线算法.该算法在布线过程中,充分考虑了线网走线相对位置及布线线形对其光学邻近效应的影响,通过相应的光刻模拟模型定义了用于估计光学邻近效应(optical proximity effect,OPE)的OPE费用函数,并采用OPE费用阈值控制Steiner树的生长方向和走线路径的选择,同时兼顾线网长度.为提高算法效率,避免布线过程中反复调用光学模拟程序带来的算法运行速度慢的问题,对可能的走线模式建立了计算OPE费用所需的光强查找表格,使算法的运行速度大大提高.在实际的工业用例上的实验结果表明,本文所提出的详细布线算法使布线结果中的OPE问题得到很大程度的改善,有利于后处理过程中的光学邻近效应校正技术的运用,算法的运行时间是可以接受的.