Search

Flip-flops are the most used sequential elements in synchronous circuits, but designs based on latches can operate at higher frequencies and occupy less area. Techniques to increase the maximum operating frequency of flip-flop based designs, such as time-borrowing, rely on tight hold constraints that are difficult to satisfy using traditional back-end optimization techniques. We propose Mix & Latch, a methodology to increase the operating frequency of synchronous digital circuits using a single clock tree and a mixed distribution of positive- and negative-edge-triggered flops, and positive- and negative-level-sensitive latches. An efficient mathematical model is proposed to optimize the type and location of the sequential elements of the circuit. We ensure that the initial registers are not moved from their initial location, although they may change type, thus allowing the use of equivalence checking and static timing analysis to verify formally the correctness of the transformation. The technique is validated using a 28nm CMOS FDSOI technology, obtaining 1.33X post-layout average operating frequency improvement on a broad set of benchmarks over a standard commercial design flow. Additionally, the circuit area was also reduced by more than 1.19X on average for the same benchmarks, although the overall area reduction is not a goal of the optimization algorithm. To the best of our knowledge, this is the first work that proposes combining mixed-polarity flip-flops and latches to improve the circuit performance., Peer Reviewed, Postprint (published version)

© 2015 IEEE.Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., The growing variability in nanoelectronic devices, due to uncertainties from the manufacturing process and environmental conditions (power supply, temperature, aging), requires increasing design guardbands, forcing circuits to work with conservative clock frequencies. Various schemes for clock generation based on ring oscillators and adaptive clocks have been proposed with the goal to mitigate the power and performance losses attributable to variability. However, there has been no systematic analysis to quantify the benefits of such schemes and no sign-off method has been proposed for timing correctness. This paper presents and analyzes a Reactive Clocking scheme with Variability-Tracking Jitter (RClk) that uses variability as an opportunity to reduce power by continuously adjusting the clock frequency to the varying environmental conditions, and thus, reduces guardband margins significantly. Power can be reduced between 20% and 40% at iso-performance and performance can be boosted by similar amounts at iso-power. Additionally, energy savings can be translated to substantial advantages in terms of reliability and thermal management. More importantly, the technology can be adopted with minimal modifications to conventional EDA flows., Peer Reviewed, Postprint (author's final draft)

Better-Than-Worst-Case-Designs use timing speculation to run with a cycle period faster than the one required for worst-case conditions. This speculation may produce timing violations and metastability that result in failures and non-deterministic timing behavior. The effects of these phenomena are not always well understood by designers and researchers in this area. This paper analyzes the impact of timing speculation and the reasons why it is difficult to adopt this paradigm in industrial designs., Postprint (author’s final draft)

The continuous shrinking of process geometries increases variability and demands for conservative margins that have a negative impact on performance. With conventional clocks, the cycle period has to be defined to accommodate the worst-case variations during the lifetime of the circuit. Elastic Clocks arise as a new paradigm to reduce the margins without sacrificing robustness. Their cycle-by-cycle adaptation to static and dynamic variability enables the use of reduced margins that only need to cover the differential variability of the circuit delays with regard to the elastic period. Given the substantial spatio-temporal correlation within every die, a significant reduction in the margins required to cover process variability, voltage and temperature fluctuations and aging can be achieved., Peer Reviewed, Postprint (published version)

De-synchronization appears as a new paradigm to automate the design of asynchronous circuits from synchronous netlists. This paper studies different protocols for de-synchronization and formally proves their correctness. Taxonomy of existing protocols for latch controllers is provided. In particular, four-phase handshake protocols devised for micro-pipelines are studied. A new controller with maximum concurrency for de-synchronization is also proposed. The applicability of de-synchronization on an implementation of the DLX microprocessor is also described and discussed., Peer Reviewed, Postprint (published version)

This paper proposes a technique for creating a combinational logic network with an output that signals when all other outputs have stabilized. The method is based on dual-rail encoding, and guarantees low timing overhead and reasonable area and power overhead. We discuss various scenarios in which completion detection can be used to measure the delay of a synchronous circuit at fabrication time or at run time, and of an asynchronous circuit at run time. We conclude by showing, on a large set of benchmarks, the effectiveness of the proposed technique., Peer Reviewed, Postprint (published version)

This paper presents a methodology to derive asynchronous circuits from optimized synchronous circuits by replacing the clock distribution tree by a handshaking network. A case study shows the applicability of the method and the potential benefits of de-synchronizing synchronous circuits., Peer Reviewed, Postprint (published version)

We present a synthesis approach for reactive systems that aims at minimizing the overhead introduced by the operating system and the interaction among the concurrent tasks, while considering multiple concurrent execution resources. A formal model based on the notion of scheduling of Petri nets is used to perform the synthesis. We show how the notion of projections of a schedule for the complete system onto the components implemented on separate resources is essential to define the correctness of the partitioned schedule., Peer Reviewed, Postprint (published version)

Deep submicron technology calls for new design techniques, in which wire and gate delays are accounted to have equal or nearly equal effect on circuit behaviour. Asynchronous speed-independent (SI) circuits, whose behaviour is only robust to gate delay variations, may be too optimistic. On the other hand, building circuits totally delay-insensitive (DI), for both gates and wires, is impractical. The paper presents an approach for automated synthesis of globally DI and locally SI circuits. It is based on order relaxation, a simple graphical transformation of a circuit's behavioural specification, for which the Signal Transition Graph, an interpreted Petri net, is used. The method is successfully tested on a set of benchmarks and a realistic design example. It proves effective showing average cost of DI interfacing at about 40% for area and 20% for speed., Peer Reviewed, Postprint (published version)

Two trends are of major concern for digital circuit designers: the relative increase of interconnect delays with respect to gate delays and the demand for design reuse. Both pose difficult problems to synchronous design styles, and can be tackled more naturally within the asynchronous paradigm. Unfortunately even in asynchronous design the normal hypotheses about the delays of gates and wires are often overly optimistic. One of the popular assumptions is to consider gate delays to be arbitrary while neglecting the skew in wire delays (so-called speed-independence (SI) assumption). Taking wire delays into account is possible and in its extreme leads to delay-insensitive (DI) implementations which work correctly under any wire delay distribution. However, such implementations are costly. This work suggests to separate all on-chip interconnections into two classes: local (for which the delays can be under control) and global (with arbitrary delays). This leads to locally SI globally DI implementations which are more practical than fully DI circuits and are in better correspondence with technology parameters than fully SI circuits. Our approach allows logic synthesis to proceed independently for all the locally SI blocks and yields functionally correct circuits without requiring any synthesis/layout iteration or interaction. This simplifies dramatically the timing convergence problem for ASICs. We tackle the problem at the behavior level and develop a simple transformation which ensures delay-insensitive properties for particular wires. The method is illustrated by a realistic design example. The preliminary experimental results show that the area and performance penalty are within 40% and 20%, respectively., Peer Reviewed, Postprint (published version)

Noise immunity is becoming one of the most important design parameters for deep-sub-micron (DSM) technologies. Asynchronous circuits seem to be a good candidate to alleviate the problems originated by simultaneous switching noise. However, they are also more sensitive than synchronous ones to spurious signal transitions and delay variations produced by crosstalk noise. This paper addresses the problem of analyzing and synthesizing asynchronous circuits with noise immunity being the main design parameter. The techniques presented in the paper focus on crosstalk noise and tackle the problem from the behavioral point of view., Peer Reviewed, Postprint (published version)

The paper introduces Lazy Transitions Systems (LzTSs). The notion of laziness explicitly distinguishes between the enabling and the firing of an event in a transition system. LzTSs can be effectively used to model the behavior of asynchronous circuits in which relative timing assumptions can be made on the occurrence of events. These assumptions can be derived from the information known a priori about the delay of the environment and the timing characteristics of the gates that will implement the circuit. The paper presents necessary conditions to synthesize circuits with a correct behavior under the given timing assumptions. Preliminary results show that significant area and performance improvements can be obtained by exploiting the extra "don't care" space implicitly provided by the laziness of the events., Peer Reviewed, Postprint (author's final draft)

State coding conflict detection is a fundamental part of synthesis of asynchronous concurrent systems from their specifications as signal transition graphs (STGs), which are a special kind of labelled Petri nets. The paper develops a method for identifying state coding conflicts in STGs that is intended to work within a new synthesis framework based on Petri net unfolding. The latter offers potential advantages due to a partial order representation of highly concurrent behaviour as opposed to the more traditional construction of a state graph, known to suffer from combinatorial explosion. We develop a necessary condition for coding conflicts to exist, by using an approximate state covering approach. Being computationally easy, yet conservative, such a solution may produce fake conflicts. A technique for refining the latter with extra computational cost, is provided., Peer Reviewed, Postprint (published version)

This paper presents a novel method to derive a Petri net from any specification model that can be mapped into a state-based representation with arcs labeled with symbols from an alphabet of events (a Transition System, TS). The method is based on the theory of regions for Elementary Transition Systems (ETS). Previous work has shown that, for any ETS, there exists a Petri Net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original Transition System. Our method extends and implements that theory by using the following three mechanisms that provide a framework for synthesis of safe Petri nets from arbitrary TSs. First, the requirement of isomorphism is relaxed to bisimulation of TSs, thus extending the class of synthesizable TSs to a new class called Excitation-Closed Transition Systems (ECTS). Second, for the first time, we propose a method of PN synthesis for an arbitrary TS based on mapping a TS event into a set of transition labels in a PN. Third, the notion of irredundant region set is exploited, to minimize the number of places in the net without affecting its behavior. The synthesis method can derive different classes of place-irredundant Petri Nets (e.g., pure, free choice, unique choice) from the same TS, depending on the constraints imposed on the synthesis algorithm. This method has been implemented and applied in different frameworks. The results obtained from the experiments have demonstrated the wide applicability of the method., Peer Reviewed, Postprint (published version)

This paper presents a solution to the problem of sequential multi-level logic synthesis of asynchronous speed-independent circuits. The starting point is a technology-independent speed-independent circuit obtained using, e.g., the monotonous cover conditions. We describe an algorithm for the factorization of this circuit aimed at implementing it in a given standard cell library, while preserving speed-independence. The algorithm exploits known efficient factorization techniques from combinational multi-level logic synthesis, but achieves also Boolean simplification. Experimental results show a significant improvement in terms of number and complexity of solvable circuits with respect to existing methods., Peer Reviewed, Postprint (published version)

This paper introduces a novel technique for synthesis of speed-independent circuits from their Signal Transition Graph specifications. The new method uses partial order in the form of the STG-unfolding segment to derive the logic implementation using approximation techniques. It is based on a new nation of slice which localises the behaviour of a particular signal instance in a structural fragment of the segment. The experimental results show the power of the approximation approach in comparison with the existing methods., Peer Reviewed, Postprint (published version)

This paper presents theory and practical implementation of a method for multi-level logic synthesis of speed-independent circuits. An initial circuit implementation is assumed to satisfy the monotonous cover conditions but is technology independent. The proposed method performs both combinational (inserting new gates) and sequential (inserting new memory elements) decomposition of complex gates in a given standard cell library, while preserving original behaviour and speed-independence. The algorithm applies known efficient algebraic factorization techniques from combinational multi-level logic synthesis, but achieves also boolean simplification and sequential decomposition. The method allows sharing of decomposed logic., Peer Reviewed, Postprint (published version)

Presents a new technique for the decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G, which is available in the library, and two gates H/sub 1/ and H/sub 2/, which are simpler than F, while preserving the original behavior and speed-independence of the circuit. To extract functions for H/sub 1/ and H/sub 2/, the method uses Boolean relations, as opposed to the less powerful algebraic factorization approach used in previous methods. After logic decomposition, overall library matching and optimization is carried out. Logic resynthesis, performed after speed-independent signal insertion for H/sub 1/ and H/sub 2/, allows for the sharing of decomposed logic. Overall, this method is more general than existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping., Peer Reviewed, Postprint (published version)

Synthesis of asynchronous circuits from Signal Transition Graphs (STGs) and/or State Graphs (SGs) involves solving state coding problems. A well-known example of such problems is that of Complete State Coding (CSC), which happens when a pair of different states in an SG has the same binary encoding. A standard way to approach state coding conflicts is to add new state signals into the original specification in such a way that the original behaviour remains intact. Existing methods have not yet been able to provide such theoretical foundation for event insertion, that could yield efficient practical results when applied to large models. This paper aims at presenting such a general framework, which is based on two fundamental concepts. One is a region of states in an abstract labelled SG (called a Transition System). Regions correspond to places in the associated STG. The second concept is a speed-independence preserving set, which is strongly related to the implementability of the model in logic. Regions and their intersections offer “nice” structural properties that make them efficient “construction blocks” for event insertion. The application of our theory, through the software tool “petrify”, to state graphs of large size has proved to be successful., Peer Reviewed, Postprint (published version)

This paper proposes a state encoding method for asynchronous circuits based on the theory of regions. A region in a Transition System is a set of states that “behave uniformly” with respect to a given transition (value change of an observable signal), and is analogue to a place in a Petri net. Regions are tightly connected with a set of properties that must be preserved across the state encoding process, namely: (1) trace equivalence between the original and the encoded specification, and (2) implementability as a speed-independent circuit. We build on a theoretical body of work that has shown the significance of regions for such property-preserving transformations, and describe a set of algorithms aimed at efficiently solving the encoding problem. The algorithms have been implemented in a software tool called petrify. Unlike many existing tools, petrify represents the encoded specification as an STG, and thus allows the designer to be more closely involved in the synthesis process. The efficiency of the method is demonstrated on a number of “difficult” examples., Peer Reviewed, Postprint (published version)

This paper presents a method to synthesize labeled Petri nets from state-based models. Although state-based models (such as finite state machines) are a powerful formalism to describe the behavior of sequential systems, they cannot explicitly express the notions of concurrency, causality and conflict Petri nets can naturally capture these notions. The proposed method in based on deriving an elementary transition system (ETS) from a specification model. Previous work has shown that for any ETS there exists a Petri net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original ETS. This paper presents the first known approach to obtain an ETS from a non-elementary TS and derive a place-irredundant Petri net. Furthermore, by imposing constraints on the synthesis method, different classes of Petri nets can be derived from the same reachability graph (pure, free choice, unique choice). This method has been implemented and efficiently applied in different frameworks: Petri net composition, synthesis of Petri nets from asynchronous circuits, and resynthesis of Petri nets., Peer Reviewed, Postprint (published version)

The paper presents a systematic method for synthesizing asynchronous circuits from event-based specifications with conflicts on output signals. It describes a set of semantic-preserving transformations performed at the Petri net level, which introduce auxiliary signal transitions implemented by internally analogue components, Mutual Exclusion (ME) elements. The logic for primary outputs can therefore be realized free from hazards and external meta-stability. The technique draws upon the use of standard logic components and two-input MEs, available in a typical design library., Peer Reviewed, Postprint (published version)