Contents

Abstract

The ongoing miniaturization in the semiconductor industry is based on shorter production cycles and increasingly complex device and process designs. To sustain this development numerical discretization based simulations play a major role replacing expensive and time-consuming experimental evaluations. The simulation domain is discretized using a mesh, forming the basis for the subsequent numerical solution of the underlying physical models. However, it is often necessary to adapt the initially generated mesh, for example, to increase the simulation accuracy in regions of interest. This mesh adaptation step often poses a computational bottleneck and parallel mesh adaptation algorithms are needed to speed up the process.
In computational science it is particularly attractive to model complex processes and relationships using graphs, as their abstraction level enables to investigate and develop efficient solutions to computational problems, such as parallel algorithms. A graph formulation of a meshing problem provides one way of parallelizing a meshing workflow: Different regions of a mesh (e.g., materials) and their adjacency relationships can be modeled with such a graph. Subsequently applying graph coloring algorithms yields independent sets of these mesh regions, which can be safely adapted in parallel avoiding race conditions. Therefore, as a first step, this work investigates available graph coloring algorithms with respect to their computational performance and solution quality. It is shown that shared-memory parallel graph coloring algorithms produce equally well-suited results for the subsequently presented techniques as serial algorithms while being about 24 times faster using 64 threads.
These graph coloring algorithms are a key strategy for alleviating the mesh adaptation bottleneck. Therefore, they form the basis of a developed novel coarse-grained shared-memory parallel mesh adaptation framework. It is based on the decomposition of the initial mesh into numerous partitions which are subsequently assigned to independent sets. The different partitions are refined in parallel using two different serial mesh adaptation algorithms: A template-based and a Delaunay-based approach yielding a maximum speedup of 8.6 using 16 threads.
In a third and final step, the computational performance of a typical process simulation is improved by applying a decomposition approach for surface meshes. The presented method focuses on the performance of the flux calculation step in a typical etching simulation and is based on an iterative generation of a so-called sparse set of surface mesh cells, with a higher cell density in specific regions of interest. Using this new method a relative speedup of about seven compared to the full evaluation method on all surface mesh cells is obtained.

Kurzfassung

Die fortschreitende Miniaturisierung in der Halbleiterindustrie basiert auf kürzeren Produktionszyklen und immer komplexeren Bauteil- und Prozessdesigns. Um diese Entwicklung aufrechtzuerhalten spielen numerische, diskretisierungsbasierte Simulationen eine wichtige Rolle, welche teure und zeitaufwendige experimentelle Auswertungen zu ersetzen. Das Simulationsgebiet wird mit einem Gitter diskretisiert, das die Grundlage für die anschließende numerische Lösung der zugrunde liegenden physikalischen Modelle bildet. Häufig ist es jedoch notwendig, das ursprünglich generierte Gitter anzupassen, um zum Beispiel die Simulationsgenauigkeit in besonders interessanten Regionen zu erhöhen. Dieser Gitteradaptionsschritt stellt oft einen rechnerischen Flaschenhals dar und es werden parallele Gitteradaptierungssalgorithmen benötigt um den Prozess zu beschleunigen.
In der rechnergestützten Wissenschaft ist es besonders attraktiv komplexe Prozesse und Beziehungen mit Hilfe von Graphen zu modellieren, da ihre Abstraktionsebene es ermöglicht effiziente Lösungen für Rechenprobleme zu untersuchen und zu entwickeln, wie zum Beispiel parallele Algorithmen. Eine Formulierung eines Gittererzeugungsproblems mittels eines Graphen bietet eine Möglichkeit den Gittererzeugungsprozess zu parallelisieren: Verschiedene Regionen eines Gitters (zum Beispiel Materialien) und deren Nachbarschaftsbeziehungen können mit einem Graphen modelliert werden. Die anschließende Anwendung von Algorithmen zur Graphenfärbung ergibt unabhängige Mengen dieser Gitterregionen, die sicher parallel adaptiert werden können ohne in Wettlaufsituationen zu geraten. Daher untersucht diese Arbeit in einem ersten Schritt verfügbare Algorithmen zur Graphenfärbung in Bezug auf ihre Performanz und Lösungsqualität. Es wird gezeigt, dass shared-memory Algorithmen zur parallelen Graphenfärbung ebenso gut geeignete Ergebnisse für die nachfolgend vorgestellten Techniken wie serielle Algorithmen liefern und etwa 24-Mal schneller bei 64 threads sind.
Diese Algorithmen zur Graphenfärbung sind eine Schlüsselstrategie zur Umgehung des Engpasses der Gitteradaptierung. Daher bilden sie die Grundlage für ein neu entwickeltes grob-granulares Programmiergerüst zur shared-memory parallelen Gitteradaptierung. Es basiert auf der Zerlegung des anfänglichen Gitters in mehrere Partitionen, die anschließend in unabhängige Mengen aufgeteilt werden. Die unterschiedlichen Partitionen werden parallel mit zwei verschiedenen seriellen Gitteradaptierungsalgorithmen verfeinert: einem vorlagen-basierten und einem Delaunay-basierten Ansatz, die eine maximale Beschleunigung von 8.6 mit 16 threads ermöglichen.
Schließlich und in einem dritten und letzten Schritt wird die Performanz einer typischen Prozesssimulation in dieser Arbeit verbessert, indem ein Zerlegungsansatz für Oberflächengitter angewendet wird. Das vorgestellte Verfahren konzentriert sich auf die Performanz des Flussberechnungsschrittes in einer typischen Ätzsimulation und basiert auf einer iterativen Erzeugung einer so genannten "dünnen Menge" von Oberflächengitterzellen mit einer höheren Zelldichte in Regionen von größerem Interesse. Mit dieser neuen Methode wird eine relative Beschleunigung von etwa sieben im Vergleich zur Berechnungsmethode mit allen Oberflächengitterzellen erreicht.