Intel Threading Challenge 2010: Von Katzen und Pokerkarten

Anfang Juni war es so weit: Intel startete seinen nächsten Parallel-Programmier-Wettbewerb, der sich aus zwei Phasen und insgesamt sechs Aufgaben zusammensetzt. Mittlerweile hat der Contest Phase 2, Aufgabe 3 erreicht, und wieder gibt es schöne Preise zu gewinnen.

Allerdings hat Intel vor den Gewinn das Denken gesetzt, und so kommt man auch bei der dritten Aufgabe der zweiten Phase nicht umhin, seine Parallelprogrammierkünste unter Beweis zu stellen. Dass es sich dabei um eine Aufgabe aus der Welt des Pokers handelt, ist (a) natürlich sehr amerikanisch und (b) sehr populär, da sich Poker schon lange größter Beliebtheit erfreut – und das nicht nur in den USA.

Dass es sich bei der zu Grunde liegenden Pokerart um die bei uns eher unbekannte Variante Pai Gow Poker handelt, spielt keine wirkliche Rolle. Alleine die Anzahl der zum Spiel gehörenden Karten (7 vs. 5 beim regulären Poker) variiert, der Rest ist wie immer. Die Aufgabe besteht darin, ein parallel programmiertes Tool zu entwicklen, das so schnell wie möglich heraus findet, mit welchen Kartenkombinationen ein einzelnen Spieler gegen die Bank gewinnen kann, welches das zweitbeste Blatt ist, das drittbeste, usw.

Die komplette Beschreibung und sämtliche Parameter findet ihr auf der Contestseite. Dort ist auch den Hinweis hinterlegt, dass zur Ermittlung des Gewinners die notwendige Zeit herangezogen wird, die das programmierte Tool verbraucht, bis es sämtliche Kartenkombinationen herausgefunden hat. Auf dieser Seite könnt ihr das Ergebnis eures Schaffens einreichen.

Ach ja: “Pai Gow” ist lediglich der Einsteiger-Wettbewerb des Intel Threading Challenge 2010. Beim Master-Challenge geht es um ein Spiel, das sich Katze und Hund nennt. Falls ihr also die echten Herausforderungen schätzt, solltet ihr dort auf jeden Fall auch mal vorbei schauen.

Für beide Aufgaben gilt, dass ihr sie bis spätestens 11. Oktober, 24:00 Uhr (PDT) eingereicht haben müsst. Und was ihr alles gewinnen könnt, erfahrt ihr auf dieser Seite. Und um das Lösen der Aufgaben ein wenig zu erleichtern, bietet Intel allen Teilnehmern Zugriff auf das Intel Manycore Testing Lab und die notwendigen Software-Tools. Damit kommen auch all diejenigen in den Genuss eines Multicore-Rechners, die keinen zuhause rumstehen haben.

Und jetzt: viel Spaß mit der 3. Aufgabe der 2. Phase der Intel Threading Challenge 2010!

Mit Intel Adivsor schrittweise parallel programmieren

Zurück von der großen Intel Entwickler-Konferenz – auch IDF (Intel Developer Forum) genannt – gibt’s hier Stück für Stück viele nützliche Infos und News aus der Welt des Parallel & Visual Computing. Soll heißen, dass ihr über all die Dinge etwas erfahrt, die ich mir in San Francisco angehört und angesehen habe. Also dann, viel Spaß damit!

Den Anfang macht ein kleines, unscheinbares Tool, dass sich Intel Parallel Advisor nennt, Teil des Intel Parallel Studio 2011 ist und Software-Entwicklern dabei helfen soll, nativ programmierten Code schneller, effizienter und einfacher zu parallelisieren. Dabei geht der Advisor sehr systematisch vor, um die bestmöglichen Ergebnisse in Sachen parallelisierter Quellcode zu erreichen. Hierzu sind fünf Schritte notwendig:

1. Survey Target: Im ersten Schritt wird der Quellcode auf mögliche Hotspots untersucht und dabei festgestellt, welche Abschnitte innerhalb des Programms besonders für eine Parallelisierung in Frage kommen.

2. Annotate Sources: Anschließend fügt der Advisor in die identifizierten Quellcodestellen sogenannte Annotationen ein, also entsprechende Pseudo-Befehle, die das Parallelisieren ermöglichen sollen. Dieser Abschnitt ist als eine Art Experiment zu sehen, mit dessen Hilfe man die bestmöglichen Ansätze für Parallelcode finden soll.

3. Check Suitability: Nachdem man die Annotationen in den seriellen Quellcode eingefügt hat, macht sich der Parallel Advisor per Mausklick daran, die vorgenommenen Änderungen des Programms auf Machbarkeit hin zu überprüfen. Hierbei wird vor allem festgestellt, was die Veränderungen zur Laufzeit tatsächlich bringen, ob sich ein Parallelisieren an dieser Stelle also überhaupt lohnt.

4. Check Correctness: Der vierte Schritt hat vor allem mit möglichen Speicherproblemen zu tun. Dabei überprüft der Parallel Advisor wiederrum per Mausklick, welche Dead Locks, Data Races und andere möglichen Probleme anhand der vorgenommenen Änderungen des ursprünglich seriellen Quellcodes zu erwarten sind. Dies ist bei der Umstellung von seriell auf parallel ein kritischer Punkt, den man auf keinen Fall unterschätzen darf. Mögliche Speicherfehler lassen sich nämlich mit herkömmlichen Testverfahren oder Debuggern nur ganz schwer oder gar nicht aufspüren.

5. Add Parallel Framework: Sobald der Parallelcode keine Fehler mehr aufweist und sämtliche Speichertests ohne Probleme durchgeführt werden konnten, müssen nur noch sämtliche Annotationen durch entsprechende Konstrukte und Funktionsaufrufe ersetzt werden. Dabei kann man aus einer Reihe von unterstützten Programmiermodellen wie Intel Threading Building Blocks, Intel Cilk Plus und anderen auswählen – je nachdem, welches Modell besser zum ausgewählten Quellecodeabschnitt passt.

Ach ja: Bilder und weitere Erklärungen zum Intel Parallel Advisor bekommt ihr noch diese Woche auf dem Software Dev Blog. So, stay tuned…

Acht nützliche Tipps zum Parallelisieren

Aufmerksamen Lesern des Software Dev Blogs wird es nicht entgangen sein: es war hier in letzter Zeit ein wenig ruhiger, was mit vielen anderen Aktivitäten meinerseits zu tun hatte. Ich war viel unterwegs, hab viele neue Themen recherchiert und gesammelt, saß mit Leuten zusammen, etc. Und der Output wird sich sehen lassen können: Das reicht von Exklusivinfos direkt vom Intel Developer Forum in San Francisco bis hin zu neuesten Beiträge rund um das Thema Cilk und Co, die ich mit dem Kollgen Deilmann von Intel gemeinsam erarbeiten werde.

Den Anfang macht heute ein Online-Artikel des werten Kollegen Edmund Preiss, der es sich mal wieder zur Aufgabe gemacht hat, die Parallelprogrammierung ein wenig näher zu begutachten. Herausgekommen sind acht sehr nützliche Tipps, die ich hier zusammenfassen will. Den kompletten Beitrag findet ihr auf elektroniknet.net.

Tipp 1: In parallelen Strukturen denken und entwickeln — Hiefür bietet sich für C++-Entwickler beispielsweise das Intel-Tool Parallel Advisor an, das dabei hilft, in einem seriellen Programm parallel Strukturen aufzuspüren. Hierzu gibt es nächste Woche mehr Infos direkt vom IDF, die ich mit vielen Bildern garnieren werde.

Tipp 2: Höhrere Abstraktionsgrade erlauben thread-sichere Programme — Hierfür bieten sich spezielle Bibliotheken an, aber auch Programmiermodelle wie OpenMP oder Intel Threading Building Blocks. Ganz neu am Start in diesem Zusammenhang sind die Intel Array Building Blocks. Auch hierzu gibt es nächste Woche dedizierte Infos.

Tipp 3: Denke und programmiere in Tasks, nicht in Threads — Dieser Tipp hilft, die Skalierbarkeit auf mehreren Prozessorkernen deutlich zu verbessern

Tipp 4: Arbeite mit so wenig Locks wie möglich, aber mit so vielen wie nötig — Hier geht es um Data Races, die beim Umgehen von Locks entstehen können. Und mit Tools wie dem Intel Parallel Inspector kann man mögliche Data Races und Dead Locks identifizieren lassen.

Tipp 5: Skalierbare Speicker-Allokatoren helfen, Speicherzuweisung bei parallelen Programmen zu optimieren.

Tipp 6: Erhöhe die parallele Auslastung, um den seriellen Anteil an Code zu verringern — Dies hat mit der Erkenntnis zu tun, dass Anwendungen nur mit ihrem Anteil an parallelen Ausführungen signifikant schneller werden. Daher sollte man mit den passenden Tools nach Programmbereichen suchen, die sich gut multithreaden lassen. Hierzu gehören beispielsweise Schleifenkonstrukte.

Tipp 7: Teste parallelisierte Programmabschnitte im seriellen Modus auf mögliche Bugs hin — Hierzu gibt es zwei Möglichkeiten: Entweder das “Abschalten” parallelisierter Codeabschnitte mithilfe bestimmter Schalter oder der Einsatz der Intel Parallel Debugger Extensions, die Teil des Intel Parallel Composer sind.

Tipp 8: Software-Tools helfen, während der einzelnen Entwicklungsschritte (Design, Kompilieren, Debuggen, Verifikation und Leistungsverbesserung), die richtigen Dinge zu tun. Hierzu gehört die Entwicklersuite Intel Parallel Studio, die Entwicklern nativ programmierter Programme genau dabei hilft.