Evolutionary Algorithms and Theirs Use in the Design of Sequential Logic Circuits

In this paper an approach based on an evolutionary algorithm to design synchronous sequential logic circuits with minimum number of logic gates is suggested. The proposed method consists of four main stages. The first stage is concerned with the use of genetic algorithms (GA) for the state assignment problem to compute optimal binary codes for each symbolic state and construct the state transition table of finite state machine (FSM). The second stage defines the subcircuits required to achieve the desired functionality. The third stage evaluates the subcircuits using extrinsic Evolvable Hardware (EHW). During the fourth stage, the final circuit is assembled. The obtained results compare favourably against those produced by manual methods and other methods based on heuristic techniques.     

On mixed-level real-time hardware evolutionary systems

A new hardware model is proposed to allow synchronous sequential circuits to evolve their behavior systematically for a prespecified objective. The proposed model is highly modularized, so that a subcircuit of a selected circuit can serve as a building block for superior circuits. The model has generality in the sense that any circuit of this class can be emulated using this model. In addition, the implementation of the model has a regular structure, so that circuits can be reconfigured very quickly through a genetic operation. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

A three-step decomposition method for the evolutionary design of sequential logic circuits

Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition, output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability. It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.     

Computing Boolean functions by polynomials and threshold circuits

We investigate the computational power of threshold—AND circuits versus threshold—XOR circuits. In contrast to the observation that small weight threshold—AND circuits can be simulated by small weight threshold—XOR circuit, we present a function with small size unbounded weight threshold—AND circuits for which all threshold—XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold gates cannot simulate alternation: There are -functions which need exponential size threshold—AND circuits. Received: August 8, 1996.     

P＋P：同步时序电路的并行码和并行故障模拟器

开发的一个新的快速故障模拟器Ｐ＋Ｐ。该模拟器使用了并行码与并行故障模拟算法，实现了同步时序电路故障模拟的两路并行性，采用了全局故障分组，锥形操作，电路级化及改进的组号ＩＤ等技术。Ｐ＋Ｐ已在ＳＵＮ ＳＰＡＲＣ－２工作站上实现，运行了大部分的ＩＳＣＡＳ Ｂｅｎｃｈｍａｒｋ同步时序电路。最后给出了实验结果。     

Adaptive versus nonadaptive queries to NP and p-selective sets

We prove that P = NP follows if for some , the class of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PF^NP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.?We draw several observations and relationships between the following two properties of a complexity class : whether there exists a truthtable hard p-selective language for , and whether polynomially-many nonadaptive queries to can be answered by making O(log n)-many adaptive queries to (in symbols, whether ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then . However, if , then these two properties are equivalent. Received: November 1, 1996.     

异步时序电路的功能测试自动生成方法

异步时序电路的测试一直是一个比较困难的问题。该文通过在前人研究的基础上，提出了一种实用、高效的自动测试生成方法。该方法通过使用基于OBDD(有序二元判决图)的布尔特征函数的运算求解来确定电路的状态转换图，然后通过对转换图的强连通图的搜索运算简化状态转换图，最后使用图论的方法求出测试序列。     

Application of artificial neural network models to linear and nonlinear RF circuit modeling

Typical RF and wireless circuits comprise a large number of linear and nonlinear components. The complexity of the RF portion of a wireless system continues to increase in order to support multiple standards, multiple frequency bands, the need for higher bandwidth, and stringent adjacent channel specifications. The time required to carry out a virtual prototyping of such complex circuits and their trade‐off analysis with the baseband circuitry can be unacceptably long, because both the circuit simulation and optimization procedures can be very time consuming. Typically, one divides the task into those of designing the nonlinear elements or subcircuits that can be accurately analyzed by using RF simulators, and uses circuit level analysis for simulating the circuits at module level. In this article, we will review some approaches to modeling both the linear RF elements as well as nonlinear subcircuits (amplifiers, mixers, VCOs), and will emphasize on the application of the artificial neural networks (ANNs). Furthermore, we will demonstrate the use of the ANN to the design of RF circuits and illustrate their application to wireless types of problems of practical interest. © 2001 John Wiley & Sons, Inc. Int J RF and Microwave CAE 11: 231–247, 2001.     

Checking Combinational Equivalence of Speed-Independent Circuits

We introduce the notion of combinational equivalence to relate two speed-independent asynchronous (sequential) circuits: a golden hazard-free circuit C ₁ and a target circuit C ₂ that can be derived from C ₁ through only combinational decomposition and extraction. Both circuits are assumed to be networks of single-output basic gates; multiple output gates such as arbiters, toggles, and dual-rail function blocks are not considered. We say that the circuits are combinationally equivalent if the decomposition and extraction preserves the essential functionality of the combinational blocks in the circuit and does not introduce hazards. The paper's focus is the bottleneck of the verification procedure, checking whether C ₂ is hazard-free. We show that C ₂ is hazard-free if and only if all of its signals are monotonic and acknowledged . We then show how cubes that approximate sets of reachable circuit states can be used to give sufficient conditions for monotonicity and acknowledgement. These sufficient conditions are used to develop a verification technique for combinational equivalence that can be exponentially faster than applying traditional, more general verification techniques. This result can be useful for verifying logic synthesis and technology mapping procedures.     

异步时序电路分析一种OBDD方法

对异步时序电路的分析和使用是一个比较困难的问题,所以,异步时序电路的实际应用范围远不如同步时序电路,通过改进JRBurch等提出的分析方法,使之适用于异步时序电路,该方法使用基于OBDD的布尔特征函数来表示电路的转移关系,并通过基于OBDD的布尔函数的运算涞确定异步时序电路的稳定状态,及当输入改变时电路的下一个稳定状态,由此可实现对电路特性的精确描述。     

Real realization: Dennett’s real patterns versus Putnam’s ubiquitous automata

Both Putnam and Searle have argued that that every abstract automaton is realized by every physical system, a claim that leads to a reductio argument against Cognitivism or Strong AI: if it is possible for a computer to be conscious by virtue of realizing some abstract automaton, then by Putnam’s theorem every physical system also realizes that automaton, and so every physical system is conscious—a conclusion few supporters of Strong AI would be willing to accept. Dennett has suggested a criterion of reverse engineering for identifying “real patterns,” and I argue that this approach is also very effective at identifying “real realizations.” I focus on examples of real-world implementations of complex automata because previous attempts at answering Putnam’s challenge have been overly restrictive, ruling out some realizations that are in fact paradigmatic examples of practical automaton realization. I also argue that some previous approaches have at the same time been overly lenient in accepting counter-intuitive realizations of trivial automata. I argue that the reverse engineering approach avoids both of these flaws. Moreover, Dennett’s approach allows us to recognize that some realizations are better than others, and the line between real realizations and non-realizations is not sharp.     

形式验证中同步时序电路的VHDL描述到S2-FSM的转换

符号模型检查（ＳｙｍｂｏｌｉｃＭｏｄｅｌＣｈｅｃｋｉｎｇ,ＳＭＣ）是一种有效的形式验证方法．该方法主要有２个难点：一个是建模,即如何建立并用有限内存来表示电路的状态机模型;另一个是在此模型基础上的验证算法．由于验证时间和有限状态机模型的大小是直接相关的,因而模型的大小就成为ＳＭＣ中的关键问题．本文提出一种基于同步电路行为描述的新的有限状态机模型Ｓ２－ＦＳＭ,并给出从同步电路的ＶＨＤＬ描述建立这种模型的过程．由于该模型的状态转换函数是基于时钟周期的,消去了与时钟无关的大量中间变量,所以同Ｄｅｈａｒｂｅ提出的模型相比,它的状态数大大减少．若干电路的实验结果表明,该模型由于减少了状态规模,建模时间和可达性分析时间大大减少,效果十分显著．     

Bounded-wait combining: constructing robust and high-throughput shared objects

Shared counters are among the most basic coordination structures in distributed computing. Known implementations of shared counters are either blocking, non-linearizable, or have a sequential bottleneck. We present the first counter algorithm that is both linearizable, non-blocking, and can provably achieve high throughput in k-synchronous executions—executions in which process speeds vary by at most a constant factor k. The algorithm is based on a novel variation of the software combining paradigm that we call bounded-wait combining (BWC). It can thus be used to obtain implementations, possessing the same properties, of any object that supports combinable operations, such as a stack or a queue. Unlike previous combining algorithms where processes may have to wait for each other indefinitely, in the BWC algorithm, a process only waits for other processes for a bounded period of time and then “takes destiny in its own hands”. In order to reason rigorously about the parallelism attainable by our algorithm, we define a novel metric for measuring the throughput of shared objects, which we believe is interesting in its own right. We use this metric to prove that our algorithm achieves throughput of Ω(N/ log N) in k-synchronous executions, where N is the number of processes that can participate in the algorithm. Our algorithm uses two tools that we believe may prove useful for obtaining highly parallel non-blocking implementation of additional objects. The first are “synchronous locks”, locks that are respected by processes only in k-synchronous executions and are disregarded otherwise; the second are “pseduo-transactions”—a weakening of regular transactions that allows higher parallelism. A preliminary version of this paper appeared in [11]. D. Hendler is supported in part by a grant from the Israel Science Foundation. S. Kutten is supported in part by a grant from the Israel Science Foundation.     

VLSI asynchronous systems: specification and synthesis

Most of today's digital systems are realized using synchronous (i.e. globally clocked) VLSI circuits. For many reasons, it is becoming increasingly hard to build large synchronous circuits. Although several techniques for building non-clocked (i.e. asynchronous) sequential circuits have been known for some time, they have been largely ignored by the digital design community. Recently, however, asynchronous circuits have been enjoying a revival. After reviewing recent research in this area, we take a simple collection of examples and, through them, explain our design system for specifying and synthesizing asynchronous circuits. We show that by being able to work in a framework where circuit activities do not have to coincide with clock pulses, designers obtain several avenues for circuit optimization that are highly promising for creating efficient and modularly expandable circuits.     

On the Correlation Between Parity and Modular Polynomials

We consider the problem of bounding the correlation between parity and modular polynomials over ℤ _q , for arbitrary odd integer q≥3. We prove exponentially small upper bounds for classes of polynomials with certain linear algebraic properties. As a corollary, we obtain exponential lower bounds on the size necessary to compute parity by depth-3 circuits with a MAJORITY gate at the top, MOD _q gates at the middle level and AND gates at the input level, when the polynomials corresponding to the depth-2 MOD _q ○AND subcircuits satisfy our conditions. Our methods also yield lower bounds for depth-3 MAJ○MOD _q ○MOD ₂ circuits (under certain restrictions) for computing parity. Our technique is based on a new general representation of the correlation using exponential sums, that allows to take advantage of the linear algebraic structure of the corresponding polynomials.     

A 3-Party Simultaneous Protocol for SUM-INDEX

Abstract. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(n ^ɛ ) bits and the other sends O(n ^1-C(ɛ) ) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.     

Circuiti autonomi nonsingolari din elementi binari,realizzabili medianten elementi a soglia

The linear separability concepts are applied in order to give either necessary or sufficient conditions for realizability by exactlyn threshold elements of a given coded cycle set of an autonomous nonsingular sequential circuit, specified byn boolean functions. Two main classes are obtained, the self-dual and the pure majority classes corresponding respectively to a necessary and to a sufficient condition. Also “necklace” circuits are described which exhibit remarkable properties. The number ofrealizable, non singular autonomons circuits are enumerated up ton=5, and one investigates also the capability of circuits ofn threshold elements to perform a state cycle of length2 ⁿ. Finally, in Appendix I, a constructive method to generate a non singular transition table is given.

---

---

Questa ricerca è stata finanziata in parte dall' U.S.A.F. sotto il Grant n. 65-44 tramite l'European Office, Office of Aerospace Research-Brnxelles.     

采用独立复位信号的同步时序电路可测试性设计

针对同步时序电路提出一种结合了插入可观测点的部分复位方法，该方法是基于迭代计算的电路状态信息和冲突分析测度而提出的．根据基于电路状态信息的测度和冲突分析所选择出来的部分复位触发器，可以割断电路中的关键回路，使得电路容易被初始化．同时减少在时序ATPG中的潜在冲突．以前的部分复位方法中，部分复位的触发器不能由独立的复位信号所控制，这也是不能彻底改善可测试性的一个重要原因．当部分复位触发器可以由独立的复位信号所控制时，电路的可测试性会显著提高．该文提出了一种新的可测试性结构来设计部分复位触发器，该方法同时减小了在管脚、延时和面积的开销。