DE-102013018380-B4 - System und Verfahren zur Kompilierung oder Laufzeitausführung eines datenparallelen Programms mit Aufteilung-Vereinigung mit Funktionsaufrufen in einem Einzelbefehl-Multi-Strang-Prozessor

Abstract

Ein System zur Kompilierung oder Laufzeitausführung eines datenparallelen Programms mit Aufteilung-Vereinigung mit Funktionsaufrufen, mit: einem SIMT Prozessor (100) mit einer Pipeline Steuereinheit (108); einer Partitionseinheit, die ausgebildet ist, Strang-Gruppen des SIMT Prozessors (100) in eine übergeordnete Gruppe und mindestens eine Arbeiter-Gruppe vor dem Kompilieren oder der Laufzeitausführung des datenparallelen Programms aufzuteilen; und einer Strang-Zuordnungseinheit, die mit der Partitionseinheit verbunden und ausgebildet ist, einen der Stränge aus der übergeordneten Gruppe zur Ausführung als übergeordneten Strang zu bestimmen und alle Stränge in der mindestens einen Arbeiter-Gruppe zur Ausführung als Arbeiter-Stränge zu bestimmen vor dem Kompilieren oder der Laufzeitausführung des datenparallelen Programms, wobei der übergeordnete Strang der übergeordneten Strang-Gruppe während einer sequenziellen Phase des datenparallelen Programms auf dem SIMT Prozessor arbeitet, die Arbeiter Stränge der Arbeiter-Gruppe während einer parallelen Phase des datenparallelen Programms auf dem SIMT Prozessor arbeiten, der übergeordnete Strang wartet bis die parallele Phase abgeschlossen ist, andere Stränge der übergeordneten Gruppe während des datenparallelen Programms bleiben untätig, und das System einen gemeinsam genutzten Speicher (110) des SIMT Prozessor konfiguriert, um eine laufende Aufgabe zu identifizieren.

Inventors

• Yuan Lin
• Gautam CHAKRABARTI
• Jaydeep MARATHE
• Okwan Kwon
• Amit Sabne

Assignees

• NVIDIA CORPORATION

Dates

Publication Date

20260507

Application Date

20131104

Priority Date

20121221

Claims (10)

1. Ein System zur Kompilierung oder Laufzeitausführung eines datenparallelen Programms mit Aufteilung-Vereinigung mit Funktionsaufrufen, mit: einem SIMT Prozessor (100) mit einer Pipeline Steuereinheit (108); einer Partitionseinheit, die ausgebildet ist, Strang-Gruppen des SIMT Prozessors (100) in eine übergeordnete Gruppe und mindestens eine Arbeiter-Gruppe vor dem Kompilieren oder der Laufzeitausführung des datenparallelen Programms aufzuteilen; und einer Strang-Zuordnungseinheit, die mit der Partitionseinheit verbunden und ausgebildet ist, einen der Stränge aus der übergeordneten Gruppe zur Ausführung als übergeordneten Strang zu bestimmen und alle Stränge in der mindestens einen Arbeiter-Gruppe zur Ausführung als Arbeiter-Stränge zu bestimmen vor dem Kompilieren oder der Laufzeitausführung des datenparallelen Programms, wobei der übergeordnete Strang der übergeordneten Strang-Gruppe während einer sequenziellen Phase des datenparallelen Programms auf dem SIMT Prozessor arbeitet, die Arbeiter Stränge der Arbeiter-Gruppe während einer parallelen Phase des datenparallelen Programms auf dem SIMT Prozessor arbeiten, der übergeordnete Strang wartet bis die parallele Phase abgeschlossen ist, andere Stränge der übergeordneten Gruppe während des datenparallelen Programms bleiben untätig, und das System einen gemeinsam genutzten Speicher (110) des SIMT Prozessor konfiguriert, um eine laufende Aufgabe zu identifizieren.
2. Das System nach Anspruch 1 , das ferner eine Strang-Disponiereinheit aufweist, die mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, die Pipeline-Steuereinheit eines Einzelbefehl-Multi-Strang-Prozessors zu veranlassen, die Ausführung des übergeordneten Strangs wie folgt zu disponieren: es wird eine Marke zum Verlassen eines Programms auf einen ersten Zustand gesetzt, wenn der übergeordnete Strang mit der Ausführung beginnt; der übergeordnete Strang wird ausgeführt, bis er einen parallelen Bereich oder ein Ende des Programms erreicht; beim Erreichen des parallelen Bereichs wird eine parallele Aufgabe festgelegt, in eine erste Barriere eingetreten, in eine zweite Barriere eingetreten und die Ausführung des übergeordneten Strangs fortgesetzt; und beim Erreichen des Endes wird die Marke zum Verlassen eines Programms auf einen zweiten Zustand gesetzt, in eine Barriere eingetreten und der übergeordnete Strang beendet die Ausführung.
3. Das System nach Anspruch 1 oder 2 , das ferner eine Strang-Disponiereinheit aufweist, die mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine Pipeline-Steuereinheit eines Einzelbefehl-Multi-Strang-Prozessors zu veranlassen, die Ausführung der Arbeiter-Stränge wie folgt zu disponieren: die Arbeiter-Stränge treten in eine erste Barriere ein; die Arbeiter-Stränge beginnen die Ausführung einer parallelen Aufgabe, die von dem übergeordneten Strang festgelegt ist, wenn der übergeordnete Strang einen parallelen Bereich erreicht und der übergeordnete Strang in eine Barriere eintritt; die Arbeiter-Stränge treten in eine zweite Barriere bei Abschluss der parallelen Aufgabe ein; und die Arbeiter-Stränge enden, wenn eine Flagge für das Verlassen eines Programms auf einen zweiten Zustand gesetzt wird und der übergeordnete Strang in eine Barriere eintritt.
4. Das System nach einem der Ansprüche 1 - 3 , das ferner eine Strang-Disponiereinheit umfasst, die mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine Barrierenfunktion der Pipeline-Steuereinheit eines Einzelbefehl-Multi-Strang-Prozessors zur Steuerung der Ausführung und Beendigung der Arbeiter-Stränge zu verwenden.
5. Das System nach einem der Ansprüche 1 - 4 , das ferner einen Funktionsprozessor aufweist, der mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine geklonte Kopie einer Eintrittsfunktion zu erzeugen und die Eintrittsfunktion als eine Nicht-Eintrittsfunktion zu verarbeiten.
6. Das System nach einem der Ansprüche 1 - 5 , das ferner einen Funktionsprozessor aufweist, der mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine Nicht-Eintrittsfunktion zu übersetzen, die ein paralleles Konstrukt aufweist, durch: Erzeugung einer Funktion, die einen Körper des parallelen Konstrukts enthält; und Einfügung von Aufrufen, die in eine Geräte-Laufzeitbibliothek zielen, wenn die Funktion in dem übergeordneten Strang ausgeführt wird.
7. Das System nach einem der Ansprüche 1 - 6 , das ferner einen Funktionsprozessor aufweist, der mit der Aufrufe von äußeren Funktionen unverändert zu übersetzen.
8. Das System nach einem der Ansprüche 1 - 7 , das ferner einen Funktionsprozessor aufweist, der mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine Geräte-Laufzeitbibliothek zu verwenden, die Funktionen bereitstellt, die von kompiliertem Anwender-Code und internen Funktionen aufgerufen werden können.
9. Das System nach einem der Ansprüche 1 - 8 , das ferner einen Funktionsprozessor aufweist, der mit der Strang-Zuordnungseinheit verbunden und ausgebildet ist, eine Austrittsmarke zu verwenden, die in einem gemeinsam benutzten Speicher gespeichert ist und verwendet wird, um dem übergeordneten Strang zu ermöglichen, um den Arbeiter-Strängen mitzuteilen, wann sie ihre Ausführung beenden sollen.
10. Das System nach einem der Ansprüche 1 - 9 , wobei das System ausgebildet ist, einen gemeinsam benutzten Speicher eines Einzelbefehl-Multi-Prozessors zur Kennzeichnung einer aktuellen Aufgabe zu konfigurieren.

Description

TECHNISCHES GEBIET Diese Anmeldung betrifft generell parallele Prozessoren und insbesondere ein System zur Kompilierung oder Laufzeitausführung eines datenparallelen Programms mit Aufteilung-Vereinigung mit Funktionsaufrufen in einem Einzelbefehl-Multi-Strang-(SIMT-) Prozessor. HINTERGRUND Wie der Fachmann auf diesem Gebiet weiß, können Anwendungen oder Programme parallel ausgeführt werden, um ihr Leistungsverhalten zu verbessern. Datenparallele Programme führen den gleichen Prozess gleichzeitig an unterschiedlichen Daten aus. Aufgabenparallele Programme führen unterschiedliche Prozesse gleichzeitig an den gleichen Daten aus. Statische parallele Programme sind Programme mit einem Grad an Parallelität, der vor der Ausführung bestimmt werden kann. Im Gegensatz dazu kann die Parallelität, die von dynamischen parallelen Programmen erreichbar ist, nur ermittelt werden, wenn sie ausgeführt werden. Unabhängig davon, ob das Programm datenparallel oder aufgabenparallel oder statisch oder dynamisch parallel ist, kann es in einer Pipeline bzw. Parallelverarbeitungslinie ausgeführt werden, was häufig der Fall ist für graphische Programme. Ein SIMT-Prozessor ist besonders geschickt bei der Ausführung datenparalleler Programme. Eine Steuereinheit in dem SIMT-Prozessor erzeugt Gruppen aus Strängen zur Ausführung und disponiert diese für die Ausführung, während welcher alle Stränge in der Gruppe den gleichen Befehl gleichzeitig ausführen. In einem speziellen Prozessor hat jede Gruppe oder „Wölbung bzw. Kette“ 32 Stränge, die 32 Ausführungs-Pipelines oder Bahnen in dem SIMT-Prozessor entsprechen. Ein datenparalleles Programm mit Aufteilung-Vereinigung beginnt mit einem Hauptprogramm, das nur einen Strang aufweist. Das Programm ist in dieser Phase in einer sequenziellen Phase oder einem sequenziellen Bereich. Bei einem gewissen Punkt während der Ausführung des Hauptprogramms trifft der Haupt-oder „Master-“ Strang auf eine Sequenz aus parallelen Phasen oder Bereichen. Jeder parallele Bereich hat einen unabhängigen Datensatz und kann von mehreren Strängen gleichzeitig ausgeführt werden. Die Anzahl an gleichzeitigen Aufgaben in jedem parallelen Bereich wird bestimmt, wenn der parallele Bereich beginnt, und sich während des parallelen Bereichs nicht ändert. Wenn ein paralleler Bereich angetroffen wird, führt der Haupt-Strang eine Aufteilung in eine Gruppe aus Strängen (die als Arbeiter-Stränge bezeichnet werden) durch, um die parallelen Bereiche parallel abzuarbeiten. Das Programm tritt dann in den parallelen Bereich ein. Wenn ein Arbeiter-Strang einen neuen parallelen Bereich antrifft, wird der neue parallele Bereich serialisiert, d.h. der parallele Bereich wird von dem eintreffenden Arbeiter-Strang selbst ausgeführt. Der Haupt-Strang wartet, bis der parallele Bereich beendet ist. Beim Austritt aus dem parallelen Bereich vereinigen sich die Arbeiter-Stränge mit dem Haupt-Strang, der dann die Ausführung des Hauptprogramms wieder fortgesetzt, wobei dann das Programm einen sequenziellen Bereich betritt. Die nachfolgende Tabelle 1 gibt ein Beispiel für ein datenparalleles Programm mit Aufteilung-Vereinigung an. Zum Zwecke des Verständnisses der Tabelle 1 und des Restes dieser Offenbarung sind die Begriffe „foo“ und „bar“ willkürliche Namen von Funktionen. Es kann daher eine beliebige Funktion anstelle von „foo“ oder „bar“ verwendet werden. Das Datenparallele Modell mit Aufteilung-Verzweigung wird häufig in der parallelen Programmierung eingesetzt. Beispielsweise verwendet der OpenMP-Standard dieses Modell als ein grundlegendes Strang-Ausführungsmodell. Der OpenACC-Standard verwendet dieses Modell für die Arbeiter-Stränge in einer Gruppe, die als eine „Arbeitsgruppe“ bezeichnet wird. Die US 2007/0 294 512 A1 offenbart ein System zur Auswahl einer Prozessoreinheit in einem parallelen System mit vielen Prozessoren. Die US 2009/0 013 323 A1 offenbart einen Prozessor mit Synchronisatoren, die verschiedene Stränge synchronisieren. Die US 2011/0 265 068 A1 beschreibt ein System das in einer Anwendung Teile identifiziert, die parallel ausgeführt werden können. Es ist eine Aufgabe der Erfindung, die logische Gruppierung von Strängen zu verbessern. ÜBERBLICK Ein Aspekt stellt ein System zur Kompilierung oder Laufzeitausführung eines datenparallelen Programms mit Aufteilung-Vereinigung mit Funktionsaufrufen gemäß Anspruch 1 bereit. In einer Ausführungsform umfasst das System unter anderem: (1) eine Partitionseinheit, die ausgebildet ist, Strang Gruppen in eine übergeordnete Gruppe und mindestens eine Arbeiter-Gruppe zu unterteilen, und (2) eine Strang-Zuweisungseinheit, die mit der Partitionseinheit verbunden und ausgebildet ist, nur einen einzelnen Strang aus der übergeordneten Gruppe zur Ausführung und alle Stränge in der mindestens einen Arbeiter-Gruppe zur Ausführung anzuweisen bzw. zu bestimmen. KURZE BESCHREIBUNG Es wird nun auf die folgenden Beschreibungen in Verbindung mit den begleitenden Zeichnungen verwiesen, in denen:1 eine Blocka