TU Darmstadt / ULB / TUbiblio

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

Oppermann, Julian (2019)
Advances in ILP-based Modulo Scheduling for High-Level Synthesis.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (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.

Typ des Eintrags: Dissertation
Erschienen: 2019
Autor(en): Oppermann, Julian
Art des Eintrags: Erstveröffentlichung
Titel: Advances in ILP-based Modulo Scheduling for High-Level Synthesis
Sprache: Englisch
Referenten: Koch, Prof. Dr. Andreas ; Sinnen, Prof. Oliver
Publikationsjahr: 2019
Ort: Darmstadt
Datum der mündlichen Prüfung: 30 Oktober 2019
URL / URN: https://tuprints.ulb.tu-darmstadt.de/9272
Kurzbeschreibung (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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
URN: urn:nbn:de:tuda-tuprints-92720
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Eingebettete Systeme und ihre Anwendungen
Hinterlegungsdatum: 24 Nov 2019 20:55
Letzte Änderung: 24 Nov 2019 20:55
PPN:
Referenten: Koch, Prof. Dr. Andreas ; Sinnen, Prof. Oliver
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 30 Oktober 2019
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen