Deshanand Singh

This book makes powerful Field Programmable Gate Array (FPGA) and reconfigurable technology accessible to software engineers by covering different state-of-the-art high-level synthesis approaches (e.g., OpenCL and several C-to-gates compilers). It introduces FPGA technology, its programming model, and how various applications can be implemented on FPGAs without going through low-level hardware design phases.

FPGA logic density is roughly doubling at every process generation. Consequently, it is becoming increasingly challenging for FPGA CAD tools to keep up with the growing complexities of high-speed designs while keeping CAD run-times reasonable. In this paper, we present a novel incremental resynthesis tool called Line-Level Incremental reSynthesis (LLIS), integrated within an industrial tool suite, that addresses the problems of timing closure as well as CAD runtime (patent pending). We describe… Show more

FPGA logic density is roughly doubling at every process generation. Consequently, it is becoming increasingly challenging for FPGA CAD tools to keep up with the growing complexities of high-speed designs while keeping CAD run-times reasonable. In this paper, we present a novel incremental resynthesis tool called Line-Level Incremental reSynthesis (LLIS), integrated within an industrial tool suite, that addresses the problems of timing closure as well as CAD runtime (patent pending). We describe a general framework that can incrementally reuse results from a previous compile based on automatic differencing of HDL changes. We show that it is possible to reduce synthesis runtime by 6.5x for common HDL changes. As compared with complete resynthesis, we preserve known good timing solutions more than 82% of the time. This represents a 3X improvement vs. non-incremental techniques. Show less

Today's FPGAs have logic capacities that are steadily increasing. The FPGA is a large array of fine-grained programmable elements that can be configured in such a way to efficiently solve many complex problems. For many applications, FPGAs are a tremendously efficient computational fabric; however, the primary method of design entry for FPGAs is through Hardware Design Languages (HDLs) such as VHDL or Verilog. These languages model the FPGA at an extremely low level where the programmer is… Show more

Today's FPGAs have logic capacities that are steadily increasing. The FPGA is a large array of fine-grained programmable elements that can be configured in such a way to efficiently solve many complex problems. For many applications, FPGAs are a tremendously efficient computational fabric; however, the primary method of design entry for FPGAs is through Hardware Design Languages (HDLs) such as VHDL or Verilog. These languages model the FPGA at an extremely low level where the programmer is expected to understand cycle-accurate details of how data is moved and transformed through the FPGA. While this programming model is required to achieve the highest possible efficiency from FPGAs, it is akin to "assembly language" programming for processors. In this talk, we explore techniques that allow us to program FPGAs at a level of abstraction that is closer to traditional software-centric approaches. These techniques allow us to tradeoff some efficiency for added designer productivity. Our language of choice is OpenCL, which is an industry standard parallel language based on 'C.' OpenCL offers numerous compelling advantages that enable designers to harness the computational power of FPGAs and yet ease the programming burden to a significant extent. Show less

GPUs are becoming an increasingly attractive option for obtaining performance speedups for data-parallel applications. FPGA technology mapping is an algorithm that is heavily data parallel; however, it has many features that make it unattractive to implement on a GPU. The algorithm uses data in irregular ways since it is a graph-based algorithm. In addition, it makes heavy use of constructs like recursion which is not supported by GPU hardware. In this paper, we take a state-of-the-art FPGA… Show more

GPUs are becoming an increasingly attractive option for obtaining performance speedups for data-parallel applications. FPGA technology mapping is an algorithm that is heavily data parallel; however, it has many features that make it unattractive to implement on a GPU. The algorithm uses data in irregular ways since it is a graph-based algorithm. In addition, it makes heavy use of constructs like recursion which is not supported by GPU hardware. In this paper, we take a state-of-the-art FPGA technology mapping algorithm within Berkeley's ABC package and attempt to parallelize it on a GPU. We show that runtime gains of 3.1× are achievable while maintaining identical quality as demonstrated by running these netlists through Altera's Quartus II place-and-route tool. Show less

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… Show more

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 metastabilityrelated 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. Show less

This paper studies the difficulty of predicting interconnect delay in an industrial setting. Industrial circuits and two industrial FPGA architectures were used in the study. We show that there is a large amount of inherent randomness in a state-of-the-art FPGA placement algorithm. Thus, it is impossible to predict interconnect delay with a high degree of accuracy. Futhermore, we show that a simple timing model can be used to predict some aspects of interconnect timing with just as much… Show more

This paper studies the difficulty of predicting interconnect delay in an industrial setting. Industrial circuits and two industrial FPGA architectures were used in the study. We show that there is a large amount of inherent randomness in a state-of-the-art FPGA placement algorithm. Thus, it is impossible to predict interconnect delay with a high degree of accuracy. Futhermore, we show that a simple timing model can be used to predict some aspects of interconnect timing with just as much accuracy as predictions obtained by running the placement tool itself. Next, we present a metric for predicting the accuracy of our interconnect delay model and show how this metric can be used to improve a timing driven physical synthesis flow. Finally, we examine the benefits of using the simple timing model in a timing driven physical synthesis flow, and attempt to establish an upper bound on these possible gains, given the difficulty of interconnect delay prediction. Show less

This work presents a Field-Programmable Gate Array (FPGA) logic synthesis technique based upon Boolean Satisfiability (SAT). This work shows how to map any Boolean function into an arbitrary PLB architecture without any custom decomposition techniques. The authors illustrate several useful applications of this technique by showing how this technique can be used for architecture evaluation and area optimization. When evaluating FPGA architecture, the authors focus on the basic building block of… Show more

This work presents a Field-Programmable Gate Array (FPGA) logic synthesis technique based upon Boolean Satisfiability (SAT). This work shows how to map any Boolean function into an arbitrary PLB architecture without any custom decomposition techniques. The authors illustrate several useful applications of this technique by showing how this technique can be used for architecture evaluation and area optimization. When evaluating FPGA architecture, the authors focus on the basic building block of the FPGA which they refer as a programmable logic block (PLB). In order to illustrate the flexibility of their evaluation framework, several unrelated PLB architectures are evaluated in an automated fashion. Furthermore, the authors show that using their technique is able to reduce FPGA resource usage by 27% on average in common subcircuits found in digital design. Show less

This paper presents an overview of an industrial physical synthesis CAD flow for FPGAs. The flow provides a performance speedup of 10%­15% for most circuits, and a significant number of circuits show a speedup of 20%­180%. We describe the algorithms used to achieve this result including: incremental retiming, BDD-based resynthesis, local rewiring, and logic replication. The effectiveness of these operations depends on the ability to accurately determine which portions of logic are timing… Show more

This paper presents an overview of an industrial physical synthesis CAD flow for FPGAs. The flow provides a performance speedup of 10%­15% for most circuits, and a significant number of circuits show a speedup of 20%­180%. We describe the algorithms used to achieve this result including: incremental retiming, BDD-based resynthesis, local rewiring, and logic replication. The effectiveness of these operations depends on the ability to accurately determine which portions of logic are timing critical at a stage of the CAD flow where there is still freedom to perform logic restructuring. We show how this problem can be effectively solved by inserting prediction and restrurcturing operations at multiple points of the FPGA CAD flow. Show less