eCommons

 

Coordinated Static and Dynamic Scheduling for High-Quality High-Level Synthesis

Other Titles

Abstract

The breakdown of Dennard scaling has led to the rapid growth of specialized hardware accelerators to meet ever more stringent performance and energy requirements. However, great performance-per-watt comes at the cost of enormous development effort. As the process of register-transfer level (RTL) optimization becomes unequivocally difficult, if not already unsustainable, high-level synthesis (HLS) has emerged as a promising approach to tackle the design productivity gap by raising the level of abstraction and in turn enabling lower design complexity and faster simulation speed. Scheduling forms the algorithmic core to state-of-the-art HLS technology, which automatically compiles untimed high-level (software) programs into cycle-accurate RTL (hardware) implementations. Given a set of constraints such as those arising from timing and resources, HLS scheduling extracts parallelism from the input program through control data flow analysis and determines the clock cycle at which each operation should be executed. Despite increasing adoption of HLS for its design productivity advantage, the lack of success in achieving high quality-of-results (QoR) out-of-the-box continues to hinder the productivity advantage for which HLS is known. First, current scheduling algorithms rely heavily on fundamentally inexact heuristics that make ad-hoc local decisions due to scalability concerns with exact methods and cannot accurately and globally optimize over a rich set of constraints. This results in sub-optimal schedules for the generated hardware whose QoR gap remains unknown to the designer as well as the tool itself. Second, current scheduling techniques rely on static compiler analysis of the input program and must make simplifying assumptions about statically unanalyzable program behaviors. These assumptions are often too strong to provide adequate support for dynamic behaviors arising from variable-latency operations, irregular program patterns, and runtime hardware hazards. Third, HLS scheduling generates and uses inaccurate resource and timing estimates that deviate significantly from actual post-implementation QoR. Inaccurate estimates prevent designers and the tool from performing meaningful design space exploration without resorting to the time-consuming downstream implementation process. The aforementioned challenges culminate in the algorithm, flexibility, and estimation gaps, respectively, faced by state-of-the-art HLS tools. To tackle these major challenges of HLS, this thesis proposes a set of coordinated static and dynamic scheduling techniques to achieve QoR on-par with or exceeding that of manually optimized design. First, this thesis addresses the algorithm gap by improving static scheduling with a novel formulation based on system of integer difference constraints (SDC) and satisfiability (SAT) to exactly handle a variety of scheduling constraints. I develop specialized schedulers based on conflict-driven learning and problem-specific knowledge to optimally and efficiently solve scheduling problems leveraging modern constraint programming capabilities. Second, this thesis addresses the flexibility gap by proposing a set of dynamic scheduling techniques to synthesize flexible and complexity-effective HLS pipelines that are aware of dynamic structural and data hazards. I introduce scheduling and synthesis techniques to generate HLS pipelines with the ability to speculate, squash, and flush, making it possible to maintain high throughput in the presence of runtime hazards. Third, this thesis addresses the estimation gap by training a set of promising machine learning models to enable fast and accurate QoR estimation in HLS. The models are able to dramatically reduce estimation errors with negligible runtime cost.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

2019-05-30

Publisher

Keywords

Electronic Design Automation; Computer engineering; Electrical engineering; Pipeline Synthesis; Computer science; High-Level Synthesis; Optimization Algorithms; machine learning; Scheduling

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Zhang, Zhiru

Committee Co-Chair

Committee Member

Suh, Gookwon Edward
Batten, Christopher

Degree Discipline

Electrical and Computer Engineering

Degree Name

Ph.D., Electrical and Computer Engineering

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record