東華大學圖書館 |

Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis./
Author:	Dai, Steve Haihang.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2019,
Description:	143 p.
Notes:	Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
Contained By:	Dissertations Abstracts International80-12B.
Subject:	Computer Engineering. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13881733
ISBN:	9781392248720

Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis.
Dai, Steve Haihang.

Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis. - Ann Arbor : ProQuest Dissertations & Theses, 2019 - 143 p.

Source: Dissertations Abstracts International, Volume: 80-12, Section: B.

Thesis (Ph.D.)--Cornell University, 2019.

This item must not be sold to any third party vendors.

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.

ISBN: 9781392248720Subjects--Topical Terms:

1567821
Computer Engineering.

Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis.
LDR:04868nmm a2200337 4500 001 2210817
005 20191121124316.5
008 201008s2019 ||||||||||||||||| ||eng d
020 $a 9781392248720
035 $a (MiAaPQ)AAI13881733
035 $a (MiAaPQ)cornellgrad:11408
035 $a AAI13881733
040 $a MiAaPQ $c MiAaPQ
100 1 $a Dai, Steve Haihang. $3 3437959
245 1 0 $a Coordinated Static and Dynamic Scheduling for High-quality High-level Synthesis.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2019
300 $a 143 p.
500 $a Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Zhang, Zhiru.
502 $a Thesis (Ph.D.)--Cornell University, 2019.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0058.
650 4 $a Computer Engineering. $3 1567821
650 4 $a Electrical engineering. $3 649834
650 4 $a Computer science. $3 523869
690 $a 0464
690 $a 0544
690 $a 0984
710 2 $a Cornell University. $b Electrical and Computer Engineering. $3 2100661
773 0 $t Dissertations Abstracts International $g 80-12B.
790 $a 0058
791 $a Ph.D.
792 $a 2019
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13881733