This paper introduces a method for delay approximation in timing analysis for spatial variation where the parameters representing the sources of variation are based on a convolution of random variation with a basis function. This results in delay models that need only include nine nonzero random variables for each edge in a typical spatial correlation model, less than previous work. As a result the symbolic representation of all potentially critical delays can be carried through the entire timing analysis without the need for approximate maximum function of statistical delays, producing a conservative but accurate upper bound on timing to meet a specified yield target. The algorithm has been applied to a set of field-programmable gate array designs and used to show that it is computationally efficient even with large designs. Further, because the timing is pessimistic but accurate, it removes the need for guardbanding the timing analysis compared to previous approaches. The representation of all potentially critical paths in a symbolic form also enables fast Monte-Carlo (MC) algorithms to supplement the deterministic ones. We show a combined deterministic and MC algorithm that is on average within 0.35% of ideal, and has a 10-6probability of an optimistic result.

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.

This paper describes architectural enhancements in the Altera Stratix? 10 HyperFlex? FPGA architecture, fabricated in the Intel 14nm FinFET process. Stratix 10 includes ubiquitous flip-flops in the routing to enable a high degree of pipelining. In contrast to the earlier architectural exploration of pipelining in pass-transistor based architectures, the direct drive routing fabric in Stratix-style FPGAs enables an extremely low-cost pipeline register. The presence of ubiquitous flip-flops simplifies circuit retiming and improves performance. The availability of predictable retiming affects all stages of the cluster, place and route flow. Ubiquitous flip-flops require a low-cost clock network with sufficient flexibility to enable pipelining of dozens of clock domains. Different cost/performance tradeoffs in a pipelined fabric and use of a 14nm process, lead to other modifications to the routing fabric and the logic element. User modification of the design enables even higher performance, averaging 2.3X faster in a small set of designs.

This paper describes architectural enhancements in the Altera Stratix-V" FPGA architecture, built on a 28nm TSMC process, together with the data supporting those choices. Among the key features are time borrowing flip-flops, a doubling of the number of flip-flops per LUT compared to previous Stratix architectures, a simplified embedded 20kb dual-port RAM block, and error correction that can correct up to 8 adjacent errors. Arithmetic performance is significantly improved using a fast adder with two levels of multi-bit skip. We also describe how the routing architecture and layout is optimized for the 28nm process to take advantage of a wider range of wire thicknesses offered on the different layers, and improvements in performance and routability are obtained without dramatic changes to the repeated floorplan of the logic plus routing fabric.

Metastability is a phenomenon that can cause system failures in digital circuits. It may occur whenever signals are being transmitted across asynchronous or unrelated clock domains. The impact of metastability is increasing as process geometries shrink and supply voltages drop faster than transistor Vts. FPGA technologies are significantly affected since leading edge FPGAs are amongst the first devices to adopt the most recent process nodes. In this paper, we present a comprehensive suite of techniques for modeling, characterizing and optimizing metastability effects in FPGAs. We first discuss a theoretical model of metastability, and verify the predictions using both circuit level simulations and board measurements. Next we show how designers have traditionally dealt with metastability problems and contrast that with the automatic CAD algorithms described in this paper that both analyze and optimize metastability-related issues. Through our detailed experimental results, we show that we can improve the metastability characteristics of a large suite of industrial benchmarks by an average of 268,000 times with our optimization techniques.

This paper describes architectural enhancements in the Stratix-III" and Stratix-IV" FPGA architectures. These architectures feature programmable power management, which allows the power and performance of logic and routing to be varied to minimize total power without any performance loss. This paper describes the technique used for programmable power management, and describes the experimental evaluation that led to the choice of regions in these architectures. The memory architecture is also explored by adding heterogeneous memory mapping to the FPGA Modeling Toolkit, and used to explore LUT based memory structures. The ALM structure provides more inputs than required for a simple 6 LUT, which can be used with simple modifications to efficiently support simple dual-ported LUT based RAM. Replacing the Stratix-II" small memory blocks with LUT RAM and changing the size of other two memories is shown to reduce overall core area across a set of benchmark designs.

This paper describes the Altera Stratix II™ logic and routing architecture. This architecture features a novel adaptive logic module (ALM) that is based on a 6-LUT, but can be partitioned into two smaller LUTs to efficiently implement circuits containing a range of LUT sizes that arises in conventional synthesis flows. This provides a performance increase of 15% in the Stratix II architecture while reducing area by 2%. The ALM also includes a more powerful arithmetic structure that can perform two bits of arithmetic per ALM, and perform a sum of up to three inputs. The routing fabric adds a new set of fast inputs to the routing multiplexers for another 3% improvement in performance, while other improvements in routing efficiency cause another 6% reduction in area. These changes in combination with other circuit and architecture changes in Stratix II contribute 27% of an overall 51% performance improvement (including architecture and process improvement). The architecture changes reduce area by 10% in the same process, and by 50% after including process migration.

This paper describes the Altera Stratix logic and routing architecture. The primary goals of the architecture were to achieve high performance and logic density. We give an overview of the entire device, and then focus on the logic and routing architecture. The Stratix logic architecture is based on a cluster of ten 4-input LUTs and its routing consists of staggered routing lines. We describe the development of the routing architecture, including its directional bias, its direct-drive routing which reduces both area and delay. The logic array block and logic cell design is also described, and new routing structures with in the logic array block, and logic element features are described.

This paper examines circuit design of buffered routing switches in symmetrical, island-style FPGAs. The effects of switch size, tile length, level-restoring, and slow input slew rates are examined. Two new fanin-based switch designs are used to eliminate nearly all of the increase in delay that arises from fanout with a previous switch design. Alternating between buffers and pass transistors is shown to improve connection delay without fanout by 25%. To take advantage of this, we propose schemes to replace some buffers with pass transistors to simultaneously reduce area and delay. Routing a suite of MCNC benchmark circuits shows that 14% in area-delay, or 7% in delay can be saved using the new switch schemes. Alternatively, approximately 13% in area can be saved with no degradation to delay.

Large circuits, whether they are arithmetic, digital signal processing, switching, or processors, typically contain a greater portion of highly regular datapath logic. Datapath synthesis algorithms preserve these regular structures, so they can be exploited by packing, placement, and routing tools for speed or density. Typical datapath synthesis algorithms, however, sacrifice area to gain regularity. Current algorithms can have as much as 30% to 40% area inflation when compared with traditional flat synthesis algorithms. This paper describes a datapath synthesis algorithm with very low area overhead, which is an enhancement to the module compaction algorithm. We propose two word-level optimizations - multiplexer tree collapsing and operation reordering. They reduce the area inflation to 3%-8% as compared with flat synthesis. Our synthesis results also retain significant amount of regularity from the original designs.

In FPGAs, the internal connections in a cluster of lookup tables (LUTs) are often fully-connected like a full crossbar. Such a high degree of connectivity makes routing easier, but has significant area overhead. This paper explores the use of sparse crossbars as a switch matrix inside the clusters between the cluster inputs and the LUT inputs. We have reduced the switch densities inside these matrices by 50% or more and saved from 10 to 18% in area with no degradation to critical-path delay. To compensate for the loss of routability, increased compute time and spare cluster inputs are required. Further investigation may yield modest area and delay reductions.

Design of FCCMs is an expensive and time consuming process, requiring a specialized software and hardware design for each application. A new class of architecture and compiler for customized computers called PECompiler that can automatically generate both hardware and software for field-programmable compute accelerators was recently introduced. This paper presents the parameterized compute accelerator and example applications that have been compiled for it. A generic very long instruction word (VLIW) instruction set is defined for the proposed compute accelerator architecture. Hardware accelerators are designed and implemented for two application programs on the TM-2 based system. It is demonstrated that for these two application programs, the hardware accelerators can provide significant performance improvement over a general-purpose CPU.

A method for evaluating and constructing sparse crossbars which are both area efficient and highly routable is presented. The evaluation method uses a network flow algorithm to accurately compute the percentage of random test vectors that can be routed. The construction method attempts to maximize the spread of the switch locations, such that any given subset of input wires can connect to as many output wires as possible. Based on Hall's Theorem, we argue that this increases the likelihood of routing.

Procedural textures can be effectively used to enhance the visual realism of computer rendered images. Procedural tex-tures can provide higher realism for 3-D objects than tradi-tional hardware texture mapping methods which use mem-ory to store 2-D texture images. This paper proposes a new method of hardware texture mapping in which texture im-ages are synthesized using FPGAs. This method is very efficient for texture mapping procedural textures of more than two input variables. By synthesizing these textures on the fly, the large amount of memory required to store their multidimensional texture images is eliminated, making tex-ture mapping of 3-D textures and parameterized textures feasible in hardware. This paper shows that using FPGAs, procedural textures can be synthesized at high speed, with a small hardware cost. Data on the performance and the hardware cost of synthesizing procedural textures in FP-GAS are presented. This paper also presents, the FPGA implementations of two Perlin noise based 3-D procedural textures.

This paper describes the Transmogrifier-2 (TM-2), a second-generation multifield programmable gate array (FPGA) rapid-prototyping system. The largest version of the system will comprise 16 boards that each contain two Altera 10K50 FPGA's, four I-Cube interconnect chips, and up to 8 Mbytes of memory. The inter-FPGA routing architecture of the TM-2 uses a novel interconnect structure, a nonuniform partial crossbar, that provides a constant delay between any two FPGA's in the system. The TM-2 architecture is modular and scalable, meaning that systems of various sizes can be constructed from copies of the same board, while maintaining routability and the constant delay feature. Other features include a system-level programmable clock that allows single-cycle access to off-chip memory, and programmable clock waveforms with edge resolution of 10 ns. The first Transmogrifier-2 boards have been manufactured and are functional. They have recently been used successfully in some simple graphics acceleration applications.

This paper describes a compiler that generates both hardware and controlling software for field-programmable compute accelerators. By analyzing a source program together with part of its input, the compiler generates VHDL descriptions of functional units that are mapped on a set of FPGA chips and an optimized sequence of control constructions that run on the customized machine. The primary technique employed in the compiler is partial evaluation, which is used to transform an application program together with part of its input into an optimized program. Further phases in the compiler identify pieces of the program that can be realized in hardware and schedule computations to execute on the resulting hardware. Finally, a set of specialized functional units generated by the compiler for a timing simulation program is used to demonstrate the approach.

This paper describes the Transmogrifier-2, a second generation multi-FPGA system. The largest version of the system will comprise 16 boards that each contain two Altera 10K50 FPGAs, four I-cube interconnect chips, and up to 8 Mbytes of memory. The inter-FPGA routing architecture of the TM-2 uses a novel interconnect structure, a non-uniform partial crossbar, that provides a constant delay between any two FPGAs in the system. The TM-2 architecture is modular and scalable, meaning that various sized systems can be constructed from the same board, while maintaining routability and the constant delay feature. Other features include a system-level programmable clock that allows single-cycle access to off-chip memory, and programmable clock waveforms with resolution to 10ns. The first Transmogrifier-2 boards have been manufactured and are functional. They have recently been used successfully in some simple graphics acceleration applications.

No abstract available.

This paper evaluates an architecture that implements a hierarchical routing structure for FPGAs, called a hierarchical FPGA (HFPGA). A set of new tools has been used to place and route several circuits on this architecture, with the goal of comparing the cost of HFPGAs to conventional symmetrical FPGAs. The results show that HFPGAs can implement circuits with fewer routing switches, and fewer switches in total, compared to symmetrical FGPAs, although they have the potential disadvantage that they may require more logic blocks due to coarser granularity.>

This paper describes a new method for polynomial interpolation in hardware, with advantages demonstrated by its application to an accurate logarithmic number system (LNS) arithmetic unit. The use of an interleaved memory reduces storage requirements by allowing each stored function value to be used in interpolation across several segments. This strategy can be shown to always use fewer words of memory than an optimized polynomial with stored polynomial coefficients. Interleaved memory function interpolators are then applied to the specific goal of an accurate logarithmic number system arithmetic unit. Many accuracy requirements for the LNS arithmetic unit are possible. Although a round to nearest would be desirable, it cannot be easily achieved. The goal suggested is to insure that the worst case LNS relative error is smaller than the worst case floating point (FP) relative error. Using the interleaved memory interpolator, the detailed design of an LNS arithmetic unit is performed using a second order polynomial interpolator including approximately 91K bits of ROM. This arithmetic unit has better accuracy and less complexity than previous LNS units.>

A logarithmic number system (LNS) arithmetic unit using a new method for polynomial interpolation in hardware is described. The use of an interleaved memory reduces storage requirements by allowing each stored function value to be used in interpolation across several segments. This strategy always uses fewer words of memory than an optimized polynomial with stored polynomial coefficients. Many accuracy requirements for the LNS arithmetic unit are possible, but a round to nearest cannot be easily achieved. The goal suggested here is to ensure that the worst case LNS relative error is smaller than the worst case FP relative error. Using the interleaved memory interpolator, the detailed design of an LNS arithmetic unit is performed using a second-order polynomial interpolator including approximately 91K bits of ROM.>

Describes a special-purpose application accelerator using field-programmable gate arrays to accelerate a range of applications. The accelerator is designed to support applications by allowing the user to implement a processor with an instruction set designed for the specific application being accelerated, using specialized instructions to implement critical fragments of the application. A compiled-code software organization is used to reduce overhead operations. A prototype has been built, and the first application to be ported to it, logic simulation, is underway.>

Describes a new logic state model for gate level simulation based upon a powerset representation of the possible drive states at the output of a logic gate. Efficient implementation techniques for this model in a compiled-code logic simulator are presented, with the results that most complicated operations can be optimized into simple table lookups. Algorithmic issues in a multiple-strength multiple-delay logic simulator are discussed. Implementation results show that for typical circuits, compiled-code implementations of multiple-strength unit-delay logic simulation and multiple-strength multiple-delay logic simulation are slightly lower than three-state unit-delay simulation, and achieve speedups of 5 to 14 times compared to interpretive versions of the same algorithms.>

Describes the application of compiled-code techniques to the design of a hardware accelerator for circuit simulation, offering a speedup by a factor of up to 4400 compared with a software circuit simulator running on a Sun-3/60 workstation. The preprocessing algorithms are designed for high speed, so overall simulation time is improved by a factor of up to 560. Compiled-code hardware accelerators offer several advantages. The hardware is simpler than fully hard-wired accelerators. The simplicity of the hardware makes it possible to track advancing implementation technology and to maintain the performance advantage as technology improves. The simulation algorithm is implemented in software, making it possible to implement and maintain multiple algorithms without hardware modifications. The hardware can be used efficiently, since compiled-code techniques can eliminate or statically perform operations that would be repeatedly performed in other hard-wired implementations.>

Logic simulation techniques that reduce both preprocessing time and execution time of unit delay logic simulation are described. Compiled code implementation techniques using a threaded code organization are applied to the event-driven logic simulation algorithm. Simulation speed is increased by a factor of tip to 10 by this technique compared to conventional event-driven simulation. The technique is then extended to hierarchical simulation, in which a fan-out procedure and simulation procedure are generated for each unique module. Hierarchical simulation reduces preprocessing time and allows the recompilation of only those modules that are modified. The simulator uses a portable machine model in which an architecture file describes the target machine. The simulator can be quickly ported to new machines by defining the architecture, while still obtaining high performance.>

An architecture is described for performing addition and subtraction of numbers in the logarithmic number system using small lookup tables. Previous implementations require approximately 4*2/sup F/ words for F bits of precision in the fraction. The author shows how to reduce the size of the lookup table to fewer than (18+F)*2/sup F/2/ words. The key to this is the use of a linear approximation of the nonlinear functions stored in the lookup tables. The functions involved are highly nonlinear in some regions, so variable size regions are used for the approximation. The replacement of the F exponential dependence on the number of words by F/2 allows roughly 50% more bits of fractional precision to be obtained for a given amount of ROM. The architecture is mathematically analyzed, yielding explicit expressions for all design parameters. The approach is illustrated with an example logarithmic addition and subtraction unit using 32-b words with 30-b exponents containing 22 fractional bits. A factor of 118 reduction in table size compared to previous techniques is achieved for this example.>

The application of 2/sup N/ trees to device model approximation is described. The domain of the device model function is partitioned using a 2/sup N/ tree, with smaller partitions where the function is more nonlinear. The function value associated with each corner of each partition is precomputed, and the function is evaluated by a given point by interpolation over the smallest partition that includes that point. This technique has the advantage that highly nonlinear functions can be modeled with modest space and time requirements. Exponential functions, such as the subthreshold behavior of FETs, can be accurately modeled. Accuracy levels of 1% are possible down to currents of 10/sup -11/ A. Table generation time is small; it is only a few minutes for a MOSFET model including subthreshold effects. This algorithm is especially suited for application to a hardware-accelerated device model evaluator. The design of a prototype that is capable of performing a device model evaluation of a SPICE level-2 model including subthreshold effects in 1 mu s is described. Less detailed models, such as timing simulator models, can be evaluated in as little as 0.2 mu s.>

A description is given of the architecture of an integrated processor that is capable of performing addition and subtraction of 30-b numbers with 20 fractional bits in the logarithmic number system. Previous techniques would require 70 Mb of ROM to implement this processor, which is not feasible for a single-chip implementation. The techniques presented here use a factor of 275 less memory. The key to this is the use of a linear approximation of the nonlinear functions stored in the lookup tables. The functions involved are highly nonlinear in some regions, so variable size regions are used for the approximation. The use of linear approximation alone would still require over 565 kb of ROM. Further compression is obtained by using linear approximation with differential coding of each table. The compression is chosen to minimize ROM size and obtains a further reduction of 55%. A total of 260 kb of ROM is required to implement the processor.>

A logic simulator is described that includes incremental preprocessing and reduced execution time. The simulator uses compiled code techniques with an event-driven algorithm. Each wire is compiled into a routine that performs fanout processing for that wire, and each gate is compiled into a routine that simulates that gate. At simulation time, the addresses of routines for active nodes and active gates are dynamically compiled into a threaded code sequence for simulating the active parts of the circuits. Gate-level simulation using C code output is up to 7 times faster, using as few as 40 machine instructions per gate event, while machine code would permit 20 instructions per gate event. This technique is then extended to hierarchical simulation, in which a fanout procedure and a simulation procedure are generated for each unique subcircuit type. Hierarchical simulation reduces preprocessing time by allowing incremental recompilation, in which only modified subcircuits are recompiled. The performance improvement is smaller due to the overhead of passing logic values and activation information between subcircuits, but a speed increase of 2 to 4 is realized.>

Designs are presented of two hardware engines for timing simulation. Both use the forward Euler integration algorithm to solve the differential equations that model the circuit. The simplicity of this algorithm compensates for the small time-step required. By structuring the algorithm to reduce data dependencies and maximize functional parallelism, a pipelined implementation is used. The use of a compact data representation and static integration stability checks results in a simple, yet fast, processor. The first engine provides a uniprocessor implementation that explores the feasibility of this approach to timing simulation. The second engine is an enhancement of the first. It uses a multiprocessor structure with a high-bandwidth interconnection network to support parallel simulation. Circuit inactivity is also used in a selective trace algorithm. The speed of this accelerator is high, allowing the simulation of circuits with over 100000 transistors in under one second per simulated clock cycle.>

A processor for the Smalltalk-80↑ programming language is described. This machine is implemented using a standard bit slice ALU and sequencer, TTL MSI, and NMOS LSI RAMS. It executes an instruction set similar to the Smalltalk-80 virtual machine instruction set. The data paths of the machine are optimized for rapid Smalltalk-80 execution by the inclusion of a context cache, tag checking, and a hardware method cache. Each context is only partly initialized when created, and has no memory allocated for it until a possibly non-LIFO reference to it is created. The machine is microprogrammed, and uses a simple next micro-address prediction strategy to obtain most of the performance of pipelining without the attendant complexity. The machine can execute simple instructions at over 7M bytecodes per second and has a predicted average throughput of 1.9M bytecodes per second.