Pipelining is an important technique in high-level synthesis, which overlaps the execution of successive loop iterations or threads to achieve high throughput for loop/function kernels. Since existing pipelining techniques typically enforce in-order thread execution, a variable-latency operation in one thread would block all subsequent threads, resulting in considerable performance degradation. In this paper, we propose a multithreaded pipelining approach that enables context switching to allow out-of-order thread execution for data-parallel kernels. To ensure that the synthesized pipeline is complexity effective, we further propose efficient scheduling algorithms for minimizing the hardware overhead associated with context management. Experimental results show that our proposed techniques can significantly improve the effective pipeline throughput over conventional approaches while conserving hardware resources.

Modulo scheduling is a popular technique to enable pipelined execution of successive loop iterations for performance improvement. While a variety of modulo scheduling algorithms exist for software pipelining, they are not amenable to many complex design constraints and optimization goals that arise in the hardware synthesis context. In this paper we describe a modulo scheduling framework based on the formulation of system of difference constraints (SDC). Our framework can systematically model a rich set of performance constraints that are specific to the hardware design. The scheduler also exploits the unique mathematical properties of SDC to carry out efficient global optimization and fast incremental update on the constraint system to minimize the resource usage of the synthesized pipeline. Experiments demonstrate that our proposed technique provides efficient solutions for a set of real-life applications and compares favorably against a widely used lifetime-sensitive modulo scheduling algorithm.

Vectorization has been commonly employed in modern processors. In this work we identify the opportunities to explore customized vector instructions and build an automatic compilation flow to efficiently identify those instructions. A composable vector unit (CVU) is proposed to support a large number of customized vector instructions with small area overhead. The results show that our approach achieves an average 1.41X speedup over the state-of-art vector ISA. We also observe a large area gain (around 11.6X) over the dedicated ASIC-based design.

In this work we address the problem of managing interconnect timing in high-level synthesis by generating a layout-friendly microarchitecture. A metric called spreading score is proposed to evaluate the layout-friendliness of microarchitectural netlist structures. For a piece of connected netlist, spreading score measures how far the components can be spread from each other with bounded length for every wire. The intuition is that components in a layout-friendly netlist (e.g., a mesh) can spread over the layout region without introducing long interconnects. We propose a semidefinite programming relaxation to allow efficient estimation of spreading score, and use it in a high-level synthesis tool. On a number of test cases, a normalized spreading score shows a stronger bias in favor of interconnect structures that have better timing after layout, compared to the widely used metric of total multiplexer inputs. We also justify our metric and motivate further study by relating spreading score to other metrics and problems for layout-friendly synthesis.

The recent development of non-volatile memory (NVM), such as spin-torque transfer magnetoresistive RAM (STT-RAM) and phase-change RAM (PRAM), with the advantage of low leakage and high density, provides an energy-efficient alternative to traditional SRAM in cache systems. We propose a novel reconfigurable hybrid cache architecture (RHC), in which NVM is incorporated in the last-level cache together with SRAM. RHC can be reconfigured by powering on/off SRAM/NVM arrays in a way-based manner. In this work, we discuss both the architecture and circuit design issues for RHC. Furthermore, we provide hardware-based mechanisms to dynamically reconfigure RHC on-the-fly based on the cache demand. Experimental results on a wide range of benchmarks show that the proposed RHC achieves an average 63%, 48% and 25% energy saving over non-reconfigurable SRAM-based cache, non-reconfigurable hybrid cache, and reconfigurable SRAM-based cache, while maintaining the system performance (at most 4% performance overhead).

Streaming processing is widely adopted in many data-intensive applications in various domains. FPGAs are commonly used to realize these applications since they can exploit inherent data parallelism and pipelining in the applications to achieve a better performance. In this paper we investigate the design space exploration problem (DSE) when mapping streaming applications onto FPGAs. Previous works narrowly focus on using techniques like replication or module selection to meet the throughput target. We propose to combine these two techniques together to guide the design space exploration. A formal formulation and solution to this combined problem is presented in this paper. Our objective is to optimize the total area cost subject to the throughput constraint. In particular, we are able to handle the feedback loops in the streaming programs, which, to the best of our knowledge, has never been discussed in previous work. Our methodology is evaluated with high-level synthesis tools, and we demonstrate our workflow on a set of benchmarks that vary from module kernel design such as FFT to large designs such as an MPEG-4 decoder.

There are two prominent problems with technology scaling: increasing design complexity and more challenges with interconnect design, including routability. High-level synthesis has been proposed to solve the complexity problem by raising the abstraction level. In this paper, we share our vision that high-level synthesis can potentially help the routability problem as well. We show that many interconnect problems that occur in layout can be avoided or mitigated by adopting a layout-friendly RTL architecture generated from high-level synthesis. We also evaluate some structural metrics that can be used to estimate the routability impact of design decisions in high-level synthesis. Experimental results have demonstrated correlations between the metrics and the routability of the resulting design.

Escalating system-on-chip design complexity is pushing the design community to raise the level of abstraction beyond register transfer level. Despite the unsuccessful adoptions of early generations of commercial high-level synthesis (HLS) systems, we believe that the tipping point for transitioning to HLS msystem-on-chip design complexityethodology is happening now, especially for field-programmable gate array (FPGA) designs. The latest generation of HLS tools has made significant progress in providing wide language coverage and robust compilation technology, platform-based modeling, advancement in core HLS algorithms, and a domain-specific approach. In this paper, we use AutoESL's AutoPilot HLS tool coupled with domain-specific system-level implementation platforms developed by Xilinx as an example to demonstrate the effectiveness of state-of-art C-to-FPGA synthesis solutions targeting multiple application domains. Complex industrial designs targeting Xilinx FPGAs are also presented as case studies, including comparison of HLS solutions versus optimized manual designs. In particular, the experiment on a sphere decoder shows that the HLS solution can achieve an 11-31% reduction in FPGA resource usage with improved design productivity compared to hand-coded design.

Memory bottleneck has become a limiting factor in satisfying the explosive demands on performance and cost in modern embedded system design. Selected computation kernels for acceleration are usually captured by nest loops, which are optimized by state-of-the-art techniques like loop tiling and loop pipelining. However, memory bandwidth bottlenecks prevent designs from reaching optimal throughput with respect to available parallelism. In this paper we present an automatic memory partitioning technique which can efficiently improve throughput and reduce energy consumption of pipelined loop kernels for given throughput constraints and platform requirements. Also, our proposed algorithm can handle general array access beyond affine array references. Our partition scheme consists of two steps. The first step considers cycle accurate scheduling information to meet the hard constraints on memory bandwidth requirements specifically for synchronized hardware designs. An ILP formulation is proposed to solve the memory partitioning and scheduling problem optimally for small designs, followed by a heuristic algorithm which is more scalable and equally effective for solving large scale problems. Experimental results show an average 6× throughput improvement on a set of real-world designs with moderate area increase (about 45% on average), given that less resource sharing opportunities exist with higher throughput in optimized designs. The second step further partitions the memory banks for reducing the dynamic power consumption of the final design. In contrast to previous approaches, our technique can statically compute memory access frequencies in polynomial time with little or no profiling. Experimental results show about 30% power reduction on the same set of benchmarks.

Reducing resource usage is one of the most important optimization objectives in behavioral synthesis due to its direct impact on power, performance and cost. The datapath in a typical design is composed of different kinds of components, including functional units, registers and multiplexers. To optimize the overall resource usage, a behavioral synthesis tool should consider all kinds of components at the same time. However, most previous work on behavioral synthesis has the limitations of (i) not being able to consider all kinds of resources globally, and/or (ii) separating the synthesis process into a sequence of optimization steps without a consistent optimization objective. In this paper we present a behavioral synthesis flow in which all types of components in the datapath are modeled and optimized consistently. The key idea is to feed to the scheduler the intentions for sharing functional units and registers in favor of the global optimization goal (such as total area), so that the scheduler could generate a schedule that makes the sharing intentions feasible. Experiments show that compared to the solution of minimizing functional unit requirements in scheduling and using the least number of functional units and registers in binding, our solution achieves a 24% reduction in total area; compared to the online tool provided by c-to-verilog.com, our solution achieves a 30% reduction on average.

Monte Carlo based SSTA serves as the golden standard against alternative SSTA algorithms, but it is seldom used in practice due to its high computation time. In this paper, we accelerate Monte Carlo based SSTA using the FPGA platform. A simple dataflow pipeline technique will not work well due to the excessive usage of FPGA logic slices. We leverage the recently proposed pattern matching method to identify common circuit structures, and further use a mathematical programming based formulation to explore the trade-off between performance and logic slices consumption. The proposed design provides two orders of magnitude speedup compared to the CPU-based implementation.

Many techniques for power reduction in advanced RTL synthesis tools rely explicitly or implicitly on observability don’t-care conditions. In this article we propose a systematic approach to maximize the effectiveness of these techniques by generating power-friendly RTL descriptions in behavioral synthesis. This is done using operation gating , that is, explicitly adding a predicate to an operation based on its observability condition, so that the operation, once identified as unobservable at runtime, can be avoided using RTL power optimization techniques such as clock gating. We first introduce the concept of behavior-level observability and its approximations in the context of behavioral synthesis. We then propose an efficient procedure to compute an approximated behavior-level observability of every operation in a dataflow graph. Unlike previous techniques which work at the bit level in Boolean networks, our method is able to perform analysis at the word level, and thus avoids most computation effort with a reasonable approximation. Our algorithm exploits the observability-masking nature of some Boolean operations, as well as the select operation, and allows certain forms of other knowledge to be considered for stronger observability conditions. The approximation is proved exact for (acyclic) dataflow graphs when non-Boolean operations other than select are treated as black boxes. The behavior-level observability condition obtained by our analysis can be used to guide the operation scheduler to optimize the efficiency of operation gating. In a set of experiments on real-world designs, our method achieves an average of 33.9% reduction in total power; it outperforms a previous method by 17.1% on average and gives close-to-optimal solutions on several designs. To the best of our knowledge, this is the first time behavior-level observability analysis and optimization are performed during behavioral synthesis in a systematic manner. We believe that our idea can be applied to compiler transformations in general.

Precision analysis and optimization is very important when transforming a floating-point algorithm into fixed-point hardware implementations. The core analysis techniques are either based on dynamic analysis or static analysis. We believe in static error analysis, as it is the only technique that can guarantee the desired worst-case accuracy. In this paper we study various underlying arithmetic candidates that can be used in static error analysis and compare their computed sensitivities. The approaches studied include Affine Arithmetic(AA), General Interval Arithmetic (GIA) and Automatic Differentiation (Symbolic Arithmetic). Our study shows that symbolic method is preferred for expressions with higher order cancellation. For programs without strong cancellation, any method works fairly well and GIA slightly outperforms others. We also study the impact of program transformations on these arithmetics.

This paper revisits the classical bitwidth optimization problem for fixed-point designs. Our approach also starts from static analysis (range analysis and precision analysis) techniques. We first point out that AA-based precision analysis, which is widely used in many previous works, are not correctly applied for some corner cases. We propose to use interval coefficients to model the sensitivity (the mathematic form is similar to classical generalized interval arithmetic) to correct those issues. Based on the analysis, we use a convex optimization problem to optimize the area costs. In the formulation, we also allow different bitwidths for the multiple uses of the same signal. We get an additional 2% to 3% area reduction compared with previous AA-based analysis and optimizations. We also conduct some optimality study to see how much the gap between the current methods and the possible optimal point is.

Hardware acceleration is crucial in modern embedded system design to meet the explosive demands on performance and cost. Selected computation kernels for acceleration are usually captured by nest loops, which are optimized by state-of-the-art techniques like loop tiling and loop pipelining. However, memory bandwidth bottlenecks prevent designs to reach optimal throughput with respect to available parallelism. In this paper we present an automatic memory partitioning technique which can efficiently improve throughput and reduce energy consumption of pipelined loop kernels for given throughput constraints and platform requirement. Our partition scheme consists of two steps, the first step considers cycle accurate scheduling information to meet the hard constraints on memory bandwidth requirements specifically for synchronized hardware designs. Experimental results show an average 6X throughput improvement on a set of real world designs with moderate area increase (about 45% on average), given that less resource sharing opportunities exist with higher throughput in optimized designs. The second step further partitions the memory banks for reducing the dynamic power consumption of the final design. In contrast with previous approaches, our technique can statically compute memory access frequencies in polynomial time with little to none profiling. Experimental results show about 30% power reduction on the same set of benchmarks.

In a behavioral synthesis system, a typical approach used to guide the scheduler is to impose hard constraints on the relative timing between operations considering performance, area, power, etc., so that the resulting RTL design is favorable in these aspects. The mechanism is often flawed in practice because many such constraints are actually soft constraints which are not necessary, and the constraint system may become inconsistent when many hard constraints are added for different purposes. This paper describes a scheduler that distinguishes soft constraints from hard constraints when exploring the design space. We propose a special class of soft constraints called integer-difference soft constraints, which lead to a totally unimodular constraint matrix in an integer linear programming formulation. By exploiting the total unimodularity, the problem can be solved optimally and efficiently using a linear programming relaxation without expensive branch and bound procedures. We also show how the proposed method can be used to support a variety of design considerations. As an example application, we apply the method to the problem of low-power synthesis with operation gating. In a set of experiments on real-world designs, our method achieves an average of 33.9% reduction in total power; it outperforms a previous method by 17.1% on average and gives close-to-optimal solutions on several designs.

Many techniques for power management employed in advanced RTL synthesis tools rely explicitly or implicitly on observability don't-care (ODC) conditions. In this paper we present a systematic approach to maximizing the effectiveness of these techniques by generating power-friendly RTL descriptions in a behavioral synthesis tool. We first introduce the concept of behavior-level observability and investigate its relation with observability under a given schedule, using an extension of Boolean algebra. We then propose an efficient algorithm to compute behavior-level observability on a data-flow graph. Our algorithm exploits knowledge about select and Boolean instructions, and allows certain forms of other knowledge, once uncovered, to be considered for stronger observability conditions. We also describe a behavioral synthesis flow where behavior-level observability is used to guide the scheduler toward maximizing the likelihood that execution of power-hungry instructions will be avoided under a latency constraint. Experimental results show that our approach is able to reduce total power, and it outperforms a previous method in [15] by 17.7% on average, on a set of real-world designs. To the best of our knowledge, this is the first work to use a comprehensive behavioral-level observability analysis to guide optimizations in behavioral synthesis.