Synthesis of hazard-free control circuits from asynchronous finite state machines specifications

We discuss a special class of state machine specifications called Asynchronous Finite State Machines (AFSM) which allows the specification and synthesis of hazard-free control circuits under the unbounded delay model. AFSM are useful for the specification of sequential behavior involving choices. In contrast, models such Signal Transition Graphs (STGs) are more amenable to the specification of deterministic concurrent behavior.AFSM specifications are transformed into STGs and then to State Graphs (SGs). At the SG level of representation, hazards can be identified as a type of violations of the Complete State Coding (CSC) property. Algorithms for obtaining SGs from AFSMs, and conditions for hazard-free implementation of SG derived from AFSM are discussed. A hazard-free synthesis technique from SG is described. A CAD prototype called CLASS (Cirrus Logic Asynchronous Synthesis System) has been built and used to successfully synthesize and verify the state machine benchmark from HP Laboroatories [1] and various other real applications.     

Initialization issues in asynchronous circuit synthesis

A design specification is said to be functionally uninitializable if an initializable implementation cannot be obtained. Due to the absence of any initialization sequence, a fault simulator or test generator that assumes an unknown starting state will be completely ineffective for uninitializable circuits. We present a novel procedure for synthesizing initializable asynchronous circuits from functionally uninitializable Signal Transition Graphs (STG). After characterizing the necessary conditions for functional uninitializability, we propose a technique that transforms the original STG into an equivalent, functionally initializable STG. We show that the presence of concurrency provides the designer with an extra degree of flexibility when implementing the circuit. It is shown that initializability can be achieved by sacrificing minimal concurrency and without violating the syntactic properties of the STG required for a hazard-free implementation. The synthesis of a trigger module illustrates this procedure.A preliminary version was presented at the International Conference on Computer Design, October 1994.     

Linear programming for hazard elimination in asynchronous circuits

Hazards can be globally eliminated from an asynchronous circuit synthesized from a Signal Transition Graph by repeatedly solving an appropriate Linear Program. This article describes how to analyze the STG specification and the synthesized circuit, using bounded delay information, to formulate the problem and use a branch-and-bound procedure to solve it. Known information about the environment delays can be expressed as time bounds on the external signal transitions, and it can be exploited by the proposed methodology.     

Hazards in noncritical races

It is often desired or required to code asynchronous sequential switching circuits such that noncritical races occur. The effect of these races on hazard-free circuit operation is investigated. It is shown that the removal of single-input-change static hazards it the networks realiziag the next-state functions is not, in general, sufficient to prevent static hazards if a noncritical race is present. A necessary and sufficient condition for hazard-free realization of a flow table containing noncritical races is given, and it is shown that a hazard-free realization is always possible.     

APGAN and RPMC: Complementary Heuristics for Translating DSP Block Diagrams into Efficient Software Implementations

Dataflow has proven to be an attractive computational model for graphical DSP design environments that support the automatic conversion of hierarchical signal flow diagrams into implementations on programmable processors. The synchronous dataflow (SDF) model is particularly well-suited to dataflow-based graphical programming because its restricted semantics offer strong formal properties and significant compile-time predictability, while capturing the behavior of a large class of important signal processing applications. When synthesizing software for embedded signal processing applications, critical constraints arise due to the limited amounts of memory. In this paper, we propose a solution to the problem of jointly optimizing the code and data size when converting SDF programs into software implementations.We consider two approaches. The first is a customization to acyclic graphs of a bottom-up technique, called pairwise grouping of adjacent nodes (PGAN), that was proposed earlier for general SDF graphs. We show that our customization to acyclic graphs significantly reduces the complexity of the general PGAN algorithm, and we present a formal study of our modified PGAN technique that rigorously establishes its optimality for a certain class of applications. The second approach that we consider is a top-down technique, based on a generalized minimum-cut operation, that was introduced recently in [14]. We present the results of an extensive experimental investigation on the performance of our modified PGAN technique and the top-down approach and on the trade-offs between them. Based on these results, we conclude that these two techniques complement each other, and thus, they should both be incorporated into SDF-based software implementation environments in which the minimization of memory requirements is important. We have implemented these algorithms in the Ptolemy software environment [5] at UC Berkeley.     

Efficient Automatic Resolution of Encoding Conflicts Using STG Unfoldings

Synthesis of asynchronous circuits from signal transition graphs (STGs) involves resolution of state encoding conflicts by means of refining the STG specification. In this paper, a fully automatic technique for resolving such conflicts by means of insertion of new signals and concurrency reduction is proposed. It is based on conflict cores, i.e., sets of transitions causing encoding conflicts, which are represented at the level of finite and complete unfolding prefixes, and a SAT solver is used to find where in the STG the transitions of new signals should be inserted and to check the validity of concurrency reductions. The experimental results show significant improvements over the state space based approach in terms of runtime and memory consumption, as well as some improvements in the quality of the resulting circuits.      

Universal delay test sets for logic networks

It has been shown earlier that, if we are restricted to unate gate network (UGN) realizations, there exist universal test sets for Boolean functions. Such a test set only depends on the function f, and checks any UGN realization of f for all multiple stuck-at faults and all robustly testable stuck-open faults. In this paper, we prove that these universal test sets are much more powerful than implied by the above results. They also constitute complete delay fault test sets for arbitrary UGN implementations of a given function. This is even true for UGN networks which are not completely testable with respect to the gate or path delay fault model. Our ability to prove the temporal correctness of such circuit realizations comes from the fact that we do not argue the correctness of individual paths, but rather complete path systems     

Automatic Processor Customization for Zero-Overhead Online Software Verification

The PSL-to-Verilog (P2V) compiler can translate a set of assertions about a block-structured software program into a hardware design to be executed concurrently with the program. The assertions validate the correctness of the software program without altering the program's temporal behavior in any way, a result never previously achieved by any online model-checking system. Additionally, the techniques and implementations described apply to any general purpose program and the absence of execution overhead renders the system ideal for the verification and debugging of real-time systems. Assertions are expressed in a simple subset of the property specification language (PSL), an IEEE standard originally intended for the behavioral specification of hardware designs. The target execution system is the eMIPS processor, a dynamically self-extensible processor realized with a field-programmable gate array (FPGA). The system can concurrently execute and check multiple programs at a time. Assertions are compiled into eMIPS Extensions, which are loaded by the operating system software into a portion of the FPGA, and discarded once the program terminates. If an assertion is violated, the program receives an exception, otherwise, it executes fully unaware of its verifier. The software program is not modified in any way. It can be compiled separately with full optimizations and executes with or without the corresponding hardware checker. The P2V compiler, implemented in Python, generates code for the implementation of the eMIPS processor running on the Xilinx ML401 development board. It is currently used to verify software properties in areas such as testing, debugging, intrusion detection, and the behavioral verification of concurrent and real-time programs.      

Robust Coupling Delay Test Sets

One of the most challenging problems in high-level testing is to reduce the size of a high-level test set while ensuring an adequate fault coverage for various implementations of a function under test. A small and high-coverage test set called a robust coupling delay test set (RCDTS) is derived from the coupling delay test set proposed previously. A partial ordering relationship among delay tests in certain implementations called ??restricted?? gate networks is used to reduce the size of test sets. The RCDTS still detects all robust path delay faults. This result is extended further to the more general balanced inversion parity networks. A test generation program RTGEN for RCDTSs is then developed, and experiments with it show that significant test set reduction can be achieved.     

Lossy Communicating Finite State Machines

A network of communicating finite state machines (CFSM) consists of a set of finite state machines that communicate asynchronously with each other over (potentially) unbounded FIFO channels by sending and receiving typed messages. As a concurrency model, CFSMs has been widely used to specify and validate communications protocols. In this paper we propose to extend the classical CFSM model by introducing a new type of actions – the deletion action. The resulted model is called lossy communicating finite state machines (LCFSMs). The LCFSM model remedies two weaknesses in classical CFSM model. We show that the LCFSM model allows specification and verification of unreliable communication channels with no need of extra CFSMs. The LCFSM model enables more succinct specification and verification of communication protocols that use unreliable communication channels. LCFSM paradigm can also be used to concisely model communication errors such as dropping datagrams in UDP due to lack of local buffers.     

Reconfigurable Testbed for Interference Cancellation in DS-CDMA Systems

Interference cancellation techniques fordirect-sequence code division multiple access (DS-CDMA)systems have the potential to provide significantcapacity gains over conventional matched filterreceivers. The complexity of the signal processingalgorithms for interference cancellation often requiresprocessing speeds that are beyond that of currentdigital signal processor (DSP) technology. In thispaper, we show that this difficulty can be overcome bypartitioning the algorithmic functionality into two coretechnologies (field programmable gate arrays [FPGA] andDSP devices) based on processing speed requirements. We give implementation proofs via a testbedthat allows a dynamic reconfiguration among constituentreceivers being considered. Experimental results on theperformance of the receivers are presented.     

Statistical analysis of asynchronous pipelines in presence of process variation using formal models

Globally Asynchronous Locally Synchronous Network on Chip (GALS NoC) is one of the possible interconnect platforms in multiprocessor systems on a chip. Designing proper links and buffers in these circuits can improve their performance. An asynchronous pipeline is a key element in buffer designs. The type of pipeline and its size can influence the performance metrics such as power consumption and delay. However, asynchronous pipelines face some challenges such as performance evaluation, verification, and process variation. We consider a new formal model to overcome these challenges simultaneously. In this paper, a new statistical model for asynchronous pipelines based on Generalized Stochastic Petri Net (GSPN) has been developed. This model can be applied to different pipeline stages, in order to compare them based on the statistical analysis of performance metrics (power consumption and delay), and to analyze their performance and timing verification in presence of variation. We have explored various kinds of asynchronous pipelines, and their corresponding results show this model has reasonable accuracy in average (below 5%) and in variance, compared to the low level Monte Carlo Hspice simulation.     

Modeling and comparing CMOS implementations of the C-element

Various applications have demonstrated that asynchronous circuits have great potential for energy-efficient and high-performance design. One of the primitives used in asynchronous control circuits is the C-element. Analytical delay and energy models are presented and applied to the most popular complementary metal-oxide-semiconductor (CMOS) implementations of the C-element. Optimization of these implementations are discussed. The implementations are also compared using simulations. The simulation results are in good agreement with the analytical predictions     

Hazard-Free Self-Timed Design: Methodology and Application to Asynchronous Routing in an Heterogeneous Parallel Machine

The goal of this research is to enable the actual building of parallel machines. The example chosen in this paper is a heterogeneous parallel machine with an intrinsic asynchronous behavior. An asynchronous router fully supports such a logical asynchronism. However, every parallel processor would exhibit asynchronism similar enough to warrant the study of a general methodology. The main part of the paper deals with an original method that ensures a hazard-free self-timed design assuming the worst conditions for robustness. Hazards are classified under three types. On top of logic hazards that resort to implementation, equation hazards are eliminated by an optimal covering. A new variable labelled state-trajectory is proposed: its integrity guarantees immunity to function hazards. The method was fruitfully applied to the VLSI CMOS implementation of the above-mentioned router. Peculiar fully customized cells were designed. Circuit-measured performances as well as some machine inner-communication performances are presented.     

CMOS circuit performance enhancement by surface orientation optimization

With the advent of novel device structures that can be easily fabricated outside of the traditional (100) plane, it may be advantageous to change the crystal orientation to optimize CMOS circuit performance. The use of alternative surface orientations such as [110] and (111) enhances hole mobility while degrading electron mobility, thus allowing for adjustment of the ratio between nMOS and pMOS transistor drive currents. By optimizing the surface orientation, up to a 15% improvement in gate delay can be expected. This value depends upon the type of logic gate, the off-state leakage specification, and technology scaling trends. The introduction of high-/spl kappa/ dielectrics may provide an added incentive for the use of non-(100) orientations as this method of circuit performance enhancement may be used to compensate for mobility degradation from the high-/spl kappa/ interface. Additional concerns including layout area and device reliability are discussed.     

Cost-efficient high-radix division

Digital signal processing implementations require fast and efficient arithmetic units. This paper proposes a fast, cost-efficient enhancement to high-radix, recursive dividers. Recursive dividers are commonly implemented using a subtractor and/or a multiplier, and hardware to determine an estimate of the quotient. Traditionally, these dividers have required an off-chip ROM or a large programmable logic array (PLA) to store a truncated quotient estimate. An interesting alternative is to simplify the hardware realization with a less accurate estimate of the quotient. This paper introduces an algorithm of this type called the expanded redundancy method which is based on Renato Stefanelli's algorithm and a further enhancement by David Mandelbaum.This study compares implementations of byte-quotient estimators (radix-256) using a ROM look-up table, a direct combinational switching network, and the proposed expanded redundancy method. The estimators will be compared by area (in terms of gate count), by gate levels of delay, and by accuracy (in terms of number of iterations to converge). Three recursive algorithms are used for this comparison: 1) nonrestoring method, 2) constant convergence method, and 3) quadratic convergence method. This study will show that the proposed implementation of a byte-quotient estimator is comparable in gate delay and accuracy and can easily be integrated on-chip with other division hardware.     

Variation-aware approaches with power improvement in digital circuits

In submicron technology, during the fabrication process factors like lithography and lens defect can change some of the physical parameters of transistors and interconnects. This change can modify the transistor electrical characteristics such as current, threshold voltage and gate capacitance, and thus it causes variation in power, delay and performance of the circuit. Process variation has become one of designer׳s challenges to the point that in below 45 nm technology it is considered as the most important issue in reliability. Power consumption and transistors variation are limiting factors to physical scalability. In this paper, we propose two approaches to reduce D2D and WID variations effects on digital CMOS circuits, at design time. The first approach concerns a variation-aware algorithm capable of extracting optimal design parameters to decrease variation and power. The second approach, using transistor stacking will help further reduce variation and power. Applying the algorithm on a digital design and according to parameters behavior in the presence of variation, we extract for each parameter value that will lead to power and variation reduction. On the other hand, with the stacking approach only basic gates are considered and subsequently gate configurations that reduce power and variation are proposed. The proposed approaches could be used identically for synchronous and asynchronous circuits. To prove this claim, we apply our approaches to a network-on-chip asynchronous router and a circuit from the ISCAS85 benchmark. All simulations are done in 32 nm technology using the HSPICE tool. The proposed algorithm similar to Monte Carlo simulation achieves the same results; however with lower execution time. The application of stacking approach to both asynchronous router and ISCAS85 circuit reduces variation effects up to 40.9% and 13.35%, respectively.     

A New Approach for Modeling Inconsistencies in Digital-Assisted Analog Design

Safety critical circuits and systems require a specified function and real world structure to match each other. At the same time the functionality and the structure become more and more complex. This results in a high effort for design verification and test such that specification-oriented testing is getting more and more under pressure. In this paper we offer an approach to warrant the match between a specification and its structure by invertibly composing the corresponding “fingerprint” model. Conversely, the fingerprint warrants the match between specification and structure. We present a theoretical framework for creating the fingerprint from the specification and the structure, respectively, and demonstrate the parallel composition of fingerprints to an overall asynchronous feedback circuit system.     

Efficient Frequency Estimation Using the Pulse-Pair Method at Various Lags

The pulse-pair (PP) method is an efficient time-domain-based technique of frequency estimation, which requires a very low number of multiplications, thus ideally suited for field-programmable gate array-type hardware implementations. The optimum frequency estimation using the PP method needs a lag value equal to two-thirds of the signal length, and requires phase unwrapping that usually makes the technique computationally unattractive. In this letter, we propose efficient techniques for estimating frequency using the optimum PP method and multiple correlation lags.