Das Aufteilen eines Programms in 4 Threads ist langsamer als ein einzelner Thread

StackOverflow https://stackoverflow.com/questions/8980056

Frage

Ich habe letzte Woche einen Raytracer geschrieben und bin an einem Punkt angelangt, an dem er so viel leistet, dass Multithreading sinnvoll wäre.Ich habe versucht, es mit OpenMP zu parallelisieren, aber die Ausführung mit mehr Threads ist tatsächlich langsamer als die Ausführung mit einem.

Beim Durchlesen anderer ähnlicher Fragen, insbesondere zu OpenMP, lautete ein Vorschlag, dass gcc den seriellen Code besser optimiert.Führen Sie jedoch den kompilierten Code unten mit aus export OMP_NUM_THREADS=1 ist doppelt so schnell wie mit export OMP_NUM_THREADS=4.D.h.Es handelt sich bei beiden Läufen um denselben kompilierten Code.

Ausführen des Programms mit time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

Die Benutzerzeit ist viel geringer als in Wirklichkeit, was bei der Verwendung mehrerer Kerne ungewöhnlich ist- Benutzer sollte größer sein als real da mehrere Kerne gleichzeitig laufen.

Code, den ich mit OpenMP parallelisiert habe

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

Beim Lesen diese Frage Ich dachte, ich hätte meine Antwort gefunden.Es geht um die Implementierung von gclib rand(), das Aufrufe mit sich selbst synchronisiert, um den Status für die Zufallszahlengenerierung zwischen Threads beizubehalten.Ich verwende rand() ziemlich oft für Monte-Carlo-Sampling, also dachte ich, dass das das Problem sei.Ich habe Aufrufe von rand entfernt und sie durch einen einzelnen Wert ersetzt, aber die Verwendung mehrerer Threads ist immer noch langsamer. BEARBEITEN:Hoppla Es stellte sich heraus, dass ich das nicht richtig getestet habe, es waren die Zufallswerte!

Nachdem diese nun geklärt sind, werde ich einen Überblick darüber geben, was bei jedem Anruf durchgeführt wird computePixel, also kann hoffentlich eine Lösung gefunden werden.

In meinem Raytracer habe ich im Wesentlichen einen Szenenbaum mit allen darin enthaltenen Objekten.Dieser Baum wird währenddessen häufig durchquert computePixel Wenn Objekte jedoch auf Schnittmengen getestet werden, werden weder in diesen Baum noch in andere Objekte geschrieben. computePixel liest die Szene im Wesentlichen mehrere Male, ruft Methoden für die Objekte auf (alle davon sind konstante Methoden) und schreibt ganz am Ende einen einzelnen Wert in sein eigenes Pixelarray.Dies ist der einzige mir bekannte Teil, bei dem mehr als ein Thread versuchen wird, in dieselbe Mitgliedsvariable zu schreiben.Es gibt nirgendwo eine Synchronisierung, da keine zwei Threads in dieselbe Zelle im Pixelarray schreiben können.

Kann jemand Orte vorschlagen, an denen es zu Streitigkeiten kommen könnte?Dinge zum Ausprobieren?

Vielen Dank im Voraus.

BEARBEITEN:Entschuldigung, es war dumm, keine weiteren Informationen zu meinem System bereitzustellen.

  • Compiler gcc 4.6 (mit -O2-Optimierung)
  • Ubuntu Linux 11.10
  • OpenMP 3
  • Intel i3-2310M Quad Core 2,1 GHz (momentan auf meinem Laptop)

Code zur Pixelberechnung:

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

Den Vorschlägen zufolge könnte es die Baumdurchquerung sein, die die Verlangsamung verursacht.Einige andere Aspekte:Es ist ziemlich viel Rekursion erforderlich, sobald die Sampling-Funktion aufgerufen wird (rekursives Strahlenreflektieren) – könnte dies diese Probleme verursachen?

War es hilfreich?

Lösung

Vielen Dank an alle für die Vorschläge, aber nach weiterer Profilerstellung und Beseitigung anderer beitragender Faktoren erfolgt die Generierung von Zufallszahlen tat erweisen sich als der Schuldige.

Wie in der obigen Frage dargelegt, muss rand() seinen Status von einem Aufruf zum nächsten verfolgen.Wenn mehrere Threads versuchen, diesen Status zu ändern, würde dies zu einer Race-Bedingung führen, weshalb die Standardimplementierung in glibc dies ist Sperren Sie jeden Anruf, um die Funktion threadsicher zu machen.Das ist schrecklich für die Leistung.

Leider sind die Lösungen für dieses Problem, die ich bei Stackoverflow gesehen habe, alle lokal, d. h.komm mit dem Problem klar in dem Bereich, in dem rand() aufgerufen wird.Stattdessen schlage ich eine „schnelle und schmutzige“ Lösung vor, die jeder in seinem Programm verwenden kann, um für jeden Thread eine unabhängige Zufallszahlengenerierung zu implementieren, die keine Synchronisierung erfordert.

Ich habe den Code getestet und er funktioniert – es gibt keine Sperrung und keine spürbare Verlangsamung durch Aufrufe von Threadrand.Auf offensichtliche Fehler können Sie gerne hinweisen.

threadrand.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

threadrand.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

Jetzt können Sie die Zufallszustände für Threads initialisieren main verwenden init_threadrand(), und anschließend eine Zufallszahl mit erhalten threadrand() bei Verwendung mehrerer Threads in OpenMP.

Andere Tipps

Die Antwort lautet: Ohne zu wissen, auf welchem ​​Computer Sie dies ausführen, und ohne den Code Ihres Computers wirklich zu sehen computePixel Funktion, dass es darauf ankommt.

Es gibt eine ganze Reihe von Faktoren, die sich auf die Leistung Ihres Codes auswirken können. Eine Sache, die mir in den Sinn kommt, ist die Cache-Ausrichtung.Vielleicht sind Ihre Datenstrukturen, und Sie haben einen Baum erwähnt, nicht wirklich ideal für das Caching, und die CPU wartet am Ende darauf, dass die Daten aus dem RAM kommen, da sie nicht in den Cache passen kann.Falsche Cache-Line-Ausrichtungen könnten so etwas verursachen.Wenn die CPU darauf warten muss, dass Dinge aus dem RAM kommen, ist es wahrscheinlich, dass der Thread kontextumgeschaltet wird und ein anderer ausgeführt wird.

Ihr Betriebssystem-Thread-Scheduler ist daher nicht deterministisch. Wann Die Ausführung eines Threads ist nicht vorhersehbar. Wenn Ihre Threads also nicht häufig ausgeführt werden oder um CPU-Kerne konkurrieren, kann dies ebenfalls zu einer Verlangsamung führen.

Auch die Thread-Affinität spielt eine Rolle.Ein Thread wird auf einem bestimmten Kern geplant und normalerweise Es wird versucht, diesen Thread auf dem gleichen Kern zu halten.Wenn mehr als einer Ihrer Threads auf einem einzelnen Kern ausgeführt wird, müssen sie sich denselben Kern teilen.Ein weiterer Grund, warum sich die Dinge verlangsamen könnten.Sobald ein bestimmter Thread auf einem Kern ausgeführt wurde, bleibt er aus Leistungsgründen normalerweise dort, es sei denn, es gibt einen guten Grund, ihn auf einen anderen Kern auszutauschen.

Es gibt noch einige andere Faktoren, an die ich mich auf den ersten Blick nicht erinnern kann. Ich schlage jedoch vor, etwas über das Einfädeln zu lesen.Es ist ein kompliziertes und umfangreiches Thema.Es gibt jede Menge Material da draußen.

Handelt es sich bei den Daten, die am Ende geschrieben werden, um Daten, die andere Threads verarbeiten können müssen computePixel ?

Eine starke Möglichkeit ist falsches Teilen.Es sieht so aus, als würden Sie die Pixel nacheinander berechnen, sodass jeder Thread möglicherweise an verschachtelten Pixeln arbeitet.Das ist normalerweise eine sehr schlechte Sache.

Was passieren könnte, ist, dass jeder Thread versucht, den Wert eines Pixels neben einen Wert zu schreiben, der in einem anderen Thread geschrieben wurde (alle schreiben in das Sensorarray).Wenn diese beiden Ausgabewerte dieselbe CPU-Cache-Zeile verwenden, wird die CPU gezwungen, den Cache zwischen den Prozessoren zu leeren.Dies führt zu einem übermäßigen Spülvorgang zwischen den CPUs, was einen relativ langsamen Vorgang darstellt.

Um dies zu beheben, müssen Sie sicherstellen, dass jeder Thread wirklich in einer unabhängigen Region funktioniert.Im Moment sieht es so aus, als würden Sie in Zeilen teilen (ich bin mir nicht sicher, da ich OMP nicht kenne).Ob dies funktioniert, hängt davon ab, wie groß Ihre Zeilen sind – aber dennoch überlappt das Ende jeder Zeile mit dem Anfang der nächsten (in Bezug auf Cache-Zeilen).Möglicherweise möchten Sie versuchen, das Bild in vier Blöcke aufzuteilen und jeden Thread an einer Reihe aufeinanderfolgender Zeilen arbeiten zu lassen (z. B. 1..10 11..20 21..30 31..40).Dies würde das Teilen erheblich reduzieren.

Machen Sie sich keine Sorgen über das Lesen konstanter Daten.Solange der Datenblock nicht geändert wird, kann jeder Thread diese Informationen effizient lesen.Seien Sie jedoch misstrauisch gegenüber veränderlichen Daten, die Ihre konstanten Daten enthalten.

Ich habe gerade nachgeschaut und das Intel i3-2310M Es hat nicht wirklich 4 Kerne, sondern 2 Kerne und Hyper-Threading.Versuchen Sie, Ihren Code mit nur 2 Threads auszuführen, und sehen Sie, dass es hilft.Ich finde, dass Hyper-Threading im Allgemeinen völlig nutzlos ist, wenn man viele Berechnungen hat, und auf meinem Laptop habe ich es ausgeschaltet und so viel bessere Kompilierungszeiten meiner Projekte erzielt.

Gehen Sie einfach in Ihr BIOS und schalten Sie HT aus – das ist für Entwicklungs-/Rechenmaschinen nicht sinnvoll.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top