Rezension von “Getting Started with Roo” von Josh Long und Steve Mayzak

December 1st, 2011

Mein Fazit “Knapper Einstieg und Überblick“.


image

Rezension des Buchs “Programming Concurrency on the JVM” von Venkat Subramaniam

December 1st, 2011

Mein Fazit “Stellenweise sehr gut, stellenweise nicht ausgereift und zu knapp“.


image

Rezension von “Complexity – A Guided Tour”

August 8th, 2011

Rezension von
Complexity – A Guided Tour by Melanie Mitchell

Dieses Buch ist eine lesenswerte und interessante Einführung. “Komplexität” ist ein Querschnittsthema und durchzieht viele Fachbereiche, wie z. B. die Biologie (Immunsystem, Gehirn, Evolution), Wirtschaftswissenschaften, Informatik und Künstliche Intelligenz.

Dementsprechend abwechslungsreich sind die behandelten Themen, wie z. B. Informationstheorie, Berechnung (“Computation”), Genetik, Evolution, Genetische Algorithmen, Zellularautomaten und Netzwerke.

Sämtliche Themen werden mit ihrem historischen Hintergrund und den beteiligten Wissenschaftlern vorgestellt, wie z. B. Darwin, Mendel, Maxwell, Gödel, Turing, von Neumann und Wolfram. Dieses Buch enthält somit auch eine Geschichte der “Komplexität”.

Das Buch richtet sich an den interessierten Laien. Mathematikkenntnisse sind nicht notwendig. Für ca. 20% des Buches ist allerdings ein Interesse an formalen Systemen notwendig. Um der Argumentation folgen zu können, muss man sich mit den Beispielen beschäftigen und im Kopf oder auf dem Papier “simulieren”. Ich glaube aber, dass man das Buch auch ohne diese formaleren Teile mit Gewinn lesen kann.

Das Buch ist eine Einführung. Um komplexe Systeme analysieren oder programmieren zu können, sind vertiefende Bücher notwendig.

Ich habe auch zwei Kritikpunkte am Buch:

In Kapitel 13 beschreibt die Autorin die Ergebnisse ihrer Dissertation. Das ist 80er-Jahre-KI und veraltet. Da hat sich inzwischen bei den Suchalgorithmen und der stochastischen Grammatik eine ganze Menge getan. So “ad hoc” werden Systeme nicht mehr modelliert.

Die Autorin hat eine ziemlich unkritische Stellung zu Patenten. Sie preist einen Professor als erfolgreich an, weil dieser ein Patent für “Techniken für die Entwicklung von Proteinsequenzen für die Entdeckung neuer Medizin” hat (S. 281). Hier hätte ich eine kritischere Einstellung erwartet, denn Patente können auch nachteilige Konsequenzen haben (Verhinderung von Wettbewerb, Monopolbildung).

Alles in allem aber ein lesenswertes, abwechslungsreiches und empfehlenswertes Buch.

Der beste Einstieg in CUDA

March 13th, 2011

Rezension des Buches “Cuda by Example” von Sanders und Kandrot.

Parallele Algorithmen waren mal ein “esoterisches” Thema für theoretische Informatiker. Mit CUDA kann jetzt jeder massiv parallel programmieren und 10- bis zu 100-fache Geschwindigkeitssteigerungen erreichen.

Es gibt diese Bücher – gerade bei neuen Themen – bei denen man den Eindruck hat, die Autoren haben die Dokumentation abgeschrieben und nur ein wenig ausgeschmückt. Das ist hier definitiv nicht der Fall.

Dieses Buch ist der perfekte Start in CUDA für Einsteiger. Aber auch manche Fortgeschrittene und Profis könnten Ihre Freude an den guten Erklärungen und Beispielen haben.

Der Buchtitel “CUDA by Example” sagt es schon: Anhand von Beispielen soll gelernt werden. Und da numerische Algorithmen, wie z. B. Vektoraddition, Matrizen-Multiplikation zwar auch behandelt werden, aber von vielen nicht als “Spaß” empfunden werden, haben die Autoren  graphische Beispiele zusammengestellt: Julia-Mengen, einen einfachen Ray Tracer, Wärmeübertragung .

Die Parallelität wird schrittweise, langsam und behutsam eingeführt und immer ausführlich erklärt. Ausgangspunkt ist sequentieller Code für die CPU, der dann umgeformt wird. 

Das Ziel des Buches, ist es, dem Leser die Grundlagen von CUDA beizubringen, damit er selber darin entwickeln kann. Die Theorie paralleler Algorithmen wird nicht behandelt, wird aber im Rahmen des Buches auch nicht benötigt.

Als parallele Lektüre und als Nachschlagewerk benötigt man den “NVIDIA CUDA Programming Guide” und die “NVIDIA CUDA Best Practices”, die beide von NVIDA mit dem CUDA Toolkit mitgeliefert werden.

Allerdings ist es ein Einsteigerbuch und die folgenden fortgeschrittenen Themen werden nicht behandelt.

- Performance-Optimierung von Kerneln

- Optimierung von Speicherzugriffen (“coalescing”)

- CUDA Arrays, 3D-Speicher

- CUDA Hardware im Detail, z. B. Warp-Scheduling

- Vermeidung von Divergenz

- Neuerungen bei Fermi, z. B. Caching

- CUDA Driver API

Fortgeschrittene Kenntnisse in C oder C++ sind notwendig, d.h. man sollte schon Programme geschrieben und gelesen haben. Auch sind Erfahrungen auf der Kommandozeile oder einer C-Entwicklungsumgebung von Vorteil. Grundwissen über parallele Algorithmen ist nicht schlecht, aber nicht unbedingt notwendig.

Und hier noch eine stichwortartige Auflistung, um die Bewertung 4 von 5 zu rechtfertigen.

Positiv

- Gute Beispiele, gute Erklärungen, langsames Tempo

- Die Autoren benutzen erst Grid-Blöcke und im zweiten Schritt Thread-Blöcke, um Parallelität einzuführen. Das ist eine gute Idee und das pädagogisch Sinnvollste. 

- Schöne Beispiele zum Anschauen, wie z. B.  Julia-Mengen, Ray Tracer als Beispiel für konstanten Speicher, Shared Memory und Bitmaps, Wärmeübertragung für 1D- und 2D-Texturen

- Schöne Einleitung mit Historie und Anwendungsbeispielen

- Installation des Treibers, des Toolkits und des SDKs werden erklärt

- Der Quellcode ist herunterladbar und funktioniert (meistens) auch

- Gutes Beispiele für atomare Operationen im Anhang (Hash-Tabelle)

Negativ

- Der Code wurde immer vollständig abgedruckt. Hier kommt es im Laufe des Buchs zu Wiederholungen. Für Einsteiger mag diese Entscheidung richtig sein, den Fortgeschrittenen nervt es, eine Funktionsdefinition mehr als einmal lesen zu müssen. Ganz schlimm ist dieses bei den Ereignisse / Events, wenn der gesamte Ray Tracer noch zweimal abgedruckt wird (einmal mit globalem, einmal mit konstantem Speicher).

- Sehr schnell veraltende Informationen wurden abgedruckt, z. B. die Liste der Devices auf S. 15f.

- Die Dateinamen der Beispielprogramme stehen nicht im Buch. Man muss daher manchmal ein wenig suchen.

- Abschnitt 3.3 „Querying Devices“ ist zu diesem Zeitpunkt zu ausführlich. Das will man nicht alles  wissen. Man kann auch zu diesem Zeitpunkt mit 95% der Begriffe nichts anfangen. Da hätte auch ein Verweis zur Dokumentation genügt.

- Für Anfänger wäre ein kurzer Abschnitt über grundlegende Design-Patterns bzw. parallele Algorithmen sehr praktisch.

Fazit

Wer CUDA lernen will, findet in diesem Buch die beste Einleitung, die es momentan gibt.

 

Using Scala and TestNG with Gradle

December 30th, 2010

I brushed up my knowledge of the programming language Scala during the christmas holidays. I read the book Programming in Scala by Odersky et al. again and i started to develop some code using the Scala plugin of IntelliJ IDEA 10. If you are programming in Groovy or Scala you really should give IDEA a try. In my opinion it is the best IDE.

Since i am a fan of TestNG i wanted to use it, too. Actually it’s easily usable with Scala using ScalaTest.The following snippet is an example of the TestNGSuite and the equality === which gives an error message it it’s operants are not equal.

package net.dinkla.scalaville.utilities

import org.scalatest.testng.TestNGSuite
import org.testng.annotations.Test

class ValueTest extends TestNGSuite {

  object TestMeasure extends Measure("TestMeasure")

  @Test
  def value() = {
    val v1 = new Value(20, TestMeasure)
    val v2 = new Value(10, TestMeasure)
    val v3 = v1 + v2
    assert(v3.amount === 30)
  }
}

As a build tool i used gradle for the first time. And it was not that straightforward, I had to search the web and read manuals for more than half an hour to get this working. The following is the complete build script. My project deviates from the standard directory structure, so i have to declare, that my source code is in src and tests are in test.

apply plugin: 'scala'

repositories {
    mavenRepo urls: 'http://scala-tools.org/repo-releases'
    mavenCentral()
}

dependencies {
    scalaTools 'org.scala-lang:scala-compiler:2.8.1'
    scalaTools 'org.scala-lang:scala-library:2.8.1'
    compile 'org.scala-lang:scala-library:2.8.1'
    testCompile 'org.testng:testng:5.14.4'
    testCompile 'org.scalatest:scalatest:1.2'
}

sourceSets {
    main {
        scala {
            srcDir 'src'
        }
    }
    test {
        scala {
            srcDir 'test'
        }
    }
}

test {
    useTestNG()
}

Lessons learned:
At the time of writing the central maven repository has older versions of ScalaTest in the directory org.scala-tools.testing. Do not use these with the newest TestNG and Scala 2.8. Use the newer version 1.2 from the directory org.scalatest in the scala-tools.org repository.

Sony verprellt die ersten Fans der Playstation 3

April 7th, 2010

Am 1. April hat Sony ein Update für die Playstation 3 herausgegeben, mit dem der Support für Linux eingestellt wird. Das hat viele verärgert und teilweise heftige Reaktionen und Diskussionen entfacht.

Forscher, Wissenschaftler und Tüftler aus dem Scientific Computing und dem High Performance Computing (HPC) waren die ersten Fans der Playstation 3. Diese ‘Early adopter’ haben den Ruf der Playstation 3 als “Supercomputer” mitbegründet. 2007 waren dieses die ersten Marketingerfolge, denn Spiele für die PS3 waren Mangelware, den allermeisten war die PS3 viel zu teuer (599 Euro) und die Spieleentwickler klagten darüber, dass die PS3 schwierig zu programmieren sei.

Und jetzt gibt man den ersten Fans ganz klar zu verstehen, dass Sony sie nicht mehr braucht und gibt ihnen sozusagen einen Tritt in den Hintern.

Von Sony wurde auch Werbung mit Linux gemacht, man sagte, die ‘PS3 ist ein Computer’. In den Handbüchern der “fat ladies” (das sind die älteren Modelle) wird die Installation von Linux im Handbuch beschrieben. Und das jetzt zu entfernen, ist rechtlich fragwürdig: Man hat ein System gekauft, dass A & B & C konnte (A=Spielen, B=PSN/Downloads, C=Linux). Jetzt kann es nur noch A & B ODER A & C. Im Gegensatz zur Meinung vieler Anderer spielt es meiner Meinung nach überhaupt keine Rolle, das Linux nur von wenigen Leuten eingesetzt wird.

Die Angabe von Sony, dass dieses aus Sicherheitsgründen geschieht, erscheint dem Technikinteressierten als eine Ausrede. Die Sicherheit der PS3 ist in der Hardware realisiert, nicht in der Software. Das Linux bereits verfügbar ist erspart den Hackern aus meiner Sicht maximal eine Woche Arbeitsaufwand, denn der Cell-Prozessor ist ein PowerPC und damit gibt es den GNU C Compiler gcc und alle andere Werkzeuge schon.

Ich persönlich bin von Sony sehr enttäuscht und empfinde das Verhalten als Schlag ins Gesicht. Ich vermute, dass die technischen Visionäre, die die Playstation 3 ins Leben gerufen haben nicht mehr am Ruder sind, sondern von einer Art Management-Heuschrecken ersetzt wurden.

Hier sind auch noch weitere Fragen zu klären, die in späteren Artikeln behandelt werden.

  • Ist der Cell-Prozessor Geschichte?
  • Wird die Sicherheit der Playstation 3 durch Linux bedroht?
  • Ich habe ein System gekauft, dass A & B & C konnte. Jetzt kann es nur noch A & B oder A & C. Ist das rechtens?

CUDA Real-Time Ray Tracer

January 3rd, 2010

During the christmas holidays i rewrote my ray tracer for the NVIDIA CUDA architecture. CUDA is extremely powerful: with an NVIDA 285 i achieved more than 250 FPS for 640×480 pixels, 57 FPS for 1080×1030.

Compare this with a similiar ray tracer running on an Intel Core i7 920.

Compiling OpenCL programs on Mac OS X Snow Leopard

September 28th, 2009

I installed Snow Leopard on my laptop yesterday. I was very curious about OpenCL and installed the drivers and the GPU Computing SDK from NVIDIA.

I searched my hard disk after installation and found the following directory: /Developer/GPU Computing/OpenCL. Looks promising.

In the subdirectory src/oclDeviceQuery I found a basic test and I tried to compile it.

$ cd src/oclDeviceQuery
$ make
ld: library not found for -loclUtil
collect2: ld returned 1 exit status
make: *** [../../..//OpenCL//bin//darwin/release/oclDeviceQuery] Error 1

I googled for “-loclUtils”? I found nothing. “liboclUtils”? Nothing. So i found a brand new problem that is not known to mankind. Hurray. ;-)

But i remembered a similiar situation when i used the CUDA-SDK. So i searched the other directories. The solution is to create the library manually.

$ pushd ../../common/
$ make
ar: creating archive ../..//OpenCL//common//lib/liboclUtil.a
q - obj/release/oclUtils.cpp.o
$ popd

So -loclUtil should now be found. And i tried to compile again.

$ make
ld: library not found for -lshrutil
collect2: ld returned 1 exit status
make: *** [../../..//OpenCL//bin//darwin/release/oclDeviceQuery] Error 1

Aha, there’s another library missing. I tried the one in /Developer/GPU Computing/shared.

$ cd ../../../shared/
$ make
src/rendercheckGL.cpp: In member function ‘virtual bool CheckBackBuffer::readback(GLuint, GLuint, GLuint)’:
src/rendercheckGL.cpp:523: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘GLuint’
src/rendercheckGL.cpp:527: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘GLuint’
src/rendercheckGL.cpp: In member function ‘virtual bool CheckFBO::readback(GLuint, GLuint, GLuint)’:
src/rendercheckGL.cpp:1342: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘GLuint’
src/rendercheckGL.cpp:1346: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘GLuint’
a - obj/release/shrUtils.cpp.o
a - obj/release/rendercheckGL.cpp.o
a - obj/release/cmd_arg_reader.cpp.o

Back into the directory with the device query sources.

$ cd ../OpenCL/src/oclDeviceQuery/
$ make

The compilation succeeds, but where’s the executable? It is not in the current directory.

$ ls
Makefile            obj/                oclDeviceQuery.cpp

I searched the directories again and its in a bin subfolder of /Developer/GPU Computing/OpenCL

$ ../../bin/darwin/release/oclDeviceQuery

oclDeviceQuery.exe Starting...

OpenCL SW Info:

 CL_PLATFORM_NAME: 	Apple
 CL_PLATFORM_VERSION: 	OpenCL 1.0 (Jul 15 2009 23:07:32)
 OpenCL SDK Version: 	1.2.0.16
...

That’s it. OpenCL runs on my laptop. Yeah. :-)

Hyper-Threading with the Intel Core i7

June 14th, 2009

I have got a new computer. As alway i build it myself. See the following photos and note the impressive size of the cpu cooler by Noctua).

   

I chose the Intel Core i7, because i was very curious about it’s technical features. It has four “real” physical cores, but provides eight “virtual” cores with hyper-threading. These “virtual” cores are shown by the operating systems in their task/process managers. See the following screenshots for Windows and Linux.

    8 cores on Linux

The question i asked myself is: How do these virtual cores perform ? How many programms can i run in parallel without hurting performance ? What is the speedup ? Is it 4 ? Is it 8 ?

So I made a test. I chose a single threaded program, the ray tracer pbrt and started this program 1, 2, 3, …, 8, 9, 10 times as a process under Linux and timed the running times. Here are the results.

Number of programms Running times Speedup Explanation
1 2 3 4 5 6 7 8 9 10
1 1:18.27 - - - - - - - - - 1
2 1:18.57 1:18.32 - - - - - - - - 1.997
3 1:18.69 1:18.76 1:19.18 - - - - - - - 2.97
4 1:19.62 1:21.88 1:20.12 1:19.68 - - - - - - 3.83
5 1:54.01 1:54.38 1:53.47 1:19.33 1:54.90 - - - - - 3.41 2 cores with 2 threads each and 1 core with 1 thread
6 1:56:13 1:22.16 1:23.09 1:54.22 1:55.41 1:54.95 - - - - 4.05 2 cores with 2 threads each and 2 core with 1 thread each
7 1:53.27 1:25.28 1:53.62 1:53.92 1:56.38 1:55.49 1:54.05 - - - 4.72 3 cores with 2 threads each and 1 core with 1 thread
8 1:59.50 1:57.72 1:55.16 1:54.96 1:58.60 1:57.72 1:58.46 1:59.62 - - 5.25 4 cores with 2 threads each
9 2:08.65 2:09.34 1:59.44 2:07.06 2:00.61 2:38.73 2:02.70 2:01.40 2:10.74 - 4.45 4 cores with 2 threads each
10 2:04.29 2:23.16 2:44.80 2:09.42 2:45.95 2:16.97 2:14.71 2:10.60 2:15.10 2:09.96 4.73 4 cores with 2 threads each

For up to four programs the Core i7 behaves like a usual four core processor. These four programs can run in parallel with the same performance of about 80 seconds. The speedup is almost linear.

When more than four programs run, the processors has to run at least two threads on one core. Then two virtual processors have to share a single physical processors and the programs take about 114 seconds.

Conclusion: Hyper-threading gives us some extra computing power here. The best speedup of 5.25 was achieved with 8 programs.

By the way: the following image was the one rendered for the benchmark. See the gallery of pbrt for more.


Parallelization with Haskell – Easy as can be

June 7th, 2009

The functional programming language Haskell provides a very easy way of parallelization. Consider the following naive implementation of the
Fibonacci function.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This implementation has a bad expontential time complexity, so it should be improved, for example with caching. But this is beyond the scope of this article. We just need a function that takes a while to finish.

In Haskell there are two operators that have to be used for parallelization: par and pseq. par a b is some kind of a “fork” operation: a is started in parallel and b is returned. Keep in mind that Haskell is has a lazy evaluation strategy. a is only evaluated if it is needed The function pseq a b evaluates first a then b.

Equipped with this two operations it is very easy to parallelize fib.

parfib n
| n < 11 = fib n -- For small values of n we use the sequential version
| otherwise = f1 `par` (f2 `pseq` (f1+f2)) -- calculate f1 and f2 in parallel, return the sum as the result
where
f1 = parfib (n-1)
f2 = parfib (n-2)

The code has to be compiled with the -threaded option.

ghc -O3 -threaded --make -o parfib ParFib.hs

The number of threads is specified at runtime with the -N command line option.

./parfib +RTS -N7 -RTS

On an Intel Core i7 920 this resulted in a speedup of 4.13 for n=38. This processor has four physical cores.

So this is efficient. Haskell is still one of the best programming languages.


Copyright © 2007-2011 Jörn Dinkla. All rights reserved.

###ENDMATTER