TU Darmstadt / ULB / TUprints

Advances in ILP-based Modulo Scheduling for High-Level Synthesis

Oppermann, Julian (2019):
Advances in ILP-based Modulo Scheduling for High-Level Synthesis.
Darmstadt, Technische Universität, [Ph.D. Thesis]

[img]
Preview
Text
thesis_joppermann.pdf
Available under CC-BY-NC-ND 4.0 International - Creative Commons, Attribution Non-commerical, No-derivatives.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: Advances in ILP-based Modulo Scheduling for High-Level Synthesis
Language: English
Abstract:

In today's heterogenous computing world, field-programmable gate arrays (FPGA) represent the energy-efficient alternative to generic processor cores and graphics accelerators. However, due to their radically different computing model, automatic design methods, such as high-level synthesis (HLS), are needed to harness their full power. HLS raises the abstraction level to behavioural descriptions of algorithms, thus freeing designers from dealing with tedious low-level concerns, and enabling a rapid exploration of different microarchitectures for the same input specification. In an HLS tool, scheduling is the most influential step for the performance of the generated accelerator. Specifically, modulo schedulers enable a pipelined execution, which is a key technique to speed up the computation by extracting more parallelism from the input description.

In this thesis, we make a case for the use of integer linear programming (ILP) as a framework for modulo scheduling approaches. First, we argue that ILP-based modulo schedulers are practically usable in the HLS context. Secondly, we show that the ILP framework enables a novel approach for the automatic design of FPGA accelerators.

We substantiate the first claim by proposing a new, flexible ILP formulation for the modulo scheduling problem, and evaluate it experimentally with a diverse set of realistic test instances. While solving an ILP may incur an exponential runtime in the worst case, we observe that simple countermeasures, such as setting a time limit, help to contain the practical impact of outlier instances. Furthermore, we present an algorithm to compress problems before the actual scheduling.

An HLS-generated microarchitecture is comprised of operators, i.e. single-purpose functional units such as a floating-point multiplier. Usually, the allocation of operators is determined before scheduling, even though both problems are interdependent. To that end, we investigate an extension of the modulo scheduling problem that combines both concerns in a single model. Based on the extension, we present a novel multi-loop scheduling approach capable of finding the fastest microarchitecture that still fits on a given FPGA device - an optimisation problem that current commercial HLS tools cannot solve. This proves our second claim.

Alternative Abstract:
Alternative AbstractLanguage
Heutzutage werden komplexe Probleme in Wissenschaft und Technik von heterogenen Rechnersysteme gelöst. In diesem Umfeld haben sich sogenannte "field-programmable gate arrays" (FPGA) als energieeffizientere Alternative zum Rechnen auf normalen Prozessorkernen oder Grafikkarten etabliert. Bei FPGAs handelt es sich um Halbleiterbauteile, die beim Einschalten einen beliebigen Schaltkreis abbilden können, welcher dann die gewünschten Berechnungen durchführt. Da sich dieses Programmiermodell grundlegend von den Gewohnheiten der Software-Welt unterscheidet, sind die Anforderungen an die verwenden Entwurfswerkzeuge hoch. Die Synthese eines Schaltkreis aus einer Problembeschreibung in einer Hochsprache wie C wird "high-level synthesis" (HLS) genannt. HLS kann Hardware-Ingenieure merklich entlasten, weil viele konkrete Aspekte des Schaltkreises automatisch erzeugt werden. Dies ermöglicht auch eine schnelle Untersuchung verschiedener Entwurfsalternativen. In einem HLS-Werkzeug hat die Ablaufplanung (engl. "scheduling") den größten Einfluss auf die Leistung des generierten Schaltkreises. Eine wichtige Technik, um die Ausführungsgeschwindigkeit weiter zu verbessern, ist die Fließbandverarbeitung (engl. "pipelining") von Berechnungen. Diese wird durch das Lösen eines zyklischen Ablaufplanungsproblems (engl. "modulo scheduling") ermöglicht. Diese Dissertation untersucht den Einsatz von mathematischen Optimierungsmethoden, genauer von ganzzahliger linearer Optimierung (engl. "integer linear programming", ILP), zur Lösung von modulo scheduling-Problemen. Es werden zwei Hauptthesen aufgestellt. Erstens, ILP-basierte Verfahren sind praktisch nutzbar im Kontext von HLS-Werkzeugen. Zweitens, ILP-basierte Verfahren eröffnen neue Möglichkeiten in der automatischen Synthese von Schaltkreisen. Als Beleg für die erste These wird eine neue, flexible ILP-Formulierung des Scheduling-Problems vorgestellt und anhand einer Vielzeit von Problem-Instanzen aus der Praxis evaluiert. Einfache Maßnahmen wie das Setzen eines Zeitlimits helfen, die theoretisch exponentiellen Laufzeiten beim ILP-Lösen abzufangen. Außerdem wird ein Algorithmus zur Komprimierung des Problems vor der eigentlichen Ablaufplanung beschrieben. Bisher ist es üblich, vor der Ablaufplanung zu bestimmen, welche und insbesondere wie viele sogenannte Operatoren im späteren Schaltkreis zur Verfügung stehen, um Teilberechnungen (z.B. eine Multiplikation von zwei Werten) durchzuführen. Tatsächlich sind aber die Ablaufplanung und Operatorallokation voneinander abhängige Probleme. Es wird daher eine Erweiterung des modulo scheduling-Problems vorgeschlagen, die beide Problemaspekte gemeinsam modelliert. Darauf basierend wird ein Scheduling-Verfahren vorgestellt, welches die schnellste Schaltung findet, die gerade noch auf einen vorgegebenen FPGA passt - ein Optimierungsproblem, welches in der Form nicht direkt von kommerziellen HLS-Werkzeugen gelöst werden kann. Dies belegt die zweite These.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Embedded Systems and Applications
Date Deposited: 22 Nov 2019 13:14
Last Modified: 22 Nov 2019 13:14
URN: urn:nbn:de:tuda-tuprints-92720
Referees: Koch, Prof. Dr. Andreas and Sinnen, Prof. Oliver
Refereed: 30 October 2019
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9272
Export:
Actions (login required)
View Item View Item