Software based Transactional Memory

This is interesting news for C# developer. MSDN DevLabs offers the STM.NET as an extension to the .NET framework 4.0 (Beta 1) for experimental purposes. STM stands for Software Transactional Memory and provides support for concurrency in order to use the multi-core architecture efficiently. STM does not provide a lock framework. It comes with an approach to isolate shared state which is the real issue when it comes to concurrency (because of dead locks and/or race conditions). Based on the ‘transaction pattern’ used in other areas of computer science, code (and memory) is handled isolated to enable an atomic execution. Code sections are demarcated accordingly. It will be interesting to check on this, especially pertaining to performance implications. But anyhow, it might be a promising step, at least for the C# folks.

More testing tools for parallelization

Intel® offers a so called “Application Concurrency Audit Tool” for free. The Intel® Concurrency Checker 2.1 is available for Windows and LINUX and can be downloaded from their software network. I started to play around a little bit with the tool. It provides a decent overview on CPU utilization, elapsed time, parallel time, utilization regarding threads, and levels of concurrency. It allows to attach running application executables as well as to test java apps.

More Parallelism Support in upcoming IDE version

The October issue of the MSDN magazine contains an article on the improved support for parallelism in the next version of Visual Studio [v. 10] as well as in .NET 4.0. Stuff from the Parallel Extensions (TPL, PLINQ) to the .Net 3.5 Framework (available as Community Technology Preview) went in as well as new features to support parallelism in native code. In addition, testing tools to cover parallelism in code are in the pipeline too. Most of these new features were presented at this year’s PDC in Los Angeles (slides are available for download). This is definitely a step in the right direction but a long road to go until writing parallel code is daily business for mainstream programmers. I got still concerns if existing programming languages, libraries, frameworks and compilers can deliver the final answer to cope with the complexity of expressing explicit parallelism.

Concurrency Aspects

The new issue of the ACM Queue got the “The Concurrency Problem” on the front page. One article is about the programming language Erlang which has the ability to solve parallel problems by design. Another excellent contribution (Real World Concurrency) is about the why and when and tries to nullify any taste of black magic. I totally agree that developers should not feel forced to use parallelization by implementation in any scenario. Performance is the main objective when parallelization is considered. But there are different ways to achieve this (and not just by using threads and locks [lets call this multithreaded code] within one process). The author calls this approach concurrency by architecture. I can live with that perception perfectly. Furthermore, a lot of hints and pitfalls are listed in order to handle locks, threads, mutexes, semaphores, and debugging in the correct way which includes good advice how to identify the right code segments for parallelization. Must read (*****)!

Ct - Parallel Extensions to C++

Intel has developed extensions to C++ supporting the optimization of serial code to be executed on multi-core processors. The research project is called Ct (t stands for throughput) and comprises language extensions as well as a runtime compiler, threading runtime and memory manager. Different sources on the web emphasize that the design goal to minimize threading/coordination overhead has been met. In comparison with OpenMP, fewer instructions are needed for parallelization.

No short term relief of multi-core programming issues available

Beside all announcements to tackle the multi-core programming challenges, no major breakthrough can be ascertained. The issues are especially relevant on the client-side in the domain of mainstream applications. I have already posted a couple of comments on that.
Even the business world has identified the current status as a problem. The Fortune magazine addresses the topic in the last issue with an interesting article - A chip too far? The article is about risks and opportunities, and a Stanford professor describes the situation as a crisis – probably yes, probably not. It is definitely a huge chance for skilled programmers and people with the right ideas. I do agree with one statement totally – after years of abstractions in terms of platforms and languages, the complexity and hardware dependencies of multi-core architectures increase the learning curve for an average programmer dramatically.

Limitations of today’s Parallelization Approaches

As already stated in detail, physics has stopped the race for more CPU clock speed. It’s about the heat, period. Hardware (Chip) manufactures response is to put more and more cores on a die – we all call this multi-core. I also tried to list and explain a couple of technologies (and also No-Go’s) to exploit those architectures; just skim through the blog. But most of the approaches are based on the process of determining sections of code which can be executed in parallel, loops for instance. Saying “sections of codes” does imply that we can expect serial remnants in the source code. And these parts [The percentage of code resisting tenaciously to be parallelized! :-)] determine the speedup factor defined by Amdahl’s Law (see post on Amdahl's Law). The dilemma looks a little bit similar to the expectations from the increase of clock speed in the past. It will not work out to lean back and wait until there are 16 or 32 cores on a single die. This will not fix the problem sufficiently because most of the existing approaches for parallelization does not scale. Other technologies and strategies have to be developed and applied. And before this will happen, it’s always a great approach to optimize the source code and to think about an effective usage of the cash (memory).

Amdahl’s Law

There is not just Moore’s Law and Murphy’s Law, both are well known to IT and Non-IT folks, but also Amdahl’s Law which is about the maximum of expected improvement to a system when only parts of the systems are improved. It is applied in Parallel Computing commonly, and specifies the theoretical speedup of a program running on multiple CPU’s in parallel. The maximum speedup is limited by the sequential parts of the code. A boundary condition is the assumptions that the problem size is the same when running in parallel. Here comes the formula (with N = number of processors and P the percentage of code that can be parallelized; hence, (1-P) is the serial code):

Speedup = 1 / (1-P) + P/N

You can play around with this formula. In essence, the sequential part of the code must be minimized to gain speedup. And, even a high number of processors does not have that impact when the percentage of parallel code is low. Anyhow, it’s a formula. In practice, the speedup depends also on other conditions, the communication (mechanisms) between the processors and the cache [Because Cache is king! ;-)].

Transactional Memory …

… is most likely one solution to overcome parallel programming issues. Currently, it is very difficult (and error prone) to use locks properly when accessing shared memory sections. Lock-free programming is much more difficult. All these issues are already covered in earlier posts.
Talking about transactional memory, this concept is not that new but not part of mainstream development platforms. Not yet, but transactional memory could be available in hardware and software soon. Basically, software-based transactional memory solutions do already exist. The concept is similar to mechanisms used in database systems controlling concurrent access to data. A transaction in the scope of software-based transactional memory is a section of code that covers a series of reads and writes to shared memory. Logically, this occurs at a single point in time. In addition, a log and a final operation, called commit, are also part of the concept. Sounds familiar? Published concepts (of software-based transactional memory) using an optimistic approach free of locks. It is up to the reader in the scope of the transaction to verify based on the logs that data in the shared memory has not been altered (by other threads). If so, a roll-back will be performed and give him another try …
This sounds really simple and desirable, right? What’s the drawback, why not using this technology for solving existing problems in parallel computing? It is the performance, decreased by maintaining logs and doing the commits. But those issues should be solved soon. It would make life easier pertaining to the understanding of multi-threading code and could prevent the pitfalls coming with lock-based programming. Each transaction could be perceived as a single-threaded, isolated operation.

F Sharp (F#) – a functional programming language in the scope of the .NET ecosystem

C# is a well known programming language designed to be used in the scope of the Microsoft .NET framework. It is an imperative and object-oriented programming language and widely accepted in this managed environment.But there is another “sharp-language”: F# - developed by Microsoft Research. F Sharp is a functional programming language with imperative and object-oriented aspects. It is part of the .NET environment and can be used within the Visual Studio development environment. Programs written in functional programming languages are easier to parallelize because of missing side-effects. Concerning this characteristic (which is basically an advantage), it is worth checking on F# in order to solve parallelization problems. The language can be obtained from the Microsoft Research website and is covered by the Microsoft Research Shared Source License Agreement.

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.

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.

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.

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.

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.

More Concurrency

I’m receiving a lot of questions about the status of parallelization in today’s world of software development. More and more people are interested in this topic. Some are driven by requirements. Some are mixing it up with the 64-bit change. ;-) Well. Despite all the support in Java, .NET, and all the frameworks like MPI and OpenMP, it is still a mess. It is not addressed adequately in respect to the roadmap of the processor industry, especially for client applications. Functional programming languages and transactional memory are no way out, because of missing acceptance and the current state of these languages, concepts, etc. On the other hand, the increase of the clock speed is no longer a save heaven. Everybody should be aware of this. And, cache is also just a workaround. Beside the existing support mentioned earlier, today’s concepts in terms of languages and compilers make assumptions that might be not true. Basically, the processors and compilers just see sequential code, but they do not work on strictly sequential code. There is always the threat of some kind of optimization, which might be a requirement for the CPU developers to gain some extra-performance. Other pitfalls are dead-locks, different locking mechanisms, and data corruptions in case of failed locking. I have not mentioned the state of complexity yet, the KISS (keep it …) is definitely not addressed. This is especially true for lock-free programming which can’t be recommended for mainstream programming. Talking about my experience, the utilization of OpenMP should be preferred for simple shared-memory scenarios. Developers should consider the positive impact of cache and must learn to utilize environmental variables, pragmas / compiler directives, and the library functions properly. Of course, the code (basically the loops) must be organized respectively. Btw, this is another condition to use OpenMP (If not, it makes no sense). More is about to come.

Raising Awareness

Microsoft is addressing the Parallel Computing topic explicitly, and compares this kind of shift with other milestones in the world of computing like graphical user interfaces or the internet. A whitepaper called “The Manycore Shift” is available on the company’s web site outlining Microsoft’s Parallel Computing Initiative. From my point of view, this comparison is correct and the need to emphasize and address this subject is overdue and should lead to results quickly, especially for mainstream development. Exciting times!