PatentDe  


Dokumentenidentifikation DE10296980T5 07.10.2004
Titel Verfahren und Einrichtung zum Zuweisen eines Thread-Vorrangs bei einem mehrfädigen Prozessor
Anmelder Intel Corporation, Santa Clara, Calif., US
Erfinder Boggs, Darrell, Aloha, Oreg., US;
Sager, David, Portland, Oreg., US;
Upton, Michael, Portland, Oreg., US;
Allen, James, Portland, Oreg., US;
Burns, David, Portland, Oreg., US
Vertreter Zenz, Helber, Hosbach & Partner GbR, 45128 Essen
DE-Aktenzeichen 10296980
Vertragsstaaten AE, AG, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, BZ, CA, CH, CN, CO, CR, CU, CZ, DE, DK, DM, DZ, EC, EE, ES, FI, GB, GD, GE, GH, GM, HR, HU, ID, IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC, LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW, MX, MZ, NO, NZ, OM, PH, PL, PT, RO, RU, SD, SE, SG, SI, SK, SL, TJ, TM, TN, TR, TT, TZ, UA, UG, UZ, VN, YU, ZA, ZM, ZW, AP, EA, EP, OA
WO-Anmeldetag 18.04.2002
PCT-Aktenzeichen PCT/US02/12339
WO-Veröffentlichungsnummer 0003001367
WO-Veröffentlichungsdatum 03.01.2003
Date of publication of WO application in German translation 07.10.2004
Veröffentlichungstag im Patentblatt 07.10.2004
IPC-Hauptklasse G06F 9/38
IPC-Nebenklasse G06F 9/46   

Beschreibung[de]
Hintergrund der Erfindung

Die vorliegende Erfindung betrifft den Betrieb eines Prozessors oder dergleichen. Insbesondere betrifft die vorliegende Erfindung das Zuweisen eines Vorrangs zu einem Thread in einem mehrfädigen (multi-threaded) Prozessor.

Wie es im Stand der Technik bekannt ist, enthält ein Prozessor eine Vielzahl von Untermodulen, von denen jedes an die Ausführung spezieller Aufgaben angepaßt ist. Bei einem bekannten Prozessor umfassen diese Untermodule folgende: einen Befehls-Cache, eine Befehlsabrufeinheit zum Abrufen geeigneter Befehle aus dem Befehls-Cache; Decodierlogik, die den Befehl in ein endgültiges oder ein Zwischenformat decodiert, Mikrooperationslogik, die Zwischenbefehle in ein endgültiges Format zur Ausführung konvertiert; und eine Ausführungseinheit, die Befehle des endgültigen Formats ausführt (entweder bei einigen Beispielen aus der Decodierlogik oder bei anderen aus der Mikrooperationslogik). Hier werden die Befehle des endgültigen Formats als Mikrooperationen bezeichnet.

Von dem Prozessor auszuführender Programmcode kann manchmal in kleinere Komponenten unterteilt werden, die als "Threads" bezeichnet werden. Ein Thread ist eine Serie von Befehlen, deren Ausführung eine gegebene Aufgabe erreicht. Beispielsweise könnte bei einer Videotelefonanwendung der Prozessor aufgerufen werden, einen Code auszuführen, um Videobilddaten sowie Audiodaten zu behandeln. Es könnte separate Codesequenzen geben, deren Ausführung derart gestaltet ist, daß sie jeweils diese Datenarten behandeln. So könnte ein erster Thread Befehle zur Videobilddatenverarbeitung und ein zweiter Thread Befehle zur Audiodatenverarbeitung enthalten. Anders ausgedrückt, ein Thread ist ein selbständiges Programm, dem üblicherweise ein Thread-Identifizierer zugeordnet ist, und während der Ausführung in einer Multi-Threaded-Umgebung kann sein Architekturzustand aufrechterhalten werden, während Befehle von einem anderen Thread ausgeführt werden.

Die Verwendung von mehrfädigen (multi-threaded) Prozessoren wurde im Stand der Technik vorgeschlagen. Bei einem solchen Prozessor kann zwischen der Ausführung von zwei oder mehr Threads umgeschaltet werden. Bei anderen mehrfädigen Prozessoren können die Threads gleichzeitig ausgeführt werden. Bei beiden Prozessoren gibt es keine Abgrenzung zwischen den Threads, wie diese behandelt werden. Insbesondere wird dem Code von einem Thread derselbe Vorrang beziehungsweise dieselbe Priorität gegeben, wie dem Code von einem anderen Thread. Dies könnte zu einem negativen Einfluß auf die Gesamtsystemleistung insbesondere dann führen, wenn die Ausführung kritischen Codes durch die Ausführung nicht-kritischen Codes ausgesetzt oder verlangsamt wird.

Angesichts des oben Ausgeführten gibt es einen Bedarf, einen Vorrang zwischen zwei oder mehr Threads zuzuweisen.

Kurzbeschreibung der Zeichnungen

1 ist eine Blockdarstellung eines Computersystems, das gemäß einem Ausführungsbeispiel der vorliegenden Erfindung betrieben wird.

2 ist eine Blockdarstellung eines Teils eines Prozessors, der in Übereinstimmung mit einem Ausführungsbeispiel der vorliegenden Erfindung konstruiert ist.

3 ist ein Zustandsdiagramm für die Zuweisung eines Thread-Vorrangs gemäß einem Ausführungsbeispiel der vorliegenden Erfindung.

4 ist ein Zustandsdiagramm für das Setzen des Startzählers für Thread0 oder Thread1 gemäß einem Ausführungsbeispiel der vorliegenden Erfindung.

Detaillierte Beschreibung

Es wird auf 1 Bezug genommen, in der eine Blockdarstellung eines Computersystems gezeigt ist, das gemäß einem Ausführungsbeispiel der vorliegenden Erfindung betrieben wird. Bei diesem Beispiel enthält das Computersystem 1 einen Prozessor 3, welcher in der Lage ist, im Speicher 5 gespeicherten Code auszuführen. Bei diesem Beispiel speichert der Speicher 5 Code für verschiedene Threads, wie beispielsweise Code für Thread0 (8), Thread1 (9), etc. Wie es im Stand der Technik bekannt ist, kann der Code für beide Threads Teil einer Benutzeranwendung und des Betriebssystems sein.

Es wird auf 2 Bezug genommen, in der eine Blockdarstellung eines Prozessors (zum Beispiel eines Mikroprozessors, eines digitalen Signalprozessors oder dergleichen) gezeigt ist, der gemäß einem Ausführungsbeispiel der vorliegenden Erfindung betrieben wird. Bei diesem Ausführungsbeispiel ist der Prozessor ein mehrfädiger Prozessor, wobei der Prozessor 10 theoretisch in zwei oder mehr logische Prozessoren unterteilt ist. So wie er hier verwendet wird, bezieht sich der Begriff "Thread" auf eine Befehlscodesequenz. Bei einer Videotelefonanwendung beispielsweise könnte der Prozessor aufgerufen werden, um Befehlscode zum Behandeln von Videobilddaten sowie von Audiodaten auszuführen. Es könnte separate Codesequenzen geben, deren Ausführung zum Behandeln jeder dieser Datenarten ausgebildet ist. So könnte ein erster Thread Befehle für eine Videobilddatenverarbeitung enthalten, und ein zweiter Thread könnte Befehle für eine Audiodatenverarbeitung enthalten. Bei diesem Beispiel gibt es eine oder mehrere Ausführungseinheiten (zum Beispiel einschließend die Ausführungseinheit 41), welche einen oder mehrere Befehle gleichzeitig ausführen können. Der Prozessor 10 kann jedoch als zwei logische Prozessoren behandelt werden, wobei ein erster logischer Prozessor Befehle aus dem ersten Thread und ein zweiter logischer Prozessor Befehle aus dem zweiten Thread ausführt.

Bei diesem Ausführungsbeispiel des Prozessors 10 werden Befehle und/oder Bytes von Daten durch die Abrufeinheit 11 abgerufen und einer Warteschlange 13 zur Verfügung gestellt und als Teil der Thread0-Warteschlange oder der Thread1-Warteschlange gespeichert. Einem Fachmann ist es klar, daß die im Prozessor 10 verwendeten Warteschlangen verwendet werden können, um mehr als zwei Threads zu speichern. Befehle aus den beiden Threads werden an einen Multiplexer (MUX) 15 angelegt, und eine Steuerlogik 17 wird verwendet, um zu steuern, ob Befehle aus dem Thread 0 oder dem Thread 1 an eine Decodiereinheit 21 geliefert werden. Die Decodiereinheit 21 kann einen Befehl in zwei oder mehr Mikrobefehle konvertieren und die Mikrobefehle in die Warteschlange 23 liefern (bei einem RISC(Reduced Instruction Set Code)-Prozessor können sich die Befehle bereits in einem decodierten Format befinden, und die Decodiereinheit 21 konvertiert sie in ein Format zur Ausführung. Die Ausgaben der Warteschlange 23 werden an einen MUX 25 geliefert, welcher Befehle aus dem Thread0 oder dem Thread1 auf der Grundlage des Betriebs einer Steuerlogik 27 an eine Umbenennungs/Zuteilungs-Einheit 31 liefert. Die Umbenennungs/Zuteilungs-Einheit 31 wiederum liefert Befehle an die Warteschlange 33. Ein MUX 35 wählt zwischen der Thread0-Warteschlange und der Thread1-Warteschlange auf der Grundlage des Betriebs der Einplanungssteuerlogik 37 aus, welche beispielsweise Befehle aus Thread0 und Thread1 auf der Grundlage verfügbarer Ressourcen in der Ausführungseinheit 41 auswählen kann. Die Ausgabe des MUX 35 wird an eine Außer-Der-Reihe-Ausführungseinheit 41 bei diesem Ausführungsbeispiel geliefert, welche den Befehl ausführt. Der Befehl wird dann in die Warteschlange 43 gebracht. Die Ausgaben der Warteschlange 43 werden an einen MUX 45 geliefert, welcher Befehle aus Thread 0 und Thread 1 an eine Festschreibeeinheit (Retire Unit) 51 auf der Grundlage des Betriebs der Steuerlogik 47 sendet.

In 2 kann eine Verzweigungsvorhersageschaltung hinzugefügt werden, um die Effizienz des Prozessors 10 zu verbessern. Beispielsweise könnte eine Verzweigungsvorhersageschaltung zur Abrufeinheit 11 hinzugefügt werden. Wie es im Stand der Technik bekannt ist, betrifft eine Verzweigungsvorhersage ein Vorhersagen, ob ein Verzweigungsbefehl (zum Beispiel BNE-Branch if not equal) genommen wird, auf der Grundlage der Vorgeschichte der Ausführungscodesequenzen beispielsweise. Sobald eine Verzweigung vorhergesagt worden ist, kann der nächste Befehl in die "Pipeline" geladen werden (zum Beispiel die Einheiten, die zur Ausführungseinheit 41 hinführen), so daß dann, wenn die Verzweigung als genommen vorhergesagt wird, die richtigen Befehle sofort für die Ausführungseinheit verfügbar sind. Wenn die Verzweigungsvorhersage falsch ist, dann sind die Befehle in der Pipeline nicht richtig und müssen hinausgespült werden, wobei die richtigen Befehle in die Pipeline geladen werden.

Bei einem Beispiel eines mehrfädigen (multi-threaded) Prozessors können zwei Threads parallel verarbeitet werden. Unter Berücksichtigung der hier angegebenen Lehren kann die vorliegende Erfindung auf drei oder mehr Threads, die parallel verarbeitet werden, ausgedehnt werden. Bei diesem Ausführungsbeispiel schließt der Begriff "parallel" eine gleichzeitige und/oder sukzessive Verarbeitung/Ausführung von Befehlen ein. Hier wird der Thread-Vorrang verwendet, um zu bestimmen, welcher Thread die Verwendung geteilter Ressourcen erlangt, wenn beide Threads dieselben Ressourcen gleichzeitig verwenden müssen. Der Thread-Vorrang könnte durch ein oder mehrere Signale gekennzeichnet werden, die in einem Speicherbereich 4 in dem Prozessor 10 (1) gespeichert werden. Beispielsweise würden Thread0Priority und Thread1Priority kennzeichnen, welcher der beiden Threads (Thread0 oder Thread1) den Vorrang gegenüber dem anderen aufweist. Bei einem Beispiel hat dann, wenn beide Signale ausgeschaltet sind, keiner der Threads einen Vorrang gegenüber dem anderen. Darüber hinaus können drei "Zähler" zur Verfügung gestellt werden, um die Zuweisung des Thread-Vorrangs zu unterstützen. Bei 2 könnten diese Zähler als Teil der Retire-Einheit 51 zur Verfügung gestellt werden. Zunächst wird ein Vorrang-Zähler (Precedence Counter) 52 zur Verfügung gestellt, welcher auf einen (unten beschriebenen) Anfangswert gesetzt wird – und bei diesem Ausführungsbeispiel – auf 0 herunterzählt. Wenn der Vorrang-Zähler 52 abgelaufen ist (das heißt 0 erreicht), ist dies eine Anzeige an den Prozessor 10, daß der Vorrang von dem Thread, der den Vorrang hat, auf den anderen Thread verschoben werden sollte. Ein Thread0-Startzähler 53 und ein Thread1-Startzähler 55 werden außerdem zur Verfügung gestellt, welche einen wert speichern, der verwendet wird, um den Anfangswert des Vorrang-Zählers (unten beschrieben) zu setzen.

Gemäß Ausführungsbeispielen der vorliegenden Erfindung wird der Thread-Vorrang-Zähler so eingestellt, daß er ein geeignet dimensioniertes Zeitfenster auf der Grundlage des Voranschreitens eines Threads zur Verfügung stellt. Beispielsweise könnte das Voranschreiten des Threads auf der Grundlage der Anzahl der Mikrooperationen basieren, die festgeschrieben (retired) werden. Wenn der Thread-Vorrang-Zähler gesetzt wird (zum Beispiel nachdem er abgelaufen ist), kann er mit einem Wert neu geladen werden, der gleich einem mehrfachen des Werts (bis zu einem vorgegebenen Maximum) aus dem dem Thread, der demnächst den Vorrang haben wird, zugeordneten Startzähler ist. Demzufolge sollte der Startzähler einen Minimalwert von 1 haben. Wenn somit eine Mikrooperation durch die Retire-Einheit 51 festgeschrieben wird, kann der Startzähler für diesen Thread auf 1 gesetzt werden, so daß dann, wenn er erneut den Thread-Vorrang erlangt, der Thread-Vorrang-Zähler auf eine relativ geringe Zahl gesetzt werden wird. Wenn während der Zeit, in der ein Thread einen Vorrang hat, der Thread-Vorrang-Zähler abläuft und der Thread nicht in der Lage war, eine Mikrooperation während dieses Zeitfensters festzuschreiben, wird der Startzähler um einen Wert (beispielsweise 1) inkrementiert, so daß beim nächsten Mal, wenn der Thread den Vorrang hat, er mehr Zeit haben wird, um wenigstens eine Mikrooperation festzuschreiben (retire).

Die Verwendung dieses Verfahrens zum Zuweisen eines Vorrangs hat wenigstens zwei Nachteile. Zunächst gibt es die Möglichkeit, daß ein Thread weiterhin einen Thread-Vorrang hat, selbst wenn er Mikrooperationen festschreibt, während der andere Thread nicht in der Lage ist, Mikrooperationen während seiner Thread-Vorrang-Zeitfenster festzuschreiben. Wenn beispielsweise Thread0 1000 aufeinanderfolgende Divisionsoperationen und ein großes Thread-Vorrang-Fenster enthält, während Thread1 einen Divisionsbefehl enthält, könnte Thread1 blockiert sein, bis die Ausführung von Thread0 die 1000 Divisionsoperationen abschließt oder bis das Thread-Vorrang-Zeitfenster endet. Bei diesem Beispiel basiert das Thread-Vorrang-Zeitfenster auf der Zeitdauer, die der Thread-Vorrang-Zähler benötigt, um abzulaufen, nachdem er gesetzt worden ist. Wenn zweitens ein Thread bezüglich der Befehle "ausgehungert" wird (das heißt Ressourcen für die Ausführung von Mikrooperationen verfügbar sind, aber das Abrufen von Befehlen eingeschränkt ist), wenn dieser Thread den Vorrang erlangt, so kann die für den Thread-Vorrang-Zähler verfügbar gemachte Zeit möglicherweise nicht ausreichend sein, um das Abrufen eines Befehls zu ermöglichen. Dies ist beispielsweise dann zu erkennen, wenn ein Seiten-Fehlversuch-Behandler oder PMH (Page Miss Handler) verwendet wird, welcher Datenübersetzungsnachschlagepuffer und Befehlsübersetzungsnachschlagepuffer und Seiten- und Cachezeilenbegrenzungsangelegenheiten behandelt. In einem solchen Fall kann es sein, daß der PMH wegen eines TLB-Fehlversuchs schnell Befehle abrufen muß, aber nicht in der Lage ist, dies auszuführen. Demzufolge muß die Inkrementierung des Startzählers für diesen Thread mehrere Male ausgeführt werden, bevor die von dem Thread-Vorrang-Zähler zur Verfügung gestellte sich ergebende Zeit ausreichend ist, um das Abrufen von Befehlen zu ermöglichen (welche schließlich zu der Ausführung und dem Festschreiben von Mikrobefehlen für diesen Thread führen würde). Somit geht jedesmal dann, wenn die Ausführung von Thread1 versucht wird und keine Befehle laden kann, Verarbeitungszeit für Thread0 verloren, und die Verarbeitungszeit für den Befehlsladeausfall geht ebenso verloren.

Gemäß einem Ausführungsbeispiel der vorliegenden Erfindung werden ein System und ein Verfahren angegeben, welche die Leistungsfähigkeit eines mehrfädigen Prozessors über die Zuteilung eines Thread-Vorrangs verbessern. Es wird auf 3 Bezug genommen, in der ein Zustandsdiagramm für das Zuweisen eines Thread-Vorrangs gemäß einem Ausführungsbeispiel der vorliegenden Erfindung gezeigt ist. Im Zustand 61 verweist der Thread-Vorrang auf dem ersten Thread, Thread0. Der Thread-Vorrang-Zähler wird bei diesem Ausführungsbeispiel in Übereinstimmung mit einem Systemtakt für den Prozessor dekrementiert 63. Wie es durch Block 65 angezeigt ist, ändert sich der Zustand vom Zustand 61 in den Zustand 67, wenn eine der folgenden Bedingungen erfüllt wird:

  • 1. Der Thread-Vorrang-Zähler hat 0 erreicht;
  • 2. Thread0 schreibt eine Mikrooperation fest;
  • 3. Es gibt keine Anzeige einer bevorstehenden befehlsseitigen (Iside) Aushungerung für Thread0 mehr.

Iside-Aushungerung liegt dann vor, wenn ein Thread keine Befehle abrufen kann, weil der andere Thread oder die anderen Threads ihn effektiv derart blockiert, daß er dies nicht ausführen kann. Hier ist eine Anzeige einer bevorstehenden Iside-Aushungerung eine Anzeige, daß eine solche Situation für einen Thread herannahen könnte. Eine Anzeige einer bevorstehenden Iside-Aushungerung könnte über die Überwachung eines oder mehrere Zustände oder Bedingungen vorweggenommen werden. Bei einem Ausführungsbeispiel können die Bedingungen eine oder mehrere der folgenden einschließen:

  • 1. Der Prozessor ist in einem Multi-Threaded-Verarbeitungsmodus im Unterschied zu einem Einzel-Thread-Verarbeitungsmodus und mehr als ein Thread ist aktiv.
  • 2. Der gerade betrachtet Thread weist keine Befehle in der Ausführungspipeline auf (zum Beispiel gibt es keine Befehle, die am MUX 35 darauf warten, daß die Einplanungssteuerlogik 37 bewirkt, daß Mikrooperationen für diesen Zweck an die Ausführungseinheit 41 (2) weitergeleitet werden).
  • 3. Die Ausgabe neuer Befehle in die Ausführungs-Pipeline wird nicht blockiert, weil der gerade betrachtete Thread eine benötigte Ressource gefüllt hat. Bei diesem Ausführungsbeispiel schließt die Ausführungspipeline die Verarbeitung von Befehlen aus dem MUX 35 über die Ausführungseinheit ein. Beispielsweise könnte die Ausführungseinheit 41 einen Speicher-Puffer für den aktuellen Thread enthalten, der mit Speicher-Befehlen gefüllt wird. In einem solchen Fall wird die Verarbeitung des Threads nicht notwendigerweise negativ beeinflußt durch das Fehlen des Befehlsabrufens, wohl aber durch die Verzögerung bei der Ausführung von Speicher-Befehlen.
  • 4. Einem Thread, der nicht der gerade betrachtet ist, wurde kein voller oder exklusiver Zugriff auf die Prozessormodule gegeben. Mit anderen Worten, diese Bedingung ist nicht erfüllt, wenn einem anderen Thread ein voller oder exklusiver Zugriff auf Prozessormodule gegeben worden ist. In einer solchen Situation wäre irgendeine Befehlsaushungerung auf der Seite des gerade betrachteten Threads beabsichtigt.
  • 5. Der gerade betrachtete Thread befindet sich in einem Zustand, in dem er versucht, Befehle abzurufen. Beispielsweise enthalten viele Prozessoren, einschließlich derjenigen, die von der Intel Cooperation (Santa Clara, Californien) hergestellt werden, ein "Stoppe-Takt"-Pin. Ein Anlegen eines Signals an dieses Pin führt dazu, daß der Prozessor seine Ressourcen ausräumt. In diesem Fall können sämtliche Ressourcen frei von ausführbaren Befehlen für den betrachteten Thread sein. Dementsprechend würde das Fehlen des Befehlsabrufens in einem solchen Fall nicht als Aushungerung angesehen werden. Ein Umschalten aus einem Multi-Thread-Modus einen Einzel-Thread-Modus ist ein weiteres Beispiel, bei welchem eine Befehlsaushungerung nicht als ein Problem angesehen werden sollte.
  • 6. Ein Sicherungsprotokoll einer höheren Leistungsfähigkeit ist nicht aktiv. Wenn es beispielsweise tatsächlich ein anderes Protokoll gibt, um den Vorrang von einem Thread zu einem anderen umzuschalten, so kann das Abarbeiten dieses Protokolls mit einer Befehlsaushungerungsbehandlung gemäß der vorliegenden Erfindung einen negativen Einfluß auf die Prozessorleistung haben.
  • 7. Ein Befehlsaushungerungs-Freigabebit ist gesetzt (das heißt das Bit kann von einer Steuerlogik gesetzt werden, um Iside-Aushungerungs/Erfassungs/Auflösung auszuschalten.
  • 8. Der betrachtete Thread wartet nicht auf einen Befehlsabruf, der das Chip verlassen hat (zum Beispiel vom Prozessor weg, wie beispielsweise Hauptspeicher).

Wenn bei diesem Ausführungsbeispiel sämtliche überwachten Bedingungen erfüllt sind, dann gibt es eine Anzeige einer bevorstehenden Iside-Aushungerung für Thread0. Obwohl acht Bedingungen oben präsentiert wurden, kann die vorliegende Erfindung auf zusätzliche Bedingungen oder eine geringeren Anzahl von Bedingungen ausgedehnt werden. Beispielsweise könnte die Anzeige einer bevorstehenden Iside-Aushungerung lediglich darauf basieren, daß die obigen Bedingungen 1, 2 und 5 wahr sind.

Im Block 67 wird der Thread-Vorrang von Thread0 zu Thread1 gewechselt. Der Thread-Vorrang-Zähler wird mit einem Wert von 16 multipliziert mit dem Wert in einem Startzähler eines zweiten Threads (Thread1) geladen. Zu diesem Zeitpunkt werden die Thread-Vorrangsignale so umgeschaltet, daß sie anzeigen, daß Thread1 den Vorrang über Thread0 hat. Die Steuerung fährt dann zu Block 69 fort, wo Thread1 den Vorrang hat und der Thread-Vorrang-Zähler in Übereinstimmung mit einem Systemtakt dekrementiert wird (Block 70). Wie es durch die Bedingungen in Block 71 angezeigt ist, ändert sich der Zustand von Block 69 zu Block 73, wenn eine oder mehrere Bedingungen erfüllt sind. Bei diesem Ausführungsbeispiel ändert sich der Zustand, wenn irgendeine der folgenden drei Bedingungen erfüllt ist.

  • 1. Der Thread-Vorrang-Zähler erreicht 0;
  • 2. Thread0 schreibt eine Mikrooperation fest (retires);
  • 3. es gibt keine Anzeige einer bevorstehenden Iside (Instruction Side)-Aushungerung für Thread1.

Im Zustand 73 wird der Thread-Vorrang-Zähler mit 16 multipliziert mit dem wert im Startzähler des Thread1 geladen, und die richtigen Thread-Vorrang-Signale werden so umgeschaltet, daß sie anzeigen, daß Thread0 Vorrang hat. Die Steuerung kehrt dann zum Block 61 zurück. Beim Rücksetzen des Prozessors (Block 75) werden die Aktionen des Zustands 73 unternommen, und Thread0 wird bei diesem Ausführungsbeispiel der Vorrang gegeben.

Es wird auf 4 Bezug genommen, in der ein Zustandsdiagramm zum Setzen des Startzählers eines der Threads0 und 1 gemäß einem Ausführungsbeispiel der vorliegenden Erfindung gezeigt ist. Beim Rücksetzen (Block 80) geht die Steuerung zum Block 81, wo der Wert für den Startzähler auf 1 gesetzt wird.

Um vom Block 81 zum Block 82 zu gelangen, sollte eine von zwei Bedingungen (Block 85) erfüllt sein:

  • 1. Der Thread-Vorrang wurde zu einem anderen Thread umgeschaltet, bevor der gegenwärtige Thread in der Lage war, eine Mikrooperation festzuschreiben (to retire);
  • 2. es gibt eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den aktuellen Thread.

Im Block 82 wird der Wert in dem Startzähler geometrisch modifiziert (indem beispielsweise ein binäres 1-Bit hineingeschoben und sämtliche Bits nach links verschoben werden). Beispielsweise würde ein Wert 1 zu einem Wert 3 gemacht werden, ein Wert 3 würde zu einem Wert 7 gemacht werden und ein Wert 2n–1 würde zu einem Wert 2n+1–1 gemacht werden (wobei n > 0 ist). Die Steuerung verbleibt beim Zustand 82, während es eine Anzeige einer bevorstehenden Iside-Aushungerung gibt (Block 86). Bei diesem Ausführungsbeispiel wird bei jedem Systemtakt der Wert in dem Startzähler inkrementiert, wie es oben erörtert worden ist, bis ein Maximalwert erreicht ist. Die Steuerung bewegt sich zurück zum Block 81, wenn eine der folgenden Bedingungen auftritt (Block 84):

  • 1. Eine Mikrooperation für diesen Thread wird festgeschrieben;
  • 2. es gibt keine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den Thread.

Die Steuerung geht vom Block 82 zum Block 83, wenn "weitere Bedingungen" nicht erfüllt sind. Bei diesem Ausführungsbeispiel geht dann, wenn die Steuerung vom Block 81 zum Block 82 ging, weil der Thread-Vorrang zu einem anderen Thread umgeschaltet wurde, bevor der aktuelle Thread in der Lage war, eine Mikrooperation festzuschreiben, die Steuerung vom Block 82 zu 83, wenn folgende "weitere" Bedingungen nicht erfüllt sind:

  • 1. Der betrachtete Thread hat eine Mikrooperation festgeschrieben; und
  • 2. das Thread-Vorrangsignal wurde nicht zu dem betrachteten Thread umgeschaltet (Block 87). Mit anderen Worten, der Wert in dem Zähler soll bei demselben Wert gehalten werden, wenn der Thread keine Mikrooperation festgeschrieben hat und dieser Thread den Thread-Vorrang hat. Die Steuerung bleibt bei Block 83, wo der aktuelle Wert in dem Startzähler auf dem gleichen Wert gehalten wird, solange die anderen Bedingungen nicht erfüllt sind (Block 88). Die Steuerung kehrt zum Block 82 zurück, wenn eine der folgenden Bedingungen erfüllt ist (Block 89):
  • 1. Der Thread-Vorrang schaltete aus dem aktuellen Thread zu einem anderen Thread um, bevor eine Mikrooperation festgeschrieben werden konnte;
  • 2. es gibt eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den Thread.

Die Steuerung geht vom Block 83 zum Block 81, wenn der Thread eine Mikrooperation festschreibt (retires) (Block 90). Schließlich geht die Steuerung vom Block 81 zum Block 83, wenn weitere Bedingungen nicht erfüllt sind (Block 91). Unter Verwendung des Verfahrens und Systems gemäß der vorliegenden Erfindung können die oben genannten Probleme vermieden werden. Die Implementierung der Ablaufdiagramme der 3 und 4 können durch eine geeignet konfigurierte Steuerlogik ausgeführt werden (die beispielsweise die Steuerlogik 37 in 2 einschließt). Alternativ kann die Steuerlogik ein Untermodul des Prozessors 10 sein, der Befehle ausführt, um die Ablaufdiagramme der 3 und 4 zu implementieren.

Obwohl verschiedene Ausführungsbeispiele speziell hier veranschaulicht und beschrieben worden sind, ist es klar, daß Modifikationen und Variationen der vorliegenden Erfindung durch die obigen Lehren abgedeckt sind und innerhalb des Umfangs der beigefügten Ansprüche liegen, ohne vom Geist und beabsichtigten Umfang der Erfindung abzuweichen.

ZUSAMMENFASSUNG

Bei einem mehrfädigen Prozessor werden Thread-Vorrang-Variablen in einem Speicher eingerichtet. Die aktuelle Zuweisung eines Thread-Vorrangs wird auf dem Ablauf eines Thread-Vorrang-Zählers gestützt. Um die Wirksamkeit des Thread-Vorrang-Zählers weiter zu vergrößern, werden jedem Thread Startzähler zugeordnet, die als Multiplikatoren für den in dem Thread-Vorrang-Zähler zu verwendenden Wert dienen. Der Wert in den Startzählern wird derart manipuliert, daß ein Thread daran gehindert wird, einen übermäßigen Vorrang bei den Ressourcen des mehrfädigen Prozessors zu erlangen.


Anspruch[de]
  1. Ein Verfahren zum Zuweisen eines Thread-Vorrangs in einem Multi-Threaded-Prozessor für wenigstens einen ersten und einen zweiten Thread, umfassend:

    Zuweisen des Vorrangs zu dem ersten Thread;

    Laden eines vorläufigen Werts in einen Thread-Vorrang-Zähler; und

    Zuweisen den Vorrangs zu dem zweiten Thread in Erwiderung des Ablaufs des Thread-Vorrang-Zählers.
  2. Das Verfahren nach Anspruch 1, wobei der vorläufiger Wert auf einem in einem ersten Startzähler, der dem ersten Thread zugeordnet ist, gespeicherten Wert basiert.
  3. Das Verfahren nach Anspruch 2, ferner umfassend:

    Bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt; und

    Inkrementieren eines in dem ersten Startzähler gespeicherten Werts in Erwiderung einer Anzeige einer bevorstehenden befehlsseiten-Aushungerung für den ersten Thread.
  4. Das Verfahren nach Anspruch 3, wobei das Bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, ein Bestimmen einschließt, ob eine Mehrzahl von Bedingungen erfüllt sind, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  5. Das Verfahren nach Anspruch 4, wobei dann, wenn der in dem ersten Startzähler gespeicherte Wert inkrementiert wird, der Wert geometrisch inkrementiert wird.
  6. Das Verfahren nach Anspruch 5, wobei der wert geometrisch inkrementiert wird, indem durch Links-Schieben ein binäres 1-Bit in den Wert hineingeschoben wird.
  7. Ein Verfahren zum Zuweisen eines Thread-Vorrangs in einem Multi-Threaded-Prozessor zum Behandeln der Verarbeitung wenigstens eines ersten und eines zweiten Threads, umfassend:

    Zuweisen des Vorrangs zu dem ersten Thread; und

    Zuweisen des Vorrangs zu dem zweiten Thread, wenn eine einer Mehrzahl von Bedingungen wahr ist, wobei die Bedingungen einschließen,

    ob die Verarbeitung des ersten Threads einen Befehl aus dem ersten Thread festschreibt (retires); und

    ob es keine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt.
  8. Das Verfahren nach Anspruch 7, wobei die Anzeige der bevorstehenden befehlsseitigen Aushungerung für den ersten Thread einschließt, daß eine Mehrzahl von Bedingungen wahr sind, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  9. Ein Prozessor zum Behandeln einer parallelen Verarbeitung wenigstens eines ersten und zweiten Threads, aufweisend:

    Steuerlogik zum Zuweisen eines Vorrangs zu dem ersten oder dem zweiten Thread;

    einen mit der Steuerlogik gekoppelten Thread-Vorrang-Zähler, wobei der Vorrang dem zweiten Thread zugewiesen wird, nachdem der Thread-Vorrang-Zähler abläuft.
  10. Der Prozessor nach Anspruch 9, wobei ein vorläufiger Wert für den Thread-Vorrang-Zähler auf einem in einem ersten Startzähler, der dem ersten Thread zugeordnet ist, gespeicherten Wert basiert.
  11. Der Prozessor nach Anspruch 10, wobei die Steuerlogik dazu dient, zu bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, und einen in dem ersten Startzähler gespeicherten Wert zu inkrementieren, wenn es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt.
  12. Der Prozessor nach Anspruch 11, wobei die Steuerlogik dazu dient zu bestimmen, daß es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, indem bestimmt wird, ob eine Mehrzahl von Bedingungen wahr sind, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  13. Der Prozessor nach Anspruch 12, wobei die Steuerlogik dazu dient, den in dem ersten Startzähler gespeicherten Wert geometrisch zu inkrementieren.
  14. Der Prozessor nach Anspruch 13, wobei der Wert geometrisch inkrementiert werden soll, indem durch Links-Schieben ein binäres 1-Bit in den Wert hineingeschoben wird.
  15. Ein Prozessor zum Behandeln einer parallelen Verarbeitung wenigstens eines ersten und eines zweiten Threads, umfassend:

    eine Steuerlogik zum Zuweisen eines Vorrangs zu dem ersten Thread und zum Zuweisen eines Vorrangs zu dem zweiten Thread in Erwiderung dessen, daß eine einer Mehrzahl von Bedingungen wahr ist, wobei die Bedingungen einschließen,

    ob die Verarbeitung des ersten Threads einen Befehl aus dem ersten Thread festschreibt (retires); und

    ob es keine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt.
  16. Der Prozessor nach Anspruch 15, wobei die Anzeige der bevorstehenden befehlsseitigen Aushungerung für den ersten Thread einschließt, daß eine Mehrzahl von Bedingungen wahr sind, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  17. Ein Computersystem zum Behandeln einer parallelen Verarbeitung wenigstens eines ersten und eines zweiten Threads, aufweisend:

    einen Speicher zum Speichern von Befehlen für den ersten und den zweiten Thread;

    einen Prozessor, enthaltend:

    eine mit dem Speicher gekoppelte Steuerlogik zum Zuweisen eines Vorrangs zwischen dem ersten und dem zweiten Thread;

    einen mit der Steuerlogik gekoppelten Thread-Vorrang-Zähler, wobei der Vorrang dem zweiten Thread zugewiesen wird, wenn der Thread-Vorrang-Zähler abgelaufen ist.
  18. Das Computersystem nach Anspruch 17, wobei ein vorläufiger Wert für den Thread-Vorrang-Zähler auf einem in einem ersten Startzähler, der dem ersten Thread zugeordnet ist, gespeicherten Wert basiert.
  19. Das Computersystem nach Anspruch 18, wobei die Steuerlogik dazu dient, zu bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, und einen in dem ersten Startzähler gespeicherten Wert zu inkrementieren, wenn es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt.
  20. Das Computersystem nach Anspruch 19, wobei die Steuerlogik dazu dient, zu bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, in dem bestimmt wird, ob eine Mehrzahl von Bedingungen wahr sind, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  21. Das Computersystem nach Anspruch 20, wobei die Steuerlogik dazu dient, den in dem ersten Startzähler gespeicherten Wert geometrisch zu inkrementieren.
  22. Das Computersystem nach Anspruch 21, wobei der Wert geometrisch inkrementiert wird, indem durch Links-Schieben ein binäres 1-Bit in den Wert geschoben wird.
  23. Ein Computersystem zum Behandeln einer parallelen Verarbeitung wenigstens eines ersten und eines zweiten Threads, aufweisend:

    einen Speicher zum Speichern von Befehlen für den ersten

    und den zweiten Thread;

    einen Prozessor, enthaltend:

    eine Steuerlogik zum Zuweisen eines Vorrangs zu dem ersten Thread und zum Zuweisen eines Vorrangs zu dem zweiten Thread in Erwiderung dessen, daß eine einer Mehrzahl von Bedingungen wahr ist, wobei die Bedingungen einschließen,

    ob die Verarbeitung des ersten Threads einen Befehl aus dem ersten Thread festschreibt (retires); und

    ob es keine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt.
  24. Das Computersystem nach Anspruch 23, wobei die Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread einschließt, daß eine Mehrzahl von Bedingungen wahr ist, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  25. Ein Satz von sich in einem Speichermedium aufhaltenden Befehlen, wobei der Satz von Befehlen in der Lage ist, von einem Prozessor ausgeführt zu werden, um die parallele Verarbeitung wenigstens eines ersten und eines zweiten Threads zu behandeln und einen Thread-Vorrang zuzuweisen, umfassend:

    Zuweisen eines Vorrangs zu dem ersten Thread;

    Laden eines vorläufigen Werts in einen Thread-Vorrang-Zähler; und

    Zuweisen des Vorrangs zu dem zweiten Thread, nachdem der Thread-Vorrang-Zähler abgelaufen ist.
  26. Der Satz von Befehlen nach Anspruch 25, wobei der vorläufige Wert auf einem in einem ersten Startzähler, der dem ersten Thread zugeordnet ist, gespeicherten Wert basiert.
  27. Der Satz von Befehlen nach Anspruch 26, wobei das Verfahren ferner einschließt:

    Bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt; und

    Inkrementieren eines in dem ersten Startzähler gespeicherten Werts in Erwiderung einer Anzeige der bevorstehenden befehlsseitigen Aushungerung für den ersten Thread.
  28. Der Satz von Befehlen nach Anspruch 27, wobei das Bestimmen, ob es eine Anzeige einer bevorstehenden befehlsseitigen Aushungerung für den ersten Thread gibt, ein Bestimmen einschließt, ob eine Mehrzahl von Bedingungen wahr ist, wobei die Bedingungen einschließen,

    ob der Prozessor in einem Multi-Threaded-Verarbeitungsmodus betrieben wird;

    ob der erste Thread keine Befehle in einer Ausführungspipeline des Prozessors hat; und

    ob der erste Thread versucht, Befehle aus einem Speicher abzurufen.
  29. Der Satz von Befehlen nach Anspruch 28, wobei dann, wenn der in dem ersten Startzähler gespeicherte Wert inkrementiert wird, der Wert geometrisch inkrementiert wird.
  30. Der Satz von Befehlen nach Anspruch 29, wobei der Wert geometrisch inkrementiert wird, indem durch Links-Schieben ein binäres 1-Bit in den Wert hineingeschoben wird.
Es folgen 4 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com