一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

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

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

求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析

旅行商问题（Traveling Salesman Problem，TSP）是组合优化中最典型的NP难问题之一，长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题，并设计出许多高效实用的启发式和宏启发式算法，其中循环LK算法是性能最好和最具代表性的算法之一．作者研究了该算法的运行时间分布：通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合，发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布，并进一步给出了该分布对求解TSP问题的物理意义．作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论．     

随机算法异步并行化的效率分析

随机算法的执行时间具有不确定性,这种不确定性为随机算法的异步并行提供了良好的基础,已有许多计算实验表明了随机算法的异步并行可以达到线性甚至超线性的加速.对于求解SAT问题的随机算法RDP,研究了异步并行效率与运行时间分布和处理器数目之间的关系.应用一种单峰分布──分段线性分布模型来模拟随机算法的运行时间分布.理论分析和计算结果均表明:当处理器数目k较小和单峰位于分布的前部时,随机算法的异步并行具有近线性加速.     

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC－A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC－A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC－A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC－FF表现出相对更好的实验效果。     

SSTT: Efficient local search for GSI global routing

In this paper, a novel global routing algorithm is presented for congestion opti-mization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted,consisting of three optimization sub-strategies: stochastic optimization, deterministic optimiza-tion and local enumeration optimization, to dynamically reconstruct the problem structure. Thus,“transition” can be made from a local minimum point to reach other parts of the search space,traverse the whole search space, and obtain the global (approximate) optimal routing solution.Since any arbitrary initial routing solution can be used as the start point of the search, the initial-ization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.     

Deterministic VLSI block placement algorithm using Less Flexibility First principle

In this paper,a simple while effective deterministic algorithm for solving the VLSI block placement problem is proposed considering the packing area and interconnect wiring simultaneously.The algorithm is based on a principle inspired by observations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle,it is tried to pack blocks with the least packing flexibility on its shape and interconnect requirement to the empty space with the least packing flexibility in a greedy manner.Experimental results demonstrate that the algorithm,though simple,is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristics for other hard problems,such as placement with preplaced modules,placement with L/T shape modules,etc.     

收缩背包问题的并行分枝界限算法

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。     

有固定波长转换器的全光环网波长分配算法

采用波分复用技术的全光网是目前宽带网络研究的方向之一,波长分配是其中主要的算法问题,具有重要的理论和应用价值.研究了具有任意固定波长转换器的环形光网上的波长分配问题.首先,提出了两个对环网上的请求集合预处理的算法,这两个算法可以将请求集合分解成一些连续的循环序列;然后,采用置换群来描述具有固定波长转换器的光环网,基于这种数学表示,提出了对环网上的波长信道进行分解的算法;基于这些算法,进一步提出了一个波长分配算法,该算法对于环形光网上的任意固定转换模式都能给出一个较好的波长分配方案.     

一种基于负载均衡机制的Ad Hoc网络路由协议技术

AdHoc网络是一种无线基础设施支持的移动网络,网络中的节点均由移动主机构成。而路由协议则是移动AdHoc网络中最关键的技术之一,它对网络的性能起决定性作用。首先阐述了AdHoc网络路由协议AODV,分析了其不足之处,给出了一种基于反向路由查找机制、单路径负载均衡和跨层节点拥塞的协议优化方案。