We present the clock architecture of the Stratix?10 FPGA, which uses a routable clock network rather than the fixed clock networks of previous generations. We describe the flexibility provided by this routable clock network and how arbitrarily sized clock trees can be synthesized and placed anywhere on the FPGA. We show how this capability to generate customized clock trees can provide better performance through reduced clock loss while maintaining the ability to handle the large number of clock domains that modern systems require. We experimentally demonstrate how a routable clock tree reduces the clock loss of the user design implementation by up to 6% of clock insertion delay.

Bioinformatics is an emerging field with seemingly limitless possibilities for advances in numerous areas of research and applications. We propose a scalable FPGA-based solution to the short read mapping problem in DNA sequencing, which greatly accelerates the task of aligning short length reads to a known reference genome. We compare the runtime, power consumption, and sensitivity of the hardware system to the BFAST and Bowtie software tools. The hardware system demonstrates a 250X speedup versus BFAST and a 31X speedup versus Bowtie on eight CPU cores. Also, the hardware system is more sensitive than Bowtie, which aligns approximately 80% of the short reads, as compared to 91% aligned by the hardware.

Coarse Grained Reconfigurable Arrays (CGRAs) are a promising class of architectures for accelerating applications using a large number of parallel execution units for high throughput. While they are typically good at utilizing many processing elements for a single task with automatic parallelization, all processing elements are required to perform their operations in lock step; this makes applications that involve multiple data streams, multiple tasks, or unpredictable schedules more difficult to program and use their resources inefficiently. Other architectures like Massively Parallel Processor Arrays (MPPAs) are better suited for these applications and excel at executing unrelated tasks simultaneously, but the amount of resources easily utilized for a single task is limited. We are developing a new architecture with the multi-task flexibility of an MPPA and the automatic parallelization of a CGRA. A key to the flexibility of MPPAs is the ability for subtasks to execute independently instead of in lock step with all other subtasks on the array. In this paper, we develop the special network and control circuitry to add support for this execution style in a CGRA with less than 2% area overhead. Additionally, we also describe the CAD tool modifications and application developer guidelines for utilizing the resulting hybrid CGRA/MPPA architecture.

Functional units provide the backbone of any spatial accelerator by providing the computing resources. The desire for having rich and expensive functional units is in tension with producing a regular and energy-efficient computing fabric. This paper explores the design trade-off between complex, universal functional units and simpler, limited functional units.

Efficient storage in spatial processors is increasingly important as such devices get larger and support more concurrent operations. Unlike sequential processors that rely heavily on centralized storage, e.g. register files and embedded memories, spatial processors require many small storage structures to efficiently manage values that are distributed throughout the processor's fabric. The goal of this work is to determine the advantages and disadvantages of different architectural structures for storing values on-chip when optimizing for energy efficiency as well as area. Examination of applications for coarse-grained reconfigurable arrays (CGRAs) shows that most values are short-lived; they are produced and consumed quickly, but the distribution of value lifetimes has a reasonably long tail. We take advantage of this distribution to optimize register storage structures for managing short-, medium-, and long-lived values. We show that using a combination of register storage structures, each tailored for values with different lifetimes, provides a reduction in overall area-energy product to 0.69× the area-energy of the baseline architecture, without loss of performance. Finally we provide energy profiles, characteristics, and comparisons of each register structure to enable architects to guide future design choices.

In this paper we present SPR, a new architecture-adaptive mapping tool for use with Coarse-Grained Reconfigurable Architectures (CGRAs). It combines a VLIW style scheduler and FPGA style placement and pipelined routing algorithms with novel mechanisms for integrating and adapting the algorithms to CGRAs. We introduce a latency padding technique that provides feedback from the placer to the scheduler to meet the constraints of a fixed frequency device with configurable interconnect. Using a new dynamic clustering method during placement, we achieved a 1.3x improvement in throughput of mapped designs. Finally, we introduce an enhancement to the PathFinder algorithm for targeting architectures with a mix of dynamically multiplexed and statically configurable interconnects. The enhanced algorithm is able to successfully share statically configured interconnect in a time-multiplexed way, achieving an average channel width reduction of .5x compared to non-shared static interconnect.

Spatially-tiled architectures, such as coarse-grained reconfigurable arrays (CGRAs), are powerful architectures for accelerating applications in the digital-signal processing, embedded, and scientific computing domains. In contrast to field-programmable gate arrays (FPGAs), another common accelerator, they typically time-multiplex their processing elements and are word rather than bit-oriented. These differences lead us to re-examine some of the traditional architecture choices made for FPGAs as we move to these coarser-granularity architectures. In this paper we study the efficiency of time-multiplexing global interconnect as architectures scale from single-bit to multi-bit datapaths. Using the Mosaic infrastructure, we analyzed the design trade-offs involved in static vs. time-multiplexed routing for global interconnect channels, as well as the benefit of including a dedicated bit-wide control interconnect to supplement the word-wide datapath of a CGRA. We show that a time-multiplexed interconnect is beneficial in these coarse-grained systems, reducing the area-energy product to 0.32times the area-energy product of a fully static interconnect. We also show that for our benchmarks, which include single-bit control logic, providing both word and bit-wide interconnect resources further reduces the area-energy product to 0.94times that of an exclusively word-wide interconnect.

For some time now, configurable computing has been hailed as the future for application-specific architectures. The purported advantages are well-known: the increasing NRE cost of chip fab is avoided, the same platform can be used for a variety of applications, and implementations can be fixed or upgraded in the field. But in spite of many attempts to move configurable computing platforms into the mainstream, they have yet to achieve their full promise. This talk will explore the barriers that have kept configurable computing on the sidelines thus far, and suggest steps that we might take to take advantage of its full potential

Platform FPGAs that integrate sequential processors with a spatial fabric have become prevalent. While these hybrid architectures ease the burden of integrating sequential and spatial code in a single application, programming them, and particularly their spatial fabrics remains challenging. The difficulty arises in part from the lack of an agreed upon computational model and family of programming languages. In addition, moving algorithms into hardware is an arcane art far removed from the experience of most programmers. To address this challenge, we present a new type architecture, an abstract model analogous to the von Neumann machine for sequential computers, that can serve as common ground for algorithm designers, language designers, and hardware architects. We show that many parallel architectures, including platform FPGAs, are implementations of this type architecture. Using examples from a variety of application domains, we show how algorithms can be analyzed to estimate their performance on implementations of this type architecture. This analysis is done without having to delve into the details of any architecture in particular. Finally, we describe some of the common features of languages designed for expressing micro-parallelism, highlighting connections with the type architecture

Programmable spatial fabrics, such as FPGAs, can provide some of the performance and efficiency benefits of custom hardware while retaining the low cost and flexibility of reprogrammable architectures. However, these fine-grained parallel architectures still have not been as widely adopted as many believe they could be for computationally intensive applications. The problem is two-fold: First, most applications contain substantial amounts of mostly sequential code that does not execute efficiently on a spatial fabric. Second, programming spatial architectures still requires some knowledge of the arcane arts of hardware engineering.Recently, hybrid processors that integrate a sequential processor with a spatial fabric have become prevalent. While hybrid computers ease the burden of integrating sequential and spatial code in a single application, programming them, and particularly their spatial fabrics, remains challenging. Part of the difficulty lies in the lack of a commonly agreed upon computational model and family of programming languages.To address this challenge, we are developing a new type architecture--an abstract model analogous to the von Neumann machine for sequential computers--that can serve as common ground for algorithm designers, language designers, and hardware architects. We show how this model applies to several relevant architectures, and present examples of how it can effectively inform algorithm, language, and hardware design, thereby improving the programmability of hybrid processors.

Interconnect delays are becoming an increasingly significant part of the critical path delay for circuits implemented in FPGAs. Pipelined interconnects have been proposed to address this problem, where long distance routes are pipelined using registers available in the configurable interconnect architecture. Unfortunately, pipelined interconnects are much harder to route than simple interconnects. QuickRoute is a fast, heuristic router based on PathFinder for pipelined interconnects. While its performance scales well with circuit size, it requires O(N2) space and in practice can only be used for circuits with up to about 10,000 nodes. This paper describes an efficient solution to this space problem based on arithmetic coding, a technique widely used in data compression. We show that this reduces the space complexity to O(NlogN) while only slightly affecting performance. This result will allow pipelined routing to be used even for very large FPGA architectures. Experiments show that memory usage is reduced by 90% even for our relatively small coarse-grained benchmark circuits

We present a pipelining-aware router for fieldprogrammable gate arrays (FPGAs). The problem of routing pipelined signals is different from the conventional FPGA routing problem. The two-terminal N/sub D/ pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N/spl ges/1) distinct pipelining resources. In the case of a multiterminal pipelined signal, the problem is to find a minimum spanning tree (MST) that contains sufficient pipelining resources such that pipelining constraints at each sink are satisfied. In this paper, we first present an optimal algorithm for finding a lowest cost 1/sub D/ route. The optimal 1/sub D/ algorithm is then used as a building block for a greedy two-terminal N/sub D/ router. Next, we discuss the development of a multiterminal routing algorithm (PipeRoute) that effectively leverages both the 1/sub D/ and N/sub D/ routers. Finally, we present a preprocessing heuristic that enables the application of PipeRoute to pipelined FPGA architectures. PipeRoute's performance is evaluated by routing a set of benchmark netlists on the reconfigurable pipelined datapath (RaPiD) architecture. Our results show that the architecture overhead incurred in routing netlists on RaPiD is less than 20%. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

Current FPGA placement algorithms estimate the routability of a placement using architecture-specific metrics. The shortcoming of using architecture-specific routability estimates is limited adaptability. A placement algorithm that is targeted to a class of architecturally similar FPGAs may not be easily adapted to other architectures. The subject of this paper is the development of a routability-driven architecture adaptive FPGA placement algorithm called Independence. The core of the Independence algorithm is a simultaneous place-and-route approach that tightly couples a simulated annealing placement algorithm with an architecture adaptive FPGA router (Pathfinder). The results of our experiments demonstrate Independence's adaptability to island-style and hierarchical FPGA architectures. The quality of the placements produced by Independence is within 5% of the quality of VPR's placements and 17% better than the placements produced by HSRA's place-and-route tool. Further, our results show that Independence produces clearly superior placements on routing-poor island-style FPGA architectures.

Current FPGA placement algorithms estimate the routability of a placement using architecture-specific metrics. The shortcoming of using architecture-specific routability estimates is limited adaptability. A placement algorithm that is targeted to a class of architecturally similar FPGAs may not be easily adapted to other architectures. The subject of this paper is the development of a routability-driven architecture adaptive FPGA placement algorithm called Independence. The core of the Independence algorithm is a simultaneous place-and-route approach that tightly couples a simulated annealing placement algorithm with an architecture adaptive FPGA router (Pathfinder). The results of our experiments demonstrate Independence's adaptability to island-style FPGAs, a hierarchical FPGA architecture (HSRA), and a coarse-grained reconfigurable architecture (RaPiD). The quality of the placements produced by Independence is within 1.2% of the quality of VPRs placements. 17% better than the placements produced by HSRA's placer, and within 0.7% of RaPiD's placer. Further, our results show that Independence produces clearly superior placements on routing-poor island-style FPGA architectures.

The simulation of large systems of biochemical reactions is a key part of research into molecular signaling and information processing in biological cells. However, it can be impractical because many relevant reactions are modeled as stochastic, discrete event processes, and the complexity of the computing task scales with the number of discrete events in a simulation. Traditionally, such simulations are computed on general purpose CPUs, and sometimes in networks of such processors. We show that an alternative algorithm to the conventional approaches based on the Gillespie algorithm reveals a fine-grained parallel structure that is amenable to realization in FPGA hardware. A method is shown for compiling biochemical reaction systems into corresponding Verilog descriptions of simulators that employ this alternative algorithm. We describe a preliminary implementation of such a compiled accelerator that demonstrates the performance of this approach, achieving an initial performance that is 20 times faster than a competing general purpose CPU.

In this work, we parameterize and explore the interconnect structure of pipelined FPGAs. Specifically, we explore the effects of interconnect register population, length of registered routing track segments, registered IO terminals of logic units, and the flexibility of the interconnect structure on the performance of a pipelined FPGA. Our experiments with the RaPiD [4] architecture identify tradeoffs that must be made while designing the interconnect structure of a pipelined FPGA. The post-exploration architecture that we found shows a 19% improvement over RaPiD, while the area overhead incurred in placing and routing benchmarks netlists on the post-exploration architecture is 18%.

As interconnect delays begin to dominate logic delays in large circuits, pipelined interconnects will be needed to achieve the highest performance. In FPGAs, this pipelining will be provided by the configurable interconnect architecture itself. This changes the routing problem substantially since the shortest path problem, which is at the core of any router, becomes NP-hard when latency constraints are added. That is, if signals must be routed through a given number of registers between source and destination, an efficient shortest path algorithm like Djikstra's algorithm is no longer an option. We propose here an approximate algorithm that uses simple heuristics to solve the pipelined shortest path problem efficiently. We have incorporated QuickRoute in the PathFinder router to route pipelined interconnects. We present the results achieved with QuickRoute for several circuits with heavily pipelined interconnect which show an improvement over a previously described algorithm.

Field-programmable gate arrays (FPGAs) have become an extremely popular implementation technology for custom hardware because they offer a combination of low cost and very fast turnaround. Because of their in-system reconfigurability, FPGAs have also been suggested as an efficient replacement for application-specific integrated circuits (ASICs) and digital signal processors (DSPs) for applications that require a combination of high performance, low cost, and flexibility. Unfortunately, the use of FPGAs in mobile embedded systems platforms is hampered by the very large overhead of FPGA-based architectures. Coarse-grained configurable architectures can reduce this overhead substantially by taking advantage of the application domain to specialize the reconfigurable architecture via coarse-grained components and interconnects. This paper presents the design and implementation of an OFDM receiver in the RaPiD reconfigurable architecture as a case study for comparing the relative cost and performance of ASIC, DSP, FPGA, and coarse-grained reconfigurable architectures. RaPiD is a coarse-grained reconfigurable architecture specialized to the domain of signal and image processing. The RaPiD architecture provides a reconfigurable pipelined datapath controlled by efficient reconfigurable control logic: We have implemented the computationally intensive parts of an OFDM receiver on the RaPiD architecture and have developed careful estimates of corresponding implementations in representative ASIC, DSP and FPGA technology. Our results show that, for this application, RaPiD fills the cost/performance gap between programmable DSP and ASIC architectures, achieving a factor of 6 better than a DSP implementation but a factor of 6 less than an ASIC implementation.

We present a pipelining-aware router for FPGAs. The problem of routing pipelined signals is different from the conventional FPGA routing problem. For example, the two terminal N-Delay pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N > 1) distinct pipelining resources. In the case of a multi-terminal pipelined signal, the problem is to find a Minimum Spanning Tree that contains sufficient pipelining resources such that the delay constraint at each sink is satisfied. We begin this work by proving that the two terminal N-Delay problem is NP-Complete. We then propose an optimal algorithm for finding a lowest cost 1-Delay route. Next, the optimal 1-Delay router is used as the building block for a greedy two terminal N-Delay router. Finally, a multi-terminal routing algorithm (PipeRoute) that effectively leverages the 1-Delay and N-Delay routers is proposed. PipeRoute's performance is evaluated by routing a set of retimed benchmarks on the RaPiD [2] architecture. Our results show that the architecture overhead incurred in routing retimed netlists on RaPiD is less than a factor of two. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

The problems of placement and routing are without doubt the most time-consuming part of the process of automatically synthesizing and configuring circuits for field-programmable gate arrays (FPGAs). FPGAs offer the ability to quickly reconfigure circuits to support rapid prototyping, emulation, or configurable computing, but the time to perform placement and routing, which can take many hours, has become a serious bottleneck. This problem is addressed here by showing that the negotiation-based routing paradigm, which has been applied successfully in several FPGA routers, can be parallelized to achieve increased performance without any significant decrease in the quality of the results. In this paper, we report several new findings related to the negotiation-based routing paradigm. We examine in-depth the convergence of the negotiation-based routing algorithm. We illustrate that the negotiation-based algorithm can be parallelized. Finally, we demonstrate that a negotiation-based parallel FPGA router performs well in terms of delay and speedup with practical FPGA circuits.

Efficient, deeply pipelined implementations exist for a wide variety of important computation-intensive applications, and many special-purpose hardware machines have been built that take advantage of these pipelined computation structures. While these implementations achieve high performance, this comes at the expense of flexibility. On the other hand, flexible architectures proposed thus far have not been very efficient. RaPiD is a reconfigurable pipelined datapath architecture designed to provide a combination of performance and flexibility for a variety of applications. It uses a combination of static and dynamic control to efficiently implement pipelined computations. This control, however, is very complicated; specifying a computation's control circuitry directly would be prohibitively difficult. This paper describes how specifications of a pipelined computation in a suitably high-level language are compiled into the control required to implement that computation in the RaPiD architecture. The compiler extracts a statically configured datapath from this description, identifies the dynamic control signals required to execute the computation, and then produces the control program and decoding structure that generates these dynamic control signals.

Abstract { Although tremendous advances have been accom-plished in logic synthesis in the past two decades, in some cases logic synthesis still cannot attain the improvements possible by clever designers. This, in part, is a result of logic synthesis not optimizing across register boundaries. In this paper we focus on precomputation as a resynthesis technique capable of resyn-thesizing across register boundaries. By using precomputation, a critical signal is computed earlier in time, thus allowing it to be combinationally optimized with logic from previous pipeline stages. Precomputation automatically discovers some standard circuit transformations like bypassing and lookahead. In addi-tion, precomputation can be used in conjunction with combina-tional logic synthesis to resynthesize a circuit to obtain better performance. This paper contributes to the understanding and development of precomputation. First, it provides a synthesis algorithm for precomputation. Second, it demonstrates how precomputation can be used to improve sequential logic resynthesis and reports the results of applyinga heuristic to a subset of theMCNC bench-marks. Third, it illustrates how precomputation generalizes and uni es bypassing and lookahead { two important and practical architectural transformations often used in processor design and high-level synthesis of DSP processors. Finally, it claries the relationships among precomputation, retiming, and implicit re-timing. 1

There is currently great interest in using fixed arrays of FPGAs for logic emulators, custom computing devices, and software accelerators. An important part of designing such a system is determining the proper routing topology to use to interconnect the FPGAs. This topology can have a great effect on the area and delay of the resulting system. Crossbar, Hierarchical Crossbar, and Mesh interconnection schemes have all been proposed for use in FPGA-based systems. In this paper, we examine Mesh interconnection schemes, and propose several constructs for more efficient topologies. These reduce interchip delays by more than 60% over the basic four-way Mesh.

Recent trends in the cost and performance of application-specific hardware relative to conventional processors discourage investing much time and energy in special-purpose architectures except for niche applications. These trends, however, may be reversed by the increasing complexity of computer architectures and the advent of configurable computing. Configurable computers have attracted considerable attention recently because they promise to deliver the performance of application-specific hardware along with the flexibility of general-purpose computers. In this paper, we discuss some of the forces driving configurable computing, and we argue that new configurable architectures are needed to realize the enormous potential of configurable computing. In particular, we believe that the commercial FPGAs currently used to construct configurable computers are too fine-grained to achieve good cost-performance on computationally-intensive applications that demand high-performance hardware. We then describe a new architecture called RaPiD (Reconfigurable Pipelined Datapaths), which is optimized for highly repetitive, computationally-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD that deliver very high performance for a wide range of applications. RaPiD achieves this using a coarse-grained reconfigurable architecture that mixes the appropriate amount of static configuration with dynamic control.

The goal of the RaPiD (Reconfigurable Pipelined Datapath) architecture is to provide high performance configurable computing for a range of computationally-intensive applications that demand special-purpose hardware. This is accomplished by mapping the computation into a deep pipeline using a configurable array of coarse-grained computational units. A key feature of RaPiD is the combination of static and dynamic control. While the underlying computational pipelines are configured statically, a limited amount of dynamic control is provided which greatly increases the range and capability of applications that can be mapped to RaPiD. This paper illustrates this mapping and configuration for several important applications including a FIR filter, 2-D DCT, motion estimation, and parametric curve generation; it also shows how static and dynamic control are used to perform complex computations.

This paper presents a new optimization technique called architectural retiming which is able to improve the performance of many latency-constrained circuits.Architectural retiming achieves this by increasing the number of registers on the latency-constrained path while preserving the functionality and latency of the circuit.This is done using the concept of a negative register, which can be implemented using precomputation and prediction.We use the name architectural retiming since it both reschedules operations in time and modi es the structure of the circuit to preserve its functionality.We illustrate the use of architectural retiming on two realistic examples and present performance improvement results for a number of sample circuits.

Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm that converges to a solution in which all signals are routed while achieving close to the optimal performance allowed by the placement. Routability is achieved by forcing signals to negotiate for a resource and thereby determine which signal needs the resource most. Delay is minimized by allowing the more critical signals a greater say in this negotiation. Because PathFinder requires only a directed graph to describe the architecture of routing resources, it adapts readily to a wide variety of FPGA architectures such as Triptych, Xilinx 3000 and mesh-connected arrays of FPGAs. The results of routing ISCAS benchmarks on the Triptych FPGA architecture show an average increase of only 4.5% in critical path delay over the optimum delay for a placement. Routes of ISCAS benchmarks on the Xilinx 3000 architecture show a greater completion rate than commercial tools, as well as 11% faster implementations.

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.

There is currently great interest in using fixed arrays of FPGAs for logic emulators, custom computing devices, and software accelerators. An important part of designing such a system is determining the proper routing topology to use to interconnect the FPGAs. This topology can have a great effect on the area and delay of the resulting system. Tree, bipartite graph, and mesh inter-connection schemes have all been proposed for use in FPGA-based systems. In this paper we examine mesh interconnection schemes, and propose several constructs for more efficient topologies. These reduce inter-chip delays by more than 60% over the basic 4-way Mesh.>

Using level-sensitive latches instead of edge-triggered registers for storage elements in a synchronous system can lead to faster and less expensive circuit implementations. These advantages derive from an increased flexibility in scheduling the computations to be performed. In edge-clocked circuits, the amount of time available for the computation between two registers is precisely the length of the clock cycle, while in level-clocked circuits computations can borrow time across latches, potentially reducing the amount of dead time not used for computation. In either type of circuit, maximizing performance requires locating the storage elements to spread the computation uniformly across a number of clock cycles. Retiming is the process of rearranging the storage elements in a circuit to reduce its cycle time or number of storage elements without changing its functionality. In this paper, we extend the retiming techniques developed by Leiserson, Rose, and Saxe (1983, 1991) for edge-clocked circuits to a general class of multi-phase, level-clocked circuits controlled using symmetric clock schedules. We first define correct timing for level-clocked circuits and describe the set of timing constraints that must be satisfied. We then present an efficient algorithm for generating and solving a set of retiming constraints at a particular clock period that results in a retimed circuit satisfying the timing constraints (if any such circuit exists). The minimum clock period for which there is a valid retiming can then be determined using a binary search.>

The problem of finding subcircuits in a larger circuit arises in many contexts in computer-aided design.This is a problem currently solved using ad hoc Fellowship.,, of CMOS circuit examples.

In spite of recent advances in circuit retiming theory, especially for circuits that use level-sensitive latches, automatic retiming tools see relatively little use in practice. We suggest that the reason for the poor results reported for retiming is that it has been applied too late in the design process when there is little flexibility for performance improvement. We give an example of using retiming early in the design process to achieve better performance while at the same time simplifying the design process itself. We extend the circuit model to include clock skew, latch propagation delay, setup and hold parameters which allow retiming to generate the fastest circuit subject to a given amount of clock stew, or generate the most robust circuit with respect to skew for a given clock frequency. We illustrate these techniques using a serial-parallel multiplier circuit and show that while edge-clocked circuits require a speed margin for clock skew, level-clocked circuits can be retimed to be inherently skew-tolerant.

WireLisp is a language that incorporates both procedural and graphic constructs for describing the structure of complex circuits. This combination provides both the clarity of a graphic representation and the expressiveness of a procedural description. A description is given of how this is done in a conceptually simple way be representing procedural information graphically. WireLisp is built on Lisp which allows the designer to extend the language with arbitrary functions. WireLisp can be used to generate a variety of different target output descriptions, and allows the incorporation of other kinds of descriptions such as behavioral and physical descriptions. WireLisp is implemented in T Lisp and has been used to describe complex (130000 transistor) VLSI chip design.>

Gemini is a program that is widely used to compare circuit layout against a specification. Extensions to Gemini that make it faster, enable it to isolate errors better, and extend its domain of application, are described. These improvements have been achieved by changes to the labeling algorithm, extensions to the local matching algorithm, better handling of symmetrical circuits, and the accommodation of series-connected transistors. GeminiII's algorithm is separated into global labeling and local matching phases. GeminiII dynamically switches between the two, depending on the amount of local structure contained in the circuit, taking advantage of the speed of the local matching algorithm when possible and relying on the power of the more general algorithm when the simple algorithm fails.>

Communication is a basic problem when using VLSI technology to implement large parallel circuits. Valuable chip area must be used to run wires connecting components on a chip and current packaging technology restricts the amount of communication that can cross chip boundaries. This paper presents a large parallel architecture for generating moves in chess and shows how it can be restructured to reduce communication and permit a straightforward VLSI implementation without any performance loss. The result is a move generator comprising 64 identical custom chips performing at a rate of 500,000 moves per second, performance that is comparable to the best existing move generator.