Parallelisierung – aus Anwendersicht

Da sich offensichtlich viel mehr Leute über Computer interessieren als für Raumfahrt (wer hätte das gedacht?). Will ich das Problem der Parallelität mal beleuchten. Zuerst mal aus „Anwendersicht“, also ohne Kenntnisse einer Programmiersprache und ohne auch Details der Programmierung zu vermitteln. Das folgt im nächsten Beitrag.

Erst mal: was kann man parallelisieren und wie geht das – darum geht es heute.

Die einfachste Sicht erhält man wenn man den Taskmanager aktiviert (oder PS unter Linux) und sich mal die Prozesse anschaut. Bei einem „jungfräulichen“ Windows XP direkt nach dem Start finden man typischerweise etwa 10 Prozesse. Wenn man einige Programme, Treiber etc. installiert hat, Online geht, können es durchaus auch viel mehr sein. So gesehen nutzen viele Kerne doch etwas, aber nur auf den ersten Blick. Jeder Prozess kann im Prinzip von einem physikalischen oder logischen Kern (das ist ein Kern der nicht existiert, aber dem Betriebssystem vorgegaukelt wird, indem der Prozessor intern aus zwei Prozessen die Instruktionen auf einen Kern verteilt damit dieser optimal ausgelastet. Das ist nicht so schnell wie ein echter Kern aber bis zu 25% schneller als ein einzelner Kern (der typische Gewinn liegt allerdings bei 10-15%). Bei Intel heißt das Hyperthreading. AMD das nicht in den CPU’s.

Wer allerdings genauer hinschaut wird feststellen, dass die meisten Prozesse nur wenig CPU Zeit brauchen. Ein Prozess kann ein Anwendungsprogramm sein, ein Dienst oder auch ein Thread.

Was ein Programm ist, brauche ich wohl nicht zu erklären. Ein Programm wird üblicherweise vom Anwender gestartet. Ein Dienst ist eigentlich fast das gleiche, nur wird er meist vom Betriebssystem gestartet. Entweder automatisch beim Start oder bei Eintreten eines Ereignisses. Ein Dienst ist normalerweise verborgen, also in de Taskleiste nicht tu sehen und macht sich auch selten oder gar nicht mit Meldungen bemerkbar. Typische Dienste sind z.B. der Virenscanner, Druckertreiber, Explorer und der Dienst zum Aufbauen von Netzwerkverbindungen SVhost.exe, denn man recht häufig im Taskmanager finden kann. In der Systemsteuerung ? Verwaltung ? Dienste kann man die installierten einsehen.

Ein Thread ist ein Teil eines Programmes, das von diesem gestartet wird und von dem Programm abhängig und meist eine eigene Aufgabe hat. Also im Bild rechts sieht man z.B. mehrere Threads von Google Chrome. Chrome öffnet für jedes Tab (im Moment des Schnappschusses waren 10 offen) einen Thread. Genauso macht es Star Office für jedes Dokument.

Prozesse haben den Vorteile, dass sich das Betriebssystem um die Verteilung an die Kerne kümmert und dabei die vom Programm gewünschte Priorität kümmert. Trotzdem wird beim Schauen auf den Taksmanager bei den meisten Anwendern ein Prozess die meiste CPU Zeit bekommen – der Leerlaufprozess, der die niedrigste Priorität aller Prozesse hat also erst dran kommt wenn alle anderen ihre Zeitscheibe erhalten haben. Betriebssysteme weisen Prozessen „Zeitscheiben“ zu, also sie bekommen einen Kern z.B. 20 ms lang und dann werden sie wieder in die Schlange eingereiht und müssen warten bis andere Prozesse der gleichen Priorität dran waren. Für Laien zum Angeben, das Verfahren heißt „Round Robin“. Es ist das einfachste Multitasking Verfahren und auch alle Computer in der Raumfahrt arbeiten danach. Es können so viel mehr Prozesse abgearbeitet werden als es Kerne gibt, auch weil bei den meisten Anwendungen ein Prozess nur wenig Rechenzeit benötigt. während ich diesen Schnappschuss anfertigte lief bei mir z.B.  simultan: Thunderbird, Google Chrome, Salamander, Expression Web, Irfan View und der SMPlayer, dazu noch die Hintergrundprozesse. Die meiste Rechenzeit braucht letzterer der ein Video neben der Arbeit abspielt. Wie man sieht liefen zum Zeitpunkt des Schnappschusses 96 Prozesse und trotzdem wurden nur 36% der CPU Zeit benötigt, ohne das Video wären es sogar nur 15%.

Das ist eine Möglichkeit, aber die Möglichkeiten von Prozessen zu kommunizieren sind beschränkt. So kann eine Anwendung selbst Aufgaben parallelisieren. Ich will hier zwei Beispiele nehmen. Die Videokodierung und Dekodierung und Bildbearbeitung. Alle Videokodierungen / Dekodierungen basieren auf dem Verfahren der Diskreten Cosinustransformation. Dieses basiert darauf, (stark vereinfacht gesagt!!!) dass die Bildinformation die in einem 8 x 8 Pixelgroßen Block ersetzt wird, durch die Koeffizienten einer Funktion. Diese muss berechnet werden (Encodierung) oder der Funktionswert ermittelt (Dekodierung). Der Algorithmus ist festgelegt und jeder Block ist vom anderen unabhängig. Ein Programm kann also bei einem Bild daran gehen, die Anzahl der Kerne abzufragen und dann das Bild in mehrere gleich große Einzelteile aufzuteilen, die dann jeweils von einem Thread, einem Prozess innerhalb des Programmes verarbeitet wird.

Bei der Bildbearbeitung basieren die meisten Verfahren auf Informationen aus den Nachbarpunkten oder es wird ein Algorithmus auf das ganze Bild (jeden Bildpunkt angewandt). Auch dies ist gut parallelisierbar. So basiert der Scharfzeichnenfilter z.B. darauf, dass von einem Bildpunkt der Mittelwert der Helligkeitswerte der Nachbarpunkte (mit frei wählbarem Radius) abgezogen wird. Auch hier kann im Prinzip jeder Bildpunkt separat berechnet werden. Neben den Kernen kann dies bei geeigneter Programmierung dann noch auf die Rechenwerke verteilt werden, von denen jeder Kern auch über mehrere (typischerweise 2-4) verfügt.

So sind innerhalb eines Programmes Dinge parallelisierbar. Doch wo geht es nicht? Nun es geht schlicht und einfach nicht dort wo die Aktion nicht vorhersehbar ist. Also bei der Interaktion mit dem Anwender. Hier ist es zwar möglich vorausschauend zu denken, also z.B. alle Seiten die mit der aktuellen Webseite verlinkt sind zu laden oder zu rendern, Nur ist das eben mehr eine Pausenfülleraktion, die auch nicht immer Sinn macht (folgt man jedem Link? – zudem erzeugt es Netzwerklast, dass dann den eigentlichen Flaschenhals darstellt. Vor allem ist die Zeit für das Rendern einer Seite sehr klein im Vergleich zur Zeit die man braucht sie zu lesen.

Wirklich am effizientesten ist die Parallelisierung von Berechnungen bei immer gleichen Algorithmen, wie die oben angesprochenen. Da bei Spielen es im Prinzip die gleiche Problematik gibt – die Szene ist vorgegeben, es müssen die Objekte nach einem Algorithmus berechnet, gezeichnet, eingefärbt und dann mit Texturen und Licht/Schatten überzogen werden. Auch dies wird für jede Einheit (meist ein Dreieck) separat durchgeführt. Daher haben Grafikkarten CPU aus sehr vielen, sehr einfach gestrickten Recheneinheiten aus vielen (Maximum sind glaub ich derzeit 480 Kernen). Werden sie mit solchen Algorithmen gefüttert die extrem gut parallelisierbar sind, dann sind sie viel schneller als die CPU. So gibt es Treiber um Bildeffekte zu berechnen oder Videos mit der Grafikkarte zu en/dekodieren, das letztere kann man wegen des feststehenden Algorithmus auch in Silizium gießen und so sind moderne Chipsätze dazu fähig Videos zu dekodieren, wodurch ein Atom erst HD Videos abspielen kann – die erfordern sonst einen Dualcoreprozessor mit der etwa zehnfachen Rechenleistung.

Was gibt es noch?

Wir haben ja einige Sci/Fi Freunde hier. Ich bin da auf was gestoßen, das euch sicher freut: Ijon tichy, Raumschiffpilot. Es hat alles was Sci/Fi Serien auszeichnet: Zeitschleifen, Außerirdische, Hologramme, Kampf um die Aufnahme der Menschheit in den galaktischen Rat, gefräßige Monster – nur ist die Serie, sagen wir mal „etwas anders“. Ladet sie euch runter und schaut selbst. (90 Minuten 713 MB, 6 Folgen à 15 Minuten, derzeit wird die Fortsetzung gedreht).

http://www.megaupload.com/?d=23ML8YIG

Das zweite ist dass ich die Blogleser von der so arg strapazierenden Aufgabe zu erläutern, warum man ein Rätsel gestellt hat entbinden will. Aber im Auflösungskommentar sollte man schon noch was erklärendes schreiben.