Specialized accelerators are increasingly attractive solutions to continue expected generational performance scaling with slowing technology scaling. Existing programmable accelerators like GPUs are limited to regular algorithms; however, supporting irregularity becomes necessary to accelerate more advanced algorithms or those from challenging domains.Irregularity occurs when aspects of the execution depend on the data -- these aspects can be control, memory, parallelism, and reuse. An example of data-dependent execution is joining two sparse lists where the branch outcome depends on data; this inherently couples computation with memory and precludes efficient vectorization -- defeating the traditional mechanisms of programmable accelerators (e.g., GPUs). Data dependencies in computations like producer-consumer streaming dependencies require detrimental synchronization overhead in shared memory systems.

We aim to develop a family of compatible dataflow accelerator mechanisms. Our critical insight is that it is unnecessary to support arbitrary forms of irregularity because specializable data dependence forms are sufficient for many workloads (despite being more restrictive). We expose these data dependence forms as first-class citizens in the instruction set architecture (ISA) so that the corresponding hardware is specialized for efficiency while remaining flexible to the requirements of applications.

This dissertation studies various applications from machine learning, graph processing, databases, and signal processing. First, we identified specializable forms for instruction and task-level irregularity (where a task is coarse-grained). These primitives are designed to be composable and extensible to enable continual evolution. Then, we used these forms to design a family of spatial architectures supporting irregularity with compatible features. Leveraging hardware flexibility, we also studied different algorithmic implementations and developed insights into the complex relationship between input, workload, and algorithmic choices on performance.

We evaluate the architecture by integrating a custom accelerator simulator into the cycle-level gem5 simulator. The input programs are written in a combination of C and intrinsics of traditional dataflow and our data dependence forms. The hardware components are implemented in Chisel with an industry 28-nm technology. Overall, our architectures achieve order-of-magnitude speedups over a similarly provisioned GPU while remaining within 30% of application-specific architectures. In graph processing, we achieved 5.7x speedup over the best prior domain-specific accelerator, using the flexibility to choose the optimal algorithm given the input workload and data characteristics. Our designed hardware can be a strong alternative to GPUs; the main compute offload accelerators today. Besides, our proposed features target irregular primitives and perform similarly to prior domain-specific architectures. We believe our work can be the first step to unifying the rapidly evolving irregular acceleration space.

The once exponential general purpose processors’ (e.g. CPUs) growth of speedup driven bytransistor scaling is fading, which urges both industry and academia to find more energy- efficient and performant architecture organization. Therefore, research on accelerators specialized for applications of interest emerges because of their promising speedup and energy saving while retaining flexibility. To design and implement specialized accelerators, intensive human effort is required to study the target applications and determine tradeoffs between performance and cost. In addition, these newly proposed hardware often implies lagging compilation techniques, which hinders the programming productivity. All these facts significantly limits the programmable accelerator adoption. Moreover, all the prior development effort can hardly be reused in other applicable do- mains, because the current software/hardware co-designed innovations seldom consider modularity for future integration. Therefore, research projects presented in this dissertation aim at significantly reforming the full-stack reconfigurable accelerator design paradigm: Ideally, each software/hardware co-design feature can be comprised in a universal design space for further accelerator composition so that people no longer build accelerators from scratch. Further, an accelerator can be automatically generated based on the given applications of interest written in a unified high-level programming interface. To achieve this goal, this dissertation develops the framework, DSAGEN, including an accelerator design space with rich software/hardware co-design features, a compiler targets to accelerators with arbitrary design points within this space, and a design automation algorithm that efficiently searches this space. According to our evaluation, the compiler can robustly target multiple application suites on hardware with arbitrary feature combinations. The framework-generated accelerators can have comparable perf/mm2 compared with prior handcrafted domain-specific accelerators. In addition, to demonstrate the wide applicability of our approach, the insights and principles learned along with this goal are also applied to applicable research questions: By deploying the DSAGEN-generated accelerator as a reconfigurable overlay on FPGA, it saves orders-of-magnitude time on compilation and reconfiguration compared with conventional high-level synthesis, while retaining flexibility. This approach suggests that a deeply spe- cialized programmable overlay accelerator can potentially supplement the existing FPGA’s high-level programming paradigm. Also, the compilation techniques for spatial architectures developed in DSAGEN can be applied to compiling an emerging instruction paradigm specialized for tensor operations — a productive and extensible compilation framework, UNIT, is presented for these instructions. The extensibility of this framework allows developers to easily integrate new instructions by describing the instruction semantics. High-performance code, that outperforms vendor provided libraries up to 2.2�, for end-to-end inferences can be generated by tensorized rewriting, accompanied with our automated tuning strategies.