Increased design complexity and time-to-market pressure in the integrated circuit (IC) industry call for a raised level of abstraction at which designs are specified. High-level synthesis is the process of generating register-transfer level (RTL) implementations from behavioral specifications, and it is the key enabler for a designing at a higher level beyond RTL. As IC manufacturing technology scales down to nanoscopic scale, the synthesis tools face a number of new challenges, including complexity, power and interconnect. In this dissertation, we propose a spectrum of new techniques in high-level synthesis to address the new challenges and to improve the quality of synthesis results.

1. Efficient and versatile scheduling engine using soft constraints. We present a scheduler that distinguishes soft constraints from hard constraints when exploring the design space, and identify a class of tractable scheduling problems with soft constraints. By exploiting the total unimodularity of the constraint matrix in an integer-linear programming formulation, we are able to solve the problem optimally in polynomial time. Compared to traditional methods, the proposed approach allows easier expression of various design intentions and optimization directions, and, at the same time, gives the scheduler freedom to make global trade-offs optimally. We show that this scheduling engine is flexible enough to support a variety of design considerations in high-level synthesis.

2. Behavior-level observability analysis and power optimization. We introduce the concept of behavior-level observability and its approximations in the context of high-level synthesis, and propose an efficient procedure to compute an approximated behavior-level observability of every operation in a dataflow graph. The algorithm exploits the observability-masking nature of some Boolean operations, as well as the select operation, and treats other operations as black boxes to allow efficient word-level analysis. The result is proven to be exact under the black-box abstraction. The behavior-level observability condition obtained by our analysis can be used to optimize operation gating in the scheduler. This leads to more opportunities in subsequent RTL synthesis for power reduction. To the best of our knowledge, this is the first time behavior-level observability analysis and optimization are performed in a systematic manner.

3. Layout-friendly high-level synthesis. We study a number of structural metrics for measuring the layout-friendliness of microarchitectures generated in high-level synthesis. For a piece of connected netlist, we introduce the spreading score to measures how far components can be spread from each other with bounded wire length in a graph embedding formulation. The intuition is that components in a layout-friendly netlist (e.g., a mesh) can spread over the layout region without introducing long interconnects. Spreading score can be approximated efficiently using a semidefinite programming relaxation. Another metric based on neighborhood population is also proposed. On a number of benchmarks, spreading score shows stronger bias in favor of interconnect structures that have shorter wire length after layout, compared to previous metrics based on cut size and total multiplexer inputs.

High-level synthesis is a design process which takes an un-timed, behavioral description in a high-level language like C and produces register-transfer-level (RTL) code that implements the same behaviour in hardware. In this design flow, the quality of the generated RTL is greatly influenced by high-level description of the language. Hence it follows that both source-level and IR-level compiler optimizations could either improve or hurt the quality of the generated RTL. The problem of ordering compiler optimization passes, also known as the phase-ordering problem, has been an area of active research over the past decade. An optimization has enabling and disabling effects on other optimizations, and such effects are caused by either the nature of the optimization itself, the input program being optimized, or the target platform for which the code is being optimized. A well-known fact in literature is that the standard optimization order chosen by the compiler writer may not be the best order for every input, and hence can end up producing inferior code.

All methods mentioned above are targeted towards compilers producing code that will be executed on a processor. In this study, we explore the effects of both source-level and IR optimizations on high-level synthesis. The parameters of the generated RTL are very

sensitive to high-level optimizations, in the sense that a right choice can provide significant benefits and a wrong choice can cause significant degradation. We consider three source-level optimizations commonly used in High-level synthesis. We study them in isolation and then propose simple yet effective heuristics to apply them to obtain a reasonable latency-area tradeoff. We also study the phase-ordering problem for IR-level optimizations from a HLS perspective. As many optimizations that are employed in a typical HLS flow were originally developed with a standard compiler in mind, and given the increasing popularity of HLS, we feel that such a study is essential to building high-quality HLS tools. Our initial results show that an input-specific order can achieve significant reduction in the latency of the generated RTL, and opens up this technology for future research.

Near storage computation has increasingly become a focus in improving the performance of big data systems. Technological trends have moved the bottle neck of data intensive workloads to the interconnects used to move data from storage to memory. This has given a rise to the need for moving processing power closer to where the data is stored. The solution presented in this paper aims to provide a developer friendly approach to computational storage that allows multiple computational storage capable devices to be used effectively by enabling data transfer between computational storage devices directly. In this work, we build a model system on Amazon AWS and run a merge sort workload to evaluate the benefits of allowing device to device communication. We identify the scenarios in which device to device communication is effective and propose additional optimizations and improvements to better the overall solution.

Future processor will not be limited by the transistor resources, but will be mainly constrained by energy efficiency. Reconfigurable architecture offers higher energy efficiency than CPUs through customized hardware and more flexibility than ASICs. FPGAs allow configurability at bit level to keep both efficiency and flexibility. However, in many computation-intensive applications, only word level customizations are necessary, which inspires coarse-grained reconfigurable arrays(CGRAs) to raise configurability to word level and to reduce configuration information, and to enable on-the-fly customization. Traditional CGRAs are designed in the era when transistor resources are scarce. Previous work in CGRAs share hardware resources among different operations via modulo scheduling and time multiplexing processing elements. In the emerging scenario where transistor resources are rich, we develop a novel CGRA architecture that features full pipelining and dynamic composition to improve energy efficiency and implement the prototype on Xilinx Virtex-6 FPGA board. Experiments show that fully pipelined and dynamically composable architecture(FPCA) can exploit the energy benefits of customization for user applications when the transistor resources are rich.

There is a growing trend to use coprocessors to offload and accelerate domain-specific applications in order to obtain significant performance improvement and energy/power reductions. Two important coprocessor components in the heterogeneous system are the GPU and FPGA. GPU (graphics processing unit) is increasingly used as a data-parallel coprocessor for general computations. The newest GPU has a much larger number of cores (compared to CPU) and very high peak FLOPS. FPGA (field programmable gate array), on the other hand, allows users to customize, at fine-grain level, the computational data path and memory hierarchy according to the exact need of the applications. FPGA excels in integer operations and bit-level operations.

The thesis starts with several coprocessor acceleration examples for our focus application domains: the first domain is on VLSICAD algorithms and the second is on computational medical imaging. We detail application acceleration examples in the domains including lithography simulation for IC manufacturing, medical image reconstruction using compressive sensing, and medical image registration using fluid models. Both GPU-accelerated versions and FPGA-accelerated versions have been implemented. Based on these implementations, we then analyze the performance and energy trade-offs, the interaction between the diverse application requirements and a spectrum of hardware systems, and how those domain-specific coprocessor acceleration case studies further bring us insights for domain-specific architecture innovations. In the end, we showcase an example for collaborative execution on the heterogeneous platform. Different scheduling policies are needed to optimize performance or energy. The thesis concludes as we present reusable architecture templates and realizations for futuristic accelerator-rich CMPs.

It is known that with the support of domain–specific customizable heterogeneous architecture, energy efficiency can be significantly improved by adapting architectures to match the requirements of a given application or application domain. One of the main challenges in this emerging trend is how to efficiently take the advantage of the heterogeneity and customization features in those architectures. This research investigates developing efficient compiler support to automate the platform mapping and code transformation process.

First, considering customizable computing engines, we have　investigated both tightly–coupled and loosely–coupled computing elements. In terms of tightly–coupled computing engine customization, customizable vector ISA supports are explored to better exploit data–level parallelism in the high performance applications. We identify the needs and opportunities to explore customized vector instructions and quantify their benefits. We build an automatic compilation flow in LLVM–2.7 compiler infrastructure to efficiently identify customized vector instructions from a given set of applications. The memory alignment overhead, which is known to be critical for vector processing efficiency, has been optimized in our customized vector ISA identification flow. To support efficient vector ISA customization, we design a composable vector unit (CVU), which can be used both separately and in a chained mode, to support a large number of virtualized custom vector instructions with minimal area overhead. The results show that our approach achieves an average 27% speedup over the state–of–art vector ISA.

Second, in terms of loosely–coupled computing elements, it is known that on–chip accelerators are combined with general–purpose cores in an effort to amortize the cost of the design across many application domains. In recent days programmable accelerators (PA) are widely investigated in the design of domain–specific architectures to improve the system performance and power. Micro–architectures with a series of PAs have been explored to provide more general supports for customization. One important feature in the PA–rich systems is that the target computational kernels are compiled with a set of pre–defined PA templates and dynamically mapped to real PAs at runtime. This imposes a demanding challenge on the compiler side regarding how to generate high–quality PA mapping code. We present an efficient PA compilation flow, which is fairly scalable in mapping large computation kernels into PA–rich architectures and provides support for full pipelined execution to achieve the highest energy efficiency. A concept called maximal PA candidate is proposed to drastically reduce the number of input PA candidates in the mapping phase without influencing the overall mapping optimality. Efficient pre–selection and pruning techniques are employed to further speedup the maximal PA mapping process. Our experimental results show that for 12 computation–intensive standard benchmarks, the proposed approach achieves a significant improvement on the compilation time comparing to the state–of–art PA compilation approaches. The average mapping quality is improved by 23.8% and 32.5% for connected PA candidates and disjoint ones, respectively.

Third, in domain–specific computing multi–level software–controlled memories have been commonly used to better utilize domain–specific knowledge of particular applications and achieve high performance/energy efficiency. At the level of L1 memory, while conventional cache works well for general workloads, some recent works explore the idea of using a hybrid cache, which can be flexibly partitioned into a traditional cache and an SCM. In the hybrid cache architecture, first–level SCM has been utilized as prefetch buffer to hide memory access latency. We quantify the impact of data reuse on SCM prefetching efficiency and propose a reuse–aware SCM prefetching (RASP) scheme, which shows 31.2% performance gain over previous work. On the other hand, SCM has also been widely used in last level on–board memory to reduce the data movements between computing cores (i.e. host processor and accelerator cores), which is usually transferred through low–bandwidth bus and known to be one of the major performance bottlenecks in modern heterogeneous systems. To efficiently manage LL–SCM, we propose a task–level–reuse–graph (TLRM) based LL–SCM data movement scheme to minimize the amount of data transfers between heterogeneous computing cores through the slow PCIe bus. With the introduction of TLRM, the data movement optimization between host and accelerator cores can be approximated using a linear programming based solution, and an average 25% reduction of host–accelerator data transfers is observed from previous work.

Energy consumption is a primary concern of current day computing systems -- from handheld battery operated systems to

servers in data centers connected to wall power. Research in academia as well as industry has focused on a variety of

techniques for minimizing energy consumption while maintaining a good level of performance. The most effective

techniques combine the best of static (or offline) and dynamic (or online/runtime) optimizations to obtain the best

solution. Static optimizations can be more complex and can afford to take a global view of the application/computation

being executed on the system -- however, such optimizations have to be conservative in nature because they cannot

anticipate all the different scenarios that can appear at runtime. Dynamic optimizations have more information about

the application/computation for the given input -- however, since such optimizations have to have low overhead, they can

afford to have only a local view of the computation/ application and the complexity of the optimization has to be

relatively low. An additional direction that needs to be considered is to determine whether dynamic optimizations

should be implemented in software or hardware. In this thesis, I present a study of three aspects of energy efficient

computing that use a combination of static and dynamic optimizations to minimize energy consumption. The first aspect is

to consider variability in the execution time of applications during scheduling for dynamic voltage frequency scaling

(DVFS) capable systems to minimize energy consumption and yet maintain a desired level of performance. The main idea is

to construct a schedule table offline and perform a simple table look-up at runtime. The second aspect is to consider

application-level reliability for applications that can tolerate certain error in the outputs. I present the study of a

profile-guided offline compilation strategy to identify critical instructions and a monitoring technique in software to

handle corner cases at runtime. Finally, the third aspect of energy efficient computing I investigate is flexibility --

customizing the instruction sets of processors to improve energy efficiency. I study the benefits of compiler directed

optimizations for generating custom instructions which are executed within a modified processor pipeline and an

architecture mechanism for detecting corner cases and to roll-back to a safe state. Additionally, I investigate the

benefits of customizing the instruction set dynamically in hardware.

As we witness the breakdown of Dennard scaling, we can no longer get faster computers by shrinking transistors without increasing power density. Yet, the amount of data to be processed has never stopped growing. The limited power budget builds a “power wall” between the ever-increasing demand for computation and the available computer hardware, which forces computer scientists to seek not only performant, but also power efficient computation solutions, especially in data centers. Moreover, the wide performance gap between the computation units and the memory builds a “memory wall” and limits performance from another dimension.

In the past decade, field-programmable gate arrays (FPGAs) have been rapidly adopted in data centers, thanks to their low power consumption and the reprogrammability that assemble highly power-efficient accelerators for memory-bound applications. Meanwhile, C-based high-level synthesis (HLS) has been growing as the FPGA acceleration market grows, bringing “hard-to-program” FPGA accelerators to a broader community in many application domains. However, to create efficient customized accelerators, FPGA-related expertise is still required for the domain experts when they write HLS C. To make it worse, even for experienced FPGA programmers, C-based HLS is often less productive compared with higher-level software languages, especially when an application cannot be easily programmed using the compiler directives designed for data-parallel programs.

This dissertation aims to address these two issues for domain-specific customizable accelerators for memory-bound applications with both regular and irregular memory access patterns. For memory-bound applications with regular memory accesses, we select stencil application as a representative for their complex data dependency that is challenging to optimize. We present SODA (Stencil with Optimized Dataflow Architecture) as a domain-specific compiler framework for FPGA accelerators. We show that by adopting theoretical analysis, model-driven design-space exploration, and domain-specific languages, programmers without FPGA expertise can build highly efficient stencil accelerators that outperform multi-thread CPUs by up to 3.3� with the memory bandwidth utilization improved by 1.65� on average. For memory-bound applications with irregular memory accesses, we select graph applications as a representative for their widespread presentation in various application domains. We first present TAPA (TAsk-PArallel) as a language extension to HLS, showing that convenient programming interfaces, universal software simulation, and hierarchical code generation can greatly improve productivity for task-parallel programs and reduce programmers’ burden. We then extend our effort to support dynamically scheduled memory accesses to cover more applications and further improve productivity. Finally, we show with two case studies from real-world graph applications, i.e., single-source shortest path for neural image reconstruction and graph convolutional neural network for learning on graph structure, that customizable accelerators can achieve up to 4.9� speedup over state-of-the-art FPGA accelerators and 2.6� speedup over state-of-the-art multi-thread CPU implementation.

This dissertation investigates the power-efficient high-performance architecture support for customizable domain-specific computing at both memory and communication levels in a customizable heterogeneous platform (CHP).

In domain-specific computing, the memory access pattern can be obtained through offline analysis. With this knowledge, the cores and the accelerators in the CHP can use on-chip scratchpad memory (SPM) and buffers to directly manage the data replacement in order to save off-chip memory bandwidth. We propose efficient schemes to hybrid the SPM and primary caches, and to also hybrid buffers and the shared last-level cache (LLC). In the hybrid primary cache, due to its low associativity, the problem of balancing the cache set utilization when the SPM is allocated in the cache is critical. We propose an adaptive hybrid cache (AH-Cache) to dynamically remap SPM blocks from high-demand cache sets to low-demand cache sets. In the hybrid LLC (typically designed as a nonuniform cache architecture, NUCA), the problem of resource contention and fragmentation becomes crucial. We propose a buffer-in-NUCA (BiN) scheme to assign shared buffer spaces to accelerators that can best utilize the additional buffer space, and use flexible paged buffer allocation to limit the impact of buffer fragmentation.

In domain-specific computing, the communication pattern can be also obtained through offline analysis. With this knowledge, the topology and routing scheme in the CHP communication subsystem can be customized to dynamically adapt to the known communication pattern. For the topology customization, we propose application-specific shortcuts and multicast realized by radio frequency interconnects (RF-I) overlaid network-on-chip (NoC). At runtime, we can flexibly allocate RF-I bandwidth to adapt the NoC topology to the known communication requirement of an application. For the routing customization, we propose an power-efficient application-specific cycle elimination and splitting (ACES) routing scheme to avoid restricting the critical routes of an application while achieving deadlock-free for irregular NoCs.

To further demonstrate the feasibility and effectiveness of these techniques, we develop a FPGA prototype of the proposed CHP with shared accelerators and buffers. The buffer sharing is achieved through a cost-efficient partial-crossbar to reduce the sharing overhead on timing and area.

High-level synthesis (HLS) tools simplify the FPGA design processes by allowing users to express their designs in high-level languages such as C/C++ or OpenCL. In this way, users could focus on algorithmic optimization with less concern for the cycle-by-cycle details at the register-transfer level (RTL). However, FPGA development flows still have two major limitations that hinder the adoption of FPGAs:

- Limited achievable frequency. There still exists a considerable gap between the quality-of-result (QoR) of an HLS-generated design and what is achievable by an RTL expert, especially the maximum operating frequency of the design. With the designs being scaled up in size, the final achievable frequency will be even lower. Unfortunately, a frequency degradation will directly lead to a proportional performance drop.

- Prolonged compilation time. In the current FPGA CAD flow, the RTL generated by the HLS compiler will be passed to the traditional synthesis and implementation tool. Although the C-to-RTL compilation is relatively quick, the RTL-to-bitstream implementation process will take much longer. With the designs becoming increasingly complex and the FPGA devices larger, the compile time surges from hours to days. Such an overlong process will seriously limit the working efficiency of engineers, especially when compared to software compilation that only takes seconds or minutes.

We observe that the existing FPGA CAD flows have not taken full advantage of HLS for further timing optimization and compilation reduction. Currently, the synthesis, placement, and routing tools are implemented and optimized to handle arbitrary RTL inputs. Those tools will adhere to the cycle-accurate behavior of the input design to ensure the correctness of the output. However, HLS-generated RTL is highly flexible and may tolerate additional pipeline registers without causing functional errors. Such latency-insensitive properties could significantly help the downstream compilation with timing closure. However, in the current toolchains, the HLS compilation is a standalone step, and the HLS-generated RTL will be treated in the same way as manually-written RTL by the logic synthesis tool. As a result, the information on pipeline flexibility in HLS designs will be lost, and the downstream physical implementation process cannot insert pipeline registers for timing closure.

Based on this observation, we propose methods to co-optimize the HLS compilation and the physical design process, which will enable frequency improvement and speed up the hardware accelerator development process simultaneously. Different from the conventional compilation stacks that separate the HLS compilation from the downstream physical implementation process, we propose to bridge the gap between HLS and physical design organically. By facilitating placement and routing with the latency-insensitive information of HLS, and in turn by guiding the HLS compilation with the physical layout information, we could achieve significant improvement in QoR and reduction in compile time.

Centered around this core idea, my thesis consists of three major parts. First, we explore how to improve the inherent timing quality of the RTL generated by HLS. Next, we couple HLS scheduling with coarse-grained floorplanning to improve the achievable frequency. Finally, we take one step further by partitioning the design for parallel placement and routing, then efficiently stitch them together without losing timing quality.

First, the thesis addresses the timing-closure challenge by improving the inherent timing quality of the machine-generated RTL. This chapter studies the timing issues in a diverse set of realistic and complex FPGA HLS designs, including two of my previously-published accelerator designs for genome sequencing. We observe that in almost all cases, the frequency degradation is caused by the broadcast structures generated by the HLS compiler. We classify three major types of broadcasts and propose a set of effective yet easy-to-implement approaches. Our experimental results show that our methods can improve the maximum frequency of a set of nine representative HLS benchmarks by 53\% on average.

In addition to optimizing the QoR of HLS by itself, the thesis further pushes up the final frequency by coupling HLS compilation with floorplanning. We propose AutoBridge, an automated framework that couples a coarse-grained floorplanning step with pipelining during HLS compilation. Since pipelining may introduce additional latency, we further present analysis and algorithms to ensure the added latency will not compromise the overall throughput. In our experiments with a total of 43 design configurations, we improve the average frequency from 147 MHz to 297 MHz (a 102% improvement) with no loss of throughput and a negligible change in resource utilization. Notably, in 16 experiments, we make the originally unroutable designs achieve 274 MHz on average. AutoBridge was recognized with the Best Paper Award in FPGA 2021.

Finally, we take one step further to enable parallel physical implementation on top of our HLS-floorplan co-design methodology. We propose a split compilation approach based on the pipelining flexibility at the HLS level. The pipeline flexibility allows us to partition designs for parallel placement and routing without timing degradation. Our research produces RapidStream, a parallelized and physical-integrated compilation framework that takes in a latency-insensitive program in C/C++ and generates a fully placed and routed implementation. When tested on the AMD/Xilinx U280 FPGA, we observed a 5-7X compile time reduction and a 1.3X frequency increase. RapidStream was recognized with the Best Paper Award in FPGA 2022.

In conclusion, my thesis targets two of the most challenging problems for modern EDA tools: timing closure and agile compilation. We first study the fanout optimization at the HLS level. Next, we explore the co-optimization of HLS and floorplanning, which has been used by at least eight other accelerator design projects. Finally, we enable the split compilation of HLS designs to reduce the compile time significantly. At the end of the thesis, we discuss future directions, including extending the methodology to support the compilation of RTL designs, multi-FPGA designs, and ASIC designs.