Use-Cases und Problemstellungen im Bereich Nebenläufigkeit und Parallelisierung

Ich schreibe diesen Beitrag in deutscher Sprache, da ich alle betreffenden Diskussionen in letzter Zeit ausschließlich in meiner Muttersprache geführt habe. Sicher werde ich den Post demnächst auch in Englisch veröffentlichen. Ich habe die Thematik bereits mehrfach angerissen – „Wann ist welche Art von Parallelisierung sinnvoll und wann nicht?“. Diese Frage steht in engem Zusammenhang mit vielen Unschärfen in den Begrifflichkeiten. Ich möchte keinesfalls engagierte Entwickler davon abhalten, sich in dieser Herausforderung zu stellen. Aber ähnlich zum Lernkurven-Vergleich drängen sich auch hier Analogien mit dem Meilenstein Objektorientierung in der Softwareentwicklung auf. Es gibt Code der ist „dermaßen objektorientiert“ geschrieben, dass er unübersichtlich, kaum wartbar und nicht mehr weiterverwendbar ist. Ein typischer Fall, beim dem über das Ziel hinausgeschossen und damit die Objektorientierung konterkariert worden ist.
Was hat das mit Parallelisierung zu tun? Im Prinzip gilt auch hier der Ansatz: was ist die konkrete Anforderung und welche Use-Cases (Anwendungsfälle) lassen sich daraus ableiten? Wobei man die Zielplattform (Systemarchitektur) nicht vernachlässigen darf. Hier eine (nicht vollständige) Liste von Fragen, mit Hilfe derer man einer Lösung näher kommen kann:

1. Wie sieht die HW-Architektur der Zielplattform aus (Schlüsselworte: Hyprerthreading, symmetrische oder asymmetrische MultiCore-CPU’s, Shared Memory, Distributed Memory)?
2. Welches Betriebssystem mit welchen Laufzeitumgebungen und Programmiersprachen werden auf der Zielplattform eingesetzt? Dabei ist das Betriebssystem immer mehr zu vernachlässigen, da präemptives Multitasking heutzutage Allgemeingut ist und damit zumindest parallele Prozessausführung gegeben ist.
3. Ist Performance die wichtigste nicht-funktionale Anforderung? Mit Performance sind in diesem Zusammenhang Datendurchsatz und Verarbeitungsgeschwindigkeit gemeint. Hier geht es auch um den Fakt, dass die Zeiten höherer Taktraten vorbei sind und der Cache leider nicht die Lösung aller Probleme darstellt.
4. Haben die betreffenden Use-Cases einen synchronen oder asynchronen Charakter?
5. Wie soll der Datenaustausch zwischen Ausführungsströmen (ich verwende diesen Begriff hier ganz bewusst) erfolgen und in welchem Umfang? Benötige ich Zugriff auf „shared“ Ressourcen und in welchem Umfang?
   

Ausgehend von der Beantwortung dieser Fragen kann eine Architektur entwickelt werden, die den Anforderungen genügt und die auf die richtigen Lösungen setzt. Richtig bedeutet in diesem Zusammenhang auch, dass die passenden Techniken verwendet werden um weitere nicht-funktionale Anforderungen wir Wartbarkeit, Erweiterbarkeit, Testbarkeit und Einfachheit (!) zu erfüllen. Ich möchte und kann an dieser Stelle keine Entscheidungsmatrix liefern; werde aber kurz ein paar Lösungsmöglichkeiten skizzieren.

• Wenn Punkt 3 das entscheidende Kriterium ist, sollte eine gute Auslastung der zur Verfügung stehenden Rechenkerne das Ziel sein. Es gibt in diesem Fall immer noch die Möglichkeit, eine Lastverteilung der Prozesse als Lösung zu wählen. Sollte dies aufgrund der Problemstellung (Arithmetik, etc.) nicht möglich sein, muss der Weg über eine Verteilung der Threads gefunden werden. Hier bietet sich beispielsweise OpenMP an. Natürlich kann sich Punkt 3 auch mit Punkt 5 überlagern, wenn auf viele „shared“ Variablen zugegriffen werden muss. Es ist anzumerken, dass OpenMP uns nicht vor Race-Conditions oder Dead-Locks bewahrt.
• Bezüglich Punkt 4 gibt es sicherlich die am weitesten entwickelten Lösungsmöglichkeiten und gute Chancen, diese Problemstellung umfassend zu lösen. Eine gute Entkopplung sowie asynchrone Kommunikationsmechanismen sind hier die Erfolgkriterien. Konkrete Anwendungsfälle existieren vor allem im Umfeld von Benutzerschnittstellen (UI’s) auf Clientsystemen. Ausführungsströme (z.B. Threads) in der Präsentationslogik sollten von der Geschäftslogik mithilfe geeigneter asynchroner Kommunikationsmechanismen getrennt werden, um gezielt eine lose Kopplung zu erreichen.Ich möchte noch anmerken, dass die Aufgabenstellung in Punkt 5 (Asynchronität) für mich nicht originär zur Problemdomäne Parallelisierung / Nebenläufigkeit gehört, in der Diskussion aber dort oft eingeordnet wird.
• Punkt 5 ist sicherlich die komplizierteste Aufgabenstellung, da bisher nur wenig Unterstützung durch Entwicklungsumgebungen, Compilern und Frameworks vorliegt. Bis es diese gibt (beispielsweise auf der Grundlage von Konzepten des „Transactional Memory“) muss man noch mit all den Schwierigkeiten des „Lock-Free Programming“ leben. Dazu gehört natürlich ein ausgefeiltes Testkonzept, um Dead-Locks und Race-Conditions auf die Spur zu kommen. Generell kann ich hinsichtlich Punkt 5 nur empfehlen, Architektur und Design hinsichtlich alternativer Lösungsmöglichkeiten des Datenaustausches genau zu prüfen.
  

Natürlich ist anzumerken, dass es auch einen Mix an Lösungen geben kann. Als konkretes Beispiel im Hochleistungsrechnen sind Hybridanwendungen aus MPI (Message Passing Interface) und OpenMP zu nennen.

Dogmushing

I went to Alaska in wintertime in 1998 the very first time (after backpacking in summer for many years). The reason was: Dogmushing. The picture is just an impression of a beautiful time in the cold at the Goldstream Kennel.

More Music is about to come ...

... just one tiny recommendation. Listen to ZOOT ALLURES (1975) from Frank Zappa. Title #3 - the torture never stops - is the perfect soundtrack for a day in the middle of the week. And remember, music is the best ...

More OpenMP Details (Data Scopes, Critical Sections)

Here comes a little bit more information on OpenMP, the standard programming model for shared memory parallelization. Variables can be shared among all threads or duplicated for each thread. Shared variables are used by threads for communication purposes. This was already outlined in an earlier post. The OpenMP Data Scope Clauses private and shared declare this behavior in the following way: private (list) declares the variables in list as private in the scope of each thread; shared (list) declares the listed variables as shared among the threads in the team. An example could look like the following: #pragma omp parallel private (k)
If the scope is not specified, shared will be the default. But there are a couple of exceptions: loop control variables, automatic variables within a block and local variables in called sub-programs.
Let’s talk about another important directive, the critical directive. The code block enclosed by
#pragma omp critical [(name)] will be executed by all threads but just by one thread at a time. Threads must wait at the beginning of a critical region until no other thread in the team is working on the critical region with the same name. Unnamed critical directives are possible. This leads me to another important fact that should not be overlooked. OpenMP does not prevent a developer to run into problems with deadlocks (threads waiting on locked resources that will never become free) and race conditions where two or more threads access the same shared variable unsynchronized and at least one thread modifies the shared variable in a concurrent scenario. Results are non-deterministic and the programming flaws are hard to find. It is always a good coding style to develop the program in a way that it could be executed in a sequential form (strong equivalency). This is probably easier said than done. So testing with appropriate tools is a must. I had the chance to participate in a parallel programming training (btw, an excellent course!) a couple of weeks ago where the Thread Checker from Intel was presented and used in exercises. It is a debugging tool for threaded application and designed to identify dead-locks and race-conditions.

Google Phone

Gizmodo.com published an article (+ picture) on HTC's Google phone called "Dream" last Thursday. It got a touchscreen as well as a keypad. There are rumours that the gadget will be in store by the end of the year. Looks promesing.

Just a recommendation

There is a fascinating article on the WIRED MAGAZINE (16.04.) with the title: How Apple Got Everything Right By Doing Everything Wrong. This is a must read for all folks interested how Apple is doing their products, maintaining their status and myth, and with many interesting insights. It is also about company and management culture, openness, transparency, proprietary solutions, vertical integration, and the different approaches in the high-tech industry from Apple to Google.
The phenomenon is that any other company, especially the software giant located in Redmond, would have been ended with endless criticism, if they had done their products this way. Another interesting view is mentioned briefly, the so-called “three-tiered systems” consisting of blend hardware, installed software and proprietary Web application. Let’s see how this model is doing in the future because this is the antithesis to the Open Source / Open System approach.

Green IT and Parallel Programming

Green-IT is one (or the) buzzwords these days. Everybody wants this sticker on the box. I do Green-IT for many years. I switch off my computer and monitor + DSL-modem when I’m done. But this behavior should not be the topic of the post. Chip design might lead to an architecture where many cores run on a lower clock speed (than a single core processor does). This is not contradiction to Moore’s law by the way. For an application which is not designed and developed to exploit a multicore-architecture (either by process-based load balancing of multithreading), the result could be a decrease in performance. So this is my point and it is probably not far-fetched. Green-IT might be another trigger to force efforts to make applications ready for today’s hardware architecture.

Erich Kästner and Dresden

Erich Kästner is one of the most popular authors of my hometown Dresden. His book “Als ich ein kleiner Junge war” is about his childhood in Saxon’s Capital, a wonderful homage to the splendor of Dresden. He was born in the “Dresdner Neustadt” and by the way, I grew up in the very same house where he was born. And here comes my recommendation, and a picture as well (this blog needs a picture from time to time!). A museum was founded in 1999 and is located very close to the places where he spent his boyhood – Antonstrasse 1 / near to the Albertplatz. The photograph shows the young Erich sitting on the wall surrounding the museum watching the busy life on the Albertplatz.

More Music …. (Music is the best)

Hey, here comes another favorite album of mine done by Frank Zappa. It’s Bongo Fury which is a co-work with Captain Beefheart by himself! Please start with the last title Muffin Man. The lyrics and the guitar at the end of the song are terrific. It might not be the appropriate album for rookies absolutely new to Frank’s music. But as it is said by the Muffin Man: I for one care less for them!

Some More Details on OpenMP

Well, in order to move forward with some annotations to OpenMP, here are a couple of details. Parallel Regions in OpenMP are separated by #pragma omp parallel [clause [clause]…]. The block inside will be executed by the designated threads in parallel (same code is executed in each and every thread). The number of threads can be defined by an environment variable and can be set to a specific number or to the maximum number of threads. Other environment variables allow the setting of the chunk size for the schedule type. Beyond this simple structure of Parallel Regions, work sharing constructs (directives) are available. One example is the do/for directive. An implicit barrier exists at the end of the do/for block for synchronization purposes. This can be disabled by specifying a nowait. A schedule clause defines the distribution on the different threads. For options are available static, dynamic, guided, and runtime. Please not the default value depends on the underlying implementation. This should be enough for tonight. It’s Friday and we should listen to some music. Find some recommendation in the next post.

Nebenläufigkeit

Folgenden Text habe ich auf meiner Website veröffentlicht, um den Link auf diesen Blog etwas zu illustrieren. Da er einen kleinen Überblick über die Intension und Thematik in deutscher Sprache gibt, möchte ich ihn gleichzeitig hier noch einmal veröffentlichen.

Multi/Many-Core, Multi-Threading und Parallelisierung

Die Zeit des Geschwindigkeitsrausches ist vorbei, zumindest was die Prozessoren betrifft, die heutzutage in Workstations, Servern und Laptops verbaut werden. Höhere Taktraten sind aufgrund der geltenden physikalischen Gesetze nicht mehr DIE Lösung für eine bessere Performance (neben der Optimierung der Instruktionen und des Cash-Speichers). Dafür werben die Hersteller mit neuen Produkten wie Dual-Core, Quad-Core, etc.. In diesen Lösungen sind mehrere (Haupt)Prozessoren auf einem einzigen Chip untergebracht und das in einer symmetrischen Art und Weise. Das heisst, die Kerne sind identisch und können dieselben Aufgaben erfüllen. Die einzelnen Kerne erhalten dabei einen eigenen Cash, der weitere Möglichkeiten der Performanceoptimierung bietet. Okay, das war die Hardware. Leider kann die Software diese neuen Möglichkeiten nicht in jedem Fall per se nutzen; sie muss darauf vorbereitet sein. Der Weg dahin ist steinig und kompliziert und wird leider durch die existierenden Compiler, Entwicklungsumgebungen und Frameworks nicht genügend unterstützt. Hier muss man zwischen den existierenden Programmiersprachen und Laufzeitumgebungen (Java, .NET) unterscheiden, die verschiedene Ansätze bieten. Dazu kommen Frameworks wie OpenMP und MPI, die in der Welt des Hochleistungsrechnens schon länger existieren. Neuerdings denkt man in dem Kontext der Parallelisierung auch wieder über funktionale Programmiersprachen nach. Wie man leicht erkennen kann, ist die Lernkurve für Entwickler hoch und die Fehlerquellen sind zahlreich. Dazu kommt, dass es oft Unschärfen in den Begrifflichkeiten gibt, vor allem wenn es um Multi-Threading, Hyper-Threading und Multi/Many-Core sowie Multi-Tasking (im Rahmen von Betriebssystemen) geht. Oft wird die Parallelisierung in der Softwareentwicklung mit dem Meilenstein Objektorientierte Programmierung verglichen. Dieser Vergleich ist durchaus realistisch. Ich befasse mich auf meinem Blog mit dem Thema Parallelisierung und möchte dabei Lösungen und aktuelle Trends aufzeigen.

Shared Memory, Multi/Many-Core and OpenMP

A typical hardware architecture these days could be outlines as follows: n cores or processors are interconnected to memory segments that can be shared. Each processor has the same access conditions (with the focus on performance) to each memory segment. OpenMP is a right choice for this hardware architecture (I’m not talking about the program code or the arithmetic inside). This is done by the developer using directives which is an explicit process. Parallel sections (typically loops) must be defined. The parallelization is done by the compiling system (using the OpenMP libraries). This means that data decomposition and communication are implicit. Parallel sections are called parallel regions; typically comprising a master thread and a team of threads which is basically a fork-join model. Only the master thread continues when the parallel region is completed. Variables can be shared among all threads or duplicated for each thread. Shared variables are used by threads for communication purposes. All this must be done carefully. OpenMP does not stop you from creating race conditions and dead-locks! More about the parallel regions and important environment variables in my next post.

Application Design, Multi/Many-Core and Other Basics

When I’m writing about concurrency I do not mean Multi/Many-Core per se. This is just about a clarification on some basics and premises. Concurrency starts with processors that support multithreading (in order to overcome idle-times). This means in hardware (and a little bit simplified), program counters and programmable register sets are added. By doing this, processors are able to run more than one instruction stream at a time. In order to exploit this behavior, the software must be coded accordingly. If this is done, the code is ready for multithreading and for Multi/Many-Core processors. I admit that this sounds toooooooo ez. Coded accordingly means either a design from the scratch or a redesign in order to support concurrency. A rework could lead to a decomposition into software threats (please use the appropriate framework to handle threats, locking, synchronization, etc) or into sub-programs. Of course and as already mentioned a couple of times, arithmetic (code) and cash usage should be reviewed and considered as well. If the system is reworked into sub-programs, today’s multitasking operating systems will take care of this. Each approach should be considered thoroughly pertaining to pro and cons. Multithreading and Concurrency (using Multi/Many Core) might come with a higher effort in testing and in hunting nasty bugs. But let’s get back to the beginning of this blog entry. Multi-Threading and Multi/Many-Core are not the same technologies and buzz-words but highly complementary.

Music is the best ...

Basically, there is much more than coding and multi/many core. I started to review my Frank Zappa collection recently. His music is so great, and he is such an smart guy with a real sense of humor (does humor belong in music?). I don't say he was! Well, for all folks out there with no idea who Frank is and what his music is all about and whatta great guitar player he is, and and and ... . Here are some recommendations from a long list of albums. Let's start with ONE SIZE FITS ALL from 1975. Two songs on this Vinyl/CD are more than brilliant: Inca Roads and San Ber´dino. Check it out. And don't forget the Sofa's on this record.

Some Annotations

I should add that the Parallel Extensions to the .Net 3.5 Framework are currently in the CTP (Community Technology Preview) status and available for download. It comprises two basic feature-sets: Data- and Task Parallelism-API and parallelization support for LINQ. The download comes with documentation and examples.

I would like to address another comment I received recently. Of course, before considering any parallelization activities, two preliminary steps are a must:

- Optimization of the numeric (actually the code)
- Optimization of the cache (because cache is always king!)

Both activities might lead to the expected performance increase without diving into complex parallelization efforts in an overhasty manner.