Auf GPU rechnen

Heutige Rechner haben bekanntlich sehr leistungsfähige CPUs mit „Quadcore“ und mehr.
Aber auch die Grafikkarten sind ziemlich toll geworden und haben zum Teil auch so große eigene Lüfter wie die CPU.
Sie haben eine Menge eigenes Memory und sie können recht komplizierte Operationen selbsttätig rechnen, natürlich nur für die grafische Darstellung.

Nun stellt sich die Frage, ob man das auch sonst zum Rechnen benutzen kann. Man hört Geschichten, dass die Grafikkarte um Größenordnungen leistungsfähiger als die CPU sei. Warum schaffen das die Grafikkartenhersteller so leicht nebenbei, besser als die CPU in deren Kernaufgabe zu sein und außerdem noch Grafik darzustellen?

Grafikkarten bieten die Möglichkeit, massiv parallel zu rechnen, aber nach dem Prinzip SIMD. Das heißt, dass ein oder sehr wenige Befehlsströme verarbeitet werden und eine große Zahl von Recheneinheiten jeweils den identischen Code mit verschiedenen Daten ausführt. Für Vektoroperationen ist das optimal. Und es erklärt auch die brachiale Leistung der Grafikchips, weil man den aufwändigen Teil, Maschinencode zu interpretieren, nur einmal (oder wenige Male) baut und nur die eigentliche Recheneinheit mehrfach. Man bekommt so mit derselben Siliziummenge mehr Rechenleistung, aber mit der Einschränkung, SIMD (oder fast SIMD) zu sein. Aber man hat diese Geräte in den Rechnern drin. Es gibt sogar „Grafikkarten“, die nur rechnen können, aber bei denen man die eigentlichen Grafikchips weggelassen hat. Und viele Rechner haben den Grafikkern mit auf dem selben Chip wie die CPU-Kerne, so dass man eine einfache Grafik zur Verfügung hat, aber man baut dann doch zusätzlich noch eine externe Grafikkarte ein, die noch besser ist. Selbst ohne die Grafikfähigkeit zu gefährden hat man also eine GPU zum Rechnen übrig.

Nun ist das Programmieren dieser Geräte nicht so einfach. Grundsätzlich muss man sich mit einem völlig neuen Programmiermodell herumschlagen. Viele Algorithmen lassen sich speziell für SIMD entwickeln, aber sie sind anders als was wir gewohnt sind und automatisch lässt sich da nur beschränkt etwas optimieren. In der Regel muss man also mit C das Programm schreiben und kann dabei auf OpenCL bauen. Das ist ein nützlicher Standard, der einiges erleichtert, aber es bleibt schwierig. Für manche Zwecke lohnt es sich aber, den Entwicklungsaufwand zu treiben.

Vor ein paar Tagen habe ich drei Vorträge über Ansätze gehört, F# zu verwenden, um die GPU zu programmieren. Man kann also unter Einhaltung gewisser Regeln F#-Programme schreiben, die sich etwa in OpenCL übersetzen lassen und dann compiliert die GPU nutzen:

  • FSCL: Homogeneous Programming and Execution on Heterogeneous Platforms (by Gabriele Cocco, Pisa University)
  • Professional GPU Development with F# and the Alea Compiler Suite (by Daniel Egloff, QuantAlea)
  • New Abstractions for Radically Simplified GPU Programming in F# and .NET (by Luc Bläser, HSR, based on joint work with QuantAlea)

All diese Ansätze sollten schon heute oder zumindest in zukünftigen Implementierungen auch für Mono laufen und damit für Linux zur Verfügung stehen.

Es würde wohl den Rahmen dieses Artikels sprengen, im Einzelnen darauf einzugehen, aber vielleicht kann ich noch Links bekommen, die auf weiterführendes Material zu den einzelnen Lösungsansätzen führen.

Share Button

Laptopnetzteile

Bei Mobiltelefonen hat es endlich geklappt, dass alle Telefone denselben Anschluss für USB-Kabel und Ladegerät unterstützen. Fast alle, nämlich genaugenommen alle außer Apple. Aber die überwältigende Mehrheit der Mobiltelefone hat denselben Anschluss und funktioniert mit denselben Ladegeräten.

So etwas wäre bei Laptops auch schön. Tatsache ist aber, dass jeder Hersteller eine Vielfalt von Modellen hat, die sich noch laufend ändern, typischerweise auch innerhalb derselben Modellbezeichnung, und die auch jeweils spezifische Netzteile brauchen. Wenn man sein Netzteil vergessen hat und in einen großen Computerladen geht, kann man das selbstverständlich bestellen, aber die Chance, dass ein passendes Teil in dem Laden oder in einem anderen Laden in einer größeren Stadt (z.B. Zürich) direkt erhältlich ist, ist vernachlässigbar. Das war schon vor 10-15 Jahren so.

Es wäre wirklich gut, wenn sich wie beim Mobiltelefon die Hersteller auf einen Standard für Netzteile für alle Laptops (meinetwegen wieder alle bis auf einen Hersteller mit einem angebissenen-Obst-Logo) einigen könnten. Ich glaube, darüber würden sich viele Kunden freuen. Aber sie schaffen es ja heute nicht einmal innerhalb ihrer eigenen Marke, was angeblich der Hersteller mit halb gegessenen Apfel immerhin geschafft haben soll, zumindest mit einer größeren Adaptersammlung.

So werden wir also weiterhin viel Elektronikmüll produzieren, weil gute Netzteile in den Müll wandern, wenn der Laptop dazu kaputt ist, und wir werden weiterhin ein paar Stunden mit der Fahrt verbringen, wenn wir das Netzteil einmal vergessen haben.

Share Button

RISC und CISC

Vor 20 Jahren gab es einen starken Trend, Mikroprossoren mit RISC-Technologie (reduced instruction set computer), zu bauen. Jeder größere Hersteller wollte so etwas bauen, Sun mit Sparc, Silicon Graphics mit MIPS, HP mit PA-Risc, IBM schon sehr früh mit RS6000, was später, als man auf die Idee kam, das zu vermarkten, als PowerPC rebranded wurde, DEC mit Alpha u.s.w. Zu einer Zeit, als man zumindest in Gedanken noch für möglich hielt Assembler zu programmieren (auch wenn man es kaum noch tat), tat das noch richtig weh. Und Software war doch sehr CPU-abhängig, weil plattformunabhägige Sprache, die es damals selbstverständlich schon lange vor Java gab, einfach wegen des Overheads der Interpretation für viele Zwecke zu langsam waren. So behalf man sich mit C-Programmen mit wahren Orgien an ifdfefs und konnte die mit etwas Glück für die jeweilige Plattform aus CPU und einem UNIX-Derivat kompilieren. Der Wechsel der CPU-Architektur eines Herstellers war damals eine große Sache, z.B. bei Sun von Motorola 680×0 zu Sparc. Und die Assemblerprogrammierung der RISC-CPUs war ein Albtraum, an den sich auch erfahrene Assemblerprogrammierer kaum herangewagt haben. Zum Glück gab es damals schon sehr gut optimierende Compiler für C und Fortran und so konnte man das Thema einem ganz kleinen Personenkreis für die Entwicklung von kleinen Teilen des Betriebssytemkerns und kleinen hochperformanten Teilen großer Libraries überlassen.

Eigentlich sollte RISC ermöglichen, mit derselben Menge an Silizium mehr Rechenleistung zu erzielen, insgesamt also Geld und vielleicht sogar Strom zu sparen. Vor allem wollte man für die richtig coole Server-Applikation, die leider immer etwas zu ressourchenhungrig für reale Hardware war, endlich die richtige Maschine kaufen können. RISC war der richtige Weg, denn so hat man einen Optmierungsschritt beim Compiler, der alles optimal auf die Maschinensprache abbildet, die optimiert dafür ist, schnell zu laufen. Ich wüsste nicht, was daran falsch ist, wenn auch diese Theorie vorübergehend nicht zum Zuge kam. Intel konnte das Problem mit so viel Geld bewerfen, dass sie trotz der ungünstigeren CISC-Architektur immer noch schneller waren. Natürlich wurde dann intern RISC benutzt und das irgendwie transparent zur Laufzeit übersetzt, statt zur Compilezeit, wie es eigentlich besser wäre. Tatsache ist aber, dass die CISC-CPUs von Intel, AMD und Co. letztlich den RISC-CPUs überlegen waren und so haben sie sich weitgehend durchgesetzt.

Dabei hat sich die CPU-Abhängigkeit inzwischen stark abgemildert. Man braucht heute kaum noch Assembler. Die Plattformen haben sich zumindest auf OS-Ebene zwischen den Unix-Varianten angeglichen, so dass C-Programme leichter überall kompilierbar sind als vor 20 Jahren, mit cygwin sogar oft unter MS-Windows, wenn man darauf Wert legt. Applikationsentwicklung findet heute tatsächlich weitgehend mit Programmiersprachen wie Java, C#, Scala, F#, Ruby, Perl, Python u.ä. statt, die plattformunabhängig sind, mittels Mono sogar F# und C#. Und ein Wechsel der CPU-Architektur für eine Hardware-Hersteller ist heute keine große Sache mehr, wie man beim Wechsel eines Herstellers von PowerPC zur Intel-Architektur sehen konnte. Man kann sogar mit Linux dasselbe Betriebssystem auf einer unglaublichen Vielfalt von Hardware haben. Die große Mehrheit der schnellsten Supercomputer, die allermeisten neu vekrauften Smartphones und alle möglichen CPU-Architekturen laufen mit demselben Betriebssystemkern, kompiliert für die jeweilige Hardware. Sogar Microsoft scheint langsam fähig zu sein, verschiedene CPU-Architekturen gleichzeitig zu unterstützen, was lange Zeit außerhalb der Fähigkeiten dieser Firma zu liegen schien, wie man an NT für Alpha sehen konnte, was ohne große finanzielle Zuwendungen seitens DEC nicht aufrechterhalten werden konnte.

Aber nun, in einer Zeit, in der die CPU-Architektur eigentlich keine Rolle mehr spielen sollte, scheint alles auf Intel zu setzen, zum Glück nicht nur auf Intel, sondern auch auf einige konkurrierende Anbieter derselben Architektur wie z.B. AMD. Ein genauerer Blick zeigt aber, das RISC nicht tot ist, sonder klammheimlich als ARM-CPU seinen Siegeszug feiert. Mobiltelefone habe häufig ARM-CPUs, wobei das aus den oben genannten Gründen heute fast niemanden interessiert, weil die Apps ja darauf laufen. Tablet-Computer und Netbooks und Laptops sieht man auch vermehrt mit ARM-CPUs. Der Vorteil der RISC-Architektur manifestiert sich dort nicht in höherer Rechenleistung, sondern in niedrigerem Stromverbrauch.

Ist die Zeit reif und CISC wird in den nächsten zehn Jahren wirklich durch RISC verdrängt?

Oder bleibt RISC in der Nische der portablen stromsparendenen Geräte stark, während CISC auf Server und leistungsfähigen Arbeitsplatzrechnern dominierend bleibt? Wir werden es sehen. Ich denke, dass früher oder später der Vorteil der RISC-Architektur an Relevanz auf leistungsfähigen Servern und Arbeitsplatzrechnern gewinnen wird, weil die Möglichkeiten der Leistungssteigerung von CPUs durch mehr elektronischen Elementen pro Quadratmeter Chipfläche und pro Chip an physikalische Grenzen stoßen werden. Dann die bestmögliche Hardwarearchitektur mit guten Compilern zu kombinieren scheint ein vielversprechender Ansatz.

Die weniger technisch interessierten Nutzer wird diese Entwicklung aber kaum tangieren, denn wie Mobiltelefone mit Android werden Arbeitsplatzrechner mit welcher CPU-Architektur auch immer funktionieren und die Applikationen ausführen, die man dort installiert. Ob das nun plattformunabhängig ist, ob man bei kompilierten Programmen ein Binärformat hat, das mehrere CPUs unterstützt, indem einfach mehrere Varianten enthalten sind oder ob der Installer das richtige installiert, interessiert die meisten Benutzer nicht, solange es funktioniert.

Share Button

SSD billiger als magnetische Festplatten?

In der vergangenen Woche war ein interessanter Vortrag bei der Elastic Search User Group in Zürich, vom Gründer der Firma und des Projekts

Eine Bemerkung war, daß es in typischen Elastic-Search-Anwendungen billiger sein kann, SSDs als magnetische Festplatten einzubauen. Magnetische Festplatten sind natürlich für das gespeicherte Byte viel billiger, aber wenn man Durchsatz in Bytes/sec braucht, seien SSDs billiger.

Ein interessanter Gedanke, erst einmal verwirrend.

Aber man baut letztlich eine Serverfarm auf, um die nötige Leistung zu erbringen. Wenn nun die Hauptaufgabe dieser Server in geschickten Lesezugriffen auf ihren Daten besteht, dann braucht man mit vollständiger Verwendung von SSDs weniger Server. Das könnte kostengünstiger sein. Und gerade für überwiegendes Lesen sind SSDs unumstritten gut.

Share Button

Festplatten zur Erdbebenmessung

Auch wenn SSDs immer mehr Verwendung finden, sind magnetische (mechanische) Festplatten weiterhin verbreitet und werden es wohl auch noch lange bleiben.

Diese mechanischen Festplatten enthalten Sensoren, mit denen man Erschütterungen erkennen kann, zum Beispiel um den Kopf in eine ungefährliche Position zu bringen, um Schäden zu verhindern. Diese Sensoren sind sicher nicht so genau wie die Seismographen, die man zur Vorhersage von Erdbeben, Tsunamis und Vulkanausbrüchen und für die geophysikalische Forschung verwendet. Aber sie sind überall vorhanden und könnten so wertvolle zusätzliche Daten liefern. Das könnte vielleicht so funktionieren, daß die Betreiber von Rechnern mit Festplatten der Erfassung und Übermittlung von seismographischen Daten an ein geophysikalisches Rechenzentrum zustimmen. Weil die genaue Standortinformation ziemlich essentiell ist, sind sicher stationäre Rechner besser geeignet als Laptops, außer es werden noch GPS-Daten zusätzlich erfaßt und übermittelt, was aber ein größeres Mißbrauchsrisiko der Daten impliziert. Wenn Millionen von Nutzern mitmachen würden, hätte man genug Daten, um die Ungenauigkeiten der Messung teilweise zu eliminieren, weil nach dem Gesetz der großen Zahl angenommen werden kann, daß sich zufällige Fehler relativ gesehen verringern, wenn man etwa Mittelwerte vieler Meßwerte bildet. Systematische Meßfehler eines Sensors kann man auch erkennen und korrigieren oder sogar die Ausreißer weglassen. Noch besser wäre vielleicht eine Gewichtung der Meßwerte nach Qualität.

Eigentliche Mittelwerte sind nur sinnvoll, wenn man mehrere Festplatten am selben Standort hat, ansonsten wäre wohl eine mehrdimensionale Funktion, die von Ort und Zeit abhängt, zu approximieren. Die Geophysiker wissen etwa, wie diese Funktionen aussehen könnten und man kann die Meßwerte, von denen man Ort und Zeit kennt, verwenden, um ein paar Parameter dieser Funktion abzuschätzen. Diese Daten könnte man mit den genaueren Messungen der professionellen Geräte kombinieren. Der Vorteil der Festplattensensoren wäre vor allem, daß man ein viel flächendeckenderes Sensorennetz erhielte als man je durch Aufstellen von Seismographen bezahlen könnte. Das wäre eine echte Big-Data-Anwendung.

Share Button

Fließkommazahlen als Ersatz für Ganzzahlen

Wie ärgerlich ist eigentlich die Tatsache, daß Lua und JavaScript keine „int“s kennen und man stattdessen Fließkommazahlen („double“) verwenden muß?

Natürlich fühlt es sich völlig falsch an und ich möchte die Entscheidung, nur diese 8-byte-Fließkomma-Zahlen als numerischen Typ zu unterstützen, nicht gutheißen.

Aber was bedeutet das nun genau? Bekommen wir nun plötzlich irgendwo 7.999999999 statt 8?

Die Fließkommazahlen sind heute zum Glück standardisiert und fast jede Implementierung hält sich einigermaßen an diesen Standard. Es gibt eine 4-Byte-Variante und eine 8-Byte-Variante. Die 4-Byte-Variante ist nur dann sinnvoll, wenn man dem Entwickler die Wahl läßt, und fast jeder Entwickler nimmt „zur Sicherheit“ lieber die 8-Byte-Variante. Diese Fließkommazahl sieht nun ungefähr so aus:
1 Bit ist das Vorzeichen
11 Bits drücken den 2er-Exponenten aus
52 Bits drücken die Mantisse aus, dazu kommt als 53stes eine führende 1, die man nicht speichern muß, weil sie ja immer da ist.
Damit kann man die ganzen Zahlen von -2^{53} bis 2^{53} exakt ausdrücken und hat damit etwas, was etwa 54-Bit-Ganzzahlen entsprechen würde. Rein Informationsmäßig ist das eine zusätzliche Bit im Vorzeichen und das andere im 2-er-Exponenten codiert. Wenn man also nur addiert, subtrahiert und multipliziert und dabei immer im Bereich von -2^{53} bis 2^{53} bleibt, kann man exakte Ergebnisse erwarten. Natürlich ist es langsamer, aber auch das ist bei heutigen CPUs, die schnelle Fließkommaoperationen seit etwa 20 Jahren standardmäßig (und vorher gegen Aufpreis) in der Hardware eingebaut haben, nicht so tragisch. Wie ist es mit den ungenutzten Bits? Normalerweise stören die nicht, aber wenn man Applikationen entwickelt, die sehr speicherintensiv sind, kann auch so etwa ausnahmsweise mal relevant werden.

Ärgerlicher ist da schon die Divsion. Hat man bei ints so etwas wie „/“ für die Division mit Abrundung und „%“ für den Rest, wird bei Fließkommazahlen mit „/“ wirklich dividiert und eine neue Fließkommazahl berechnet. Wie rundet man hier ab, um das „int-/“ und das „int-%“ zu bekommen? Es sollte dabei ja trotzdem noch das 6.9999999999999 zu 7 gerundet werden.

Ungefähr so etwas könnte funktionieren:

def divmodf(x, y)
xf = x.to_f
yf = y.to_f
df = if (yf < 0) then
-0.2
else
0.2
end
qf = (xf + df) / yf;
q = qf.floor
r = (yf*(qf-q)).round(0)
return q,r
end

Das ist jetzt in Ruby geschrieben, aber es würde natürlich ähnlich in Lua oder JavaScript funktionieren.

Share Button

Carry-Bit: Wie funktioniert das?

English

Alle, die in der Grundschule noch das handschriftliche Addieren gelernt haben, kennen das Verfahren eigentlich. Es ist nichts anderes als das, nur nicht im Zehnersystem, auch nicht im Zweiersystem, sondern im 256er-System (8 Bit), 65536er-System (16 Bit), 4294967296er-System (32 Bit), 18446744073709551616er-System (64 Bit) oder was auch immer die Wortbreite der CPU ist. Dass man immer mit Zweierpotenzen arbeitet, ist heute üblich, aber es kann durchaus sein, dass man von unseren zweiwertigen Bits einmal auf dreiwertige „Trits“ wechselt, wenn sich die Hardware-Technologie weiterentwickelt. Wir werde es sehen.

Ich finde es zwar nicht sinnvoll, dass man sich bei der Applikationsentwicklung mit solchen Details auf Bit-Ebene herumschlagen muss, aber da man ja mit Java, C, C++, C# und ähnlichen Sprachen heute einen großen Teil der Applikationsentwicklung durchführt, kommt man daran nicht vorbei. Diese Sprachen zwingen den Entwickler, sich mit diesen Fragen zu einem gewissen Maße auseinanderzusetzen, um deren Darstellungen ganzer Zahlen zu verstehen. Aber das „Carry“-Bit sieht man leider in diesen Sprachen nicht, obwohl es für das Verständnis wichtig ist.

Ich habe mich seit etwa Anfang der 80er Jahre damit beschäftigt, Software zu erstellen. Die damals für mich zugänglichen Rechner waren 8-Bit-Rechner mit 6502 oder 6510 als CPU und 1 MHz Taktfrequenz. Man konnte sie in einem Basic-Dialekt programmieren, aber das war für viele Zwecke unbrauchbar, weil es zu langsam war. So kam Assemblersprache zum Einsatz. Ich habe dann später noch 680×0-Assembler und 80×86-Assembler verwendet, aber ab Mitte der 90er Jahre kam das eigentlich nicht mehr vor. Eine 8-Bit-CPU kann zwei 8-Bit-Zahlen miteinander addieren und dabei ein 8-Bit-Ergebnis liefern. Dabei gibt es zwei Varianten zu unterschieden, nämlich signierte Ganzzahlen, die meistens im Zweierkomplement dargestellt werden. Das bedeutet, dass das erste Bit das Vorzeichen codiert. Somit sind die Werte von 0 bis 127 postive Ganzzahlen, wie man es erwartet. Die 127 hat das Bit-Muster 01111111. Nun könnte man meinen, dass das Bitmuster 10000000 die direkt darauffolgende Zahl, also 128 ist, aber in Wirklichkeit ist das die -128, weil ja das erste Bit das Vorzeichen codiert und die „1“ für negatives Vorzeichen steht. Erhöht man die -128 weiter, erhöht sich der Zahlwert, weiter, wird also weniger negativ. Man hat dann am Schluss 11111111, um die -1 auszudrücken. Dieses etwas obskure Verhalten ist plausibel, wenn man sich vorstellt, nicht mit ganzen Zahlen zu rechnen, sonde mit Restklassen modulo 256. Dabei werden zwei Zahlen also kongruent, also zusammengehörig, angesehen, wenn sie sich nur um ein Vielfaches von 256 unterscheiden. Um alle 256 möglichen Restklassen abzudecken, kann man als Vertreter die Zahlen von 0 bis 255 (unsigned byte) oder von -128 bis 127 (signed byte, Zweierkomplement) verwenden. Beides kommt in unseren heutigen Programmiersprachen vor.

Für das Carry-Bit nehme ich zunächst der Einfachheit einmal an, dass wir nur mit nicht-negativen Zahlen rechnen. Die möglichen Werte eines Speicherworts sind also von 0 bis 2^n-1, wobei n die Wortbreite ist, also in unserem Beispiel 8. Heutige CPUs haben normalerweise 64bit Wortbreite, was nichts an der prinzipiellen Funktionisweise ändert, aber mit 8Bit ist das Beispiel übersichtlicher. Jeder kann sich vorstellen, wie sich das Prinzip auf 32 oder 64 oder 36 oder auch 96 Bit übertragen ließe.

Es steht also die Bitfolge 11111111 für 255. Nun kann man mit einem Assemblerbefehl, der oft ADD oder so ähnlich heißt, zwei solche Zahlen addieren. Das heißt, dass die Addition innerhalb der CPU als eine einzige Operation innerhalb von einem oder einigen wenigen Taktzyklen durchgeführt werden kann. Nun ergibt die Addition von zwei unsignierten 8-Bit-Zahlen eine Zahl zwischen 0 und 510 (111111110 binär), leider zu viel für ein Byte. Mit einem Bit mehr ließe sich das aber ausdrücken. So behilft man sich, indem man die niedrigen 8 Bit des Ergebnisses als Resultat akzeptiert, aber das neunte, oberste Bit, das nun 0 oder 1 sein kann, in einem sogenannten Carry-Bit oder Carry-Flag oder Übertragsbit in der CPU speichert. Dieses kann man nun abfragen und davon abhängig einen anderen Pfad einschlagen, zum Beispiel eine Fehlerbehandlung wegen eines Überlaufs auslösen, wenn die weiteren Verarbeitungsschritte nicht in der Lage sind, mehr als 8-Bit zu verwenden. Aber es gibt auch eine sehr elegante Lösung, die zum Zuge kommt, wenn man Zahlen addiert, die mehrere Bytes (oder CPU-Worte) breit sind. Ab der zweiten Addition verwendet man so etwas wie ADC („Add with Carry“). Dabei wird das Carrybit, das 0 oder 1 ist, als dritter Summand einbezogen. Damit ist das Ergebnis diesmal sogar zwischen 0 und 511 (111111111 binär). Wieder erhält man ein Carry-Bit. Man kann diese Addition nun fortfahren, bis man alle Bytes der Summanden verarbeitet hat. Wenn sie verschieden lang sind, kann man die oberen Bytes des kürzeren Summanden durch 0 ersetzen, solange das Carry-Bit noch 1 ist, oder ansonsten die Bytes des längeren Summanden einfach übernehmen. Um das Gesamtergebnis auszudrücken braucht man in diesem Fall eventuell ein Byte (oder CPU-Wort) mehr als der längere der beiden Summanden hat.

So lässt sich relativ einfach eine Langzahladdition in Assemblersprache schreiben. Es ist einer der größten Design-Fehler vieler heutiger Programmiersprachen, insbesondere von C, dass sie einerseits mit Low-Level-Ganzzahltypen ausgestattet sind, aber andererseits uns das Carry-Bit vorenthalten, so dass man dieses mit viel Gebastel ermitteln muss.

Die Subtraktion von Langzahlen funktioniert sehr ähnlich, dafür gibt es meist ein SBC („subtract with carry“) oder SBB („subtract with borrow“), je nachdem, wie das Carry-Bit bei der Subtraktion interpretiert wird.

Für die vorzeichenbehafteten Ganzzahlen muss man beim jeweils höchsten Byte der beiden Summanden aufpassen und hier das Vorzeichenbit berücksichtigen. Häufig gibt es ein sogenanntes Overflow-Bit, das in diesem Fall zumindest erkennen lässt, wann man ein weiteres Speicherwort benötigt.

Die 64-Bit-Addition heutiger CPUs könnte prinzipiell so funktionieren, dass sie bitweise nacheinander oder byteweise nacheinander mit Carry addiert. Mir sind die Implementierungsdetails von ARM, Intel und AMD zwar nicht bekannt, aber ich gehe davon aus, dass man dort eine größere Parallelisierung der Operation verwendet. Es gibt Algorithmen, die es so ermöglichen, eine Langzahladdition unter Verwendung von Parallelisierung wesentlich schneller auszuführen als mit dem hier beschriebenen Verfahren. Vielleicht schreibe ich dazu auch irgendwann einmal etwas, wenn es jemanden interessiert.

Interessant ist es auch, Multiplikation, Division, Quadratwurzel, Kubikwurzel und ähnliches zu berechnen. Auch damit habe ich Erfahrung, kann das also bei Interesse gerne beschreiben. Kurz gesagt sind diese Operationen auf heutigen CPUs sehr einfach in Assemblersprache zu implementieren, weil dort Multiplikation und Division bereits vorhanden sind, aber es geht auch mit 8-Bit-CPUs ohne Multiplikationsbefehl, falls das jemanden aus Nostalgiegründen interessieren sollte. Gerade für die Multiplikation gibt es aber wesentlich bessere Algorithmen, wenn die Faktoren sehr lang sind.

Ich möchte einen Artikel über die mögliche Ermittlung des Carrybits in C verfassen. Dieser wird auf Englisch erscheinen und unter der englischen Übersetzung dieses Artikels als Ping-Back verlinkt sein.

Share Button

Entwicklung der Hardware: Parallelisierung

English

Bis etwa einigen Jahren konnte man davon ausgehen, daß sich die Taktfrequenz von gängigen Mikroprozessoren regelmäßig erhöht und bei der Entwicklung neuer Software darauf vertrauen, daß die Hardware zumindest in naher Zukunft leistungsfähig genug sein würde, um gewisse Ineffizienzen zu kompensieren. Nun ist die Leistungsfähigkeit eines Rechners von sehr viel mehr Faktoren als der Taktfrequenz abhängig, vor allem auch davon, wieviele Operationen in einem Takt bzw. wieviele Takte für eine Operation benötigt werden. Wichtig ist erfahrungsgemäß aber auch ein genügend großer Hauptspeicher und natürlich gewisse Optimierungen auf der Platine und auf dem Chip, die man gar nicht so explizit wahrnimmt und auch nicht so leicht ändern kann. Grundsätzlich ist aber die Leistung einzelner CPU-Kerne nur noch langsam gestiegen, man bekommt aber ohne weiteres einen Chip, auf dem mehrere CPU-Kerne implementiert sind. Dualcore, Quadcore u.s.w. sind ja gut bekannt. Ein Link dazu: The Free Lunch is Over

Nun kann man diese mehrfachen Prozessoren mit einer einzelnen Ressourcen-hungrigen Applikation nutzen, wenn diese mehrere parallel verlaufende Threads oder Prozesse verwendet. Leider gibt es dabei ein paar Probleme. Das ärgerlichste ist, daß man zwar viele Entwickler findet, die sagen, das zu können, aber daß die Sache nachher tatsächlich stabil funktioniert, ist leider seltener. Häufig erlebt man Schönwetter-Software. Auf dem Rechner des Entwicklers funktioniert sie prima, vielleicht auch auf dem Testsystem. Aber im produktiven Einsatz treten dann obskure Fehler auf, die niemand nachvollziehen kann. Oder die verschiedenen Threads und Prozesse warten so oft gegenseitig aufeinander, daß in Wirklichkeit im Durchschnitt doch nur eine CPU genutzt wird. Oder das System blockiert sich selbst („Verklemmung“ oder engl. „dead-lock“). Natürlich nicht auf dem Rechner des Entwicklers, weil die spezielle Situation, die dazu führt, nur unter Last im produktiven Einsatz zum ersten Mal auftritt. Was lernt man daraus? Für diese Art von Architektur braucht man sehr gute Entwickler, die sich die parallelen Abläufe vorstellen können und die genug Erfahrung damit haben. Und man sollte sich nicht zu weit aus dem Fenster lehnen, sondern Dinge entwickeln, die zwar die Parallelität ausnutzen, aber doch robust genug sind, um nicht nur knapp zu funktionieren. Außerdem ist es wichtig, mir sehr realitätsnahen Daten und Datenmengen zu testen und auch Lasttests durchzuführen. Auf Testsystemen, die den späteren Produktivsystemen ähneln.

Ein anderer Ansatz löst das ganze Problem durch Frameworks. Es gibt sicher gute und leichtgewichtige Frameworks, aber bei gängigen Frameworks wie JEE (früher J2EE) brauchen diese schon selbst so viele Ressourcen und sie schränken die Möglichkeiten bei der Entwicklung so stark ein, daß man zumindest den Vorteil des einfacheren Multithreadings sofort wieder verliert, weil das Framework selber jetzt einen großen Teil der Rechenleistung und des Hauptspeichers in Anspruch nimmt. Es mag andere gute Gründe geben, solche Frameworks mit JEE-Applikationsservern einzusetzen, aber der Performance-Gewinn durch Parallelisierung hält sich normalerweise in Grenzen.

Das Problem ist immer wieder, daß man Datenstrukturen hat, die von mehreren Threads oder Prozessen manipuliert werden können und daß dadurch Probleme auftreten, die sich zwar handhaben lassen, die aber in der Praxis große Schwierigkeiten bereiten.

Zwei radikale Ansätze sind:

  • Verzicht auf gemeinsam genutzte Datenstrukturen
  • Verwendung von unveränderbaren Datenstrukturen

Der erste Ansatz ist zum Beispiel bei Entwicklung mit Ruby oder mit C gut möglich, weil die einzelnen Prozesse relativ wenig Hauptspeicher verbrauchen und man sich so leisten kann, mehr Prozesse gleichzeitig laufen zu lassen. Nun kann man mit verschiedenen Mechanismen Interprozeßkommunikation durchführen, z.B. unter Linux und Unix mit Posix-IPC oder mit TCP/IP. Das funktioniert vor allem dann gut, wenn man relativ unabhängige Prozesse hat, die nur wenig miteinander kommunizieren müssen. Und auch dafür braucht man ähnlich gute Entwickler wie beim Multithreading, die IPC gut beherrschen, außer man hat das Glück, daß die Prozesse so unabhängig voneinander laufen, daß sie gar nicht miteinander kommunizieren müssen. Vielleicht hat Erlang diese Idee in praktikabler Form umgesetzt. Dort kann man mit einer großen Anzahl von Prozessen arbeiten, die völlig voneinander getrennte Speicherbereiche für ihre Daten haben, während es ein Messaging-System für die Kommunikation zwischen diesen Prozessen gibt.

Die andere Idee, alle geteilten Datenstrukturen unveränderbar („immutable“) zu machen, wird z.B. von Scala und Clojure umgesetzt. Der Nachteil, daß man statt ein Objekt zu ändern, nur eine Kopie mit dieser Änderung erzeugen kann, wird durch Mechanismen abgemildert, die in gewissen Fällen intern so ein Kopieren durch teilweise Referenzierung des Eingabeobjekts ersetzen. Das gibt es auch in einem einfachen Fall in Java, wo der Zeichenketten-Type (String) immutable ist und wo Teile der Zeichenkette, die mittels substring() erzeugt werden, dieselbe interne Struktur wie die ursprüngliche Zeichenkette referenzieren.

In jedem Fall muß man sich aber über Abhängigkeiten der Prozesse und Threads untereinander Gedanken machen, damit man keine „dead-locks“ baut. Mit Scala und Clojure ist es aber möglich, leichtgewichtige Frameworks zu bauen, die die Ausführung von sehr vielen Threads gleichzeitig erlauben, weil das Versprechen der Unveränderbarkeit der geteilten Objekte viele Probleme eliminiert. Twitter benutzt zum Beispiel intern Scala und ist damit in der Lage, auch bei Ereignissen, die sehr viel Kommunikationsbedarf auslösen, mit der Last fertigzuwerden.

Ein Problem prinzipieller Natur bleibt natürlich, wenn der Kommunikationsbedarf zwischen den Prozessen sehr groß ist. In einem großen System können nicht alle Kommunikationspfade optimal schnell sein, denn bei n parallelen Prozessoren gibt es {n(n-1)\over2} Kommunikationspaare, was für große n mit dem Quadrat der Anzahl der Prozessoren wächst, also zu Kompromissen zwingt. Man bekommt entweder bei einem gemeinsamen Kanal Kapazitätsprobleme oder man muß bei getrennten Kanälen neben Pfaden zu den direkten Nachbarn auch auf zusammengesetzte Verbindungen setzen. Um es plastisch zu beschreiben: Eine wirklich große Applikation läuft verteilt über mehrere Rechenzentren, in denen es jeweils mehrere Racks gibt. Die Racks haben jeweils mehrere Rechner, die Rechner mehrere CPUs und die CPUs mehrere Kerne. Mit viel Geld kann man raffiniertere Hardware bauen, wo eine größere Anzahl von CPU-Kernen schnell miteinander kommunizieren kann, aber in unmittelbarer Nachbarschaft eines CPU-Kerns mit maximal schneller Kommunikation lassen sich nur begrenzt viele andere CPU-Kerne unterbringen.

Eine Idee war, eine große Anzahl von Rechnern topologisch in einem Hyperwürfel anzuordnen. Man hat also 2^n Teilrechner in Positionen, die den gedachten Ecken eines n-dimensionalen Würfels entsprechen und die Kanten dieses Hyperwürfels sind die leistungsfähigen Verbindungen dazwischen. So kommt man mit maximal n Schritten zu jeder anderen Teilrechner und kann auch in n Schritten ein Zwischenergebnis von allen Teilrechnern aggregieren und danach wieder verteilen. Weiß jemand, welche Ansätze man in heutigen Hochleistungsrechnern mit sehr vielen CPUs wählt?

Grundsätzlich kann eine Berechnung mit wenig Kommunikationsbedarf der Teilprozesse sehr gut parallel ablaufen, aber ein hoher Kommunikationsbedarf kann den Gewinn durch die Parallelisierung zunichte machen.

Share Button

Warum haben Laptop-Displays so geringe Auflösungen?

English

Hier ein Beitrag von Linus Torvalds zu der Frage auf google+.
Der Beitrag ist auf Englisch, nicht auf Schwedisch geschrieben.

P.S. Ich werde in der nächsten Zeit dabei bleiben, normalerweise so etwa am Freitag einer Woche einen Artikel für den Blog zu schreiben.
Manchmal fällt mir aber zwischendurch noch etwas ein, was dann halt auch hier erscheint.

Share Button