一种VLSI设计到无向赋权图的转换系统

基于VLSI剖分问题的需要,设计并实现了VLSI设计到无向赋权图的转换系统(VLSI/Graph Converter,VGC).介绍了电路构造图和图文件存储格式,给出了VGC的处理流程图,提出了针对VLSI线网的无向赋权图转换算法.该算法解决的关键问题是,遍历树状结构的VLSI线网,将其转换为无向赋权图并存储为指定的图文件格式.VGC系统在Windows平台下用C++实现.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU转换为无向赋权图,避免了直接在VLSI线网上进行剖分,提高了VLSI剖分的效率.     

VLSI积木块布图设计的通道定序与布线

本文研究了VLSI积木块布图设计中的通道定序与布线问题。首先提出了T形约束图的概念和通道分级的思想,针对布局中出现的循环通道约束,基于三边通道的布线,通过引入一类通道——预定通道来破坏约束环。在此基础上,给出了一个在给定积木块的布局和总体布线条件下通道定序与布线的有效算法。算法已在UNIVAC1100/10上用FORTRAN77实现,结果令人满意。     

图表示下的知识约简

 知识约简主要有代数表示下的知识约简和信息表示下的知识约简.本文提出图表示下的知识约简,给出图表示下求最小约简的完备递归算法.借鉴人工智能理论中的图搜索技术,提出旋转剪枝和回溯剪枝两个搜索算子求最小约简,并证明了在这种表示下求最小约简的完备性,理论分析和实验结果表明,在图表示下求最小约简是有效可行的.     

全定制软/硬件协同设计中的硬件优化技术

提出了基于单相似系统生成的软/硬件协同设计中的硬件优化技术.介绍了一种基于子图匹配软/硬件协同设计技术的大致框架,引进通用子图群合并算法,并着重讨论了基于节点压缩优化技术的高效子图群合并算法.实验结果很好地证明了所有上述理论的正确性以及算法的有效性.     

全定制软/硬件协同设计中的硬件优化技术

提出了基于单相似系统生成的软/硬件协同设计中的硬件优化技术.介绍了一种基于子图匹配软/硬件协同设计技术的大致框架,引进通用子图群合并算法,并着重讨论了基于节点压缩优化技术的高效子图群合并算法.实验结果很好地证明了所有上述理论的正确性以及算法的有效性.     

Beta在线匹配

二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法BetaOM,并证明了该算法的正确性.本文把BetaOM分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.     

基于DNA计算的最大流算法在图聚类上的应用研究

提出使用DNA计算解决图聚类问题,提供了使用DNA两阶段法求最小切进行图分析的新思路.在使用两阶段算法前,首先根据一定的规则对给定图进行构造,使其适合使用DNA两阶段算法.在两阶段算法中,使用DNA分子对图中顶点、边进行编码.经过生化反应生成关于构造图从选定源节点到槽节点的所有路径,再利用电子计算求出关于给定源节点和槽节点的最小切,从而完成对图的划分,然后迭代执行两阶段算法直到获得满意的聚类数目为止.给出了算法的证明,说明了算法的可行性.     

防御零值功耗攻击的AES SubByte模块设计及其VLSI实现

 密码器件在执行高级加密标准(Advanced Encryption Standard,AES)时常以能量消耗方式泄漏密钥信息,为有效降低其与实际处理数据之间的相关性,该文提出一种具有防御零值功耗攻击性能的AES SubByte模块设计及其VLSI实现方案.首先,在分析GF(256)域求逆算法的基础上,采用关键模块复用的方法,提出一种更为有效的加法性屏蔽求逆算法;然后依此进一步得到一种新型的SubByte模块结构,实现在不影响对所有中间数据进行加法性屏蔽编码的同时,减少电路的芯片开销、提高电路的工作速度.实验结果表明,所设计的电路具有正确的逻辑功能.与传统SubByte模块比较,该设计的最高工作频率和面积都有较大的优化.     

一种改进的分布式最大权独立集算法

能快速准确寻找给定图中的最大权独立集的分布式算法,对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架,假设所有节点了解自己邻居节点之间的局部拓扑信息,启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明,所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求,且权和性能优于已有的分布式算法。     

一种适合于低代价、低功耗VLSI实现的块匹配运动估值算法

本文给出了一种用于块匹配运动估值的改进的多分辨率望远镜搜索(MRTlcS)算法.它以望远镜的逆向搜索取代了传统的望远镜搜索,这一改进有效地降低了VLSI实现时对片上存储器容量和带宽的要求.此外本文还采用运动跟踪和自适应搜索窗技术来减小运动估值的计算复杂性.适合于低代价、低功耗VLSI实现是新算法的显著特点.模拟结果表明新算法要求的平均运算量仅为MRTlcS算法的30%左右,而仍然可以得到相似的视频解码图质量.本文也给出了新算法和MRTlcS算法用于VLSI实现时的硬件代价和功耗比较.     

基于BSG模型的BBL布局

布局是VLSI物理设计的关键步骤之一.对于一般的BBL布局,一个基本问题是如何对布局问题的解进行有效的表示,文献[1]提出了BSG模型并对non-slicing结构的BBL布局进行了成功的表示.文章对BSG模型进行了研究和实现,并在用模拟退火算法实现过程中进行了搜索策略的改进,得到了较好的实验结果.     

A design synthesis system for recursive DSP algorithms represented by fully specified flow graphs

This paper describes a design synthesis environment which can generate an efficient VLSI layout from a recursive DSP algorithm specified by a graph. The design synthesis environment is divided into three parts: optimal schedule generation, circuit synthesis, and VLSI layout generation (silicon compilation). The scheduler first computes optimality conditions for a given input algorithm and then finds a schedule which satisfies the optimality conditions. We have employed a cyclo-static optimal multiprocessor compiler as a scheduler. The circuit synthesis component translates the optimal schedule into a structural specification, including the control structures, for an circuit realization. In the final part, a VLSI layout is generated from the structural specification. We have chosen the LAGER system for the silicon compilation. This paper illustrates the design synthesis process with complete details of a simple, complete example, a second order Direct Form II IIR filter.This work was supported in part under the Joint Services Electronics Program Contract # DAAL-03-90-C-0004.     

求图的约束最小割集的一个有效算法及其应用

本文提出确定把无向连通图G(V,E)切割为两个子图G_1(V_1,E_1)和G_2(V_2,E_2)且满足顶点集V_1和V_2的顶点数|V_1|和|V_2|为给定值的约束最小割集的一种有效算法。该算法理论比较简单,步骤简捷有效,并能保证在多项式时间内获得最优解;此外,本文举例说明该算法具体步骤过程并介绍该算法在计算机辅助电路分析和设计中的某些实际应用。     

An algorithm for counting short cycles in bipartite graphs

Let G=(U/spl cup/W, E) be a bipartite graph with disjoint vertex sets U and W, edge set E, and girth g. This correspondence presents an algorithm for counting the number of cycles of length g, g+2, and g+4 incident upon every vertex in U/spl cup/W. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as O(gn/sup 3/) where n=max(|U|,|W|).     

关于无重复分解产生树的定理

本文定义了一种二分图,称之为互补划分图。利用此图容易证明有关互补划分的定理,并可得到一个判别是否是本性互补划分的较弱的条件。     

An inequality on guessing and its application to sequentialdecoding

Let (X,Y) be a pair of discrete random variables with X taking one of M possible values, Suppose the value of X is to be determined, given the value of Y, by asking questions of the form “Is X equal to x?” until the answer is “Yes”. Let G(x|y) denote the number of guesses in any such guessing scheme when X=x, Y=y. We prove that E[G(X|Y)^ρ]⩾(1+lnM)^-ρΣ_y [Σ_xP_X,Y(x,y)^1/1+ρ] ^1+ρ for any ρ⩾0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X|Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X|Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets     

On zero-error source coding with decoder side information

Let (X,Y) be a pair of random variables distributed over a finite product set V/spl times/W according to a probability distribution P(x,y). The following source coding problem is considered: the encoder knows X, while the decoder knows Y and wants to learn X without error. The minimum zero-error asymptotic rate of transmission is shown to be the complementary graph entropy of an associated graph. Thus, previous results in the literature provide upper and lower bounds for this minimum rate (further, these bounds are tight for the important class of perfect graphs). The algorithmic aspects of instantaneous code design are considered next. It is shown that optimal code design is NP-hard. An optimal code design algorithm is derived. Polynomial-time suboptimal algorithms are also presented, and their average and worst case performance guarantees are established.     

一种用于三层布线的分层算法

随着VLSI/LSI技术的发展,多层布线已能够实现。互连网络的分层问题就是要使得互连网络所需的通孔数最少。在通孔最小化问题中,如果布图拓扑逻辑已给出,这类问题被称为受限的通孔最小化(CVM)问题。本文针对三层布线中的CVM问题提出了一种分层算法,使得布图所需的通孔数最小化。应用此算法能获得比文献中所述更少的通孔数。     

二分图的无关分解及其在覆盖问题中的应用

为了大容量存贮器制造过程中因缺陷而造成成品率低的问题，或并行阵列中的容错重组问题，一般采用冗余修复的方法，该问题可以归结为对二分图的覆盖，且该问题属于ＮＰ完全问题。     

关于产生哈密顿圈的定理及其应用

作者曾提出利用王氏代数产生图的全部哈密顿圈,本文继续研究了这种算法。为了简化计算,给出一个关于王积度数约束的定理,为了避免算法中的不必要的重复,提出一种改进的方法。 最后讨论了本算法在布线设计中的应用等。