DE3752059T2

DE3752059T2 - Ereignisgesteuertes Exekutivprogramm

Info

Publication number: DE3752059T2
Application number: DE3752059T
Authority: DE
Inventors: John Cheetham; Robert Edward Collins; Smith Cornwell; Bhalchandra Ramchanda Tulpule
Original assignee: United Technologies Corp
Current assignee: RTX Corp
Priority date: 1986-10-29
Filing date: 1987-10-26
Publication date: 1997-08-14
Anticipated expiration: 2007-10-27
Also published as: EP0274339A2; EP0274339B1; DE3752059D1; EP0274339A3; JPS63184841A

Description

Die Erfindung bezieht sich auf ereignisgesteuerte Exekutivprogramme für Signalprozessoren.
In den letzten Jahren hat es einen Anstieg in dem Bedarf an digitalen Echtzeitcomputersystemen hoher Leistung gegeben, die in der Lage sind, komplexe Steuerprobleme zu lösen, welche einen hohen. Durchsatz verlangen. Die Entwerfer von digitalen Computersystemen hoher Leistung haben auf Multiprozessorarchitekturen wie systolische Prozessormatrizensysteme, zeitverschachtelt arbeitende Systeme oder Multiprozessornetze zurückgegriffen, um zu versuchen, den Bedarf zu decken. In den meisten dieser Systeme teilen sich die Matrizen von Prozessoren in die Gesamtarbeitslast. Jeder Prozessor führt dieselben Sätze von Aufgaben aus und arbeitet mit den entsprechenden Datensätzen unter der Leitung einer Systeinsteuereinheit. In vielen Systemen wie z.B. einem Netz von Prozessoren steuert jedes Verarbeitungselement seine eigenen internen Daten, arbeitet mit seinen eigenen internen Daten und verkehrt mit anderen Prozessoren für Daten- und Ausführungsfluß- sowie Steuerzwecke.
In den meisten digitalen Echtzeitmultiprozessorsystemen gibt es üblicherweise einen konkurrierenden Bedarf an einer Minimierung der gesamten Rechenzeitverzögerung. Die Rechenzeitverzägerung hängt in einem Multiprozessorsystem von den sich im schlimmsten Fall ergebenden kritischen Pfadaufgabenzeiten in den Prozessoren sowie von den Datenhandhabungsverzögerungen der Prozessoren untereinander ab. Der Bedarf an einer Minimierung der Transportzeitverzögerung drückt sich deshalb in einem Bedarf an einem Betriebssystem oder einem Aufgabenexekutivprogramm aus, das viele Aufgaben wirksam erfüllen kann, und zwar sowohl innerhalb als auch außerhalb des lokalen Verarbeitungselements, und das die Handhabung von Daten und Steuersignalen der Aufgaben untereinander minimiert.
Im Stand der Technik basierten die Betriebssysteme, die für Echtzeitsteuerungsanwendungen ausgebildet waren, auf einem Echtzeitexekutivprogramm, in welchem Echtzeitereignisse sorgfältig aufgelistet oder "geplant" wurden, um eine Folge von zeitgesteuerten Aufgaben zu beginnen. In einem solchen Exekutivprogramm führte jede nennenswerte Zunahme an Ausführungszeit einer Aufgabe während der Entwurfsperiode üblicherweise zu einer Neuaufteilung der Echtzeitaufgaben und/oder resültierte in beträchtlichen Entwurfsänderungskosten. Außerdem waren die bekannten Exekutivprogamme nicht in der Lage, sich dynamisch auf die nicht vollständig vörhersagbaren oder vanablen Zeiten des Auftretens von externen Ereignissen in anderen Prozessoren in einem Multiprozessorsystem einzustellen.
Die US-A-3 662 401 beschreibt ein Verfahren zum Steuern der Ausführung von gegenseitig abhängigen Aufgaben gemäß dem Oberbegriff des unabhängigen Patentanspruches 1.
Ein Ziel der vorliegenden Erfindung ist es, ein Aufgabenexekutivprogramm in einem Multiprozessorsystem zu schaffen, das unter Berücksichtigung von Aufgabenabhängigkeiten und -voraussetzungen Daten und Steuerflußsignale managt, um zeitgerecht und kohärent die erforderlichen Eingangsdaten für eine Aufgabe dem Prozessor zur Verfügung zu stellen, der diese Daten benötigt, um die Aufgabe richtig auszuführen.
Ein weiteres Ziel der vgrliegenden Erfindung ist es, ein Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen, das eine Architektur berücksichtigt, bei der eine bestimmte abhängige Aufgabe verlangen kann, daß mehrere vorrangige Aufgaben in lokalen oder irgendwelchen anderen Prozessoren abgearbeitet werden, bevor sie ausgeführt wird.
Ein weiteres Ziel der vorliegenden Erfindung ist es, ein Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen, das flexibel genug ist, um entweder während des Entwurfsprozesses oder dynamisch aufgrund von Änderungen in den Ausführungszeiten von Aufgaben, die sich während der Ausführung beträchtlich ändern können, geändert zu werden.
Ein weiteres Ziel der vorliegenden Erfindung ist es, ein einfaches, niedrige Generalkosten verursachendes Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen.
Ein weiteres Ziel der vorliegenden Erfindung ist es, ein Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen, in welchem Unterbrechungen und Datenblöcke zwischen den Prozessoren wirksam gehandhabt werden.
Ein weiteres Ziel der vorliegenden Erfindung ist es, ein Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen, welches Protokollblockierungen und verborgene Transportsverzögerungen, die bei bekannten Multiprozessorsystemen vorherrschen, vermeidet.
Ein weiteres Ziel der vorliegenden Erfindung ist es, ein Aufgabenexekutivprogramm für ein Multiprozessorsystem zu schaffen, welches zeitkritische Pfade optimiert.
Ein weiteres Ziel der vorliegenden Erfindung ist es, die Relokalisierbarkeit von Aufgaben in einem Multiprozessorsystem wie zwischen Prozessoren zu erleichtern.
Ein weiteres Ziel der vorliegenden Erfindung ist es, für eine wirksame Handhabung von Durchlaufdaten und Steuersignalen zwischen mehreren Prozessoren zu sorgen.
Diese Ziele werden gemäß der Erfindung durch die Merkmale des kennzeichnenden Teils des unabhängigen Anspruchs 1 erreicht.
Gemäß einem Aspekt der Erfindung können Aufgabenvorränge und Signalabhängigkeiten in einem Multiprozessorsystem, in welchem Aufgaben zwischen den Prozessoren aufgeteilt werden, in Form einer Entwurfshilfe grafisch ausgedrückt werden, die als ein Vorrangdiagramm bezeichnet wird; dabei werden die zugeordneten Aufgaben in gegenseitiger Abhängigkeit in Form von Aufgaben veranschaulicht, welche verschiedenen Signalprozessoren in dem Multiprozessorsystem zugeordnet sind, und in Form von Unterbrechungen und einer Übertragung von Daten zwischen Prozessoren zur richtigen Zeit. Das Exekutivprogramm wird dann so entworfen, daß es gemäß den Vorrängen und gegenseitigen Abhängigkeiten, die in dem Vorrangdiagramm dargestellt sind, arbeitet. Wenn eine Aufgabe endet, wird ein Aufgabenendesignal getriggert und dem Exekutivprogramm übermittelt, das seinerseits ein Aufgabenendeunterbrechungssignal einem weiteren Prozessor zuführt, wobei die beendete Aufgabe eine Voraussetzung für den Beginn der Ausführung einer weiteren, abhängigen Aufgabe in dem anderen Prozessor ist. Aktualisierte Daten, die aus der Beendigung der Aufgabe in dem Prozessor resultieren, der das Unterbrechungssignal liefert, werden zu dem anderen Prozessor zur Zeit der Beendigung der Aufgabe übertragen. Die Kohärenz der übertragenen Daten kann gewährleistet werden, indem die Daten gesendet werden, bevor die Unterbrechung erzeugt wird. Wenn das Exekutivprogramm in jedem Prozessor das Aufgabenendeunterbrechungssignal entweder aus seiner eigenen Aufgabe oder aus einem anderen Prozessor in dem Multiprozessorsystem empfängt, ermittelt es aus einer Abhängigkeitstabelle diejenigen Aufgaben, welche von der Beendigung der Aufgabe abhängig sind, die durch das Aufgabenendeunterbrechungssignal repräsentiert wird. Momentanzustandssignale werden gemäß dieser Ermittlung für den Zweck erzeugt, den Momentanzustand von Voraussetzungen für jede Aufgabe zu aktualisieren. Die Momentanzustandssignale werden in einem Speicher als eine Momentanzustandsliste einer Aufgabenvoraussetzungstabelle gespeichert. Daher haben alle noch auszuführenden Aufgaben, die von der Beendigung der Aufgabe und dem zugeordneten Aufgabenendeunterbrechungssignal abhängig sind, den Momentanzustand ihrer Voraussetzungen in bezug auf diese Aufgabe in der Momentanzustandsliste der Voraussetzungstabelle in aktualisierter Form. Aufgaben, für die alle Voraussetzungen erfüllt worden sind, werden zur Ausführung in einer ausgewählten Reihenfolge in eine Warteschlange eingereiht.
Weiter kann gemäß einem zusätzlichen Aspekt der Erfindung in einem Multiprozessorsystem die Architektur so sein, daß Daten nicht direkt von einem Prozessor zum anderen übertragen werden können. Entweder wegen des Fehlens oder wegen des Ausfalls eines direkten Pfades; in einem solchen Fall müssen weiter gemäß der vorliegenden Erfindung die Daten statt dessen einen oder mehrere andere Prozessoren oder zugeordnete Speichervorrichtungen durchlaufen. In einer solchen Architektur wird der Zwischenprozessor oder werden die Zwischenprozessoren oder ihre zugeordneten Speichervorrichtungen als Zwischenglieder für den Empfang eines Aufgabenunterbrechungssignals und seiner zugeordneten aktualisierten Daten, die sich auf die Beendigung der Aufgabe beziehen, zwischen dem Quellenprozessor und dem Zielprozessor dienen. In einem solchen Fall wird der Quellenprozessor eine Unterbrechung senden, die durch den Zwischenprozessor empfangen wird, der auch die aktualisierten Daten empfängt. Nach dem Empfang der Daten sendet der Zwischenprozessor das Aufgabenunterbrechungssignal und Daten zu dem Zielprozessor, der dann die Unterbrechung und die Daten empfängt. Solche "Übergaben" von Unterbrechungen und Daten können in Fällen verkettet werden, in denen mehrere Prozessorgrenzen überquert werden müssen.
Weiter können gemäß einem Aspekt der Erfindung die Aufgaben, deren Ausführung vorgesehen ist und für die alle Voraussetzungen erfüllt worden sind, in mehrere Aufgabenausführungswarteschlangen eingereiht werden. Die Zahl der Ausführungswarteschlangen wird größer sein als die oder gleich der Zahl von unterschiedlichen Aufgabenraten für das Steuersystem. Mit anderen Worten, es kann mehrere Schichten von Aufgaben geben, die innerhalb des Steuersystems mit verschiedenen Raten ausgeführt werden. Jeder Steuerungsrate können eine oder mehrere Warteschlangen zugeordnet sein. Der Grund für die zusätzlichen Warteschlangen innerhalb einer bestimmten Aufgabenrate besteht darin, daß in vielen Fällen ein Satz von Aufgaben als zeitkritischer angesehen wird und daß deshalb ihre gesamte Transportzeitverzägerung minimiert werden muß. Selbstverständlich kann die Reihenfolge der Ausführung von in Warteschlangen eingereihten Aufgaben gemäß anderen Typen von Kriterien oder wie durch andere Prioritäten diktiert ausgewählt werden.
Zum effektiven Ausnutzen des möglichen Wachstums und zum Erzielen der Flexibilität und von anderen erwünschten Fähigkeiten von Multiprozessorarchitekturen wie z.B. denjenigen Architekturen, die ohne Einschränkung in den beigefügten Fig. 1 und 2 bildlich dargestellt sind, wird eine neue Lösung gemäß der vorliegenden Erfindung für den Entwurf des Exekutivprogramms verlangt.
Das gilt ganz besonders in einer besonderen Klasse von Problemen, wo die Rechenaufgaben unregelmäßig sind und jeder Prozessor unterschiedlich auf einer anderen Datenbasis arbeitet; mit anderen Worten, wo nichthomogene Datenbasen innerhalb einer heterogenen Multiprozessorarchitektur vorhanden sind. Diese Klasse von Problemen verlangt sequentielle Berechnungen in Echtzeit, die in der Lage sind, datenabhängige Entscheidungen zu treffen und sich in nichtregulären Mustern zu verzweigen. Es gibt deshalb einen Bedarf an einer vielseitigen Multiprozessorsystemarchitektur und einem vielseitigen Aufgabenexekutivprogramm, die die sich ändernden Echtzeitzwecke für solche Probleme erfüllen können, indem sie große und sich ständig ändernde komplexe Berechnungen auf sequentielle Weise effizient ausführen.
Die Durchsatzforderungen an diese unregelmäßigen Echtzeitrechenanwendungen sind sehr groß und komplex und können sich von Fall zu Fall drastisch ändern. Der volle Bereich der Daten- und artithmetischen Manipulation sowie der verlangten Eingangs-Ausgangssignalhandbabungsfähigkeiten können sich je nach Fall ebenfalls drastisch ändern. In vielen Fällen sind die Berechnungskomplexitäten auf das Vorhandensein von Verknotung, Schleifenbildung und Vermischung von Datenflußpfaden zwischen den Funktionen zurückzuführen. Die Datenflußpfade und Aufgabenausführungen hängen von der Betriebsart und von seriellen, datengesteuerten Entscheidungen ab.
Der Bedarf an einem hohen Durchsatz ist synonym mit dem Bedarf an der Ausführung einer bestimmten Aufgabe innerhalb einer bestimmten Zeit mit einem Minimum an Wartezeit. Zum Beispiel in Fällen wie Avionik-Echtzeitsteuersystemen sind die Rechentransportverzögerungsforderungen extrem streng, da sie die Leistung und die Fähigkeiten des Systems hinsichtlich der Bandbreite sowie das Störungsmanagement und die Zuverlässigkeitsqualitäten des Gesamtsystems bestimmen. Die Verwendung von Multiprozessoren dehnt den Daten- und Ausführungsfluß über die Prozessorgrenzen hinweg aus und wird zu einem zusätzlichen Faktor, der zu der gesamten Transportzeitverzögerung beiträgt. Die Notwendigkeit, diese zusätzliche Transportzeitverzögerung zu reduzieren, ist daher mit der Forderung nach einer effizienten und eine große Bandbreite aufweisenden Kommunikation zwischen den Interprozessordatenelementen eng verbunden. Eine hohe Kommunikationsbandbreite, die es ermöglicht, eine große Zahl von Signalen schnell zu übertragen, ist wegen des Vorhandenseins von unregelmäßigen und unvorhersagbaren Daten- und Ausführungsflüssen, die sich über die Multiprozessoren ausbreiten, besonders notwendig.
Eine bestimmte Rechenaufgabe, die in Multiprozessorarchitekturen auszuführen ist, wie sie z.B. in den Fig. 1 und 2 dargestellt sind, ohne daß darunter eine Einschränkung zu verstehen sein soll, kann unter Verwendung einer Anzahl unterschiedlicher Methoden angegangen werden. Eine einfache Lösung würde darin bestehen, einen oder zwei Prozessoren für das Management von Eingangsdaten zu verwenden und mehrere andere Prozessoren für die meisten der Rechenaufgaben zu benutzen. Ausgangsabstimmebenen und eingebaute Testaufgaben könnten dann durch die Eingangs-/Ausgangsprozessoren benutzt werden. Das Problem bei dieser Lösung besteht darin, daß nicht alle Prozessoren zu jeder Zeit effizient ausgenutzt werden. Einige Prozessoren können unterbenutzt sein, während einige andere nicht länger in Echtzeit arbeiten können.
Eine weitere Verbesserung eines effektiven Durchsatzes verlangt ein anderes Schema, in welchem Aufgaben ausgewählt werden können, um parallel ausgeführt zu werden, ohne daß nennenswerte zusätzliche Software in dem Exekutivprogramm bereitgestellt wird. Eine solche Lösung für den Entwurf des Aufgabenexekutivprogramms beinhaltet das Aufteilen und Verschmelzen von kritischen, gegenseitig abhängigen Aufgaben für den Zweck des Ausgleichens der gesamten Rechenlast. Das verlangt jedoch eine beträchtliche Ausgeklügeltheit des Exekutivprogramms, die ein potentiell beträchtliches Overhead erfordert.
Ein weiterer, vielleicht wichtigerer Grund für das Erfordernis eines ausgeklügelten Exekutivprogramms ist das Problem einer Protokollblockierung, bei der die Daten- und Steuerungsabhängigkeiten Prozessoren zwingen können, aufeinander zu warten. Das ist eine Situation, die in einem System, welches aus mehr als zwei Prozessoren besteht, besonders schwierig vorhersagbar, testbar oder simulierbar ist. Wenn gestattet wird, daß sich diese Situation einstellt, könnte es zu katastrophalen Ergebnissen kommen. Andere, subtilere Formen der Protokollblockierung können zu unnötigen und verborgenen Transportverzögerungszeiten bei der Ausführung von kritischen Zeitsteuerpfaden führen. Dieses Problem wird durch ineffiziente Techniken bei der Planung von Aufgaben verursacht, deren Voraussetzungen erfüllt worden sind, d.h., die zum Gehen bereit sind. Eine weitere Quelle einer großen Transportzeitverzögerung ist der Mangel an effizienten Techniken zum übertragen von Daten zwischen Prozessoren.
Das ereignisgesteuerte Exekutivprogramm für ein Multiprozessorsystem nach der vorliegenden Erfindung hat den sehr wichtigen Vorteil, daß es durch Entwurfsänderungen nicht nachteilig beeinflußt wird, welche die Ausführungszeiten von Aufgaben nachteilig beeinflussen könnten. Ein ereignisgesteuertes Exekutivprogramm bleibt durch diese Änderungen unbeeinflußt, weil seine Ausführungsfolge nur von der Aufgabenabhängigkeit abhängt, die durch das Vorrangdiagramm vorgegeben wird.
Das Problem des Erzielens eines hohen Gesamtdurchsatzes in einem Multiprozessorsystem nach der vorliegenden Erfindung wird gelöst, indem ein flexibles, ereignisgesteuertes Exekutivprogramm benutzt wird, das mit einem Vorrangdiagramm zum Umreißen der Aufgabendefinition für eine effiziente Ausführung der Arbeitslast arbeitet.
Ein ereignisgesteuertes Exekutivprogramm für ein Multiprozessorsystem nach der vorliegenden Erfindung schafft die Flexibilität der Realisierung, die bei Echtzeitexekutivprogrammen fehlt, und ist ein Schlüsselelement, das für die effektive Ausnutzung von Multiprozessorarchitekturen wesentlich ist.
Gemäß noch einem weiteren Aspekt der vorliegenden Erfindung unterbricht das Auftreten jedes Ereignisses die gegenwärtige Aufgabe für eine Überprüfung der relativen Prioritäten der gegenwärtig unterbrochenen Aufgabe und der neuen Aufgabe(n), für die das Ereignis eine Voraussetzung ist. Eine Aufgabe der höchsten Priorität, die auch alle ihre Voraussetzungen erfüllt hat, wird dann gesucht und wird dann, falls sie gefunden wird, zur Ausführung aufgerufen. Falls sie nicht gefunden wird, wird wieder in die gegenwärtig unterbrochene Aufgabe eingetreten. Dynamische Änderungen in den relativen Zeitsteuerungen von Aufgaben haben daher keinen nachteiligen Einfluß auf das Exekutivprogramm. Das Exekutivprogramm kann auch während des Entwurfsprozesses leicht geändert werden, um es einem neuen Vorrangdiagramm anzupassen, indem einfach die Voraussetzungs- und Abhängigkeitstabellen geändert werden.
Die vorliegende Erfindung schafft ein generisches Exekutivprogramm für alle Konfigurationen und Forderungen, das dürch Tabellen von Vorrängen und Abhängigkeiten gesteuert wird, welche auf einem Vorrangdiagramm von Aufgaben und Signalen basieren. Das Exekutivprogramm ist von Aufgabenzeitsteuerungen dynamisch unabhängig. Es stellt die Flexibilität bereit, die für Entwurfsänderungen benötigt wird, welche in dem Entwurfsprozeß im Stand der Technik häufig zu sehr hohe Kosten verursachenden architektonischen Umwälzungen geführt haben. Die vorliegende Erfindung bietet die Möglichkeit, irgendwelche und alle kritischen Pfade leicht optimieren zu können. Darüber hinaus wird eine effiziente Handhabung von Interprozessorunterbrechungen ermöglicht. Datensignale zwischen Prozessoren werden auf eine kohärente Weise übertragen, indem einfach die Daten vor der Unterbrechung gesendet werden und gleichzeitig die Notwendigkeit einer Abfrage und die damit verbundenen Unzulänglichkeiten und die Gefahr von Sperrungen eliminiert werden. Durchlaufaufgaben werden ebenso effizient gehandhabt. Die Verfolgbarkeit und Überwachung von normalen Aufgabenbeendigungsereignissen sind gewährleistet. Die Fehlertoleranz für abnormale Ereignisse ist ein zusätzliches Merkmal der vorliegenden Erfindung.
Diese und andere Ziele, Merkmale und Vorteile der vorliegenden Erfindung werden im Lichte der ausführlichen Beschreibung einer besten Ausführungsform derselben deutlicher werden, die in den beigefügten Zeichnungen dargestellt ist, in denen:
Fig. 1 eine bildliche Darstellung einer zweidimensionalen Multiprozeßorgitterarchitektur ist, in der ein Multiprozessoraufgabenexekutiv programm nach der vorliegenden Erfindung benutzt werden kann;
Fig. 2 eine bildliche Darstellung einer dreidimensionalen Multiprozessorgitterarchitektur ist, in welcher ein Multiprozessorexekutivprogramm nach der vorliegenden Erfindung benutzt werden kann;
Fig. 3 eine vereinfachte Blockschaltbilddarstellung eines Vorrangdiagramms ist, das eine Anzahl von auszuführenden Aufgaben in einer Anzahl von Prozessoren zeigt und die gegenseitigen Abhängigkeiten zwischen den Aufgaben angibt;
Fig. 4 eine bildliche Darstellung einer Abhängigkeitstabelle ist, die jede der Aufgaben nach Fig. 3 und jede der abhängigen Aufgaben, die mit jeder in Beziehung stehen, zeigt;
Fig. 5 eine bildliche Darstellung einer Voraussetzungstabelle ist, welche eine Voraussetzungsliste für jede der Aufgaben nach Fig. 3 zeigt und außerdem eine Momentanzustandsliste für jede der Voraussetzungen für jede Aufgabe zeigt;
Fig. 6 eine bildliche Darstellung eines Aufgabenidentifizierers ist, welcher jeder der Echtzeitunterbrechungen sowie den Interprozessorunterbrechungen, die dem Exekutivprogramm zugeordnet sind, zugeordnet ist, gemäß der vorliegenden Erfindung;
Fig. 7 eine bildliche Darstellung des Betriebes eines hierarchischen Multitaskingexekutivprogramms ist, in welchem mehrere Aufgabenraten gleichzeitig in Betrieb sind;
Fig. 8 eine bildliche Darstellung einer Ausführungsseguenz ist, die die Ausführung der Aufgaben zeigt, welche in Fig. 3 dargestellt sind;
Fig. 9 eine Darstellung eines zweiten Vorrangdiagramms für ein zweites Multiprozessorsystem ist;
Fig. 10 eine Abhängigkeitstabelle und eine Voraussetzungstabeile für das Vorrangdiagramm nach Fig. 9 zeigt; und
Fig. 11 eine vereinfachte Flußdiagrammdarstellung einer Serie von logischen Schritten ist, die bei der Realisierung eines Aufgabenexekutivprogramms für ein Multiprozessorsystem nach der vorliegenden Erfindung ausgeführt werden können.

Bester Weg zur Ausführung der Erfindung

Fig. 1 ist eine bildliche Darstellung einer zweidimensionalen Multiprozessorgitterarchitektur 10. Es sind mehrere zweidimensionale, modulare Verarbeitungselemente 12, 14, 16, 18 dargestellt, die mit einander auf eine Art und Weise verbunden sind, welche im folgenden ausführlicher beschrieben ist. Die Zahl der Verarbeitungselemente beträgt wenigstens zwei, kann aber irgendeine Zahl sein.
Es ist klar, daß die Architekturen, die in den beiden Fig. 1 und 2 dargestellt sind, nicht im Sinne einer Beschränkung dargeboten werden, da das ereignisgesteuerte Multiprozessoraufgabenexekutivprogramm, das hier beschrieben wird, in einem breiten Bereich von unterschiedlichen Einsatzmöglichkeiten anwendbar ist, die von einem bloßen einzelnen "Uniprozessor" bis zu einem allgemeinen Multiprozessorsystem reichen.
Eine zweidimensionale, modulare Ein-/Ausgabesteuereinheit (input/output controller oder IOC) 20, wie sie in Fig. 1 gezeigt ist, kann in der zweidimensionalen Multiprozessorgitter architektur 10 benutzt werden. Eine solche Ein- /Ausgabesteuereinheit dient dem Zweck, Daten und Steuersignale zwischen der Außenwelt und der Multiprozessorarchitektur zu übertragen. Zusätzliche Ein-/Ausgabesteuereinheiten können benutzt werden, wie es durch eine zusätzliche Ein/Ausgabesteuereinheit 22 angegeben ist, die hilft, die Ein- /Ausgabeaufgabenlast zu teilen. Unter dem Gesichtspunkt der Modularität kann es vorteilhaft sein, sowohl modulare Verarbeitungselemente als auch modulare Ein-/Ausgabesteuereinheiten zur Verwendung als symmetrische Baüsteine in der Gitterarchitektur 10 zu haben. Das schließt jedoch nicht notwendigerweise ein, daß solche Bausteine auch benutzt werden oder daß sie, wenn sie benutzt werden, identisch arbeiten würden. Mit anderen Worten, im Rahmen der vorliegenden Erfindung kommt ein heterogenes Multiprozessorsystem in Frage.
Das Aufgabenexekutivprogramm nach der vorliegenden Erfindung kann, wie oben dargelegt, in einer Architektur wie der in Fig. 1 gezeigten benutzt werden, die vorliegende Erfindung ist aber nicht darauf beschränkt, obwohl sie darin besonders vorteilhaft ist, was im folgenden mehr ins einzelne gehend beschrieben ist.
In einer zweidimensionalen Architektur sollte jedes zweidimensionale, modulare Verarbeitungselement 12, 14, 16, 18 optimal vier Kanäle haben. Diese gehen gemäß der Darstellung in Fig. 1 zum Beispiel von einem Ringbus 32 aus und verlassen das modulare Verarbeitungselement 12 über jede der vier Seiten der gestrichelten Linien, die die Grenzen des modularen Verarbeitungselements angeben. Es ist klar, daß eine tatsächliche Schaltungsrealisierung der zweidimensionalen Multiprozessorgitterarchitektur (oder statt dessen eine Architektur beliebiger Dimension) keinerlei Relation zu den in Fig. 1 gezeigten guadratischen Formen zu haben braucht, da die Schaltungen auf Leiterplatten montiert werden können, die mit anderen Leiterplatten in ein Chassis eingesetzt werden. Die gegenseitigen Verbindungen werden in einem solchen Fall nicht so einfach oder symmetrisch sein, wie es hier dargestellt ist. Diese Figuren dienen daher für viele Fälle lediglich als bildliche und funktionale Darstellungen, welche bei der Präsentation der angewandten Prinzipien helfen.
Die zweidimensionale Gitterarchitektur, die in Fig. 1 dargestellt ist, basiert auf einem zweckbestimmten Speicherbereich zwischen jeder modularen Entität und jeder anderen modularen Entität, miüder sie in dem Gitter kommuniziert. Diese zweckbestimmte Funktion kann am effektivsten durch einen Zweikanaldirektzugriffsspeicher (dual port random access memory oder DPR) realisiert werden. Selbstverständlich ist ein Zweikanaldirektzugriffsspeicher nicht absolut notwendig, da ein Speicherzuteilungsverfahren, bei dem traditionellere Speichervorrichtungen benutzt werden, anstelle desselben angewandt werden könnte.
Wenn eine modulare Bauweise für jedes der zweidimensionalen, mödularen Verarbeitungselemente 12, 14, 16, 18 erwünscht ist, wird es am besten sein, zwei Zweikanal-Direktzugriffsspeicher oder -RAMs pro modularem Verarbeitungselement vorzusehen. Die anderen beiden Kanäle in jedem Element werden keinen Zweikanal- RAM haben, da sie mit anderen modularen Verarbeitungselementen in Verbindung stehen werden, die ihn haben. Die Symmetrie der Verarbeitungselemente, die so aufgebaut sind, ist am vorteilhaftesten, was anhand von Fig. 1 gezeigt werden kann. Dort ist zu beobachten, daß das modulare Verarbeitungselement 12 einen "Süd"-Kanal mit einem DPR 34 hat, der mit einem "Nord"-Kanal des modularen Verarbeitungselements 16 in Verbindung steht, welches keinen zugeordneten DPR hat. Ebenso hat der "Ost"-Kanal des modularen Verarbeitungselements 12 keinen zugeordneten DPR, aber der "West"-Kanal des modularen Verarbeitungselements 14 hat einen zugeordneten DPR 36. Auf diese Weise steigert die Symmetrie der modularen Verarbeitungselemente 12, 14, 16, 18 die Einfachheit, mit welcher ein Multiprozessorgitter aufgebaut werden kann, in welchem jedes modulare Verarbeitungselement mit einer weiteren modularen Entität kommuniziert, im allgemeinen über einen zweckbestimmten DPR. Selbstverständlich könnte die Symmetrie der einzelnen Verarbeitungselemente anders als gezeigt sein.
Der "Nord"-kanal des modularen Verarbeitungselements 12 enthält einen DPR 38, der Daten- und Adreßleitungen 40 hat, die von ihm ausgehen, zur Verbindung mit einer weiteren modularen Entität (nicht gezeigt). Es dürfte ohne weiteres klar sein, daß die Daten- und Adreßleitungen 40 nicht notwendigerweise mit einer weiteren modularen Entität verbunden zu sein brauchen, da die Grenzen der Architektur irgendwo enden müssen. Steuerleitungen 42 gehen ebenfalls von dem Ringbus 32 aus zur Kommunikation über die "Nord"-Grenze für das modulare Verarbeitungselement 12. Diese Leitungen sind nicht absolut notwendig, sondern bestehen normalerweise aus festverdrahteten Unterbrechungen. Solche Unterbrechungen können auch über den DPR gehen, statt separat übertragen zu werden.
Die "Ost"-Grenze des modularen Verarbeitungselements 12 hät, wie dargestellt, Daten- und Adreßleitungen 44 und Steuerleitungen 46, die von dem Ringbus 32 ausgehen, zur Verbindung mit der "West"-Grenze des Verarbeitungselements 14 über den DPR 36.
Ebenso hat die "West"-Grenze der Entität 12 Daten- und Adreßleitungen 48 und Steuerleitungen 50, die von dem Ringbus 32 ausgehen.
Die "Süd"-Grenze des modularen Verarbeitungselements 12 hat einen Kanal, der mit Daten- und Adreßleitungen 52 verbunden ist, die mit dem Ringbus 32 über den DPR 34 verbunden sind. Steuerleitungen 54 bilden die festverdrahteten Unterbrechungen zu dem benachbarten modularen Verarbeitungselement 16.
Es ist zu erkennen, daß die modulare Symmetrie der modularen 109 oder Ein-/Ausgabesteuereinheit 20 in bezug auf die Zahl der darin enthaltenen DPRs anders ist als die der modularen IOC 22. Diese Darstellung dient lediglich zur Veranschaulichung, es ist jedoch klar, daß, nachdem eine besondere Symmetrie für entweder eine IOC oder einen SP gewählt worden ist, es wenig Änreiz geben wird, eine weitere Symmetrie verfügbar zu haben. Das soll jedoch nicht heißen, daß nicht eine oder mehrere unterschiedliche Symmetrien von IOCs oder SPs nicht in derselben Architektur benutzt werden können. Zum Beispiel könnten zwei Typen von SPs benutzt werden, von denen einer drei DPRs und der andere nur eine hat. Darüber hinaus können die Verarbeitungsentitäten selbst alle verschiedene Prozessoren oder Prozessorstrukturen in sich mit Schnittstellen haben, die über das System gleichmäßig sind.
Die modulare IOC 22 nach Fig. 1 umfaßt eine zentrale Ein- /Ausgabesteuereinheit (IOC) 60, die von einem Ringbus 62 umgeben ist, der mit Datenleitungen 64, Adreßleitungen 66 und Steuerleitungen 68 in Verbindung steht, welche von der IOC 60 ausgehen. Es ist zu erkennen, daß der Ringbus 62 für die IOC 22 etwas anders ist als der Ringbus 32, und zwar insoweit, als er einen "unterbrochenen Kreis" mit einer Lücke aufweist, durch die ein Paar Datenleitungen 70 und Steuerleitungen 72 hindurchführt, welche an den "West"-Kanal der modularen IOC 22 angeschlossen sind, zum Kommunizieren mit E/A-Vorrichtungen in der äußeren Welt.
An der "Nord"- und an der "Süd"-Grenze der modularen IOC 22 gibt es Kanäle, die zweckbestimmte Speicher 74, 76 haben, bei denen es sich um DPRs handeln kann und die benutzt werden können, um mit anderen modularen Entitäten in der Gitterarchitektur über Daten- und Adreßbusleitungen 78, 80 bzw. Steuerleitungen 82, 84 zu kommunizieren. Die "Nord"-Grenze kommuniziert mit der IOC 20. Die modulare Entität, falls vorhanden, die mit ihrer "Süd"-Grenze kommuniziert, ist nicht gezeigt, kann aber ein leerer Schlitz, eine weitere modulare IOC oder ein modulares Verarbeitungselement sein.
An der "Ost"-Grenze der modularen IOC 22 ist ein Kanal gezeigt, der Daten- und Adreßlelitungen 86 und Steuerleitungen 88 zum Kommunizieren mit einer benachbarten modularen Entität hat. Es gibt keinen zweckbestimmten Speicher, welcher dem "Ost"-Kanal dieser besonderen modularen IOC zugeordnet ist, da gemäß der Darstellung in Fig. 1 sie in einem Fall benutzt wird, in welchem das benachbarte modulare Verarbeitungselement 16 bereits einen zweckbestimmten Speicher 90 hat.
Fig. 2 veranschaulicht eine dreidimensionale Gitterarchitektur, in der mehrere dreidimensionale, modulare Verarbeitüngselemente 120, 122, 124, 126 und eine dreidimensionale, modulare IOC 128 benutzt werden. Die vier modularen Entitäten 120, 124, 126, 128 können bildlich so dargestellt werden, als lägen sie in derselben Ebene, wogegen die modulare Entität 122 bildlich so dargestellt werden kann, als läge sie in einer weiteren Ebene, parallel zu und hinter der Frontebene. Andere modulare Entitäten sind v6rstellbar, die in derselben Ebene mit der Entität 122 liegen, sie sind aber der Einfachheit halber nicht gezeigt. Jede der modularen, Entitäten in dem dreidimensionalen Gitter ist mit einer oder mehreren benachbarten modularen Entitäten über Zweikanal- RAMs (DPRs) verbunden. Diese sind in Fig. 2, als Würfel gezeigt und sind mit zweckbestimmten Adreß-, Daten- und Steuerleitungen zwischen modulare Entitäten geschaltet. Jede der Entitäten ist so dargestellt, als sei sie von einem "Band"- Bus für Adreß-, Daten- und Steuerleitungen umgeben. Es ist zu erkennen, daß bei der IOC 128 deren Daten-, Adreß- und Steuer-"Band"-Leitungen in einem Punkt unterbrochen sind, um eine Verbindung mit der äußeren Welt über Leitungen 130, zu gestatten, die in ihrer Funktion den Leitungen 70, 72 des in Fig. 1 gezeigten zweidimensionalen Falles gleichen werden. Die dreidimensioale Gitterarchitektur nach Fig. 2 gleicht auch der nach Fig. 1, mit der Ausnahme der zusätzlichen Dimension. Es ist selbstvertändlich klar; daß die Gitterarchitektur auf irgendeine Zahl von Dimensionen ausgedehnt werden kann, was aber hier nicht gezeigt ist, weil es schwierig ist, mehr als drei Dimensionen bildlich darzustellen.
Die Architekturen, die in den Fig. 1 und 2 dargestellt sind, werden, wie oben bereits erwähnt, nicht im Sinne einer Einschränkung präsentiert, sondern lediglich als eine Hilfe für den Leser bei dem Verständnis des Zusammenhanges, in welchem das Aufgabenexekutivprogramm nach der vorliegenden Erfindung benutzt werden kann. Es ist daher klar, daß das Aufgabenexekutivprogramm, das hier präsentiert und beansprucht wird, einfach bei einem einzelnen Prozessor benutzt werden kann und sich darüber hinaus in der Anwendung nicht auf die Typen von Architekturen beschränkt, die in den Fig. 1 und 2 gezeigt sind, sondern bei anderen Architekturen ebensogut breite Anwendung findet.
Bei dem Aufgliedern der Rechenaufgabe in kleine Einheiten ist die kleinste individuelle Einheit aus Softwaremodul(n) plus Daten- und Steuerblöcken, die in einem ausgewählten Prozessor festgelegt werden kann, als eine Aufgabe definiert. Zum Beispiel wird in Avionik-Steuersystemen das Signalmanagement einer Sensorgruppe als eine Aufgabe definiert; eine Triplex-Signalauswahlunterroutine braucht nicht als eine Aufgabe definiert zu werden, sondern wird vielmehr als eine Komponente oder Unteraufgabe definiert, die in Verbindung mit anderen Unteraufgaben verbunden wird, um eine Aufgabe zu bilden. Es dürfte klar sein, daß die Definition einer Aufgabe nicht notwendigerweise fest ist. Sie verlangt die Inkaufnahme von Modularität und Exekutivprogramm-Overhead für die Verarbeitung. Da der Exekutivprogramm-Overhead direkt von der Zahl der Aufgaben in dem Vorrangdiagramm abhängig ist, ist eine "kleine" Zahl üblicherweise erwünscht.
Ein Vorrangdiagramm zeigt die gegenseitige Beziehung von unterteilten Aufgaben. Mit anderen Worten, ein Vorrangdiagramm gibt die Abhängigkeiten und Voraussetzungen jeder Aufgabe an. Ein Beispiel eines Vorrangdiagramms ist in Fig. 3 gezeigt. In dieser Figur wird eine Aufgabe 142, die mit "A" bezeichnet ist, durch ein "externes" Ereignis gestartet, das nicht angegeben ist, das aber allgemein durch einen EINTRITT-Schritt 140 angegeben werden kann. Aufgaben 143, 144, 146, die mit "B", "C" bzw. "D" bezeichnet sind, hängen von der Aufgabe A ab. Es können jedoch nur die Aufgaben B und C durch die Aufgabe A gestartet werden, weil die Aufgabe D auch von der Aufgabe B abhängig ist. Ebenso hängt die letzte Aufgabe 148, die mit "F" bezeichnet ist, von den Aufgaben D und C ab. Die Aufgaben B und C sind durch die Prozessoren P2 bzw. P3 auszuführen, wobei der Prozessor P1 den, Rest übernimmt. Der gesamte Aufgabenvorrang kann durch ein biagramm für alle Aufgaben dargestellt werden, die durch sämtliche Prozessoren in einem bestimmten Zeitrahmen abzuarbeiten sind. So wird an dem Ende der Ausführung der Aufgabe E, die in Fig. 3 gezeigt ist, ein Schritt 150 ausgeführt, in welchem ein Austritt erfolgt. In dem normalen Verlauf von Ereignissen würde wieder in einen Schritt 140 in irgendeinem Punkt eingetreten, wobei zu die ser Zeit alle Schritte A, B, C, D und E erneut ausgeführt würden. Dieser Prozeß könnte ad infinitum weitergehen. Es ist klar, daß die breitesten Ansprüche der vorliegenden Erfindung nicht auf ein Aufgabenexekutivprogramm für ein Multiprozessorsystem beschränkt sind. So würden für den Einzelprozessorfall die Aufgaben nach Fig. 3 nicht auf drei Prozessoren aufgeteilt werden, sondern würden gemäß der vorliegenden Erfindung unter Verwendung eines Aufgabenexekutivprogramms ausgeführt werden, das mit einem Prozessor arbeitet.
In irgendeiner Multiprozessorarchitektur, wie sie in den Fig. 1 und 2 gezeigt ist, wird es normalerweise verschiedene Typen von Unterbrechüngen geben, die gehandhabt werden müssen. Solche Unterbrechungen könnten einen Macrosync- oder MS-Typ von Unterbrechung umfassen, welche den Beginn (oder das Ende) eines sich wiederholenden Zeitrahmens für Synchronisierzwecke angibt, einen Echtzeit- oder RT-Typ von Unterbrechung sowie Interprozessorunterbrechungen zum Anzeigen eines, Endes einer Aufgabe oder einer Forderung zum Starten einer Aufgabe, wenn die Voraussetzungen erfüllt sind.
Eine typische Aufgabe (ID) ist in Fig. 6 gezeigt, und ein solches Identifikationssignal wird über die Datenleitungen in Verbindung mit einer Unterbrechung zu einem Prozessor übertragen. Als erstes wird die Prozessornummer identifiziert, d.h. der Prozessor, der für das Ausführen der Aufgabe bestimmt ist, wie es in einem Block 160 angegeben ist, der eine beliebige Zahl von Bits breit (parallel) oder lang (seriell) sein kann. Jeder Aufgabe kann ein eindeutiger alphanumerischer Identifizierer zugeordnet sein, wie es in einem, Block 162 angegeben ist. Eine Aufgabenwarteschlangennummer wird in einem Fall ebenfalls zugeordnet, in welchem es mehr als eine Warteschlange gibt, z.B. für entweder unterschiedliche Aufgabenraten oder unterschiedliche Warteschlangen innerhalb einer Rate. Das ist in Fig. 6 durch einen Block 164 angegeben. Außerdem wird der Aufgabentyp in einem Block 166 angegeben, in welchem der Typ der auszuführenden Aufgabe identifiziert ist. Bei den Aufgabentypen kann es sich um einen Durchlauf für einen Datenblock, eine Forderung zum Starten einer Aufgabe (wenn die Voraussetzungen erfüllt sind) oder um ein Aufgabenendesignal handeln.
Fig. 4 zeigt eine Abhängigkeitstabelle 152, die aus dem Vorrangdiagramm nach Fig. 3 erzeugt wird. Die Eingaben in der Tabelle enthalten die Gruppen von Aufgaben-IDs, wie sie in Fig. 6 gezeigt sind, welche, zu denjenigen Aufgaben gehören, die von einer bestimmten Aufgabe abhängig sind. Die Tabelle ist derart organisiert, daß die ID einer Aufgabe auf den Beginn der Gruppe von abhängigen Aufgaben zielt. Es ist zu erkennen, daß das Abarbeiten einer Aufgabe A, die mit "A" links in der Tabelle bezeichnet ist, zu Abhängigkeitstabellenaufgaben-ID-Eingaben für die Aufgaben B, C und D bei 154, 156, 158 führt. Ebenso werden Aufgaben-ID-Eingaben für die anderen Aufgaben in dem Vorrangdiagramm gemacht.
In Fig. 5, auf die nun Bezug genommen wird, ist eine Voraussetzungstabelle 160 dargestellt. Für jede ausführbare Aufgabe, die in einer Spalte von ausführbaren Aufgaben aufgelistet ist, welche mit einem, Großbuchstaben links in der Tabelle bezeichnet ist, enthält die Voraussetzungstabelle eine Eintragung für eine Voraussetzungsliste 162 und eine Momentanzustandsliste 164. Die Liste von Voraussetzungen für jede ausführbare Aufgabe enthält alle anderen Aufgaben, die abgearbeitet werden müssen, bevor die fragliche Aufgabe eingeleitet werden kann. Diese Liste kann in Kompilierzeit erzeugt werden und basiert auf dem Vorrangdiagramm nach Fig. 3. Es kann eine Regel aufgestellt werden, daß sie während der Ausführung nicht geändert werden kann. So verlangt z.B. die Aufgabe D, daß zuerst die Aufgaben A und B abgearbeitet werden müssen. Die Momentanzustandsliste wird benutzt, um mit dem Zustand von Voraussetzungen für jede bestimmte Aufgabe Schritt zu halten. In der Darstellung in Fig. 5 zeigt die Momentanzustandsliste, daß die Aufgabe A abgearbeitet ist, was durch Eintragungen 166, 168, 170 gezeigt ist, die den Aufgaben B, C und D entsprechen, welche von der Aufgabe A abhängig sind und für die die Aufgabe A eine Voraussetzung ist. Diese Liste repräsentiert somit, diejenigen Voraussetzungen, die in dem laufenden Aufgabenrahmen, welcher der Aufgabe zugeordnet ist, erfüllt worden sein müssen. Diese Liste wird unter Verwendung der Liste von Voraussetzungen in der Voraussetzungsliste mit der Aufgabenrate reinitialisiert.
Es gibt eine Anzahl von Aufgabenraten, die mit einem Multitaskingexekutivprogramm verbunden sind. So wird eine Aufgabe, die innerhalb einer kurzen Zeitspanne von z.B. 12,5 Millisekunden abgearbeitet werden muß, mit einer Rate von 80 Hertz wiederholt. Aufgaben, die nicht so schnell abgearbeitet werden müssen, z.B. mit einer Rate von 40 Hertz, werden alle 25 Millisekunden wiederholt. Gemäß der Darstellung in Fig. 7 wird es bei einem Multitaskingexekutivprogramm, bei dem fünf verschiedene Raten gleichzeitig ablaufen, zusätzlich z.B. eine Rate von 20 Hertz geben, in welcher Aufgaben, welche dieser Rate zugeordnet sind, alle 50 Millisekunden wiederholt ausgeführt werden, wie es in Fig. 7(c) gezeigt ist. Ebenso werden bei einer Rate von 10 Hertz Aufgaben alle 100 Millisekunden wiederholt, wie es in Fig. 7(d) gezeigt ist. Bei einer Rate von 5 Hertz, wie sie in Fig. 7(e) gezeigt ist, wird es einen Abstand von 200 Millisekunden zwischen den Wiederholungen dieser Aufgaben geben. Für jede der Raten wird es wenigstens eine Ausführungswarteschlange geben.
Die fünf unterschiedlichen Aufgabenraten nach Fig. 7 werden, wie gezeigt, jeweils durch Macrosync-Impulse 172 synchronisiert, die über die Multiprozessorarchitektur übertragen werden; um Synchronismus herzustellen. Für die fünf Raten, die in Fig. 7 gezeigt ist, wird es sechzehn Wiederholungen eines 12,5- ms-Macrosync-Impulses geben, bevor die gesamte 5-Raten-Aufgabe einmal abgearbeitet worden ist.
Eine Aufgabe wird in eine Ausführungswarteschlange eingereiht, wenn sie ihre Voraussetzungen erfüllt. Die Anzahl von Ausführungswarteschlangen wird größer als die oder gleich der Zahl der unterschiedlichen Aufgabenraten sein. Der Grund für irgendwelche zusätzlichen Warteschlangen innerhalb einer bestimmten Aufgabenrate ist, daß in vielen Fällen eine Gruppe von Aufgaben, z.B. die Nickachsenberechnungen in einem Avionic-Fall zeitkritischer betrachtet werden und deshälb ihre gesamte Transportzeitverzögerung minimiert werden muß. Die zusätzlichen Aufgabenwarteschlangen werden deshalb zur parallelen Ausführung bereitgestellt.
Fig. 8 veranschaulicht die Ausführungsseguenz für das Vorrangdiagramm nach Fig. 3 in Relation zu den Zeiten zum Ausführen jeder Aufgabe. Es werden, wie gezeigt, Aufgaben 143 (B) und 144 (C) in den Prozessoren P2 und P3 ausgeführt, und die übrigen Aufgaben werden in dem Prozessor P1 ausgeführt. Die schräffierten Bereiche zeigen eine Zeit, die unbenutzt ist oder für andere Prozessoraufgaben benutzt wird. Es ist zu erkennen, daß, wenn die Aufgabe 144 (C) zu lange dauert, was durch eine gestrichelte Aufgabenendeunterbrechungslinie 200 gezeigt ist, eine Aufgabe 148 (E) beträchtlich, verzögert werden würde, was auch für die frühere Aufgabenendeunterbrechung 202 gelten würde.
Zusätzliche Unterbrechungen 204, 206 zeigen benachbarten Prozessoren das Ende der Aufgabe "A" an, während eine weitere Unterbrechung 208 dem Prozessor P1 das Ende der Aufgabe B anzeigt.
Der Betrieb des Aufgabenexekutivprogramms kann als "ereignis"- oder "unterbrechungs"-gesteuert beschrieben werden. Es brauchen nur die folgenden drei Grundtypen von Ereignissen betrachtet zu werden:
(1) Aufgabenendeunterbrechungen
(2) Durchlaufunterbrechungen, und
(3) Startanforderungsunterbrechungen.
Wenn ein Prozessor eine Aufgabenendeunterbrechung empfängt, benutzt er die Aufgabe ID gemäß der Darstellung in Fig. 6, um die Gruppe von abhängigen Aufgaben in der Abhängigkeitstabelle gemäß der Darstellung in Fig. 4 aufzufinden. Jede abhängige Aufgabe ID und ihre zugeordneten Voraussetzungskriterien werden dann benutzt, um den Momentanzustand von Voraussetzungen in der Voraussetzungstabelle gemäß der Darstellung in Fig. 5 zu aktualisieren. Wenn alle Voraussetzungen für eine Aufgabe erfüllt sind, wird die Aufgabe in die passende Ausführungswarteschlange eingereiht, wofür ihr Aufgabenwarteschlangennummernblock in der Aufgabe ID benutzt wird. Die Gruppe von sämtlichen abhangigen Aufgaben wird durch das Exekutivprogramm auf diese Art und Weise verarbeitet, bevor diese Overhead-Arbeit verlassen wird. Bei dem Beispiel nach den Fig. 3, 4, 5 und 8 würde die Aufgabenendeunterbrechung 202, die durch den Prozessor P3 an den Prozessor P1 bei der Beendigung der Aufgabe 144 (C) ausgegeben wird, zu dem Aktualisieren der Momentanzustandsliste der Voraussetzungstabelle für die Aufgabe E führen. Wenn eine Aufgabe von der Beendigung der Aufgabe C und nur der Aufgabe C abhängig wäre, dann würde die Aufgabenendeunterbrechung, die durch die Aufgabe C bewirkt wird, zu dem Einreihen dieser Aufgabe in die geeignete Ausführungswarteschlange des Prozessors führen.
Es wird Fälle geben, in denen eine Unterbrechung mehr als eine Prozessorgrenze zu überqueren haben wird. Zum Beispiel könnte eine Aufgabe in dem Prozessor P3 eine Voraussetzung für eine Aufgabe in dem Prozessor P2 sein. In diesem Fall würde die Unterbrechung aus dem Prozessor P3 - den Prozessor P1 zu "durchlaufen" haben. Eine Durchlaufunterbrechung und aktualisierte Daten werden P1 zur Weiterleitung zu P2 geliefert. P1 würde auf diese Unterbrechung und Daten antworten, indem er die zugeordnete Aufgabe, ID benutzt, um die Quelle und das Ziel des Datenblockes zu bestimmen. Die Aufgabenendeunterbrechung und die Daten würden dann P2 zur Ausführung geliefert werden. Die Abhängigkeitstabelle kann eine Eintragung der Durchlaufaufgabe(n) enthalten oder nicht enthalten. Die Abhängigkeitstabellen, die in Fig. 4 gezeigt sind, enthalten eine derartige Eintragung nicht, weil sie durch das Unterbrechungsdienstprogramm selbst direkt und am schnellsten gehandhabt wird.
In dem Fall von Datenblöcken, die lokal benutzt und durch einen weiteren Prozessor hindurchgeleitet werden können, brauchen zwei mögliche Lösungen nicht berücksichtigt zu werden. Die erste beinhaltet das Nichtklassifizieren der Aufgabe als einen Durchlauf, sondern als ein Aufgabenendesignal und das Arbeiten wie oben beschrieben. Die Alternative beinhaltet das Ausführen der Durchlaufaufgabe wie oben beschrieben und das anschließende Setzen eines Ereignisflags, so daß der Datenblock lokal benutzt werden kann, indem die Abhängigkeits- und Voraussetzungstabellen benutzt werden. Die letztgenannte Lösung kann bevorzugt werden, da der anfordernde Prozessör nicht immer feststellen kann, ob ein Datenblock nur hindurchgeleitet wird oder nicht.
Eine Startanforderungsunterbrechung kann benutzt werden, um von einem Prozessor zu, verlangen, eine Aufgabe zu starten, die durch die Aufgabe ID angegeben wird, und zwar unabhängig von ihren Voraussetzungen. Diese Unterbrechung kann benutzt werden, um Aufgaben einzuleiten, die keine Voraussetzungen haben, z.B. Echtzeit- und Macrosync- oder MS-Unterbrechungeh. Diese Unterbrechungen können auch als Aufgabenendeunterbrechungen gehandhabt werden. Es wird jedoch manchmal ein Mechanismus benötigt, um eine Aufgabe in einem weiteren Prozessor zu starten, unabhängig davon, was er getan hat.
Es wird nun auf Fig. 11 Bezug genommen, bei der es sich um eine vereinfachte Flußdiagrammdarstellung einer Serie von logischen Schritten handelt, die bei dem Ausführen der Aufgaben, welche in den Fig. 3, 4, 5 und 8 dargestellt sind, realisiert werden können.
Nach dem Eintritt in einem Schritt 210 wird anschließend ein Entscheidungsschritt 212 ausgeführt, in welchem eine Feststellung getroffen wird, ob ein internes Aufgabenendesignal erzeugt worden ist. Wenn dem so ist, wird anschließend ein Entscheidungsschritt 214 ausgeführt, in welchem festgestellt wird, ob es irgendwelche externen Abhängigkeiten gibt oder nicht gibt, die von der Abarbeitung der angegebenen Aufgabe abhängig sind., Wenn dem so ist, wird anschließend ein Schritt 216, ausgeführt, in welchem Daten, die sich auf das Abarbeiten der Aufgabe beziehen, zu irgendeinem und allen anderen Prozessoren in Abhängigkeit von der Abarbeitung der Aufgabe übertragen werden. Ein Aufgabenendeunterbrechungssignal kann dann, wie es in einem Schritt 218 gezeigt ist, an irgendwelche und alle anderen Prozessoren in Abhängigkeit von der Abarbeitung der Aufgabe angelegt werden. Aufgaben 218 ünd 216 könnten gegeneinander vertauscht werden, aber die Übertragung von Daten zuerst ist die bevorzugte Technik, weil Kohärenz gewährleistet werden kann, wenn die Aufgabenendeunterbrechung erst gesendet wird, nachdem die Datenübertragung abgeschlossen ist. Eine solche Lösung würde darauf basieren, daß dem Zielprozessor erst gestattet wird, auf Daten zuzugreifen, wenn er die Aufgabenendeunterbrechung empfangen hat.
Wenn in dem Schritt 212 festgestellt worden ist, daß es kein internes Aufgabenendesignal gibt, das erzeugt worden ist, dann wird anschließend ein Schritt 220 ausgeführt, in welchem festgestellt wird, ob ein Aufgabenendeunterbrechungssignal aus einem anderen Prozessor empfangen worden ist oder nicht. Wenn dem so ist, wird anschließend ein Schritt 222 ausgeführt, in welchem festgestellt wird, ob das Aufgabenendesignal einen Durchlauf von Daten repräsentiert, die für einen anderen Prozessor bestimmt sind. Wenn es sich um einen Durchlauf handelt, dann wird anschließend ein Schritt 224 ausgeführt, in welchem die Durchlaufdaten empfangen und dem Zielprozessor zugeführt werden. Das kann selbstverständlich über eine "Kette" von Prozessoren und Speicherbereichen erfolgen, ganz wie bei einer "Eimerkette".
Selbstverständlich muß die Aufgabenendeunterbrechung auch zu dem Zielprozessor oder zu dem Zwischenprozessor übertragen werden, wie es in einem Schritt 226 angegeben ist.
An dem Ende des Schrittes 226 oder, wenn in dem Schritt 222 festgestellt worden ist, daß es keine Anforderung eines Durchlaufes gibt, wird anschließend ein Schritt 228 ausgeführt, in welchem aktualisierte Daten aus einem weiteren Prozessor empfangen und gespeichert werden.
Nachdem der Schritt 228 beendet ist oder nachdem der Schritt 218 beendet ist, falls in dem Schritt 214 festgestellt worden ist, daß es keine externen Abhängigkeiten gibt, dann wird anschließend ein Schritt 230 ausgeführt, in welchem eine Abhängigkeitstabelle konsultiert wird, um diejenigen internen Aufgaben zu bestimmen, die von der Abarbeitung der abgearbeiteten Aufgabe abhängen, wie es durch das gerade empfangene Aufgabenendeunterbrechungssignal dargestellt wird. Die Momentanzustandsliste von erfüllten Voraussetzüngen wird dann für jede derartige Aufgabe aktualisiert. Die Momentanzustandsliste wird dann mit der Voraussetzungsliste für jede derartige Aufgabe verglichen, wie es in einem Schritt 232 angegeben ist. Diejenigen Aufgaben, für die alle Voraussetzungen erfüllt sind, werden dann zur Ausführung, in einer ausgewählten Reihenfolge, in eine Warteschlange eingereiht, wie es in einem Schritt 234 angegeben ist.
Nach dem Abarbeiten des Schrittes 234 oder, wenn in dem Schritt 220 festgestellt worden ist, daß kein Aufgabenendeunterbrechungssignal aus einem anderen Prozessor empfangen worden ist, erfolgt ein Austritt, wie es in einem Schritt 236 angegeben ist.
Ein weiteres Beispiel eines Vorrangdiagramms für ein Aufgabenexekutivprogramm ist in Fig. 9 gezeigt. Dieses Beispiel ist etwas komplexer als das in Fig. 3 gezeigte Beispiel. Die Aufgaben in Fig. 9 sind auf vier Prozessoren P3, P1, P2, P4 verteilt. Die Aufgaben sind wie in Fig. 3 als zwischen den vier Prozessoren vertikal aufgeteilt dargestellt. Diese Methode der bildlichen Darstellung hat keine spezielle Bedeutung, sondern dient lediglich dazu, eine Trennung der Prozessoren in separate und unterschiedliche Signalverarbeitungselemente zu zeigen. Abhängigkeits- und Voraussetzungstabellen 211a, 211b, die dem Diagramm nach Fig. 9 entsprechen, sind in Fig. 10 gezeigt.
Wie in Fig. 3 benutzt ein Prozessor, wenn er eine Aufgabenendeunterbrechung empfängt, die Aufgabe ID, um die Gruppe von abhängigen Aufgaben in der Abhängigkeitstabelle aufzufinden. Jede abhängige Aufgabe ID und ihre zugeordneten Voraussetzungskriterien werden benutzt, um die Momentanzustandsliste von Voraussetzungen in der Voraussetzungstabelle zu aktualisieren. Wenn alle Voraussetzungen erfüllt sind, wird die Aufgabe in die geeignete Ausführungswarteschlange eingereiht, die ihre Aufgabe ID ergibt. Die Gruppe von allen abhängigen Aufgaben wird auf diese Weise verarbeitet, bevor ein Austritt aus dieser Aüfgabe erfolgt. Für das Beispiel nach den Fig. 9 und 10 zeigen die Abhängigkeits- und Voraussetzungstabellen, daß die Aufgabenendeunterbrechung, die durch die Aufgabe C geliefert wird, zu dem Einreihen der Aufgaben F und G in den geeigneten Prozessorausführungswarteschlangen und zum Aktualisieren des Voraussetzungszustands der Aufgabe H führen wird.
Wie zuvor bei den Unterbrechungen und/oder Daten, die Prozessorgrenzen überqueren müssen, wird eine Durchlaufunterbrechung geliefert. Wieder wird ein Prozessor auf diese Unterbrechung antworten, indem er die zugeordnete Aufgabe ID benutzt, um die Quelle und das Ziel des Datenblockes zu bestimmen. Die Aufgabe wird innerhalb eines Unterbrechungsdienstprogramms ausgeführt, um die höchste Durchsatzrate für Durchlaufaufgaben zu erzielen.
In einem ausführlicheren Beispiel eines Durchlaufes, als er vorstehend angegeben ist, verlangt gemäß der Darstellung in dem Vorrangdiagramm nach Fig. 9 die Abarbeitung der Aufgabe E in dem Prozessor P4 eine Durchlaufunterbrechung für den Prozessor P2, um die Voraussetzungen der Aufgabe J in dem Prozessor P1 zu erfüllen. Die Aufgabenabarbeitungsunterbrechung und aktuahsierte Daten werden P2 durch P4 geliefert und führen zur planmäßigen Festlegung der Durchlaufaufgabe. P2 unterbricht den Prozessor P1 und überträgt die notwendigen Daten zu P1. Der Prozessor P1 benutzt diese Unterbrechung aus P2, um die Momentanzustandsliste der Voraussetzungstabelle für die Aufgabe J zu aktualisieren. Es ist wie, derum zu erkennen, daß die Äbhängigkeitstabelle keine Eintragung der Durchlaufaufgabe(n) enthält, weil diese Aufgaben in den Unterbrechungen über eine Suchtabelle, die nicht gezeigt ist, effizienter gehandhabt werden.
Hier gelten wieder ebenso die Kommentare bezüglich der Datenblöcke, die lokal benutzt werden, sowie durch einen weiteren Prozessor hindurchgeleitet werden, wie sie oben mit Bezug auf Fig. 3 angegeben worden sind.
Die Beschreibung, die oben mit Bezug auf Fig. 3 angegeben ist und sich aüf Startanforderungsunterbrechungen bezieht, gilt auch im Hinblick auf Fig. 9.
Die Erfindung ist zwar mit Bezug auf eine beste Ausführungsform derselben gezeigt und beschrieben worden, dem einschlägigen Fachmann ist jedoch klar, daß die vorstehenden und verschiedene andere Änderungen, Auslassungen und Hinzufügungen hinsichtlich Form und Einzelheiten vorgenommen werden können.

Claims

1. Verfahren zum Steuern der Ausführung, von gegenseitig abhängigen Aufgaben, die verschiedenen Signalprozessoren zugeordnet sind, beinhatend die Schritte:

Übertragen (216) von Daten, die aus der Abarbeitung einer Aufgabe in einem ersten Prozessor resultieren, wobei die Abarbeitung der Aufgabe eine Voraussetzung für den Beginn der Ausführung einer anderen Aufgabe in einem zweiten Prozessor ist;

Abgeben (212) eines Aufgabenendeunterbrechungssignals von dem ersten Prozessor, der die Aufgabe abgearbeitet hat, an den zweiten Prozessor, in welchem die Ausführung der anderen Aufgabe begonnen werden soll; und

Bestimmen (230) anhand einer Abhängigkeitstabelle in dem zweiten Prozessor aufgrund des Aufgabenendeunterbrechungssignals derjenigen Aufgaben, die von der Abarbeitung der abgearbeiteten Aufgabe abhängig, sind,, was durch das Aufgabenendeunterbrechüngssignal dargestellt wird, und Liefern von Momentanzustandssignalen, die die Abarbeitung angeben;

Speichern der Momentanzustandssignale;

Vergleichen (232) der gespeicherten Momentanzustandssignale mit gespeicherten Aufgabenvoraussetzungssignalen, welche die Aufgaben angeben, die ausgeführt werden müssen, bevor die bewußte Aufgabe ausgeführt werden kann;

Einreihen (234) zur Ausführung, in einer ausgewählten Reihenfolge, derjenigen Aufgaben, für die der Schritt des Vergleichens anzeigt, daß alle Voraussetzungen erfüllt worden sind, in eine Warteschlange;

wobei das Verfahren durch folgende Schritte gekennzeichnet ist:

Übertragen (216) von Daten, die aus der Abarbeitung einer zweiten Aufgabe resultieren, von einem dritten Prozessor in eine Signalspeichervorrichtung;

Abgeben (212) eines ersten Ende-der-zweiten-Aufgabe-Unterbrechungssignals von dem dritten Prozessor an den zweiten Prozessor entweder direkt oder über die erste Signalspeichervorrichtung, das die Abarbeitung der zweiten Aufgabe angibt, was eine Voraussetzung für den Beginn, der Ausführung von wenigstens einer Aufgabe zur Ausführung in dem ersten Prozessor ist;

Übertragen (216) der Daten, die sich gegenwärtig in der ersten Signälspeichervorrichtung befinden, in eine zweite Signalspeichervorrichtung;

Abgeben eines zweiten Ende-der-zweiten-Aufgabe-Unterbrechungssignals von dem zweiten Prozessor an den ersten Prozessor;

Übertragen (212) der Daten, die sich gegenwärtig in der zweiten Signalspeichervorrichtung befinden, in den ersten Prozessor;

Bestimmen (230) anhand einer Abhängigkeitstabelle in dem ersten Prozessor aufgrund des zweiten Ende-der-zweiten-Aufgabe-Unterbrechungssignals derjenigen Aufgaben, die von der Abarbeitung der zweiten Aufgabe abhängig sind, was durch das zweite Endeder-zweiten-Aufgabe-Unterbrechungssignal dargestellt wird, und Liefern von Momentanzustandssignalen, die die Abarbeitung angeben;

Speichern der Momentanzustandssignale;

Vergleichen (232) der gespeicherten Momentanzustandssignale mit gespeicherten Aufgabenvoraussetzungssignalen, die Aufgaben angeben, welche auszuführen sind, nach einem Vergleich von einem oder mehreren gespeicherten Momentanzustandssignalen mit den gespeicherten Aufgabenvoraussetzungssignalen; und

Einreihen (234) in eine Warteschlange zur Ausführung, in einer ausgewählten Reihenfolge, derjenigen Aufgaben, für die der Schritt des Vergleichens anzeigt, daß alle Voraussetzungen erfüllt worden sind.