Deep neural network (DNN) training workloads are increasingly susceptible to hardware failures in datacenters. For example, Google experienced "mysterious, difficult to identify problems" in their TPU training systems due to hardware failures [7]. Although these particular problems were subsequently corrected through significant efforts, they have raised the urgency of addressing the growing challenges emerging from hardware failures impacting many DNN training workloads.

A summary of contributions made by significant papers from the first 25 years of the Field-Programmable Logic and Applications conference (FPL) is presented. The 27 papers chosen represent those which have most strongly influenced theory and practice in the field.

The list of significant papers from the first 25 years of the Field-Programmable Logic and Applications conference (FPL) is presented in this paper. These 27 papers represent those which have most strongly influenced theory and practice in the field.

This article consists of a collection of slides from the author's conference presentation on the special features, system design and architectures, processing capabilities, and targeted markets for Altera's Arria 10 family of processor products.

editorial Free Access Share on Guest Editorial: TRETS Special Edition on the 15th International Symposium on FPGAs Guest Editors: André DeHon View Profile , Mike Hutton View Profile Authors Info & Claims ACM Transactions on Reconfigurable Technology and SystemsVolume 1Issue 1Article No.: 2pp 1–3https://doi.org/10.1145/1331897.1341292Published:17 March 2008Publication History 0citation417DownloadsMetricsTotal Citations0Total Downloads417Last 12 Months14Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

Process variation and prerouting interconnect delay uncertainty affect timing and power for modern VLSI designs in nanometer technologies. This paper presents the first in-depth study on stochastic physical synthesis algorithms leveraging statistical static timing analysis (SSTA) with process variation and prerouting interconnect delay uncertainty for field-programmable gate arrays (FPGAs). Evaluated by SSTA using the placed and routed circuits, the stochastic clustering, placement, and routing reduce the mean delay by 5.0%, 4.0%, and 1.4%, respectively, and reduce the standard deviation of delay by 6.4%, 6.1%, and 1.4%, respectively for MCNC designs. The majority of improvements come from modeling interconnect delay uncertainty for clustering and from considering process variation for placement, while routing has less improvement on delay. In addition, we study the interaction between each individual design stage. When applying all stochastic algorithms concurrently, the mean delay and standard deviation are reduced by 6.2% and 7.5%, respectively. On the other hand, stochastic clustering with deterministic placement and routing is a good flow with little change to the entire flow, but the mean delay is reduced by 5.0%, the standard deviation is reduced by 6.4%, and the runtime is slightly reduced compared to the deterministic flow. Finally, while its improvement over timing is small, stochastic routing is able to reduce the total wire length by 4.5% and to reduce the overall runtime by 4.2% compared to deterministic routing.

No abstract available.

This paper discusses the need for new high-speed hardware architectures for future networks and in particular the need for high speed, high capacity shared buffer designs. An implementation of such a buffer using FPGA technology utilizing RLDRAM II is presented. The architecture that has been derived and implemented operated at 12.8Gbps and is scalable up to 20Gbps.

Structured ASICs have recently emerged as a mid-way between cell-based ASICs with high NRE costs and FPGAs with high unit costs. Though the structured ASIC fabric attacks mask and other fixed cost it does not solve verification, particularly physical verification issues with ASICs or logic errors missed by simulation which would require re-spins. These can be avoided by testing in-system with an FPGA and migrating the FPGA design to a closely coupled structured ASIC fabric. Here we describe a practical methodology for a fast, push-button, and thorough verification approach tying an FPGA prototype to a matching structured-ASIC implementation for cost-reduction. Our focus is the equivalence verification between the respective revisions of a design, including netlist, compiler settings, macro-block parameters, timing constraints, pin layout and resource count.

Modern FPGA chips contain multiple dedicated clocking networks, because nearly all real designs contain multiple clock domains. In this paper, we present an FPGA technology mapping algorithm targeting designs with multi-clock domains such as those containing multi-clocks, multi-cycle paths, and false paths. We use timing constraints to handle these unique clocking issues. We work on timing constraint graphs and process multiple arrival/required times for each node in the gate-level netlist. We also recognize and process constraint conflicts efficiently. Our algorithm produces a mapped circuit with the optimal mapping depth under timing constraints. To the best of our knowledge, this is the first FPGA mapping algorithm working with multi-clock domains. Experiments show that our algorithm is able to improve circuit performance by 16.8% on average after placement and routing for a set of benchmarks with multi-cycle paths, comparing to a previously published depth-optimal algorithm that does not consider multi-cycle paths.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt with in timing analysis, a large number of tags needs to be created and propagated, thus deteriorating efficiency. In this paper, weminimize the number of the tags through a biclique-covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags.With the produced tags, we remove the false path timing and guarantee to cover the nonfalse path timing. Since the minimum biclique covering of the general bipartite graph is NP complete [Indag. Math., vol. 39, p. 211, 1977], [Discrete Math., vol. 149, no. 1–3, p. 159, 1996], we use a minimal degree ordering approach to perform the biclique-covering minimization. The experimental results show significant reduction on the number of tags.

We propose a framework to unify the process of false paths and multi-cycle paths in static timing analysis (STA). We use subgraphs attached with timing constraints to represent false paths and multi-cycle paths. The complexity of the subgraph representation is reduced to improve efficiency. Finally, we present theorems to show that the unified framework produces correct timings. The experimental results demonstrate that the minimization is effective for both artificial and industry test cases.

Both custom IC and FPGA designs in the nanometer regime suffer from process variations. But different from custom ICs, FPGAs, programmability offers a unique design freedom to leverage process variation and improve circuit performance. We propose the following variation aware chip-wise placement flow in this paper. First, we obtain the variation map for each chip by synthesizing the test circuits for each chip as a preprocessing step before detailed placement. Then we use the trace-based method to estimate the performance gain achievable by chipwise placement. Such estimation provides a lower bound of the performance gain without detailed placement. Finally, if the gain is significant, a variation aware chipwise placement is used to place the circuits according to the variation map for each chip. Our experimental results show that, compared to the existing FPGA placement, variation aware chipwise placement improves circuit performance by up to 19.3% for the tested variation maps.

Modern FPGAs are not just able to trade off speed and area, but features, cost, static power, dynamic power, reliability and yield. This talk will discuss methodologies, metrics and success criteria for evaluation of FPGA architectural decisions. We will outline the current industrial approach to evaluating an architectural feature, and describe some of the challenges that are currently being faced for commercial architectures using some recent advances in FPGA architecture design as examples.

Process variation affecting timing and power is an important issue for modern integrated circuits in nanometer technologies. FPGAs are similar to ASICs in their susceptibility to these issues, but face unique challenges in that critical paths are unknown at test time. This paper presents the first in-depth study on applying statistical timing analysis with cross-chip and on-chip variations to speed-binning and guard-banding in FPGAs. Considering the uniqueness of reprogrammability in FPGAs, we quantify the effects of timing-model with guard-banding and speed-binning on statistical performance and timing yield. We also develop a new variation aware placement, which is the first statistical algorithm for FPGA layout and reduces yield loss by 3.4x with guard-banding and 25x with speed-binning for MCNC and QUIP designs.

In this paper, we propose a timing model reduction algorithm for hierarchical timing analysis based on a bicliquestar replacement technique. In hierarchical timing analysis, each functional block is characterized into an abstract timing model. The complexity of analysis is linear to the number of edges in the abstract timing model for timing propagation. We propose a biclique-star replacement technique to minimize the number of edges in the timing model. The experiments on industry test cases show that by allowing acceptable errors, the proposed algorithm can largely reduce the number of edges in the timing model.

Static timing analysis (STA) with multiple clock domains and complicated exception conditions is a complex practical problem that can dramatically increase compilation time, both for back-end analysis and during place and route. In FPGA placement, timing analysis with many constraints can dominate placement run-time.In this paper we introduce a simple binary edge-mask data structure on arcs in a timing netlist which allows for efficient timing analysis in the presence of many such constraints. The technique applies to either BFS or DFS-based timing analysis. Preliminary implementations on just the basic concept show a 59% decrease in STA run-time for multi-clock designs, indicating that significant benefit is to be gained from a complete implementation. On a set of heavily constrained designs this benefit improved to 80% run-time decrease.Further applications of the edge-mask concept are shown to efficiently deal with thru-x constraints, enumerating the k-longest paths in a timing graph, and partial/incremental timing analysis aimed at significant improvements in placement time.

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.

The design of FPGA architectures involves optimization of area, delay, power and routability across hundreds of architectural choices (e.g. LUT size, wire length, flexibility and circuit sizing). Since the difficulty of defining and predicting the design space only grows as we approach 65nm and 45nm processes it is necessary to have a better understanding of uncertainty in the architecture definition. In this paper we look at the sources of uncertainty, describe current unpublished methods for encapsulating error and uncertainty in experiments, and propose new methodologies involving ad-hoc, analytic and Monte Carlo simulation techniques to manage these risks in the future.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt in timing analysis, a large number of tags need to be created and propagated, and thus deteriorated the efficiency. In this paper, we minimize the number of the tags through a biclique covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags. The produced tags remove the false path timing and guarantee to cover the true path timings. Since the minimum biclique covering of the general bipartite graph is NP complete, we use a minimal degree ordering approach to perform the biclique covering minimization. The experimental results show significant reduction on the number of tags.

In this session, we will first present an overview of new challenges in commercial FPGA architecture design with an emphasis on the circuit and architecture issues for power at current and upcoming process nodes. Today’s 90nm FPGAs utilize techniques such as programmable shut-down of unused resources at the architectural level and multiple threshold voltages and gate-oxides at the circuit level. At 65nm and 45nm new techniques will need to target not only power mitigation but process variation in power and timing and their impact on yield and manufacturability.

As programmable logic grows more viable for implementing full design systems, performance has become a primary issue for programmable logic device architectures. This paper presents the high-level design of Dali, a PLD architecture specifically aimed at performance-driven applications. We will present significant portions of the background research that contributed to our architectural decisions, an overview of the core routing architecture and benchmarking experiments used to evaluate the prototype device.

The design of programmable logic architectures and supporting computer-aided design tools fundamentally requires both a good understanding of the combinatorial nature of netlist graphs and sufficient quantities of realistic examples to evaluate or benchmark the results. In this paper, the authors investigate these two issues. They introduce an abstract model for describing sequential circuits and a collection of statistical parameters for better understanding the nature of circuits. Based upon this model they introduce and formally define the signature of a circuit netlist and the signature equivalence of netlists. They give an algorithm (GEN) for generating sequential benchmark netlists, significantly expanding previous work (Hutton et al, 1998) which generated purely combinational circuits. By comparing synthetic circuits to existing benchmarks and random graphs they show that GEN circuits are significantly more realistic than random graphs. The authors further illustrate the viabilty of the methodology by applying GEN to a case study comparing two partitioning algorithms.

The development of new field-programmed, mask-programmed, and laser-programmed gate-array architectures is hampered by the lack of realistic test circuits that exercise both the architectures and their automatic placement and routing algorithms. In this paper, we present a method and a tool for generating parameterized and realistic synthetic circuits. To obtain the realism, we propose a set of graph-theoretic characteristics that describe a physical netlist, and have built a tool that can measure these characteristics on existing circuits. The generation tool uses the characteristics as constraints in the synthetic circuit generation. To validate the quality of the generated netlists, parameters that are not specified in the generation are compared with those of real circuits and with those of more "random" graphs.

Abstract—The design of programmable logic architectures and supporting computer-aided design tools fundamentally requires both a good understanding of the combinatorial nature of netlist graphs and sufficient quantities of realistic examples to evaluate or benchmark the results. In this paper, the authors investigate these two issues. They introduce an abstract model for describing sequential circuits and a collection of statistical parameters for better understanding the nature of circuits. Based upon this model they introduce and formally define the signature of a circuit netlist and the signature equivalence of netlists. They give an algorithm (GEN) for generating sequential benchmark netlists, significantly expanding previous work (Hutton et al., 1998) which generated purely combinational circuits. By comparing synthetic circuits to existing benchmarks and random graphs they show that GEN circuits are significantly more realistic than random graphs. The authors further illustrate the viabilty of the methodology by applying GEN to a case study comparing two partitioning algorithms. Index Terms—Benchmark, digital circuits, placement. I.

The development of new Field-Programmed, Mask-Programmed and Laser-Programmed Gate Array architectures is hampered by the lack of realistic test circuits that exercise both the architectures and their automatic placement and routing algorithms.In this paper, we present a method and a tool for generating parameterized and realistic random circuits.To obtain the realism, we propose a set of graph-theoretic characteristics that describe a physical netlist, and have built a tool that can measure these characteristics on existing circuits.The generation tool uses the characteristics as constraints in the random circuit generation.To validate the quality of the generated netlists, parameters that are not speci ed in the generation are c ompared with those of real circuits, and with those of \random" graphs.rameter which i s a c haracteristic of the circuit in question. Circuit Characterization Circuit Generation ValidationCharacteristics and Measured Parameters (n, nPI, nPO, delay, shape, edge-length, fanout dist'n) 2 Circuit Characterization This section describes some of the statistical and structural characteristics of circuits which w e h a v e identi ed.For the purposes of this paper we focus on combinational circuits only, and have used the MCNC benchmark circuits to form the

An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a nonalgorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. This paper presents an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. This result is made more significant in light of the recent proof by Garg and Tamassia that the problem is NP-complete for general digraphs. The algorithm decomposes the digraph into biconnected and triconnected components and defines conditions for merging the components into an upward plane drawing of the original digraph. To handle the triconnected components, we provide a linear algorithm to test whether a given plane drawing of a single-source digraph admits an upward plane drawing with the same faces and outer face, which also gives a simpler, algorithmic proof of Thomassen’s result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in $O(n^2 )$ time and $O(n)$ space (n being the number of vertices in the input digraph) and represents the first polynomial-time solution to the problem.