一个新的MOS模拟单元电路版图的STACK生成方法

提出了一种新的MOS模拟单元电路的STACK版图自动生成方法。该方法将电路网表映射为扩散图,基于扩散图进行电路划分、模板匹配和对称查找。提出的对称查找算法适用于非全对称电路的最大匹配对称结构查找。文中改进了Atallah欧拉路径生成算法,通过增加哑元条保证欧拉路 径的生成。对生成的STACK,采用分布式寄生电容模型计算各个节点的寄生电容,并计算STACK的面积和形状,以确保其能够满足设计要求。     

在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.     

公交网络下的一种费用限制最小时态路径查询索引

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△_max·|E|·（log|E|+△_max））,其中,|V|表示顶点数,|E|表示边数,△_max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素.     

基于X.400系列建议的电子邮政系统

本文介绍了一个基于X.400系列标准而设计并在微机上实现的电子邮政系统的总体结构及主要模块功能． 并给出了用户代理UA及传输代理MTA的实现算法流图。对MHS在微机上的实现作了研究和探讨。     

一类扩展的动态描述逻辑

作为描述逻辑的扩展,动态描述逻辑为语义Web服务的建模和推理提供了一种有效途径.在将语义Web服务建模为动作之后,动态描述逻辑从动作执行结果的角度提供了丰富的推理机制,但对于动作的执行过程却不能加以处理.借鉴Pratt关于命题动态逻辑的相关研究,一方面,对动态描述逻辑中动作的语义重新进行定义,将每个动作解释为由关于可能世界的序列组成的集合;另一方面,在动态描述逻辑中引入动作过程断言,用来对动作的执行过程加以刻画.在此基础上提出一类扩展的动态描述逻辑EDDL(X),其中的X表示从ALC(attributive language with complements)到SHOIN(D)等具有不同描述能力的描述逻辑.以X为描述逻辑ALCQO(attributive language with complements,qualified number restrictions and nominals)的情况为例,给出了EDDL(ALCQO)的表判定算法,并证明了算法的可终止性、可靠性和完备性.EDDL(X)可以从动作执行过程和动作执行结果两个方面对动作进行全面的刻画和推理,为语义Web服务的建模和推理提供了进一步的逻辑支持.     

一种基于K-Means局部最优性的高效聚类算法

K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为(L混合循环术语集的LCS和MSC推理提供了理论基础.     

排序的相互k-Skyband查询算法

不同于传统的k-Skyband 查询方法,提出一种相互k-Skyband 查询(MkSB),它从对称角度执行Skyline查询,找出所有既在q的动态k-Skyband(DkSB)中又在q的反向k-Skyband(RkSB)中的数据对象.进一步地,为了更好地支持用户决策和数据分析,排序操作被引入到MkSB算法中.因为MkSB 需要执行q的DkSB 和反向RkSB,故它需要遍历索引多次,从而导致了大量冗余的I/O 开销.利用信息重用技术和若干有效的修剪方法,MkSB 将多次的索引搜索合并成单次,极大地降低了I/O访问次数.同时,证明了基于窗口查询的MkSB(WMkSB)算法具有最低的I/O 代价.在真实与合成数据集上的实验结果表明,所提出的算法是有效的且明显胜过基于BBS 的算法,尤其WMkSB 算法具有极少的I/O 开销,通常能够减少95%以上的冗余I/O.     

基于OBDD的描述逻辑εL循环术语集推理

循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图（ordered binary decision diagram,简称OBDD）是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑循环术语集的推理.首先,针对描述逻辑εL中的循环术语集,给出了描述图上关于最大模拟关系的重要性质,并借助集合表示和集合运算对该性质进行了表述和证明.在此基础上,应用布尔函数对描述图进行编码,给出了基于OBDD求解最大模拟关系的方法,进而给出了最大不动点语义下基于OBDD对概念包含关系进行判定的算法;接下来,基于OBDD给出了求解描述图中可以到达循环路径的所有结点的方法,进而给出了最小不动点语义下基于OBDD对概念包含关系进行判定的算法;最后,对算法的正确性、复杂度等进行了分析和证明,并对算法进行了编程实现,给出了关于计算性能的实验结果.该工作为循环术语集的推理提供了一条有效途径,也为OBDD在逻辑推理中的应用提供了新的案例.     

完全析取范式群判定SHOIN(D)-可满足性

针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.     

Fast evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm.     

A parallel approach to the Eulerian cycle problem

A novel parallel approach for constructing Eulerian cycles of a given graph is presented. The proposed approach constitutes a combination of genetic algorithms and artificial neural networks. By tackling the Eulerian cycle problem as a constraint optimization problem, Eulerian cycle existence is determined, and either Eulerian cycles (if they exist) or paths encompassing the greatest possible number of edges (maximal traversal of edges, with edges traversed no more than once) are consistently constructed. Apart from being of theoretical interest, Eulerian cycle existence and construction have recently found significant applications in such areas of VLSI circuit design, RAM fault detection, and CPU access. © 2002 Wiley Periodicals, Inc.     

Conjugate symmetry

Conjugate symmetry is an entirely new approach to symmetric Boolean functions that can be used to extend existing methods for handling symmetric functions to a much wider class of functions. These are functions that currently appear to have no symmetries of any kind. Conjugate symmetries occur widely in practice. In fact, we show that even the simplest circuits exhibit conjugate symmetry. To demonstrate the effectiveness of conjugate symmetry we modify an existing simulation algorithm, the hyperlinear algorithm, to take advantage of conjugate symmetry. This algorithm can simulate symmetric functions faster than non-symmetric ones, but due to the rarity of symmetric functions, this optimization is of limited benefit. Because the standard benchmark circuits contain many symmetries it is possible to simulate these circuits faster than is possible with the fastest known event-driven algorithm. The detection and exploitation of conjugate symmetries makes use of GF(2) matrices. It is likely that conjugate symmetry and GF(2) matrices will find applications in many other areas of EDA.     

Generalized Serret-Andoyer Transformation and Applications for the Controlled Rigid Body

The Serret-Andoyer transformation is a classical method for reducing the free rigid body dynamics, expressed in Eulerian coordinates, to a 2-dimensional Hamiltonian flow. First, we show that this transformation is the computation, in 3-1-3 Eulerian coordinates, of the symplectic (Marsden-Weinstein) reduction associated with the lifted left-action of SO(3) on T*SO(3)—a generalization and extension of Noether's theorem for Hamiltonian systems with symmetry. In fact, we go on to generalize the Serret-Andoyer transformation to the case of Hamiltonian systems on T*SO(3) with left-invariant, hyperregular Hamiltonian functions. Interpretations of the Serret-Andoyer variables, both as Eulerian coordinates and as canonical coordinates of the co-adjoint orbit, are given. Next, we apply the result obtained to the controlled rigid body with momentum wheels. For the class of Hamiltonian controls that preserve the symmetry on T*SO(3), the closed-loop motion of the main body can again be reduced to canonical form. This simplifies the stability proof for relative equilibria , which then amounts to verifying the classical Lagrange-Dirichlet criterion. Additionally, issues regarding numerical integration of closed-loop dynamics are also discussed. Part of this work has been presented in LumBloch:97a. This revised version was published online in July 2006 with corrections to the Cover Date.     

Scheduling Functions for Spatiotemporal Mapping of d-Dimensional Algorithms with Homogeneous Dependences on (d-2)-Dimensional Parallel Architectures

A formalized method is proposed for construction of scheduling functions for spatiotemporal mapping of d-dimensional algorithms represented by systems of homogeneous recurrence equations on (d-2)-dimensional parallel architectures. Basic operations of the algorithms are scheduled separately by means of functions with rational coefficients.     

A Methodology for Mapping and Partitioning Arbitrary N-Dimensional Nested Loops into 2-Dimensional VLSI Arrays

A new methodology is proposed for mapping and partitioning arbitrary n-dimensional nested loop algorithms into 2-dimensional fixed size systolic arrays.Since planar VLSI arrays are easy to implement,our approach has good feasibility and applicability.In the transformation process of an algorithm,we take into account not only data dependencies imposed by the original algorithm but also space dependencies dictated by the algorithm ransformation,Thus,any VLSI algorithm generated by our methodology has optimal parallel execution time and yet remains space-time conflict free.Moreover,a theory of the least complete set of interconnection matrices is proposed to reduce the computational complexity for finding all possible space transformations for a given algorithm.     

A worst-case efficient algorithm for hidden-line elimination †

Many practical algorithms for hidden-line and surface elimination in a 2-dimensional projection of a 3-dimensional scene have been proposed. However surprisingly little theoretical analysis of the algorithms has been carried out. Indeed no non-trivial lower bounds for the problem are known. We present a plane-sweep-based hidden-line-elimination algorithm for 2-dimensional projections of scenes consiting of arbitrary polyhedra. It requires, in the worst case0(n log n) space and 0((n + k) log² n) time, where n is the number of edges in the 3-dimensional scene, and k is the number of edge intersections in the specific projection.     

Image Restoration in Optical-Acoustic Tomography

We consider the optical-acoustic tomography problem. In the general case, the problem is to reconstruct a real-valued function with a compact support in the n-dimensional Euclidean space via its spherical integrals, i.e., integrals over all (n – 1)-dimensional spheres centered at points on some (n – 1)-dimensional hypersurface. We deal with the cases n = 2 and n = 3, which are of the most practical interest from the standpoint of possible medical applications. We suggest a new effective method of reconstruction, develop restoration algorithms, and investigate the quality of the algorithms for these cases. The main result of the paper is construction of explicit approximate reconstruction formulas; from the mathematical standpoint, these formulas give the parametrix for the optical-acoustic tomography problem. The formulas constructed is a background for the restoration algorithms. We performed mathematical experiments to investigate the quality of the restoration algorithms using the generally accepted tomography quality criteria. The results obtain lead to the general conclusion: the quality of the restoration algorithms developed for optical-acoustic tomography is only slightly lower then the quality of the convolution and back projection algorithm used in Radon tomography, which is a standard de facto.     

Estimating the Focus of Expansion in Analog VLSI

In the course of designing an integrated system for locating the focus of expansion (FOE) from a sequence of images taken while a camera is translating, a variety of direct motion vision algorithms based on image brightness gradients have been studied (McQuirk, 1991, 1996b). The location of the FOE is the intersection of the translation vector of the camera with the image plane, and hence gives the direction of camera motion. This paper describes two approaches that appeared promising for analog very large scale integrated (VLSI) circuit implementation. In particular, two algorithms based on these approaches are compared with respect to bias, robustness to noise, and suitability for realization in analog VLSI. From these results, one algorithm was chosen for implementation. This paper also briefly discuss the real-time analog CMOS/CCD VLSI architecture realized in the FOE chip.