一种改进的子集可满足性算法用于FPGA布线

介绍了用布尔可满足性(SAT)和子集可满足性(sub-SAT)算法解决FPGA的详细布线问题。在布线资源固定的FPGA布线环境中,布尔公式可以证明所给电路的不可布通性,这一点要优于典型的one-net-at-a-time方法。子集可满足性方法把一个有N个约束的"严格的"SAT问题转换成一个新的"松弛的"SAT问题,仅当在原始问题中变量的不可满足个数不超过阈值k(kN)时,这一问题是可满足的。它改进了布尔可满足性,但是却产生了很多额外的变量和子句。针对这一问题,提出了用伪布尔可满足性(PBS)来消除子集可满足性公式带来的缺点。初步的实验结果表明,把这个方法加入子集可满足性方法中可以减少变量和子句数量,并显著减少运行时间。     

基于布尔可满足性的逻辑电路等价性验证方法

提出了基于布尔可满足性(Boolean Satisfiability,SAT)的逻辑电路等价性验证方法。这一验证方法把每个电路抽象成一个有穷自动机(FSM),为两个待验证的电路构造积机,把等价性验证问题转换成了积机的断言判定问题。改进了Tseitin变换方法,并将其用于把电路约束问题变换成(Conjunctive Normal Form,CNF)公式。之后则用先进的CNF SAT求解器zChaff判定积机所生成的布尔公式的可满足性。事例电路验证说明了该方法的有效性。     

一种改进的基于SAT的多错误诊断算法

改进了二种组合电路设计错误诊断DED（Design Error Diagnosis）算法。它使用多可满足性问题（SAT）求解技术，通过对布尔可满足解计数来实现对多个逻辑错误的诊断定位。改进了电路诊断架构，新架构的合取范武表述所使用的变量和子句数目大为减少；通过多种启发武方法，避免了不必要的操作，使算法在时间和内存上保持有效性。     

SAT数据结构与组合测试生成

有效的布尔可满足性算法必然包括有效的数据结构。本文深入地分析了用于回溯搜索SAT算法的数据结构，指出了它们各自所具有的优势和不足。并将SAT应用于组合电路的测试生成中。根据应用的特点和在分析的基础上，设计并实现了一个主要是针对组合测试生成的SAT算法，初步的实验结果证明了它在测试生成应用中的有效性。     

结合AIG和两变量观测策略的SAT满足性算法

现今,布尔可满足性(SAT)解算器已在工业电路验证过程中得到了广泛的应用。大多数SAT解算器是基于DPLL算法来构造的,需要电路输入形式是合取范式(CNF)的形式。CNF形式的构建会使电路表示正交化,但通常会产生更多的额外变量,同时也会破坏电路的原始结构信息,在使用DPLL算法搜索整个变量空间的时候需要大量的时间消耗。本文提出了一些方法来解决这些问题。首先使用与/非门(AIG)来简化待验证电路,然后在基于CNF的两变量观测策略上,结合合取范式CNF和析取范式DNF的图特性来改善DPLL搜索过程,加速布尔约束推导(BCP)的进行。针对ISCAS85电路的验证结果验证了本算法的有效性。     

时序电路等价验证的触发器匹配

通常的时序电路等价性验证方法是将触发器按时序展开,从而将时序电路转化为组合电路进行验证。而一般在待验证的两个时序电路中,触发器是一一对应的,找到触发器的对应关系,时序电路的验证就会得到很大的简化。该文通过一种新的基于布尔可满足性(SAT)算法的自动测试模式生成(ATPG)匹配模型建立联接电路,使用时序帧展开传递算法比较触发器的帧时序状态输出,同时在SAT解算中加入信息学习继承等启发式算法,将时序电路的触发器一一匹配。在ISCAS89电路上的实验结果表明,该文算法在对触发器的匹配问题上是非常有效的。     

基于布尔可满足性的精确逻辑综合综述

逻辑综合是电子设计自动化(EDA)的重要步骤,随着算力逐渐提升和新的计算范式不断涌现,传统基于全局启发式算法的逻辑综合面临新的挑战。启发式算法面临的主要问题是得到一个次优解,随着算力的提升,逻辑优化越来越追求精确解而不满足于次优解。该文首先简述逻辑函数表达方法和布尔可满足性(SAT)问题;其次针对精确综合的算法、编码等方面介绍了在布尔逻辑网络的面积优化和深度优化方面的精确综合研究进展;最后对精确综合的未来发展趋势进行讨论。     

结合逻辑模拟和布尔可满足性的设计错误诊断方法

在集成电路设计验证与调试过程中,逻辑错误诊断工具通常会给出一定数量的候选错误区域,然后通过特定的算法尽可能多地减少候选区域,以方便错误的准确定位。在此提出一种结合模拟与布尔可满足性（SAT）的错误诊断方法．用于提高错误诊断准确性。该方法首先使用模拟方法对候选的错误区域逐一进行判断,对于不能由模拟方法判别的候选区域,使用基于SAT的形式化方法进一步判断。针对ISCAS’85电路的实验结果表明,该方法具有较高的错误诊断准确性和效率。     

使用布尔可满足性的组合电路等价性验证算法

该文提出了一种使用布尔可满足性SAT的新颖组合电路等价性验证技术。算法是在联接电路(Miter circuit)中进行推理来简化验证问题,推理中使用了与／非图结构简化、BDD扩展、隐含学习多种方法,最后使用有效SAT解算器zChaff解决验证任务。该算法综合了BDD和SAT的优点,限制BDD构建大小避免了内存爆炸,推理简化减小了SAT搜索空间。ISCAS85电路实验结果表明了本算法的有效性。     

一种用于FPGA的新型混合布线算法

布尔可满足性是计算机科学中最基础的问题之一,已经出现了包括著名的基于查找的SAT算法在内的各种算法.对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优点,例如:同步线网嵌入及可布通性确定.然而基于SAT的布线法在可扩展性方面有很大缺陷.而另一方面,几何查找布线算法即使具有广泛的拆线重布线的能力,但当北一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难.文章提出了将一种布尔可满足性算法与VPR430相结合的新型、有效的混合布线算法.试验结果表明与相应的纯几何布线算法相比,这种算法在运行时间上有了极大的改善(减少了29%),并且对布线整体方案无不良影响.     

Design of a transmission gate based CMOL memory array

A design of a nanoelectronic memory array, compatible with both the molecular switch (nanodevice) electrical characteristics and CMOS 45 nm semiconductor technology node is presented. The proposed transmission gate based CMOL (hybrid CMOS/MOLecular) memory cell does not suffer from the operational difficulties faced by the conventional CMOL cell. The control circuitry with improved multiplexer designs is introduced, and it shows that the required voltage levels to program the nanodevices can be achieved. Moreover, the proposed memory cell has the same area as the existing CMOL inverter cell allowing easier implementation of both logic and memory circuits on the same chip.     

CMOL: Second life for silicon?

This is a brief review of the recent work on the prospective hybrid CMOS/nanowire/nanodevice (“CMOL”) circuits including digital memories, reconfigurable Boolean-logic circuits, and mixed-signal neuromorphic networks. The basic idea of CMOL circuits is to combine the advantages of CMOS technology (including its flexibility and high fabrication yield) with the extremely high potential density of molecular-scale two-terminal nanodevices. Relatively large critical dimensions of CMOS components and the “bottom-up” approach to nanodevice fabrication may keep CMOL fabrication costs at affordable level. At the same time, the density of active devices in CMOL circuits may be as high as 10¹² cm² and that they may provide an unparalleled information processing performance, up to 10²⁰ operations per cm² per second, at manageable power consumption.     

Efficient logic architectures for CMOL nanoelectronic circuits

CMOS molecular (CMOL) circuits promise great opportunities for future hybrid nanoscale IC implementation. Two new CMOL building blocks using transmission gates have been introduced to obtain efficient combinational and sequential logic for CMOL designs. Compared with the existing CMOL circuits, the proposed CMOL designs based on these blocks can achieve more than 30% improvement in speed and up to 80% improvement in density and power consumption while providing similar fault tolerance capabilities. This work significantly advances the applications of CMOL to actual electronic circuits and systems     

Three-dimensional CMOL: three-dimensional integration of CMOS/nanomaterial hybrid digital circuits

The CMOS molecular (CMOL) circuit is a promising hybrid structure incorporating the nanowire crossbar into the CMOS integrated circuit (IC) implementation. In this letter, a novel three-dimensional (3D) architecture of the CMOL circuit is introduced. This structure eliminates the special pin requirement of the original CMOL designs, providing a feasible and efficient solution to build the practical CMOL circuits. In this 3D structure, the density of the nanowire crossbar is doubled. Such a high-density implementation enables the 3D CMOL technology to leap ahead of the IC roadmap by more than three generations.     

数字集成电路物理设计阶段的低功耗技术

通过一个图像处理SoC的设计实例,着重讨论在物理设计阶段降低CMOS功耗的方法.该方法首先调整PAD摆放位置、调整宏单元摆放位置、优化电源规划,得到一个低电压压降版图,间接降低CMOS功耗;接着,通过规划开关活动率文件与设置功耗优化指令,直接降低CMOS功耗.最终实验结果表明此方法使CMOS功耗降低了10.92%.基于该设计流程的图像处理SoC已经通过ATE设备的测试,并且其功耗满足预期目标.     

一种针对AVS去块滤波的高性能结构

在AVS视频解码器设计中,环路去块滤波成为实时处理的瓶颈之一。该文提出了一种实用的环路滤波结构,处理一个宏块只需要164个周期。使用新颖的滤波顺序,待滤波数据缓冲从1616宏块大小降低为168半宏块大小。使用数据重用策略, 滤波中间数据的存储空间大大减小。实验表明,使用0.18m CMOS工艺,在50MHz下综合,该文提出的设计只需要9.2k门。工作在50MHz频率下,该文提出的设计能够支持高清视频解码的实时滤波处理。     

Designing novel reversible BCD adder and parallel adder/subtraction using new reversible logic gates

Reversible logic has received much attention in recent years when calculation with minimum energy consumption is considered. Especially, interest is sparked in reversible logic by its applications in some technologies, such as quantum computing, low-power CMOS design, optical information processing and nanotechnology. This article proposes two new reversible logic gates, ZRQ and NC. The first gate ZRQ not only implements all Boolean functions but also can be used to design optimised adder/subtraction architectures. One of the prominent functionalities of the proposed ZRQ gate is that it can work by itself as a reversible full adder/subtraction unit. The second gate NC can complete overflow detection logic of Binary Coded Decimal (BCD) adder. This article proposes two approaches to design novel reversible BCD adder using new reversible gates. A comparative result which is presented shows that the proposed designs are more optimised in terms of number of gates, garbage outputs, quantum costs and unit delays than the existing designs.     

A programmable artificial retina

An artificial retina is a device that intimately associates an imager with processing facilities on a monolithic circuit. Yet, except for simple environments and applications, analog hardware will not suffice to process and compact the raw image flow from the photosensitive array. To solve this output problem, an on-chip array of bare Boolean processors with halftoning facilities is proposed, with versatility provided by programmability. For a pixel memory size of 3 b, the authors demonstrate both the technological practicality and the computational efficiency of this programmable Boolean retina concept. Using semistatic shifting structures together with some interaction circuitry, a minimal retina Boolean processor can be built with less than 30 transistors and controlled by as few as six global clock signals. The successful design, integration, and test of a 65×76 Boolean retina on a 50-mm² CMOS 2-μm circuit are described     

Leading-zero anticipatory logic for high-speed floating pointaddition

This paper describes a new leading-zero anticipatory (LZA) logic for high-speed floating-point addition (FADD). This logic carries out the pre-decoding for normalization concurrently with addition for the significand. It also performs the shift operation of normalization in parallel with the rounding operation. The use of simple Boolean algebra allows the proposed logic to be constructed from a simple CMOS circuit. Its area penalty is as small as 30% of the conventional LZA method. The FADD core using the proposed logic was fabricated by 0.5 μm CMOS technology with triple metal interconnections and runs at 164 MHz under the condition of V_DD=3.3 V     

Cortical Models Onto CMOL and CMOS— Architectures and Performance/Price

Here we introduce a highly simplified model of the neocortex based on spiking neurons, and then investigate various mappings of this model to the CMOL CrossNet nanogrid nanoarchitecture. The performance/price is estimated for several architectural configurations both with and without nanoscale circuits. In this analysis we explore the time multiplexing of computational hardware for a pulse-based variation of the model. Our analysis demonstrates that the mixed-signal CMOL implementation has the best performance/price in both nonspiking and spiking neural models. However, these circuits also have serious power density issues when interfacing the nanowire crossbars to analog CMOS circuits. Although the results presented here are based on biologically based computation, the use of pulse-based data representation for nanoscale circuits has much potential as a general architectural technique for a range of nanocircuit implementation.