• Artikel

Dieser Artikel wurde maschinell übersetzt.

Taskbasierte Programmierung

Skalierbare Multithreadprogrammierung mit Aufgaben

Ron Fosner

Computer werden vom schneller und schnellere Prozessoren und in Richtung mehr und mehr Kerne weiterentwickelt. Das bedeutet, dass Anstieg der losen Verarbeitungsleistung zu relativ niedrigen Kosten verfügbar sind. Jedoch bedeutet, dass diese Systeme nutzen programmieren, dass latente Verarbeitungsleistung eine größere Herausforderung ist. Alle diese mehrere Prozessoren verwenden, müssen Sie in die Welt der Parallelverarbeitung ausreicht.

Es gibt viele Möglichkeiten für die Verteilung Ihrer Arbeit auf mehrere Kerne. In der Ausgabe vom Oktober MSDN Magazin (msdn.microsoft.com/magazine/gg232758 ) ich Sie einige grundlegende Konzepte der Multithreadprogrammierung vorgestellt und gezeigt, wie der Thread die Ausführung in Code mit OpenMP und Thread-Pools hinzufügen. Ich auch veranschaulicht, wie mit Tools in Visual Studio 2010 um Kern zu messen und Thread-Auslastung als Maßeinheit wie gut eine Implementierung threading verbessert die Leistung Ihrer Anwendung.

In diesem Artikel werden ich eine anspruchsvollere multithreading Technik namens aufgabenbasierte Programmierung betrachten. Aufgaben können Sie die Arbeit der Anwendung hinweg werden einiger oder aller CPU-Kerne, die verfügbar sind. Mit ein bisschen sorgfältige Programmierung können Sie minimieren und selbst Daten Abhängigkeit oder Synchronisierung der Uhrzeit Einschränkungen vorzunehmen.

Aufbauend auf aus meiner früheren Artikel gelernt haben, werde ich Sie über eine komplexere Multithread-Anwendung nutzen, die Vorgänge verwendet. Aufgaben ermöglichen die Anwendung selbst bis zu der Anzahl der Kerne verfügbar und der Umfang der Arbeit, die durchzuführende skalieren.

Eine Maus in einen Labyrinth

Wenn ich auf sat Schreiben dieses Artikels haben versucht, ein Problem kommen, die zum Parallelisieren kompliziert, aber dennoch einfach visualisieren Abläufe wurde. I drücken Sie nach dem Erstellen einer Projektmappe, die ein 2D Labyrinth lösen würden die Idee. Mag auf den ersten Blick es ein bisschen trivial, ist tatsächlich ziemlich schwierig korrekt implementieren – ich weiß, dass ich drei Versuche, es richtig hinzubekommen angefertigt.

Abbildung 1 zeigt eine einfache, seriellen Labyrinth Solver in Aktion. Die Lösung für die Labyrinth ist nur einen Pfad lange, sinuous zum mit vielen Zweigstellen, die die Dead enden. Nicht überraschend bezeichnet ich die Lösung “ Maus ”. Die Maus wird die aktuelle Zelle beobachten und versuchen Sie vorwärts zur nächsten Zelle zu wechseln. Wenn Sie eine Wand Treffer versucht er Links zu wechseln. Wenn links wechseln kann nicht versucht er rechts wechseln. Falls es in alle diese Anweisungen nicht möglich, wird, markieren den aktuellen Pfad als Dead-End und sichern.

image: Single-Threaded Maze

Abbildung 1 Singlethreaded Labyrinth

Wenn die Maus bewegt, in eine neue Zelle wird macht es notieren Sie sich alle Pfade, die es nicht enthalten. Beispielsweise ist eine Maus vorwärts verschieben, doch wurde auch links wechseln können, merkt dann Sie diese Zelle und die gewünschte Richtung. Somit die Maus um einen Korridor nach unten bewegt wird, notieren Sie Doorways auf beiden Seiten und diese auf einem Stapel abgelegt. Erreicht die Maus eine Dead-End, die Sie holt an folgenden Stellen, sichert und deaktivieren in Richtung der gespeicherten heads. Schließlich wird die Endpunkt jedoch einfach Dauerhaftigkeit erreicht werden.

Nachdem eine Maus gesichert hat, ist es erforderlich, um zu verhindern, dass Sie versuchen, eine Richtung, die Sie bereits durchsucht hat. Dies geschieht durch das Markieren einer Zelle als bereits besucht, wenn eine Maustaste in eine Zelle erfolgreich verschoben wurde. Damit eine Maus versucht eine neue Richtung zu verschieben, zuerst überprüft, dass keine Wand ist. Ist kein Wand, überprüft er, wenn die Zelle, der in Betracht ziehen wird in verschieben vor besucht wurde. Es wird Bewegung in Zellen verwerfen, die bereits besucht haben. Dies veranschaulicht die durch die grau Pfade in Abbildung 1.

Der Mouse-Lösung

Diese Lösung ist relativ leicht zu visualisieren, und daher leicht zu verstehen, die Logik für die Suche ist. Außerdem ist es etwas zu überwachenden hypnotic – zumindest für einen Moment. Ein vereinfachtes Flussdiagramm für eine serielle Maus wird angezeigt, in der Abbildung 2.

image: Flow Chart of Mouse Actions

Abbildung 2 Flussdiagramm von Aktionen Mouse

Zwar sehr einfach das Problem vom Konzept her kennen, stehen einige uneingeschränkt Elemente, die es eine Herausforderung. Zuerst müssen Sie keine Ahnung, wie lange eine Maus ausgeführt werden soll, bevor er eine Dead-End Treffer. Zweitens können Sie keine Ahnung wie viele Verzweigungen, die es entlang der Route ermittelt wird.

Dieses Problem ist doppelt interessant, wenn Sie versuchen, es auf mehrere Threads ausgeführt. Die einfachste Möglichkeit, dieses Problem Mehrkerntechnologie angezeigten, um mehrere Mäuse und erteilen jeder Maus einen eigenen Thread ist – das ist der Ansatz, den ich aufgenommen haben. Als ein zusätzlicher Vorteil verbessert dies die Visualisierung, weil ich die Maus aktive Farbe wechseln können, die ein neuer Thread übernimmt.

In der Tat war es etwas schwieriger als ursprünglich betrachtet. Sobald ich ein Singlethread-Arbeitsversion hatte vorgenommen ich den Fehler versuchen, Version angepasst und Multithreading zu machen. Dies war mein einzelne größte architektonische Fehler. Ich ging über drei unterschiedliche Revisionen, bevor ich wieder waren und die Architektur aufgabenorientiertes werden überarbeitet.

Eingegangen wird nicht meinen fehlgeschlagenen Bemühungen mit Ausnahme der Zustand, die alle den Schwerpunkt auf mich versuchen, Optimieren Sie die Leistung durch die Daten nicht kopiert und versucht, Arbeitsspeicher minimieren und Zugriff auf die freigegebenen Daten von verschiedenen Threads zu optimieren. Im Wesentlichen musste in meiner ursprünglichen Entwurf einen globalen Stapel, den sperren könnten, und ich die Speicherorte der untaken Zweige auf dem Stapel push, würde wie ich darin ausgeführt wurde. Wenn ein Thread Arbeit beendet und wurde in der Suche nach der mehr Arbeit zum Verarbeiten den Stapel (zum gleichzeitigen Zugriff durch einen anderen Thread zu vermeiden) gesperrt werden würde, pop-deaktiviert die Position und die Richtung und dann im Stapel zu entsperren. Während dies zu einem gewissen Grad gearbeitet, umständlich war und gezwungen, fügen Sie neue Daten in jeder Maus, um den Pfad so, dass es einen Pfad vom Anfangspunkt an Ihrem aktuellen Speicherort müsste.

Beim finden Sie sich in einem Multithreadprogramm für einen partiellen Status vornehmen, bis Sie die mit, oder spezielle beginnen, mid-state Informationen hinzufügen Groß-/Kleinschreibung Verhalten oder im Allgemeinen bei etwas, das ist nicht generisch, dem tasking Code und dann ist es Zeit zu überdenken Ihren Entwurf.

Was ich bis dieser Vorgang beendet war, platzieren die aktuellen Pfadinformationen in jeder Maus und dass dieses Teil der Maus Initialisierungsinformationen. Wenn ich einen Zweig Punkt erreicht, ich eine Maus-Datenstruktur erstellt und initialisiert es aus der aktuellen Maus Informationen – wodurch erstellt eine Maus Klon, z. B. links geht, wenn die ursprüngliche nach rechts bewegt. Der Klon enthält die ursprüngliche Speicher. Das einzige, was sich in jeder Maus ist ein Zähler, die protokolliert die Anzahl der erstellten Mäuse – Dies ist wie die Maus eine Farbe zugewiesen werden.

Auch über aktiviert und versucht eine globale Kopie der Labyrinth, die Zustandsinformationen für die einzelnen Zellen enthält und wurde nicht platzieren Sie alle Sperren, um das Schreiben der Zustandsinformationen. Dies war eine Vereinfachung ich als eine Abwägung akzeptiert, eine Maus auf einem Pfad selbst arbeiten. Es prüft immer, ob die Zelle markiert ist, als bereits besucht, bevor er in die Zelle verschoben wird.

Da es keine Sperren, um die globale Zellendaten, ist es möglich, jedoch unwahrscheinlich, zwei Mäusen beides unten einen Pfad zum gleichen Zeitpunkt starten, möglicherweise. Möglicherweise entweder zwar einen Stapel mit doppelten Eintrag oder über einen looped Pfad zum, in der zwei Mäusen ineinander ausgeführt. Ich stimme in jedem Fall die Tatsache Maus möglicherweise nach einem Pfad problemlos ausgeführt werden, kann der Thread unterbrochen erhalten und wenn er es ermittelt, dass einige andere Maus seinen Pfad überschritten hat. In diesem Fall sichert die Maus einfach als wäre es eine Wand erreicht hat da die Maus, die es überschritten erfolgreich einen Pfad folgt. Unterbrochene Maus die Chance verpasst und hat einige zusätzliche Arbeit.

Wenn es noch viele weitere Verarbeitung beteiligt, markieren die Zellen, ich möglicherweise mehr zögern, um die Tatsache akzeptieren, die einige nutzlose Arbeit erledigt abgerufen werden kann. Sperren von gemeinsam genutzten Daten eliminieren bedeutet einfach habe ich den Algorithmus etwas robuster zu machen. Entwerfen Sie in solchen Situationen bedeutet, dass es weniger Platz auf Fehler machen. Die wahrscheinlichste Quelle von Fehlern in Programmen, die multithreaded gehören in der Regel eine Art von Fehler, wie z. B. eine Racebedingung sperren oder Annahmen über, wenn Daten oder Leistungsindikatoren aktualisiert.

Wenn Sie Ihre Daten behandeln, die möglicherweise etwas veraltet und Wiederherstellen von diesen Situationen stabil genug Algorithmen vornehmen können, sind Sie auf dem richtigen Weg zur Herstellung einer stabilen Multithread-Architektur.

Aufgabe Warteschlangen und Abhängigkeiten

Windows Vista werden neue Algorithmen für die Planung und neue primitive Typen, die die zugrunde liegenden Unterstützung für eine Anzahl von Microsoft .NET Framework 4-Features eingeführt. Eines dieser Features ist der Task Parallel Library (TPL), die sehr wenige der häufigeren paralleler Algorithmen wie Fork/Join, parallel für Arbeit stehlen und Aufgabe inlining Programmierung bereitstellt. Wenn Sie in nicht verwaltetem C++ Code können Sie von Intel Threading Building Blocks (TBB) oder Microsoft Parallel Muster Library (PPL) nutzen.

Diese Bibliotheken verfügen über Klassen, die multithreaded programming Aufträgen und Aufgaben unterstützen. Sie verfügen außerdem über viele threadsichere Containerklassen. Diese Klassen getestet und optimiert die Leistung, damit, sofern Sie deep-seated erforderlich, Schreiben Sie eine angepasste Variante aus irgendeinem Grund haben, Sie werden besser mit einigen getestet, robusten Codes.

Da dies ein einführende Artikel über threading und Aufgaben, und Sie möglicherweise von Einblick profitieren in die Funktionsweise von threading Bibliotheken, habe ich meinen eigenen Satz von Wrapper um zwei neue Features in Windows Vista: ThreadPool und SlimReaderWriterLock (SRWLock). Diese sind beide kostengünstige Möglichkeiten des ausführenden Threads Daten sicher über die Situationen, in denen Sie einen Writer und viele Leser haben und die Daten ist nicht in der Regel über einen langen Zeitraum gesperrt. Beachten Sie, dass das Ziel dieses Artikels ist, durchlaufen Sie wie ich einen Threadpool implementieren, der Aufgaben ausgewählt haben – Aufgaben, die Abhängigkeiten aufweisen können. Erläutern Sie die grundlegenden Mechanismen habe ich einige Liberties durch den Code zu verstehen erleichtern übernommen. Der Code funktioniert, aber Sie ist besser, eine der Bibliotheken threading bei jeder echte Implementierung auswählen.

Für meinen Algorithmus Labyrinth möchte die generische multithreading Algorithmen verwendet werden: Aufgaben, die Abhängigkeiten (implementiert mit SRWLock) und einen Taskplaner (mit dem Betriebssystem ThreadPool) haben können. Dies ist der generischste, da im Grunde eine Aufgabe wird einem Bit der Arbeit, die durchgeführt werden muss, und der Taskplaner für die Kommunikation mit dem Betriebssystem sorgt erhalten die Aufgabe in einem Thread ausgeführt. Sie sind generisch, weil es möglich ist, Aufgaben von Code zu erstellen, die ausgeführt werden, und löst es in einem ThreadPool.

Die Herausforderung ist Aufgaben erstellen, die genug Zeit haben, stellen den Aufwand für das Abrufen von Ihnen geplanten überwinden lohnt einnehmen. Wenn Sie einige große monolithischen Vorgänge, die ausgeführt werden müssen haben, dann können Sie einige Threads erstellen und Ausführen des Codes. Andererseits, es gibt viele Anwendungen, in denen Gruppen von Vorgängen, die erforderlich zu erhalten, einige seriell, andere nicht. In einigen Fällen wissen im Voraus Sie wie viel Arbeit erledigt werden muss;in anderen Fällen, insbesondere abrufen oder reagieren auf Benutzereingaben oder einige Kommunikation – Sie sind nur für etwas, die nur gelegentlich erweiterte Verarbeitung erfordern abrufen. Dies wird einfach von der generischen Natur der ThreadPool und seine zugeordneten Vorgangs-Warteschlange verarbeitet.

Anpassen den ThreadPool

Damit Sie genau wissen, wie ein tasking System über den ThreadPool erstellt ich wirklich nur drei der dazugehörigen Schnittstellen verwenden müssen:

CreateThreadpool();
CloseThreadpool();
TrySubmitThreadpoolCallback();

Die ersten beiden sind nur für die Buchhaltung-Funktionen. TrySubmitThreadpoolCallback verwendet im Grunde einen Zeiger auf eine Funktion zum Ausführen sowie einige Kontextvariablen. Rufen Sie diese Funktion wiederholt, um den Threadpool auszuführende Aufgaben zu laden, und es dient diese First in First Out (FIFO) Weise (hier keine Garantien).

Um mit meinen Aufgaben arbeiten zu können, habe ich einen kurzen Wrapper zum ThreadPool, die mir die Anzahl der Threads im Threadpool anpassen kann (siehe Abbildung 3 ). Außerdem habe ich eine Submit-Funktion, die kümmern wird der laufenden Kontextvariablen, die dem Vorgang zugeordnet sind.

Abbildung 3 ThreadPool Wrapper

class ThreadPool {
  PTP_POOL m_Pool;
public:
  static VOID CALLBACK WorkCallback(
    PTP_CALLBACK_INSTANCE instance,
    void* Context);
  ThreadPool(void);
  ~ThreadPool(void);
  
  static unsigned GetHardwareThreadsCount();

  // create thread pool that has optimal 
  // number of threads for current hardware
  bool create() { 
    DWORD tc = GetHardwareThreadsCount(); 
    return create(tc,tc); 
  }
  bool create(
    unsigned int minThreads, 
    unsigned int maxThreads = 0);
  void release();
  bool submit(ITask* pWork);
};

Der interessante Aspekt zu beachten ist, dass Sie normalerweise nur erstellen möchten beliebig viele Softwarethreads als Hardwarethreads vorhanden sind. Dies kann manchmal minus eins sein, wenn Sie einen Hauptthread aus etwas anderes tun. Hinweis Die Anzahl der Threads, die Sie erstellen, hat nichts mit der Größe der Warteschlange Aufgabe tun – es ist durchaus zulässig, dass ein ThreadPool mit vier Threads erstellen und senden Sie Hunderte von Aufgaben. Es ist wahrscheinlich nicht empfehlenswert, jedoch um einen einzelnen seriellen Auftrag und teilen Sie Sie in Tausenden von Aufgaben. Dies ist ein Hinweis darauf, dass Sie zu viele fein des Tasks haben. Wenn Sie sich in diesem Fall, und Sie werden nur haben eine Aufgabe erstellen, deren Aufgabe es ist die nächsten 100 Vorgänge planen – oder wenn Sie eine der tasking Bibliotheken verwenden, erstellen Sie eine Aufgabe Arbeit stehlen, inlining oder follow-on.

Meine Aufgabe-Klasse (Beachten der Großes T, die ich verwenden werde, um meine Aufgabe Wrapperklasse wie in Abbildung 4 kennzeichnen) verfügt über die Möglichkeit, dass hängt von anderen Aufgaben ab. Da der ThreadPool das Betriebssystem diese Fähigkeit besitzt, müssen ich ihn hinzuzufügen. Daher ist ein Task gestartet wird, auf einem Thread ausgeführt, wird als Erstes stellen Sie sicher, dass es keine ausstehenden Abhängigkeiten an. Andernfalls, der Thread wartet auf die SRWLock Ausführung der Aufgabe blockiert wird. Der Task wird nur neu geplant erhalten, wenn die SRWLock freigegeben wird.

Abbildung 4 Task Wrapper

class ITask {
protected:
  vector<ITask*>    m_dependentsList;      // Those waiting for me
  ThreadSafe_Int32  m_dependencysRemaining;// Those I'm waiting for

  // The blocking event if we have dependencies waiting on
  SRWLOCK m_SRWLock; 
  CONDITION_VARIABLE m_Dependencies;

  void SignalDependentsImDone();
  ITask(); 
  virtual ~ITask();

public:  
  void blockIfDependenciesArePending();
  void isDependentUpon(ITask* pTask);

  unsigned int queryNumberDependentsRemaining()

  // A parent Task will call this
  void clearOneDependency();
  virtual void doWork(void*) = 0;
  virtual void* context() = 0;
};

Erneut, mich darauf hinweisen, dass dies ist kein Code würde in einer Anwendung nicht für akademische angezeigt werden soll, aber den Block hier platzieren, können Sie sehen, was genau geschieht. Das Betriebssystem wird Beachten Sie den Block und eine andere Aufgabe zu planen. Schließlich – es sei denn, es ein Programmierfehler ist, blockierte Aufgabe wird die Blockierung aufheben und abrufen, die ausgeführt werden neu berechnet.

Im Allgemeinen ist es nicht sinnvoll, einen Task zu planen, die sofort angehalten werden. Da der ThreadPool-Taskwarteschlange großen und FIFO ist, sollten Sie zum Planen von Tasks, die zunächst keine Abhängigkeiten aufweisen. Wenn ich wurden diese schreiben, für eine optimale Leistung anstelle der Veranschaulichung, würde ich eine Ebene hinzufügen, die nur Vorgänge übermittelt, die keine Abhängigkeiten für den Threadpool hatte. Ich kann sofort mit diesem abgerufen werden, da die blockierte Threads schließlich ausgelagert abgerufen werden. In jedem Fall müssen Sie haben einige threadsicheren Methode der Signalisierung, dass ein Vorgang erfolgt und SRWLocks für diese Situation verwendet werden kann. Integrieren Sie in meiner Klasse Task ist natürlich, statt jeden Fall behandeln spezielle Code schreiben müssen.

Standardmäßig kann ein Task eine beliebige Anzahl von Aufgaben Abhängigkeiten haben. Normalerweise möchten Sie verringern oder beseitigen alle wartenden, wenn, und Sie können mithilfe eines Tools wie Visual Studio Aufgabenliste oder Intel Graphics Leistung Analyzers, Ihnen hilft, diese aufspüren. Die Implementierung, die ich hier vorstellen, ist ein äußerst einfaches tasking System und sollte nicht für Code, der hohen Leistung verwendet werden. Es ist gut geschützten Code für das Abrufen von den Multithread-Fuß frisch, jedoch sollte in Richtung TBB, TPL oder PPL für einen effizienteren Code aussehen.

Der ThreadPool ruft WorkCallback-Funktion, die einen Präfix-Code ausgeführt, die die Datenstruktur der Task abgefragt wird wird, etwa so:

VOID CALLBACK ThreadPool::WorkCallback(
  PTP_CALLBACK_INSTANCE instance, void* pTask) {

  ITask * pCurrentTask = (ITask*) pTask;
  pCurrentTask->blockIfDependenciesArePending( );
  pCurrentTask->doWork(pCurrentTask->context() );
  pCurrentTask->SignalDependentsImDone();
}

Der grundlegende Vorgang ist:

  1. Der ThreadPool lädt die WorkCallback aus seiner internen Taskwarteschlange.
  2. Der Code fragt den Task aus, um festzustellen, ob alle Abhängigkeiten (übergeordnete Abhängigkeiten). Wenn Abhängigkeiten gefunden werden, die blockieren Sie Ausführung.
  3. Sobald keine Abhängigkeiten sind, rufen Sie DoWork, ist die tatsächliche Teil des Task-Codes, der pro Vorgang eindeutig ist.
  4. Deaktivieren Sie bei der Rückgabe von DoWork untergeordnete Abhängigkeiten von diesem Task.

Wichtig zu beachten ist Präambel und PostScript-Code in den Meine ThreadPool-Klasse, die überprüft und löscht Abhängigkeiten in der Aufgabe vorhanden ist. Dieser Code ruft für jeden Thread ausgeführt, aber eine eindeutige Aufgaben zugeordnet. Nach dem Ausführen des Präambel Codes Ruft die tatsächliche Vorgang Arbeit Funktion aufgerufen.

Erstellen einen benutzerdefinierten Task Class Wrapper

Grundlegende Aufgabe eines Vorgangs ist einigen Kontext und einen Funktionszeiger erhalten die Aufgabe, die im Threadpool ausgeführt. Da ich wollte, Aufgaben zu erstellen, die der Abhängigkeiten wurden, benötigte ich Code zum Behandeln der Aufzeichnungen der laufenden Sperren und entsperren Abhängigkeiten (siehe Abbildung 4 ).

Beim Erstellen eine Aufgabe können Sie dann es mitteilen, dass es von anderen Vorgängen abhängig, ist indem Sie einen Zeiger zu der abhängigen Aufgabe. Eine Aufgabe enthält einen Zähler für die Anzahl der Tasks, die darauf warten, sowie ein Array von Zeigern auf Aufgaben, die zum warten.

Bei eine Aufgabe keine Dependants verfügt, wird seine Arbeit-Funktion aufgerufen. Nach der Arbeit-Funktion zurückgegeben wird, durchläuft es die Task-Zeiger im Array ClearOneDependency für jede Klasse, welche verringert die Anzahl der verbleibenden Abhängigkeiten von diesem Vorgang aufrufen. Wenn die Anzahl der Abhängigkeiten auf Null fällt, wird der SRWLock freigegeben Entblockens des Threads, der die Aufgabe wartet auf diese Abhängigkeiten ausgeführt. Der Ausführung des Tasks Thread ruft entsperrt und die Ausführung fortgesetzt.

Dies ist der allgemeine Übersicht darüber, wie ich meine Aufgaben und die ThreadPool-Klasse entworfen. Ich wurde beendet, bis es auf diese Weise entwerfen, da systemeigene Threadpool des Betriebssystems nicht ganz dieses Verhalten und ich wollte Ihnen Code zur Wiedergabe mit, wo Sie im Steuerelement der Abhängigkeit Mechanismen sind. Ursprünglich hatte ich viel komplizierteren als Wrapper für ThreadPool, die eine Warteschlange Priorität enthalten jedoch bewusst, dass ich Dinge unnötig wodurch erschwert wurde und, dass eine einfache untergeordnete-übergeordneten Abhängigkeitsbeziehung war ich brauchte. Wenn Sie einen Blick auf einen Threadplaner anpassen möchten, schauen Sie sich Joe Duffy-Artikel “ erstellen einen benutzerdefinierten Threadpool (Teil 2): Ein Work Queue, stehlen ” tinyurl.com/36k4jcy-.

Ich häufig Code ziemlich defensiv schreiben. Ich häufig einfache Implementierungen zu schreiben, die zu arbeiten, und dann umzugestalten und Funktionalität durch regelmäßige Überprüfungen Weg, um sicherzustellen, dass ich alles bis messed noch nicht erhöhen. Leider ich auch häufig Code zu erstellen, um Verweise auf andere Variablen übergibt, die in einem Multithreadprogramm etwas Schlechtes ist, wenn Sie nicht sorgfältig.

Ich wurde mehr als einmal rückgängig gemacht beim Konvertieren von Code Labyrinth Singlethread-Lösung zu einem multithreaded. Ich musste außerdem durchlaufen und sicherstellen, dass ich war Kopien der Daten übergeben, wenn gab es eine Möglichkeit, die der Wert in einem Thread geändert.

Ich habe versucht auch konservativen werden, beginnen Sie mit einem Singlethread-Version, die nur die aktuellen Maus Pfad gespeichert. Die das Problem der verfolgen noch weitere Daten eingeführt. Wie bereits erwähnt, ich dies durch die ausführenden Klon Mäuse, die Daten für alle Ihre Eltern mussten gelöst. Ich habe auch der mit Prioritäten versehenen ThreadPool-Wrapper und Sperren auf die globalen Labyrinth Zelldaten zu entfernen. Aller Wahrscheinlichkeit eingeführt ich etwas zusätzliche Arbeit, aber ich machte auch viele der Quellen von Fehlern, die erheblich vereinfachen von Mein Code aufgetreten sein könnten.

Der ThreadPool-Wrapper und Task-Klasse hat genau wie vorgesehen funktioniert. Ich verwendete diese Klassen in einigen Komponententests aus, um sicherzustellen, dass Sie das Verhalten wies, das ich erwartet hat. Ich instrumentiert auch mithilfe der Intel Graphics Performance-Analyzers des Multitaskings auf dem Tool, das eine Funktion hat, mit der Sie dynamisch tag-Threads, und untersuchen Sie, die Teile des Codes in einem bestimmten Thread ausgeführt werden. Diese Visualisierung der Threadausführung mich, die überprüfen, ob die Threads ausgeführt wurden, blockieren und einfach neu geplant werden, wie erwartet.

Wenn ich die Mäuse Klone des übergeordneten werden überarbeitet, wurde dies bis erheblich vereinfachen die Aufzeichnungen durch die Simulation ist erforderlich, da jeder Maus, eigenständig wurde beendet. Nur freigegebenen Daten, die ich, dass beendet war das globale Zelle Array angibt, wenn eine Zelle besucht wurde. Ich kann nicht genug betonen, die mit eine gute Visualisierung auf der Terminplanung von Vorgängen wird von größter Wichtigkeit ist.

Mouse-Pool

Ich habe das Problem Labyrinth, da es eine Reihe von Problemen, das dargestellt Sie zuschneiden können, einen Singlethread-Algorithmus beim Konvertieren in einen Multithread. Die größte Überraschung mir war, nachdem bit den bullet und den Algorithmus an, einige der Aufzeichnungen zu beseitigen, ich zum Verwalten versucht hatte, rewrote Algorithmus Labyrinth lösen plötzlich wesentlich einfacher geworden. Geworden, es ist einfacher als das Singlethread-Algorithmus, da gab es keine Notwendigkeit, einem Stapel der Verzweigung Punkte – Sie sind einfach deaktivieren in eine neue Maus erzeugt.

Standardmäßig wurde jeder Maus einen Klon des übergeordneten Objekts, sodass jeder Maus eine geerbte Pfadnachverfolgung bis zu dem Erstellen eines Prozesses. Die Maus nicht wissen, jedoch absichtlich habe ich die Labyrinth Generation Algorithmen, die versuchen, den letzten möglichen Pfad auszuwählen. Keine sinnvollen und vereinfacht werden. Das Testprogramm ermöglicht die Auswahl zwischen einer Anzahl von Labyrinth Generation Algorithmen, angefangen bei des ursprünglichen Algorithmus, die lange Corridors mit gelegentlichen Verzweigungen führt letztendlich zu Dead enden generiert – zu Algorithmen, die sehr branchy mit kurzen Corridors. Mit diesen verschiedenen Mazes angezeigt, kann das unterschiedliche Verhalten der Multithread-Lösung aus der Singlethread-Projektmappe ziemlich drastische sein.

Wenn ich eine Multithread-Methode zur Lösung von des ursprünglichen Labyrinth Algorithmus angewendet, verringert ich die Suche Dauer durch 48 Prozent auf einem 4-CPU-System. Dies ist, da der Algorithmus lange Corridors viel ist, und es gibt nicht viele Verkaufschancen aus zusätzlichen Mäuse erzeugen (siehe Abbildung 5 ).

Figure 5 Solving the Original Long-Maze Algorithm

Abbildung 5 Beheben von der ursprünglichen Long Labyrinth Algorithm

Abbildung 6 zeigt eine Labyrinth mit weitere Zweige. Jetzt sind viel mehr Möglichkeiten zum Abmelden Mäuse erzeugen und diese Suche gleichzeitig. Abbildung 6 zeigt die Multi-Threaded Lösung für diese kurzen Pfad Labyrinth, wo erhalte ich eine Reduzierung der Zeit, eine Lösung mit mehr Vorgänge von 95 Prozent zu finden.

Figure 6 Multiple Mice Make It Easy to Solve the Maze in Much Less Time

Abbildung 6 mehrere Mäuse machen es leicht zu lösen die Labyrinth in wesentlich weniger Zeit

Dies dient nur zur Veranschaulichung, dass einige Probleme zu unterbrechen auseinander als andere mehr amenable sind. Mein Kollege unbedingt darauf hinweisen, dass das Programm Labyrinth konzipiert ist, optisch interessant sein, d. h., Sie können den Fortschritt der Mäuse und über diese Schritte finden Sie unter. Wenn ich interessiert, suchen einfach die Lösung für die Labyrinth in kürzester Zeit, das Rendering und die Mäuse würde werden entkoppelt –, aber das wäre dann nicht als Spaß zu beobachten.

Lose Threads

Eines der größten Probleme, die ich sehen, wenn ich helfen, Leute, die versuchen, Ihre Anwendungen schneller ausgeführt werden, ist eine unverzüglich versuchen multithreading. Mir ist bekannt, dass unverzüglich. Beim Hinzufügen im multithreading, Sie plötzlich in der Komplexität, die meisten Programmierer in einem Bereich verwendet werden nicht verfügen viele Erfahrungen mit einem Layer hinzufügen.

Leider Wenn Sie scheuen von multithreading, Sie lassen einen guten Teil der Rechenleistung unutilized landen.

Ich habe behandelt die Grundlagen der Funktionsweise eines Systems tasking und erhält Sie die Grundlagen für die Vorgehensweise zum Einrichten großer Aufträge in Aufgaben aufteilen. Der aktuelle Ansatz, während Sie gut, ist jedoch nicht die empfohlene Vorgehensweise für das Abrufen der maximalen Leistung über aktuelle und zukünftige Multi-Core-Hardware. Wenn Sie Interesse abrufen weitere Leistungsverbesserungen auf Hardware, die auf Ihre Anwendung ausgeführt werden kann, müssen Sie Ihre Anwendung dies bedenken Architekt.

Am besten bekommen, maximale ist skalierbare Leistung in Ihrer Anwendung, finden am besten an Anforderungen Ihrer Anwendung in verschiedenen Architekturen, die diese Bibliotheken bereitstellen und nutzen einer der vorhandenen parallel Libraries. Nicht verwaltete, in Echtzeit oder leistungskritischen Anwendungen werden in der Regel am besten bedient, mithilfe der bereitgestellten TBB, während verwaltete Anwendungen eine größere Vielfalt von multithreading-Optionen in der .NET Framework-4-Schnittstellen. In beiden Fällen bestimmt wählen Sie diese threading-APIs die allgemeine Struktur der Anwendung und beim Entwerfen der Aufgaben zu arbeiten und gleichzeitig verwendet werden.

In einem zukünftigen Artikel werde ich Implementierungen betrachten, die diese Verfahren nutzen und veranschaulichen das Erstellen von Anwendungen, um diese verschiedenen threading Bibliotheken so, dass Sie Ihre eigenen Implementierungen verwenden entwerfen können.

In keinem Fall sollten verfügen Sie nun über die grundlegende Kenntnisse, um einige grundlegende threading Ansätze zu testen, und Sie einen Blick auf die threading-Bibliotheken zu beginnen, die am besten herausfinden, wie Ihre zukünftigen Anwendungen entwerfen. Beim multithreading kann eine Herausforderung darstellen, mit einem skalierbaren Bibliotheken ist das Gateway auf maximale Leistung der Hardware, aktuelle und zukünftige zu nutzen.

Ron Fosner optimiert seit 20 Jahren Hochleistungsanwendungen und -spiele für Windows und hat allmählich den Bogen raus. Er ist Grafik- und Optimierungsexperte bei Intel und am glücklichsten, wenn alle CPU-Kerne vollends ausgenutzt werden. Sie erreichen ihn unter Ron@directx.com.

Dank an die folgenden technischen Experten für die Überprüfung der in diesem Artikel: Aaron Coday, Zwiebel Granatir and Brad Werth