Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

基于改进遗传算法的布局优化子问题

本针对子问题，构造了布局子问题(关于同构布局等价类)的改进遗传算法。将该算法应用于二维布局优化子问题，数值实验表明该算法能够在很好地保持图元的邻接关系的前提下找到子问题的最优解。由于布局优化问题可分解为有限个子问题，所以利用该算法可以找到整个布局优化问题的全局最优解。     

开关布局中本质不同的开关线路计算

通过对开关布局问题的研究，来解决一类象开关线路一样比较特殊，比较复杂的布局优化问题。从而寻找出这类问题的全局优化算法。本应用对称群对集合的作用，轨道，不动点等讨论了开关布局问题，给出了本质不同的开关线路个数的计算公式。     

Ultra-trace analysis of U,Th, Ca and selected heavy metals in high purity refractory metals with isotope dilution mass spectrometry

A method for the determination of trace impurities (U, Th, Ca, Fe, Cr, Ni, Cu, and Cd) in the refractory metals molybdenum and tungsten with isotope dilution mass Spectrometry (IDMS) has been developed. This method enables determinations of uranium and thorium down to the lowest pg/g level with high precision and accuracy. Selective chromatographic, extractive and electrolytic methods for the trace-matrix separation were combined with positive thermal ionization mass spectrometry. Different samples of high purity (4N) and of ultra high purity (UHP) materials for advanced technologies were analysed. The detection limits reached are (in ng/g): U 0.006, Th 0.008, Ca 10, Fe 19, Cr 0.5, Ni 0.6, Cu 2.7, and Cd 0.12. A comparison of results with other sensitive analytical methods (ICP-MS, GDMS, SIMS) makes obvious the urgent necessity of a reliable calibration method like IDMS because the analytical results obtained by the other methods often spread over a wide range.     

“神龙一号”加速器束流输运系统研制

文章系统介绍了“神龙一号”直线感应加速器束流输运系统的研制过程和取得的成果, 重点阐述了螺线管线圈、二极校正线圈、多功能腔等关键单元部件的设计、传输元件的磁轴测量和准直安装、束线的总体布局、束流调试等研究内容. 束流调试结果表明, 该束流传输线的设计是成功的, 并且具有较宽的动态适应范围. 最后, 结合束流调试的经验, 提出了一些建议供以后工作参考.     

群集建筑中大跨裙摆屋盖风荷载特性的数值模拟研究

以苏州太平金融大厦为工程背景,针对其大跨裙摆屋盖的风荷载作用,首先采用RNG k-ε模型模拟分析了其平均风压分布规律,以及风向变化对屋盖表面风荷载体型系数的影响;其次,引入干扰因子IF,探讨了周边建筑对大跨裙摆屋盖风荷载的气动干扰作用。结果表明:0°风向下,走廊上方屋盖两侧区域出现“上吸下顶”的叠加作用;90°风向下屋盖北侧飘带末端区域受到狭道风效应出现正压集中现象;风向变化对大跨裙摆屋盖的风荷载体型系数分布影响较大;且周围建筑物对大跨裙摆屋盖的气动干扰效应明显,主要表现为风压“遮挡效应”,而局部区域表现为风压“放大效应”。     

油田注水系统拓扑布局优化的混合遗传算法

以投资最小为目标函数,建立了注水系统拓扑布局优化数学模型.根据模型特点,将优化问题分为两层,分别采用遗传算法和非线性优化方法进行求解.并对遗传算法的操作过程进行了改进,调整了适应函数,改进了交叉和变异操作,结合了模拟退火算法,在操作过程中使约束条件得到满足,减少了不可行解的产生,使遗传算法的优化性能得到了提高.优化算例说明了该方法的有效性.     

基于变密度法的平模台振加强筋布局优化

针对混凝土预制构件水平成型振动台(简称平模台振)振动效果改进的问题,提出了通过优化振动台面加强筋布局来提高其振动效果的方法.基于变密度拓扑优化法,建立以加强筋单元相对密度为设计变量,振动台面柔度最小为目标的优化模型,并进行灵敏度分析,采用最优准则法求解优化模型;根据拓扑优化结果,对振动台面加强筋进行布局优化,获得了合理...     

Parallelizing Tabu Search on a Cluster of Heterogeneous Workstations

In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation.     

神经网络在非线性规划中的应用

本文对蔡少棠[1 ] ,[2 ] 等提出的非线性规划神经网络作了改进 ,使得该神经网络适合于通用VLSI技术实现 .