装填布局的同构和非同构模式

装填布局问题在工程实践上具有广泛的应用，在理论上属于NPC问题．布局模式是其中的一个重要问题．该文以卫星舱布局方案设计为背景，研究装填布局模式问题，定义了同构和非同构布局模式、待布物的布局等价关系等概念，给出了关系矩阵和模式矩阵以及它们的变换，描述了布局模式控制区和非同构度，提出了同构和非同构布局模式的识别及构造方法．文后讨论了布局模式的若干应用．该工作希望能为缓解装填布局优化问题求解时存在的组合爆炸以及构造高效的求解算法提供启发和借鉴．     

容许两个盘故障的磁盘阵列数据布局与图分解的条件和存在性研究

从一个新的途径讨论容许两个盘故障的磁盘阵列数据布局：把由数据单元和通过“异或”运算得到的校验单元组成的校验组用一个图表示，把校验组容许两个盘故障的阵列布局归结为校验组的单元集合的划分，进而转化为校验组的图的顶点和边组成集合的满足一定条件的分解．证明了校验组容许两个盘故障的单元集合划分的充分必要条件及存在性；讨论了优化阵列布局方案性能的条件；给出了阵列布局的步骤．从而为设计具有最优性能的容许两个盘故障的磁盘阵列数据布局方案提供了有效的途径．     

三维实体布局的八叉树语言及优化算法

本文设计了一个八叉树操作语言，并利用该语言实现了三维实体布局的优化算法，该算法能从任一初始布局可行解迅速收敛到一个局部最优解上，从而明显改善初始布局方案。文章最后给出了一个简单的应用实例。     

并行混合遗传算法及其在布局设计中的应用

布局问题在理沦上属于NPC问题，在工程实践上具有广泛的应用。为较好地求解该问题，该文以并行遗传算法（PGA）为基础，针对其早熟和收敛速度慢两大缺陷加以改进，给出了一种并行混合遗传算法(PHGA)．PHGA采用该文提出的压力插他排序选择算子，起到了双重作用：一是在进化初期可以防止早熟；二是在进化后期有利于加快算法的收敛。算法利用混沌初始化可提高初始群体的质量，并依自适应交叉和变异概率值对子群体进行分类，与Powell法混合可以很好地改善算法的局部搜索性能。文中通过标准函数优化和布局设计的算例验证了该算法的可行性和有效性。     

遗传布局算法

VLSI门阵列模式布局是一类NP完全问题，传统的分析、研究方法和求解策略不能提供优化布局。文中将遗传算法应用于门阵列模式布局，提出了遗传布局算法，设计了相应的选择函数、交叉算子和变异算子，使布局的构形更趋合理。模拟结果表明，应用遗传布局算法能在较短的时间内提供优化解，为解决大规模、复杂的布局问题提供了广阔的前景。     

矩形件带排样的一种遗传算法

采用遗传算法解决矩形件带排样问题,用带符号的有序整数串作为初始种群个体,改善了初始个体解的质量．提出基于最低水平线的择优插入算法,在解码过程中动态地调整个体中的零件顺序,选取最适合的零件进行填充,使零件排放紧凑,提高了材料的利用率．对20多道基准排样例题的实验计算结果表明,文中算法速度快,所得排样方案的材料利用率高．最后提出利用该算法解决VLSI模块布局问题的方法框架．     

一个有效的圆片规模布局算法

本文提出了一个圆片规模布局算法，它是国外一个相应算法的改进形式，区别在于利用力定向布局法的方式不同。在相对位置阶段，该算法利用布局的层次特性将需确定所有电路元件相对位置的问题缩减至仅需确定宏电路元件相对位置的问题；在实际位置阶段，采用分治策略和取消前阶段层次划分的方式回避了需确定任意元实际位置的问题．其时间复杂度远低于国外相应算法．     

自动布局布线程序

功述描述了用于规划芯片的自动布局布线程序。其特点是在单元电路版图实现之前进行布局布线以及布线是在单元内部进行，不存在专门的布线通道。这种布图模式，以多端网连接模型作为布局布线的连接模型，并以布线均匀作为主要的目标函数。 整个程序模块分为矩阵网格规划和布局，总体布线，端口分配三部分。在布局中采用最小切割算法。初始布线以布线均匀，连线长度最短为目标，并采用一个基于布线均匀的“重心“算法。通过再布线和通     

采用遗传算法的手绘草图关系模板生成方法

草图理解包含两个方面：草图图形识别和草图布局分析．但目前的研究大部分集中于一些特殊图形的草图识别上。实际上，草图布局分析对草图信息内容的发现，尤其是在获取其构思方面更为重要。本文为事实草图图形的布局分析提出了一种基于遗传算法的模板生成方法．在定义和描绘了布局模式的基础上．本方法能找出有潜在语义的图形对象间的模式。实验表明：遗传算法能够有效找出明显或是潜在的模式，并能很减轻手工标注模式的负担。     

一种基于二叉树结构表达的矩形物体布局的启发式方法

本文提出了一种利用二叉树结构表达矩形物体布局状态空间的方法．通过将布局空间依次分割，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来完成不同大小矩形物体的布局方案的确定．通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案．同时，所得布局方案均满足工业上一刀切的要求．实验结果证明了该算法的灵活性和有效性．     

SVM based layout retargeting for fast and regularized inverse lithography

Inverse lithography technology （ILT）, also known as pixel-based optical proximity correction （PB-OPC）, has shown promising capability in pushing the current 193 nm lithography to its limit. By treating the mask optimization process as an inverse problem in lithography, ILT provides a more complete exploration of the solution space and better pattern fidelity than the tradi-tional edge-based OPC. However, the existing methods of ILT are extremely time-consuming due to the slow convergence of the optimization process. To address this issue, in this paper we propose a support vector machine （SVM） based layout retargeting method for ILT, which is designed to generate a good initial input mask for the optimization process and promote the convergence speed. Supervised by optimized masks of training layouts generated by conventional ILT, SVM models are learned and used to predict the initial pixel values in the‘undefined areas’ of the new layout. By this process, an initial input mask close to the final optimized mask of the new layout is generated, which reduces iterations needed in the following optimization process. Manu-facturability is another critical issue in ILT;however, the mask generated by our layout retargeting method is quite irregular due to the prediction inaccuracy of the SVM models. To compensate for this drawback, a spatial filter is employed to regularize the retargeted mask for complexity reduction. We implemented our layout retargeting method with a regularized level-set based ILT （LSB-ILT） algorithm under partially coherent illumination conditions. Experimental results show that with an initial input mask generated by our layout retargeting method, the number of iterations needed in the optimization process and runtime of the whole process in ILT are reduced by 70.8%and 69.0%, respectively.     

Disc cutters plane layout design of the full-face rock tunnel boring machine (TBM) based on different layout patterns

The quality of plane layout design of the disc cutters for the full-face rock tunnel boring machine (TBM) directly affects the balance of force distribution on the cutter head during the excavating. Various layout patterns have been adopted in practice during the layout design of the disc cutters. Considering the engineering technical requirements and the corresponding structure design requirements of the cutter head, this study formulates a nonlinear multi-objective mathematical model with multiple constraints for the disc cutters plane layout design, and analyses the characteristics of a multi-spiral layout pattern, a dynamic star layout pattern and a stochastic layout pattern. And then a genetic algorithm is employed to solve a disc cutters’ multi-spiral layout problem, and a cooperative co-evolutionary genetic algorithm (CCGA) is utilized to solve a disc cutters’ star or stochastic layout problems. The emphasis was put on the study of superiority of three different layout patterns. Finally, an instance of the disc cutters’ plane layout design was solved by the proposed methods using three different kinds of layout patterns. Experimental results showed the effectiveness of the method of combining the mathematical model with the algorithms, and the pros and cons of the three layout patterns.     

A method of evaluating VDT screen layout by eye movement analysis

Abstract

The method for evaluating VDT screen layout by eye movements is studied. When the subjects read from the VDT screen, the change in their line of sight was measured by their eye movements. The measured eye movement patterns were divided into the sequential and rereading processes. When related to these characteristics, the performance of subjects was found to be good when the sequential process predominated over the rereading process. The eye movement pattern was shown to change with screen layout. The eye movement pattern proved effective in determining that tabular format is more legible than textual format. This confirmed the usefulness of the method of evaluating VDT screen layout by the eye movement pattern.     

MACSYM: A hierarchical parallel image processing system for event-driven pattern understanding of documents

MACSYM is a hierarchical parallel processing system for pattern understanding applications. It features event-driven parallel processing for knowledge-based understanding of document images. The system is composed of a master processor, slave processors and a large shared memory, and is equipped with versatile communication facilities. The parallel processing software system M.UM has been developed on MACSYM. It supplies a parallel processing language MacC, an extended version of C, and supports the programming for document image understanding. The Japanese newspaper layout understanding system EXPRESS is being developed on MACSYM. It analyzes a newspaper image and extracts articles in a few seconds.     

Characterization and Parallelization of Decision-Tree Induction

This paper examines the performance and memory-access behavior of the C4.5 decision-tree induction program, a representative example of data mining applications, for both uniprocessor and parallel implementations. The goals of this paper are to characterize C4.5, in particular its memory hierarchy usage, and to decrease the run-time of C4.5 via algorithmic improvement and parallelization. Performance is studied via RSIM, an execution driven simulator, for three uniprocessor models that exploit instruction level parallelism to varying degrees. This paper makes the following four contributions. The first contribution is presenting a complete characterization of the C4.5 decision-tree induction program. The results show that with the exception of the input data set, the working set fits into an 8-Kbyte data cache; the instruction working set also fits into an 8-Kbyte instruction cache. For data sets larger than the L2 cache, performance is limited by accesses to main memory. The results further establish that four-way issue can provide up to a factor of two performance improvement over single-issue for larger L2 caches; for smaller L2 caches, out-of-order dispatch provides a large performance improvement over in-order dispatch. The second contribution made by this paper is examining the effect on the memory hierarchy of changing the layout of the input dataset in memory, showing again that the performance is limited by memory accesses. One proposed data layout decreases the dynamic instruction count by up to 24%, but usually results in lower performance due to worse cache behavior. Another proposed data layout does not improve the dynamic instruction count over the original layout, but has better cache behavior and decreases the run-time by up to a factor of two. Third, this paper presents the first decision-tree induction program parallelized for a ccNUMA architecture. A method for splitting the decision tree hash table is discussed that allows the hash table to be updated and accessed simultaneously without the use of locks. The performance of the parallel version is compared to the original version of C4.5 and a uniprocessor version of C4.5 using the best data layout found. Speedup curves from a six-processor Sun E4000 SMP system show a speedup on the induction step of 3.99, and simulation results show that the performance is mostly unaffected by increasing the remote memory access time until it is over a factor of ten greater than the local memory access time. Last, this paper characterizes the parallelized decision-tree induction program. Compared to the uniprocessor version, the parallel version exerts significantly less pressure on the memory hierarchy, with the exception of having a much larger first level data working set.     

Exact truss topology optimization for external loads and friction forces

In replying to a valuable Discussion by Mariano Vázquez Espi, the authors show that the problem of friction forces in general can be handled by the Prager-Rozvany layout theory, and the optimal Michell layout does not always correspond to the maximum value of the static friction force. Moreover, it is explained that discontinuities in the specific cost function can be accommodated by an extended version of the Prager-Shield optimality criteria, which was already demonstrated in the second author’s first (1976) book.     

A genetic algorithm with the heuristic procedure to solve the multi-line layout problem

The paper presents a genetic algorithm-based meta-heuristic to solve the facility layout problem (FLP) in a manufacturing system, where the material flow pattern of the multi-line layout is considered with the multi-products. The matrix encoding technique has been used for the chromosomes under the objective of minimizing the total material handling cost. The proposed algorithm produces a table with the descending order of the data corresponding to the input values of the flow and cost data. The generated table is used to create a schematic representation of the facilities, which in turn is utilized to heuristically generate the initial population of the chromosomes and to handle the heuristic crossover and mutation operators. The efficiency of the proposed algorithm has been proved through solving the two examples with the total cost less than the other genetic algorithms, CRAFT algorithm, and entropy-based algorithm.     

A layout algorithm for signaling pathways

Visualization is crucial to the effective analysis of biological pathways. A poorly laid out pathway confuses the user, while a well laid out one improves the user’s comprehension of the underlying biological phenomenon.We present a new, elegant algorithm for layout of biological signaling pathways. Our algorithm uses a force-directed layout scheme, taking into account directional and rectangular regional constraints enforced by different molecular interaction types and subcellular locations in a cell. The algorithm has been successfully implemented as part of a pathway visualization and analysis toolkit named Patika, and results with respect to computational complexity and quality of the layout have been found satisfactory. The algorithm may be easily adapted to be used in other applications with similar conventions and constraints as well.Patika version 1.0 beta is available upon request at http://www.patika.org.     

Parallel versions of Stone's strongly implicit algorithm

In this paper, we describe various methods of deriving a parallel version of Stone's Strongly Implicit Procedure (SIP) for solving sparse linear equations arising from finite difference approximation to partial differential equations (PDEs). Sequential versions of this algorithm have been very successful in solving semi‐conductor, heat conduction and flow simulation problems and an efficient parallel version would enable much larger simulations to be run. An initial investigation of various parallelizing strategies was undertaken using a version of high performance Fortran (HPF) and the best methods were reprogrammed using the MPI message passing libraries for increased efficiency. Early attempts concentrated on developing a parallel version of the characteristic wavefront computation pattern of the existing sequential SIP code. However, a red‐black ordering of grid points, similar to that used in parallel versions of the Gauss–Seidel algorithm, is shown to be far more efficient. The results of both the wavefront and red‐black MPI based algorithms are reported for various size problems and number of processors on a sixteen node IBM SP2. Copyright © 2001 John Wiley & Sons, Ltd.