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.

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.

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.

Concurrency and Functional Programming Languages

Following the thread on new trends and concurrency – I think we will see functional programming languages as one approach to tackle concurrency. It is worth to think about this option. Haskell is an elegant programming language; it’s functional and not sequential. Complex problem definitions can be described (by using a functional language) in a way that parallelization (a concurrent solution of the problem) is feasible. Program code is written more abstract, on a mathematical / abstract basis. It is not machine or processor specific. Using an imperative language, parallelization is not a piece of cake; especially when we are talking about lock-free programming. The learning curve is steep and the outcome error-prone. The current status of programming languages, tools and RAD is definitely not ready to support mainstream development in order to support concurrency in a world of dual-, quad-, or … core processors.

Distributed Computing

I'm looking for people interested in distributed computing; especially with experience in MPI / OpenMP. I do see a lack of solutions / tools /frameworks to leverage the power of multi-kernel CPU's and multi-processor architecture. More is about to come ...