{"id":12711,"date":"2021-02-28T23:32:35","date_gmt":"2021-02-28T22:32:35","guid":{"rendered":"https:\/\/blog.mi.hdm-stuttgart.de\/?p=12711"},"modified":"2023-06-18T18:05:36","modified_gmt":"2023-06-18T16:05:36","slug":"effiziente-last-abarbeitung","status":"publish","type":"post","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2021\/02\/28\/effiziente-last-abarbeitung\/","title":{"rendered":"Effiziente Last-Abarbeitung"},"content":{"rendered":"\n<p><span style=\"color:#728390\" class=\"has-inline-color\">Geschrieben von Steffen K\u00f6hler und Laurin Keim.<\/span><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Einleitung<\/h2>\n\n\n\n<p>Bei dem vorliegenden Block-Post handelt es sich um den Zusammenschrieb eines Studentenprojekts mit dem Motto \u201cLast effizient abarbeiten\u201d. In diesem wurden verschiedene Vorgehensweisen, Protokolle und in gewissem Ma\u00dfe auch Hardware-Architekturen erarbeitet und nachvollzogen. Dabei wurden teilweise eigene Vorgehensweisen erdacht und anschlie\u00dfend mit bereits bestehenden Protokollen verglichen.<\/p>\n\n\n\n<p>W\u00e4hrend des Projekts kamen immer wieder neue Fragestellungen auf, deren Beantwortung zu neuen Themen und Fragen gef\u00fchrt haben. Die Themengebiete, die schlussendlich behandelt worden sind, lassen sich in groben Z\u00fcgen in folgender Grafik auff\u00fchren.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/DdOQ4v8k_Ow6hgMbOceRaY6NArvaqhHf4A7w7VfSWjXE6R7FE1Wh6venqya80xwX-kFdYnqVU9RgBP1fOf4SGJlrsVbtP9clJGMlBpFyF86n4NMlFGB63CFT5tqbqNk3NA\" width=\"602\" height=\"931\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 1: Ein \u00dcberblick \u00fcber die behandelten Themen w\u00e4hrend des Semesters, aufgef\u00e4chert nach Themengebieten.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">I\/O-Boundaries<\/h2>\n\n\n\n<p>M\u00f6chte man Last effizient abarbeiten, so gilt es zun\u00e4chst die grunds\u00e4tzlichen Vorg\u00e4nge in einem Rechner n\u00e4her zu beleuchten, um diese Vorg\u00e4nge anschlie\u00dfend so effizient wie m\u00f6glich zu optimieren.<\/p>\n\n\n\n<p>F\u00fchrt man in einem Computer eine bestimmte Software aus, so wird diese zun\u00e4chst in Maschinensprache \u00fcbersetzt. Laut [44] ist ein Computer somit einfach ausgedr\u00fcckt Software, die der Hardware sagt, was sie tun soll. Auf einem g\u00e4ngigen Computer l\u00e4uft nat\u00fcrlich nicht nur ein einzelner Thread (Ausf\u00fchrungsstrang in der Abarbeitung eines Computerprogramms \/ unabh\u00e4ngiger Teil eines Prozesses. Eine genauere Beschreibung folgt im Abschnitt &#8220;Thread&#8221;). Neben den Anwendungen, die vom Nutzer bewusst gestartet wurden, l\u00e4uft das Betriebssystem sowie unz\u00e4hlige, im Hintergrund laufende Anwendungen. Dabei werden diese Threads nicht parallel abgearbeitet. Stattdessen wechselt der Prozessor sehr schnell zwischen den Anwendungen hin und her, was eine gef\u00fchlte Parallelit\u00e4t erm\u00f6glicht.<\/p>\n\n\n\n<p>S\u00e4mtliche Vorg\u00e4nge, die Kommunikation mit externen System ben\u00f6tigen, k\u00f6nnen als I\/O-Operationen bezeichnet werden. [43] Als Beispiele lassen sich hierbei der Aufruf eines Web-Services, die Interaktion mit einer Datenbank oder eben auch einfach die Interaktion mit dem File-System auff\u00fchren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">I\/O-Bottleneck<\/h3>\n\n\n\n<p>Ausgehend von den gegebenen Informationen k\u00f6nnte man davon ausgehen, dass die CPU (Central Processing Unit) der begrenzende Faktor bez\u00fcglich der Geschwindigkeit eines Rechners ist. In den vergangenen Jahrzehnten hat sich jedoch die Leistung von Prozessoren in regelm\u00e4\u00dfigen Abst\u00e4nden verdoppelt [40]. Das Mooresche Gesetz besagt diesbez\u00fcglich genauer, dass sich die Komplexit\u00e4t integrierter Schaltkreise mit minimalen Komponentenkosten regelm\u00e4\u00dfig verdoppelt, je nach Quelle alle 12, 18 oder 24 Monate.&nbsp;<\/p>\n\n\n\n<p>Mit dieser rasanten Verbesserung der Prozessorleistung konnten die Komponenten, welche f\u00fcr den Input bzw. den Output von Daten verantwortlich sind, nicht mithalten.&nbsp;<\/p>\n\n\n\n<p>Laut [35] hat sich die CPU-Performance innerhalb der Jahre 2004-2008 etwa verzehnfacht. Im gleichen Zeitraum wurde die Memory-Bandbreite am Beispiel von Intel von 4.3 GB\/s auf 40 GB\/s angehoben, was ebenfalls in etwa einer Verzehnfachung entspricht. Im Gegensatz dazu wurde die Geschwindigkeit des PCIe-bus (Peripheral Component Interface express, eine interne Schnittstelle f\u00fcr Erweiterungskarten in Computer-Systemen) von 250 MB\/sec pro Leitung auf 500 MB\/sec pro Leitung erh\u00f6ht, was einer Verdoppelung entspricht.&nbsp;<\/p>\n\n\n\n<p>Diese Zahlen verdeutlichen, dass keine der Komponenten mit der rasanten Entwicklung der CPUs mithalten kann. Anders ausgedr\u00fcckt ist der Datenzugriff grunds\u00e4tzlich langsamer als die Datenverarbeitung.&nbsp;<\/p>\n\n\n\n<p>Unterschiedlicher Quellen zufolge ist I\/O in 80-90% aller Anwendungsf\u00e4lle der begrenzende Faktor. Diese Problematik ist allerdings nicht alleine auf die Hardware zur\u00fcckzuf\u00fchren. Das Standard-Protokoll POSIX bietet hier im Grunde keine Optimierungsm\u00f6glichkeiten, worauf im folgenden Abschnitt kurz eingegangen werden soll.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">POSIX &#8211; Portable Operating System Interface<\/h3>\n\n\n\n<p>POSIX steht f\u00fcr Portable Operating System Interface. Wie [11] zu entnehmen ist, handelt es sich dabei um eine standardisierte Programmierschnittstelle, welche die Schnittstelle zwischen Anwendungssoftware und Betriebssystem darstellt. Es basiert auf Unix-Betriebssystemen, da es als Herstellerneutral gilt.<\/p>\n\n\n\n<p>POSIX erm\u00f6glicht es dem Programmier, Data-Streams zu \u00f6ffnen und somit Daten zu lesen und zu schreiben. Es stehen also unter anderem Systembefehle wie read, write, open und close zur Verf\u00fcgung, viel mehr M\u00f6glichkeiten bietet POSIX allerdings nicht. Somit gibt es keine M\u00f6glichkeiten den entsprechenden Daten Hinweise anzuh\u00e4ngen, die beispielsweise auf ein sequentielles Lesen der Datei hinweisen. Ebenso w\u00e4re es denkbar Daten entsprechend zu markieren, wenn sich vorher absehen l\u00e4sst, dass diese \u00fcberschrieben werden k\u00f6nnten. Mit diesen oder \u00e4hnlichen Verfahren k\u00f6nnte man den Datenverkehr durchaus effizienter gestalten, es gibt allerdings kein Standardverfahren welches diese Vorg\u00e4nge erm\u00f6glicht.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">I\/O-Problematik &#8211; Austausch des kompletten Stacks?<\/h3>\n\n\n\n<p>Die Tatsache, dass I\/O grunds\u00e4tzlich von der CPU-Leistung \u00fcbertroffen wird, l\u00e4sst die Frage aufkommen, weshalb die Situation sich nicht l\u00e4ngst ge\u00e4ndert hat.&nbsp;<\/p>\n\n\n\n<p>Die Antwort hierauf liegt in der Komplexit\u00e4t das Datenpfades. Die Verbesserung einer Komponente in der Struktur wie beispielsweise des PCIe-Busses \u00e4ndert an der Gesamtperformance nichts. Solange auch nur eine Komponente der Struktur den Datenfluss bremst, hat man im gesamten System nichts gewonnen.&nbsp;<\/p>\n\n\n\n<p>Alle einzelnen Komponenten auszutauschen ist wiederum \u00e4u\u00dferst schwierig, da keine Firma das gesamte System baut. Eine Architektur abseits des Standards wie PCIe oder SAS zu bauen ist schlichtweg zu kostspielig.<\/p>\n\n\n\n<p>Eine der Komponenten, welche sich vergleichsweise einfach austauschen bzw. erg\u00e4nzen l\u00e4sst, ist die Festplatte. Auch im Consumer-Bereich wird beim Kauf neuer Hardware gro\u00dfer Wert auf SSD-Festplatten als Erg\u00e4nzung oder Ersatz von herk\u00f6mmlichen Festplatten gelegt. Der tats\u00e4chliche Performance-Gewinn soll im folgenden Kapitel durch ein eigenes Experiment \u00fcberpr\u00fcft und gemessen werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Experiment &#8211; HDD vs. SSD<\/h3>\n\n\n\n<p>Die Idee beim folgenden Experiment ist denkbar einfach. Genutzt wurde ein Computer, in dem sowohl eine HDD als auch eine SDD-Festplatte verbaut ist. Es sollen die gleichen Daten auf beide Platten geschrieben bzw. gelesen werden. Implementiert wurde dieser Test in C++. Die Zeiten werden dabei durch den folgenden Programmcode gemessen:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh3.googleusercontent.com\/uzEqY2UZaZ_Vfv_FDteivsZ_jo_wPu9Ivp9Bsq5DsZkMcX8tfHTC8KeoHh9RQyZBMe-n9VJTVLesZiHbQxCb1Ulr0ZC89xrWnpT2GXVevNTKiHCLpStXxnMiKYkurQQREg\" width=\"757\" height=\"449\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 2: C++ Code, welcher eine Timer-Klasse erzeugt, mit dessen Hilfe sich Zeitmessungen durchf\u00fchren lassen.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Einfache Text-Dateien<\/h3>\n\n\n\n<p>Es wurden zun\u00e4chst einfache Text-Dateien generiert, in denen sich zuf\u00e4llige Zahlenwerte befinden. Diese Dateien wurden einmal auf der SSD und einmal auf der HDD-Festplatte abgelegt. Wie der folgenden Tabelle zu entnehmen ist, wurde hinsichtlich der Anzahl der Dateien sowie der beinhalteten Zufallszahlen variiert. Es ergaben sich die folgenden Messungen:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Anzahl Dateien<\/strong><\/td><td><strong>Anzahl Zufallszahlen pro Datei<\/strong><\/td><td><strong>Zugriffszeit HDD<\/strong><\/td><td><strong>Zugriffszeit SSD<\/strong><\/td><td><strong>Verh\u00e4ltniswerte<\/strong><\/td><\/tr><tr><td>100<\/td><td>10.000<\/td><td>293 ms<\/td><td>308 ms<\/td><td>105,12%<\/td><\/tr><tr><td>100<\/td><td>100.000<\/td><td>3405 ms<\/td><td>3546 ms<\/td><td>104,14%<\/td><\/tr><tr><td>1<\/td><td>10.000.000<\/td><td>2918 ms<\/td><td>3319 ms<\/td><td>113,74%<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 1: Zeitmessungen von Lesevorg\u00e4ngen von SSD- und HDD-Festplatten im Vergleich. Das Ergebnis entspricht nicht der Erwartungshaltung.<\/figcaption><\/figure>\n\n\n\n<p>Die Zugriffszeiten der SSD waren in diesem Experiment l\u00e4nger, als die der HDD-Festplatte. Dies widerspricht den Recherchen und unserer Erwartungshaltung. Offensichtlich wurden beim Experiment einige Faktoren nicht ber\u00fccksichtigt.<\/p>\n\n\n\n<p>Es wurde daher vermutet, dass die entsprechenden Daten bereits in irgendeiner Form gecached worden sind. Das Experiment wurde daher einige Male wiederholt. Unter anderem wurde die Messung direkt nach dem Neustart des Rechners durchgef\u00fchrt, um ein Caching m\u00f6glichst auszuschlie\u00dfen. Das Ergebnis der Messung hat sich jedoch nicht ge\u00e4ndert.&nbsp;<\/p>\n\n\n\n<p>Nach einigen weiteren Recherchen und Gespr\u00e4chen sind wir auf den sogenannten Standby-Cache von Windows aufmerksam geworden. Es handelt sich hierbei um einen Speicherbereich im RAM, den Windows mit h\u00e4ufig verwendeten Daten f\u00fcllt. Der Standby-Cache l\u00e4sst sich unter Windows einsehen, indem man im Taskmanager auf &#8220;Ressourcenmonitor&#8221; klickt. Unter dem Reiter \u201cArbeitsspeicher\u201d ist dann eine grafische sowie eine tabellarische Anzeige vorhanden, die Aufschluss \u00fcber die im Arbeitsspeicher befindlichen Daten geben. In der vorliegenden Abbildung befinden sich aktuelle 3499 MB im Standby-Cache.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/YlyetOfb5vFkbLgr2n34kdJOb8z8F-strlq5jgMcHoFx3xMLAHFajfmYYbHFlW1vedNzNc5S3dyRg-HGCYYpJ3En8Zevt_ps7Bl1yVBbKUkInw8Qs7oDQ9rAd8AFIK_MTQ\" width=\"744\" height=\"325\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 3: Screenshot des Ressourcen-Monitors (Reiter: &#8220;Arbeitsspeicher&#8221;). Der Standby-Cache belegt 3499 MB.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Standby-Cache leeren &#8211; Messvorgehen hinterfragen<\/h3>\n\n\n\n<p>Mithilfe eines Programms, welches sich unter [34] herunterladen und installieren l\u00e4sst, wurde der Standby-Cache geleert.<\/p>\n\n\n\n<p>Das Ergebnis l\u00e4sst sich im Ressourcenmonitor erkennen:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/K7Y4uX8s7eS9HJbSdp6YtEEOp7GplKfKzonC9HBkzdC-FBkGhgKZ6fKMjvpbCu_5cqDTkQZWzEfkmBIvmS6WB4PBY1-XLuSpib47sfXyQlLcWUp05UO36sU2bT7CxfAOzw\" width=\"659\" height=\"268\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 4: Screenshot des Ressourcen-Monitors (Reiter: &#8220;Arbeitsspeicher&#8221;). Der Standby-Cache wurde geleert und belegt daher nahezu \u00fcberhaupt keinen Speicher.<\/figcaption><\/figure>\n\n\n\n<p>Nach erneuter Durchf\u00fchrung der Messung haben wir folgendes Ergebnis erhalten:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Anzahl Dateien<\/strong><\/td><td><strong>Anzahl Zufallszahlen pro Datei<\/strong><\/td><td><strong>Zugriffszeit HDD<\/strong><\/td><td><strong>Zugriffszeit SSD<\/strong><\/td><td><strong>Verh\u00e4ltniswerte<\/strong><\/td><\/tr><tr><td>1<\/td><td>10.000.000<\/td><td>4590 ms<\/td><td>4543 ms<\/td><td>98,98 %<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 2: Zeitmessung von Lesevorg\u00e4ngen von SSD- und HDD-Festplatten im Vergleich. Auch nach dem Leeren des Standby-Caches entspricht das Ergebnis nicht unserer Erwartung. Die Zeiten sind nahezu gleich.<\/figcaption><\/figure>\n\n\n\n<p>Die Messergebnisse entsprechen erneut nicht den Erwartungen. Beide Zeiten sind in etwa gleich. Offensichtlich ist am grunds\u00e4tzlichen Aufbau der Messung etwas nicht korrekt.&nbsp;<\/p>\n\n\n\n<p>Um festzustellen, ob sich das Lesen der Textdatei \u00fcberhaupt zur Messung eignet, wird im Folgenden die sich ergebende Bandbreite errechnet, welche die SSD aufgrund unserer Messung haben m\u00fcsste. Das Ergebnis wird anschlie\u00dfend mit g\u00e4ngigen Werten verglichen, die von Herstellern angegeben werden. Bei einer korrekten Messung m\u00fcssten sich die Werte stark \u00e4hneln.<\/p>\n\n\n\n<p>Die Formel der Bandbreite lautet wie folgt:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\" data-line=\"\">C = D\/t<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\"><li>Dateigr\u00f6\u00dfe D: 65 MB<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Zeit t: 4,5 s<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Bandbreite C: 14,4 MB\/s<\/li><\/ul>\n\n\n\n<p>Die sich ergebende Bandbreite f\u00fcr beide Festplatten (die Zeiten waren in etwa gleich) entsprechen 14,4 MB\/s. Normalerweise erreichen SSD Platten jedoch eine Bandbreite von etwa 550 MB\/s. Offensichtlich war der Standby-Cache nicht das einzige Problem. Die Messung scheint grunds\u00e4tzlich falsch zu sein.<\/p>\n\n\n\n<p>Nach weiteren Recherchen und Gespr\u00e4chen hat sich folgendes ergeben:<\/p>\n\n\n\n<p>Durch das zeilenweise Lesen von Textdateien muss immer wieder das Betriebssystem nach Ressourcen gefragt werden. Dadurch entsteht ein enorm gro\u00dfer Overhead. Dieser l\u00e4sst sich jedoch kaum exakt bestimmen, da das Betriebssystem die Ressourcen je nach Verf\u00fcgbarkeit vergibt und dem Nutzer hier wenig bis gar keine Kontrolle gibt. Diesen Overhead herauszurechnen ist somit nahezu unm\u00f6glich.<\/p>\n\n\n\n<p>Stattdessen soll der Overhead so gering wie m\u00f6glich gehalten werden, indem statt Text-Dateien gro\u00dfe Bin\u00e4rdateien gelesen und geschrieben werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Schreiben und lesen einer gro\u00dfen Bin\u00e4r-Datei<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td><strong>Gr\u00f6\u00dfe der Datei&nbsp;<\/strong><\/td><td><strong>Zeit HDD<\/strong><\/td><td><strong>Zeit SSD<\/strong><\/td><td><strong>Verh\u00e4ltnis<\/strong><\/td><\/tr><tr><td><strong>Schreiben<\/strong><\/td><td>1 GB<\/td><td>5842.89ms<\/td><td>2873.9ms<\/td><td>49,19%<\/td><\/tr><tr><td><strong>Lesen<\/strong><\/td><td>1 GB<\/td><td>5909.68ms<\/td><td>2463.7ms<\/td><td>41,69%<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 3: Zeitmessung von Lese- und Schreibvorg\u00e4ngen von SSD- und HDD-Festplatten im Vergleich. Hier wurden Bin\u00e4rdateien (statt Textdateien) geschrieben und gelesen. Das Ergebnis stimmt mit unseren Erwartungshaltungen \u00fcberein, die SSD-Platte ist deutlich schneller als die HDD-Platte.<\/figcaption><\/figure>\n\n\n\n<p>Die Resultate der obigen Tabelle entsprechen schlussendlich unseren Erwartungen. Das Schreiben der Bin\u00e4rdatei auf eine SSD-Festplatte ist um etwa 50% schneller als die HDD. Beim Lesen ist ein Geschwindigkeitsgewinn von immerhin rund 40% messbar.<\/p>\n\n\n\n<p>Dieses Ergebnis ist weit weniger lehrreich als die vorherigen Versuche, welche nicht das gew\u00fcnschte Ergebnis erzielt haben. Die gescheiterten Experimente haben aufgrund verschiedener Recherchen zu einem gro\u00dfen Erkenntnisgewinn bez\u00fcglich der Optimierung und Speicherverwaltung von Betriebssystemen beigetragen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">CPU<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Instruction Level Parallelism<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Branchless Programming<\/h4>\n\n\n\n<p>Verzweigungsfreies Programmieren ist ein Programmier-Paradigma f\u00fcr Mikro-Optimierungen, bei welchem versucht wird, die Menge bedingter Sprung-Anweisungen zu minimieren, um einen Geschwindigkeits-Vorteil zu erlangen.<\/p>\n\n\n\n<p>Heutige CPUs besitzen eine Instruktions-Pipeline [48], in welcher mehrere Instruktionen parallel abgearbeitet werden k\u00f6nnen. Instruktionen, welche sp\u00e4ter im Programm-Fluss vorkommen, k\u00f6nnen dabei bereits ausgef\u00fchrt werden, w\u00e4hrend vorige Instruktionen noch auf Daten warten. Dies funktioniert reibungslos, wenn der zu nehmende Programm-Pfad eindeutig ist. Sollte es zwei m\u00f6gliche Pfade geben, wie es bei bedingten Spr\u00fcngen der Fall ist, muss die CPU raten, welcher der beiden Pfade in die Pipeline geladen werden soll, da das Ergebnis der Bedingung noch nicht fertig berechnet ist, wenn die n\u00e4chste Instruktion geladen werden soll. Sollte die CPU jedoch einen falschen Pfad in die Pipeline geladen haben, m\u00fcssen alle Ergebnisse des Pfads verworfen, der Pipeline-Inhalt gel\u00f6scht und der andere Programm-Pfad geladen werden. Dieser Vorgang wird als Pipeline-Flush bezeichnet und ben\u00f6tigt vergleichsweise viel Zeit [48][47].<\/p>\n\n\n\n<p>Um sogenannte Pipeline-Flushes zu vermeiden, muss beim Programmieren auf bedingte Spr\u00fcnge verzichtet werden.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Beispiel<\/h5>\n\n\n\n<p>Im Folgenden ist links ein Programm-Abschnitt mit Verzweigungen und rechts entsprechend die verzweigungsfreie Version gegeben.<\/p>\n\n\n\n<p>Hier wird sich die Eigenschaft zunutze gemacht, dass boolsche Ausdr\u00fccke beziehungsweise Werte auch Zahlen-Werte sind, auf denen arithmetische Operationen ausgef\u00fchrt werden k\u00f6nnen. Hier muss jedoch beachtet werden, dass nicht alle Programmiersprachen die M\u00f6glichkeit bieten, arithmetische Operationen auf boolschen Werten auszuf\u00fchren. Die Programmiersprache C unterst\u00fctzt jedoch diese M\u00f6glichkeit.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Verzweigungsbehaftet<\/strong><\/td><td><strong>Verzweigungsfrei<\/strong><\/td><\/tr><tr><td>if (a &lt; b) {&nbsp;&nbsp;&nbsp;x = a;}else{&nbsp;&nbsp;&nbsp;x = b;}<\/td><td>x = a*(a&lt;b) + b*(a&gt;=b)<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 4: Beispiel f\u00fcr ein verzweigungsbehafteten Code und ein entsprechendes verzweigungsfreies \u00c4quivalent.<\/figcaption><\/figure>\n\n\n\n<p>Generell kann diese Variante wie folgt allgemein formuliert werden, was von [47] inspiriert wurde. c bedeutet \u2018condition\u2019, x ist ein beliebiger Wert.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Verzweigungsbehaftet<\/strong><\/td><td><strong>Verzweigungsfrei<\/strong><\/td><\/tr><tr><td>if (c0) {&nbsp;&nbsp;&nbsp;x = x0;}else if (c1){&nbsp;&nbsp;&nbsp;x = x1;}\u2026else {&nbsp;&nbsp;&nbsp;x = xN;}<\/td><td>x = x0*c0 + x1*c1 + \u2026 + xN*(!(c0&amp;c1&amp;&#8230;&amp;cN-1))<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 5: Allgemeine Formulierung einer beliebig langen if-else-Verzweigung als verzweigungsbehafteten Code (links) und verzweigungsfreien Code (rechts).<\/figcaption><\/figure>\n\n\n\n<h5 class=\"wp-block-heading\">Experiment<\/h5>\n\n\n\n<p>Um den Geschwindigkeitsvorteil von verzweigungsfreiem Programmieren zu messen, wurden zwei Algorithmen erstellt, welche in Tabelle 6 dargestellt sind. Einer mit Verzweigungen (links) und einer ohne (rechts). Der hier gew\u00e4hlte Algorithmus soll alle Kleinbuchstaben eines Strings in Gro\u00dfbuchstaben umwandeln.<\/p>\n\n\n\n<p>Leider konnte hier aber kein Geschwindigkeitsvorteil gemessen werden, vielmehr war die verzweigungsfreie Variante langsamer. Dies liegt unter Anderem daran, dass der Compiler (MSVC 2019) trotz h\u00f6chster Optimierungs-Stufe, die Konvertierung eines Integers zu einem Boolean nicht verzweigungsfrei generiert. Dadurch besitzt der in C geschriebene verzweigungsfreie Code im Assembly-Format trotzdem bedingte Spr\u00fcnge, was aus Abbildung 5 ersichtlich wird. \u2018IS_LOWER_CASE\u2019 ist definiert als ((c) &gt;= &#8216;a&#8217; &amp;&amp; (c) &lt;= &#8216;z&#8217;).<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Verzweigungsbehaftet<\/strong><\/td><td><strong>Verzweigungsfrei<\/strong><\/td><\/tr><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/TYn7RFHnzga1qqXwFJWDj0SX9rd5oKZQ4EA5Fyzv679kg53Gv6Sg5z66IJqajrFPxQriOTzCvmi4hYVHr24L1iPxKp-TL-Qkj4qbAil9Eb6l7TZVPZn4FWBhbiWLqJsOpg\" width=\"286\" height=\"104\"><\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/i9K_fUOGfKFwjhvOLrfRSKh_8UIeApateWM0SgaJ-1Xj7UFm0uPJXYMWeaP2Fved6roR4XMMFigM3UgarqXm8bBqmr0yAMdlCqNkvfrr6fLSRdmKJDfJWRLFzL5Qb0pdpg\" width=\"286\" height=\"63\"><\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 6: C++-Code zum Umwandeln von Kleinbuchstaben in Gro\u00dfbuchstaben eines Strings.<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/wrYrb2wMQ8YdCKARL0Cs8DG8W0QPFYe7YMtQQ09aump_xUkGVX1OwPNcGwexVv_u8UdEFNkIb4CB_NWCsexetvELC38fzjxQ4lP7RFws20BxRLS9KXQpw9FwxlMkgZJ63w\" width=\"488\" height=\"359\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 5: Assembly der verzweigungsfreien Version in MASM. Zu beachten sind hier die \u2018jl\u2019- und \u2018jg\u2019-Instruktionen, welche zu Pipeline-Flushes f\u00fchren k\u00f6nnen.<\/figcaption><\/figure>\n\n\n\n<p>Ein weiterer Versuch war, einen kleinen Code-Abschnitt in Assembly direkt zu schreiben, um die volle Kontrolle \u00fcber die Assembly-Generierung zu behalten, was in Tabelle 7 dargestellt wird. Hierbei sollte der Algorithmus lediglich die Konvertierung eines Integers in einen Boolean durchf\u00fchren.<\/p>\n\n\n\n<p>Im Assembly-Code wird statt der Sprung-Anweisung eine bedingte Kopier-Instruktion \u2018cmovnz\u2019 verwendet, welche nur dann Operand 2 in Operand 1 kopiert, wenn das Zero-Flag gesetzt ist. Durch solche und \u00e4hnliche Instruktionen ist es unter Anderem m\u00f6glich, in Assembly effektiv verzweigungsfrei zu programmieren.<\/p>\n\n\n\n<p>Jedoch k\u00f6nnen hier anhand von Messungen leider auch keine deutlichen Laufzeit-Unterschiede erkannt werden. Vermutlich ist die CPU daher in der Lage, auch mehrere Programm-Pfade parallel in die Pipeline zu laden, sodass eine fehlerhafte Sprung-Vorhersage keine gro\u00dfen Performance-Verluste mit sich bringt.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td><strong>Verzweigungsbehaftet<\/strong><\/td><td><strong>Verzweigungsfrei<\/strong><\/td><\/tr><tr><td>Zeit (s)<\/td><td>2.757<\/td><td>2.502<\/td><\/tr><tr><td>Assembly<\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/3l4wmY3SHz9wF_YbIK4tnCpWj2Q6Exnq0RN6k9yayVaT4YakYnv2cAAmqILWizTIeTAiOfrNOKmHI2UGpVCY_kO-EuX70IZqX46IFd486-HXpDX9-N3Q2exwQcUNcLkXsQ\" width=\"225\" height=\"141\"><\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/ZDwoZVqn4TupskfjLbQ8YDc8VwvPbZL0gyIqmMAeQCMTa5fOyY67oQS2MBsOhcP7pbyVGdDflcU2dY--eEZze-IWvrM44iETfUZm0LkhXbEiF1yx6CnCIrUSH832m8vS2w\" width=\"230\" height=\"100\"><\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 7: Mess-Ergebnisse des manuell geschriebener Assembly-Code in MASM-Syntax f\u00fcr das Konvertieren eines Integers in einen Bool-Wert.<\/figcaption><\/figure>\n\n\n\n<h5 class=\"wp-block-heading\">Anwendungsgebiete<\/h5>\n\n\n\n<p>Zus\u00e4tzlich zum Geschwindigkeits-Vorteil auf CPUs werden verzweigungsfreie Algorithmen auch auf GPUs verwendet, da dort mehrere Prozessor-Kerne mit einer Instruktions-Pipeline gekoppelt sind und daher dieselbe Instruktion echt parallel, aber mit verschiedenen Daten ausgef\u00fchrt wird. Bei Verzweigungen wird daher nicht gesprungen, sondern jede Instruktion in der Verzweigung ausgef\u00fchrt, was dazu f\u00fchrt, dass nicht alle Kerne immer ausgelastet sind. Mit verzweigungsfreiem Programmieren k\u00f6nnen alle Kerne alle Instruktionen sinnvoll verarbeiten [47].<\/p>\n\n\n\n<p>Ein weiteres Anwendungsgebiet ist die Kryptographie. Hierbei spielt nicht die Geschwindigkeit die entscheidende Rolle, sondern das Laufzeit-Verhalten. Verzweigungsfreies Programmieren hat die Eigenschaft, dass nur ein Weg durch das Programm existiert. Ohne Ber\u00fccksichtigung sonstiger Einfl\u00fcsse besitzt das Programm dadurch eine konstante Laufzeit. Dies ist in der Kryptographie wichtig, da anhand ungleicher Laufzeiten bei verschiedenen Eingaben Hinweise zu verwendeten Algorithmen oder Schl\u00fcsseln entstehen, was die Sicherheit beeintr\u00e4chtigt [47][55].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">SIMD (Single Instruction Multiple Data)<\/h4>\n\n\n\n<p>SIMD aus der Flynnschen Klassifikation [7] beschreibt die Eigenschaft eines Prozessors, mehrere Daten in einer Instruktion echt parallel zu verarbeiten. Damit ist SIMD eine M\u00f6glichkeit, Parallelisierung auf Instruktions-Ebene zu realisieren. Um das echt-parallele Ausf\u00fchren einer Instruktion auf mehrere Daten zu erm\u00f6glichen, besitzt der Prozessor mehrere Rechen-Einheiten. Somit k\u00f6nnen die Daten parallel durch mehrere Rechen-Einheiten geleitet werden. Zus\u00e4tzlich besitzen SIMD-taugliche Prozessoren neben einem neuen Befehls-Satz auch spezielle Register, welche eine Gruppe aus gleich gro\u00dfer Daten enthalten k\u00f6nnen [7]. Zum Beispiel sind bei 8-Byte gro\u00dfen Registern folgende Konstellationen m\u00f6glich:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Anzahl Felder in Register<\/strong><\/td><td><strong>Daten-Gr\u00f6\u00dfe pro Feld (Byte)<\/strong><\/td><\/tr><tr><td>1<\/td><td>8<\/td><\/tr><tr><td>2<\/td><td>4<\/td><\/tr><tr><td>4<\/td><td>2<\/td><\/tr><tr><td>8<\/td><td>1<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 8: M\u00f6gliche SIMD-Register-Aufteilungen f\u00fcr 8-Byte-Register.<\/figcaption><\/figure>\n\n\n\n<p>Die erste SIMD-Implementierung von Intel war MMX [56] mit 8 Byte-Registern. Im Laufe der Zeit sind immer umfangreichere und komplexere Befehlssatz-Architekturen entstanden. Dabei sind die SIMD-Register immer gr\u00f6\u00dfer geworden. Mit dem heute neusten Befehlssatz AVX512 [57] besitzen die SIMD-Register eine Gr\u00f6\u00dfe von 512 Bit (64 Byte). Somit kann der Prozessor 64 1-Byte-Operationen oder 8 8-Byte-Operationen parallel ausf\u00fchren, was einen extremen Performance-Gewinn erm\u00f6glicht.<\/p>\n\n\n\n<p>Aktuelle Compiler k\u00f6nnen leider noch nicht automatisch feststellen, ob bestimmte Programm-Sequenzen mit SIMD effizienter abgearbeitet werden k\u00f6nnen. Daher m\u00fcssen diese Instruktionen manuell im Programm-Code mittels intrinsischer Anweisungen oder direkt in Assembly eingef\u00fcgt werden [58].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Cache und Cache-Strategien<\/h3>\n\n\n\n<p>Durch Parallelisierung und Pipelining auf Instruktions-Ebene kann die Abarbeitung von Programmen deutlich beschleunigt werden. Jedoch kann dieser Performance-Gewinn nicht genutzt werden, wenn die ben\u00f6tigten Daten f\u00fcr eine Berechnung noch nicht vorliegen. Dies ist zum Beispiel der Fall, wenn sich die Daten noch auf dem Hauptspeicher befinden und f\u00fcr die Berechnung zun\u00e4chst geladen werden m\u00fcssen.&nbsp;<\/p>\n\n\n\n<p>Folgende Grafik zeigt eine stark vereinfachte Darstellung einer Hauptplatine, auf welcher die sogenannte Scott-CPU (welche zwar funktionst\u00fcchtig w\u00e4re aber nie gebaut worden ist) und der RAM (Random Access Memory) verbaut sind. [59]<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/vSAdirrtnj017_vjYJQzWnNTdqShw1JwDF8AjfiT8jV0h5RjuHDoiwqI9hu3OKnHT_Y3VQThy_gh3gLwQB32sc9r_VOcxTanTsjzjoDPlYe8VW4fhBG22ukOAM2Otqk0nA\" width=\"381\" height=\"425\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 6: Stark vereinfachte Darstellung einer Hauptplatine, auf dem sich RAM und CPU befinden. Diese sind \u00fcber den Adress-Bus, \u00fcber den Daten-Bus sowie den Control-Bus miteinander verbunden.<\/figcaption><\/figure>\n\n\n\n<p>Die CPU und der RAM sind \u00fcber den Adress-Bus sowie den Daten-Bus mit jeweils 8 Leitungen verbunden, was bedeutet dass es sich hier um ein 8-Bit-System handelt. Zus\u00e4tzlich existiert der Control-Bus, mit dessen Hilfe dem RAM mitgeteilt wird, ob Daten gelesen oder geschrieben werden sollen.<\/p>\n\n\n\n<p>Um eine genauere Vorstellung von den im RAM befindlichen Daten zu erhalten, wurde die folgende Tabelle erstellt.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>address<\/strong><\/td><td><strong>data<\/strong><\/td><\/tr><tr><td>01100010<\/td><td>10010110&nbsp;<span class=\"has-inline-color has-vivid-red-color\">(Instruction)<\/span><\/td><\/tr><tr><td>10010100<\/td><td>10010100 <span class=\"has-inline-color has-vivid-cyan-blue-color\">(Number)<\/span><\/td><\/tr><tr><td>11001110<\/td><td>10010110&nbsp;<span class=\"has-inline-color has-vivid-red-color\">(Instruction)<\/span><\/td><\/tr><tr><td>10101100<\/td><td>10010011 <span class=\"has-inline-color has-vivid-purple-color\">(Address)<\/span><\/td><\/tr><tr><td>00011001<\/td><td>10010110 <span class=\"has-inline-color has-vivid-red-color\">(Instruction)<\/span><\/td><\/tr><tr><td>10011001<\/td><td>10101101 <span class=\"has-inline-color has-vivid-purple-color\">(Address)<\/span><\/td><\/tr><tr><td>&#8230;<\/td><td>&#8230;<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 9: \u00dcberblick \u00fcber der im RAM befindlichen Daten.<\/figcaption><\/figure>\n\n\n\n<p>Es l\u00e4sst sich erkennen, dass der RAM Adressen und Daten beinhaltet. Mit Daten sind an dieser Stelle jedoch nicht nur Zahlenwerte gemeint (z.B. Variablen im Programm), sondern auch Instruktionen sowie weitere Adressen. Es l\u00e4sst sich erahnen, dass sich im RAM ganze Programmabl\u00e4ufe wiederfinden lassen. Es muss an dieser Stelle betont werden, dass die CPU nur arbeiten kann, solange die eben beschriebenen Daten zu ihr gelangen.<\/p>\n\n\n\n<p>Die Schreib- und Lesevorg\u00e4nge sind in den folgenden Grafiken dargestellt. M\u00f6chte die CPU bestimmte Daten lesen, so sendet sie \u00fcber den Adress-Bus eine bestimmte Adresse an den RAM (rote Leitungen) und aktiviert zudem das Enable-Wire des Control-Busses. Der RAM sendet daraufhin die an dieser Adresse befindlichen Daten \u00fcber den Daten-Bus an die CPU. Ein Schreibvorgang geschieht in \u00e4hnlicher Art und Weise. Erneut sendet die CPU eine Adresse \u00fcber den Adress-Bus, diesmal aktiviert sie jedoch das Set-Wire im Control-Bus. \u00dcber den Daten-Bus kann sie dann die entsprechenden Daten an den RAM senden, welcher die an dieser Adresse bereits befindlichen Daten \u00fcberschreibt.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Lese-Zugriff<\/td><td>Schreib-Zugriff<\/td><\/tr><tr><td><img decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/8GA03UbiQNHaER78q-wHmnjBBIZFXCJ5tPJ-gKIXKmfCTRhJ5bOZoiKTw7F0XHh0-lbbHJtmp_JY_1MDPXMTx10RwuRzjtXD1Jv73rnQdBbh5vi_YNiBv6KKAI4U9rTWlw\" style=\"width: px\"><\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/Xm7nIKuR9FewdATMhI-tjdFqpuE679hpHIwUM9S64aOlHDqJD_a8BB3jRM61SYAtRHDwj7z_rFQWxinSuxXDXWP31TLm_C7brfbKNmsL5cfx7zIErol5vOH3_U0TWRxRkw\" width=\"261\" height=\"291\"><\/td><\/tr><tr><td>CPU sendet Adresse \u00fcber Adress-Bus an RAM und aktiviert zudem das Enable-Wire. Die Daten werden vom RAM an die CPU \u00fcber den Daten-Bus zur\u00fcckgeschickt.<\/td><td>CPU sendet Adresse \u00fcber Adress-Bus an RAM und aktiviert zudem das Set-Wire. Die Daten werden von der CPU an den RAM \u00fcber den Datenbus gesendet. Der RAM \u00fcberschreibt die an der entsprechenden Adresse befindlichen Daten.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 10: Schreib-\/ Lese-Zugriff<\/figcaption><\/figure>\n\n\n\n<p>Da der Hauptspeicher deutlich weiter entfernt ist, als die Register der CPU, ben\u00f6tigt der Strom deutlich l\u00e4nger, bis er zum Hauptspeicher und wieder zur\u00fcck geflossen ist. Daher m\u00fcsste die CPU warten, bis die Daten vom Hauptspeicher zur Verf\u00fcgung stehen, was sehr ineffizient w\u00e4re.<\/p>\n\n\n\n<p>W\u00e4hrend CPUs n\u00e4mlich \u00fcblicherweise eine Taktrate von 1 GHz &#8211; 4 GHz (Consumerbereich) aufweisen, ist der RAM mit einer Taktrate von 400 MHz &#8211; 800 MHz (bzw. 1600 MHz bei DDR3, 2133 MHz bei DDR4) deutlich langsamer getaktet [45]. Bei einer groben \u00dcberschlagsrechnung l\u00e4sst sich erkennen, dass es etwa 200 CPU-Zyklen braucht, bis Daten vom RAM zur CPU gelangt sind.&nbsp;<\/p>\n\n\n\n<p>Um den Weg zum Speicher und damit die Zugriffszeit zu verk\u00fcrzen, wurden Cache-Speicher eingef\u00fchrt. Dies sind kleinere Speicher, welche direkt auf dem CPU-Chip liegen und damit f\u00fcr die CPU deutlich schneller zugreifbar sind. Hierbei dient der Cache als Puffer-Speicher, um eine Teil-Kopie des Hauptspeichers zu halten [4].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Cache-Layer<\/h4>\n\n\n\n<p>Um den Speicher-Zugriff im Durchschnitt noch schneller zu machen, besitzen heutige Prozessoren meist nicht einen Cache-Speicher, sondern mehrere Cache-Schichten. Alle Caches liegen dabei nachwievor auf dem CPU-Chip, jedoch unterscheiden sich die Caches bezogen auf die Entfernung zum Prozessor und der Gr\u00f6\u00dfe. Je h\u00f6her die Cache-Schicht, desto gr\u00f6\u00dfer, aber auch langsamer der Cache-Speicher, da mehr Transistoren verbaut sind und der Strom l\u00e4nger ben\u00f6tigt um den Speicher abzurufen. Ein Cache besitzt normalerweise nicht f\u00fcr einen einzelnen Wert im Speicher einen Eintrag, sondern f\u00fcr ganze Speicher-Bl\u00f6cke, normalerweise in der Gr\u00f6\u00dfe einer Speicher-Seite, genannt \u2018Cache-Line\u2019.<\/p>\n\n\n\n<p>Caches lassen sich in 3 Schichten einordnen.&nbsp;<\/p>\n\n\n\n<p>Es existiert der Level 1 Cache (L1 Cache), welcher nur von einer CPU genutzt wird. Dieser ist mit 2 KB &#8211; 64 KB der kleinste Cache, kann daf\u00fcr aber mit der gleichen Geschwindigkeit wie die CPU arbeiten, was bedeutet dass hier Daten ohne zus\u00e4tzlichen Zyklus gelesen und geschrieben werden k\u00f6nnen. [45]<\/p>\n\n\n\n<p>Der Level 2 Cache (L2 Cache) ist mit 256 KB &#8211; 512 KB bereits etwas gr\u00f6\u00dfer und kann, je nach Ausf\u00fchrung, nur von einem Kern oder aber von mehreren Kernen genutzt werden.&nbsp;<\/p>\n\n\n\n<p>Zuletzt gibt es noch den Level 3 Cache (L3 Cache), welcher mit 1 MB &#8211; 8 MB am gr\u00f6\u00dften ist. Dieser Cache wird stets von allen Kernen geteilt, ist allerdings nicht in jedem System verbaut sondern tendenziell im h\u00f6heren Preissegment vorzufinden. Ben\u00f6tigt die CPU bestimmte Daten aus einer Cache-Line, so wird zun\u00e4chst \u00fcberpr\u00fcft, ob sich diese Daten im L1-Cache befinden. Wenn dem so ist, werden die Daten hiervon bezogen, ansonsten wird der L2- und L3-Cache nach demselben Muster \u00fcberpr\u00fcft. Befinden sich die Daten nicht in einem der Caches, so werden die Daten in diesem Fall aus dem RAM bezogen [45].<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh3.googleusercontent.com\/oJe0eyAti43WodTBcZusC1DdHlSnE7-1eQIZg8kyt-3ZpPeVsvzJn5uYjC-QHsuNsMzWlhQ6v8i0nFrMxBa6WSQ1lbuVvSuwv7oqnUyCMGRw1A0WII1ALkOoRX-_PXwSaA\" width=\"470\" height=\"200\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 7: Cache-Layer-Anordnung<\/figcaption><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">Lokalit\u00e4ts-Eigenschaften<\/h4>\n\n\n\n<p>Caches w\u00fcrden keinen Vorteil bringen, wenn die geladenen Daten nur einmal ben\u00f6tigt werden w\u00fcrden. Dar\u00fcber hinaus w\u00e4re das Laden gr\u00f6\u00dferer Speicher-Bereiche unsinnig, wenn benachbarte Speicher-Stellen nicht ben\u00f6tigt werden w\u00fcrden.<\/p>\n\n\n\n<p>Aus diesem Grund gibt es die Lokalit\u00e4ts-Eigenschaften, welche ein typisches Muster in Bezug auf Speicher-Zugriffe g\u00e4ngiger Programme beschreiben. Dadurch ist gew\u00e4hrleistet, dass das Cachen sinnvoll ist. Es werden grunds\u00e4tzlich zwei Arten von Lokalit\u00e4ten unterschieden, welche aus [9] entnommen wurden:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Lokalit\u00e4t-Art<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><td><strong>Beispiel<\/strong><\/td><\/tr><tr><td>zeitlich<\/td><td>Aktuell zugegriffene Speicher-Bereiche werden in naher Zukunft mit hoher Wahrscheinlichkeit wieder ben\u00f6tigt. Daher eignet es sich, diese Speicher-Stellen zu puffern, um beim nochmaligen Zugriff die Daten schneller laden zu k\u00f6nnen.<\/td><td>Schleife<\/td><\/tr><tr><td>r\u00e4umlich<\/td><td>Mit hoher Wahrscheinlichkeit werden Adressen in unmittelbarer Nachbarschaft zum aktuellen Zugriff angesprochen. Daher eignet es sich, direkt gr\u00f6\u00dfere Speicher-Bereiche zu laden, um benachbarte Daten nicht auch vom Hauptspeicher laden zu m\u00fcssen.<\/td><td>Sequenzieller Programmablauf<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 11: Lokalit\u00e4tseigenschaften.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">k-Fach Satz-assoziativer Cache<\/h3>\n\n\n\n<p>Caches besitzen eine bestimmte Menge an Cache-Lines, welche in der Regel einem Vielfachen von Zwei entsprechen. Diese Cache-Lines k\u00f6nnen in sogenannte S\u00e4tze gruppiert werden. Das k in \u2018k-Fach-Satz-Assoziativ\u2019 steht hierbei f\u00fcr die Menge an Cache-Lines pro Satz. Je nachdem wie hoch das k ist, werden zwei verschiedene Sonderf\u00e4lle an Abbildungen unterschieden, welche im Folgenden erl\u00e4utert werden [4]. Unter \u2018Abbildung\u2019 wird bei Caches die Zugeh\u00f6rigkeit eines Speicher-Blocks aus dem Hauptspeicher zu einer Cache-Line verstanden.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>k<\/strong><\/td><td><strong>Typ<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>1<\/td><td>Direkt Abgebildet<\/td><td>Jeder Speicher-Block ist exakt einer Cache-Line zugeordnet.<\/td><\/tr><tr><td>Anzahl Cache-Lines<\/td><td>Voll-Assoziativ<\/td><td>Kein Speicher-Block ist einer festen Cache-Line zugeordnet.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 12: Sonder-Bezeichnungen von Caches bei Extremwerten f\u00fcr k.<\/figcaption><\/figure>\n\n\n\n<p>Es kann festgehalten werden, dass bei steigendem k weniger Fehlzugriffe entstehen und damit eine h\u00f6here Performance erreicht werden kann. Je mehr Cache-Lines einem Speicher-Block zugeordnet werden k\u00f6nnen, desto variabler k\u00f6nnen diese je nach Laufzeit-Verhalten zugewiesen und l\u00e4nger nicht ben\u00f6tigte Speicher-Bl\u00f6cke aussortiert werden.<\/p>\n\n\n\n<p>Jedoch f\u00fchrt die h\u00f6here Flexibilit\u00e4t zu komplexerer Logik und damit mehr Transistor-Bedarf, was sich in Kosten, Platz- und Energiebedarf auswirkt. Zus\u00e4tzlich wird mehr Speicher ben\u00f6tigt, da weniger Bits der Speicher-Adresse f\u00fcr die Indexierung und daher mehr Bits f\u00fcr den Cache-Line-Tag ben\u00f6tigt werden [4].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Hardware-Implementierung<\/h4>\n\n\n\n<p>Anhand der Speicher-Adresse, welche von der CPU angefragt wird, kann die Cache-Line ermittelt werden. Der Cache ist als Tabelle strukturiert. Im Folgenden sind die Bestandteile der Adresse angegeben:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/gI2YY6pQeGjYHwrxQNxZvSVTX6s24QKpXbg5nL526jYFT4mEBJJE87Mpxvy38SHdWg3zYm_3Wnlj8CXbOtaLNTTzrVdHBHvnYspGG-6mKtqKhjA5R_TASKy4Flg2W1gQ1w\" width=\"602\" height=\"115\"><\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 13: Bestandteile der Speicher-Adresse zur Ermittlung der Cache-Line im Cache.<\/figcaption><\/figure>\n\n\n\n<p>Der Offset wird bei der Selektierung der Cache-Line nicht ber\u00fccksichtigt und entspricht lediglich dem Adress-Index innerhalb eines Speicher-Blocks. Alle Adressen mit gleicher Block-Adresse geh\u00f6ren zur selben Cache-Line. Der Satz-Index gibt die Tabellen-Zeile des Caches an, wobei jede Zeile einem Satz entspricht. Um Speicher-Bl\u00f6cke zu unterscheiden, welche auf dieselbe Cache-Line abgebildet werden, wird der Tag der Speicher-Adresse in der Cache-Line abgespeichert und als Block-ID verwendet.<\/p>\n\n\n\n<p>Jede Cache-Line besitzt zus\u00e4tzliche Zustands-Bits, um zu erkennen, ob die angeforderten Daten im Cache vorhanden oder modifiziert sind [4].<\/p>\n\n\n\n<p>Typische Bestandteile einer Cache-Line sind wie folgt:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Spalte<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>Valid\u00e4ts-Bit (V)<\/td><td>Gibt an, ob Eintrag noch g\u00fcltig ist. Wenn nicht, muss der Cache-Block beim n\u00e4chsten Zugriff neu geladen werden.<\/td><\/tr><tr><td>Dirty-Bit (D)<\/td><td>Gibt an, ob Eintrag vom eigenen Kern modifiziert wurde. Sollte der Speicher-Block ausgetauscht werden, muss dieser zur\u00fcck geschrieben werden, wenn dieser modifiziert ist, um keine Daten zu verlieren.<\/td><\/tr><tr><td>Tag<\/td><td>Block-ID des Satzes.<\/td><\/tr><tr><td>Daten<\/td><td>Gepufferte Daten des Speicher-Blocks.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 14: Cache-Line-Bestandteile<\/figcaption><\/figure>\n\n\n\n<p>Ein m\u00f6glicher Cache-Zugriff kann dann wie folgt aussehen:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Schritt<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>1<\/td><td>Satz anhand von Index-Bits finden.<\/td><\/tr><tr><td>2<\/td><td>Gefundenen Satz anhand von Tag-Bits durchsuchen. Wenn Cache-Block nicht gefunden wurde, gibt es einen Fehlzugriff.<\/td><\/tr><tr><td>3<\/td><td>Block-G\u00fcltigkeit anhand von Valid\u00e4ts-Bit \u00fcberpr\u00fcfen. Wenn Block nicht valide, gibt es einen Fehlzugriff.<\/td><\/tr><tr><td>4<\/td><td>Ansonsten kann der Speicher direkt aus dem Cache geladen werden.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 15: Beispiel-Ablauf eines Cache-Zugriffs.<\/figcaption><\/figure>\n\n\n\n<p>Bei einem Fehlzugriff muss der Speicher-Block vom Hauptspeicher geladen werden und anhand von Ersetzungs-Strategien im Cache gespeichert und die angeforderten Daten an den Prozessor weitergeleitet werden [4].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Cache-Ersetzungs-Strategien<\/h4>\n\n\n\n<p>Sollte ein Satz mehrere Cache-Lines enthalten, k\u00f6nnen die Speicher-Bl\u00f6cke freier auf die entsprechenden Cache-Lines zugewiesen werden. Wenn ein noch nicht gepufferter Speicher-Block geladen werden soll, und keine freien Cache-Lines in einem Satz mehr zur Verf\u00fcgung stehen, muss entschieden werden, welche der Cache-Lines ersetzt werden soll. Hierf\u00fcr existieren verschiedene Ersetzungs-Strategien [4], welche jeweils unterschiedliche Priorit\u00e4ten besitzen. Ersetzungs-Strategien sollten anhand ihrer Priorit\u00e4t sortiert und angewendet werden, um bestm\u00f6gliche Performance zu erlangen. Im Folgenden ist eine Beispiel-Priorisierung gegeben.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Priorit\u00e4t<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>1<\/td><td>Invalide Cache-Lines l\u00f6schen<\/td><\/tr><tr><td>2<\/td><td>Nicht modifizierte Cache-Lines ersetzen, da das Zur\u00fcckschreiben viel Zeit kostet.<\/td><\/tr><tr><td>3<\/td><td>LRU (Least Recently Used): Eintrag, welcher am L\u00e4ngsten nicht mehr verwendet wurde, kann ersetzt werden.<br>Alternativ k\u00f6nnen auch zuf\u00e4llige Eintr\u00e4ge ersetzt werden, was auch gute Ergebnisse bringt, aber deutlich weniger Transistoren ben\u00f6tigt.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 16: Beispiel-Priorisierung von Ersetzungs-Strategien.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Parallelisierung<\/h3>\n\n\n\n<p>Parallelisierung wird dadurch erreicht, dass bestimmte Funktions-Einheiten dupliziert werden. Hierbei ist die Definition, was Funktionseinheiten sind, je nach Anwendungsgebiet und Abstraktions-Ebene unterschiedlich.<\/p>\n\n\n\n<p>Im Bereich der Rechner-Architektur wird Parallelisierung zum Beispiel durch das Duplizieren der Prozessoren erreicht.<\/p>\n\n\n\n<p>Auf Befehlssatz-Ebene werden Rechenwerke dupliziert, um mehrere Daten parallel bearbeiten zu k\u00f6nnen, wie im Kapitel \u2018SIMD\u2019 bereits erw\u00e4hnt wurde.<\/p>\n\n\n\n<p>Im Folgenden werden zwei verschiedene Multi-Core-Architekturen beschrieben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Symmetric Multiprocessing (SMP)<\/h4>\n\n\n\n<p>Symmetrische Multiprozessor-Systeme kennzeichnen sich dadurch, dass die Kommunikation zwischen den Kernen sowie die Daten\u00fcbertragung \u00fcber einen zentralen Bus l\u00e4uft. Dadurch k\u00f6nnen immer alle Kerne automatisch benachrichtigt werden, da jede Nachricht gebroadcastet wird.<\/p>\n\n\n\n<p>SMP wird normalerweise nur bei kleineren Systemen mit bis zu circa 8 Kernen realisiert, da die Kommunikation \u00fcber einen Bus l\u00e4uft und daher bei steigender Teilnehmer-Anzahl die Latenz der Daten\u00fcbertragung als auch die Bus-Auslastung immer gr\u00f6\u00dfer wird.<\/p>\n\n\n\n<p>M\u00f6gliche L\u00f6sungs-Ans\u00e4tze f\u00fcr eine geringere Bus-Auslastung w\u00e4ren, mehrere Busse f\u00fcr die Kommunikation zu verwenden, was aber die Cache-Controller-Logik komplexer macht.<\/p>\n\n\n\n<p>Aufgrund dessen sind SMP-Systeme nicht gut als skalierende Multiprozessor-Systeme geeignet [29].<\/p>\n\n\n\n<p>Die folgende Abbildung soll ein SMP-System veranschaulichen.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/x1dA7kWRl2gvhxjxtl6V-_KxgGotY6tNEtVLLGdgIhGEe-eTh2I7uof0N5HXo8uhADepYxpKF7pIrlBp5mzE5xVf89GPeTEGRokuksw94UwZeg1-2QnsaWy-9Uy8oxb4-w\" width=\"378\" height=\"265\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 8: SMP mit vier Kernen sowie Layer-1 und Layer-2 Caches.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Cache-Koh\u00e4renz<\/h3>\n\n\n\n<p>Bei Multi-Prozessor-Systemen, wie sie in heutigen PC\u2019s meistens verbaut sind, besitzt jeder CPU-Kern einen oder mehrere eigene private Caches. Solange jeder Kern einen anderen Prozess abarbeitet und dadurch keine Kommunikation erforderlich ist, funktioniert diese Art der Parallelisierung einwandfrei. Dies ist zum Beispiel dann der Fall, wenn einzelne voneinander unabh\u00e4ngige Prozesse parallel ausgef\u00fchrt werden sollen. Threads innerhalb eines Prozesses m\u00fcssen aber in der Regel synchronisiert werden, da hier Aufgaben auf verschiedene Threads verteilt und Endergebnisse wieder zusammengef\u00fchrt werden m\u00fcssen, was das Arbeiten auf dem selben Adressraum und das Abstimmen der Threads erfordert. Bearbeiten zwei Kerne denselben Speicher-Block, so m\u00fcssen deren Caches aktualisiert werden, um nicht auf veralteten Daten zu arbeiten. Diese Problematik wird Cache-Koh\u00e4renz genannt und besch\u00e4ftigt sich mit der Synchronisation der privaten Speicher der Kerne [5].<\/p>\n\n\n\n<p>Mit Hilfe von Cache-Koh\u00e4renz-Protokollen ist es m\u00f6glich, Cache-koh\u00e4rente Systeme zu implementieren. Jedoch ist hierbei nur gew\u00e4hrleistet, dass die aktuellste Version des angeforderten Speicher-Blocks, welche in einem der Caches oder im RAM vorliegt, zur\u00fcckgegeben wird. Dies bezieht sich aber ausschlie\u00dflich auf Cache-Speicher, wie der Name bereits andeutet [5]. Register-Speicher, welche sich direkt im Prozessor-Kern befinden, sind davon ausgenommen. Dies ist auch richtig so, da die Register-Inhalte selbst nur tempor\u00e4re Zust\u00e4nde wie Zwischen-Ergebnisse bestimmter Operationen enthalten. Zudem k\u00f6nnen die Prozessor-Kerne jeweils an unterschiedlichen Instruktionen beziehungsweise Programm-Pfaden arbeiten, sodass die Inhalte der Register von Kern zu Kern durchaus unterschiedliche Werte besitzen k\u00f6nnen, d\u00fcrfen und auch m\u00fcssen, um Parallelisierung auf Kern-Ebene zu erm\u00f6glichen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Bus-Snooping<\/h4>\n\n\n\n<p>Hierbei handelt es sich um eine M\u00f6glichkeit, wie Cache-Koh\u00e4renz in symmetrischen Multiprozessor-Systemen umgesetzt werden kann. Jeder private Cache eines Kerns besitzt einen Cache-Controller, welcher am Bus lauscht und entsprechende Nachrichten anderer Kerne empf\u00e4ngt, verarbeitet und eventuell eigene Nachrichten auf den Bus gibt [17].<\/p>\n\n\n\n<p>Abbildung 9 veranschaulicht dieses Verfahren anhand eines CPU-Kerns.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/ZDcxuBhkQeLq-ALwgtJlkXrLFegIjANbL_XHKYdjEMlNsitkXsNB-AfHAYF64K03TjusP98RcgCiHQlOMkPHRUR46cVTYFcs5usIaHPNGE_MyI8CzfkutTu3pLm1RFj0eQ\" width=\"378\" height=\"189\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 9: Bus-Snooping-Prinzip f\u00fcr einen Kern.<\/figcaption><\/figure>\n\n\n\n<p>Es werden zwei verschiedene Arten von Snooping-Protokollen unterschieden, welche sich im Verhalten bei Schreib-Aktionen unterscheiden.<\/p>\n\n\n\n<p>Write-Invalidate-Protokolle invalidieren die Cache-Lines anderer Kerne. Dieser Invalidierungs-Vorgang muss nur einmal get\u00e4tigt werden. Daher wird hier deutlich weniger Bus-Verkehr erzeugt [17]. Beispiel-Implementierungen sind MSI [24], MESI [22], MOSI [23] und MOESI [46], welche in den folgenden Abschnitten genauer betrachtet werden.<\/p>\n\n\n\n<p>Write-Update-Protokolle aktualisieren den Datenbestand der anderen Cache-Lines jedes Mal bei einem Schreib-Zugriff. Daher wird hier deutlich mehr Bus-Last erzeugt. Ein Vorteil gegen\u00fcber dem Write-Invalidate-Protokollen ist jedoch, dass weniger Cache-Misses auftreten, da die Caches nicht invalidiert werden, was eine geringere Latenz bei Schreib\/Lese-Zugriffen erm\u00f6glicht [17].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">MSI \/ MESI \/ MOSI \/ MOESI<\/h4>\n\n\n\n<p>MESI, MOSI sowie MOESI sind Erweiterungen des Basis-Protokolls MSI. Jeder Cache eines Kerns ist mit einem Cache-Controller ausgestattet, welcher eine Verbindung zum privaten Cache sowie zum Daten-Bus der CPU besitzt. Somit registriert der Controller Aktionen des eigenen Kerns, als auch Aktionen anderer Kerne und kann dadurch entsprechend reagieren. Der Controller besitzt f\u00fcr jede Cache-Line einen bestimmten Zustand. Die Namen der Protokolle bestehen hierbei immer aus den Anfangsbuchstaben der entsprechenden Zust\u00e4nde. Folgende Zust\u00e4nde sind m\u00f6glich und wurden aus [24],[22],[23],[46] entnommen.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Block-Zustand<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>Invalid<\/td><td>Speicher-Block ist invalide und muss neu geladen werden.<\/td><\/tr><tr><td>Shared<\/td><td>Speicher-Block nicht manipuliert und valide.<\/td><\/tr><tr><td>Modified<\/td><td>Speicher-Block manipuliert und valide.<\/td><\/tr><tr><td>Exclusive<\/td><td>Wie Shared, aber es existiert nur eine Kopie. Anhand dieses Zustands wird die Bus-Auslastung reduziert, da bei Schreib-Zugriffen keine Invalidierungs-Nachricht gesendet werden muss, da nur der eigene Cache eine Kopie des Speicher-Blocks h\u00e4lt.<\/td><\/tr><tr><td>Owned<\/td><td>Sollte ein anderer Kern den Speicher-Block anfragen, so kann der Cache dem anfragenden Cache seinen Cache-Line-Inhalt zusenden. Damit wird der Zugriff auf den Hauptspeicher verhindert, welcher deutlich l\u00e4nger dauern w\u00fcrde.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 17: Block-Zust\u00e4nde des MOESI-Protokolls [46].<\/figcaption><\/figure>\n\n\n\n<p>Der Memory-Controller trifft nun anhand einer Eingabe, welche vom Kern oder vom Daten-Bus kommt, und des Zustands des adressierten Speicher-Blocks eine Entscheidung, t\u00e4tigt eventuell eine entsprechende Aktion und wechselt den Zustand in einen entsprechenden Folgezustand.<\/p>\n\n\n\n<p>Die Verhaltensweisen des MSI Protokolls sind in zwei Zustandsgraphen abgebildet [42].<\/p>\n\n\n\n<p>Die folgende Grafik zeigt die Aktion der CPU (blau) sowie die Reaktion des eigenen Cache-Controllers (rot). Zudem wird dargestellt, in welchen Zustand der Cache-Controller den entsprechenden Speicher-Block nach Ausf\u00fchrung sein Aktion \u00fcberf\u00fchrt.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/HOIu3ZondTVxxxiCH8uKi93VZejLhGwrOf1D_qziCq_DJD8O6OrTdC03LB585GR368vwqCWxmdxSrSN2WEyx-hESYAwZyG4Aqy6D3dKJsaediATvI4X2tMfYXH-MTx97zQ\" width=\"602\" height=\"425\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 10: Zustands-\u00dcbergangs-Diagramm der Kern-Eingabe.<\/figcaption><\/figure>\n\n\n\n<p>Um das MSI-Protokoll zu vervollst\u00e4ndigen, bedarf es jedoch noch einer zweiten Grafik, die die Reaktion des Busses auf die Aktionen anderer CPUs darstellt. In diesem Fall werden also die Aktionen einer fremden CPU (blau) sowie die Reaktion des eigenen Cache-Controllers (rot) aufgezeigt. Zus\u00e4tzlich l\u00e4sst sich erkennen, in welchen Zustand der eigene Cache-Block nach der Aktion des Cache-Controllers \u00fcberf\u00fchrt wird.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/Ggb9NwT75sFNlGocIeDCx8p0cAjeD2BQw5vSdKHisbOle9GN3PYpWEJo_XS6rJA-pUAq82czIm0-giYuktTAQcACSfqcJfbSoSz8OJJH7I8BVz8vHXJWBFfth3N-n3M0gg\" width=\"602\" height=\"425\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 11: Zustands-\u00dcbergangs-Diagramm f\u00fcr Bus-Eingabe.<\/figcaption><\/figure>\n\n\n\n<p>Um auch die Erweiterungen des MSI-Protokolls darzustellen, wurde eine Zustands-Tabelle erstellt, welche in Tabelle 20 abgebildet ist.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Nachrichten-Arten<\/h5>\n\n\n\n<p>Bus-Nachrichten k\u00f6nnen sowohl Eingabe als auch Ausgabe des Cache-Controllers sein. Lese\/Schreib-Aktionen der CPU sind ausschlie\u00dflich Eingaben, da diese nur von einem Prozessor initiiert werden k\u00f6nnen.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Nachrichten-Art<\/strong><\/td><td><strong>Leitung<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>R<\/td><td>CPU<\/td><td>CPU will Block lesen.<\/td><\/tr><tr><td>W<\/td><td>CPU<\/td><td>CPU will auf Block schreiben.<\/td><\/tr><tr><td>Invalidate<\/td><td>Bus<\/td><td>Cache-Block muss invalidiert werden.<\/td><\/tr><tr><td>Read-Miss<\/td><td>Bus<\/td><td>Kern des anfragenden Cache will Speicher-Block lesen.<\/td><\/tr><tr><td>Write-Miss<\/td><td>Bus<\/td><td>Kern des anfragenden Cache will auf Speicher-Block schreiben.<\/td><\/tr><tr><td>Flush<\/td><td>Bus<\/td><td>Sende eigenen Block-Inhalt an anfragenden Cache.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 18: Nachrichten-Arten von MOESI [46].<\/figcaption><\/figure>\n\n\n\n<h5 class=\"wp-block-heading\">\u00dcbertragungs-Format<\/h5>\n\n\n\n<p>Das \u00dcbertragungsformat, mit welchem Memory-Controller-bezogene Daten \u00fcber den Bus ausgetauscht werden, ist in der Regel gleich und k\u00f6nnte nach eigenen \u00dcberlegungen wie folgt aussehen.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Nachricht-Bestandteil<\/strong><\/td><td><strong>Beschreibung<\/strong><\/td><\/tr><tr><td>Aktion<\/td><td>Zum Beispiel Read-Miss oder Write-Miss.<\/td><\/tr><tr><td>Block-Adresse<\/td><td>Da der Zustand abh\u00e4ngig vom jeweiligen Speicher-Block ist.<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 19: \u00dcbertragungsformat f\u00fcr Memory-Controller-Kommunikation \u00fcber den Bus.<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Zustand<\/strong><\/td><td><strong>Eingabe<\/strong><\/td><td><strong>Ausgabe<\/strong><\/td><td><strong>Folge-Zustand<\/strong><\/td><td><strong>Beschreibung<\/strong>&nbsp;&nbsp;<\/td><\/tr><tr><td>S<\/td><td>W<\/td><td>Invalidate<\/td><td>M<\/td><td>&#8211; invalidiere alle anderen m\u00f6glichen Kopien des Blocks&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>S<\/td><td>R<\/td><td>&#8211;<\/td><td>S<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>S<\/td><td>Invalidate<\/td><td>&#8211;<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>S<\/td><td>Write-Miss<\/td><td>&#8211;<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>S<\/td><td>Read-Miss<\/td><td>&#8211;<\/td><td>S<\/td><td>&#8211; anderer Kern erh\u00e4lt Block von RAM<\/td><\/tr><tr><td>I<\/td><td>R<\/td><td>Read-Miss<\/td><td>S, E<\/td><td>&#8211; erhalte Block von RAM: E<br>&#8211; erhalte Block von Cache: S<br>&#8211; muss von anderen Cache-Controllern mitgeteilt werden&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>I<\/td><td>W<\/td><td>Write-Miss<\/td><td>M<\/td><td>&#8211; Speicher-Block aus anderem Cache oder RAM nachladen<\/td><\/tr><tr><td>I<\/td><td>Invalidate<\/td><td>&#8211;<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>I<\/td><td>Write-Miss<\/td><td>&#8211;<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>I<\/td><td>Read-Miss<\/td><td>&#8211;<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>M<\/td><td>R<\/td><td>&#8211;<\/td><td>M<\/td><td><\/td><\/tr><tr><td>M<\/td><td>W<\/td><td>&#8211;<\/td><td>M<\/td><td><\/td><\/tr><tr><td>M<\/td><td>Invalidate<\/td><td>&#8211;<\/td><td>&#8211;<\/td><td>&#8211; nicht m\u00f6glich, alle anderen Kerne sind invalidiert, wenn Zustand=M<\/td><\/tr><tr><td>M<\/td><td>Write-Miss<\/td><td>Flush<\/td><td>I<\/td><td>&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>M<\/td><td>Read-Miss<\/td><td>Flush<\/td><td>S, O<\/td><td>&#8211; eigenen Block in anfragenden Cache (und RAM, wenn MSI) kopieren<br>&#8211; RAM-Zugriff durch anfragenden Kern verhindern<\/td><\/tr><tr><td>E<\/td><td>R<\/td><td>&#8211;<\/td><td>E<\/td><td><\/td><\/tr><tr><td>E<\/td><td>W<\/td><td>&#8211;<\/td><td>M<\/td><td><\/td><\/tr><tr><td>E<\/td><td>Invalidate<\/td><td>&#8211;<\/td><td>&#8211;<\/td><td>&#8211; nicht m\u00f6glich<\/td><\/tr><tr><td>E<\/td><td>Read-Miss<\/td><td>&#8211;<\/td><td>S<\/td><td>&#8211; anderer Kern fragt selben Block an, daher existieren jetzt &gt;1 Kopien&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>E<\/td><td>Write-Miss<\/td><td>Flush<\/td><td>I<\/td><td><\/td><\/tr><tr><td>O<\/td><td>R<\/td><td>&#8211;<\/td><td>O<\/td><td><\/td><\/tr><tr><td>O<\/td><td>W<\/td><td>Invalidate<\/td><td>M<\/td><td><\/td><\/tr><tr><td>O<\/td><td>Invalidate<\/td><td>&#8211;<\/td><td>I<\/td><td><\/td><\/tr><tr><td>O<\/td><td>Read-Miss<\/td><td>Flush<\/td><td>O<\/td><td>&#8211; RAM-Zugriff verhindern<br>&#8211; Cache-Block zu anfragendem Kern kopieren&nbsp;&nbsp;&nbsp;<\/td><\/tr><tr><td>O<\/td><td>Write-Miss<\/td><td>Flush<\/td><td>I<\/td><td><\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 20: Zustands\u00fcbergangs-Tabelle f\u00fcr MSI \/ MOSI \/ MESI \/ MOESI [46]<\/figcaption><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">Distributed Shared Memory (DSM)<\/h4>\n\n\n\n<p>DSM-Systeme sind im Gegensatz zu symmetrischen Multiprozessor-Systemen eine skalierbare L\u00f6sung f\u00fcr Multiprozessor-Systeme. Hierbei ist der Cache-Speicher und die dazugeh\u00f6rigen Zustands-Informationen auf alle Teilnehmer aufgeteilt und alle Kerne k\u00f6nnen sich \u00fcber ein Netzwerk direkt kontaktieren. Zus\u00e4tzlich existiert pro Knoten f\u00fcr jeden Speicher-Block ein Verzeichnis (Directory), welches unter Anderem Informationen dar\u00fcber enth\u00e4lt, welcher Teilnehmer eine Kopie des Speicher-Blocks h\u00e4lt.<\/p>\n\n\n\n<p>Dies ist jedoch deutlich langsamer als ein SMP-System, da oft \u00fcber mehrere Knoten hinweg kommuniziert wird. Da nun nicht mehr nur ein \u00dcbertragungs-Medium existiert und nicht mehr auf einen gemeinsamen Speicher zugegriffen werden muss, ist die Latenz und Auslastung nicht mehr abh\u00e4ngig von der Anzahl der Teilnehmer [20].<\/p>\n\n\n\n<p>Ein Beispiel-Protokoll zur Wahrung der Cache-Koh\u00e4renz in DSM-Systemen ist das Directory-Protokoll [19], auf das im weiteren Verlauf dieses Artikels aber nicht weiter eingegangen wird.<\/p>\n\n\n\n<p>DSM in Verbindung mit dem Directory-Protocol ist in folgender Abbildung f\u00fcr einen Teilnehmer visualisiert.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh3.googleusercontent.com\/95hYEu3dqAoIxRLi9OZcFciszc-PhvxFmvMqDh3cO9hHLNBq2NrYbk1vYeA9AZhSgsHCCQi-fml6jQby7-dJLIImKx9NP-JGazvyH8qv2JyNeKICXbjVHjK2Oyo7YTXdQw\" width=\"302\" height=\"227\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 12: Directory-Protokoll-Implementierung [60]. \u2018Memory\u2019 entspricht dem Speicher, welcher \u2018Kern_0\u2019 zugewiesen wurde. \u2018D\u2019 entspricht dem Directory-Speicher pro Cache-Block.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Synchronisation<\/h3>\n\n\n\n<p>Sowohl bei Uni-Core als auch bei Multi-Core-Systemen k\u00f6nnen Programm-Str\u00e4nge mit Hilfe verschiedener Threads gef\u00fchlt-parallel oder echt-parallel abgearbeitet werden. Daher wird in diesem Kapitel sowohl auf Single- als auch auf Multi-Core-Systeme Bezug genommen.<\/p>\n\n\n\n<p>Cache-Koh\u00e4renz erm\u00f6glicht es, dass Caches synchronisiert werden. Jedoch ist die Progamm-Abarbeitung dadurch noch nicht Thread-sicher, da Caches nur beim Beschreiben aktualisiert werden und Instruktionen nicht-atomar ausgef\u00fchrt werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Atomare Instruktion<\/h3>\n\n\n\n<p>Eine atomare Instruktion ist eine Instruktion, welche nicht von Threads des selben Kerns unterbrochen und nur von einem Kern gleichzeitig ausgef\u00fchrt werden kann. Manche Instruktionen sind bereits an sich schon atomar, wie zum Beispiel Load\/- und Store-Instruktionen (mov). Andere Instruktionen bestehen aus mehreren Teil-Schritten, wodurch die gesamte Instruktion zwischen den Teil-Schritten von anderen Threads unterbrochen werden kann. Unterbrechbare Instruktionen sind meist sogenannte Read-Modify-Write-(RMW)-Instruktionen [12]. Dies sind Instruktionen, welche bestimmte Daten vom Hauptspeicher oder Cache laden, diese manipulieren und anschlie\u00dfend wieder zur\u00fcck schreiben. Man kann hier bereits erahnen, dass solche Instruktionen mindestens aus drei Teil-Schritten bestehen, wobei jeder Teilschritt f\u00fcr sich atomar ist [61].<\/p>\n\n\n\n<p>Ein Beispiel einer unterbrechbaren Instruktion ist das Inkrementieren eines Wertes im Cache. In der folgenden Tabelle ist links die Anweisung in einer h\u00f6heren Programmiersprache, in der Mitte die entsprechende Instruktion und rechts die Teilschritte angegeben.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Anweisung<\/strong><\/td><td><strong>Instruktion (MASM)<\/strong><\/td><td><strong>Teil-Schritte (MASM)<\/strong><\/td><\/tr><tr><td>++x;<\/td><td>inc dword ptr [rcx]<\/td><td>mov edx,dword ptr [rcx]inc edxmov dword ptr [rcx],edx<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 21: Teilschritte einer Inkrementierungs-Anweisung.<\/figcaption><\/figure>\n\n\n\n<p>Wollen nun mehrere Threads gleichzeitig die Variable x inkrementieren, so k\u00f6nnen mehrere Threads denselben uninkrementierten Speicher-Wert aus dem Cache auslesen, ehe der aktualisierte Wert von einem der Threads wieder zur\u00fcck in den Cache geschrieben werden kann. Dies ist eine klassische Race-Condition und tritt auf, wenn mehrere Threads versuchen, den selben Speicher-Bereich zu manipulieren. In der folgenden Tabelle ist dieser Ablauf nochmal genauer veranschaulicht.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Instruktion<\/strong><\/td><td><strong>Thread1<\/strong><\/td><td><strong>Thread2<\/strong><\/td><td><strong>Cache<\/strong><\/td><\/tr><tr><td>&#8211;<\/td><td>0<\/td><td>0<\/td><td>7<\/td><\/tr><tr><td>T1: mov edx,dword ptr [ecx]<\/td><td>7<\/td><td>0<\/td><td>7<\/td><\/tr><tr><td>T1: inc edx<\/td><td>8<\/td><td>0<\/td><td>7<\/td><\/tr><tr><td>T2: mov edx,dword ptr [ecx]<\/td><td>8<\/td><td>7<\/td><td>7<\/td><\/tr><tr><td>T2: inc edx<\/td><td>8<\/td><td>8<\/td><td>7<\/td><\/tr><tr><td>T2: mov dword ptr [ecx],edx<\/td><td>8<\/td><td>8<\/td><td>8<\/td><\/tr><tr><td>T1: mov dword ptr [ecx],edx<\/td><td>8<\/td><td>8<\/td><td>8<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 22: Race-Condition zweier Threads. Cache-Speicher ist f\u00fcr beide Threads gleich, da bei einem Multiprozessor-System davon ausgegangen wird, dass die Caches koh\u00e4rent sind.<\/figcaption><\/figure>\n\n\n\n<p>Um solche Race-Conditions zu verhindern, k\u00f6nnen manche RMW-Instruktionen atomar ausgef\u00fchrt werden. Daf\u00fcr muss in Assembly ein \u2018lock\u2019-Prefix [38] vor die entsprechende Instruktion gesetzt werden. Im Falle der Inkrementations-Operation w\u00fcrde die Instruktion wie folgt aussehen: \u2018lock inc dword ptr [ecx]\u2019. Eine m\u00f6gliche Implementierung einer solchen atomaren RMW-Instruktion in Hardware kann mit Hilfe eines Memory-Controllers realisiert werden. Die Daten werden in dem Fall erst gar nicht vom CPU-Kern geladen, sondern die Manipulation der Daten dem Memory-Controller \u00fcberlassen. So findet die Instruktions Abarbeitung an einem zentralen Ort statt, um zu gew\u00e4hrleisten, dass die entsprechende Instruktion nicht gleichzeitig ausgef\u00fchrt wird. Der Memory-Controller erh\u00e4lt vom CPU-Kern eine Anfrage zur Abarbeitung der entsprechenden atomaren Instruktion mit den daf\u00fcr ben\u00f6tigten Parametern. Wird dieselbe Instruktion bereits f\u00fcr einen anderen Kern ausgef\u00fchrt, so wird dem anfragenden Kern \u00fcber einen BUSY-Interrupt mitgeteilt, dass die Anfrage gerade nicht verarbeitet werden kann und sp\u00e4ter nochmal eine Anfrage gestellt werden soll. Die Abarbeitung einer solchen Instruktion geschieht aber in der Regel so schnell, dass der Kern mit dem n\u00e4chsten Versuch kaum warten muss. Ist der Memory-Controller mit der Bearbeitung der Anfrage fertig, wird das entsprechende Flag im internen Speicher gel\u00f6scht, sodass darauffolgende Anfragen anderer Kerne zur Abarbeitung atomarer Instruktionen wieder ber\u00fccksichtigt werden k\u00f6nnen [31].<\/p>\n\n\n\n<p>Atomare Instruktionen sind die kleinste Synchronisations-Primitive und k\u00f6nnen als solche alleinstehend zum Manipulieren einzelner Daten verwendet werden. Jedoch muss beachtet werden, dass das Ausf\u00fchren atomarer Instruktionen verglichen an der nicht-atomaren Version der jeweiligen instruktion, deutlich l\u00e4nger ben\u00f6tigt, da nicht nur mit dem jeweiligen privaten Cache, sondern mit dem Memory-Controller kommuniziert werden muss, welcher selbst etwas Zeit zur Abarbeitung ben\u00f6tigt. Zus\u00e4tzlich werden durch das Arbeiten auf dem geteilten Speicher jedes Mal die Caches invalidiert. Daher sollte das Ausf\u00fchren atomarer Instruktionen so gut wie m\u00f6glich minimiert werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Locking, Hierarchisches Locking<\/h3>\n\n\n\n<p>Sollten komplizierte Operationen mit gr\u00f6\u00dferen Datens\u00e4tzen atomar ausgef\u00fchrt oder die Anzahl atomarer Instruktionen reduziert werden, eignet es sich, einen gr\u00f6\u00dferen Programm-Abschnitt zu sperren, welcher dann nur von einem Thread gleichzeitig durchlaufen werden kann. Solche Programm-Abschnitte werden auch kritische Sektionen [62] genannt. Die Idee ist dabei, dass die Threads nur am Anfang der kritischen Sektion synchronisiert werden m\u00fcssen, um abzukl\u00e4ren, welcher der Threads die kritische Sektion ausf\u00fchren darf. Innerhalb der kritischen Sektion darf der einzelne Thread die kritischen Operationen nicht-atomar ausf\u00fchren. Vor Verlassen der kritischen Sektion muss der Thread die Sektion wieder frei geben, sodass die anderen Threads auch die M\u00f6glichkeit haben, diese auszuf\u00fchren. Dies bringt einen enormen Geschwindigkeits-Vorteil gegen\u00fcber dem Best\u00fccken der kritischen Sektion mit atomaren Instruktionen [63].<\/p>\n\n\n\n<p>Das Gruppieren logischer Programm-Bereiche, um diese gemeinsam zu locken und somit weniger Locking-Overhead zu erhalten, wird auch als hierarchisches Locking bezeichnet [63].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Locking-Implementierung<\/h3>\n\n\n\n<p>Beim Locking existieren generell zwei Aktionen. Die erste Aktion ist das Locken der kritischen Sektion. Hierbei muss der Thread testen, ob ein Flag-Bit, welches im geteilten Speicher liegt, gesetzt ist. Wenn es gesetzt ist bedeutet dies, dass sich bereits ein anderer Thread in der kritischen Sektion befindet und daher diese f\u00fcr den aktuellen Thread gesperrt ist. Sollte das Lock-Flag jedoch nicht gesetzt sein, so setzt der aktuelle Thread das Lock-Flag und beginnt mit der Ausf\u00fchrung der kritischen Sektion [63].<\/p>\n\n\n\n<p>Da das Lesen, Vergleichen und gegebenenfalls Manipulieren des Lock-Flags atomar ablaufen muss, existieren entsprechende RMW-Instruktionen, welche atomar ausgef\u00fchrt werden k\u00f6nnen. Eine davon ist die Test-and-Set-Instruktion [31]. Hierbei wird der alte Flag-Wert zur\u00fcck gegeben und das Lock-Flag auf 1 gesetzt. Der eigentliche Vergleich kann dann nicht-atomar ausgef\u00fchrt werden, da gew\u00e4hrleistet ist, dass nur ein Thread eine 0 lesen kann, sollte die kritische Sektion nicht gesperrt sein.<\/p>\n\n\n\n<p>Ist die kritische Sektion gesperrt so existieren verschiedene M\u00f6glichkeiten, was der Thread tun soll.<\/p>\n\n\n\n<p>Im einfachsten Fall versucht der Thread die kritische Sektion so lange zu locken, bis er erfolgreich war. Diese Art von Lock wird auch als Spin-Lock bezeichnet [65]. Spin-Locks sind sinnvoll, wenn ein Kontext-Wechsel mehr Zeit in Anspruch nehmen w\u00fcrde, als auf das Freiwerden der kritischen Sektion zu warten.<\/p>\n\n\n\n<p>Stehen dem aktuellen Thread auch noch andere Aufgaben zur Abarbeitung zur Verf\u00fcgung, und h\u00e4ngen diese nicht unmittelbar von der kritischen Sektion ab, so kann der Thread bei misslungenem Locking-Versuch zun\u00e4chst die anderen Aufgaben abarbeiten. Somit kann der CPU-Kern optimal ausgelastet werden [10].<\/p>\n\n\n\n<p>Sollte es keine anderen Aufgaben f\u00fcr den aktuellen Thread geben und die kritische Sektion l\u00e4nger blockiert sein, bietet es sich an, den Thread zu pausieren und einen Kontext-Wechsel einzuleiten, um einen anderen Thread abzuarbeiten und so die CPU m\u00f6glichst gut auszulasten. Der pausierte Thread wird vom Betriebssystem wieder in die Warte-Schlange des Schedulers eingeh\u00e4ngt, wenn die kritische Sektion wieder frei gegeben wird [63].<\/p>\n\n\n\n<p>Die zweite Aktion, welche beim Locking notwendig ist, ist das Freigeben der kritischen Sektion. Hierbei muss lediglich das Lock-Flag wieder auf 0 gesetzt werden, was mit einer einfachen Store-Instruktion wie \u2018mov\u2019 implementiert werden kann, da diese bereits atomar ist [64].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Lock-Experiment<\/h3>\n\n\n\n<p>Mit Hilfe eines&nbsp; kleinen Experiments soll best\u00e4tigt werden, dass das Locken gr\u00f6\u00dferer Programm-Bereiche performanter ist, als das Verwenden entsprechender atomarer Instruktionen. Zus\u00e4tzlich soll am Beispiel des Lockings gezeigt werden, dass alle h\u00f6heren Synchronisations-Objekte h\u00f6herer Programmiersprachen wie Mutexes, auf atomaren RMW-Instruktionen aufbauen.<\/p>\n\n\n\n<p>Es sollen 8 Threads gestartet werden, von denen jeder eine geteilte Variable 300_000_000 Mal inkrementiert. Beim Locking wird die Variable entsprechend in der kritischen Sektion 300_000_000 Mal Inkrementiert, bevor der Thread die Sektion wieder frei gibt. F\u00fcr die Implementierung des Lockings wurde die Bit-Test-and-Set-Instruktion (BTS) [36] des IA32-Befehlssatz verwendet, da diese die IA32-Variante der Test-and-Set-Instruktion ist. Die BTS-Instruktion setzt dabei ein einzelnes Bit auf 1 und legt den alten Bit-Wert im Carry-Flag ab. Mit Hilfe des zweiten Parameters kann der Bit-Offset des entsprechenden Bits angegeben werden.<\/p>\n\n\n\n<p>Zu Beachten ist hier, dass das Locking nicht 8-Mal schneller als die nicht-gelockte Variante ist, sondern nur ca. doppelt so schnell. Dies ist darauf zur\u00fcck zu f\u00fchren, dass sich die Threads auch bei nicht-atomaren Instruktionen die Cache-Lines invalidieren, da die Cache-Koh\u00e4renz-Protokolle nachwievor aktiv sind, und somit eine gr\u00f6\u00dfere Bus-Auslastung hervorgerufen wird, was die Gesamt-Performance reduziert.<\/p>\n\n\n\n<p>Da die atomare BTS-Instruktion immer in den Speicher schreibt und damit die Cache-Lines anderer Kerne invalidiert werden, kann es bei einem Spin-Lock passieren, das sich die Kerne ihre Cache-Lines gegenseitig st\u00e4ndig invalidieren, w\u00e4hrend sie auf das Freiwerden der kritischen Sektion warten. Dadurch leidet die Gesamt-Performance des Systems, da der Daten-Bus unn\u00f6tig ausgelastet wird und dadurch andere Benachrichtigungen l\u00e4nger ben\u00f6tigen um verarbeitet zu werden [30].<\/p>\n\n\n\n<p>Um dies zu verhindern, gibt es die sogenannte \u2019Test &amp; Test-and-Set\u2019-Methodik [30]. Hierbei wird mit einer normalen Lade-Operation das Lock-Flag geladen und anschlie\u00dfend \u00fcberpr\u00fcft. Sollte das Flag gesetzt sein, wird das Flag nochmal geladen und \u00fcberpr\u00fcft, ob sich der Wert jetzt ge\u00e4ndert hat. Sollte das Flag nicht gesetzt sein, so wird versucht die kritische Sektion mittels der Test-and-Set-Operation zu sperren.<\/p>\n\n\n\n<p>Im Experiment wurde diese Methodik auch implementiert und sowohl die Variante mit, als auch die Variante ohne Test gemessen. Durch den zus\u00e4tzlichen Test konnte ein Performance-Gewinn von ca. \u2153 gemessen werden. Zus\u00e4tzlich zur Lock-Implementierung mittels Test-and-Set wurde die Lock-Funktionalit\u00e4t noch mit Hilfe der Compare-and-Swap-Operation [66] implementiert, um zu zeigen, dass verschiedene RMW-Instruktionen f\u00fcr die Lock-Implementierung herangezogen werden k\u00f6nnen. Zeitlich gibt es zwischen den beiden Implementierungen aber keine nennenswerten Unterschiede.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Variante<\/strong><\/td><td><strong>Zeit (s)<\/strong><\/td><td><strong>Code (MASM)<\/strong><\/td><\/tr><tr><td>ohne Synchronisation<\/td><td>1.966<\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh3.googleusercontent.com\/dLwLEVxcIduyaLqJisdjTqOSBHTkcNvFJ9i_dIuDQQSkvhHIHDAcnmHqLTis8w2Nzl-Du_oFQgiNA2RAMTzcSOcUuriG_UEEHUtmYjoYDwp_4VtOEg9jxz1_POZohoX42Q\" width=\"291\" height=\"105\"><\/td><\/tr><tr><td>mit atomarer Instruktion<\/td><td>51.896<\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/XkZQnfKC3Rp315YU9kVN5rBt5AjQ6rOOSJ10OnAJbGFnhfr16-YOfJ-bBcEgGMcXaNYccgtWSpWanAYejYTGo1x3Y7cu1BCczb0xurJ7IWxHoHV72KFa3z__7uf5m8SZnQ\" width=\"268\" height=\"107\"><\/td><\/tr><tr><td>Spin-Lock mit Test-and-Set<\/td><td>mit test: 4.537<br>ohne test: 6.676<\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/wzRdWz88HVD1avtZPRP7f_JKctvQ0L0CUpaAiKmArx4e2LeIe_bsr_px4M-U2PFIhO5Oclm-3opUWci0EiMPSzErGNYsilIXjEqOWymtpIRDQDuxFrDUyGgqES5gEYlHEw\" width=\"214\" height=\"202\"><\/td><\/tr><tr><td>Spin-Lock mit Compare-And-Swap<\/td><td>mit test: 4.493<br>ohne test: 6.828<\/td><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/nx-FGnUeow30KaRJ1MvxwLpZS80iL9VZhJJsaLJXsr-bcEMhJcXDOw2c4u2zM3TSRx7KbVX1FnY1sMxv21Uy_OYCWjshmJvucAidTe8hbIK60g7UdkYAYTJYK2YmG05l2w\" width=\"301\" height=\"228\"><\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 23: Lock-Implementierungen mit Compare-and-Swap und Test-and-Set.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Blocking vs. Non-Blocking<\/h3>\n\n\n\n<p>Blocking und Non-Blocking bezieht sich auf die Eigenschaft einer Funktion, wenn diese eine Aktion ausf\u00fchrt, welche unter Umst\u00e4nden nicht sofort abgeschlossen werden kann. Ein Beispiel sind Locking-Funktionen, welche versuchen, eine bestimmte kritische Sektion zu sperren. Sollte die Sektion bereits gesperrt sein und das Lock ein Spin-Lock sein oder bei misslungenem Locking ein Kontext-Wechsel vollzogen werden, so handelt es sich um einen Blocking-Aufruf, da aus dieser Funktion erst wieder zur\u00fcck gekehrt wird, wenn das Locking erfolgreich war. Die weitere Programm-Abarbeitung wird also blockiert. Dies ist w\u00fcnschenswert, wenn der darauffolgende Programm-Code nur ausgef\u00fchrt werden darf, wenn das Locking erfolgreich war oder allgemeiner gesagt, wenn eine bestimmte Bedingung eingetreten ist. Sollte die Anwendung aber weiterhin ansprechbar sein oder noch andere Aufgaben abarbeiten, so ist es besser, direkt eine Antwort von der Funktion zu erhalten. Anhand dem R\u00fcckgabe-Wert wei\u00df die Anwendung, ob der Aufruf erfolgreich war oder nicht und kann dadurch entweder die aktuelle oder eine andere Aufgabe abarbeiten, um die Echtzeit-Eigenschaft zu bewahren. Solche Funktionen werden nicht blockierende Funktionen genannt. Am Beispiel vom Locking wird einfach ein boolscher Wert zur\u00fcck gegeben, welcher angibt, ob das Locking erfolgreich war oder nicht, anstatt in einer Dauer-Schleife wie beim Spin-Lock zu verweilen [25]. Eine Beispiel Implementation eines Non-Blocking-Locks mit Hilfe von \u2018Test &amp; Test-and-Set\u2019 ist wie folgt gegeben.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/Rpm9Gp3mcRF-mKgGIU3k3ILbb9IwLOVrzpkIjEnpf7xvIbN-6xCd3obCNQzOuika3eJi17x0zK4htg_kYGJHHX63ZjZXp_IXhQdkT4W0IMwhvO9_KMq1tG3H4SgotCSGFg\" width=\"344\" height=\"235\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 13: nicht-blockierende Lock-Implementation mit Hilfe von Test-and-Set.<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Double-Checked-Locking-Pattern<\/h3>\n\n\n\n<p>Da Locking im Allgemeinen, bezogen auf die Performance, teuer ist, sollte es nur ausgef\u00fchrt werden, wenn es notwendig ist. Daher gibt es das sogenannte Double-Checked-Locking-Pattern. Die Idee bei dem Pattern ist, dass das Locking nur ausgef\u00fchrt werden soll, wenn eine bestimmte Bedingung, bezogen auf die Logik der Anwendung, eintritt, wie zum Beispiel wenn ein Array Elemente enth\u00e4lt, also nicht leer ist. Wenn die Bedingung eingetreten ist, kann versucht werden, die kritische Sektion zu locken. Bei erfolgreichem Locking muss jedoch nochmals getestet werden, ob die Bedingung noch erf\u00fcllt ist, da ein anderer Thread bereits in die kritische Sektion eingetreten sein k\u00f6nnte und daher die Bedingung evtl. gar nicht mehr erf\u00fcllt ist. Da zweimal getestet werden muss, nennt sich das Pattern \u2018Double-Checked-Locking\u2019 [21].<\/p>\n\n\n\n<p>Ein typisches Anwendungsgebiet sind Singleton-Patterns, da hier nur das einmalige Erzeugen des Objektes gelockt werden muss. Das Erhalten der bereits existierenden Referenz kann ohne Locking ausgef\u00fchrt werden [21].<\/p>\n\n\n\n<p>Die Syntax sieht grob wie folgt aus:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\" data-line=\"\">if (&lt;condition&gt;){\n    lock();\n    if (&lt;condition&gt;) {&lt;do work&gt;}\n    unlock();\n}\n<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">Dead-Lock<\/h4>\n\n\n\n<p>Im Zusammenhang mit Locking muss darauf geachtet werden, dass das Sperren und Freigeben kritischer Sektionen so strukturiert ist, dass es nicht passieren kann das zwei Threads jeweils auf die Freigabe der kritischen Sektion des jeweils anderen Threads warten. Dieses Szenario nennt man Dead-Lock, weil damit die weitere Programm-Abarbeitung nicht mehr m\u00f6glich ist [6].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Synchronisations-Objekte<\/h4>\n\n\n\n<p>Aufbauend auf atomaren Instruktionen und Locking k\u00f6nnen verschiedene Synchronisations-Objekte implementiert werden, welche in verschiedenen Anwendungsgebieten in h\u00f6heren Programmier-Modellen beziehungsweise Programmier-Sprachen Verwendung finden [10]. Im Folgenden Abschnitt werden zwei M\u00f6gliche Synchronisations-Objekte betrachtet.<\/p>\n\n\n\n<p>Das erste ist das Mutex-Objekt, hierbei handelt es sich eigentlich nur um eine andere Beschreibung f\u00fcr das klassische Locking. Das Mutex repr\u00e4sentiert hierbei intern ein Lock-Flag und bietet standardm\u00e4\u00dfig die Funktionen lock(), tryLock() und unlock() an. Mutex steht f\u00fcr \u2018Mutual Exclusive\u2019 (Gegenseitig Ausschlie\u00dfend). Damit ist die Charakteristik einer kritischen Sektion gemeint. Nur ein Thread gleichzeitig kann das Mutex besitzen [10].<\/p>\n\n\n\n<p>Ein etwas komplexeres Objekt ist das Semaphore. Hierbei existiert kein Flag, welches angibt, ob eine Sektion gesperrt ist, sondern ein Z\u00e4hler. Damit ist es m\u00f6glich, dass mehrere Threads gleichzeitig eine bestimmte Sektion betreten k\u00f6nnen. Der Z\u00e4hler gibt dabei an, wie viele Threads die Sektion erfolgreich locken d\u00fcrfen. Erreicht der Z\u00e4hler 0, so werden darauffolgende Threads in einer Queue abgelegt und pausiert. Das Semaphore-Objekt besitzt in der Regel 2 Funktionen. Eine zum Inkrementieren des Z\u00e4hlers und eine zum Dekrementieren. Wird der Z\u00e4hler inkrementiert, wird zun\u00e4chst geschaut, ob in der Queue ein Thread existiert. Wenn dem so ist, wird dieser aus der Queue entfernt und der Scheduler-Queue hinzugef\u00fcgt. Der Z\u00e4hler wird nur inkrementiert, wenn kein wartender Thread existiert [13].<\/p>\n\n\n\n<p>Mit Hilfe von Semaphoren k\u00f6nnen Patterns wie das \u2018Producer-Consumer\u2019-Pattern implementiert werden, in welchem Threads auf Berechnungs-Ergebnisse anderer Threads warten. Die Producer-Threads k\u00f6nnen dann die Consumer-Threads durch das Inkrementieren des Semaphore-Z\u00e4hlers informieren, wenn neue Arbeit verf\u00fcgbar ist [67].<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Threads<\/h4>\n\n\n\n<p>Ein Thread kann als unabh\u00e4ngiger Teil eines Prozesses beschrieben werden. [49]<\/p>\n\n\n\n<p>Als Prozess wird die Ausf\u00fchrung eines Programms bezeichnet, welches eine Eingabe erh\u00e4lt und auf Basis dieser Eingabe und des entsprechenden Programms eine Ausgabe liefert.&nbsp;<\/p>\n\n\n\n<p>Ein Thread &#8211; auch Aktivit\u00e4tstr\u00e4ger genannt &#8211; ist im eigentlichen Sinne ein Ausf\u00fchrungsstrang in der Abarbeitung eines Computerprogramms. Threads sind unabh\u00e4ngig von anderen Prozessteilen. Sie nutzen einen gemeinsamen Prozessspeicherbereich sowie einen eigenen User- und Kernel-Mode-Stack. Sie lassen sich priorisieren, zudem ist im Falle von Multi-Kern-System durch Threads echte Parallelit\u00e4t erreichbar. Steht nur ein Kern zur Verf\u00fcgung l\u00e4sst sich durch h\u00e4ufige Kontextwechsel eine gef\u00fchlte Parallelit\u00e4t erreichen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Kontext-Wechsel<\/h4>\n\n\n\n<p>Auf handels\u00fcblichen Computern laufen eine Vielzahl von Prozessen. Dabei handelt es sich sowohl um die vom Nutzer gestartete Anwendung sowie um Prozesse, die im Hintergrund laufen.&nbsp;&nbsp;<\/p>\n\n\n\n<p>Geht man von einem Ein-Kern-System aus, so kann zu einem Zeitpunkt immer nur ein Prozess auf der CPU bearbeitet werden. Dennoch f\u00fchlt es sich f\u00fcr den Nutzer so an, als w\u00fcrden alle Anwendungen parallel laufen. Diese gef\u00fchlte Parallelit\u00e4t wird durch h\u00e4ufige und sehr schnelle Kontextwechsel erreicht.&nbsp;<\/p>\n\n\n\n<p>Kontextwechsel k\u00f6nnen unter anderem durch einen hardwareseitigen Interrupt hervorgerufen werden. Es existiert diesbez\u00fcglich ein Hardware-Z\u00e4hler, der nach einer gewissen Zeit einen Compare-Interrupt feuert. Das laufende Programm wird somit unterbrochen. Auf der CPU l\u00e4uft nun das Betriebssystem welches somit die Kontrolle erlangt. [50]<\/p>\n\n\n\n<p>Letzteres kann nun aufgrund des Prozess-Schedulers entscheiden, welcher Anwendung als n\u00e4chstes Zeit auf der CPU zur Verf\u00fcgung gestellt wird und wie lange. Diesbez\u00fcglich sollte nat\u00fcrlich unbedingt darauf geachtet werden, dass zu jedem Zeitpunkt ein Prozess auf der CPU l\u00e4uft, um diese optimal zu nutzen. Ben\u00f6tigt eine Anwendung bestimmte Daten, die es \u00fcber einen I\/O-Request anfordert, so kann es in sehr einfachen Systemen w\u00e4hrend der Wartezeit zur Unt\u00e4tigkeit der CPU kommen. Diese Ressourcenverschwendung gilt es nat\u00fcrlich zu vermeiden.&nbsp;<\/p>\n\n\n\n<p>In etwas komplexeren Systemen werden daher verschiedene Prozesse zur gleichen Zeit im Memory gehalten. Sobald eine Anwendung warten muss, beispielsweise auf das Eintreffen angeforderter Daten, kann auch ein softwareseitiger Interrupt vorgenommen werden. Durch einen syscall informiert die Anwendung die CPU, dass diese pausiert werden kann.<\/p>\n\n\n\n<p>Es folgt ein Kontextwechsel. Die Wartezeit wird somit f\u00fcr eine andere Anwendung genutzt. Welche Anwendung das im einzelnen ist h\u00e4ngt dabei vom Scheduler ab.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Vorteile von Threads<\/h4>\n\n\n\n<p>Wie sich aufgrund des vorangegangenen Kapitels vermuten l\u00e4sst, bringen Threads einige Vorteile mit sich.&nbsp;<\/p>\n\n\n\n<p>Neben der bereits beschriebenen individuellen Rechenzeitzuteilung, was zu einer besseren CPU-Auslastung f\u00fchrt, l\u00e4sst sich mithilfe von Threads auch die Programmstruktur vereinfachen. Besonders geeignet sind hier Serverprogramme, welche Client-Requests abarbeiten. Jedem Client kann hier ein Thread zugewiesen werden. Im Gegensatz zu Prozessen, bei denen ein Kontextwechsel vergleichsweise lange dauert, sind hier mithilfe von Threads sehr schnelle Kontextwechsel m\u00f6glich.<\/p>\n\n\n\n<p>Ein weiterer Vorteil von Threads ist die erm\u00f6glichte Parallelisierung im Kontext von Multikernprozessoren. Laufen verschiedene Threads auf verschiedenen, physisch existierenden Kernen, so wird echte Parallelisierung erreicht.&nbsp;<\/p>\n\n\n\n<p>Es kann zudem eine architektonisch saubere Struktur von Programmen aufgezogen werden, indem man das Shared-Memory-Programmiermodell im Falle von Multikernprozessoren anwendet. Durch die Benutzung dieses gemeinsamen Speichers kann eine schnelle Interprozesskommunikation realisiert werden. Dabei gilt es allerdings, Raise-Conditions durch ein hinreichendes Ma\u00df an Synchronisation zu vermeiden.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Thread-Scheduling &#8211; Eigenes Experiment<\/h4>\n\n\n\n<p>Um die Performance eines Multi-Prozessor-Systems zu maximieren, bedarf es einer m\u00f6glichst performanten Scheduling-Strategie. Im folgenden wurde ein Gedankenexperiment gemacht, welches in Teilen implementiert worden ist. Einen \u00dcberblick \u00fcber die Strategie soll das folgende Bild geben.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/ON898lvBxxr3p3Ubru3irEn2JkcGl6psRc2ggTCInY_GM6USmIEayoKtnqOSES6clwAb0yEm4OVINuoEOpeBr8q2q69JCj1EDyN5PkmnK7eQmTCqNh8M_hZ603xsilvsdg\" width=\"602\" height=\"468\"><\/td><\/tr><\/tbody><\/table><figcaption>Abbildung 14: Zu einer Gruppe geh\u00f6rende Tasks k\u00f6nnen aus der Main-Queue auf verschiedene Task-Worker verteilt werden, welche diese parallel abarbeiten.<\/figcaption><\/figure>\n\n\n\n<p>Die Grundidee besteht darin, bestehende Tasks zun\u00e4chst in einer Main-Queue zu halten. Tasks, die sich innerhalb einer Gruppe befinden, k\u00f6nnen gleichzeitig ausgef\u00fchrt werden. Sie sind also unabh\u00e4ngig voneinander, sodass w\u00e4hrend ihrer Abarbeitung keine weitere Kommunikation n\u00f6tig ist.<\/p>\n\n\n\n<p>Zus\u00e4tzlich existieren verschiedene Task-Worker, die ihre eigene Task-Queue besitzen.<\/p>\n\n\n\n<p>Ein Task-Worker kann nun \u00fcberpr\u00fcfen, ob sich mindestens ein Task in der Main-Queue befindet.<\/p>\n\n\n\n<p>Befindet sich in der Main-Queue mindestens ein Task, so kann ein Task-Worker auf die Main-Queue ein Lock anwenden. Damit ist gew\u00e4hrleistet, dass kein anderer Task-Worker zum gleichen Zeitpunkt Tasks von der Main-Queue in die eigene Task-Queue \u00fcbertragen kann. Der entsprechende Task-Worker muss zudem noch einen Lock auf seine eigene Task-Queue setzen. Die Begr\u00fcndung hierf\u00fcr folgt in K\u00fcrze. Der entsprechende Task kann jetzt vom Task-Worker abgearbeitet werden. Befinden sich mehrere Tasks in der Main-Queue, so werden diese von den verschiedenen Workern in ihre jeweiligen Task-Queues \u00fcbertragen und k\u00f6nnen somit zur gleichen Zeit verarbeitet werden, wodurch echte Parallelit\u00e4t entsteht.&nbsp;<\/p>\n\n\n\n<p>Durch das Locking entsteht nat\u00fcrlich ein gewisses Ma\u00df an Overhead. W\u00e4hrend die Main-Queue gelockt ist, k\u00f6nnen keine anderen Task-Worker auf die Main-Queue zugreifen. Es ist demnach sinnvoll, nicht nur einen Task, sondern direkt mehrere Tasks von der Main-Queue in die Task-Queue zu \u00fcbertragen, um den Overhead zu verringern.&nbsp;<\/p>\n\n\n\n<p>Stellt ein Task-Worker fest, dass sich aktuell keine Tasks in der Main-Queue befinden, ein anderer Task-Worker jedoch einige Tasks in dessen Task-Queue hat, so ist der Task-Worker in der Lage, Tasks von einer fremden Task-Queue in seine eigenen Task-Queue zu \u00fcbertragen. Dies erh\u00f6ht die Parallelit\u00e4t und erkl\u00e4rt zudem, warum beim \u00dcbertragungsvorgang aus der Main-Queue in die eigene Task-Queue letztere ebenfalls gelockt werden muss.<\/p>\n\n\n\n<p>Selbstverst\u00e4ndlich f\u00fchrt auch das \u201cKlauen\u201d von Tasks aus fremden Task-Queues zu einem Overhead, den es so gering wie m\u00f6glich zu halten gilt. Das \u00dcbertragen eines einzelnen Tasks w\u00e4re in diesem Zusammenhang daher nicht sinnvoll. Der einfachste Ansatz, um dem Overhead entgegenzuwirken, ist die Einf\u00fchrung einer Mindestanzahl an zu \u00fcbertragenen Tasks. Stellt ein Task-Worker fest, dass sich weniger Tasks in einer fremden Task-Queue befinden, wartet er einfach auf neue Tasks in der Main Queue.<\/p>\n\n\n\n<p>Um die Scheduling-Strategie noch effizienter zu gestalten, w\u00e4re es sinnvoll, Informationen \u00fcber die Komplexit\u00e4t und die damit verbundene Rechendauer einzelner Tasks zu erlangen. Ist die Mindestanzahl der zu \u00fcbertragenden Tasks beispielsweise auf 5 gesetzt und ein Task-Worker hat gerade 4 Tasks in seiner Task-Queue, so wird ihm kein anderer Task-Worker Tasks abnehmen. Handelt es sich dabei jedoch um mindestens einen sehr aufw\u00e4ndigen Task, so sind alle anderen Task-Worker unter Umst\u00e4nden \u00fcber eine lange Zeit inaktiv. Sinnvoller w\u00e4re es demnach, die Komplexit\u00e4t der einzelnen Tasks in die Entscheidung, ob Tasks von einem Task-Worker zu einem anderen Task-Worker \u00fcbertragen werden, miteinflie\u00dfen zu lassen.&nbsp;<\/p>\n\n\n\n<p>Dies kann zum einen manuell geschehen. Der Programmierer gibt dabei die gesch\u00e4tzte Task-Dauer als Metrik mit an. Es k\u00f6nnten hier zwischen drei verschiedenen l\u00e4ngen unterschieden werden, kurz, mittel und lang. Stellt nun ein Task-Worker fest, dass ein anderer Task-Worker einige lange Tasks in seiner Task-Queue hat, so w\u00fcrde sich das Locking sowie die \u00dcbertragung wahrscheinlich schon bei einem einzelnen Task lohnen. In \u00e4hnlicher Weise k\u00f6nnte anhand der Komplexit\u00e4t nun auch entschieden werden, wie viele Tasks ein einzelner Task-Worker aus der Main-Queue in seine eigenen Queue \u00fcbernimmt.&nbsp;<\/p>\n\n\n\n<p>Noch eleganter w\u00e4re es, die Komplexit\u00e4t einzelnen Tasks automatisch zu ermitteln und dem Programmierer diesen Schritt abzunehmen. Die Dauer eines Tasks muss hier beim erstmaligen Durchlauf ermittelt werden. Wird ein Task mehrfach ausgef\u00fchrt oder l\u00e4sst sich eine gro\u00dfe \u00c4hnlichkeit zwischen mehreren Tasks feststellen, kann zur Compilezeit eine Art Schl\u00fcsselwort \u00fcbergeben werden, um dem Compiler die gesch\u00e4tzte Komplexit\u00e4t des jeweiligen Tasks mitzuteilen.&nbsp;<\/p>\n\n\n\n<p>Zudem w\u00e4re eine Sch\u00e4tzung anhand der ben\u00f6tigten Instruktionen oder anhand des Parser-Baums denkbar.<\/p>\n\n\n\n<p>Selbstverst\u00e4ndlich gibt es mittlerweile zahlreiche Strategien, die \u00fcblicherweise eingesetzt werden. Eine Auswahl davon wird im n\u00e4chsten Kapitel behandelt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Thread-Scheduling-Strategien<\/h4>\n\n\n\n<p>Eine der g\u00e4ngigen Strategien, die unserem Experiment aus dem vorherigen Kapitel relativ nahe kommt, die das sogenannte <strong>Load-Sharing. <\/strong>[51]<strong> <\/strong>Es existiert eine globale Queue, in der die Threads gehalten werden. Sobald ein Prozessor keine Aufgabe mehr hat, \u00fcbernimmt er einen Thread aus der Queue. Die Lastverteilung folgt hierbei einer relativ best\u00e4ndigen Strategie. Vorteile dieses relativ einfachen Vorgehens sind unter anderem die gleichm\u00e4\u00dfige Verteilung von Last auf die Prozessoren. Zudem wird bei dieser Strategie kein zentraler Scheduler ben\u00f6tigt. Da diese Strategie sehr viel von Einzel-Prozessor-Systemen \u00fcbernimmt, kann die die globale Queue beim Load-Sharing in gleicher Weise aufgebaut werden wie bei beliebigen Schemata von Einzel-Prozessor-Systemen.<\/p>\n\n\n\n<p>Eine weitere Strategie wird als so genanntes <strong>Gang-Scheduling <\/strong>bezeichnet. [52] Hier werden in erster Linie Threads gleichzeitig bearbeitet, die m\u00f6glichst zum gleichen Prozess geh\u00f6ren. Gang-Scheduling ist vor allem f\u00fcr den Fall interessant, wenn zwei oder mehr Threads oder Prozesse miteinander kommunizieren m\u00fcssen. Diese Strategie sorgt dann daf\u00fcr, dass dies zum gleichen Zeitpunkt geschehen kann, ohne dass ein Thread auf den anderen warten muss um Daten zu senden oder zu empfangen, was zu Leerlaufzeiten f\u00fchren w\u00fcrde.&nbsp;<\/p>\n\n\n\n<p>Eine v\u00f6llig andere Strategie stellt das <strong>Dedicated-Processor-Assignment <\/strong>dar. [53] Wenn das Scheduling einer Applikation stattfindet, wird hier jeder Thread einem Prozessor zugeordnet. Diese Zuordnung bleibt bestehen, bis die Applikation vollendet ist. Sollte ein Thread w\u00e4hrend des Programmablaufs unt\u00e4tig werden, da er aufgrund von I\/O oder Synchronisation nichts tun kann, so bleibt die entsprechende CPU in dieser Zeit unt\u00e4tig.&nbsp;<\/p>\n\n\n\n<p>Dies mag zun\u00e4chst ineffizient erscheinen, schlie\u00dflich werden die Thread-Scheduling-Strategien eingesetzt, um die Last m\u00f6glichst effizient abzuarbeiten und Unt\u00e4tigkeiten zu vermeiden. Diese Strategie hat allerdings ihre Berechtigung, und zwar im Rahmen von Massiv-Parallelen-Systemen mit vielen tausend Prozessoren. In diesem Rahmen spielt die Nutzung eines einzelnen Prozessors keine allzu gro\u00dfe Rolle mehr. Die Vermeidung von Overhead durch Prozess-Switching wiederum sorgt in diesem Fall f\u00fcr einen schnelleren Programmablauf.&nbsp;Nicht unerw\u00e4hnt bleiben soll in diesem Zusammenhang das <strong>Dynamic-Scheduling. <\/strong>[54] F\u00fcr manche Applikationen lassen sich System- und Sprachwerkzeuge zur Verf\u00fcgung stellen, die es erm\u00f6glichen, die Anzahl der Threads dynamisch zu ver\u00e4ndern. In diesem Fall kann das Betriebssystem die Last anpassen, um so die gegebene Anzahl an Threads in m\u00f6glichst optimaler Weise auszulasten. Bei dieser Strategie sind sowohl das Betriebssystem als auch die Applikation selbst am eigentlichen Scheduling-Prozess beteiligt. Dabei ist die Aufgabe des Betriebssystems vorrangig, die jeweiligen Prozessoren in sinnvoller Art und Weise zu allokieren. Das Dynamic-Scheduling ist dem Gang-Scheduling und dem Dedicated-Processor-Assignment f\u00fcr Anwendungen \u00fcberlegen, die von dieser Art des Schedulings gebrauch machen k\u00f6nnen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Speicher-Allokatoren<\/h2>\n\n\n\n<p>Speicher-Allokatoren dienen dem Allokieren und Freigeben von Speicher-Bereichen des Heaps. Dabei verwalten die Allokatoren einen bestimmten Speicher-Bereich und geben davon Teile auf Anfrage an die Anwendung zur freien Verwendung raus. Ben\u00f6tigt die Anwendung den Speicher-Block nicht mehr, so gibt sie ihn an den Allokator zur\u00fcck. Es existieren verschiedenen Arten von Allokatoren, welche jeweils f\u00fcr bestimmte Anwendungsgebiete geeignet sind. Da das Allokieren und Deallokieren von Heap-Speicher in Anwendungen oft verwendung findet, ist die Performance solcher Allokatoren entsprechend wichtig. Aber auch die Speicher-Effizienz spielt eine wichtige Rolle. Die Allokatoren k\u00f6nnen entsprechend ihrer F\u00e4higkeiten in drei Gruppen eingeteilt werden. Allokatoren, mit welchen unterschiedlich gro\u00dfe Speicher-Bl\u00f6cke allokiert werden k\u00f6nnen, Allokatoren, mit denen Speicher-Bl\u00f6cke in beliebiger Reihenfolge allokiert und deallokiert werden k\u00f6nnen, oder Allokatoren, mit welchen unterschiedlich gro\u00dfe Bl\u00f6cke in beliebiger Reihenfolge allokiert und deallokiert werden k\u00f6nnen [1].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">General Purpose<\/h3>\n\n\n\n<p>Die letzte Eigenschaft erfordert eine deutlich komplexere Logik, was zu einer deutlich schlechteren Performance f\u00fchrt. Zudem m\u00fcssen f\u00fcr jeden Speicher-Block sowohl Adresse als auch Gr\u00f6\u00dfe gespeichert werden, um beim Freigeben eines Speicher-Blocks die Gr\u00f6\u00dfe des freiwerdenden Bereichs bestimmen zu k\u00f6nnen. Ein weiterer Nachteil, was sich ebenfalls auf die Speicher-Effizienz negativ auswirkt ist, dass es zu Speicher-Fragmentierung kommen kann. Dabei entstehen durch das Allokieren und Deallokieren beliebig gro\u00dfer Speicher-Bereiche l\u00fccken die aber eventuell f\u00fcr weitere Allokationen nicht verwendet werden k\u00f6nnen, da diese zu klein sind. So kann die summe aller L\u00fccken der angefragten Speicher-Block-Gr\u00f6\u00dfe entsprechen, der Speicher aber nicht genutzt werden, da er nicht zusammenh\u00e4ngend ist. Um den Speicher besser auszunutzen kann dieser defragmentiert werden. Dabei werden die allokierten Speicher-Bl\u00f6cke verschoben, um freie L\u00fccken zu schlie\u00dfen und so mehr zusammenh\u00e4ngenden freien Speicher zu erhalten. Dies ist aber nur m\u00f6glich, wenn die Zeiger auf die Speicher-Bl\u00f6cke durch eine Indirektion f\u00fcr \u00e4u\u00dfere Anwendungs-Komponenten zugreifbar sind, da die Speicher-Bl\u00f6cke nach der Defragmentierung eventuell an einer anderen Speicher-Adresse liegen k\u00f6nnten und \u00e4u\u00dfere Komponenten so auf eine falsche Adresse zugreifen w\u00fcrden.. Zudem erfordert Defragmentierung zus\u00e4tzlich Rechenaufwand, welcher sich wiederum negativ auf die Performance auswirkt.Solche Allokatoren werden General-Purpose-Allocators genannt. Diese sollten eher bei allgemeinen und seltenen Allokationen verwendet werden.<\/p>\n\n\n\n<p>Ein typischer General-Purpose-Allokator ist der malloc()\/free() aus der C-Programmiersprache [1].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Stack<\/h3>\n\n\n\n<p>Muss die Allokations\/- und Deallokations-Reihenfolge nicht variabel sein, so kann ein Stack-Allokator verwendet werden. Hierbei k\u00f6nnen unterschiedlich gro\u00dfe Bl\u00f6cke allokiert werden. Die Allokations\/- und Deallokations-Reihenfolge muss jedoch dem LOFI-Prinzip entsprechen (Last-Out-First-In). Dadurch wird die Speicher-Fragmentierung von vornherein verhindert, was sich positiv auf die Speicher-Effizienz auswirkt. Zudem ist die Zugriffszeit O(1), da immer der zuletzt allokierte Block wieder frei gegeben wird und daher ein Suchen des freizugebenden Blocks nicht erforderlich ist.<\/p>\n\n\n\n<p>Geeignet ist der Allokator f\u00fcr Initialisierungsvorg\u00e4nge, bei dem unterschiedlich gro\u00dfe Objekte, welche aber nur einmalig erzeugt werden m\u00fcssen, erzeugt und sp\u00e4ter wieder in entgegengesetzter Richtung zerst\u00f6rt werden [1].<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Pool<\/h3>\n\n\n\n<p>Mit Hilfe des Pool-Allokators k\u00f6nnen Bl\u00f6cke gleicher Gr\u00f6\u00dfe in beliebiger Reihenfolge allokiert und deallokiert werden. Dadurch wird der Speicher mit diesem Allokator ebenfalls nicht fragmentiert. Da alle Bl\u00f6cke gleich gro\u00df sind, kann beim Allokieren beziehungsweise Freigeben des Speichers, die position durch einfache Berechnungen ermittelt werden, sodass auch hier die betroffenen Speicher-Bl\u00f6cke nicht gesucht werden m\u00fcssen, was einer Zugriffs-Zeit von O(1) entspricht.<\/p>\n\n\n\n<p>Pool-Allokatoren werden immer dann verwendet, wenn viele Objekte eines bestimmten Typs ben\u00f6tigt werden. Dies ist zum Beispiel bei Projektilen in Computer-Spielen oder Physik-Simulationen der Fall [1].<\/p>\n\n\n\n<p>Im Folgenden wurden Zeit\/- und Speicher-Verbrauchs-Messungen durchgef\u00fchrt, um festzustellen, wie gro\u00df die Performance-Unterschiede der einzelnen Allokatoren bezogen auf Zeit und Platz sind.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Experiment &#8211; Allocator<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Speicher-Verbrauch<\/h4>\n\n\n\n<p>Die Speicher-Werte wurden aus dem Monitoring-Fenster von Visual-Studio entnommen. Der initiale Speicher-Verbrauch dieses Prozesses betr\u00e4gt 1,4 MB. Der vorgenommenen Messung l\u00e4sst sich entnehmen, dass der Pool\/Stack-Allokator etwa 12% weniger Speicher als der General-Purpose-Allokator ben\u00f6tigt.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Block-Gr\u00f6\u00dfe(Byte)<\/strong><\/td><td><strong>Anzahl Bl\u00f6cke<\/strong><\/td><td><strong>Angefragter Speicher (MB)<\/strong><\/td><td><strong>Pool (MB)<\/strong><\/td><td><strong>Stack (MB)<\/strong><\/td><td><strong>General Purpose (MB)<\/strong><\/td><\/tr><tr><td>256<\/td><td>10.000<\/td><td>2.441<\/td><td>3.9<\/td><td>4<\/td><td>5,2<\/td><\/tr><tr><td>1024<\/td><td>10.000<\/td><td>9.766<\/td><td>11,3<\/td><td>11,4<\/td><td>12,6<\/td><\/tr><tr><td>10.000<\/td><td>10.000<\/td><td>95.367<\/td><td>97<\/td><td>97,1<\/td><td>115,5<\/td><\/tr><tr><td>100.000<\/td><td>10.000<\/td><td>953.674<\/td><td>957<\/td><td>957,1<\/td><td>962,4<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 24: Ben\u00f6tigter Speicher verschiedener Allokatoren f\u00fcr dieselbe Menge an angefragtem Speicher.<\/figcaption><\/figure>\n\n\n\n<p>Es wurde erwartet, dass der ben\u00f6tigte Speicher des General-Purpose-Allokators bei gr\u00f6\u00dferen Speicher-Mengen-Anfragen deutlich schneller anw\u00e4chst als beim Pool-\/ und Stack-Allokator, da aufgrund der Speicher-Fragmentierung mehr Speicher ungenutzt bleibt. Je mehr Speicher belegt ist, desto mehr fragmentierten Speicher und daher auch zus\u00e4tzlicher Speicher wird beim General-Purpose-Allokator ben\u00f6tigt. Jedoch konnte dies bei den Messungen nicht best\u00e4tigt werden.<\/p>\n\n\n\n<p>Dies k\u00f6nnte daran liegen, dass alle allokierten Speicher-Bl\u00f6cke die selbe Gr\u00f6\u00dfe besitzen und daher ein besseres Ausnutzen des Speichers m\u00f6glich ist. Um aussagekr\u00e4ftigere Messergebnisse zu erhalten, k\u00f6nnte eine umfangreiche Messung durchgef\u00fchrt werden, welche sowohl unterschiedliche Block-Gr\u00f6\u00dfen, als auch unterschiedliche Block-Mengen allokiert. Die Block-Gr\u00f6\u00dfen k\u00f6nnten hierbei wiederum in unterschiedlichen Reihenfolgen allokiert werden. Dies wurde aber im Rahmen dieses Projekts nicht mehr durchgef\u00fchrt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Performance<\/h4>\n\n\n\n<p>Bei den eigenen Allokatoren, Pool und Stack, wurden zwei Messungen, einmal mit und einmal ohne Locking, durchgef\u00fchrt. Dadurch sind die Ergebnisse aussagekr\u00e4ftiger, da Malloc, welcher als General-Purpose-Allokator verwendet wurde, standardm\u00e4\u00edg Locking enth\u00e4lt. Die untere Messung in einem Feld entspricht immer der mit Lock().<\/p>\n\n\n\n<p>Die Messung kam zustande, indem &lt;Anzahl Bl\u00f6cke&gt;*&lt;Block-Gr\u00f6\u00dfe&gt;-Gro\u00dfe Speicher-Bl\u00f6cke allokiert und danach wieder deallokiert wurden. Dieser Vorgang wurde 100 Mal wiederholt.<\/p>\n\n\n\n<p>Je gr\u00f6\u00dfer die zu allokierenden Speicher-Bl\u00f6cke werden, desto schwieriger ist es f\u00fcr den General-Purpose-Allokator, passende freie Speicher-Bereiche zu finden. Dies kann anhand der Messungen auch sehr sch\u00f6n veranschaulicht werden. Die ben\u00f6tigte Zeit steigt immer schneller, je gr\u00f6\u00dfer die Speicher-Bl\u00f6cke werden.<\/p>\n\n\n\n<p>Die Zeiten der eigenen Allokatoren ver\u00e4ndern sich nicht, da deren Zugriffszeiten O(1) sind [1].<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Block-Gr\u00f6\u00dfe (Byte)<\/strong><\/td><td><strong>Anzahl Bl\u00f6cke<\/strong><\/td><td><strong>Pool (sec)<\/strong><\/td><td><strong>Pool Thread-sicher (sec)<\/strong><\/td><td><strong>Stack<\/strong><\/td><td><strong>Stack Thread-sicher (sec)<\/strong><\/td><td><strong>General Purpose<\/strong><\/td><\/tr><tr><td>256<\/td><td>10.000<\/td><td>0,125<\/td><td>0,352<\/td><td>0,353<\/td><td>0,601<\/td><td>0,641<\/td><\/tr><tr><td>1024<\/td><td>10.000<\/td><td>0,112<\/td><td>0,344<\/td><td>0,358<\/td><td>0,571<\/td><td>1,079<\/td><\/tr><tr><td>10.000<\/td><td>10.000<\/td><td>0,109<\/td><td>0,361<\/td><td>0,351<\/td><td>0,585<\/td><td>5,926<\/td><\/tr><tr><td>100.000<\/td><td>10.000<\/td><td>0,112<\/td><td>0,325<\/td><td>0,349<\/td><td>0,620<\/td><td>57,101<\/td><\/tr><\/tbody><\/table><figcaption>Tabelle 25: Ben\u00f6tigte Zeit zum Allokieren \/ Deallokieren einer bestimmten Menge an Speicher.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Quellen<\/h2>\n\n\n\n<p>[1] Gregory, Jason: Game Engine Architecture. Chapman and Hall\/CRC, London: CRC Press, Taylor &amp; Francis Group, 2018.<\/p>\n\n\n\n<p>[2] &#8220;Asynchronous Messaging Patterns&#8221; &#8211; <a href=\"https:\/\/blogs.mulesoft.com\/dev\/design-dev\/asynchronous-messaging-patterns\/\">https:\/\/blogs.mulesoft.com\/dev\/design-dev\/asynchronous-messaging-patterns\/<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[3] &#8220;In Praise of Computer Architecture: A Quantitative Approach Fourth Edition&#8221; &#8211; <a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.115.1881&amp;rep=rep1&amp;type=pdf\">https:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.115.1881&amp;rep=rep1&amp;type=pdf<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[4] &#8220;Cache&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Cache\">https:\/\/de.wikipedia.org\/wiki\/Cache<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[5] &#8220;Cache-Koh\u00e4renz&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Cache-Koh%C3%A4renz\">https:\/\/de.wikipedia.org\/wiki\/Cache-Koh\u00e4renz<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[6] &#8220;Deadlock (Informatik)&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Deadlock_(Informatik)\">https:\/\/de.wikipedia.org\/wiki\/Deadlock_(Informatik)<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[7] &#8220;Flynnsche Klassifikation&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Flynnsche_Klassifikation\">https:\/\/de.wikipedia.org\/wiki\/Flynnsche_Klassifikation<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[8] &#8220;Lock&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Lock\">https:\/\/de.wikipedia.org\/wiki\/Lock<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[9] &#8220;Lokalit\u00e4tseigenschaft&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Lokalit%C3%A4tseigenschaft\">https:\/\/de.wikipedia.org\/wiki\/Lokalit\u00e4tseigenschaft<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[10] &#8220;Mutex&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Mutex\">https:\/\/de.wikipedia.org\/wiki\/Mutex<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[11] &#8220;Portable Operating System Interface&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Portable_Operating_System_Interface\">https:\/\/de.wikipedia.org\/wiki\/Portable_Operating_System_Interface<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[12] &#8220;RMW-Befehl&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/RMW-Befehl\">https:\/\/de.wikipedia.org\/wiki\/RMW-Befehl<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[13] &#8220;Semaphor (Informatik)&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Semaphor_(Informatik)\">https:\/\/de.wikipedia.org\/wiki\/Semaphor_(Informatik)<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[14] &#8220;Streaming SIMD Extensions&#8221; &#8211; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Streaming_SIMD_Extensions\">https:\/\/de.wikipedia.org\/wiki\/Streaming_SIMD_Extensions<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[15] &#8220;4 Design Patterns In Web Development&#8221; &#8211; <a href=\"https:\/\/dev.to\/flippedcoding\/4-design-patterns-in-web-development-55p7\">https:\/\/dev.to\/flippedcoding\/4-design-patterns-in-web-development-55p7<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[16] &#8220;Priority Queue pattern&#8221; &#8211; <a href=\"https:\/\/docs.microsoft.com\/en-us\/azure\/architecture\/patterns\/priority-queue\">https:\/\/docs.microsoft.com\/en-us\/azure\/architecture\/patterns\/priority-queue<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[17] &#8220;Bus snooping&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bus_snooping\">https:\/\/en.wikipedia.org\/wiki\/Bus_snooping<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[18] &#8220;Compare-and-swap&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Compare-and-swap\">https:\/\/en.wikipedia.org\/wiki\/Compare-and-swap<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[19] &#8220;Directory-based cache coherence&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Directory-based_cache_coherence\">https:\/\/en.wikipedia.org\/wiki\/Directory-based_cache_coherence<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[20] &#8220;Distributed shared memory&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Distributed_shared_memory\">https:\/\/en.wikipedia.org\/wiki\/Distributed_shared_memory<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[21] &#8220;Double-checked locking&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Double-checked_locking\">https:\/\/en.wikipedia.org\/wiki\/Double-checked_locking<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[22] &#8220;MESI protocol&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/MESI_protocol\">https:\/\/en.wikipedia.org\/wiki\/MESI_protocol<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[23] &#8220;MOSI protocol&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/MOSI_protocol\">https:\/\/en.wikipedia.org\/wiki\/MOSI_protocol<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[24] &#8220;MSI protocol&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/MSI_protocol\">https:\/\/en.wikipedia.org\/wiki\/MSI_protocol<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[25] &#8220;Non-blocking algorithm&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Non-blocking_algorithm\">https:\/\/en.wikipedia.org\/wiki\/Non-blocking_algorithm<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[26] &#8220;Comparison with AHCI&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/NVM_Express#Comparison_with_AHCI\">https:\/\/en.wikipedia.org\/wiki\/NVM_Express#Comparison_with_AHCI<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[27] &#8220;Reactor pattern&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Reactor_pattern\">https:\/\/en.wikipedia.org\/wiki\/Reactor_pattern<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[28] &#8220;SIMD&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/SIMD\">https:\/\/en.wikipedia.org\/wiki\/SIMD<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[29] &#8220;Symmetric multiprocessing&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Symmetric_multiprocessing\">https:\/\/en.wikipedia.org\/wiki\/Symmetric_multiprocessing<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[30] &#8220;Test and test-and-set&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Test_and_test-and-set\">https:\/\/en.wikipedia.org\/wiki\/Test_and_test-and-set<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[31] &#8220;Test-and-set&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Test-and-set\">https:\/\/en.wikipedia.org\/wiki\/Test-and-set<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[32] &#8220;Event Queue&#8221; &#8211; <a href=\"https:\/\/gameprogrammingpatterns.com\/event-queue.html\">https:\/\/gameprogrammingpatterns.com\/event-queue.html<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[33] &#8220;Concurrency vs Event Loop vs Event Loop + Concurrency&#8221; &#8211; <a href=\"https:\/\/medium.com\/@tigranbs\/concurrency-vs-event-loop-vs-event-loop-concurrency-eb542ad4067b\">https:\/\/medium.com\/@tigranbs\/concurrency-vs-event-loop-vs-event-loop-concurrency-eb542ad4067b<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[34] &#8220;Empty Standby List&#8221; &#8211; <a href=\"https:\/\/wj32.org\/wp\/software\/empty-standby-list\/\">https:\/\/wj32.org\/wp\/software\/empty-standby-list\/<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[35] &#8220;I\/O Bottlenecks: Biggest Threat to Data Storage&#8221; &#8211; <a href=\"https:\/\/www.enterprisestorageforum.com\/technology\/features\/article.php\/3856121\/IO-Bottlenecks-Biggest-Threat-to-Data-Storage.htm\">https:\/\/www.enterprisestorageforum.com\/technology\/features\/article.php\/3856121\/IO-Bottlenecks-Biggest-Threat-to-Data-Storage.htm<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[36] &#8220;BTS \u2014 Bit Test and Set&#8221; &#8211; <a href=\"https:\/\/www.felixcloutier.com\/x86\/bts\">https:\/\/www.felixcloutier.com\/x86\/bts<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[37] &#8220;CMPXCHG \u2014 Compare and Exchange&#8221; &#8211; <a href=\"https:\/\/www.felixcloutier.com\/x86\/cmpxchg\">https:\/\/www.felixcloutier.com\/x86\/cmpxchg<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[38] &#8220;LOCK \u2014 Assert LOCK# Signal Prefix&#8221; &#8211; <a href=\"https:\/\/www.felixcloutier.com\/x86\/lock\">https:\/\/www.felixcloutier.com\/x86\/lock<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[39] &#8220;Investigating I\/O bottlenecks&#8221; &#8211; <a href=\"https:\/\/www.mssqltips.com\/sqlservertutorial\/254\/investigating-io-bottlenecks\/\">https:\/\/www.mssqltips.com\/sqlservertutorial\/254\/investigating-io-bottlenecks\/<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[40] &#8220;I\/O Bottleneck&#8221; &#8211; <a href=\"https:\/\/www.techopedia.com\/definition\/30479\/io-bottleneck\">https:\/\/www.techopedia.com\/definition\/30479\/io-bottleneck<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[41] &#8220;Strategy Design Pattern&#8221; &#8211; <a href=\"https:\/\/www.youtube.com\/watch?v=-NCgRD9-C6o\">https:\/\/www.youtube.com\/watch?v=-NCgRD9-C6o<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[42] &#8220;4 2 3 MSI Write Invalidate Protocol&#8221; &#8211; <a href=\"https:\/\/www.youtube.com\/watch?v=ctLdDiCDF28\">https:\/\/www.youtube.com\/watch?v=ctLdDiCDF28<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[43] &#8220;5 &#8211; CPU vs I\/O Bound Operations&#8221; &#8211; <a href=\"https:\/\/www.youtube.com\/watch?v=On0k9VMN9bE\">https:\/\/www.youtube.com\/watch?v=On0k9VMN9bE<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[44] &#8220;CPU Bound vs. I\/O Bound | Computer Basics&#8221; &#8211; <a href=\"https:\/\/www.youtube.com\/watch?v=Wsv07g4ml8I\">https:\/\/www.youtube.com\/watch?v=Wsv07g4ml8I<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[45] &#8220;Cache Memory Explained&#8221; &#8211; <a href=\"https:\/\/www.youtube.com\/watch?v=Zr8WKIOIKsk\">https:\/\/www.youtube.com\/watch?v=Zr8WKIOIKsk<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[46] &#8220;MOESI protocol&#8221; &#8211; <a href=\"https:\/\/en.wikipedia.org\/wiki\/MOESI_protocol\">https:\/\/en.wikipedia.org\/wiki\/MOESI_protocol<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[47] &#8220;Branchless Programming: Why &#8220;if&#8221; is Slowww&#8230; and what we can do about it!&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=bVJ-mWWL7cE\">https:\/\/www.youtube.com\/watch?v=bVJ-mWWL7cE<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[48] &#8220;Pipeline (Prozessor)&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Pipeline_(Prozessor)\">https:\/\/de.wikipedia.org\/wiki\/Pipeline_(Prozessor)<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[49] &#8220;Prozesse und Threads | #Betriebssysteme&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=TGgUEamLvGs\">https:\/\/www.youtube.com\/watch?v=TGgUEamLvGs<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[50] &#8220;Introduction to CPU Scheduling&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=EWkQl0n0w5M\">https:\/\/www.youtube.com\/watch?v=EWkQl0n0w5M<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[51] &#8220;popular multiprocessor thread-scheduling strategies&#8221; <a href=\"https:\/\/www.sawaal.com\/operating-systems-question-and-answers\/explain-the-popular-multiprocessor-thread-scheduling-strategies_3393\">https:\/\/www.sawaal.com\/operating-systems-question-and-answers\/explain-the-popular-multiprocessor-thread-scheduling-strategies_3393<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[52] &#8220;Gang scheduling&#8221; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gang_scheduling\">https:\/\/en.wikipedia.org\/wiki\/Gang_scheduling<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[53] &#8220;Dedicated Processor Assignment : Thread Scheduling&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=osNTAYqekl8\">https:\/\/www.youtube.com\/watch?v=osNTAYqekl8<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[54] &#8220;Dynamic Scheduling : Thread Scheduling&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=uRDZRmHT8V4\">https:\/\/www.youtube.com\/watch?v=uRDZRmHT8V4<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[55] &#8220;Branch (computer sience)&#8221; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Branch_%28computer_science%29\">https:\/\/en.wikipedia.org\/wiki\/Branch_(computer_science)<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[56] &#8220;MMX&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Multi_Media_Extension\">https:\/\/de.wikipedia.org\/wiki\/Multi_Media_Extension<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[57] &#8220;AVX&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Advanced_Vector_Extensions\">https:\/\/de.wikipedia.org\/wiki\/Advanced_Vector_Extensions<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[58] &#8220;Intrinsische Funktion&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Intrinsische_Funktion\">https:\/\/de.wikipedia.org\/wiki\/Intrinsische_Funktion<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[59] &#8220;See How a CPU Works&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=cNN_tTXABUA&amp;t=212s\">https:\/\/www.youtube.com\/watch?v=cNN_tTXABUA&amp;t=212s<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[60] &#8220;Scalable Cache Coherence&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=VlU41fxzbrU\">https:\/\/www.youtube.com\/watch?v=VlU41fxzbrU<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[61] &#8220;Atomare Operation&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Atomare_Operation\">https:\/\/de.wikipedia.org\/wiki\/Atomare_Operation<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[62] &#8220;Kritischer Abschnitt&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Kritischer_Abschnitt\">https:\/\/de.wikipedia.org\/wiki\/Kritischer_Abschnitt<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[63] &#8220;Lock&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Lock\">https:\/\/de.wikipedia.org\/wiki\/Lock<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[64] &#8220;x64 Assembly MultiThreading 3: Mutexes, SpinLocks and Critical Sections&#8221; <a href=\"https:\/\/www.youtube.com\/watch?v=R8Ttz8bJ81o&amp;list=PL0C5C980A28FEE68D&amp;index=71\">https:\/\/www.youtube.com\/watch?v=R8Ttz8bJ81o&amp;list=PL0C5C980A28FEE68D&amp;index=71<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[65] &#8220;Spinlock&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Spinlock\">https:\/\/de.wikipedia.org\/wiki\/Spinlock<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[66] &#8220;Compare-and-swap&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Compare-and-swap\">https:\/\/de.wikipedia.org\/wiki\/Compare-and-swap<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n\n\n\n<p>[67] &#8220;Erzeuger-Verbraucher-Problem&#8221; <a href=\"https:\/\/de.wikipedia.org\/wiki\/Erzeuger-Verbraucher-Problem\">https:\/\/de.wikipedia.org\/wiki\/Erzeuger-Verbraucher-Problem<\/a> &#8211; letzter Zugriff: 2021-02-27<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Geschrieben von Steffen K\u00f6hler und Laurin Keim. Einleitung Bei dem vorliegenden Block-Post handelt es sich um den Zusammenschrieb eines Studentenprojekts mit dem Motto \u201cLast effizient abarbeiten\u201d. In diesem wurden verschiedene Vorgehensweisen, Protokolle und in gewissem Ma\u00dfe auch Hardware-Architekturen erarbeitet und nachvollzogen. Dabei wurden teilweise eigene Vorgehensweisen erdacht und anschlie\u00dfend mit bereits bestehenden Protokollen verglichen. W\u00e4hrend [&hellip;]<\/p>\n","protected":false},"author":1013,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[651,2],"tags":[],"ppma_author":[837],"class_list":["post-12711","post","type-post","status-publish","format-standard","hentry","category-system-designs","category-system-engineering"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":23945,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2023\/02\/05\/jamstack-und-astro-vor-und-nachteile-einer-serverless-architektur\/","url_meta":{"origin":12711,"position":0},"title":"JAMStack und Astro:  Vor- und Nachteile einer serverless Architektur","author":"zack walker","date":"5. February 2023","format":false,"excerpt":"Einleitung Seit den fr\u00fchen Tagen der Web-Entwicklung hat die Performance von Websites eine wichtige Rolle gespielt. W\u00e4hrend sich das Internet im Laufe der Jahre weiterentwickelt hat, haben sich auch die Anforderungen an die Performance von Websites erh\u00f6ht. Benutzer erwarten eine schnelle und reibungslose Nutzererfahrung, unabh\u00e4ngig von der Gr\u00f6\u00dfe ihres Ger\u00e4ts\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/02\/Screenshot-2023-02-05-at-22.08.11.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/02\/Screenshot-2023-02-05-at-22.08.11.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/02\/Screenshot-2023-02-05-at-22.08.11.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/02\/Screenshot-2023-02-05-at-22.08.11.png?resize=700%2C400&ssl=1 2x"},"classes":[]},{"id":24536,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2023\/03\/19\/von-studierenden-fur-studierende-grundlagentutorium-unterstutzung-empowerment\/","url_meta":{"origin":12711,"position":1},"title":"Von Studierenden f\u00fcr Studierende: Grundlagentutorium &#8211; Unterst\u00fctzung &amp; Empowerment","author":"Tamara Hezel","date":"19. March 2023","format":false,"excerpt":"Kim Bastiaanse, Tamara Hezel Einleitung Die Idee zu unserem Projekt entstand aus einem Gespr\u00e4ch mit einer Studentin des 3. Semesters. Aufgrund von Wissensl\u00fccken und Unsicherheiten hatte sie \u00fcberlegt, ihr Studium abzubrechen. Wir f\u00fchlten uns direkt in unsere ersten Semester im Studiengang Mobile Medien zur\u00fcckversetzt und \u00fcberlegten, was uns damals geholfen\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/gMqnGsMdK7UF6sYIWMq7XDYYPl2O4KeKk7VGGfIir9JTXBQmmmb42idNXZAuCf71_KaTrmKinBIjQ2I0_xrUYEUeByfVcjRUg1umCfJC8Fv2ftIohCIrfkI4udGuMoBvVKMms7Oj9549xtAkH4dLQ_c.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/gMqnGsMdK7UF6sYIWMq7XDYYPl2O4KeKk7VGGfIir9JTXBQmmmb42idNXZAuCf71_KaTrmKinBIjQ2I0_xrUYEUeByfVcjRUg1umCfJC8Fv2ftIohCIrfkI4udGuMoBvVKMms7Oj9549xtAkH4dLQ_c.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/gMqnGsMdK7UF6sYIWMq7XDYYPl2O4KeKk7VGGfIir9JTXBQmmmb42idNXZAuCf71_KaTrmKinBIjQ2I0_xrUYEUeByfVcjRUg1umCfJC8Fv2ftIohCIrfkI4udGuMoBvVKMms7Oj9549xtAkH4dLQ_c.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":11711,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2020\/09\/29\/perfekter-gluhwein-fur-zuhause-thermometer-mit-raspberry-pi-und-aws\/","url_meta":{"origin":12711,"position":2},"title":"Perfekter Gl\u00fchwein f\u00fcr Zuhause: Thermometer mit Raspberry Pi und AWS","author":"jg129","date":"29. September 2020","format":false,"excerpt":"Abstract Kein anderes Getr\u00e4nk ist mit Weihnachtsm\u00e4rkten so verbunden wie Gl\u00fchwein. Und so trinkt sich der ausschweifende Weihnachtsmarktbesucher im Laufe der Adventszeit von Stand zu Stand bis er schlie\u00dflich am Ende des Jahres seinen Lieblingsstand gefunden hat. Doch auch daheim kann der perfekte Gl\u00fchwein gelingen.\u00a0 Wir zeigen, wie man sich\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/lh3.googleusercontent.com\/rbu36fXExVo14XfyUicXbIFjAgh1bvNnXHlaUVRfqLevpyZx4KVyjeuYdgItPx6y39R8L9Ub_hug03LYM3AIAW_F14vhBiXOZlt92qIpN0Y2h0H-czZ65ERnn3qUoWVh7JfI5ihA","width":350,"height":200,"srcset":"https:\/\/lh3.googleusercontent.com\/rbu36fXExVo14XfyUicXbIFjAgh1bvNnXHlaUVRfqLevpyZx4KVyjeuYdgItPx6y39R8L9Ub_hug03LYM3AIAW_F14vhBiXOZlt92qIpN0Y2h0H-czZ65ERnn3qUoWVh7JfI5ihA 1x, https:\/\/lh3.googleusercontent.com\/rbu36fXExVo14XfyUicXbIFjAgh1bvNnXHlaUVRfqLevpyZx4KVyjeuYdgItPx6y39R8L9Ub_hug03LYM3AIAW_F14vhBiXOZlt92qIpN0Y2h0H-czZ65ERnn3qUoWVh7JfI5ihA 1.5x"},"classes":[]},{"id":25607,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2023\/08\/15\/usability-in-code-an-overview-from-ide-to-ai\/","url_meta":{"origin":12711,"position":3},"title":"Usability in Code an Overview from IDE to AI","author":"Marc Schillke","date":"15. August 2023","format":false,"excerpt":"Wenn man \u00fcber Usability Kontext von IT redet, wird ein integraler Part gerne komplett \u00fcbersehen: Den Entwickler.Wie soll Usability richtig umgesetzt werden wenn, der der Beides umsetzten, muss von beiden Themen w\u00e4hrend seiner Arbeit nichts mitbekommt?Warum h\u00f6rt Usability immer dort auf, wo der Entwickler auf sein Handwerkszeug schaut? Die Fragen\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=1050%2C600&ssl=1 3x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2023\/08\/download.webp?resize=1400%2C800&ssl=1 4x"},"classes":[]},{"id":20446,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2021\/08\/14\/supply-chain-attacks\/","url_meta":{"origin":12711,"position":4},"title":"Supply Chain Attacks &#8211; Die Lieferkette schl\u00e4gt zur\u00fcck","author":"Verena Eichinger","date":"14. August 2021","format":false,"excerpt":"ein Artikel von Verena Eichinger, Amelie Kassner und Elisa Zeller Nach SolarWinds schafft es eine neue Schlagzeile aus der IT-Welt in den Massenmedien ihre Kreise zu ziehen. \u00dcber 500 Superm\u00e4rkte in Schweden mussten wegen eines Cyberangriffs schlie\u00dfen. Wie bereits bei SolarWinds handelt es sich auch hier um eine Supply Chain\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=1050%2C600&ssl=1 3x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/08\/titelbild-1.png?resize=1400%2C800&ssl=1 4x"},"classes":[]},{"id":21753,"url":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2021\/09\/26\/the-way-of-system-thinking\/","url_meta":{"origin":12711,"position":5},"title":"The Way of System Thinking &#8211; Was Systemdenken ausmacht","author":"Julia Grimm","date":"26. September 2021","format":false,"excerpt":"Ein Artikel von Jessica Hofmann und Julia Grimm In unserem Leben, egal ob im Privaten oder Beruf, m\u00fcssen wir Entscheidungen treffen. Diese Entscheidungen haben so gut wie immer eine Konsequenz. Bei allt\u00e4glichen Entscheidungen ist uns das oft nicht bewusst. Erst bei gro\u00dfen und schweren Entscheidungen sind wir Menschen uns dar\u00fcber\u2026","rel":"","context":"In &quot;Allgemein&quot;","block_context":{"text":"Allgemein","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/category\/allgemein\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/09\/systems-thinking.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/09\/systems-thinking.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/09\/systems-thinking.jpg?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2021\/09\/systems-thinking.jpg?resize=700%2C400&ssl=1 2x"},"classes":[]}],"jetpack_sharing_enabled":true,"authors":[{"term_id":837,"user_id":1013,"is_guest":0,"slug":"lk173","display_name":"Laurin Keim","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/60b6efc7d4ed4727f12ba72dc11998e5218fea7205564129792591e6a90dbc44?s=96&d=mm&r=g","0":null,"1":"","2":"","3":"","4":"","5":"","6":"","7":"","8":""}],"_links":{"self":[{"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/posts\/12711","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/users\/1013"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/comments?post=12711"}],"version-history":[{"count":16,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/posts\/12711\/revisions"}],"predecessor-version":[{"id":12791,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/posts\/12711\/revisions\/12791"}],"wp:attachment":[{"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/media?parent=12711"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/categories?post=12711"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/tags?post=12711"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/wp-json\/wp\/v2\/ppma_author?post=12711"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}