Seite 3: MapReduce & Fazit

Inhaltsverzeichnis

MapReduce und Mandelbrot

Das von Google patentierte MapReduce-Framework entstand, um große Datenmengen parallel zu verarbeiten. Das Verfahren wendet im ersten Schritt eine sogenannte Map-Funktion auf eine Liste von Daten eines beliebigen Typs T an. Im zweiten fasst eine Reduce-Funktion die Ergebnisse zusammen. Das QtConcurrent-Framework implementiert MapReduce in der Funktion mappedReduced:

QFuture<T> QtConcurrent::mappedReduced ( const Sequence 
   & sequence, MapFunction mapFunction, ReduceFunction 
      reduceFunction, QtConcurrent::ReduceOptions reduceOptions
        = UnorderedReduce | SequentialReduce )

Dabei haben die Map- und Reduce-Funktionen folgende Formen:

U mapFunction(T &input) 
void reduceFunction(V &result, const U &intermediate)  

Mit dem Parameter reduceOptions legt der Entwickler fest, ob die Reihenfolge der Ausgangssequenz im Reduce-Schritt beibehalten werden soll. Auf das Ergebnis der Berechnung lässt sich per QFuture zugreifen, wobei die Klasse QFutureWatcher bei Bedarf nützliche Signale und Slots liefert.

Das Beispiel QMapReduceMandelbrot demonstriert MapReduce anhand der Berechnung einer Mandelbrot-Menge. Ähnlich wie das QParallelMandelbrot-Beispiel wird das zu berechnende Bild wieder in Abschnitte von je 100 Bildzeilen zerlegt. Die Funktion Data::initChunkList() speichert die Zeilennummer dieser Chunks in der Liste chunkList. Die Map-Funktion calcChunk berechnet aus der Zeilennummer den zugehörigen Bildabschnitt:

QImage calcChunk(const int chunk) {

    int i1, i2;
    double z_re, z_im, xScale, yScale, xOfs, yOfs;
    QImage chunkImage(imageWidth, chunkLen, QImage::Format_RGB32);
  
    xOfs = -(double)imageWidth/1.25;
    yOfs = -(double)imageHeight/2.0;
    xScale = 2.6 / (double)imageWidth;
    yScale = 2.6 / (double)imageHeight;
    for (i1 = 0; i1 < chunkLen; i1++) 
        for (i2 = 0; i2 < imageWidth; i2++) {
            z_re = (double)(i2 + xOfs) * xScale;
            z_im = (double)(chunk + i1 + yOfs) * yScale;
            chunkImage.setPixel(i2, i1, 
                palette[mandelPixel(z_re, z_im)].rgb());
       }
    return(chunkImage);
}

Die Reduce-Funktion collectChunks fasst die Bildabschnitte zusammen. Dazu erzeugt der Code zunächst ein QImage, in das er die Teilbilder per drawImage kopiert. Für eine korrekte Berechnung der Offsets setzt das Verfahren voraus, dass man MappedReduced mit dem Parameter QtConcurrent::OrderedReduce aufruft:

void collectChunks(QImage &mandelImage, const QImage &chunkImage) {

     static int offset = 0;
     if (!offset) mandelImage = QImage(imageWidth, imageHeight,
        QImage::Format_RGB32);
     QPainter p(&mandelImage);
     p.drawImage(QPoint(0, offset), chunkImage);
     offset += chunkLen;

Die Funktion Data::calcMandelBrot() verwendet QFutureWatcher für den Zugriff auf Signale, die über Fortschritt und Beendung der Berechnung informieren:

void Data::calcMandelBrot() {

    mandelWatcher = new QFutureWatcher<QImage>; 
    QObject::connect(mandelWatcher, SIGNAL(finished()), this,
        SLOT(mandelFinished()));
    QObject::connect(mandelWatcher, SIGNAL(progressValueChanged(int)),
        this, SLOT(mandelProgress(int)));
    mandelImage = QtConcurrent::mappedReduced(chunkList, 
        calcChunk, collectChunks, QtConcurrent::OrderedReduce);
    mandelWatcher->setFuture(mandelImage);
}

Sowohl QParallelMandelbrot als auch QMapReduceMandelbrot ermitteln die benötigte Rechenzeit mit einem QTime-Objekt. Auf dem Notebook des Autors ist zwischen beiden Varianten kein signifikanter Performanceunterschied messbar (Abweichung deutlich unter 1 Prozent). Erwartungsgemäß wird die Rechenzeit im Wesentlichen in der Funktion mandelPixel verbraucht, sodass die unterschiedlichen Ansätze für die Parallelisierung nicht ins Gewicht fallen.

Mehr zu QtConcurrent

Abschließend sei noch ein Überblick über weitere Funktionen von QtConcurrent gegeben. Zusätzlich zur Funktion mappedReduced gibt es die blockierende Variante blockingMappedReduced, deren Aufruf erst zurückkehrt, wenn alle Elemente der Sequenz vollständig bearbeitet sind. Alternativ zu einer Sequenz lassen sich beiden Funktionen Beginn und Ende eines Iterators übergeben. Neben mappedReduced bietet QtConcurrent eine einfache map-Funktion:

QFuture<void> QtConcurrent::map ( Sequence & sequence, 
    MapFunction function )

Der Aufruf wendet function auf jedes Element von sequence an. Die Parameterübergabe geschieht dabei per Referenz, sodass die Elemente in-place modifiziert werden. Falls die Elemente der Sequenz unverändert bleiben sollen, bietet sich die Funktion mapped an:

QFuture<T> QtConcurrent::mapped ( const Sequence & sequence, 
    MapFunction function )

Hier werden die Rückgabewerte von function in einer QFuture-Variablen gespeichert. Für den Zugriff auf die Ergebnisse gibt es die zwei blockierenden Funktionen resultAt und results sowie die Klassen const_iterator und QFutureIterator:

T QFuture::resultAt ( int index ) const
QList<T> QFuture::results () const
QFuture::const_iterator
QFutureIterator ( const QFuture<T> & future )

Mit den Funktionen filter und filtered ermöglicht QtConcurrent das Filtern von Daten anhand einer Filterfunktion:

QFuture<void> QtConcurrent::filter ( Sequence & sequence, 
    FilterFunction filterFunction )
QFuture<T> QtConcurrent::filtered ( const Sequence & sequence, 
    FilterFunction filterFunction )

Dabei entfernt ein Aufruf von filter alle Elemente aus der Sequenz, für die die Filterfunktion den Wert "false" zurückliefert. filtered kopiert die Elemente in die QFuture-Variable, für die filterFunction den Wert "true" zurückgibt.

Fazit

Nebenläufigkeit lässt sich mit Qt auf vielfältige Weise realisieren. Das Erzeugen eigener Threads mit QThread bietet die größte Flexibilität, verlangt aber vom Programmierer besondere Sorgfalt im Umgang mit kritischen Bereichen. Mit der Basisklasse QRunnable kann der Entwickler Code auf effiziente Weise im Thread-Pool ausführen. Die Klasse erzeugt wenig Overhead, implementiert aber keinerlei Signale oder Slots. Für das parallele Ausführen einer Funktion und das Anwenden von Funktionen auf Listenobjekte ist QtConcurrent eine gute Wahl. Hier bieten die Klassen QFuture und QFutureWatcher zahlreiche Steuerungsmöglichkeiten.

Dr. Matthias Nagorni
war mehr als 10 Jahre als Softwareentwickler und Produktmanager bei SUSE/Novell tätig und hat zahlreiche Open-Source-Applikationen in Qt veröffentlicht. (ane)