Inhaltsverzeichnis

Inhaltsverzeichnis � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� Vorbetrachtungen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

��� Gegenstand dieser Arbeit � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� Grundlagen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

����� Das von Neumann�Paradigma � � � � � � � � � � � � � � � � � � � � � � ������ Nachteile des von Neumann�Ansatzes � � � � � � � � � � � � � � � � � � ������ Das Daten�uss�Paradigma � � � � � � � � � � � � � � � � � � � � � � � � � ����� Nachteile des reinen Daten�uss�Ansatzes � � � � � � � � � � � � � � � � ����� Die Kosten der Parallelit�t � � � � � � � � � � � � � � � � � � � � � � � �

� Hybride Architekturen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

��� Data�ow with Argument Fetching � � � � � � � � � � � � � � � � � � � � � � ������� Programm�Tupel und Architekturmodell � � � � � � � � � � � � � � � ������� Operationsmodell des puren Daten�ussansatzes mit argument fet�ching � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������� Besonderheit des argument fetching � � � � � � � � � � � � � � � � ������ Erweiterung zum Hybriden � � � � � � � � � � � � � � � � � � � � � � � ������� Schlussbemerkungen � � � � � � � � � � � � � � � � � � � � � � � � � � � �

��� Large Grain Data�ow Computing � Makro Data�ow � � � � � � � � � � � ������� Large�Grain Data�ow Graph � � � � � � � � � � � � � � � � � � � � � � ������� LGDG�Architektur � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������� Schlussbemerkungen � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

��� Threaded Data�ow � Process Orientated Data�ow System PODS � ������� Architekturen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������� Partitionierung des Daten�ussgraphen � � � � � � � � � � � � � � � � ������� Scheduling der SCS � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������ Programm� und Daten�Partitionierung � � � � � � � � � � � � � � � � ������� Schlussbemerkungen � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

� Zusammenfassung und Ausblick � � � � � � � � � � � � � � � � � � � � � � � � ��

��� Zusammenfassung � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� Ausblick � Multithread�Architekturen � � � � � � � � � � � � � � � � � � � � ��

Abbildungsverzeichnis � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

Literaturverzeichnis � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

Inhaltsverzeichnis �

� Vorbetrachtungen

��� Gegenstand dieser Arbeit

Auf der Suche nach immer leistungsf�higeren Prozessorarchitekturen f�hrt derWeg an Multiprozessor�Rechnern nicht vorbei� Leider wird erkennbar� dass sichdie �ber �j�hrige Erfahrung in der Entwicklung von Steuer�uss�Prozessorennicht unmittelbar auf parallele Architekturen �bertragen l�sst� Einige Probleme�die sich auf Einzelprozessoren durch einfache Mechanismen e�ektiv l�sen liessen�erweisen sich auf Multiprozessorsystemen als viel komplexer und oft unbere�chenbar ��

Alternative Architekturen bieten Mechanismen� um solche Probleme zu l�sen�Die Vorteile der Daten�ussarchitekturen bez�glich Parallelverarbeitung� Synchro�nisation auf unterster Ebene und Latenzmaskierung als inherente Eigenschaftenliegen klar auf der Hand� Leider impliziert dies eine zumindest teilweise Abkehrvom gro�en Erfahrungsschatz im Umgang mit den von Neumann�Architekturen���� Von diesen Erfahrungen dennoch zu pro�tieren� die Vorteile der von Neu�mann�Architektur mit denen der Daten�uss�Architektur zu verbinden und dieGrundlage f�r einen skalierbaren universellen Parallelrechner zu scha�en� ist Zielder Forschung im Bereich der hybriden Daten�uss�Architekturen�

Diese Arbeit behandelt einf�hrend die Grundlagen der Daten�uss� und derSteuer�uss�Architekturen� sowie der De�nition der Begri�e Synchronisation undLatenz und ihrer Bedeutung f�r die Welt der Parallelverarbeitung� Der Haupteilwidmet sich der Vorstellung wesentlicher Konzepte der hybriden Daten�ussarchi�tekturen am Beispiel dreier Implementationen� deren Aufbau und Funktionsweisehier beschrieben wird� Auf die Besonderheiten und Herausforderungen bez�glichdes Complilerbaus und der Softwareentwichling f�r diese Architekturen wird hin�gewiesen� jedoch nicht n�her eingegangen� Den Abschluss bildet eine Einsch�t�zung des Ein�usses der hybriden Daten�usskonzepte auf moderne Architekturenund die kurze Vorstellung der weiterf�hrenden Forschung�

��� Grundlagen

In diesem Abschnitt werden kurz die beiden Berechnungsmodelle

� das Berechnungsmodell nach von Neumann bzw� das Steuer�uss�Modell

� das Daten�uss�Modell

vorgestellt und charakterisiert� sowie einige Grunds�tze zur Parallelverarbeitungerl�utert�

�� als Beispiel hierf�r seien die Latenzzeiten bei Speicherzugri�en angef�hrt � diese sind aufEinprozessorsystemen durch Pipelining zu maskieren� machen aber auf MehrprozessorsystemenSynchronisationsmechanismen erforderlich

� Abschnitt �

����� Das von Neumann�Paradigma

Das Berechnungsmodell nach von Neumann oder das Steuer�uss�Modell wurde��� von John von Neumann als Konzept zur Gestaltung eines Universalrechnersvorgeschlagen� Es ist dasjenige� welches wegen seiner Einfachheit� der darausresultierenden Geschwindigkeit und seiner hohen Flexibilit�t allen heutigen Uni�versal�Prozessoren zugrundeliegt� Diese Flexibilit�t r�hrt von folgenden Charakte�ristiken dieses Ansatzes her�

� ein einzelner Programmz�hler enth�lt die Adresse des folgenden auszu�f�hrenden Befehles und wird implizit �einfaches Hochz�hlen� oder explizit�Eintragen neuer Adresse bei Spr�ngen� ���� ver�ndert

� es wird ein sequenzieller Steuer�uss erzeugt� der das ProgrammInstruktion f�r Instruktion abarbeitet

� anhand des Befehlsz�hlers ist der Maschinenzustand immer ein�deutig erkennbar und reproduzierbar

� alle Informationen �Daten� Befehle� Adressen� werden einheitlich alsBin�rvektoren fester L�nge gespeichert

� es gibt einen globalen Speicher f�r alle Informationen� dieser wird von derCPU mit Hilfe von Adressen angesprochen �passiver Speicher� � dies machtdie Implementierung von komplexen Kontroll� und Daten�Strukturen ein�fach

l oad r 0, ( sp+a)

l oad r 1, ( sp+b)

mul r 0, r 1, r 2

di v r 0, r 1, r 0

add r 2, r 0, r 0

r t s

l oad r 1, ( sp+c)

Abbildung �� Steuer�uss f�r a b�a

c

�

Vorbetrachtungen �

ALU

Adr essbus

Oper anden−r egi st er sa t z

Dat enbus

St euer wer k mitBef ehl sdecoder

Pr ogr amm−zä hl er mitBef ehl s−adr ess −r egi st er

Bef ehl s−r egi st er

Oper anden−adr ess −r egi st er

Abbildung �� prinzipielle von Neumann�Maschinenstruktur

Die grundlegenden Komponenten eines Steuer�ussprozessors sind �Abb����

� ALU � arithmetic logic unit � die Einheit zur Ausf�hrung von Opera�tionen auf Bin�strings

� Register � tempor�re Speicherzellen zum Ablegen der Operanden bzw�Befehle

� Steuerwerk � Einheit zum Decodieren der Befehlsw�rter und Ansteuernaller Komponenten des Prozessors

� Programmz�hler � enth�lt die Adresse des n�chsten abzuarbeitendenBefehles

� Operandenadressregister � enth�lt die Adressen der n�chsten zu schrei�benden oder zu lesenden Daten

Die Bearbeitung eines Befehles geschieht in folgenden Schritten�

�� das Steuerwerk l�sst den Programmz�hler die Befehlsadresse auf demAdressbus anlegen

�� aus dem Speicher wird der codierte Befehl ins Befehlsregister geschriebenund dort vom Befehlsdecoder im Steuerwerk decodiert

�� die ben�tigten Operanden werden in die ALU geladen �entweder aus demOperandenregister oder mit Hilfe von Speicherzugri�en �ber das Operan�denadressregister aus dem Hauptspeicher� und der Arbeitsmodus der ALU

Abschnitt �

gesetzt

� die ALU berechnet das Ergebnis und legt es an den Datenbus� von wo auses entweder zum Speicher oder zur�ck ins Operandenregister geschriebenwird

�� der Programmz�hler wird inkrementiert �normalerweise um � auf die fol�gende Adresse im Adressraum� bei komplizierteren Befehlen sind auchgr��ere Abst�nde m�glich� im Falle von Sprungbefehlen wird durch dasSteuerwerk eine neue Adresse eingetragen ����

Fortgeschrittene von Neumann�Architekturen sind in der Lage� aus einemkomplexen Befehlsstrom multiple Instruktionen zu lesen� in mehreren Funktions�einheiten gleichzeitig zu verarbeiten �Superskalar� und VLIW�Architekturen� unddamit eine Parallelisierung auf Instruktionsebene auszunutzen�

Multiprozessor�Systeme mit Steuer�ussprozessoren sind im wesentlichen alsSIMD �single instruction multiple data� oder MIMD �multiple instruction mul�tiple data� angelegt� Bei SIMD arbeiten mehrere Recheneinheiten parallel mitdem selben Befehlsstrom � diese Architektur eignet sich vor allem zur gleichzei�tigen Manipulation von unabh�ngigen Elementen einer Datenstruktur �Vektor��Matrizen�Operationen�� Im Gegensatz dazu verf�gt in MIMD�Systemen jederProzessor �ber seinen eigenen Befehlsz�hler und kann einen eigenen Befehlstrombearbeiten� dies macht allerdings die Programmierung zu einer sehr komplexenAufgabe�

����� Nachteile des von Neumann�Ansatzes

O�ensichtlich erlegt der lineare Steuer�uss einem Programm noch zus�tzlichesequenzielle Beschr�nkungen auf� die im urspr�nglichen Algorithmus nicht vorge�sehen waren�

Die passive Charakteristik des Speichers verlangt� dass die CPU jeden Befehlund jedes Datum separat vom Speicher anfordern muss� Dies resultiert in hohembidirektionalem Verkehr �ber eine einzige Verbindung � der von Neumann�Fla�

schenhals �J� Backus��

Speziell f�r Multiprozessor�Maschinen ergibt sich aus der Speicherorganisationein weiteres Problem � auf den globalen Speicher kann von mehreren Prozessenparallel zugegri�en werden� Um die Konsistenz des shared memory dennochsicherzustellen� sind zus�tzliche Synchronisationsmechanismen n�tig����

Ein gro�er Nachteil des einzelnen Steuer�usses ist ausserdem die Tatsache�dass Instruktionen� die Speicherzugri�e durchf�hren� gro�e Latenzen verursachen�Bei Einprozessorsystemen k�nnen diese E�ekte zwar durch Ma�nahmen wieCaching� Prefetching oder Instruction Reordering eingegrenzt oder maskiertwerden� jedoch f�hren diese Ma�nahmen zu Synchronisationsproblemen� wenn sieohne Anpassung auf Multiprozessorsysteme �bertragen werden sollten� ���

Vorbetrachtungen

����� Das Daten�uss�Paradigma

Das Daten�uss�Berechnungsmodell� beruht auf den fundamentalen Prinzipien� diein den fr�hen ��er Jahren des vorigen Jahrhunderts von Jack Dennis entwickeltwurden� Das Prinzip beruht grunds�tzlich auf einer einzigen grunds�tzlichen Aus�f�hrungsregel ��ring rule�� ein Befehl ist ausf�hrbar� wenn alle von ihmben�tigten Operanden zur Verf�gung stehen� Auf dieser zentralen Regel beruhenfolgende Eigenschaften des Daten�ussmodells�

� es ist asynchron � es existiert keine von einem Befehlsz�hler vorgegebeneBearbeitungsreihenfolge

� es ist selbstorganisierend �self scheduling� � die Bearbeitungsreihenfolgewird nur durch die Datenabh�ngigkeiten bestimmt

� es impliziert Parallelverarbeitung � alle Instruktionen� die keine unmittel�baren Datenabh�ngigkeiten untereinander besitzen� sind gleichzeitig aus�f�hrbar

Diese Eigenschaften bedingen folgende entscheidende Vorteile des DF�Ansatzes�

� es wird ein sehr hoher Datendurchsatz erreicht

� die Abarbeitung synchronisiert sich selbst und ist frei von Seitene�ektenwie Speicherinkonsistenzen

add

di vmul

Rt s

bb aa cc

desti nati on

mat chi ng

Abbildung �� Daten�uss�Graph f�r a b�a

c

�

Mat chi ngUnit

Fet chUnit

Pr ocess i ngUnit s

Memor y( acti vit y st or e)

execut abl ei nst r uc ti ons

Dat a t okens

mat chedt okens

Abbildung �� prinzipielle DF�Maschinenstruktur �hier dynam� DF� ��

�� im folgenden wird Daten�uss oder �data �ow� auch mit DF abgek�rzt verwendet

� Abschnitt �

Der Kontroll�uss in einem Programm wird somit durch den Fluss der Datenzwischen den Instruktionen repr�sentiert � das hei�t� ein Programm kann alsgerichteter Graph dargestellt werden� In einem solchen Daten�uss�Graphen

�Abb��� symbolisieren die Knoten die Instruktionen und die gerichteten Kantendie Datenabh�ngigkeiten zwischen den Befehlen ��� � Die Daten werden entlangder Kanten in Form von sogenannten Token weitergegeben� die von jeder Instruk�tion konsumiert und neu erzeugt werden�

Diese Token sind auch die Basisstruktur f�r die Berechnung innerhalb einerDaten�ussmaschine� Sie enthalten neben den Daten die ID der Instruktion� f�rdie sie jeweils bestimmt sind� Anhand dieser ID wird eine �berpr�fung �tokenmatching� durchgef�hrt� Falls genug Token mit der selben ID verf�gbar sind�werden diese an den Zielbefehl �bergeben und dieser zur Bearbeitung bereitge�stellt� Je nach Auspr�gung und Implementierung des Daten�uss�Modellsgeschehen das Matching und die �bergabe in abgewandelter und optimierterForm��

Die grunds�tzlichen Charakteristiken einer Daten�ussmaschine bleiben jedocherhalten� Es gibt keine einzelne zentrale aktive Komponente �CPU�� sondern dieFunktionalit�t ist auf verschiedene spezialisierte Einheiten verteilt� die unterein�ander durch eine Ring�Pipeline verbunden sind� Hier herrscht nur Datenverkehr ineiner Richtung � ein von Neumann�Flaschenhals wird also ausgeschlossen� Aus�serdem k�nnen alle Einheiten asynchron arbeiten� w�hrend eventuelle Flussunre�gelm�ssigkeiten durch Queues ausgeglichen werden� Durch die Pipeline reisen dieToken� welche in den folgenden Funktionseinheiten �Abb�� verarbeitet werden�

� Matching Unit � hier werden die Daten�Token gespeichert� anhand derBefehls�ID des Zielbefehls verglichen und bei �bereinstimmung als Token�paar weitergeschickt

� Fetch�Unit � hier wird der zur ID passende Befehl aus dem Activity Store�Befehlsspeicher� geholt � zusammen mit den Daten �Operanden� wird eineausf�hrbare Instruktion gebildet und weitergeschickt

� Processing Unit�s� � hier werden die ausf�hrbaren Instruktionen bearbeitetund mit den Ergebnissen neue Datentoken gebildet � da jede ankommendeInstruktion ohne weiter Bedingungen ausf�hrbar ist� k�nnen hier multipleRecheneinheiten benutzt werden

Der reine Daten�uss�Ansatz �pure data�ow� basiert auf dem Transport der Dateninnerhalb der Token� was einen hohen Transport� und Kopieraufwand bedeutet�Um dies abzuschw�chen� wurde der sogenannte I�Structure�Speicher eingef�hrt�ein als shared memory organisierter Speicher� der von einem eigenen Prozessorkontrolliert wird und in eindeutig markierten Speicherzellen die Daten enth�lt� I�Structures erlauben einen kontrollierten und sich �berlappenden Zugri� sowohlvon produzierenden als auch von konsumierenden Instruktionen�

�� Stichworte� static�dynamic DF� tagged token DF� single�token�per�arc� explicit tokenstore� ���

Vorbetrachtungen �

����� Nachteile des reinen Daten�uss�Ansatzes

Trotz des I�Structure�Speichers bleiben einige Nachteile bestehen� die die E�ekti�vit�t des Daten�uss�Modells einschr�nken� Als erstes sei der riesige Aufwandbemerkt� den die Matching Unit betreiben muss� um die passenden Token ein�ander zuzuordnen� Zum reinen Vergleichsaufwand kommt das Problem der Spei�cherverf�gbarkeit� da jedes nicht zuordenbare Token automatisch Speicher allo�kiert� Dies kann beim Ausf�hren eines Programmes oberhalb einer bestimmtenKomplexit�t leicht zum �berlauf des Speichers und zum Deadlock des Systemsf�hren ��� �

Weiterhin sei die Tatsache erw�hnt� dass f�r jeden ausf�hrbaren Befehl einKontextwechsel in der�den Prozessoreinheit�en� eingeleitet werden muss� eventu�elle Lokalit�ten werden nicht ber�cksichtigt�

Die implizite Parallelit�t des Daten�ussgraphen macht das Nachvollziehen derBerechnungsschritte und damit eine Fehlersuche problematisch� Ausserdem kannbis zum Abschluss der Berechnung kaum ein konsistenter Maschinenzustand fest�gestellt werden� was unter anderem die Behandlung von Interrupts mit demdadurch erforderlichen globalen Kontexwechsel erschweren w�rde�

����� Die Kosten der Parallelitt

Ein Parallelrechner ist nach De�nition eine Ansammlung von Berechnungsres�sourcen �Rechenelemente� Speicherelemente und Kommunikationselemente�� dier�umlich verteilt und untereinander verbunden sind� Jede Berechnung ben�tigtendlich viel �und � �� Platz und Zeit und die Kommunikation unterliegt denSchranken der Lichtgeschwindigkeit� Diese Voraussetzungen erfordern dieBetrachtung der Begri�e Latenz und Synchronisation im Zusammenhang mit derParallelisierung�

� Latenz � die Zeit� die zwischen einer Anforderung und der entsprechendenAntwort vergeht� Latenzkosten sind die nutzbare Prozessorzeit� die w�renddes Wartens verloren geht� Die Struktur einer Parallelmaschine impliziertgr��ere Latenzkosten als ein Einzelprozessor wegen der �bertragungszeitenim Kommunikationsnetzwerk� Hinzu kommt� dass verschiedene Teile desSystems mit unterschiedlichen Latenzkosten behaftet sind� wodurch dieErhaltung einer gegebenen Ordung zwischen Anfragen und Antwortennicht unbedingt m�glich ist�

� Synchronisation � die zeitliche Abstimmung von verschiedenen Kon�

texten� innerhalb einer Berechnung� Alle Synchronisationsmechanismenbeinhalten die Identi�kation der Beteiligten� den Test auf Erf�llung derSynchronisationsbedingungen und Ma�nahmen f�r den Fall� dass diesenicht erf�llt wurden� Diese Ma�nahmen sind entweder ein Blockieren derBerechnung bis zum Eintre�en des erwarteten Ereignisses �dies ver�schwendet auf jeden Fall Berechnungsressourcen� oder ein Kontextwechsel ��

� unter Kontext ist die Berechnungsumgebung eines Programmfragmentes auf einem Pro�zessor zu verstehen � er wird durch die Befehlssequenz und den Maschinenzustand �Programm�z�hler und Registerinhalte� charakterisiert

� Abschnitt �

um die Bedingung sp�ter erneut zu testen und mittlerweile mit der Berech�nung eines anderen Programmteiles fortzufahren� Synchronisationskostensind die Prozessorzeit� die aktiv zur Synchronisierung verwendet werdenmuss�

Diese beiden Begri�e und ihre E�ekte bedingen die Tatsache� dass es ein opti�males Parallelit�tsniveau f�r jedes Programm gibt� jenseits dessen sich die Aus�f�hrung des Programmes verlangsamt� wenn es noch weiter parallelisiert werdenw�rde� ���

Gesamt auf wand

Kont ext gr ö ß e

ganzesPr ogr amm

ei nze l nerBef ehl

Ber echnung sze it

Zusa t z−Auf wandf ü r Sync., ...

Ber echnung s−auf wand

Abbildung �� Speedup vs� Overhead ��

Dieser E�ekt l�sst sich im sogenannten Speedup vs� Overhead Diagramm�Abb��� darstellen� Hier wird die Beschleunigung durch Verteilung auf mehrereProzessoren dem steigenden Aufwand durch zahlreichere Kontextwechel undandere Synchronisationsmechanismen gegen�bergestellt�

Die beiden vorgestellten Paradigmen siedeln sich nahe der �usseren Punktendieses Graphen an � beide weisen entscheidende Kostenvorteile auf der einen Seite�aber auch gro�e Nachteile auf�

� wird wie beim Daten�uss�Ansatz das Programm auf Instruktionsebene zer�legt� ist eine hochparallele Verarbeitung m�glich �im Extremfall � Befehlpro Prozessor�� deren Zeitersparnis jedoch vom Aufwand� jede Instruktioneinzeln zuzuweisen und die Abarbeitung nach jeder Instruktion zu synchro�nisieren� wieder wettgemacht wird

� wird wie beim von Neumann�Prinzip das gesamte Programm an einen Pro�zessor �bergeben� ergibt sich keine M�glichkeit zur Parallelverarbeitung�allerdings ist auch keine Synchronisation und nur ein Kontextwechsel �dasinitiale Laden des Programmes� n�tig

Allerdings existiert ein Optimum mit minimal m�glichem Overhead bei maximalm�glicher Parallelisierung� Um dieses Optimum zu erreichen� ist eine Mischformbeider Paradigmen n�tig�

� beim Kontextwechsel wird der aktuelle Maschinenzustand ausgelagert und gespeichertund ein neuer Kontext zur Berechnung in den Prozessor geladen � die Kosten f�r einen Kontext�wechsel sind gegnerell ziemlich hoch

Vorbetrachtungen �

� Hybride Architekturen

So unterschiedlich Steuer�uss� und Daten�uss�Paradigma in ihren Grunds�tzenerscheinen� sind sie doch nicht unvereinbar� Sie sind vielmehr als zwei Extrema

eines kontinuierlichen Spektrums von m�glichen Berechnungsmodellen zubetrachten� zwischen denen Architekturen existieren� die die Eigenschaften beiderAns�tze vereinen und m�glichst die Vorteile erg�nzen�

Die hybriden Ans�tze versuchen die E�ektivit�t des Steuer�uss�Pardigmas mitdem innewohnenden Parallelismus des Daten�uss�Ansatzes zu vereinen und soeine universelle Architektur f�r ein paralleles Multiprozessorsystem zu scha�en�Dabei m�ssen folgende Kernprobleme des Daten�ussparadigmas gel�st oderumgangen werden�

� riesiger Vergleichsaufwand beim Token�Matching

� hoher Kommunikationsaufwand beim �bergeben der Daten zwischen denOperationen

� aufw�ndige� da h�u�ge� Kontextwechsel beim Zuweisen neuer Operationenauf Prozessorelemente

� Vernachl�ssigung von Lokalit�ten

Gleichzeitig sollen

� die optimale Ausnutzung gegebener Paralletit�ten bzw� die optimale Paral�lelisierung von Algorithmen

� maximale Ressourcenausnutzung

� e�ektive Synchronisation

� Minimierung von Speicher� und�oder Kommunikations�Latenzen oderderen optimale Maskierung

angestrebt werden�

Es existieren eine Vielzahl von Modellen und Implementierungen� die Archi�tekturen mit hybriden Features beschreiben� Diese Arbeit soll sich auf dreiAns�tze konzentrieren� die wichtige zentrale Ideen bei der Vereinigung von Daten�und Steuer�uss�Prinzip illustrieren�

�� Abschnitt �

��� Data�ow with Argument Fetching

In seinem Artikel A Flexible Achitecture Modell for Hybrid Data�Flow and Con�trol�Flow Evaluation beschreibt G�R� Gao den Entwurf eines DF�von Neumann�Hybriden basierend auf dem puren Daten�uss�Modell mit argument fetching ��Kap��� � Dazu wird vorerst das Konzept des puren Daten�uss mit argument fet�ching vorgestellt� einer modi�zierten reinen DF�Architektur� die M�glichkeitenzur Kombination der hohen Leistung konventioneller Strukturen mit den St�rkender daten�ussgesteuerten Parallelverarbeitung er��net� Daraufhin werden dieseErweiterungen eingef�hrt� die die Ausf�hrung von Befehlssequenzen m�glichmachen�

����� Programm�Tupel und Architekturmodell

Das Daten�uss�Programm sei als Tupel fP � Sg notiert� mit�

� P als Menge von Befehlen� auch als P�Code bezeichnet

� S als gerichteter Graph� genannt Signalgraph� auch als S�Code bezeichnet

Das P�Code�Segment enth�lt ��Adress�Befehle der Form

Ni��OP arg� arg� result�

bestehend aus Operator OP� der Adressen beider Argumente arg�� arg� und derAdresse f�r das Ergebnis result� Ausserdem ist jede p�Instruktion eindeutig ducheine Adresse Ni im IPU�Speicher identi�ziert�

Das S�Code�Segment besteht aus einer Menge von Knoten� die durch gerich�tete Kanten verbunden sind� Die Knoten enthalten die Adresse des Befehles�w�hrend die Kanten die Abh�ngigkeiten beschreiben� Die Kanten sind so notiert�als dass jeder Knoten eine Liste von Adressen der Folgeknoten enth�lt� die soge�nannte signal list � Zus�tzlich be�ndet sich in jedem Knoten ein Statusfeld mitInformationen �ber die Anzahl der zur Ausf�hrung der Instruktion erforderlichenArgumente� sowie die Zahl der bereits verf�gbaren Argumente � dadurch wird derenable state der Instruktion beschrieben�

Done Li nkFi r e Li nk

I PU

I SU

Pr ogr amm & Dat a Memor y

Enabl e St at e &Si gnal Li st Memor y

Par all el −Pr ozessor en

Queue

Si gnal Pr ocessor

Abbildung �� abstrakte DF�Architektur

N122

22

N322

22

N222

22

S−Code:

P−Code: N1: * a a xN2: * b b yN3: + x y z

aa

bb

Abbildung �� Programm�Tupel f�r z�a�� b

�

�� Kap���

Hybride Architekturen ��

Die Architektur �Abb��� f�r dieses Berechnungsmodell sieht zwei Einheitenvor�

� die Instruction Scheduling Unit �ISU�� die die S�Codes �den Daten�ussgra�phen� und die Statusinformationen f�r alle Instruktionen enth�lt und dieSignale zwischen den Instruktionen auf dem Graphen verarbeitet

� die Instruction Processing Unit �IPU�� die die aktivierten Instruktionenabarbeitet � in ihrem Speicher be�nden sich neben den P�Codes die Ope�randen und Ergebnisse

����� Operationsmodell des puren Daten�ussansatzes mit argument

fetching

Die Bearbeitung eines Programmes geschieht nach folgenden Regeln�

�� eine P�Instruktion wird aktiv� wenn ihre entsprechende S�Instruktion aktivwird� also alle Signale empfangen hat ��� alle Operandenadressen sind ver�f�gbar�

�� eine aktive P�Instruktion feuert� wenn ein passendes Feuer�Signal mitBefehls� und Operandenadressen geschickt wird

�� die P�Instruktion wird in der IPU berechnet� der Ergebniswert im Daten�speicher abgelegt und ein done signal generiert� welches die Befehls� undErgebnisadresse enth�lt

� die S�Instruktion wird durch das done signal aktiviert und schicktSignale �mit der Adresse des Ergebnisses als Operandenadresse� an alleInstruktionen in ihrer signal list � deren Statusfelder werden entspre�chend aktualisiert

����� Besonderheit des argument fetching

Die Besonderheit bei dieser Daten�uss�Architektur liegt eindeutig in der Berech�nung der P�Codes in der IPU � diese durchl�uft n�mlich die gleichen Schritte� wieein Befehl auf einer Steuer�ussmaschine�

� instruction fetch �Befehl lesen�

� operand fetch �Operanden lesen�

� execution �Berechnung�

� result store �Ergebnis zur�ckschreiben�mit den entsprechenden Speicherzugri�en

Hiermit o�enbart sich auch der entscheidendste Unterschied zu den reinen Daten��uss�Ans�tzen � es wird nicht mit Daten�Token gearbeitet� die Daten �ie�en eigentlich nicht� sondern verbleiben im Datenspeicher der IPU� es durchlaufen nurReferenzen den Zyklus�

Durch die strikte Trennung von Scheduling und Berechnung ist es einfach� dasbestehende Modell dahingehend zu erweitern� dass anstatt nur einer P�Instruktioneine ganze Kette von Befehlen unter sequenzieller Kontrolle berechenbar ist�w�hrend die Aktivierung und Synchronisation dieser Sequenzen daten�ussge�steuert bleibt ��� �� Kap���

�� Abschnitt �

����� Erweiterung zum Hybriden

Auch wenn die Ausf�hrung einer einzelnen Instruktion nach dem von Neumann�Prinzip geschieht� fehlt doch zur Bearbeitung von Befehlssequenzen ein wichtigerMechanismus � der Befehlsz�hler� der die aktuelle Befehlsadresse enth�lt undw�hrend der Ausf�hrung auf die Adresse des Folgebefehls inkrementiert wird�Allerdings w�ren hier multiple Befehlsz�hler n�tig� einer f�r jede Befehlsse�quenz ���

Ziel eines solchen Mechanismus im Daten�uss�Modell soll sein� bei der Abar�beitung einer Sequenz die Scheduling�Phase in der ISU zu umgehen� das hei�t� esmuss eine Funktionalit�t f�r die IPU eingef�hrt werden� die es erlaubt� nach derAbarbeitung einer Instruktion einer Sequenz sofort die n�chste Instruktion feuernzu lassen� Dazu wird jede P�Instruktion um ein Tag�Feld erweitert� das ein Flagenth�lt� ob es sich um eine Daten�uss� oder eine von Neumann �Instruktionhandelt� Je nach Inhalt des Tags reagiert die IPU nach Abarbeitung der Instruk�tion nach folgenden modi�zierten Operations�Regeln�

�� eine P�Instruktion wird aktiv� wenn

� ihre entsprechende S�Instruktion aktiv wird� also alle Signale emp�fangen hat ��� alle Operandenadressen sind verf�gbar� oder

� sie eine Folgeinstruktion einer Sequenz ist und ihr Vorg�nger dieAbarbeitung abgeschlossen hat

�� ��� �wie zuvor�

�� die P�Instruktion wird in der IPU berechnet und der Ergebniswert imDatenspeicher abgelegt� Danach geschieht vom Modus abh�ngig folgendes�

� bei einer von Neumann �Instruktion wird ein Feuer�Signal mit derAdresse der n�chsten P�Instruktion generiert

� bei einer Daten�uss �Instruktion wird ein done signal generiert�welches die Befehls� und Ergebnisadresse enth�lt

� ��� �wie zuvor�

Done Li nkFi r e Li nk

I PU

I SU

Di r ect Fi r e Li nk

Abbildung � hybride Archi�tektur

Nat�rlich muss das Architekturmo�dell um einen neuen Feuer�Signal�Pfaderweitert werden� um die Umgehungder ISU zu erm�glichen�

Diese Architektur unterst�tzt nundie parallele Verarbeitung vonBefehlen verschiedener gleichzeitigaktiver Befehlssequenzen neben denregul�ren Daten�ussbefehlen auf ver�schiedenen parallelen Prozessoren ���

Hybride Architekturen ��

����� Schlussbemerkungen

Das pure Daten�ussparadigma �auch mit argument fetch � arbeitet nach demPrinzip der feink�rnigen Parallelit�t� also Parallelit�t auf Instruktionsebene�was theoretisch zur optimalen Auslastung der IPUs f�hrt� Jedoch l�sst dies dieScheduling Unit schnell zum Flaschenhals werden� da sie in der selben Zeit� in dern Befehle auf ebensovielen IPUs berechnet werden� den gesamten Signalverkehr�mind� �n�SD� Signale�� verarbeiten muss� um wieder genug aktive Instruktionenbereitstellen zu k�nnen� Dieser Flaschenhals wird durch die Partitionierung desProgrammes in Sequenzen zwar entsch�rft� aber das allerdings wirkt sich nat�rlichnegativ auf den erreichbaren Grad der Parallelit�t aus�

� Je gr�ber das Programm partitioniert wird� umso weniger Schedulingauf�wand besteht� umso geringer ist aber die Auslastung der IPUs �im Extrem�fall gibt es nur eine Sequenz� die auf einem Prozessor l�uft� der sich unterUmgehung der ISU alle weiteren Instruktionen selbst zuteilt�

� Je gr��er die Kapazit�t der ISU� desto mehr Signale k�nnen gleichzeitigbearbeitet und damit Instruktionen aktiviert werden� die parallel bear�beitet werden k�nnen� und desto geringer kann die Sequenzl�nge sein

Die Kapazit�t der IPU� die Kapazit�t der ISU und die Gr��e der Sequenzensind die Parameter� die die Leistung der Maschine bestimmen� und die im wei�teren besondere Anforderungen an die Compiler stellen � dies ist noch Gegenstandk�nftiger Forschung ���

F�r genauere Simulationsdaten siehe �� Kap���� ��� ��

�� SD � durchschnittliche Signaldicht pro Befehl

� Abschnitt �

��� Large Grain Data�ow Computing � Makro Data�ow

Die Grundidee des grobk�rnigen Daten�ussansatzes ist die Berechnung in zweigetrennten logischen Ebenen� Hierdurch ist die separate Behandlung von Berech�nungs� und Scheduling�Operationen m�glich� wobei angestrebt wird� durchZusammenfassen von voneinander abh�ngigen Operationen zu m�glichst gro�enBl�cken oder sogenannten Makros� die Komplexit�t des Programmes und damitden Schedulingaufwand relativ zur Menge der tats�chlich angestellten Berechnungoder Datenmanipultion zu minimieren � im Gegensatz zum feink�rnigen DF�Schema� Beiden Ebenen liegen verschiedene Berechnungsmodelle zugrunde� aufder unteren Ebene �ndet die Bearbeitung der Operationen innerhalb der Bl�ckenach dem Steuer�ussprinzip statt� w�hrend die Verwaltung und Zuweisung derBl�cke auf der h�heren Ebene nach dem Daten�ussprinzip geschieht�

Um dies zu erm�glichen� sind folgende Betrachtungen n�tig�

� die Aufbereitung des Programmes in einen Large Grain Data�owGraph

� der Entwurf einer Architektur f�r das zweischichtige Berechnungs�modell

����� Large�Grain Data�ow Graph

��� de�niert den LGDG als Tupel �O�C�D�B� aus folgenden Komponenten�

� O � Menge der Operationsknoten� die Berechnungen und Datenmanipula�tionen ausf�hren

� C � Menge der Steuerknoten �control nodes� zur Steuerung des Daten��usses

� D � Menge der gerichteten Kanten� die Datenports von Knoten verbinden

� B � Menge der gerichteten Kanten� die Steuerports von O�Knoten mitdenen von C�Knoten verbinden

Daten �ie�en also nur entlang von D�Kanten�Im folgenden wird der Begri� des sogenannten Basisblocks �basic block� ein�

gef�hrt� Dieser ist eine Folge von Instruktionen� die nur mit der ersten beginnendals ununterbrochene Sequenz ausgef�hrt werden und nicht mit einem Sprungbe�fehl enden� Ein solcher Block kann in einen O�Knoten des LGDG gepackt werden�und wird als Ganzes an ein Prozessorelement zu Berechnung �bergeben� DieInstruktionen innerhalb des Blocks verf�gen im allgemeinen �ber eine hohe Loka�lit�t� das bedeutet� dass die Daten� auf die w�hrend der Bearbeitung zugegri�enwird� im lokalen Speicher gehalten werden k�nnen und die Abarbeitung derSequenz innerhalb des Prozessorelements sehr e�ektiv nach dem Steuer�ussprinzipgeschehen kann�

Nach ��� gilt als Ausgangspunkt f�r die Erstellung eines LGDG ein Programmin einer imperativen Programmiersprache� Dieses sequenzielle Programm wird ineinen sequenziellen LGDG umgewandelt� einen sogenannten straight�line LGDG �

Hybride Architekturen �

In einem in ��� beschrieben Algorithmus wird die Erarbeitung eines solchenGraphen durch Au��sung der bedingten Spr�nge� Zusammenfassung von Opera�tionen und der Einf�hrung von Switch und Merge�Knoten detailliert beschrieben�

O1

C1swit ch

O2

C2swit ch

C2mer ge

O−node

C−node

D−ar c

B−ar c

Abbildung � straight�line LGDG

Ein straight�line LGDG enth�ltvorerst keine explizit parallel ausf�hr�baren Segmente� diese k�nnen jedochdurch eine globale Analyse der Daten�abh�ngigkeiten identi�ziert und paral�lelisiert werden� Auch diese Methodender Daten�uss�Analyse werden inKapitel � von ��� ausf�hrlichbeschrieben�

Einige Eigenschaften und daraus resultierende Vorteile der LGDG sind�

� klare Trennung der signi�kanten Operationen �O�Knoten� von den Schedu�ling�Vorg�ngen �C�Knoten� � daraus folgt�

� alle Operationen zur Datenmanipulation �nden auf dem Knoten�Level statt� und ein phyischer Datentransport zwischen denSchichten ist unn�tig� Signale zum Anzeigen der Datenverf�gbarkeitgen�gen

� da auf der Knotenebene nach dem von Neumann�Prinzip gearbeitetwird� k�nnen klassische Speichertechniken und globaler speicherals shared memory zum Ablegen der Daten verwendet werden � dieswirkt sich vor allem auf die e�ektive Implementierung von Daten�strukturen aus

� tempor�re Namen �compilergeneriert� werden ausschliesslich innerhalbeines O�Knotens benutzt� das hei�t� sie m�ssen bei einem Kontextwechselweder �bertragen noch gespeichert werdem� was den Aufwand und dieNetzwerkbelastung erheblich verringert

�� Abschnitt �

����� LGDG�Architektur

Das Schema der zweischichtigen Verarbeitung setzt eine ebenso in zwei Ebenengeteilte Architektur voraus� bestehend aus�

� Knoten�Schicht �node level�� wo die Operationen �o�nodes� ausgef�hrtwerden

� Graph�Schicht �graph level�� wo entschieden wird� welche O�nodes aktiviertweden

Beide Schichten operieren asynchron und werden nur durch Token�Queues�FIFO�Pu�er zum Ausgleich unregelm�ssiger Token�Ankunfts� und Konsumie�rungsraten� koordiniert�

Die Knotenschicht besteht aus mehreren Prozessormodulen � ��� nach ����und einem globalen Speicher� Der Speicher enth�lt globale Variablen und Daten�stukturen� Prozessormodule und Speicher sind �ber ein Interconnection�Netzwerkverbunden� w�hrend ein separates Netzwerk zur Verteilung der Token zur Vef��gung stehen muss � der Token�Bus�

Ein Prozessorelement besteht aus einem Knotenprozessor� lokalem Speicherund Befehlsspeicher� einigen speziellen Co�Prozessoren und Token�Queues zurKommunikation� Jeder Knotenprozessor besteht aus � Teilen�

� dem Befehlsprozessor� der die eigentlichen Maschinenbefehle ausf�hrt

� der Instruction�Queue als Pu�er und

� dem Prefetcher � dieser hat die Aufgabe� die Eingangs�Token�Queue zulesen� die erste Instruktion der O�node in die Instruktion�Queue zu setzenund damit den Kontextwechsel einzuleiten� daraufhin die folgenden Befehledes O�node�Rumpfes aus dem Speicher in die Queue zu �bertragen� bis einEnd�Marker gelesen wird� und dann zum n�chsten Token �berzugehen ���

Die Graph�Schicht beherbergt die Einheiten� die die Operationen auf demDaten�ussgraphen ausf�hren� die Matching Unit und den Instruction Store� Letz�terer ist eigentlich eine normale Speichereinheit� ausgelegt als pseudo�assoziativerSpeicher� der die zu aktivierenden Makro�Instruktionen enth�lt� die mit den ver�f�gbaren Operanden zu aktivierten Token verkn�pft und �ber den Token�Bus zurKnotenschickt �bergeben werden� Die Verf�gbarkeit der Operanden wird in derMatching Unit festgestellt� Alle Input�Token werden in der Matching Unit zwi�schengespeichert� bis �bereinstimmungen anhand der Namen der Zielinstruk�tionen gefunden sind � daraufhin werden die Operandenpaare zum InstructionStore �bergeben�

��� enth�lt noch die Beschreibung einiger Optimierungen� unter anderem dieZerlegung aller O�nodes zu O�nodes mit maximal � Operanden� die M�glichkeitdes Bypassing der Matching Unit durch Token mit nur einem Operanden �diesofort aktivierbar sind� und die Methoden der node migration �Verlagerung vonKnoten vom graph�level� zum node�level�code� und node aggregation �Zusammen�fassung von Knoten�� um den Graphen noch weiter zu vereinfachen� ohne jedochdie Semantik des Original LGDG zu �ndern�

Hybride Architekturen ��

Cl ust erMemor y

I nt er connecti on Net wor k

Token Bus

I nst r ucti on St or e

Lokal er Spei cher

Bef ehl s−spei cher

I nst r ucti onPr ocessor

I nst r ucti onQueue

Pr ef et cher

Pr ozess or−Modul i −1

Pr ozess or−Modul i +1

Mat chi ng Unit

Gr aph Unit

Node Level

Token Queue

Co−Pr ozessor en

Token Queue Token Queue

Token QueueToken Queue

Abbildung ��� LGDG�Architektur

�� Abschnitt �

����� Schlussbemerkungen

Durch die Partitionierung der Daten�ussgraphen und der daraus folgendenReduzierung der Token�Anzahl wird in dieser Architektur vermieden� dass dieMatching Unit zum Flaschenhals des Systems wird�

Parallelit�t wird im Unterschied zu den feink�rnigen Daten�ussans�tzen hiernicht auf der Ebene der arithmetischen Ausdr�cke� sondern auf unterster Befehl�sebene durch exzessives Pipelining in den Prozessorelementen realisiert� Aufgrundder Tatsache� dass den Pipelines ausschliesslich aktivierte Basisbl�cke zugef�hrtwerden� ist sogar ideales Pipelining realisierbar� da diese Bl�cke nicht unter�brechbar sind und keine Steuerbefehle �Spr�nge� ect� � enthalten� die L�cken inder Pipeline verursachen oder komplizierte Mechanismen wie Sprungvorhersagenn�tig machen w�rden�

Eines der kritischsten Probleme des Daten�ussansatzes� der e�ektive Kontext�wechsel� wird hier durch die besonderen Eigenschaften der Basisbl�cke�O�Knotenumgangen � Datenwiederherstellen und �speichern bei Start� oder Ende einesBasisblockes ist unn�tig und die Umgebungsinformationen werden mit demResult�Token zur n�chsten Activity gesandt�

Ein weiteres bekanntes Problem mit shared memory bei Multiprozessor�Maschinen ist die potenzielle Inkonsistenz des Speicherinhaltes beim unsynchroni�sierten Zugri� mehrerer Prozessoren auf dieselbe Speicherzelle� Dieses Problemwird durch die innewohnenden Eigenschaften des Daten�ussmechanismus aufhoher Ebene unterbunden � dieser stellt sicher� dass gleichzeitig laufende Befehls�str�me immer datenunabh�ngig voneinander sind und das abh�ngige Befehle erstmit der Verf�gbarkeit der Daten aktiviert werden k�nnen�

Hybride Architekturen ��

��� Threaded Data�ow � �Process Orientated Data�owSystem� PODS

Eine prozessorientierte Sichtweise erlaubt es� ein Daten�ussprogramm als eineSammlung von miteinander kommunizierenden Prozessen auszuf�hren� Jedergegebene Daten�ussgraph kann in ein oder mehrere leichtgewichtige Prozesse��hnlich Threads� zerlegt und einzelnen verf�gbaren Prozessorelementen zuge�wiesen werden� Jeder Prozess wird solange ausgef�hrt� wie Operanden f�r dieaktuelle Operation verf�gbar sind� Produziert eine Operation ein Ergebnistoken�was von einer folgenden Operation im gleichen Prozess benutzt wird� wird esdirekt und lokal per einfacher Speicheroperation zum Slot des Zieloperanden �ber�geben� Nur wenn das Token eine Operation eines anderen Prozesses zum Ziel hat�muss es den Weg durch die Matching Unit nehmen ��� �� Kap���

����� Architekturen

F�r PODS existieren � Ans�tze�

� eine simulierte Spezial�Architektur als MIMD�Maschine mit verteiltemSpeicher

� eine Hypercube�Implementation mir �� Prozessoreinheiten� die bis auf dasRouting alle obengenannten Funktionalit�ten besitzen � das Routing �ber�nimmt eine spezielle Kommunikationshardware

Local I− St r uct ur eMemor y

Mem.Manager

Executi on Unit

Routi ngUnit

Mat chi ngSt or e

Arr ayMngr

Local I− St r uct ur eMemor y

Mem.Manager

Executi on Unit

Routi ng Unit

Mat chi ngSt or e

Arr ayMngr

Abbildung ��� abstrakte PODS�Architektur

Jede Prozessoreinheit verf�gt neben der Recheneinheit f�r Bearbeitung derProzesse und Ausf�hrung der Kontextwechsel �ber eine Routing Unit� einen Mat�ching Store� einen Speichermanager und einen Arraymanager� der unabh�ngig von�und anstelle� der Recheneinheit lokale Arrayzugri�e vornimmt und entfernteLeseoperationen bedient�

�� Abschnitt �

����� Partitionierung des Daten�ussgraphen

In einem Daten�ussgraphen wird duch einen Bogen zwischen zwei Knoten �Opera�tionen� eine direkte Datenabh�ngigkeit der zweiten Operation vom Ergebnis derersten repr�sentiert� Daher ist es klar� dass beide Operationen niemals parallelausgef�hrt werden k�nnen� Aus dieser Beobachtung ergeben sich folgende Konse�quenzen�

� voneinander abh�ngige Operationen k�nnen auf derselben Recheneinheitausgef�hrt werden

� Daten �Operanden� k�nnen lokal �bergeben werden� unter Umgehung destypischen Tokenverarbeitungskreislaufes � direct token recycling

Durch Ausweitung dieser Konsequenzen auf ganze Folgen von Daten�ussopera�toren l�sst sich verallgemeinernd jeder Pfad durch einen Daten�ussgraph alssequentielle Folge von Operationen darstellen� jede derer von ihrem Vorg�ngerabh�ngig ist und ohne Verlust der Parallelit�t sequenziell ausgef�hrt werden kann�Diese sequenziell ausf�hrbaren Pfade durch den Daten�ussgraphen werden alssequentielle Codesegmente �SCS � sequential code segments� bezeichnet ��Kap��� �

Folgende Abbildungen zeigen den Daten�ussgraphen f�r das Programmfrag�

ment

��B � B

�� �AC

p �

�Aund ein m�gliches Set von SCS�

Sqr Mul Mul

Sub Mul

Sub Sqrt

Add Sub

Di v Di v

BB AA CC

44 22

Abbildung ��� Daten�ussgraph

SqrMul Mul

SubMul

Sub

Sqrt

Add

Sub

Di v

Di v

BB AA CC

44 22

BB AA

SCS1 SCS2 SCS3 SCS4

Abbildung ��� Sequentielle Code�Segmente

Hybride Architekturen ��

����� Scheduling der SCS

Anstatt jede Operation einzeln zu verwalten� wird auch hier das daten�ussgesteu�erte Scheduling auf die Ebene der SCS verlagert� Hier werden die einzelnen SCSnach dem Vorbild der Prozesszustandsmodells gesteuert�

Ein SPS gilt als passiv � solange sein erster Operator inaktiv ist� d� h� nochnicht alle Operanden bereitstehen� und verbleibt im Programmspeicher� Sobaldalle Operanden f�r die erste Operation verf�gbar sind� wird der gesamte SPSaktiv und� mit einem einfachen Prozesskontrollblock �PCB� versehen� als soge�nannter subcompact process �SP� in den Befehlsspeicher geladen� Der PCBenth�lt die Startadresse des SCS im Befehlsspeicher� einen Befehlsz�hler f�r dieaktuelle Instruktion innerhalb des SCS und ein Statusfeld f�r den Prozesszustand�Folgende drei Prozesszust�nde sind de�niert�

� ready � SP ist aktiv� aktueller Befehl hat alle Operanden� aber es ist keineProzessoreinheit frei

� running � eine Prozessoreinheit f�hrt Befehle dieses SP aus

� blocked � der aktuelle Befehl ist nicht ausf�hrbar �es fehlt mind� � Ope�rand�

r unni ng

r eady bl ocked

dest r oyed

i nac ti ve

akt uell er Bef ehlbekommt l et z t enOper anden

Pr ozess or−ei nheit fr ei

l et z t er Bef ehl desSCS abgear beit et

er st er Bef ehlbekommt l et z t enOper anden

akt uell er Bef ehlni cht ausf ü hr bar

Abbildung ��� SP�Zustands�berg�nge

Nebenstehende Abbildung zeigt

den Zustandsgraphen� Zu Anfang wirdein SP in den Befehlsspeicher geladenund be�ndet sich im ausf�hrungsbe�reiten Zustand� Sobald ein Prozessorfrei wird und mit der Abarbeitungeines SP aus dem Befehlsspeicherbeginnt� �ndert sich dessen Zustandauf running � Dieser h�lt an bis� ent�weder� der letzte Befehl abgearbeitetist und der SCS terminiert oder� einBefehl nich wegen fehlender Ope�randen noch nicht ausgef�hrt werdenkann� In letzterem Fall wechselt derProzesszustand zu blockiert und derSP verweilt im Befehlsspeicher� bis dieAnkunft des Operanden den Zustandwieder auf bereit �ndert �� Kap��� �

����� Programm� und Daten�Partitionierung

Um einen Daten�ussgraphen auf ein Multiprozessorsystem zu �bertragen� m�ssenzwei grunds�tzliche Aufgaben gel�st werden�

�� den Graph in optimale Sequenzen zerlegen

�� die Sequenzen den Prozessorelementen zuweisen

�� Abschnitt �

Die Partitionierung des Graphen erfolgt durch einen Tiefen�F�rbungs�Algo�rithmus� der ein Set von SCS erzeugt� die vorerst noch zu klein sind und zur wei�teren Reduzierung der Kommunikationslast gruppiert werden m�ssen� DieserGruppierungsprozess ist ein NP�vollst�ndiges Problem� daher werden iterativ Heu�ristiken angewandt� um die gr��e der SCS schrittweise an die Architektur desSystems anzupassen� Hierbei werden

� die Zahl der Prozessorelemente

� die Leistung der einzelnen Prozessorelemente

� die Kommunikationskosten

� die Netzwerktopologie und �geschwindigkeit und

� die Kosten f�r Kontextwechsel

in Betracht gezogen� Die Formulierung von optimalen Partitionierungsregeln istnoch Gegenstand der Forschung �� Kap��� �

Die Abarbeitung von Programmschleifen �ndet Beobachtungen zufolge meistinnerhalb eines SPs statt und kann

�� r�umlich �ber mehrere Prozessorelemente �dies bedeutet� dass der SP beiinneren Schleifen zu einem rein sequenziellen Ablauf degeneriert�� oder

�� zeitlich �ber mehrere Iterationen veteilt werden �das bietet sich besondersbei Arrayzugri�en an�

�hnlich wichtig ist wie die Partitionierung des Programmes die Aufteilunggro�er Datenstrukturen wie Arrays� um ein optimales Verh�ltnis zwischen Kom�munikationsaufwand und Datenparallelit�t zu erhalten� F�r Arrays wird dasPrinzip der einfachen Zuweisung f�r I�Structures �single�assignment principle

nach Arvind� ausgenutzt� dies garantiert� dass nur genau eine Instruktion einArrayelement schreiben kann� Hier wird nun versucht� jedes Arrayelement auf dieselbe Prozessoreinheit zu �bertragen� wie die Instruktion� die darauf zugreift� Soerh�lt jedes Prozessorelement ein Teil des Array� auf das kein anderes Prozessor�element zugreifen kann� F�r weitere Details zum Thema Array�Partitionierungsiehe �� Kap��� � On Array Partitioning on PODS �

����� Schlussbemerkungen

Das grundlegende prozessorientierte Daten�uss�Modell hat folgende Vorteile�

� die F�higkeit� zu einer von Neumann�Maschine zu degenerieren �wennm�glich�

� die Reduzierung der Anzahl der Token� die durch Matching Unit und Inter�prozessornetzwerk bew�ltigt werden m�ssen� durch Benutzung der SPs

� innerhalb eines SP ist das instruction fetching und die Ausf�hrung so e��zient� wie bei einer typischen von Neumann�Architektur m�glich� vor allem�wenn Schleifen vollst�ndig innerhalb eines Porzesses liegen

Hybride Architekturen ��

� f�r Programme ist u�a� die Anzahl der verf�gbaren Prozessoreinheiten zuvernachl�ssigen� die Graph�Partitionierungs�Phase kann die SPs an die spe�zi�sche Architektur anpassen �� Kap���

� Abschnitt �

� Zusammenfassung und Ausblick

��� Zusammenfassung

Die drei vorgestellten Ans�tze zeigen einige Schritte auf� die zur Vereinigung vonSteuer�uss� und Daten�uss�Konzepten unternommen wurden�

Das erste und zugleich �ltste Modell zeigt� dass man eine reine Daten�ussma�schine leicht modi�zieren kann� um erstens die Befehlsabarbeitung nach dem vonNeumann�Prinzip m�glich zu machen und damit einfache Steuer�ussprozessorenals Berechnungselemente in ein Daten�uss�System integriert werden k�nnen� undzweitens� dass mit einigen �nderungen auch sequenzieller Code e�ektiv abgear�beitet werden kann�

Die Wichtigkeit der Trennung zwischen Ausf�hrung und Scheduling �ndet imLarge Grain DF und im Process Orientated DF eine zentrale Bedeutung� BeideAns�tze beruhen auf der Einf�hrung zweier logischer Berechnungsebenen� die denbeiden verschiedenen Paradigmen unterliegen� Ressourcenverwaltung und Zuwei�sung von Programmsequenzen an die Berechnungselemente geschieht nach demDaten�u�prinzip� wodurch eine volle Ausnutzung der parallel nutzbaren Res�sourcen gew�hrleistet wird� Die eigentliche Berechnung und Datenmanipulationinnerhalb der Programmsequenzen geschieht auf jedem Prozessorelement nachdem Steuer�ussprinzip� Daraus ergeben sich die Vorteile� dass die Optimierungendes von Neumann�Verfahrens� wie zum Beispiel Pipelining� Caching und Prefet�ching� ohne Seitene�ekte angewandt werden k�nnen� Au�erdem verbleiben lokaleDaten im lokalen Speicher� bis die Sequenz beendet und ein Kontextwechsel erfor�derlich ist�

Nat�rlich gibt es Unterschiede zwischen LGDF und PODS � die Partitionie�rung des Daten�ussgraphen� Beim LGDF geschieht sie eher horizontal bestehendeCodesequenzen werden zu nicht interkommunizierenden Bl�cken zusammenge�fasst� PODS dagegen zerlegt den Daten�ussgraphen vertikal in interkommunizie�rende Threads� Die Bl�cke des LGDF werden nichtblockierend abgearbeitet� dadie Instruktionen innerhalb keine externen Datenabh�ngigkeiten mehr besitzen�Im Gegensatz dazu werden die Threads des PODS immer dann blockiert und ver�dr�ngt� wenn Datenabh�ngigkeiten auftreten� bis diese erf�llt sind�

Die vorgestellten Ans�tze sind in erster Linie als Simulation oder Prototyp f�rForschungszwecke implementiert worden� Das Hauptproblem bestand immer inder Scha�ung eines geeigenten Compilers� der in der Lage ist� beliebige Pro�gramme in architektur�optimierten Code umzuwandeln�

Dennoch sind die Erkenntnisse der Forschung im Bereich der hybriden Daten��ussarchitekturen in die Generationen aktueller Universalprozessoren eingegangenund geben Ausblicke f�r zuk�nftige Forschungen im Bereich der Parallelverarbei�tung�

Zusammenfassung und Ausblick �

��� Ausblick � Multithread�Architekturen

Basierend auf der Erkenntnis� dass Daten�uss� und Steuer�uss�Modell keineUnvereinbarkeiten darstellen� wurden viele der Grunds�tze des reinen Daten�uss�Modells durch konventionellere Ideen ersetzt� Zur gleichen Zeit hielten Daten�uss�Techniken Einzug in die von Neumann�Berechnungsmodelle� Basierend auf diesenMischformen bildete sich innerhalb des Kontinuums das Konzept des Multithrea�ding heraus� mit einigen theoretisch und kommerziell fruchtbaren Vorteilen�Multithread�Architekturen k�nnen vorerst in zwei Gruppen eingeteilt werden�Architekturen mit nichtblockierenden und blockierenden Threads� Die Architek�turen mit nichtblockierenden Threads werden allgemein korrekter als die LGDF�Architekturen bezeichnet� da ihnen des Daten�ussparadigma zugrunde liegt�w�hrend die eigentlichen Multithreading�Architekturen von RISC oder superska�laren RISC abstammen� Multithread�Prozessoren besitzen mehrfache Register�s�tze� um die Kontexte mehrere Threads gleichzeitig speichern und das ContextSwitching extrem schnell �� Prozessorzyklus� durchf�hren zu k�nnen� Wird dieAusf�hrung eines Threads durch Speicherlatenz oder synchronisationsbedingteWartezeiten blockiert� wird die Zeit mit der Ausf�hrung eines anderen Threads�berbr�ckt� Bez�glich der Thread�Scheduling�Verfahren k�nnen � Architekturva�rianten unterschieden werden� cycle�by�cycle�interleaving � block�interleaving undsimultaneous multithreading� ���� Diese Architekturen setzen eine sehr komplexeHardware voraus ����

Aktuelle Forschungen streben eine Kombination von superskalarer Hardwaremit daten�ussgesteuerten nichtblockierenden Threads an � das ganze ist unterdem Namen Scheduled Data�ow bekannt�� Da diese Architektur im Gegensatzzu den normalen Superskalar�Architekturen auf Mechanismen wie out�of�order�execution verzichtet und die entsprechende Hardware durch zus�tzliche Register�s�tze und Funktionseinheiten ersetzt� wird die Parallelit�t auf Thread�Ebene nocherh�ht� Eine weitere signi�kante Eigenschaft dieses Ansatzes ist die Entkopplungvon Ausf�hrung und Speicherzugri�en� Wie die Analysen in ��� zeigen� ist Sche�duled Data�ow im Vergleich mit der superskalaren Architektur ohne out�of�order�execution leisungsf�higer� verliert diesen Vorsprung aber im Vergleich mit einersuperskalaren Architektur mit out�of�order�execution� Der R�ckstand ver�schwindet wiederum� wenn beide Architekuren skaliert werden� Zus�tzlich bietetScheduled Data�ow noch Raum zur Implementation von Sprungvorhersagemecha�nismen und spekulativer Befehlsausf�hrung� sowie Befehlssatz� und Compileropti�mierungen� und verf�gt somit �ber ein hohes Potenzial� viel leistungsf�higer alsdie komplexesten Superskalar�Architekturen zu werden�

�� f�r Details zu den Multithreading�Architekturen � siehe �

�� leider ist dem Autor dieser Arbeit die entsprechende Quelle erst zu sp�t zug�nglichgeworden� sonst w�re das Thema mit Sicherheit im Detail behandelt worden ���

�� Abschnitt �

Abbildungsverzeichnis

Steuer�uss f�r a b�a

c

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

prinzipielle von Neumann�Maschinenstruktur

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

Daten�uss�Graph f�r a b�a

c

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

prinzipielle DF�Maschinenstruktur �hier dynam� DF� ��

� � � � � � � � � � � � � � � � � � � � � � � � � � � � �

Speedup vs� Overhead �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �abstrakte DF�Architektur � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��Programm�Tupel f�r z� a

�� b

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��hybride Architektur � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��straight�line LGDG � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��LGDG�Architektur � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��abstrakte PODS�Architektur � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��Daten�ussgraph � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��Sequentielle Code�Segmente � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��SP�Zustands�berg�nge � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

Literaturverzeichnis

�� A�R�Hurson B� Lee� Data�ow architektures and multithreading� IEEE � ��� �

�� Kechang Dai� Large�grain data�ow computation and its architektural support� �����Dissertation� TU Berlin�

�� Robert A� Iannucci� Parallel Machines� Parallel Machine Languages � The Emergence

of Hybrid Data�ow Computer Architektures � Kluwer Academic Publishers� �����

�� L� Bic J� Gaudiot� Advanced Topics in Data�ow Computing � Prentice�Hall� Inc�� �����

�� Theo Ungerer J� Silc� Borut Robic� Asynchrony in parallel computing� From data�owto multitreading� http���edok���tib�uni�hannover�de�edoks�e�������������pdf�

�� J� Arul K�M� Kavi� R�Giorgi� Scheduled data�ow� Execution paradigm� architectureand performance evaluation� IEEE Transactions On Computers Vol��� � �����

Literaturverzeichnis ��