Sequential circuits employing a combination of mixed-polarity flip-flops and latches allow significant improvements in clock frequency compared to useful skew and retiming. However, no work addresses the task of enabling a scan- based test on a circuit optimized with such techniques, while simultaneously minimizing the area overhead due to shadow latches used to complete the scan chain when latches are used in the design. This poses a serious limitation to the industrial application of mixed FF and latch-based techniques, since post-fabrication tests are an unavoidable step in IC production. This paper presents a macro-cell structure to enable both the exploitation of time borrowing for frequency optimization and the execution of the scan test of a design. The proposed solution requires minimal changes in the test setup and is evaluated using a recent methodology, Mix&Latch. Moreover, the work proposes modifications to Mix&Latch that allow reusing the standard cells introduced for the scan test to solve hold timing violations, avoiding additional hardware overhead. Results show that the lumped cell structure does not significantly impact frequency gains, and the ILP formulation of latch and FF type optimization can be extended to cover the DFT optimization part, ensuring only a moderate increase in area and power consumption, comparable with the DFT impact on regular FF-based designs.

Modularity—composing a large system using individually designed units—is an essential practice in hardware design. Yet, modularity might compromise quality: when individually designed units are put together, some of their states may become unreachable and, consequently, the logic that implements them is redundant. Sequential synthesis aims to remove redundant circuit logic by leveraging state unreachability. It critically depends on invariants—relations between signals and registers that hold in all reachable states—to prove the validity of redundancies. Yet, existing invariant generation techniques are mostly problem-specific (for a particular circuit or a property) or reliant on localized reasoning. We propose Promise, a fast circuit redundancy removal strategy. Promise exploits the rich information from simulation traces and uses efficient polynomial-time algorithms to infer global circuit invariants, optimizing the circuit and aiding other sequential synthesis procedures. Experiments show that Promise effectively optimizes circuits produced by high-level synthesis tools. Promise is open-sourced and available at github.com/ETHZ-DYNAMO/promise.

Bi-decomposition rewrites logic functions as the composition of simpler components. It is related to Boolean division, where a given function is rewritten as the product of a divisor and a quotient, but bi-decomposition can be defined for any Boolean operation of two operands. The key questions are how to find a good divisor and then how to compute the quotient. In this article, we select the divisor by approximation of the original function and then characterize by an incompletely specified function the full flexibility of the quotient for each binary operator. We target area-driven exact bi-decomposition, and we apply it to the bi-decomposition of Sum-of-Products (SOP) forms. We report experiments that exhibit significant gains in literals of SOP forms when rewritten as bi-decompositions with respect to the product operator. This suggests the application of this framework to other logic forms and binary operations, both for exact and approximate implementations.

Flip-flops (FFs) are the most commonly used sequential elements in synchronous circuits, but their timing requirements limit the operating frequency. Borrowing time with a latch-based approach can increase operating frequency, but traditional back-end optimization tools struggle to manage hold time requirements. The Mix & Latch technique achieves higher frequencies and often lower area than commercial state-of-the-art retiming by exploiting four types of synchronous sequential gates, namely, positive and negative edge-triggered flip-flops (FFs) and positive and negative transparent latches, all using a single clock tree.In this article, we first significantly accelerate the Mix & Latch flow convergence with respect to past work, by using a post-synthesis-based timing analysis that eliminates the first placement and routing needed for post-layout timing analysis. Then, by adding tolerance margins to the timing model, the pessimism is reduced to improve both convergence speed and maximum frequency. Finally, we reduce the complexity of the problem by applying the methodology only to the sequential elements belonging to critical paths. The effectiveness of Mix & Latch is then demonstrated on a RISC-V processor core from the Pulp platform using 28nm CMOS FDSOI technology. The results are compared to both the original Mix & Latch flow and a retiming performed with a state-of-the-art tool, showing a 25% frequency improvement over the original flow and 7.5% over the retiming flow. Compared to the retiming flow, we achieve comparable or lower power and area, while preserving the original registers and allowing logic equivalence checking.

This paper presents an overview of different approaches, based on theory of regions, for Transition System and Petri net decomposition into a synchronous product of restricted subclasses of Petri nets. A decomposition targeting State Machines was implemented in a prototype software, by reduction to maximal independent set which computes minimal sets of irredundant state machines. Then, states of single state machines were merged by reduction to the Boolean satisfiability problem (SAT). Furthermore, an extension to Free-choice Petri net decomposition was implemented, reducing the whole decomposition process to a series of SAT problems. We report experimental results that show a good trade-off between quality of results vs. time of computation, including different variants of the decomposition flows. In particular, we introduce a new approach allowing a simultaneous search of components, exploiting Binary Decision Diagrams and the excitation-closure property provided by theory of regions.

Recent HLS efforts explore the generation of dynamically scheduled, dataflow circuits from high-level code; their ability to adapt the schedule at runtime to particular data and control outcomes promises superior performance to standard, statically scheduled HLS solutions. However, dataflow circuits are notoriously resource-expensive: their distributed handshake mechanism brings performance benefits in some cases, but causes an unneeded resource overhead when general dynamism is not required. In this work, we present a verification framework based on model checking to systematically reduce the hardware complexity of dataflow circuits. We devise a series of formal proofs that identify the absence of particular behavioral scenarios and use this information to replace the generic dataflow logic with simpler and cheaper control structures. On a set of benchmarks obtained from high-level code, we demonstrate that our technique significantly reduces the resource requirements of dataflow circuits (i.e., it results in LUT and FF reductions of up to 51% and 53%, respectively), while still reaping all performance benefits of dynamic scheduling.

Petri nets and transition systems are two important formalisms used for modeling concurrent systems. One interesting problem in this domain is the creation of a Petri net with a reachability graph equivalent to a given transition system. This paper focuses on the creation of a set of synchronizing Free-choice Petri nets (FCPNs) from a transition system. FCPNs are more amenable for visualization and structural analysis while not being excessively simple, as in the case of state machines. The results show that with a small set of FCPNs, the complexity of the model can be reduced when compared to the synthesis of a monolithic Petri net.

Platforms with multiple field-programmable gate arrays (FPGAs), such as Amazon Web Services (AWS) F1 instances, can efficiently accelerate multikernel pipelined applications, e.g., convolutional neural networks for machine vision tasks or transformer networks for natural language processing tasks. To reduce energy consumption when the FPGAs are underutilized, we propose a model to 1) find offline the minimum-power solution for given throughput constraints and 2) dynamically reprogram the FPGA at runtime (which is complementary to dynamic voltage and frequency scaling) to match best the workloads when they change. The offline optimization model can be solved using a mixed-integer nonlinear programming (MINLP) solver, but it can be very slow. Hence, we provide two heuristic optimization methods that improve result quality within a bounded time. We use several very large designs to demonstrate that both heuristics obtain comparable results to MINLP, when it can find the best solution, and they obtain much better results than MINLP, when it cannot find the optimum within a bounded amount of time. The heuristic methods can also be thousands of times faster than the MINLP solver.

Commercial high-level synthesis tools typically produce statically scheduled circuits. Yet, effective C-to-circuit conversion of arbitrary software applications calls for dataflow circuits, as they can handle efficiently variable latencies (e.g., caches), unpredictable memory dependencies, and irregular control flow. Dataflow circuits exhibit an unconventional property: registers (usually referred to as “buffers”) can be placed anywhere in the circuit without changing its semantics, in strong contrast to what happens in traditional datapaths. Yet, although functionally irrelevant, this placement has a significant impact on the circuit’s timing and throughput. In this work, we show how to strategically place buffers into a dataflow circuit to optimize its performance. Our approach extracts a set of choice-free critical loops from arbitrary dataflow circuits and relies on the theory of marked graphs to optimize the buffer placement and sizing. Our performance optimization model supports important high-level synthesis features such as pipelined computational units, units with variable latency and throughput, and if-conversion. We demonstrate the performance benefits of our approach on a set of dataflow circuits obtained from imperative code.

Transition systems (TS) and Petri nets (PN) are important models of computation ubiquitous in formal methods for modeling systems. An important problem is how to extract from a given TS a PN whose reachability graph is equivalent (with a suitable notion of equivalence) to the original TS.This paper addresses the decomposition of transition systems into synchronizing state machines (SMs), which are a class of Petri nets where each transition has one incoming and one outgoing arc and all markings have exactly one token. This is an important case of the general problem of extracting a PN from a TS. The decomposition is based on the theory of regions, and it is shown that a property of regions called excitation-closure is a sufficient condition to guarantee the equivalence between the original TS and a decomposition into SMs.An efficient algorithm is provided which solves the problem by reducing its critical steps to the maximal independent set problem (to compute a minimal set of irredundant SMs) or to satisfiability (to merge the SMs). We report experimental results that show a good trade-off between quality of results vs. computation time.

Multi-FPGA platforms, like Amazon AWS F1, can run in the cloud multikernel pipelined applications, like convolutional neural networks (CNNs), with excellent performance and lower energy consumption than CPUs or GPUs. We propose a method to efficiently map these applications on multi-FPGA platforms to maximize the application throughput. Our methodology finds, for the given resources, the optimal number of parallel instances of each kernel in the pipeline and their allocation to one or more among the available FPGAs. We obtain this by formulating and solving a mixed-integer, nonlinear optimization problem, in which we model the performance of each component and the duration of the phases in which the accelerated computation can be split into, namely: 1) data transfer from a host CPU to the DDR memory of each FPGA; 2) data transfer from FPGA DDR to FPGA on-chip memory; 3) kernel computation on the FPGA; 4) data transfer from FPGA on-chip memory to FPGA DDR; and 5) data transfer from FPGA DDR to host. Finding the optimal solution using a mixed-integer nonlinear programming (MINLP) solver is often highly inefficient. Hence, we provide a fast heuristic method that according to our experiments can be much more efficient than the MINLP solver and finds comparable results. For larger problems (more CNN layers), our heuristic method can quickly find (several thousand times faster) much better solutions than the MINLP solver, even if we run the latter for a very long time.

When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This article proposes HiDaP, a novel multilevel algorithm that uses RTL information and analytical methods for the macro placement problem of modern designs dominated by multicycle connection pipelines. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the register latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components. An adaptive multiobjective cost function is used to simultaneously minimize wirelength, timing, overlap, and distance to preferred locations, which can be user defined or generated by analytic methods (spectral and force directed). These techniques have been applied to a set of large industrial circuits and compared against state-of-the-art commercial and academic placers, and also to handcrafted floorplans generated by expert backend engineers. The proposed approach outperforms previous algorithmic methods and can produce solutions with better wirelength and timing than the best handcrafted floorplans. Post-routing layouts are almost brought to timing closure and DRC cleanness with minimal engineer modification, showing that the generated floorplans provide an excellent starting point for the physical design flow and contribute to reduce turn-around time significantly.

Bi-decomposition is a design technique widely used to realize logic functions by the composition of simpler components. It can be seen as a form of Boolean division, where a given function is split into a divisor and quotient (and a remainder, if needed). The key questions are how to find a good divisor and then how to compute the quotient. In this paper we choose as divisor an approximation of the given function, and characterize the incompletely specified function which describes the full flexibility for the quotient. We report at the end preliminary experiments for bi-decomposition based on two AND-like operators with a divisor approximation from 1 to 0, and discuss the impact of the approximation error rate on the final area of the components in the case of synthesis by three-level XOR-AND-OR forms.

Commercial high-level synthesis tools typically produce statically scheduled circuits. Yet, effective C-to-circuit conversion of arbitrary software applications calls for dataflow circuits, as they can handle efficiently variable latencies (e.g., caches) and unpredictable memory dependencies. Dataflow circuits exhibit an unconventional property: registers (usually referred to as "buffers") can be placed anywhere in the circuit without changing its semantics, in strong contrast to what happens in traditional datapaths. Yet, although functionally irrelevant, this placement has a significant impact on the circuit's timing and throughput. In this work, we show how to strategically place buffers into a dataflow circuit to optimize its performance. Our approach extracts a set of choice-free critical loops from arbitrary dataflow circuits and relies on the theory of marked graphs to optimize the buffer placement and sizing. We demonstrate the performance benefits of our approach on a set of dataflow circuits obtained from imperative code.

This paper presents a new transistor placement method applied to the ASTRAN EDA tool, an open-source solution for the automatic design of complex digital gates. Although it currently reaches an optimized solution through a Threshold Accepting approach, ASTRAN does not guarantee a minimum-width placement. In this paper, a method based on Boolean satisfiability is proposed, ensuring an optimal solution for the transistor placement task through modeling the problem into a set of Boolean variables and clauses aware of four design rule constraints. Experiments comparing the proposed method and the current ASTRAN placement technique have shown reductions in the layout area. Furthermore, our method achieved a significant improvement regarding runtime, an essential feature for designing digital circuits and systems on-demand.

Decomposition is a technology-independent process, in which a large complex function is broken into smaller, less complex functions. The costs of two-level or factored-form representations (cubes and literals) are used in most decomposition methods, as they have a high correlation with the area of cell-based designs. However, this correlation is weaker for field-programmable gate arrays (FPGAs) based on look-up tables. Furthermore, local optimizations have limited power due to the structural bias of the circuit descriptions. This paper tries to reduce the structural biasing by remapping the look-up table network and decomposing the derived functions using the support as cost function. The proposed method improves the FPGA mapping results of a commercial tool for the 20 largest MCNC benchmarks, with gains of 28% in delay plus 18% in area when targeting delay, and a reduction of 28% in area plus 14% in delay with area as cost function. Results with 23% less area and 6% less delay are obtained after physical synthesis (post place-and-route). Moreover, 12 of the best known results for delay (and 3 for area) of the EPFL benchmarks are improved.

FPGA-based accelerators demonstrated high energy efficiency compared to GPUs and CPUs. However, single FPGA designs may not achieve sufficient task parallelism. In this work, we optimize the mapping of high-performance multi-kernel applications, like Convolutional Neural Networks, to multi-FPGA platforms. First, we formulate the system level optimization problem, choosing within a huge design space the parallelism and number of compute units for each kernel in the pipeline. Then we solve it using a combination of Geometric Programming, producing the optimum performance solution given resource and DRAM bandwidth constraints, and a heuristic allocator of the compute units on the FPGA cluster.

When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This paper proposes a novel multi-level approach for the macro placement problem of complex designs dominated by macro blocks, typically memories. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components, aimed at wirelength minimization. These techniques have been applied to a set of large industrial circuits and compared against both a commercial floorplanner and handcrafted floorplans by expert back-end engineers. The proposed approach outperforms the commercial tool and produces solutions with similar quality to the best handcrafted floorplans. Therefore, the generated floorplans provide an excellent starting point for the physical design iterations and contribute to reduce turn-around time significantly.

Restructuring techniques for And-Inverter Graphs (AIG), such as rewriting and refactoring, are powerful, scalable and fast, achieving highly optimized AIGs after few iterations. However, these techniques are biased by the original AIG structure and limited by single output optimizations. This paper investigates AIG optimization for area, exploring how far Boolean methods can reduce AIG nodes through local optimization.Boolean division is applied for multi-output functions using two-literal divisors and Boolean decomposition is introduced as a method for AIG optimization. Multi-output blocks are extracted from the AIG and optimized, achieving a further AIG node reduction of 7.76% on average for ITC99 and MCNC benchmarks.

The progressive miniaturization of technology and the unequal scalability of the BEOL and FEOL layers aggravate the routing congestion problem and have a negative impact on manufacturability. Standard cells are designed in a way that they can be treated as black boxes during physical design. However, this abstraction often prevents an efficient use of its internal free resources.

A new methodology for system-on-chip-level logic-IP-internal electromigration verification is presented in this paper, which significantly improves accuracy by comprehending the impact of the parasitic RC loading and voltage-dependent pin capacitance in the library model. It additionally provides an on-the-fly retargeting capability for reliability constraints by allowing arbitrary specifications of lifetimes, temperatures, voltages, and failure rates, as well as interoperability of the IPs across foundries. The characterization part of the methodology is expedited through the intelligent IP-response modeling. The ultimate benefit of the proposed approach is demonstrated on a 28-nm design by providing an on-the-fly specification of retargeted reliability constraints. The results show a high correlation with SPICE and were obtained with an order of magnitude reduction in the verification runtime.

A new methodology for SoC-level logic-IP-internal EM verification is presented, which provides an on-the-fly retargeting capability for reliability constraints. This flexibility is available at the design verification stage, in the form of allowing arbitrary specifications (of lifetimes, temperatures, voltages and failure rates), as well as interoperability of IPs across foundries. The methodology is characterization- and reuse-based, and naturally incorporates complex effects such as clock gating and variable switching rates at different pins. The benefit from such a framework is demonstrated on a 28nm design, with close SPICE-correlation and verification in a retargeted reliability condition.

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.

Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs.

Elastic systems operate in a dataflow-like mode using a distributed scalable control and tolerating variable-latency computations. At the same time, multithreading increases the utilization of processing units and hides the latency of each operation by time-multiplexing operations of different threads in the datapath. This paper proposes a model to unify multithreading and elasticity. A new multithreaded elastic control protocol is introduced supported by low-cost elastic buffers that minimize the storage requirements without sacrificing performance. To enable the synthesis of multithreaded elastic architectures, new hardware primitives are proposed and utilized in two circuit examples to prove the applicability of the proposed approach.

The complexity of the VLSI physical design flow grows dramatically as the level of integration increases. An effective way to manage this increasing complexity is through the use of regular designs which contain more reusable parts. In this work we introduce HiReg, a new floorplanning algorithm that generates regular floorplans. HiReg automatically extracts repeating patterns in a design by using graph mining techniques. Regularity is exploited by reusing the same floorplan for multiple instances of a pattern, as long as neither area, wire length or existing hierarchy constraints are violated or compromised. The proposed scheme is targeted towards early system-level design of chip multiprocessors (CMPs). Experiments show the scalability of the method for many-core CMPs and competitive results in area and wire length.

An approach for cell routing using gridded design rules is proposed. It is technology-independent and parameterizable for different fabrics and design rules, including support for multiple-patterning lithography. The core contribution is a detailed-routing algorithm based on a Boolean formulation of the problem. The algorithm uses a novel encoding scheme, graph theory to support floating terminals, efficient heuristics to reduce the computational cost, and minimization of the number of unconnected pins in case the cell is unroutable. The versatility of the algorithm is demonstrated by routing single- and double-height cells. The efficiency is ascertained by synthesizing a library with 127 cells in about one hour and a half of CPU time. The layouts derived by the implemented tool have also been compared with the ones from a commercial library; thus, showing the competitiveness of the approach for gridded geometries.

The discovery of process models from event logs has emerged as one of the crucial problems for enabling the continuous support in the life-cycle of an information system. However, in a decade of process discovery research, the algorithms and tools that have appeared are known to have strong limitations in several dimensions. The size of the logs and the formal properties of the model discovered are the two main challenges nowadays. In this paper we propose the use of numerical abstract domains for tackling these two problems, for the particular case of the discovery of Petri nets. First, numerical abstract domains enable the discovery of general process models, requiring no knowledge (e.g., the bound of the Petri net to derive) for the discovery algorithm. Second, by using divide and conquer techniques we are able to control the size of the process discovery problems. The methods proposed in this paper have been implemented in a prototype tool and experiments are reported illustrating the significance of this fresh view of the process discovery problem.

Tiled hierarchical architectures for Chip Multiprocessors (CMPs) represent a rapid way of building scalable and power-efficient many-core computing systems. At the early stages of the design of a CMP, physical parameters are often ignored and postponed for later design stages. In this work, the importance of physical-aware system-level exploration is investigated, and a strategy for deriving chip floorplans is described. Additionally, wire planning of the on-chip interconnect is performed, as its topology and organization affect the physical layout of the system. Traditional algorithms for floorplanning and wire planning are customized to include physical constraints specific for tiled hierarchical architectures. Over-the-cell routing is used as one of the major area savings strategy. The combination of architectural exploration and physical planning is studied with an example and the impact of the physical aspects on the selection of architectural parameters is evaluated.

This paper presents an integrated flow for architectural exploration and physical planning of large-scale hierarchical tiled CMPs. Classical floorplanning and wire planning techniques have been adapted to incorporate layout constraints that enforce regularity in the interconnect networks. Routing is performed on top of memories and components that underutilize the available metal layers for interconnectivity. The experiments demonstrate the impact of physical parameters in the selection of the most efficient architectures. Thus, the integrated flow contributes to deliver physically-viable architectures and simplify the complex design closure of large-scale CMPs.

Random fluctuations will be a major factor interfering with the operation of nanometer scale electronic devices. This article presents circuit architectures that can exploit such fluctuations, if signals have a particle-like (discrete, token-based) character. We define an abstract circuit primitive that, though lacking functionality when used with fluctuation-free signals, becomes universal when fluctuations are allowed. Key to the power of a signal’s fluctuations is the ability to explore the state space of a circuit. This ability is used to resolve deadlock situations, which could otherwise only be averted by increased design complexity. The results in this article suggest that in the design of future computers, signal fluctuations, rather than being an impediment to be avoided at any cost, may be an important ingredient to achieve efficient operation.

The 1-D design style with gridded design rules is gaining ground for addressing the printability issues in subwavelength photolithography. One of the synthesis problems in cell generation is transistor folding, which consists of breaking large transistors into smaller ones (legs) that can be placed in the active area of the cell. In the 1-D style, diffusion sharing between differently sized transistors is not allowed, thus implying a significant area overhead when active areas with different sizes are required. This paper presents a new formulation of the transistor folding problem in the context of 1-D design style and a mathematical model that delivers area-optimal solutions. The mathematical model can be customized for different variants of the problem, considering flexible transistor sizes and multiple-height cells. An innovative feature of the method is that area optimality can be guaranteed without calculating the actual location of the transistors. The model can also be enhanced to deliver solutions with good routability properties.

The continuous scaling of nanoelectronics is increasing the complexity of chip multiprocessors (CMPs) and exacerbating the memory wall problem. As CMPs become more complex, the memory subsystem is organized into more hierarchical structures to better exploit locality. To efficiently discover promising architectures within the rapidly growing search space, exhaustive exploration is replaced with tools that implement intelligent search strategies. Moreover, faster analytical models are preferred to costly simulations for estimating the performance and power of CMP architectures. The memory traffic generated by CMP cores has a cyclic dependency with the latency of the memory subsystem, which critically affects the overall system performance. Based on this observation, a novel scalable analytical method is proposed to estimate the performance of highly parallel CMPs (hundreds or thousands of cores) with hierarchical interconnect networks. The method can use customizable probabilistic models and solves the cyclic dependencies between traffic and latency by using a fixed-point strategy. By using the analytical model as a performance and power estimator, an efficient metaheuristic-based search is proposed for the exploration of large design spaces. The proposed techniques are shown to be very accurate and a promising strategy when compared to the results obtained by simulation.

The continuous scaling of nanoelectronics is increasing the complexity of chip multiprocessors (CMPs) and exacerbating the memory wall problem. As CMPs become more complex, the memory subsystem is organized into more hierarchical structures to better exploit locality. During the exploration and design of CMP architectures, it is essential to efficiently analyze their performance. However, performance is highly determined by the latency of the memory subsystem, which in turn has a cyclic dependency with the memory traffic generated by the cores. This paper proposes a scalable analytical method to estimate the performance of highly parallel CMPs (hundreds of cores) with hierarchical interconnect fabrics. The method can use customizable probabilistic models and solves the cyclic dependencies by using a fixed-point strategy. The technique is shown to be a very accurate and efficient strategy when compared to the results obtained by simulation.

This paper investigates the use of formal verification techniques to create online judges that can assist in teaching logic circuit design. Formal verification not only contributes to give an exact assessment about correctness, but also saves the instructor the tedious task of designing test cases. The paper explains how formal verification has been integrated in an online judge. It also describes the courseware created for a course on logic circuits and the successful experience of using it in a one-week summer course with students from secondary and high school.

With the scaling of process technologies, communication delays represent a bottleneck for the performance of circuits. One of the main issues that has to be handled is the variability of such delays. Latency-insensitive circuits offer a form of elast

Elasticity is a paradigm that tolerates the variations in computation and communication delays. By applying elastic transformations that allow varying the original timing, circuits can be optimized beyond the conventional rigid transformations that do not modify the external timing. Pipelining is one of the classical techniques to improve the throughput of a circuit. This article reveals how elasticity can be effectively and practically used to derive pipelined circuits by using correct-by-construction transformations that can be fully automated. Two designs, one of them industrial, are used to demonstrate how the area-performance trade-off can be explored using elasticity.

This paper presents a method for automatic microarchitectural pipelining of systems with loops. The original specification is pipelined by performing provably-correct transformations including conversion to a synchronous elastic form, early evaluation, inserting empty buffers, anti-tokens, and retiming. The design exploration is done by solving an optimization problem followed by simulation of solutions. The method is explained on a DLX microprocessor example. The impact of different microarchitectural parameters on the performance is analyzed.

Elastic systems, either synchronous or asynchronous, can be optimized for the average-case performance when they have units with early evaluation or variable latency. The performance evaluation of such systems using analytical methods is a complex problem and may become a bottleneck when an extensive exploration of different architectural configurations must be done. This paper proposes an analytical method for performance evaluation using symbolic expressions. Two version of the method are presented: an exact method that has high run time complexity and an efficient approximate method that computes the lower bound of the system throughput.

Elastic systems provide tolerance to the variations in computation and communication delays. The incorporation of elasticity opens new opportunities for optimization using new correct-by-construction transformations that cannot be applied to rigid non-elastic systems. The basics of synchronous and asynchronous elastic systems will be reviewed. A set of behavior-preserving transformations will be presented: retiming, recycling, early evaluation, variable-latency units and speculative execution. The application of these transformations for performance and power optimization will be discussed. Finally, a novel framework for microarchitectural exploration will be introduced, showing that the optimal pipelining of a circuit can be automatically obtained by using the previous transformations.

The architecture definition, design, and validation of the interconnect networks is a key step in the design of modern on-chip systems. This paper proposes a mathematical formulation of the problem of simultaneously defining the topology of the network and the message routes for the traffic among the processing elements of the system. The solution of the problem meets the physical and performance constraints defined by the designer. The method guarantees that the generated solution is deadlock free. It is also capable of automatically discovering topologies that have been previously used in industrial systems. The applicability of the method has been validated by solving realistic size interconnect networks modeling the typical multiprocessor systems.

The theory of regions was introduced in the early nineties as a method to bridge state and event-based models. This paper tackles the problem of deriving a Petri net from a state-based model, using the theory of regions. Some of the restrictions required in the traditional approach are dropped in this paper, together with significant extensions that make the approach applicable in new scenarios. One of these scenarios is Process Mining, where accepting (discovering) additional behavior in the synthesized Petri net is sometimes valued. The algorithmic emphasis used in this paper contributes to the demystification of the theory of regions as been only a good theoretical exercise, opening the door for its application in the industrial domain.

Retiming and recycling are two transformations used to optimize the performance of latency-insensitive (a.k.a. synchronous elastic) systems. This paper presents an approach that combines these two transformations for performance optimization of elastic systems with early evaluation. The method is based on Mixed Integer Linear Programming.

Speculation is a well-known technique for increasing parallelism of the microprocessor pipelines and hence their performance. While implementing speculation in modern design practice is error-prone and mostly ad-hoc, this paper proposes a correct-by-construction method for implementing speculation in Elastic Systems. The technique is based on applying provably correct transformations. The benefits of speculation are illustrated with two examples in which these transformations are systematically applied. The method proposed in this paper is amenable for automation in a synthesis flow.

Power and performance benefits of scaling are lost to worst case margins as uncertainty of device characteristics is increasing. Adaptive techniques can dynamically adjust the margins required to tolerate variability and recover a significant part of the benefits lost due to worst-case conditions. Additionally, the stringent timing requirements for the synthesis of low-skew clock trees involve higher power consumption, and limit the adaptability to varying operating conditions. This paper introduces an elastic clocking scheme as an adaptive technique to confront variability and provide substantial power savings by dynamically adjusting to operating conditions. The synthesis and sign-off analysis of the elastic clocks is fully automated. Changes to the design flow and sign-off analysis of elastic clocks are addressed by automation of design flow support.

Variable-latency designs may improve the performance of those circuits in which the worst-case delay paths are infrequently activated. Telescopic units emerged as a scheme to automatically synthesize variable-latency circuits. In this paper, a novel approach is proposed that brings three main contributions with regard to the methods used for telescopic units: first, no multi-cycle timing analysis is required to ensure the correctness of the circuit; second, the method can be applied to large circuits; third, the circuit can be optimized for the most frequent input patterns. The approach is based on finding approximations of critical nodes in the netlist that substitute the exact behavior. Two cycles are required when the approximations are not correct. These approximations can be obtained by the simulation of traces applied to the circuit. Experimental results on selected examples show a tangible speed-up (15%) with a small area overhead (3%).

Logic decomposition has been extensively used to optimize the worst-case delay and the area in the technology independent phase. Bi-decomposition is one of the state-of-art techniques to reduce the depth of the netlist due to the affordable computational cost. We present a novel n-way decomposition technique that improves bi-decomposition. The problem of decomposition is formulated as a Boolean relation which captures a larger set of possible solutions compared to bi-decomposition. The solution obtained from the Boolean relation improves the delay with near-zero cost in area. As it is shown on the experimental results, a considerable improvement is achieved on large netlists and even larger depending on which technology mapper is used.

Clock skew scheduling has been effectively used to reduce the clock period of sequential circuits. However, this technique may become impractical if a different skew must be applied for each memory element. This paper presents a new technique for clock skew scheduling constrained by the number of skew domains. The technique is based on a multi-level clustering approach that progressively groups flip-flops with skew affinity. This new technique has been compared with previous work, showing the efficiency in the obtained performance and computational cost. As an example, the skews for an OpenSparc with almost 16K flip-flops and 500K paths have been calculated in less than 5 minutes when using only 2 to 5 skew domains.

Performance models for Network-on-Chip (NoC) are essential for design, optimization and Quality of Service (QoS) assurance. Classical queueing theory has been often used to provide fast analytical models to estimate average performance. This paper presents a new analytical model that focuses on QoS assurance. It assumes that the NoC has an underlying synchronous behavior with constant service time routers. The comparisons with simulation results show a tangible improvement with regard to the classical M/D/1 models when estimating the worst-case latencies and queue delays. The model can be applied to any network modeled as a queueing system with constant-time routers.

A Boolean relation can specify some types of flexibility of a combinational circuit that cannot be expressed with don't cares. Several problems in logic synthesis, such as Boolean decomposition or multilevel minimization, can be modeled with Boolean relations. However, solving Boolean relations is a computationally expensive task. This paper presents a novel recursive algorithm for solving Boolean relations. The algorithm has several features: efficiency, wide exploration of solutions, and customizable cost function. The experimental results show the applicability of the method in logic minimization problems and tangible improvements with regard to previous heuristic approaches.

Elasticity in circuits and systems provides tolerance to variations in computation and communication delays. This paper presents a comprehensive overview of elastic circuits for those designers who are mainly familiar with synchronous design. Elasticity can be implemented both synchronously and asynchronously, although it was traditionally more often associated with asynchronous circuits. This paper shows that synchronous and asynchronous elastic circuits can be designed, analyzed, and optimized using similar techniques. Thus, choices between synchronous and asynchronous implementations are localized and deferred until late in the design process.

This issue presents five regular papers and two short papers exposing recent advances in the design of asynchronous systems. Most of the contributions were originally presented at the 14th IEEE International Symposium on Asynchronous Circuits and Systems, held in Newcastle upon Tyne, U.K., in April 2008.

Buffer resizing and buffer insertion are two transformation techniques for the performance optimization of elastic systems. Different approaches for each technique have already been proposed in the literature. Both techniques increase the storage capacity and can potentially contribute to improve the throughput of the system. Each technique offers a different trade-off between area cost and latency. This paper presents a method that combines both techniques to achieve the maximum possible throughput while minimizing the cost of the implementation. The provided method is based on mixed integer linear programming. A set of experiments is designed to show the feasibility of the approach.

This paper presents a method for correct-by-construction microarchitectural pipelining that handles cyclic systems with dependencies between iterations. Our method combines previously known bypass and retiming transformations with a few transformations valid only for elastic systems with early evaluation (namely, empty FIFO insertion, FIFO capacity sizing, insertion of anti-tokens, and introducing early evaluation multiplexors). By converting the design to a synchronous elastic form and then applying this extended set of transformations, one can pipeline a functional specification with an automatically generated distributed controller that implements stalling logic resolving data hazards off the critical path of the design. We have developed an interactive toolkit for exploring elastic microarchitectural transformations. The method is illustrated by pipelining a few simple examples of instruction set architecture ISA specifications.

Nanometer-scale structures suitable for computing have been investigated by several research groups in recent years. A common feature of these structures is their dynamic evolution through cascaded local interactions embedded on a discrete grid. Finding configurations capable of conducting computations is a task that often requires tedious experiments in laboratories. Formal methods—though used extensively for the specification and verification of software and hardware computing systems—are virtually unexplored with respect to computational structures at atomic scales. This paper presents a systematic approach toward the application of formal methods in this context, using techniques like abstraction, model-checking, and symbolic representations of states to explore and discover computational structures. The proposed techniques are applied to a system of CO molecules on a grid of Copper atoms, resulting in the design of a complete library of combinational logic gates based on this molecular system. The techniques are also applied on (more general) systems of cellular automata that employ an asynchronous mode of timing. The use of formal methods may narrow the gap between Physical Chemistry and Computer Science, allowing the description of interactions of nanometer scale systems on a level of abstraction suitable to devise computing devices.

State encoding is one of the most difficult problems in the synthesis of asynchronous controllers. This paper presents a method that can solve the problem of large controllers specified with signal transition graphs. The method is based on the structural theory of Petri nets and uses integer-linear programming to insert state signals in locations that guarantee the consistency and absence of critical races. The structural nature of the proposed method makes it conservative, i.e., a solution cannot be guaranteed, even if it exists. Nevertheless, the experiments show that this limitation did not preclude finding a solution for all the examples presented in this paper. The method can be customized for area or delay optimization. The experimental results confirm the quality of the circuits, as compared with state-based methods. They also show the significant benefits that could be obtained if logic synthesis would be incorporated in synthesis frameworks that generate controllers by syntax-directed translation.

A protocol for latency-insensitive design with early evaluation is presented. The protocol is based on a symmetric view of the system in which tokens carrying information move in the forward direction and anti-tokens canceling information move in the backward direction. An implementation of the protocol and an example illustrate the flow for converting a regular synchronous design into an elastic circuit with early evaluation.

Retiming, c-slow retiming and recycling are different transformations for the performance optimization of sequential circuits. For retiming and c-slow retiming, different models that provide exact solutions have already been proposed. An exact model for recycling was yet unknown. This paper presents a general formulation that covers the combination of the three schemes for performance optimization. It provides an exact model based on integer linear programming that resorts to the structural theory of marked graphs. A set of experiments has been designed to show the benefits in performance obtained by combining retiming and recycling. The results also show the applicability of the method in large circuits.

A novel method to solve the state encoding problem in Signal Transition Graphs is presented. It is based on the structural theory of Petri nets and can be applied to large specifications with hundreds of signals. This new method opens the door to incorporate logic synthesis in the design flow of large control circuits obtained from high-level specifications. The experimental results validate the quality of the encoded circuits and show the significant improvements that can be obtained by the synthesis of large controllers.

A simple protocol for latency-insensitive design is presented. The main features of the protocol are the efficient implementation of elastic communication channels and the automatable design methodology. With this approach, fine-granularity elasticity can be introduced at the level of functional units (e.g. ALUs, memories). A formal specification of the protocol is defined and an efficient scheme for the implementation of elasticity that involves no datapath overhead is presented. The opportunities this protocol opens for microarchitectural design are discussed.

We formally define - at the stream transformer level - a class of synchronous circuits that tolerate any variability in the latency of their environment. We study behavioral properties of networks of such circuits and prove fundamental compositionality results. The paper contributes to bridging the gap between the theory of latency-insensitive systems and the correct implementation of efficient control structures for them

Most of the logic synthesis algorithms are not scalable for large networks and, for this reason, partitioning is often applied. However traditional mincut-based partitioning techniques are not always suitable for delay and area logic optimizations. The paper presents an approach that uses a dominator-based partitioning and conventional logic synthesis techniques for delay optimization of large networks. The calculation of dominators is crucial to find topologically ordered clusters suitable for logic restructuring. As a result, a scalable and efficient strategy for delay optimization is proposed and evaluated, showing tangible improvements with respect to existing techniques. A comparison with a standard mincut-based partitioning technique is also presented.

The continuous minituarization of integrated circuits may reach atomic scales in a couple of decades. Some researchers have already built simple computation engines by manipulating individual atoms on metal surfaces. This paper presents a systematic approach to automate the design of logic gates using molecule cascades. Temporal logic is used to characterize molecular interactions and specify the behavior of logic gates. Model-checking techniques are used for the exploration of structures behaviorally equivalent to the logic gates. As an example, a complete library of combinational logic gates has been designed using a particular molecular system. This new approach provides a methodology to bridge the gap between physical chemists and computer scientists in seeking computational structures at atomic scales.

Early evaluation allows to execute operations when enough information at the inputs has been received to determine the value at the outputs. Systems that can tolerate variable-latency units, such as latency-insensitive or asynchronous systems, can enhance their performance by using early evaluation. The most relevant example of a unit with early evaluation is the multiplexor: the output can be determined as soon as the information of the selected channel arrives, without waiting for the other channels.

A novel strategy for the logic synthesis of asynchronous control circuits is presented. It is based on the structural theory of Petri nets and integer linear programming. Techniques that are capable of checking implementability conditions, such as complete state coding, and deriving a gate netlist to implement the specified behavior are presented. These techniques can handle Petri net specifications consisting of several thousands of transitions and provide a significant speed-up compared with techniques that have previously been proposed

Asynchronous implementation techniques, which measure logic delays at runtime and activate registers accordingly, are inherently more robust than their synchronous counterparts, which estimate worst case delays at design time and constrain the clock cycle accordingly. Desynchronization is a new paradigm to automate the design of asynchronous circuits from synchronous specifications, thus, permitting widespread adoption of asynchronicity without requiring special design skills or tools. In this paper, different protocols for desynchronization are first studied, and their correctness is formally proven using techniques originally developed for distributed deployment of synchronous language specifications. A taxonomy of existing protocols for asynchronous latch controllers, covering, in particular, the four-phase handshake protocols devised in the literature for micropipelines, is also provided. A new controller that exhibits provably maximal concurrency is then proposed, and the performance of desynchronized circuits is analyzed with respect to the original synchronous optimized implementation. Finally, this paper proves the feasibility and effectiveness of the proposed approach by showing its application to a set of real designs, including a complete implementation of the DLX microprocessor architecture

A reactive system must process inputs from the environment at the speed and with the delay dictated by the environment. The synthesis of reactive software from a modular concurrent specification model generates a set of concurrent tasks coordinated by an operating system. This paper presents a synthesis approach for reactive software that is aimed at minimizing the overhead introduced by the operating system and the interaction among the concurrent tasks. A formal model based on Petri nets is used to synthesize the tasks and verify the correctness of their composition. A practical application of the approach is illustrated by means of a real-life industrial example, which shows the significant impact of the approach on the performance of the system.

A recursive algorithm for solving Boolean relations is presented. It provides several features: wide exploration of solutions, parametrizable cost function and efficiency. The experimental results show the applicability of the method and tangible improvements with regard to previous heuristic approaches.

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.

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.

An approach for logic decomposition that produces circuits with reduced logic depth is presented. It combines two strategies: logic bi-decomposition of Boolean functions and tree-height reduction of Boolean expressions. It is a technology-independent approach that enables one to find tree-like expressions with smaller depths than the ones obtained by state-of-the-art techniques. The approach can also be combined with technology mapping techniques aiming at timing optimization. Experimental results show that new points in the area/delay space can be explored, with tangible delay improvements when compared to existing techniques.

The verification of a n-stage pulse-driven IPCMOS pipeline, for any n>0, is presented. The complexity of the system is 32n transistors and delay information is provided at the level of transistor The correctness of the circuit highly depends on the timed behavior of its components and the environment. To verify the system, three techniques have been combined: (1) relative-timing-based verification from absolute timing information, (2) assume-guarantee reasoning to verify untimed abstractions of timed components and (3) mathematical induction to verify pipelines of any length. Even though the circuit can interact with pulse-driven environments, the internal behavior between stages commits a handshake protocol that enables the use of untimed abstractions. The verification not only reports a positive answer about the correctness of the system, but also gives a set of sufficient relative-timing constraints that determine delay slacks under which correctness can be maintained.

This paper presents a design flow for timed asynchronous circuits. It introduces lazy transitions systems as a new computational model to represent the timing information required for synthesis. The notion of laziness explicitly distinguishes between the enabling and the firing of an event in a transition system. Lazy transition systems 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 the necessary conditions to generate circuits and a synthesis algorithm that exploits the timing assumptions for optimization. It also proposes a method for back-annotation that derives a set of sufficient timing constraints that guarantee the correctness of the circuit.

This paper presents a symbolic approach for the analysis of bounded Petri nets. The structure and behavior of the Petri net is symbolically modeled by using Boolean functions, thus reducing reasoning about Petri nets to Boolean calculation. The set of reachable markings is calculated by symbolically firing the transitions in the Petri net. Highly concurrent systems suffer from the state explosion problem produced by an exponential increase of the number of reachable states. This state explosion is handled by using Binary Decision Diagrams (BDDs) which are capable of representing large sets of markings with small data structures. Petri nets have the ability to model a large variety of systems and the flexibility to describe causality, concurrency, and conditional relations. The manipulation of vast state spaces generated by Petri nets enables the efficient analysis of a wide range of problems, e.g., deadlock freeness, liveness, and concurrency. A number of examples are presented in order to show how large reachability sets can be generated, represented, and analyzed with moderate BDD sizes. By using this symbolic framework, properties requiring an exhaustive analysis of the reachability graph can be efficiently verified.

The problem of optimal software synthesis for concurrent processes to be implemented on a single processor is addressed. The approach calls for the representation of the concurrent processes with Petri nets that give a theoretical foundation for the scheduling algorithm that sequentializes the concurrent processes and for the code generation step. The approach maximizes the amount of static scheduling to reduce the need of context switch and operating system intervention. Experimental results show the potential of our method to reduce software design time and errors.

A method for automating the synthesis of asynchronous control circuits from high level (CSP-like) and/or partial STG (involving only functionally critical events) specifications is presented.The method solves two key subtasks in this new, more flexible, design flow: handshake expansion, i.e. inserting reset events with maximum concurrency, and event reshuffling under interface and concurrency constraints, by means of concurrency reduction.In doing so, the algorithm optimizes the circuit both for size and performance.Experimental results show a significant increase in the solution space explored when compared to existing CSP-based or STG-based synthesis tools.

This paper describes a novel methodology for high performance asynchronous design based on timed circuits and on CAD support for their synthesis using relative timing. This methodology was developed for a prototype iA32 instruction length decoding and steering unit called RAPPID ("revolving asynchronous Pentium processor instruction decoder") that was fabricated and tested successfully. Silicon results show significant advantages-in particular, performance of 2.5-4.5 instructions per nS-with manageable risks using this design technology. RAPPID achieves three times faster performance and half the latency dissipating only half the power and requiring a minor area penalty as a comparable 400 MHz clocked circuit. Relative timing is based on user-defined and automatically extracted relative timing assumptions between signal transitions in a circuit and its environment. It supports the specification, synthesis, and verification of high-performance asynchronous circuits, such as pulse-mode circuits, that can be derived from an initial speed-independent specification. Relative Timing presents a "middle-ground" between clocked and asynchronous circuits, and is a fertile area for CAD development. We discuss possible directions for future CAD development.

The speed of a divider based on a digit-recurrence algorithm depends mainly on the latency of the quotient digit generation function. In this paper we present an analytical approach that extends the theory developed for standard SRT division and permits us to implement division schemes where a simpler function speculates the quotient digit. This leads to division units with shorter cycle time and variable latency since a speculation error may be produced and a post-correction of the quotient may be necessary. We have applied our algorithm to the design of a radix-16 speculative divider for double precision floating point numbers, that resulted in being faster than analogous implementations.

This paper describes a method of synthesis of asynchronous circuits with relative timing. Asynchronous communication between gates and modules typically utilizes handshakes to ensure functionality. Relative timing assumptions in the form "event a occurs before event b" can be used to remove redundant handshakes and associated logic. This paper presents a method for automatic generation of relative timing assumptions from the untimed specification. These assumptions can be used for area and delay optimization of the circuit. A set of relative timing constraints sufficient for the correct operation of the circuit is back-annotated to the designer. Experimental results for control circuits of a prototype iA32 instruction length decoding and steering unit called RAPPID (Revolving Asynchronous Pentium(R)Processor Instruction Decoder) shows significant improvements in area and delay over speed-independent circuits.

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.

Logic decomposition is a well-known problem in logic synthesis, but it poses new challenges when targeted to speed-independent circuits. The decomposition of a gate into smaller gates must preserve not only the functional correctness of a circuit but also speed independence, i.e., hazard freedom under unbounded gate delays. This paper presents a new method for logic decomposition of speed-independent circuits that solves the problem in two major steps: (1) logic decomposition of complex gates and (2) insertion of new signals that preserve hazard freedom. The method is shown to be more general than previous approaches and its effectiveness is evaluated by experiments on a set of benchmarks.

This paper presents a new technique for 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 available in the library and two gates H/sub 1/ and H/sub 2/ 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, the 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 sharing of decomposed logic. Overall, this method is more general than the existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.

Interfaces, by nature, are often asynchronous since they serve for connecting multiple distributed mod ules/agents without common clock. However, the most recent developments in the the ory of asynchronous design in the areas of specifications, mo dels, analysis, verification, synthesis, technology mapping, timing optimization and performanc e analysis are not widely known and r arely accepted by industry.

Petri nets are a graph-based formalism appropriate to model concurrent systems such as asynchronous circuits or network protocols. Symbolic techniques based on Binary Decision Diagrams (BDDs) have emerged as one of the strategies to overcome the state explosion problem in the analysis of systems modeled by Petri nets. The existing techniques for state encoding use a variable-per-place strategy that leads to encoding schemes with very low density. This drawback has been partially mitigated by using Zero-Suppressed BDDs, that provide a typical reduction of BDD sizes by a factor of two. This work presents novel encoding schemes for Petri nets. By using algebraic techniques to analyze the topology of the net, sets of places "structurally related" can be derived and encoded by only using a logarithmic number of Boolean variables. Such an approach allows one to drastically decrease the number of variables for state encoding and reduce memory and CPU requirements significantly.

This paper introduces bzy Transitions Systems &zTSs).The notion of laziness exDlicitlv distinguishes behveen the enabling and the firing of an e;ent in"a transition system.LzTSS can be effectively used to model the behavior of asynchronous circuits in whicfi relative timing assumptions cm-be made on the occurrence of events.These assumptions can be derived from the information known a priori about fie de]ay of fie 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 assumr3tions.Preliminary results show that significant area and performance improvements can be obtained by exploiting the extra "don't care" space implicitly provided by the Iazmess of the events.

The energy at the I/O pins is a significant part of the overall consumption of a chip. To reduce this energy, this work extends to the data bus the working zone encoding method originally applied to encoding an external address bus. This method is based on the conjecture that programs favor a few working zones of their address space at each instant and that addresses to consecutive accesses for each zone frequently differ by a small amount. When the difference is small, instead of sending the whole address, the method sends an offset with respect to the previous address to that zone, together with an identifier for the zone. In this paper the same idea is extended to the data bus. The approach has been applied to several SPEC95 streams of references to memory along with the corresponding data values in a system with multiplexed address and multiplexed instruction/data buses. Moreover the effect of instruction and data caches is evaluated. Comparisons are given with previous methods for bus encoding, showing significant improvement in all cases except for the multiplexed address bus with instruction cache, where the best scheme depends on the overhead of the implementation.

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.

Asynchronous circuits can be modeled as concurrent systems in which events are interpreted as signal transitions. The synthesis of concurrent systems implies the analysis of a vast state space that often requires computationally expensive methods. This work presents new methods for the synthesis of speed-independent circuits from a new perspective, overcoming both the analysis and computation complexity bottlenecks. The circuits are specified by free-choice signal transition graphs (STGs), a subclass of interpreted Petri nets. The synthesis approach is divided into the following steps: correctness, binary coding, implementability conditions, and logic synthesis. Each step is efficiently implemented by applying a set of structural techniques that analyze STGs without explicitly enumerating the underlying state space. Experimental results show that circuits can be generated from specifications that exceed in several orders of magnitude the largest STGs ever synthesized-with over 10/sup 27/ states. Computation times are also dramatically reduced. Nevertheless, the quality of results does not suffer from the use of structural techniques.

The energy consumption due to input-output pins is a substantial part of the overall chip consumption. To reduce this energy, this work presents the working-zone encoding (WZE) method for encoding an external address bus, based on the conjecture that programs favor a few working zones of their address space at each instant. In such cases, the method identifies these zones and sends through the bus only the offset of this reference with respect to the previous reference to that zone, along with an identifier of the current working zone. This is combined with a one-hot encoding for the offset. Several improvements to this basic strategy are also described. The approach has been applied to several address streams, broken down into instruction-only, data-only, and instruction-data traces, to evaluate the effect on separate and shared address buses. Moreover, the effect of instruction and data caches is evaluated. For the case without caches, the proposed scheme is specially beneficial for data address and shared buses, which are the cases where other codings are less effective. On the other hand, for the case with caches the best scheme for the instruction-only and data-only traces is the WZE, whereas for the instruction-data traces it is either the WZE or the bus-invert with four groups (depending on the energy overhead of these techniques).

This paper presents a novel approach for automatic test patterngeneration of asynchronous circuits. The techniques used for thispurpose assume that the circuit can only be exercised by applyingsynchronous test vectors, as is done by real-life testers.The main contribution of the paper is the abstraction of thecircuit's behavior as a synchronous finite state machine in such away that similar techniques to those currently used for synchronouscircuits can be safely applied for testing.Currently, the fault model being used is the input stuck-at model.Experimental results on different benchmarks show that our approachgenerates test vectors with high fault coverage.

This paper presents a novel technique for synthesis of speed-independentcircuits. It is based on partial order representation ofthe state graph called STG-unfolding segment. The new methoduses approximation technique to speed up the synthesis process.The method is illustrated on the basic implementation architecture.Experimental results demonstrating its efficiency are presented anddiscussed.

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.

The energy consumption at the I of the overall chip consumption.4 0 pins is a significant part his paper presents a method for encoding an external address bus which lowers its activity and, thus, decreases the energy.This method relies on the locality of memory references.Since applications favor a few working zones of their address space at each instant, for an address to one of these zones only the offset of this reference with respect to the previous reference to that zone needs to be sent over the bus, along with an identifier of the current working zone.This is combined with a modified one-hot encoding for the offset.An estimate of the area and energy overhead of the encoder/decoder are given; their effect is small.The approach has been applied to two memory-intensive examples, obtaining a bus-activity reduction of about.2 3 in both of them.Comparisons are given with previous metho L for bus encoding, showing significant improvement. I .

State assignment problems still need satisfactory solutions to make asynchronous circuit synthesis more practical. A well-known example of such a problem is that of complete state coding (CSC), which happens when a pair of different states in a specification has the same binary encoding. A standard way to approach state coding conflicts is to insert new state signals into the original specification in such a way that the original behavior remains intact. This paper proposes a method which improves over existing approaches by coupling generality, optimality, and efficiency. The method is based on the use of a class of "ground objects", called regions, that play the role of a bridge between state-based specifications (transition systems, TS's) and event-based specifications (signal transition graphs, STG's), We need to deal with both types of specification because designers usually prefer a timing diagram-like notation, such as STG, while optimization and cost analysis work better at the state level. A region in a transition system is a set of states that corresponds to a place in an STG (or the underlying Petri net). Regions are tightly connected with a set of properties that are to 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 will 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. This significantly improves the readability of the result (compared to a state-based description in which concurrency is represented implicitly by interleaving), and 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.

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.

This paper presents a set of sufficient conditions for the gate-level synthesis of speed-independent circuits when constrained to a given class of gate library. Existing synthesis methodologies are restricted to architectures that use simple AND-gates, and do not exploit the advantages offered by the existence of complex gates. The use of complex gates increases the speed and reduces the area of the circuits. These improvements are achieved because of (1) the elimination of the distributivity, signal persistency and unique minimal state requirements imposed by other techniques; (2) the reduction in the number of internal signals necessary to guarantee the synthesis; and finally (3) the utilization of optimization techniques to reduce the fan-in of the involved gates and the number of required memory elements.

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.

The speed of high-radix digit-recurrence dividers and square-root units is mainly determined by the complexity of the result-digit selection. We present a scheme in which a simpler function speculates the result digit, and, when this speculation is incorrect, a rollback or a partial advance is performed. This results in operations with a shorter cycle time and a variable number of cycles. The scheme can be used in separate division and square-root units, or in a combined one. Several designs were realized and compared in terms of execution time and area. The fastest unit considered is a radix-512 divider with a partial advance of six bits.>

The speed of SRT-type dividers is mainly determined by the complexity of the quotient-digit selection, so that implementations are limited to low-radix stages. A scheme is presented in which the quotient-digit is speculated and, when this speculation is incorrect, a rollback or a partial advance is performed. This results in a division operation with a shorter cycle time and a variable number of cycles. Several designs have been realized, and a radix-64 implementation that is 30% faster than the fastest conventional implementation (radix-8) at an increase of about 45% in area per quotient bit has been obtained. A radix-16 implementation that is about 10% faster than the radix-8 conventional one, with the additional advantage of requiring about 25% less area per quotient bit, is also shown.>

Methods for the synthesis of asynchronous circuits from signal transition graphs (STGs) have commonly used the state graph to solve the two main steps of this process: the state assignment problem and the generation of hazard-free logic. The size of the state graph can be of order O(2/sup n/), where n is the number of signals of the circuit. As synthesis tools for asynchronous systems start to mature, the size of the STGs increases and the exponential algorithms that work on the state graph become obsolete. This paper presents alternative algorithms that work in polynomial time and, therefore, avoid the generation of the SG. With the proposed algorithms, STGs can be synthesized and hazard-free circuits generated in extremely low CPU times. Improvements in two or three orders of magnitude (from hours to seconds) with respect to existing algorithms are achieved when synthesizing fairly large STGs.

Current algorithms to force the complete state coding (CSC) property for signal transition graphs work on the state graph and, therefore require exponential time and space. Polynomial algorithms have been only proposed for marked graphs. In this paper, a P-time algorithm for unique state coding (USC) is presented. Although more restrictive than CSC, it is shown that the USC property can be efficiently guaranteed for large STGs. Several experiments evidence that the obtained results are even better than those generated by exponential-time techniques.>

The response time of parallel adders is mainly determined by the carry propagation delay. The evaluation of conditions of the type A+B=K is addressed. Although an addition is involved in the comparison, it is shown that it can be evaluated without carry propagation, thus drastically reducing the computation time. Dependencies produced by branches degrade the performance of pipelined computers. The evaluation of conditions is often one of the critical paths in the execution of branch instructions. A circuit is proposed for the fast evaluation of A+B=K conditions that can significantly improve processor performance.>