The design of active array structures in analog circuits requires careful matching to minimize the impact of variations. This work presents a constructive approach for building these arrays to directly incorporate shifts due to process variations, considering systematic first-order and second order gradients; to account for systematic layout effects, including parasitic mismatch and layout-dependent effects due to stress; and to ensure that the resulting layout delivers high performance. The proposed algorithms are targeted to FinFET technologies and are validated for multiple analog blocks in a commercial 12nm FinFET process. The layouts generated by the proposed method are demonstrated to provide better matching and performance than prior methods.

Deep learning (DL) accelerators are optimized for standard convolution. However, lightweight convolutional neural networks (CNNs) use depthwise convolution (DwC) in key layers, and the structural difference between DwC and standard convolution leads to significant performance bottleneck in executing lightweight CNNs on such platforms. This work reuses the fast general matrix-vector multiplication (GEMM) core of DL accelerators by mapping DwC to channel-wise parallel matrix-vector multiplications. An analytical framework is developed to guide pre-RTL hardware choices, and new hardware modules and software support are developed for end-to-end evaluation of the solution. This GEMM-based DwC execution strategy offers substantial performance gains for lightweight CNNs: 7× speedup and 1.8× lower off-chip communication for MobileNet-v1 over a conventional DL accelerator, and 74× speedup over a CPU, and even 1.4× speedup over a power-hungry GPU.

Analog designs consist of multiple hierarchical functional blocks. Each block can be built using one of several design topologies, where the choice of topology is based on circuit performance requirements. A major challenge in automating analog design is in the identification of these functional blocks, which enables the creation of hierarchical netlist representations. This can facilitate a variety of design automation tasks, such as circuit layout optimization, because the layout is dictated by constraints at each level, such as symmetry requirements, that depend on the topology of the hierarchical block. Traditional graph-based methods find it hard to automatically identify the large number of structural variants of each block. To overcome this limitation, this article leverages recent advances in graph neural networks (GNNs). A variety of GNN strategies is used to identify netlist elements for circuit functional blocks at higher levels of the design hierarchy, where numerous design variants are possible. At lower levels of hierarchy, where the degrees of freedom in circuit topology is limited, structures are identified using graph-based algorithms. The proposed hierarchical recognition scheme enables the identification of layout constraints, such as symmetry and matching, which enable high-quality hierarchical layouts. This method is scalable across a wide range of analog designs. An experimental evaluation shows a high degree of accuracy over a wide range of analog designs, identifying functional blocks, such as low-noise amplifiers, operational transconductance amplifiers, mixers, oscillators, and band-pass filters, in larger circuits.

Well island generation and well tap placement is an important problem in analog/mixed-signal (AMS) circuits. Well taps can only prevent latchups within a certain radius of influence within a well island, and hence must be appropriately inserted to cover all devices. However, existing automated AMS layout paradigms typically defer the insertion of well taps and creation of well islands to a post-processing step after placement. This alters the placement, resulting in increased area and wire length, as well as circuit performance degradation. Therefore, there is a strong need for a solution that generates well islands and inserts well taps during placement so the placer can account for well overheads in optimizing placement metrics. In this work, we propose a modular solution using a graph-based optimization scheme that can be used within multiple placement paradigms with minimal intrusion. We demonstrate the integration of this scheme into stochastic, analytical, and designer-driven row-based placement. The method is demonstrated in advanced FinFET technologies. Layouts generated using this scheme show better area, wire length, and performance metrics at the cost of a marginal runtime degradation when compared to the post-processing approach. Using our scheme, there is an average improvement of 3% and 4% and a maximum improvement of 23% and 11% in area and wirelength, respectively, of layouts of various classes of AMS circuits at the cost of 17% average and 29% maximum increase in total runtime.

An analog/mixed-signal designer typically performs circuit optimization, involving intensive SPICE simulations, on a schematic netlist and then sends the optimized netlist to layout. During the layout phase, it is vital to maintain symmetry requirements to avoid performance degradation due to mismatch: these constraints are usually specified using user input or by invoking an external tool. Moreover, to achieve high performance, the layout must avoid large interconnect parasitics on critical nets. Prior works that optimize parasitics during placement work with coarse metrics such as the half-perimeter wire length, but these metrics do not appropriately emphasize performance-critical nets. The novel charge flow (CF) formulation in this work addresses both symmetry detection and parasitic optimization. By leveraging schematic-level simulations, which are available “for free” from the circuit optimization step, the approach (a) alters the objective function to emphasize the reduction of parasitics on performance-critical nets, and (b) identifies symmetric elements/element groups. The effectiveness of the CF-based approach is demonstrated on a variety of circuits within a stochastic placement engine.

Well island generation and well tap placement pose an important challenge in automated analog/mixed-signal (AMS) layout. Well taps prevent latchup within a radius of influence in a well island, and must cover all devices. Automated AMS layout flows typically perform well island generation and tap insertion as a postprocessing step after placement. However, this step is intrusive and potentially alters the placement, resulting in increased area, wire length, and performance degradation. This work develops a graph-based optimization that integrates well island generation, well tap insertion, and placement. Its efficacy is demonstrated within a stochastic placement engine. Experimental results show that this approach generates better area, wire length and performance metrics than traditional methods, at the cost of a marginal runtime degradation.

Common-centroid (CC) layouts are widely used in analog design to make circuits resilient to variations by matching device characteristics. However, CC layout may involve increased routing complexity and higher parasitics than other alternative layout schemes. This paper critically analyzes the fundamental assumptions behind the use of common-centroid layouts, incorporating considerations related to systematic and random variations as well as the performance impact of common-centroid layout. Based on this study, conclusions are drawn on when CC layout styles can reduce variation, improve performance (even if they do not reduce variation), and when non-CC layouts are preferable.

The common-centroid (CC) layout style is widely used to minimize the impact of variations among matched devices in analog blocks such as current mirror banks and differential pairs. This paper presents a constructive, performance-aware CC placement and routing algorithm for transistor arrays. Specifically, the proposed approach maximizes diffusion sharing, incorporates length of diffusion (LOD) based stress-induced performance variations, and mitigates resistive parasitics and electromigration (EM) hotspots, all of which are critical in modern technology nodes. The proposed algorithms are validated using cell- and circuit-level test cases in a commercial 12nm FinFET process. As compared to existing works, the cells generated using the proposed approach are shown to provide better performance in the presence of systematic variations, LOD, layout parasitics, and EM-induced degradation.

The quality of layouts generated by automated analog design have traditionally not been able to match those from human designers over a wide range of analog designs. The ALIGN (Analog Layout, Intelligently Generated from Netlists) project [2, 3, 6] aims to build an open-source analog layout engine [1] that overcomes these challenges, using a variety of approaches. An important part of the toolbox is the use of machine learning (ML) methods, combined with traditional methods, and this talk overviews our efforts. The input to ALIGN is a SPICE-like netlist and a set of perfor- mance specifications, and the output is a GDSII layout. ALIGN automatically recognizes hierarchies in the input netlist. To detect variations of known blocks in the netlist, approximate subgraph iso- morphism methods based on graph convolutional networks can be used [5]. Repeated structures in a netlist are typically constrained by layout requirements related to symmetry or matching. In [7], we use a mix of graph methods and ML to detect symmetric and array structures, including the use of neural network based approximate matching through the use of the notion of graph edit distances. Once the circuit is annotated, ALIGN generates the layout, going from the lowest level cells to higher levels of the netlist hierarchy. Based on an abstraction of the process design rules, ALIGN builds parameterized cell layouts for each structure, accounting for the need for common centroid layouts where necessary [11]. These cells then undergo placement and routing that honors the geomet- ric constraints (symmetry, common-centroid). The chief parameter that changes during layout is the set of interconnect RC parasitics: excessively large RCs could result in an inability to meet perfor- mance. These values can be controlled by reducing the distance between blocks, or, in the case of R, by using larger effective wire widths (using multiple parallel connections in FinFET technologies where wire widths are quantized) to reduce the effective resistance. ALIGN has developed several approaches based on ML for this purpose [4, 8, 9] that rapidly predict whether a layout will meet the performance constraints that are imposed at the circuit level, and these can be deployed together with conventional algorithmic methods [10] to rapidly prune out infeasible layouts. This presentation overviews our experience in the use of ML- based methods in conjunction with conventional algorithmic ap- proaches for analog design. We will show (a) results from our efforts so far, (b) appropriate methods for mixing ML methods with tra- ditional algorithmic techniques for solving the larger problem of analog layout, (c) limitations of ML methods, and (d) techniques for overcoming these limitations to deliver workable solutions for analog layout automation.

Automated subcircuit identification and annotation enables the creation of hierarchical representations of analog netlists, and can facilitate a variety of design automation tasks such as circuit layout and optimization. Subcircuit identification must navigate the numerous alternative structures that can implement any analog function, but traditional graph-based methods cannot easily identify the large number of such structural variants. The novel approach in this paper is based on the use of a trained graph convolutional neural network (GCN) that identifies netlist elements for circuit blocks at upper levels of the design hierarchy. Structures at lower levels of hierarchy are identified using graph-based algorithms. The proposed recognition scheme organically detects layout constraints, such as symmetry and matching, whose identification is essential for high-quality hierarchical layout. The subcircuit identification method demonstrates a high degree of accuracy over a wide range of analog designs, successfully identifies larger circuits that contain subblocks such as OTAs, LNAs, mixers, oscillators, and band-pass filters, and provides hierarchical decompositions of such circuits.

Automating analog layout is a long-standing research problem, with a history that goes back several decades. While digital design is largely automated today, analog layout has been significantly more resistant: automation has not made much headway in industry settings. There are several reasons for this, including:

The problem of analog design automation has vexed several generations of researchers in electronic design automation. At its core, the difficulty of the problem is related to the fact that machinegenerated designs have been unable to match the quality of the human designer. The human designer typically recognizes blocks from a netlist and draws upon her/his experience to translate these blocks into a circuit that is laid out in silicon. The ability to annotate blocks in a schematic or netlist-level description of a circuit is key to this entire process, but it is a process fraught with complexity due to the large number of variants of each circuit type. For example, the number of topologies of operational transconductance amplifiers (OTAs) easily numbers in the hundreds. A designer manages this complexity by dividing this large set of variants into classes (e.g., OTAs may be telescopic, folded cascode, etc.). Even so, the number of minor variations within each class is large. Early approaches to analog design automation attempted to use rule-based methods to capture these variations, but this database of rules required tender care: each new variant might require a new rule. As machine learning (ML) based alternatives have become more viable, alternative forms of solving this problem have begun to be explored.

This paper presents analog layout automation efforts under the ALIGN ("Analog Layout, Intelligently Generated from Netlists") project for fast layout generation using a modular approach based on a mix of algorithmic and machine learning-based tools. The road to rapid turnaround is based on an approach that detects structure and hierarchy in the input netlist and uses a grid based philosophy for layout. The paper provides a view of the current status of the project, challenges in developing open-source code with an academic/industry team, and nuts-and-bolts issues such as working with abstracted PDKs, navigating the "wall" between secured IP and open-source software, and securing access to example designs.

In this paper, we propose a routing flow for nets within a standard cell that generates layout of standard cells without any design rule violations. Design rules, density rules for metal fill, and pin-access requirements are modeled via Boolean formulas for discrete layout objects on grids. Formulas are translated into a single Boolean satisfiability problem (SAT). Having constraints on net connectivity and candidate routes, the SAT solver produces legal and complete routing concurrently for all nets satisfying mandatory pin-access and density requirements. A SAT-based optimization engine minimizes undesired layout patterns such as DFM (design-for-manufacturing) hot spots.

Non-rigid 3D registration is a technique for matching 3D scans of a scene involving deformable objects. Augmented reality, gesture recognition, medical imaging, and many other computer vision and graphics applications require real-time registration to model deformable or articulated objects. Unfortunately, non-rigid registration is a computationally intensive problem that requires careful optimization to maximize throughput and latency. We present a FPGA+CPU accelerator for real-time non-rigid 3D registration based on Tree Reweighted Message Passing (TRW-S). We overcome memory bound issues and scheduling limitations of conventional TRW-S by dynamically generating the Markov Random Fields. This, along with a bevy of other architectural optimizations, allows us to almost saturate 1024 multipliers in a Arria 10 at 100MHz. We achieve a 600x speed up over baseline TRW-S and our registration architecture has up to 81x energy reduction over a software implementation of our algorithm. We demonstrate the performance of our system by performing real-time (20 scan per second) registration on a complicated surgical scene.

Graph applications have been gaining importance in the last decade due to emerging big data analytics problems such as Web graphs, social networks, and biological networks. For these applications, traditional CPU and GPU architectures suffer in terms of performance and power consumption due to irregular communications, random memory accesses, and load balancing problems. It has been shown that specialized hardware accelerators can achieve much better power and energy efficiency compared to the general purpose CPUs and GPUs. In this paper, we present a template-based methodology specifically targeted for hardware accelerator design of big-data graph applications. Important architectural features that are key for energy efficient execution are implemented in a common template. The proposed template-based methodology is used to design hardware accelerators for different graph applications with little effort. Compared to an application-specific high-level synthesis methodology, we show that the proposed methodology can generate hardware accelerators with up to 18× better energy efficiency and requires less design effort.

Specialized hardware accelerators can significantly improve the performance and power efficiency of compute systems. In this paper, we focus on hardware accelerators for graph analytics applications and propose a configurable architecture template that is specifically optimized for iterative vertex-centric graph applications with irregular access patterns and asymmetric convergence. The proposed architecture addresses the limitations of the existing multi-core CPU and GPU architectures for these types of applications. The SystemC-based template we provide can be customized easily for different vertex-centric applications by inserting application-level data structures and functions. After that, a cycle-accurate simulator and RTL can be generated to model the target hardware accelerators. In our experiments, we study several graph-parallel applications, and show that the hardware accelerators generated by our template can outperform a 24 core high end server CPU system by up to 3x in terms of performance. We also estimate the area requirement and power consumption of these hardware accelerators through physical-aware logic synthesis, and show up to 65x better power consumption with significantly smaller area.

Intelligent data analysis has become more important in the last decade especially because of the significant increase in the size and availability of data. In this paper, we focus on the common execution models and characteristics of iterative graph analytics applications. We show that the features that improve work efficiency can lead to significant overheads on existing systems. We identify the opportunities for custom hardware implementation, and outline the desired architectural features for energy efficient computation of graph analytics applications.

As the size of available data is increasing, it is becoming inefficient to scale the computational power of traditional systems. To overcome this problem, customized application-specific accelerators are becoming integral parts of modern system on chip (SOC) architectures. In this paper, we summarize existing hardware accelerators for data centers and discuss the techniques to implement and embed them along with the existing SOCs.

Heterogeneous architectures with single-instruction set architecture (ISA) asymmetric cores can improve both the performance and energy efficiency of software execution by dynamically selecting the most appropriate core type to run each execution thread. In this paper, we propose a trace-based methodology to explore power and performance benefits of single-ISA heterogeneous core architectures. The basic idea is to collect multiple traces by running a workload on different homogeneous platforms, and to align these traces for offline analysis. For this, we propose a wavelet-based similarity metric, which captures both fine-grain and coarse-grain software phases across different traces. Then, we propose a scalable dynamic programming algorithm to optimize this metric to align the traces. Our experiments show that the runtime and energy values predicted by our offline methodology have good accuracy with respect to the real measurements from a prototype heterogeneous system.

Heterogeneous architectures with single-ISA asymmetric cores have the potential to improve both the performance and energy efficiency of software execution by dynamically selecting the most appropriate core type to run each execution thread. In this paper, we propose a trace-based methodology to explore power and performance benefits of single-ISA heterogeneous core architectures. The basic idea is to collect multiple traces by running a workload on different homogeneous platforms, and to align these traces for offline analysis. For this, we propose a wavelet-based similarity metric, which captures both fine-grain and coarse-grain software phases across different traces. Then, we propose a scalable dynamic programming algorithm to optimize this metric to align the traces. Our experiments show that the runtime and energy values predicted by our offline methodology have good accuracy with respect to the real measurements from a prototype heterogeneous system. The proposed methodology can enable design space exploration of single-ISA heterogeneous multi-core systems using traces from off-the-shelf homogeneous systems.

Gate sizing and threshold voltage selection is an important step in the VLSI design process to optimize power and performance of a given netlist. In this paper, we provide an overview of the ISPD-2013 Discrete Cell Sizing Contest. Compared to the ISPD-2012 Contest, we propose improvements in terms of the benchmark suite and the timing models utilized. In this paper, we briefly describe the contest, and provide some details about the standard cell library, benchmark suite, timing infrastructure and the evaluation metrics.

We propose a flow for routing nets within a standard cell that 1) generates candidate routes for point-to-point segments; 2) finds conflicts (electrical shorts and geometric design rule violations) between candidate routes; and 3) solves a SAT instance producing a legal and complete routing for all nets in the standard cell. This approach enables routing automation for cutting-edge process technology nodes. We present how to make this technique more effective by introducing pruning techniques to reduce the work required in all three steps. We also show how we can further optimize routing quality within the SAT formulation through the use of successively more stringent constraints. Recent improvements in the speed of SAT solvers make such a formulation practical for even complex standard cells. A routing tool based on our SAT formulation is currently being used to route real industrial standard cell layouts. It demonstrates acceptable runtime and 89% coverage of our industrial standard cell library, including scan flip-flops, adders, and multiplexers. We also observe a significant reduction in amount of metal2 routing in comparison with industrial hand-crafted standard cells.

Circuit optimization is essential to minimize power consumption of designs while satisfying timing constraints. The CAD problem focused on in the ISPD-2012 Contest is simultaneous gate sizing and threshold voltage assignment. In this paper, we describe an overview of the contest objectives and the provided benchmark suite. Furthermore, some details are provided in terms of the standard cell library, timing models, and the evaluation metrics of the ISPD-2012 Contest.

It is becoming increasingly important to design high-performance circuits with as low power as possible. In this paper, we study the gate sizing and device parameter selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian relaxation-based formulation that decouples timing analysis from optimization without a resulting loss in accuracy. We also propose a graph model that accurately captures discrete cell-type characteristics based on library data. We model the relaxed Lagrangian subproblem as a graph problem and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. We also show the benefit of the graph model we propose to solve the discrete optimization problem. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

In this work we propose a regular layout fabric practical for industrial random logic design and present cell synthesis algorithms specialized to this fabric. We show results on an industrial test-case where physical synthesis onto a library of extremely regular cells results in only 7% increase in leakage in comparison to traditional standard cells. We also show that using this fabric based cell synthesis system allows better overall area by allowing more upper layer routing. We achieve a 4% routable die size reduction by simultaneous cell synthesis and custom M1 routing.

This paper presents an algorithm for compressing long traces generated using RTL or other fast simulation. The compressed traces can be used by power analysis tools to estimate power on the original traces. We show that the length of the compressed trace is independent of the length of original trace and is a function of circuit size (precisely, its active part) for which the trace was generated. Our experiments show up to 578× compression ratio on several long RTL traces (up to 320,000 clock transitions) used for power analysis on three industrial blocks (4K, 114K and 202K gates). This leads to significant runtime improvement, especially when the traces are reused over multiple power analysis runs. The dynamic power estimated using compressed traces is within 5% of the power analysis on original traces.

It is becoming more and more important to design high performance designs with as low power as possible. In this paper, we study the gate sizing and device technology selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use the traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian Relaxation (LR) based formulation that decouples timing analysis from optimization without resulting in loss of accuracy. We also propose a graph model that accurately captures discrete cell type characteristics based on library data. We model the relaxed Lagrangian subproblem as a discrete graph problem, and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

We explore the power benefits of changing a microprocessor path histogram through circuit sizing based on statistical timing analysis and optimization (STAO) versus a deterministic timing approach that uses statistical design to establish a global guardband followed by conventional optimization (SDGG). Using an analytical modeling approach, we quantify the differences in total power between the two approaches while maintaining an equivalent performance distribution. For a relative 1σ random WID stage delay variation of 5% and representative microprocessor critical paths, the analysis indicates that the STAO approach enables ~2% power reduction over the SDGG approach. To achieve a 4% and 6% power reduction through the STAO approach, the process variation needs to increase by a factor of 2x and 4x, respectively.

We describe various design automation solutions for design migration to a dual-Vt process technology. We include the results of a Lagrangian Relaxation based tool, iSTATS, and a heuristic iterative optimization flow. Joint dual-Vt allocation and sizing reduces total power by 10+% compared with Vt allocation alone, and by 25+% compared with pure sizing methods. The heuristic flow requires 5x larger computation runtime than iSTATS due to its iterative nature.

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 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.

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.

In this paper, we present our experiences in using symbolic model checking to analyze a specification of a software system for aircraft collision avoidance. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in whether model checking can be effectively applied to large software specifications. To investigate this, we translated a portion of the state-based system requirements specification of Traffic Alert and Collision Avoidance System II (TCAS II) into input to a symbolic model checker (SMV). We successfully used the symbolic model checker to analyze a number of properties of the system. We report on our experiences, describing our approach to translating the specification to the SMV language, explaining our methods for achieving acceptable performance, and giving a summary of the properties analyzed. Based on our experiences, we discuss the possibility of using model checking to aid specification development by iteratively applying the technique early in the development cycle. We consider the paper to be a data point for optimism about the potential for more widespread application of model checking to software systems.

In this paper we present our results and experiences of using symbolic model checking to study the specification of an aircraft collision avoidance system. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in the question of whether or not model checking techniques can be applied to large software specifications.To investigate this, we translated a portion of the finite-state requirements specification of TCAS II (Traffic Alert and Collision Avoidance System) into a form accepted by a model checker (SMV). We successfully used the model checker to investigate a number of dynamic properties of the system.We report on our experiences, describing our approach to translating the specification to the SMV language and our methods for achieving acceptable performance in model checking, and giving a summary of the properties that we were able to check. We consider the paper as a data point that provides reason for optimism about the potential for successful application of model checking to software systems. In addition, our experiences provide a basis for characterizing features that would be especially suitable for model checkers built specifically for analyzing software systems.The intent of this paper is to evaluate symbolic model checking of state-machine based specifications, not to evaluate the TCAS II specification. We used a preliminary version of the specification, the version 6.00, dated March, 1993, in our study. We did not have access to later versions, so we do not know if the properties identified here are present in later versions.

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. Applications range from logic optimization of asynchronous digital circuits to evaluation of execution times of programs for real-time systems. We present an efficient algorithm to find exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. This result is more general than the methods presented in several previously published papers as it handles cyclic graphs and yields the tightest possible bounds on event separations. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph. Examples are presented that demonstrate the utility and efficiency of the solution. The algorithm will form a basis for exploration of timing-constrained synthesis techniques.>

Field-programmable gate arrays (FPGAs) are an important implementation medium for digital logic. Unfortunately, they currently suffer from poor silicon area utilization due to routing constraints. In this paper we present Triptych, an FPGA architecture designed to achieve improved logic density with competitive performance. This is done by allowing a per-mapping tradeoff between logic and routing resources, and with a routing scheme designed to match the structure of typical circuits. We show that, using manual placement, this architecture yields a logic density improvement of up to a factor of 3.5 over commercial FPGAs, with comparable performance. We also describe Montage, the first FPGA architecture to fully support asynchronous and synchronous interface circuits.

Field-programmable gate arrays (FPGAs) are becoming an increasingly important implementation medium for digital logic. One of the most important keys to using FPGAs effectively is a complete, automated software system for mapping onto the FPGA architecture. Unfortunately, many of the tools necessary require different techniques than traditional circuit implementation options, and these techniques are often developed specifically for only a single FPGA architecture. In this paper we describe automatic mapping tools for Triptych, an FPGA architecture with improved logic density and performance over commercial FPGAs. These tools include a simulated-annealing placement algorithm that handles the routability issues of fine-grained FPGAs, and an architecture-adaptive routing algorithm that can easily be retargeted to other FPGAs. We also describe extensions to these algorithms for mapping asynchronous circuits to Montage, the first FPGA architecture to completely support asynchronous and synchronous interface applications.

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. We present results of applying an efficient algorithm to solve this problem of three different application domains. These are: analysis of instruction execution times of an asynchronous multiprocessor, analysis of a high-performance mixed asynchronous/synchronous communication interface, and isochronic fork analysis in asynchronous circuit synthesis. The algorithm we use yields exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. This class of graphs is quite large and includes graphs that are not strongly connected. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph.

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. Applications range from logic optimization of asynchronous digital circuits to evaluation of execution times of programs for real-time systems. We present an efficient algorithm to find exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph.>