The compelling next generation streaming applications containing several computationally intensive nested loop programs are the driving force for the System-on-chip (SoC) architectures. SoC platforms are characterized by the presence of diverse components like traditional processors augmented with programmable or non-programmable accelerators. The accelerators implement computationally intensive loop programs of a given application. An SoC platform can improve the performance, optimize power, and reduce cost by orders of magnitude due to specialized execution on these accelerators. The effort for programming and synthesizing the loop accelerators for streaming applications is still enormous. Therefore, the PARO design methodology is presented in this thesis, which enables automated synthesis and exploration of accelerators for streaming applications. In this dissertation, we present a source-to-source transformation called hierarchical tiling, which kneads the loop descriptions in a high-level language using a polyhedral framework with multiple hierarchies of tiles. This important extension of well known transformation called loop tiling, enables utilization of multiple levels of parallelism and memories in an accelerator architecture. With hierarchical tiling, the system designer is thus able to specify the degree of parallelism (number of PEs), local memory usage, and requisite communication bandwidth for the accelerator architecture. Other design flows contain simple tiling or loop unrolling, which can only specify only one or the other criteria but not all of them. The transformation, however, may create a loop code characterized by the presence of a lot more control conditions, which could become a performance bottleneck. Therefore, a novel back-end methodology for control generation was presented. I/O communication can also become a performance bottleneck. Therefore, depending on the tiling parameters and schedule, a custom memory architecture with multiple banks, address generators, and I/O controllers is automatically generated. The consideration of front-end transformation like hierarchical tiling and novel back-end synthesis of control and I/O communication unit, leads to highly efficient accelerator implementations. We used several loop benchmarks from different class of loop algorithms ranging from linear algebra, image processing, to networking. The synthesized loop accelerators show an average gain of around 2.5x, 4.5x, and 50x in terms of area, power, and performance over embedded processors. Streaming applications are characterized by the presence of multiple communicating loops. With state-of-the-art polyhedral techniques, one can generate fast individual loop accelerators, but there exists no methodology for automated generation of intermediate communication hardware which is often a major bottleneck. In this context, a novel intermediate dependence graph called mapped loop graph was introduced for the modular representation of task level parallelism of communicating loops and their mapping information in the polyhedral model. A methodology is proposed for the projection of a mapped loop graph in the polyhedral model onto model parameters of a data flow model of computation called windowed synchronous data flow (WSDF). Subsequently, the generation of an efficient dedicated communication primitive called multi-dimensional FIFO from the windowed synchronous data flow model is undertaken. The communication synthesis is able to generate communication hardware for data transfer and synchronization between the loop accelerators, which is able to handle parallel access and out-of-order communication in entirety, unlike the existing approaches. In order to ease the integration of accelerators in an SoC, a methodology for automated generation of a memory map, a software driver, and a hardware wrapper was proposed. The hardware/software codesign approach may offer an advantage of 2-20x over pure software solutions. The selection of an optimal architecture can be daunting due to a plethora of architecture and compiler design decisions. Exhaustive exploration of the design space is prohibitive due to absurdly large execution time. Therefore, we propose a method using modern search heuristics based on evolutionary algorithms and estimation of objectives to identify Pareto-optimal designs (i.e., non-dominated designs with best trade-offs) in terms of area cost, power consumption, and performance. This not only reduces the exploration time to a matter of around an hour for relevant accelerator benchmarks, but also delivers better design solutions than random search techniques. For a given workload scenario, a best-fit accelerator can be chosen from the Pareto-optimal set of designs. The proposed analytical method for finding the best-fit accelerator is based on real-time calculus and uses system performance models.

Unter „System-on-a-Chip (SoC)“ versteht man die Integration von verschiedenen Komponenten, wie z.B. herkömmliche Prozessoren mit programmierbaren oder nicht programmierbaren Schleifenbeschleuniger, auf einem Stück Silizium. Viele rechenintensive Schleifenprogramme, z.B. aus dem Bereich der Signalverarbeitung oder Bildverarbeitung, lassen sich effizient auf Schleifenbeschleunigern ausführen. SoC-Plattformen können Leistung, Flächenkosten und Leistungsaufnahme von eingebetten Anwendungen aufgrund dieser Beschleuniger optimieren und um Größenordnungen reduzieren. Obwohl solche SoCs auf FPGAs oder ASICs realisiert werden können, ist der aufwand für die Realisierungs Schleifenbeschleuniger immer noch sehr hoch. Um hierbei Abhilfe zu leisten, wird in dieser Arbeit die PARO Design-Methodik vorgestellt. Es handelt sich im Wesentlichen um einen Compiler, der eine RTL Beschreibung der Schleifenbeschleuniger in Form von Prozessor-Arrays generiert. Kachelung ist eine bekannte Compiler Transformation. In dieser Dissertation wird die hierarchische Kachelung präsentiert, eine Transformation, die die Schleifenbeschreibungen in der Hochsprache transformiert, um mehrere Parallelitäts- und Speicherebenen in einer Beschleuniger-Architektur zu nutzen. Mit dieser Transformation ist der Systementwickler in der Lage, den Grad der Parallelität (Anzahl der PEs), den lokalen Speicher und die erforderliche Kommunikationsbandbreite der Beschleunigerarchitektur zu spezifizieren. Andere Design-Methodiken enthalten Transformationen, die nur jeweils eine der beiden Kriterien berücksichten können. Die in dieser Arbeit vorgestellten Transformation erzeugt ein Schleifenprogramm, welches viel mehr Kontrollbedingungen enthält. Diese können ein Performanzengpass hervorrufen. Aus diesem Grund wurde eine generische Methode zur Kontrolgenerierung vorgestellt, die die lokale und globale Steuerung für eine effiziente Ausführung der Schleifen kombiniert. Außerdem wird eine passende Speicherarchitektur mit mehreren Speicherbänken, Adressgeneratoren und I/O-Controllern automatisch generiert, so dass die Kommunikation nicht der Flaschenhals ist. Mit all diesen Techniken ist man in der Lage, Schleifenbeschleuniger zu generieren, die einen durchschnittlichen Gewinn von Faktoren 2,5, 4,5 und 50 in Bezug auf Fläche, Strom, und Leistung gegenüber Embedded-Prozessoren erzielt. Typische streaming-Anwendungen enthalten mehreren kommunizierenden Schleifen. Für eine modulare Darstellung der Parallelität der kommunizierenden Schleifen und ihren Abbildungsinformationen als Abhängigkeitsgraph im polyedrischen Model, wurde der sogenannte Loop-Graph entwickelt. Diese einheitliche Methodik für die Projektion eines Loop-Graphen im polyedrische Modell auf das sogenannte „Windowed Synchronous Data Flow (WSDF)“-Modell wurde vorgestellt. Die sogenannten „multi-dimensionalen FIFOs“ für die Datenübertragung und Synchronisation zwischen den Schleifenbeschleunigern wurde danach aus den WSDF-Parametern hergeleitet. Daher ist die Kommunikations-Hardware nicht der Engpass des Beschleunigerkette, das aus mehreren kommunizierenden Schleifenbeschleunigern und mehrdimensionalen FIFOs besteht. Die Beschleuniger können auch als Co-Prozessoren in einem SoC verwendet werden. Um die Integration von Beschleunigern in einem SoC zu unterstützen, wurde eine Methodik zur automatisierten Generierung der Speicherabbildung, eine Treiber-Software und eine Hardwareschnittstelle vorgestellt. Experimentelle Ergebnisse zeigen außerdem, dass der Performance-Gewinn für ein Hardware/Software Co-Design 10-fach geringer als bei einer reinen Hardware-Implementierung ausfällt. Dies liegt an dem großen Hardware/Software Kommunikationsaufwand. Trotzdem bieten die Beschleuniger einen Performanz-Vorteil von 2 bis 20-fach gegenüber einer reinen Software-Lösungen und darüber hinaus eine wesentlich geringere Leistungsaufnahme. Aufgrund der Vielzahl von Architektur und Compiler-Designentscheidungen, kann die Auswahl einer optimalen Architektur sehr aufwändig sein: Die vollständige Erkundung des Entwurfsraums erfordert sehr große Laufzeiten, weshalb wir moderne meta-Suchheuristiken, wie z.B. evolutionäre Algorithmen, und die effiziente Schätzung von Zielfunktionen wie Flächenkosten und Leistungsaufnahme verwenden. Dies reduziert nicht nur die Laufzeit der Exploration für relevante Beschleunigerbenchmarks, sondern liefert auch ein besseres Ergebnis als die zufällige Suche. Für gegebene Systemeinschränkungen muss ein passender Beschleuniger aus dem Pareto-optimalen Satz von Designs ausgewählt werden. Die vorgeschlagene analytische Methode zur Bestimmung des Best-Fit-Beschleunigers basiert auf dem Echtzeit-Kalkül.