Evaluating Parallel Simulated Evolution Strategies for VLSI Cell Placement

Simulated Evolution (SimE) is an evolutionary metaheuristic that has produced results comparable to well established stochastic heuristics such as SA, TS and GA, with shorter runtimes. However, for optimization problems with a very large set of elements, such as in VLSI cell placement and routing, runtimes can still be very large and parallelization is an attractive option for reducing runtimes. Compared to other metaheuristics, parallelization of SimE has not been extensively explored. This paper presents a comprehensive set of parallelization approaches for SimE when applied to multiobjective VLSI cell placement problem. Each of these approaches are evaluated with respect to SimE characteristics and the constraints imposed by the problem instance. Conclusions drawn can be extended to parallelization of SimE when applied to other optimization problems.      

X射线光刻技术的进展及问题

Ｘ射线光刻是一种能满足下世纪初超大规模集成电路（ＶＬＳＩ）生产的深亚微米图形加工技术。论述了这种光刻技术的发展历史及近年来的主要进展。重点讨论了在Ｘ射线源、接近式曝光和全反射投影曝光等方面取得的成就与存在的问题。展望了这种技术的发展前景     

Open critical area model and extraction algorithm based on the net flow-axis

In the integrated circuit manufacturing process, the critical area extraction is a bottleneck to the layout optimization and the integrated circuit yield estimation. In this paper, we study the problem that the missing material defects may result in the open circuit fault. Combining the mathematical morphology theory, we present a new computation model and a novel extraction algorithm for the open critical area based on the net flow-axis. Firstly, we find the net flow-axis for different nets. Then, the net flow-edges based on the net flow-axis are obtained. Finally, we can extract the open critical area by the mathematical morphology. Compared with the existing methods, the nets need not to divide into the horizontal nets and the vertical nets, and the experimental results show that our model and algorithm can accurately extract the size of the open critical area and obtain the location information of the open circuit critical area.     

An approximation algorithm for dissecting a rectangle into rectangles with specified areas

Given a rectangle R with area α and a set of n positive reals A={a₁,a₂,…,a_n} with ∑_ai∈Aa_i=α, we consider the problem of dissecting R into n rectangles r_i with area so that the set R of resulting rectangles minimizes an objective function such as the sum of the perimeters of the rectangles in R, the maximum perimeter of the rectangles in R, and the maximum aspect ratio of the rectangles in R, where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECT-RATIO, respectively. We propose an O(nlogn) time algorithm that finds a dissection R of R that is a 1.25-approximate solution to PERI-SUM, a -approximate solution to PERI-MAX, and has an aspect ratio at most , where ρ(R) denotes the aspect ratio of R.     

Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].     

薄板结构加筋布局优化设计方法研究

提出一种两步优化策略,以加筋板结构的固有频率最大化为目标函数,以结构所受外载荷作用的最大静变形为约束条件,开展薄板结构加筋构件的布局优化设计研究。为了降低加筋布局优化的难度,提高优化设计的效率,将加筋等效为一系列弹性铰（点）支撑,以便快速获得加筋横向移动的灵敏度信息。在基本不改变结构重量的情形下,通过合理布局加筋位置,能显著改善结构的刚度分布,提高结构的整体承载能力。随后,小幅调整加筋的截面尺寸,以满足对结构最大变形的设计要求。最后,用两个算例验证了所提优化方法的可行性和有效性。     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

基于人流密集度的网点数量与布局预测模型——以宁波市公共自行车系统为例

针对宁波市公共自行车网点数量增加而新使用者增量和日周转率呈现下行的趋势, 对网点数量和布局进行分析和建模. 首先, 通过K-means聚类方法对不同网点按日周转率进行分类, 结果发现日周转率在4以下的低效网点高达52.86%, 低于0.5的网点占9.73%, 而在15以上的超负载网点占2.5%, 两极分化现象非常明显. 其次, 讨论了宁波市城市公共自行车专项规划中基于面积和服务人口的网点数量预测模型的不足之处. 最后, 以较为成熟的城市公交线路为基础, 通过统计各公交站点的人流密集度, 提出了基于人流密集度的网点数量与布局预测模型, 并给出了网点在空间上的布局. 同时指出各城市公共自行车网点数量与布局问题既有发展共性又有地域个性, 基于公交线路人流密集度模型具有普适性价值.     

卫星舱内长方体群布局的优化模型及全局优化算法

本文研究了卫星舱内长方体群优化问题,建立了一个三维布局优化模型,并用图论,群论等工具克服了布局优化问题时断时续性质带来的困难,在此基础上构造了一个全局收敛的优化算法,文中所用的方法可用于求解类似问题。     

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.