Modern organizations produce and collect large volumes of data, that need to be processed repeatedly and quickly for gaining business insights. For such processing, typically, Data-intensive Flows (DIFs) are deployed on distributed processing frameworks. The DIFs of different users have many computation overlaps (i.e., parts of the processing are duplicated), thus wasting computational resources and increasing the overall cost. The output of these computation overlaps (known as intermediate results) can be materialized for reuse, which helps in reducing the cost and saves computational resources if properly done. Furthermore, the way such outputs are materialized must be considered, as different storage layouts (i.e., horizontal, vertical, and hybrid) can be used to reduce the I/O cost. In this PhD work, we first propose a novel approach for automatically materializing the intermediate results of DIFs through a multi-objective optimization method, which can tackle multiple and conflicting quality metrics. Next, we study the behavior of different operators of DIFs that are the first to process the loaded materialized results. Based on this study, we devise a rule-based approach, that decides the storage layout for materialized results based on the subsequent operation types. Despite improving the cost in general, the heuristic rules do not consider the amount of data read while making the choice, which could lead to a wrong decision. Thus, we design a cost model that is capable of finding the right storage layout for every scenario. The cost model uses data and workload characteristics to estimate the I/O cost of a materialized intermediate results with different storage layouts and chooses the one which has minimum cost. The results show that storage layouts help to reduce the loading time of materialized results and overall, they improve the performance of DIFs. The thesis also focuses on the optimization of the configurable parameters of hybrid layouts. We propose ATUN-HL (Auto TUNing Hybrid Layouts), which based on the same cost model and given the workload and characteristics of data, finds the optimal values for configurable parameters in hybrid layouts (i.e., Parquet). Finally, the thesis also studies the impact of parallelism in DIFs and hybrid layouts. Our proposed cost model helps to devise an approach for fine-tuning the parallelism by deciding the number of tasks and machines to process the data. Thus, the cost model proposed in this thesis, enables in choosing the best possible storage layout for materialized intermediate results, tuning the configurable parameters of hybrid layouts, and estimating the number of tasks and machines for the execution of DIFs. / Moderne Unternehmen produzieren und sammeln große Datenmengen, die wiederholt und schnell verarbeitet werden müssen, um geschäftliche Erkenntnisse zu gewinnen. Für die Verarbeitung dieser Daten werden typischerweise Datenintensive Prozesse (DIFs) auf verteilten Systemen wie z.B. MapReduce bereitgestellt. Dabei ist festzustellen, dass die DIFs verschiedener Nutzer sich in großen Teilen überschneiden, wodurch viel Arbeit mehrfach geleistet, Ressourcen verschwendet und damit die Gesamtkosten erhöht werden. Um diesen Effekt entgegenzuwirken, können die Zwischenergebnisse der DIFs für spätere Wiederverwendungen materialisiert werden. Hierbei müssen vor allem die unterschiedlichen Speicherlayouts (horizontal, vertikal und hybrid) berücksichtigt werden. In dieser Doktorarbeit wird ein neuartiger Ansatz zur automatischen Materialisierung der Zwischenergebnisse von DIFs durch eine mehrkriterielle Optimierungsmethode vorgeschlagen, der in der Lage ist widersprüchliche Qualitätsmetriken zu behandeln. Des Weiteren wird untersucht die Wechselwirkung zwischen verschiedenen peratortypen und unterschiedlichen Speicherlayouts untersucht. Basierend auf dieser Untersuchung wird ein regelbasierter Ansatz vorgeschlagen, der das Speicherlayout für materialisierte Ergebnisse, basierend auf den nachfolgenden Operationstypen, festlegt. Obwohl sich die Gesamtkosten für die Ausführung der DIFs im Allgemeinen verbessern, ist der heuristische Ansatz nicht in der Lage die gelesene Datenmenge bei der Auswahl des Speicherlayouts zu berücksichtigen. Dies kann in einigen Fällen zu falschen Entscheidung führen. Aus diesem Grund wird ein Kostenmodell entwickelt, mit dem für jedes Szenario das richtige Speicherlayout gefunden werden kann. Das Kostenmodell schätzt anhand von Daten und Auslastungsmerkmalen die E/A-Kosten eines materialisierten Zwischenergebnisses mit unterschiedlichen Speicherlayouts und wählt das kostenminimale aus. Die Ergebnisse zeigen, dass Speicherlayouts die Ladezeit materialisierter Ergebnisse verkürzen und insgesamt die Leistung von DIFs verbessern. Die Arbeit befasst sich auch mit der Optimierung der konfigurierbaren Parameter von hybriden Layouts. Konkret wird der sogenannte ATUN-HL Ansatz (Auto TUNing Hybrid Layouts) entwickelt, der auf der Grundlage des gleichen Kostenmodells und unter Berücksichtigung der Auslastung und der Merkmale der Daten die optimalen Werte für konfigurierbare Parameter in Parquet, d.h. eine Implementierung von hybrider Layouts. Schließlich werden in dieser Arbeit auch die Auswirkungen von Parallelität in DIFs und hybriden Layouts untersucht. Dazu wird ein Ansatz entwickelt, der in der Lage ist die Anzahl der Aufgaben und dafür notwendigen Maschinen automatisch zu bestimmen. Zusammengefasst lässt sich festhalten, dass das in dieser Arbeit vorgeschlagene Kostenmodell es ermöglicht, das bestmögliche Speicherlayout für materialisierte Zwischenergebnisse zu ermitteln, die konfigurierbaren Parameter hybrider Layouts festzulegen und die Anzahl der Aufgaben und Maschinen für die Ausführung von DIFs zu schätzen.

Unternehmen sammeln mehr Daten als je zuvor und müssen auf diese Informationen zeitnah reagieren. Relationale Datenbanken eignen sich nicht für die latenzfreie Verarbeitung dieser oft unstrukturierten Daten. Um diesen Anforderungen zu begegnen, haben sich in der Datenbankforschung seit dem Anfang der 2000er Jahre zwei neue Forschungsrichtungen etabliert: skalierbare Verarbeitung unstrukturierter Daten und latenzfreie Datenstromverarbeitung. Skalierbare Verarbeitung unstrukturierter Daten, auch bekannt unter dem Begriff "Big Data"-Verarbeitung, hat in der Industrie schnell Einzug erhalten. Gleichzeitig wurden in der Forschung Systeme zur latenzfreien Datenstromverarbeitung entwickelt, die auf eine verteilte Architektur, Skalierbarkeit und datenparallele Verarbeitung setzen. Obwohl diese Systeme in der Industrie vermehrt zum Einsatz kommen, gibt es immer noch große Herausforderungen im praktischen Einsatz. Diese Dissertation verfolgt zwei Hauptziele: Zuerst wird das Laufzeitverhalten von hochskalierbaren datenparallelen Datenstromverarbeitungssystemen untersucht. Im zweiten Hauptteil wird das "Dual Streaming Model" eingeführt, das eine Semantik zur gleichzeitigen Verarbeitung von Datenströmen und Tabellen beschreibt. Das Ziel unserer Untersuchung ist ein besseres Verständnis über das Laufzeitverhalten dieser Systeme zu erhalten und dieses Wissen zu nutzen um Anfragen automatisch ausreichende Rechenkapazität zuzuweisen. Dazu werden ein Kostenmodell und darauf aufbauende Optimierungsalgorithmen für Datenstromanfragen eingeführt, die Datengruppierung und Datenparallelität einbeziehen. Das vorgestellte Datenstromverarbeitungsmodell beschreibt das Ergebnis eines Operators als kontinuierlichen Strom von Veränderugen auf einer Ergebnistabelle. Dabei behandelt unser Modell die Diskrepanz der physikalischen und logischen Ordnung von Datenelementen inhärent und erreicht damit eine deterministische Semantik und eine minimale Verarbeitungslatenz. / Modern companies are able to collect more data and require insights from it faster than ever before. Relational databases do not meet the requirements for processing the often unstructured data sets with reasonable performance. The database research community started to address these trends in the early 2000s. Two new research directions have attracted major interest since: large-scale non-relational data processing as well as low-latency data stream processing. Large-scale non-relational data processing, commonly known as "Big Data" processing, was quickly adopted in the industry. In parallel, low latency data stream processing was mainly driven by the research community developing new systems that embrace a distributed architecture, scalability, and exploits data parallelism. While these systems have gained more and more attention in the industry, there are still major challenges to operate them at large scale. The goal of this dissertation is two-fold: First, to investigate runtime characteristics of large scale data-parallel distributed streaming systems. And second, to propose the "Dual Streaming Model" to express semantics of continuous queries over data streams and tables. Our goal is to improve the understanding of system and query runtime behavior with the aim to provision queries automatically. We introduce a cost model for streaming data flow programs taking into account the two techniques of record batching and data parallelization. Additionally, we introduce optimization algorithms that leverage our model for cost-based query provisioning. The proposed Dual Streaming Model expresses the result of a streaming operator as a stream of successive updates to a result table, inducing a duality between streams and tables. Our model handles the inconsistency of the logical and the physical order of records within a data stream natively, which allows for deterministic semantics as well as low latency query execution.

Die gemeinsame Integration von Bildsensor und analoger hochparalleler Verarbeitungseinheit stellt eine Möglichkeit zur Realisierung von leistungsfähigen ein-chip Bildaufnahmesystemen dar. Die vorliegende Arbeit liefert Beiträge zum systematischen Entwurf von derartigen Systemen und analysiert bekannte und neuartige Schaltungstechniken bezüglich ihrer Eignung für deren Implementierung. Anhand des vom Autor mitentwickelten CMOS-Bildsensors mit hochparalleler analoger Bildverarbeitungseinheit werden die vorgestellten Methoden und Schaltungstechniken demonstriert. Die Problematik beim Entwurf hochparalleler analoger Systeme besteht in der im Vergleich zu digitalen Systemen geringen Automatisierbarkeit. Es ist kein top-down-Entwurf möglich, da nicht jede beliebige Funktion mit beliebiger Genauigkeit realisierbar ist. Um die jeweilige Genauigkeit der Funktionsblöcke bei der Analyse des hochparallelen Systems berücksichtigen zu können, sind rechenaufwendige Simulationen nötig. Um diesen Rechenaufwand zu senken, wird vorgeschlagen, für die Simulation des Gesamtsystems einen angepaßten Simulator und für die Analyse der schaltungstechnischen Realisierung der Funktionsblöcke konventionelleWerkzeuge für elektrische Netzwerke zu verwenden. Die beiden Simulationsdomänen werden mit Hilfe von numerischen Verhaltensmodellen verbunden. Durch diese Trennung wird die Simulation des Gesamtsystems als Bestandteil des Entwurfsflusses praktikabel. Für die Bewertung, inwieweit die zufälligen Schwankungen der Bauelementeparameter das Verhalten von Baublöcken beeinflussen, wird die Varianzanalyse als Alternative zur konventionellen Monte-Carlo-Analyse vorgeschlagen. Die Varianzanalyse ist wesentlich weniger rechenaufwendig und liefert genaue Resultate für alle Schaltungseigenschaften mit hinreichend glatten Parameterabhängigkeiten, wenn die Bauelementeparameter als normalverteilt und statistisch unabhängig angenommen werden können. Sie hat darüberhinaus den Vorteil, das Schaltungsverständnis für den Entwerfer zu erhöhen, da sofort die Bauelementeparameter mit dem größten Einfluß auf das Schaltungsverhalten identifiziert werden können. Der Vergleich verschiedener Schaltungstechniken hat gezeigt, daß zeitdiskrete wertkontinuierliche Verfahren, bei denen die Information als Strom repräsentiert wird, für die Realisierung von hochparallelen analogen Systemen besonders geeignet sind. Als besonderer Vorteil ist die weitestgehende Unabhängigkeit des Verhaltens derartiger Schaltungen von Bauelementeparametern hervorzuheben.Weitere Schaltungstechniken, deren Verhalten von zufälligen Parameterabweichungen nur wenig beeinflußt werden, sind in einer Taxonomie zusammengefaßt. Es wurde ein CMOS-Bildsensor mit hochparalleler analoger Bildverarbeitungseinheit und digitaler Ausgabe realisiert. Der current-mode-Bildsensor ist separat von der Verarbeitungseinheit angeordnet. Es wurden vier verschiedene Realisierungsmöglichkeiten untersucht und eine konventionelle integrierende voltage-mode Pixelzelle mit nachfolgendem differentiellen Spannungs- Strom-Wandler realisiert. Das Rechenfeld ist für die räumliche Faltung oder lineare Transformation von Bilddaten mit digital bereitzustellenden Koeffizienten ausgelegt. Dessen Operation basiert auf einer bit-weisen analogen Verarbeitung. Der Schaltkreis wurde erfolgreich getestet. Die nachgewiesene Bildqualität deckt sich in guter Näherung mit den bei der Simulation des Gesamtsystems getroffenen Vorhersagen / The joined implementation of an image sensor and a highly parallel analog processing unit is an advantageous approach for realizing efficient single-chip vision systems. This thesis proposes a design flow for the development of such systems. Moreover known and novel circuit techniques are analysed with respect for their suitability for the implementation of highly parallel systems. The presented methodologies and circuit techniques are demonstrated at the example of a CMOS image sensor with an embedded highly parallel analog image processing unit in whose design the author was involved. One of the major problems in designing highly parallel analog circuits is the low automation compared to the design of digital circuits. As not every function can be realized with arbitrary accuracy top-down-design is not feasible. So, when analysing the system behaviour the respective precision of each function block has to be considered. As this is a very demanding task in terms of computing power, it is proposed to use a dedicated tool for the simulation of the system and conventional network analysis tools for the inspection of the circuit realizations. Both simulation domains are combined by means of numerical behavioural models. By using separate tools system-simulations of highly parallel analog systems as a part of the design flow become practicable. Variance analysis basing on parameter sensitivities is proposed as an alternative to the conventional Monte-Carlo-analysis for investigating the influence of random device parameter variations on the system behaviour. Variance analysis requires much less computational effort while providing accurate results for all circuit properties with sufficiently smooth parameter dependencies if the random parameters can be assumed normally distributed and statistically independent. Additionally, variance analysis increases the designer’s knowledge about the circuit, as the device parameters with the highest influence on the circuit performance can immediately be identified. The comparison of various circuit techniques has shown, that sampled-time continuous-valued current-mode principles are the best choice for realizing highly parallel analog systems. A distinctive advantage of such circuits is their almost independence from device parameters. A selection of further circuit techniques with low sensitivity to random device parameter variations are summarized in a taxonomy. A CMOS image sensor with embedded highly parallel analog image processing unit has been implemented. The image sensor provides a current-mode output and is arranged separate from the processing unit. Four different possibilities for realizing an image sensor have been analysed. A conventional integrating voltage-mode pixel cell with a succeeding differential voltage- to-current-converter has been selected. The processing unit is designed for performing spatial convolution and linear transformation with externally provided digital kernels. It operates in bit-wise analog manner. The chip has been tested successfully. The measured image quality in good approximation corresponds with the estimations made with system simulations.

Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt. Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt. Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat. Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer. Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien, die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.

Die gemeinsame Integration von Bildsensor und analoger hochparalleler Verarbeitungseinheit stellt eine Möglichkeit zur Realisierung von leistungsfähigen ein-chip Bildaufnahmesystemen dar. Die vorliegende Arbeit liefert Beiträge zum systematischen Entwurf von derartigen Systemen und analysiert bekannte und neuartige Schaltungstechniken bezüglich ihrer Eignung für deren Implementierung. Anhand des vom Autor mitentwickelten CMOS-Bildsensors mit hochparalleler analoger Bildverarbeitungseinheit werden die vorgestellten Methoden und Schaltungstechniken demonstriert. Die Problematik beim Entwurf hochparalleler analoger Systeme besteht in der im Vergleich zu digitalen Systemen geringen Automatisierbarkeit. Es ist kein top-down-Entwurf möglich, da nicht jede beliebige Funktion mit beliebiger Genauigkeit realisierbar ist. Um die jeweilige Genauigkeit der Funktionsblöcke bei der Analyse des hochparallelen Systems berücksichtigen zu können, sind rechenaufwendige Simulationen nötig. Um diesen Rechenaufwand zu senken, wird vorgeschlagen, für die Simulation des Gesamtsystems einen angepaßten Simulator und für die Analyse der schaltungstechnischen Realisierung der Funktionsblöcke konventionelleWerkzeuge für elektrische Netzwerke zu verwenden. Die beiden Simulationsdomänen werden mit Hilfe von numerischen Verhaltensmodellen verbunden. Durch diese Trennung wird die Simulation des Gesamtsystems als Bestandteil des Entwurfsflusses praktikabel. Für die Bewertung, inwieweit die zufälligen Schwankungen der Bauelementeparameter das Verhalten von Baublöcken beeinflussen, wird die Varianzanalyse als Alternative zur konventionellen Monte-Carlo-Analyse vorgeschlagen. Die Varianzanalyse ist wesentlich weniger rechenaufwendig und liefert genaue Resultate für alle Schaltungseigenschaften mit hinreichend glatten Parameterabhängigkeiten, wenn die Bauelementeparameter als normalverteilt und statistisch unabhängig angenommen werden können. Sie hat darüberhinaus den Vorteil, das Schaltungsverständnis für den Entwerfer zu erhöhen, da sofort die Bauelementeparameter mit dem größten Einfluß auf das Schaltungsverhalten identifiziert werden können. Der Vergleich verschiedener Schaltungstechniken hat gezeigt, daß zeitdiskrete wertkontinuierliche Verfahren, bei denen die Information als Strom repräsentiert wird, für die Realisierung von hochparallelen analogen Systemen besonders geeignet sind. Als besonderer Vorteil ist die weitestgehende Unabhängigkeit des Verhaltens derartiger Schaltungen von Bauelementeparametern hervorzuheben.Weitere Schaltungstechniken, deren Verhalten von zufälligen Parameterabweichungen nur wenig beeinflußt werden, sind in einer Taxonomie zusammengefaßt. Es wurde ein CMOS-Bildsensor mit hochparalleler analoger Bildverarbeitungseinheit und digitaler Ausgabe realisiert. Der current-mode-Bildsensor ist separat von der Verarbeitungseinheit angeordnet. Es wurden vier verschiedene Realisierungsmöglichkeiten untersucht und eine konventionelle integrierende voltage-mode Pixelzelle mit nachfolgendem differentiellen Spannungs- Strom-Wandler realisiert. Das Rechenfeld ist für die räumliche Faltung oder lineare Transformation von Bilddaten mit digital bereitzustellenden Koeffizienten ausgelegt. Dessen Operation basiert auf einer bit-weisen analogen Verarbeitung. Der Schaltkreis wurde erfolgreich getestet. Die nachgewiesene Bildqualität deckt sich in guter Näherung mit den bei der Simulation des Gesamtsystems getroffenen Vorhersagen / The joined implementation of an image sensor and a highly parallel analog processing unit is an advantageous approach for realizing efficient single-chip vision systems. This thesis proposes a design flow for the development of such systems. Moreover known and novel circuit techniques are analysed with respect for their suitability for the implementation of highly parallel systems. The presented methodologies and circuit techniques are demonstrated at the example of a CMOS image sensor with an embedded highly parallel analog image processing unit in whose design the author was involved. One of the major problems in designing highly parallel analog circuits is the low automation compared to the design of digital circuits. As not every function can be realized with arbitrary accuracy top-down-design is not feasible. So, when analysing the system behaviour the respective precision of each function block has to be considered. As this is a very demanding task in terms of computing power, it is proposed to use a dedicated tool for the simulation of the system and conventional network analysis tools for the inspection of the circuit realizations. Both simulation domains are combined by means of numerical behavioural models. By using separate tools system-simulations of highly parallel analog systems as a part of the design flow become practicable. Variance analysis basing on parameter sensitivities is proposed as an alternative to the conventional Monte-Carlo-analysis for investigating the influence of random device parameter variations on the system behaviour. Variance analysis requires much less computational effort while providing accurate results for all circuit properties with sufficiently smooth parameter dependencies if the random parameters can be assumed normally distributed and statistically independent. Additionally, variance analysis increases the designer’s knowledge about the circuit, as the device parameters with the highest influence on the circuit performance can immediately be identified. The comparison of various circuit techniques has shown, that sampled-time continuous-valued current-mode principles are the best choice for realizing highly parallel analog systems. A distinctive advantage of such circuits is their almost independence from device parameters. A selection of further circuit techniques with low sensitivity to random device parameter variations are summarized in a taxonomy. A CMOS image sensor with embedded highly parallel analog image processing unit has been implemented. The image sensor provides a current-mode output and is arranged separate from the processing unit. Four different possibilities for realizing an image sensor have been analysed. A conventional integrating voltage-mode pixel cell with a succeeding differential voltage- to-current-converter has been selected. The processing unit is designed for performing spatial convolution and linear transformation with externally provided digital kernels. It operates in bit-wise analog manner. The chip has been tested successfully. The measured image quality in good approximation corresponds with the estimations made with system simulations.

Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt. Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt. Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat. Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer. Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien, die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.