Chemnitz, Techn. Univ., Diplomarb., 2001.

Universiẗat, Diss., 2002--Dortmund. / Gedr. Ausg. im Logos-Verl., Berlin.

Der Einsatz von Multicore-Prozessoren in der industriellen Steuerungstechnik birgt sowohl Chancen als auch Risiken. Die vorliegende Dissertation entwickelt und bewertet aus diesem Grund generische Strategien zur Nutzung dieser Prozessorarchitektur unter Berücksichtigung der spezifischen Rahmenbedingungen und Anforderungen dieser Domäne. Multicore-Prozessoren bieten die Chance zur Konsolidierung derzeit auf dedizierter Hardware ausgeführter heterogener Steuerungssubsysteme unter einer bisher nicht erreichbaren temporalen Isolation. In diesem Kontext definiert die vorliegende Dissertation die spezifischen Anforderungen, die eine integrierte Ausführung in der Domäne der industriellen Automatisierung erfüllen muss. Eine Vorbedingung für ein derartiges Szenario stellt allerdings der Einsatz einer geeigneten Konsolidierungslösung dar. Mit einem virtualisierten und einem hybriden Konsolidierungsansatz werden deshalb zwei repräsentative Lösungen für die Domäne eingebetteter Systeme vorgestellt, die schließlich hinsichtlich der zuvor definierten Kriterien evaluiert werden. Da die Taktraten von Prozessoren physikalische Grenzen erreicht haben, werden sich in der Steuerungstechnik signifikante Performanzsteigerungen zukünftig nur durch den Einsatz von Multicore-Prozessoren erzielen lassen. Dies hat zur Vorbedingung, dass die Firmware die Parallelität dieser Prozessorarchitektur in geeigneter Weise zu nutzen vermag. Leider entstehen bei der Parallelisierung eines komplexen Systems wie einer Automatisierungs-Firmware im Allgemeinen signifikante Aufwände. Infolgedessen sollten diesbezügliche Entscheidungen nur auf Basis einer objektiven Abwägung potentieller Alternativen getroffen werden. Allerdings macht die Systemkomplexität eine Abschätzung der durch eine spezifische parallele Firmware-Architektur zu erwartenden Performanz zu einer anspruchsvollen Aufgabe. Dies gilt vor allem, da eine Parallelisierung gefordert wird, die für eine Vielzahl von Lastszenarien in Form gesteuerter Maschinen geeignet ist. Aus diesem Grund spezifiziert die vorliegende Dissertation eine anwendungsorientierte Methode zur Unterstützung von Entwurfsentscheidungen, die bei der Migration einer bestehenden Singlecore-Firmware auf eine homogene Multicore-Architektur zu treffen sind. Dies wird erreicht, indem in automatisierter Weise geeignete Firmware-Modelle auf Basis von dynamischem Profiling der Firmware unter mehreren repräsentativen Lastszenarien erstellt werden. Im Anschluss daran werden diese Modelle um das Expertenwissen von Firmware-Entwicklern erweitert, bevor mittels multikriterieller genetischer Algorithmen der Entwurfsraum der Parallelisierungsalternativen exploriert wird. Schließlich kann eine spezifische Lösung der auf diese Weise hergeleiteten Pareto-Front auf Basis ihrer Bewertungsmetriken zur Implementierung durch einen Entwickler ausgewählt werden. Die vorliegende Arbeit schließt mit einer Fallstudie, welche die zuvor beschriebene Methode auf eine numerische Steuerungs-Firmware anwendet und dabei deren Potential für eine umfassende Unterstützung einer Firmware-Parallelisierung aufzeigt. / The application of multi-core CPUs in industrial control technology holds chances as well as risks. Consequently, this thesis develops and evaluates generic strategies for using this processor architecture in due consideration of the specific framework conditions and demands of this domain. Multi-core CPUs offer the chance of consolidating heterogeneous control subsystems currently running on dedicated hardware devices while maintaining a degree of temporal isolation in between them that has been unattainable so far. In this context, this thesis defines the specific demands an integrated execution has to meet in the domain of industrial automation. However, one precondition to this scenario is the use of an appropriate consolidation solution. Thus, two representative solutions for the domain of embedded systems are presented in terms of a virtualized and a hybrid consolidation approach, before being finally evaluated with regard to the previously defined criteria. As CPU clock rates have reached physical boundaries, significant future performance gains in the domain of control technology will only be achieved by the application of multi-core CPUs. As a precondition, the firmware has to exploit the parallelism of this processor architecture in an appropriate manner. Unfortunately, for a sophisticated system like an automation firmware, a parallelization commonly induces significant efforts. Thus, decisions in this regard should only be made on the basis of an objective consideration of potential alternatives. However, an estimation of a specific parallel firmware design's prospective performance is challenging due to the system's complexity. This is particularly true, as a parallelization is required that fits a variety of load scenarios in terms of the machines being controlled. Thus, this thesis specifies an application-oriented method that supports the design decisions to be taken when migrating an existing single-core firmware to a homogeneous multi-core architecture. This is achieved by automatically building adequate firmware models based on dynamic firmware profiling under multiple representative load scenarios. These models are then enhanced by the firmware developers' expert knowledge before multi-objective genetic algorithms are applied for exploring the design space of parallelization alternatives. Finally, a specific solution from the retrieved Pareto front can be selected on basis of its evaluation metrics for an implementation by a developer. This thesis concludes with a case study that applies the aforementioned method to a numerical control firmware and thereby reveals its potential of supporting a firmware parallelization in a comprehensive way.

In the recent past, the field of scientific computing has become of more and more importance for scientific as well as for industrial research, playing a comparable role as experiment and theory do. This success of computational methods in scientific and engineering research is next to the enormous improvement of computer hardware to a large extend due to contributions from applied mathematicians, who have developed algorithms which make real life applications feasible. Examples are adaptive methods, high order discretization, fast linear and non-linear solvers and multi-level methods. The application of these methods in a large class of problems demands for suitable and robust tools for a flexible and efficient implementation. In order to play a crucial role in scientific and engineering research, besides efficiency in the numerical solution, also efficiency in problem setup and interpretation of simulation results is of utmost importance. As modeling and computing comes closer together, efficient computational methods need to be applied to new sets of equations. The problems to be addressed by simulation methods become more and more complicated, ranging over different scales, interacting on different dimensions and combining different physics. Such problems need to be implemented in a short period of time, solved on complicated domains and visualized with respect to the demand of the user. %Only a modular abstract simulation environment will fulfill these requirements and allow to setup, solve and visualize real-world problems appropriately. In this work, the concepts and the design of the C++ finite element toolbox AMDiS (adaptive multidimensional simulations) are described. It is shown, how abstract data structures and modern software concepts can help to design user-friendly finite element software, which provides large flexibility in problem definition while on the other hand efficiently solves these problems. Also systems of coupled problems can be solved in an intuitive way. In order to demonstrate its possibilities, AMDiS has been applied to several non-standard problems. The most time-consuming part in most simulations is the solution of linear systems of equations. Multi-level methods use discretization hierarchies to solve these systems in a very efficient way. In AMDiS, such multi-level techniques are implemented in the context of adaptive finite elements. Several numerical results are given which compare this multigrid solver with classical iterative methods. Besides the development of more efficient algorithms also the growing hardware capabilities lead to an improvement of simulation possibilities. Modern computing clusters contain more and more processors and also personal computers today are often equipped with multi-core processors. In this work, a new parallelization approach has been developed which allows the parallelization of sequential code in a very easy way and reduces the communication overhead compared to classical parallelization concepts.

Gegenstand der vorliegenden Arbeit sind Verfahren für große freie und restringierte Minimierungsprobleme. Dabei wird der Ansatz verfolgt, mit Hilfe des Raumzerlegungkonzepts Verfahren mit einer immanenten parallelen Struktur zu entwerfen, die damit zu grobkörnig parallelisierbaren Algorithmen führen.

The paper "Parallel Genetic Algorithms" discusses the theoretical basics of Evolutionary Algorithms concentrating on Genetic Algorithms. Possibilities for a parallelization of these algorithms are examined and explained on the basis of concepts of parallel programming. A concrete suggestion for a practical realization of a parallel Genetic Algorithm at different levels of complexity is presented. / Die Studienarbeit zum Thema "Parallele Genetische Algorithmen" befasst sich mit den theoretischen Grundlagen Evolutionärer Algorithmen, wobei die Konzentration bei Genetischen Algorithmen liegt, und untersucht die Möglichkeiten einer parallelen Realisierung dieser Algorithmen. Des weiteren werden Konzepte der Parallelen Programmierung diskutiert sowie ein konkreter Vorschlag zur praktischen Realisierung eines parallelen Genetischen Algorithmus' auf verschiedenen Komplexitätsebenen vorgestellt.

Es werden die Möglichkeiten zur Parallelisierung des Algorithmus zum Indexaufbau im ICIx System untersucht. Ausgehend von der Vorstellung dieses Algorithmus erfolgt zuerst die Erläuterung des verwendeten Kostenmodells. Nach einer Zerlegung des gesamten Trainingsprozesses in Teilschritte werden diese hinsichtlich der zu erwartenden Beschleunigung des Trainings untersucht.

The diploma thesis with the subject ¨Parallel Genetic Algorithms with Applications¨ deals with the parallelization of Genetic Algorithms for the creation of efficient optimization methods especially for simulation based application problems. First, an introduction to Genetic Algorithms and an overview of possible parallelization approaches as well as already published results of research are given. This is followed by a detailed explanation of the conception and realization of own Parallel Genetic Algorithms. The paper is rounded off by an particularized description of the results of extensive test runs on the Chemnitzer Linux-Cluster (CLiC). / Die Diplomarbeit zum Thema ¨Parallele Genetische Algorithmen mit Anwendungen¨ befasst sich mit der Parallelisierung Genetischer Algorithmen zur Erzeugung effizienter Optimierungsverfahren für insbesondere simulationsbasierte Anwendungsprobleme. Zunächst werden eine Einführung in Genetische Algorithmen sowie ein Überblick über mögliche Parallelisierungsansätze und bereits veröffentlichte Forschungsergebnisse gegeben. Dem schließt sich eine detaillierte Erläuterung der Konzeption und Umsetzung eigener Paralleler Genetischer Algorithmen an. Abgerundet wird die Arbeit durch eine ausführliche Darstellung der Ergebnisse umfangreicher Testläufe auf dem Chemnitzer Linux-Cluster (CLiC).

We address the important field of large scale matrix based algorithms in control and model order reduction. Many important tools from theory and applications in systems theory have been widely ignored during the recent decades in the context of PDE constraint optimal control problems and simulation of electric circuits. Often this is due to the fact that large scale matrices are suspected to be unsolvable in large scale applications. Since around 2000 efficient low rank theory for matrix equation solvers exists for sparse and also data sparse systems. Unfortunately upto now only incomplete or experimental Matlab implementations of most of these solvers have existed. Here we aim on the implementation of these algorithms in a higher programming language (in our case C) that allows for a high performance solver for many matrix equations arising in the context of large scale standard and generalized state space systems. We especially focus on efficient memory saving data structures and implementation techniques as well as the shared memory parallelization of the underlying algorithms.

Software packages for the numerical solution of partial differential equations (PDEs) using the finite element method are important in different fields of research. The basic data structures and algorithms change in time, as the user\'s requirements are growing and the software must efficiently use the newest highly parallel computing systems. This is the central point of this work. To make efficiently use of parallel computing systems with growing number of independent basic computing units, i.e.~CPUs, we have to combine data structures and algorithms from different areas of mathematics and computer science. Two crucial parts are a distributed mesh and parallel solver for linear systems of equations. For both there exists multiple independent approaches. In this work we argue that it is necessary to combine both of them to allow for an efficient and scalable implementation of the finite element method. First, we present concepts, data structures and algorithms for distributed meshes, which allow for local refinement. The central point of our presentation is to provide arbitrary geometrical information of the mesh and its distribution to the linear solver. A large part of the overall computing time of the finite element method is spend by the linear solver. Thus, its parallelization is of major importance. Based on the presented concept for distributed meshes, we preset several different linear solver methods. Hereby we concentrate on general purpose linear solver, which makes only little assumptions about the systems to be solver. For this, a new FETI-DP (Finite Element Tearing and Interconnect - Dual Primal) method is proposed. Those the standard FETI-DP method is quasi optimal from a mathematical point of view, its not possible to implement it efficiently for a large number of processors (> 10,000). The main reason is a relatively small but globally distributed coarse mesh problem. To circumvent this problem, we propose a new multilevel FETI-DP method which hierarchically decompose the coarse grid problem. This leads to a more local communication pattern for solver the coarse grid problem and makes it possible to scale for a large number of processors. Besides the parallelization of the finite element method, we discuss an approach to speed up serial computations of existing finite element packages. In many computations the PDE to be solved consists of more than one variable. This is especially the case in multi-physics modeling. Observation show that in many of these computation the solution structure of the variables is different. But in the standard finite element method, only one mesh is used for the discretization of all variables. We present a multi-mesh finite element method, which allows to discretize a system of PDEs with two independently refined meshes. / Softwarepakete zur numerischen Lösung partieller Differentialgleichungen mit Hilfe der Finiten-Element-Methode sind in vielen Forschungsbereichen ein wichtiges Werkzeug. Die dahinter stehenden Datenstrukturen und Algorithmen unterliegen einer ständigen Neuentwicklung um den immer weiter steigenden Anforderungen der Nutzergemeinde gerecht zu werden und um neue, hochgradig parallel Rechnerarchitekturen effizient nutzen zu können. Dies ist auch der Kernpunkt dieser Arbeit. Um parallel Rechnerarchitekturen mit einer immer höher werdenden Anzahl an von einander unabhängigen Recheneinheiten, z.B.~Prozessoren, effizient Nutzen zu können, müssen Datenstrukturen und Algorithmen aus verschiedenen Teilgebieten der Mathematik und Informatik entwickelt und miteinander kombiniert werden. Im Kern sind dies zwei Bereiche: verteilte Gitter und parallele Löser für lineare Gleichungssysteme. Für jedes der beiden Teilgebiete existieren unabhängig voneinander zahlreiche Ansätze. In dieser Arbeit wird argumentiert, dass für hochskalierbare Anwendungen der Finiten-Elemente-Methode nur eine Kombination beider Teilgebiete und die Verknüpfung der darunter liegenden Datenstrukturen eine effiziente und skalierbare Implementierung ermöglicht. Zuerst stellen wir Konzepte vor, die parallele verteile Gitter mit entsprechenden Adaptionstrategien ermöglichen. Zentraler Punkt ist hier die Informationsaufbereitung für beliebige Löser linearer Gleichungssysteme. Beim Lösen partieller Differentialgleichung mit der Finiten Elemente Methode wird ein großer Teil der Rechenzeit für das Lösen der dabei anfallenden linearen Gleichungssysteme aufgebracht. Daher ist deren Parallelisierung von zentraler Bedeutung. Basierend auf dem vorgestelltem Konzept für verteilten Gitter, welches beliebige geometrische Informationen für die linearen Löser aufbereiten kann, präsentieren wir mehrere unterschiedliche Lösermethoden. Besonders Gewicht wird dabei auf allgemeine Löser gelegt, die möglichst wenig Annahmen über das zu lösende System machen. Hierfür wird die FETI-DP (Finite Element Tearing and Interconnect - Dual Primal) Methode weiterentwickelt. Obwohl die FETI-DP Methode vom mathematischen Standpunkt her als quasi-optimal bezüglich der parallelen Skalierbarkeit gilt, kann sie für große Anzahl an Prozessoren (> 10.000) nicht mehr effizient implementiert werden. Dies liegt hauptsächlich an einem verhältnismäßig kleinem aber global verteilten Grobgitterproblem. Wir stellen eine Multilevel FETI-DP Methode vor, die dieses Problem durch eine hierarchische Komposition des Grobgitterproblems löst. Dadurch wird die Kommunikation entlang des Grobgitterproblems lokalisiert und die Skalierbarkeit der FETI-DP Methode auch für große Anzahl an Prozessoren sichergestellt. Neben der Parallelisierung der Finiten-Elemente-Methode beschäftigen wir uns in dieser Arbeit mit der Ausnutzung von bestimmten Voraussetzung um auch die sequentielle Effizienz bestehender Implementierung der Finiten-Elemente-Methode zu steigern. In vielen Fällen müssen partielle Differentialgleichungen mit mehreren Variablen gelöst werden. Sehr häufig ist dabei zu beobachten, insbesondere bei der Modellierung mehrere miteinander gekoppelter physikalischer Phänomene, dass die Lösungsstruktur der unterschiedlichen Variablen entweder schwach oder vollständig voneinander entkoppelt ist. In den meisten Implementierungen wird dabei nur ein Gitter zur Diskretisierung aller Variablen des Systems genutzt. Wir stellen eine Finite-Elemente-Methode vor, bei der zwei unabhängig voneinander verfeinerte Gitter genutzt werden können um ein System partieller Differentialgleichungen zu lösen.