&Inhalt 1 Einleitung 2 1.1 Abstract 2 1.2 Die zugrunde liegende Hardware 2 1.3 Das Bildgenerierungsprogramm 2 1.4 Motivation der direkten Programmierung 3 2 Der Knotenrechner 4 2.1 Struktur 4 2.2 Datenkonsistenz 4 2.3 Projektion des Programmes auf die Hardware 4 3 Betriebssystem 7 3.1 Schnittstelle vom Modul zum Kernel 7 3.1.1 Beschreibung der einzelnen Syscalls 9 3.2 Schnittstelle vom Modul zum Master (allgemein) 10 3.3 Schnittstelle vom Modul zum Master (konkret) 10 4 Algorithmen 12 4.1 Vektortransformation 12 4.2 z-Puffer Algorithmus 13 4.3 Sutherland Hodgman Clipping 14 5 Der Prozessor i860 und einige Anmerkungen zum konkreten Einsatz. 16 5.1 Allgemeine Beschreibung 16 5.1.1 Überblick 16 5.1.2 Befehle 16 5.1.3 Die einfache Einheit 17 5.1.4 Fließkommaeinheit 17 5.1.5 Grafikeinheit 17 5.1.6 Memory Management Unit (MMU) 18 5.1.7 Parallele Architektur 18 5.1.8 Software Entwicklungsumgebung 19 5.2 Datentypen 20 5.2.1 Integer, Ganze Zahlen mit Vorzeichen 20 5.2.2 Kardinale Zahlen ohne Vorzeichen 20 5.2.3 Fließkommazahlen, "einfache Genauigkeit" (single precision) 20 5.2.4 Fließkommazahlen, "doppelte Genauigkeit" (double precision) 20 5.2.5 Pixel (Bildpunkte) 21 5.3 Register 22 5.4 Caches 23 5.5 dual-instruction mode 24 5.5.1 Zusammenspiel von bestimmten Befehlen im dual-instruction mode 24 5.5.2 Einschränkungen bei der Verwendung des dual-instruction mode 24 5.6 Beschreibung des Befehlssatzes des i860 im einzelnen. 26 5.6.1 einfache Befehle 27 5.6.2 Fließkomma- und Grafikbefehle 49 5.6.3 Sonstige Befehle 67 6 Vektortransformation lmtransf 68 6.1 Division durch Null 68 6.2 Detailbeschreibung der Prozedur lmtransf und des Optimierungsvorganges. 68 6.2.1 Sonderfall ohne Division 68 6.2.2 Normalfall mit Division 72 7 z/p-Puffer Routine zpbuf 78 7.1 Datenformat 78 7.2 Detailbeschreibung 78 7.2.1 Clippingschleife 80 7.2.2 Zeilenweise scannen 82 8 Schnittstellenroutine Radiosity 95 9 Programmteil Raytracing 101 E.1 Compiler 102 E.2 Intel 102 E.3 Literatur 102 &Einleitung 1 Einleitung 1.1 Abstract Auf einem Knotenrechner (Prozessoren i860 durch einen Ring verbunden) wird ein Bildgenerierungssystem (Objecttracer) implementiert. Aufgrund der mangelhaften Optimierungsfähigkeiten des Compilers sollen die rechenaufwendigen Kernschleifen direkt in Assembler programmiert werden, mit besonderem Augenmerk auf Geschwindigkeitssteigerung. Konkret sind dies eine Routine zur Vektortransformation anhand einer Matrix und eine z-Puffer-Routine zum Zeichnen von sich räumlich überlappenden Polygonen in der Ebene. 1.2 Die zugrunde liegende Hardware Ein Knotenrechner mit mehreren RISC-Prozessoren soll zur Generierung von Bildern eingesetzt werden. Der Knotenrechner besteht aus einzelnen Knoten, die jeweils ein eigenes RAM und bis zu drei Prozessoren des Typs i860 enthalten. Die Knoten sind durch eine Ringstruktur verbunden, in der sich außerdem noch ein Knoten mit einem m68030 befindet. Abgesehen von der parallelen Anordnung mehrerer Prozessoren im Knotenrechner weist der Prozessor i860 selbst Parallelitätseigenschaften auf, und zwar auf der Befehlsebene. Der i860 besteht aus zwei Verarbeitungseinheiten, nämlich einer Kerneinheit, die Befehle holt und einfache Befehle ausführt, und einer Fließkomma- und Grafikeinheit. Die Fließkomma- und Grafikeinheit besteht ihrerseits wieder aus je einer Einheit fuer Addition, Multiplikation und Grafik. Da die vier Einheiten größtenteils unabhängig sind, können sie gleichzeitig arbeiten. Diese Möglichkeit wird durch die besondere Gruppe der dual-operation-Befehle unterstützt, die gleichzeitig die Additions- und Multiplikationseinheit bedienen, sowie durch das Verbinden je eines Fließkomma- oder Grafik- und eines einfachen Befehls im dual-instruction-mode, so daß bis zu drei Operationen unter einigen Bedingungen in einem Zyklus ausgeführt werden können. Die meisten Befehle der Fließkommaeinheiten sind in Pipelines von ein bis drei Stufen ausführbar. Ebenso sind Ladebefehle in Pipeline ausführbar. Hinzu kommt, daß die meisten Befehle in vielen Situationen überlappend ausgeführt werden, so daß bei der Programmierung durch geschickte Anordnung der Befehlsfolge viel Rechenzeit gespart werden kann. 1.3 Das Bildgenerierungsprogramm Das zu implementierende Programm, der Objecttracer, kombiniert die Verfahren Radiosity und Raytracing. Es soll ein möglichst realistisches Bild einer virtuellen Szene erzeugt werden. Dazu werden den im Raum angesiedelten Objekten zunächst Beleuchtungsstärken zugeordnet, die angeben, wieviel Licht auf das entsprechende Objekt fällt (Radiosity). Ist eine feste "Lichtmenge" (min_light) an die Objekte verteilt, wird vom Betrachter ausgehend jeder Bildpunkt in die Szene verfolgt und gemäß des Ursprungs des gedachten Strahls gefärbt (Raytracing). Rechenleistung durch den Knotenrechner ist vor allem für zwei Berechnungen gefragt: Transformation von Vektorlisten an einer Matrix und Zeichnen von Dreiecken nach dem z-Puffer Algorithmus. radiosity: b_p := brightest_polygon (objects); min_light := b_p / 10; while b_p > min_light do matrix := f (b_p); *1 objects[view] := lmtransf (matrix,objects[world]); *2 z_buf := infinite; *3 p_buf := 0; *4 zp_buf := zpbuf (objects[view]); *5 emmiting_light (objects) := sum (p_buf;p_buf = object); nonemitted_light (b_p) := 0; b_p := brightest_polygon (objects); end; tracer: matrix := f (view); *1 objects[view] := lmtransf (matrix,objects[world]); *2 z_buf := infinite; *3 p_buf := 0; *4 zp_buf := zpbuf (objects[view]); *5 plist := f (p_buf); while plist.object do tracer (plist.object); plist := plist.next; end; show (plist); Die für die Ausführung in den i860-Knoten gedachten Programmteile sind jeweils mit *1..*5 gekennzeichnet. Es sind die Teile des Programmes, die mit relativ wenig Ein- und Ausgabedaten auskommen und dabei eine hohe Rechenleistung erfordern. Neben den nicht transformierten Koordinaten (objects [world]), die für jeden Durchlauf der Sequenz gleich bleiben, muß nur die Matrix immer neu übergeben werden. Ausgabe ist in beiden Fällen eine Liste von Objektnummern mit eventuell zusätzlichen Angaben (plist oder emmiting_light). Die rechenintensiven Prozeduren hierbei sind die Transformation der Vektoren "lmtransf" und das Zeichnen der Objekte "zpbuf". 1.4 Motivation der direkten Programmierung Der i860 ist ein RISC-Prozessor und dementsprechend hat sich der Programmierer um die ordnungsgemäße Nutzung der Parallelitätseigenschaften selbst zu kümmern. Da beim i860 hier besonders viele Ausnahmen und spezielle Effekte zu beachten sind, ist es sehr schwer, einen allgemeinen und doch voll optimierenden Compiler zu erstellen. Und da sich offenbar noch niemand mit Erfolg an diese Aufgabe gewagt hat, ist eine volle Ausnutzung der Rechenleistung nur durch explizite Optimierung des Programmes auf Assemblerebene möglich. In einem Punkt ist eine Optimierung übrigens dennoch gescheitert. Bei dem Versuch, den Daten-Cache optimal auszunutzen, ist deutlich geworden, daß es schlicht unmöglich ist, das Verhalten der Caches des i860 berechenbar zu machen oder in sinnvoller Weise zu beeinflussen. Sogar ein Cache-Flush erfordert einen hohen Aufwand an Rechenleistung und der Cache ist im Betrieb wegen der schlechten Ersetzungsstrategie nur zu etwa 50% ausgelastet. Daher wurde auf eine Optimierung bezüglich der Cachestruktur verzichtet. &Knotenrechner 2 Der Knotenrechner 2.1 Struktur Zunächst besteht der Rechner aus einer Anzahl von Knoten. Die einzelnen Knoten sind untereinander durch eine Ringstruktur verbunden (Bild 2.1). Dazu befindet sich auf jedem Knoten eine FIFO-Registerbaugruppe (first-in-first-out), die vom im Ring vorangehenden Knoten Daten übernehmen und an den im Ring nachfolgenden Knoten weiterleiten kann. Die Daten können vom Prozessor des Knotens entnommen werden und es können neuen Daten in die FIFO eingereiht werden. Der Knoten selbst enthält bis zu drei Prozessoren des Typs i860, die gemeinsam auf einen RAM-Arbeitsspeicher zugreifen (Bild 2.2). Die gemeinsamen Arbeitsspeicher fassen in der vorliegenden Version vier Megabyte. Da diese jedoch für drei Prozessoren und zusätzlich diverse Verwaltungsaufgaben ausreichen müssen, sollte im Entwurf der Algorithmen mit einem allein verfügbaren Speicher von etwa einem Megabyte gerechnet werden. 2.2 Datenkonsistenz Von den bis zu drei Prozessoren je Knoten muß sich mindestens einer, am besten genau einer, um die Kommunikation auf dem Ring kümmern. Da dieser Prozessor auch die Daten für die beiden anderen Prozessoren auf dem selben Knoten empfängt und versendet, greifen verschiedene Prozessoren auf den gleichen Bereich des Arbeitsspeichers zu. Es kommt also vor, daß ein Prozessor Datenbereiche mehrfach liest, die von einem anderen Prozessor zwischenzeitlich verändert worden sind. Da die Prozessoren i860 mit internem Daten- und Befehlscache ausgestattet, jedoch nicht des bus-snoopings (Abhorchen der Busaktivitäten) befähigt sind, kann es hierdurch zu Inkonsistenzen kommen. Aus diesem Grund ist es notwendig, die von mehreren Prozessoren gemeinsam genutzten Bereiche durch das Betriebssystem als nicht in den Cache einzutragen zu kennzeichnen, und zwar in allen der drei beteiligten Prozessoren. Zu diesen Bereichen gehört ein Pufferbereich, in dem eingehende Nachrichten und Daten von anderen Prozessoren abgelegt werden. Das gleiche Problem ergibt sich, wenn über den Ring ein Programmteil in den Knoten geladen wird. Die Speicherstellen, die gerade mit dem neuen Programmteil geladen werden, können schon im Befehlscache desselben oder eines anderen Prozessors eingetragen sein. Auch hier sollten alle für Programme vorgesehenen Bereiche von vorn herein für Cachezugriffe gesperrt sein. Das hieße allerdings, daß der Befehlscache nie zum Einsatz kommen würde. Daher wäre es sinnvoll, die Programmteile nach dem Laden für den Cache freizugeben und vor dem Start auf allen Prozessoren einen Cacheflush (Cache löschen) zu initieren. 2.3 Projektion des Programmes auf die Hardware Es wäre möglich, die Ringstruktur des Rechners einfließen zu lassen in den Entwurf des Algorithmus. Beispielsweise könnte ein Prozessor die Transformation der Vektoren übernehmen und die transformierten Vektoren an den nächsten Prozessor im Ring weiterleiten, damit dieser seinerseits die erhaltenen Daten nutzt und den z/p-Puffer füllt. So könnte man jeweils zwei Prozessoren zusammenspannen. Dieses Verfahren ist jedoch nicht geeignet, die nicht näher bestimmte Anzahl der vorhandenen Prozessoren auszunutzen. Stattdessen wird für die Implementierung des Programmes von der tatsächlichen Struktur des Knotenrechners abstrahiert, und es wird eine Sternstruktur mit dem m68030 als Master und den i860'ern als Slaves angenommen (Bild 2.3). Ebenso werden sowohl das Radiosity-Programm als auch der Tracer so geteilt, daß das Programm vom Master bearbeitet wird, die aufwendigen Berechnungen aber als Teilaufgaben an die i860'er abgegeben werden (remote calls). In der Skizzierung der Programmteile unter 1.3 sind die Anteile für die i860'er jeweils mit Sternen markiert: Die Daten werden jeweils vom Master vor- und nachbereitet, die i860'er führen nur Teilschritte aus. & & Da mehrere Knoten und Prozessoren zur Verfügung stehen, müssen auch die Aufgaben für die i860'er aufgeteilt werden. Eine Möglichkeit im Fall Radiosity wäre, jeweils mehrere Beleuchtungssituationen nebeneinander zu berechnen. Dazu ist es nötig, jeweils einen kompletten z/p-Puffer im Speicher des Knotens zu halten. Bei einer Auflösung von 1024*1024 Punkten, z zu 32 bit und p zu 32 bit sind dies acht Megabyte, also pure Verschwendung, abgesehen davon, daß acht Megabyte nicht zur Verfügung stehen. Um den Speicherbedarf im einzelnen Knoten zu senken, soll, anstatt mehrere "Bilder" gleichzeitig zu berechnen, ein Bild in mehrere Teilbilder aufgeteilt, und diese unabhängig voneinander errechnet werden (Bild 2.4). Wird das Vollbild wieder zu 1024*1024 Punkten angenommen und dieses in 8*8 Teilbilder aufgeteilt, so ergeben sich z/p-Puffer der Größe 128*128 Punkte, was einen Speicherbedarf von nur noch 128 Kilobyte je Prozessor ergibt (für den z/p-Puffer). Das Problem hierbei ist, daß nicht genau 64 Prozessoren zur Verfügung stehen, die Zahl der Prozessoren vielmehr unbestimmt bleibt. Daher belegt der Master jeden i860 mit einem Teilbild und weist die restlichen Teilbilder jeweils den Prozessoren zu, die als erste mit ihren Aufgaben fertig sind. Dadurch sind zwar jeweils zu Ende eines Bildberechnungsschrittes einige i860'er nicht ausgelastet, das Programm ist jedoch gegenüber Veränderungen der Bildgrößen sowie der Anzahl der verfügbaren Prozessoren sehr flexibel. Ein weiterer Nachteil ist, daß für jedes Teilbild Berechnungen notwendig sind, die bei Bearbeitung als Gesamtbild nur einmal anfallen würden. So muß für jedes Teilbild die Liste der Vektoren transformiert werden, da ja ein anderer Ausschnitt der Szene zu sehen sein soll. Viele Polygone werden auch in zwei oder mehreren Teilbildern zu liegen kommen und müssen so den Clipping-Algorithmus mehrfach durchlaufen. Bei n zur Verfügung stehenden Prozessoren wird sich also keine Leistungssteigerung auf das n-fache einstellen. &Betriebssystem 3 Betriebssystem Obwohl ein Betriebssystem immer einen Verwaltungsüberhang bedeutet, bietet es Flexibilität durch die Möglichkeit, Programme modular zu gestalten und von der tatsächlichen Struktur der Hardware unabhängig zu halten. Für den Knotenrechner wird ein Betriebssystem benötigt, daß sich um die Übertragung von Datenpaketen über den Ring kümmert und so eine Kommunikation zwischen den Knoten gewährleistet. Dazu muß es dem Anwendermodul im Knoten Funktionen (syscall) bereitstellen, die ein Senden und Empfangen von Daten von und an andere Knoten ermöglichen. Außerdem verwaltet das Betriebsystem den Arbeitsspeicher des Knotens, da es sich diesen mit einem oder mehreren Anwendermodulen teilen muß. Auch hier muß es dem Anwendermodul die Möglichkeit bieten, Speicher anzufordern und wieder freizugeben. Beim Booten des Rechnerringes sind die Knoten zunächst leer, weshalb es ebenfalls Aufgabe des Betriebssystems sein wird, einen Teil von sich selbst (Kernel) und später Anwendermodule in die einzelnen Knoten zu laden und zu starten. Dieser Vorgang ist jedoch für den Entwurf eines Moduls weitgehend uninteressant, es muß nur eine Einsprungadresse ins Modul definiert sein. Das Anwendermodul kann auf Veranlassung des Masters zu einem beliebigen Zeitpunkt geladen und wieder gelöscht werden. Im Entwurf des Moduls ist der Programmierer frei, solange er die partielle Korrektheit garantiert. Soll das Modul flexibel sein, so nimmt es vom Master über den Kernel jeweils Daten und Kommandos entgegen, die es abarbeitet. Im Prinzip könnte das Modul aber auch autonom arbeiten und feste Arbeitsabläufe erledigen. Konkret sind aus Sicht des Moduls die Schnittstelle zum Kernel und die zum Master zu definieren. 3.1 Schnittstelle vom Modul zum Kernel Nach Laden eines Moduls richtet der Kernel einen linearen Arbeitsspeicher ein (lomem..himem-1), von dem sowohl der Kernel als auch das Modul mit dem Syscall sethimem Stücke abschneiden können. Dann springt der Kernel an die modul-relative Adresse 0 und übergibt im Register r16 als Parameter einen Zeiger auf ein Feld von Zeigern "kmif" (kernel modul interface, Bild 3.1). Bis auf Interrupts und Syscalls bleibt die Programmkontrolle bis zum Ausklinken beim Modul. Das Modul hat sich um Einrichtung eines Stacks in seinem Speicher selbst zu kümmern. Das Feld "kmif" besteht aus 32-bit Zeigern: Index Name Normal Beschreibung kmif: +0 lomem ^lomem Zeiger auf Anfang des freien Speichers +4 himem ^himem Zeiger hinter Ende des freien Speichers +8 syscall ^syscall Zeiger auf Tabelle der syscall-Adressen Mit freiem Speicher ist nicht etwa gemeint, daß das Modul hierauf beliebig zugreifen könnte, sondern vielmehr, daß es sich von diesem Speicher Stücke geben lassen kann. Dazu muß es sich über den syscall sethimem an den Kernel wenden. Die Tabelle "syscall" besteht ebenfalls aus 32-bit Zeigern: Index Name Return Beschreibung syscall: +0 terminate - Ausklinken des Moduls +4 sendbus - Senden eines Datenpakets auf den Bus +8 waitbus ^paket Warten, bis Paket verfügbar +12 freebus - Freigeben des letzten verfügbaren Pakets +16 pollbus ^paket/0 Abfrage, ob ein Paket verfügbar ist (0=nein) +20 sethimem ^memory/0 Reserviere Speicher, dec (himem,s) +24 resethimem - Gib alle reservierten Speicher frei & & Die Parameter werden in den Registern r16..r27 aufsteigend übergeben, das Ergebnis wird in r16 zurückgegeben. Die Pakete werden dem Modul in einem Ringpuffer bereitgestellt. Im Prinzip haben die Pakete beliebige Länge. Würden die Pakete jedoch in einem Ringpuffer lückenlos abgelegt, würde es am Ende des Ringes jeweils zum Wraparound eines Paketes kommen. Das wäre nicht weiter tragisch, wenn nicht das Anwendermodul freien Zugriff auf den Puffer hätte. So müßte sich das Modul jedoch um den Wraparound kümmern, was erheblichen Mehraufwand an Rechenleistung bedeutet. Daher dürfen die Pakete nur eine maximale Länge haben, die vom Master beim Installieren des Kernels festzulegen ist, und werden in gleichgroßen Blöcken abgelegt. Dabei wird zwar Speicherplatz im Ringpuffer verschwendet, aber eher geringfügig, dafür werden die Pakete nicht unnötig im Speicher umkopiert. Um vom Master Daten in großer Menge entgegennehmen zu können, schickt der Master diese direkt an den Kernel, welcher die Daten in den Bereich ablegt, der zuletzt über sethimem reserviert worden ist. Das Modul und der Master müssen also zuvor kommunizieren, damit beide wissen, daß eine Übertragung einer großen Datenmenge erfolgen wird. Lange Vektor- und Objektlisten lassen sich dem Modul so schnell übergeben, ohne daß der Master um den Speicheraufbau des Knotens wissen müßte. 3.1.1 Beschreibung der einzelnen Syscalls terminate: Das Modul verabschiedet sich, der Knoten ist frei zum Nachladen eines anderen Moduls. Es ist zwar nicht unbedingt nötig, daß sich das Modul selbst beendet, aber es ist sauberer. Im Prinzip könnte der Kernel auf Befehl des Masters das Modul auch einfach abwürgen. Parameter: keine. sendbus: Ein Paket wird an einen anderen Busteilnehmer geschickt. Es ist darauf zu achten, daß das Paket nicht zu lang ist, da es sonst nicht in die Datenpuffer des Kernel paßt. Parameter: r16.l Nummer des Empfänger r17.l ^Paket r18.l Länge des Pakets Ergebnis: keins waitbus: Wartet, bis ein Paket durch den Kernel zur Verfügung gestellt wird. Wenn schon eines bereit steht oder sobald eines eingetroffen ist wird ein Zeiger auf das Paket zurückgegeben. Über die Länge des Paketes wird nichts ausgesagt. Das Paket wird aus dem Ringpuffer nicht ausgereiht! Dies muß explizit durch freebus geschehen. Ein zweiter Aufruf von waitbus würde also dasselbe Paket liefern. Dadurch ist es dem Modul möglich, auf das Paket im Puffer solange zuzugreifen, wie es will, ohne daß es bereits durch neu eintreffende Pakete überschrieben würde. Parameter: keine Ergebnis: ^Paket freebus: Gibt das letzte Paket im Ringpuffer frei. Parameter: keine Ergebnis: keins pollbus: Prüft, ob im Ringpuffer ein Paket zur Verfügung steht. Ist eines da, wird genau wie bei waitbus der Zeiger auf das Paket geliefert, ansonsten eine Null. Parameter: keine Ergebnis: ^Paket, wenn eines da ist, sonst 0. sethimem: Reserviert Speicher unterhalb von himem und dekrementiert himem entsprechend. Außerdem merkt sich der Kernel die Adresse und die Länge des Bereiches, den er hier bereitstellt. Diese Adresse nutzt er, um große Datenmengen, die der Master direkt an den Kernel schickt, abzulegen. Um Konfusion zu vermeiden, ist vor einer solchen Übertragung eine Verabredung zwischen Master und Modul zu treffen. Parameter: r16.l Anzahl Bytes, die reserviert werden sollen. Ergebnis: Zeiger auf den reservierten Bereich, oder 0, falls nicht genug Speicher frei ist. resethimem: Gibt alle von Kernel und Modul mit sethimem reservierten Bereiche wieder frei, indem himem auf den ursprünglichen Wert gesetzt wird (topmem). Parameter: keine Ergebnis: keins 3.2 Schnittstelle vom Modul zum Master (allgemein) Sofern das Modul nicht autonom rechnet, was hieße, daß es ohne weitere Anweisungen auskäme, wird es vom Master Pakete empfangen, die es je nach Zustand als Daten- oder Kommandopakete interpretieren kann. Wann es welchen Zustand eingenommen hat, hängt von der jeweiligen Anwendung ab. Die einzige direkte anwendungsunabhängige Kommunikation zwischen Master und Modul ist die der Übertragung einer großen Datenmenge vom Master direkt in den Speicher des Moduls. Wie bereits erwähnt, würde es mit hoher Wahrscheinlichkeit zu großem Durcheinander kommen, wenn das Modul nicht vor der Übertragung durch den Master informiert würde, damit es einen genügend großen Speicherbereich mit sethimem bereitstellen kann. Im Allgemeinen teilt also der Master dem Modul mit, daß Daten eintreffen werden, und wie viele. Nachdem dann das Modul über sethimem den entsprechenden Speicherbereich reserviert hat, teilt es dem Master mit, daß die Übertragung losgehen kann. Daraufhin werden die Daten übertragen und, sobald dies abgeschlossen ist, teilt der Master dem Modul mit, daß die Daten nun vorliegen und gegebenenfalls noch, was er damit tun soll. Wie die Kommunikation im einzelnen aussieht, ist Sache der Anwendung, außerdem kann natürlich dieses Protokoll verändert werden, je nach Bedarf. 3.3 Schnittstelle vom Modul zum Master (konkret) Die Anwendung radiosity besteht aus einer Initialisierungsphase und beliebig vielen Rechenphasen. In der Initialisierungsphase werden dem Modul Parameter mitgeteilt, nämlich die Größe des z-Puffer, die Busadresse des Master und die des Modules selbst, und es werden die Liste der Dreiecke sowie die Liste der Vektoren in nicht transformierter Form übertragen. Das erste Paket, das das Modul vom Master erhält, hat folgenden Aufbau: Index Bytes Beschreibung Paket: +0 4 Adresse des Master +4 4 Nummer des Moduls +8 2 Breite des z-Puffers in Elementen +10 2 Höhe des z-Puffers in Elementen +12 4 Anzahl der Vektoren +16 4 Anzahl der Dreiecke +20 4 Anzahl der Bytes je Dreieck +24 4 Anzahl Zählpaare je Ergebnispaket vom Modul an den Master Das Modul reserviert nun zwei Speicherbereiche für Vektoren, einen für die nicht transformierten, den anderen für die Ergebnisse der Transformation (lmtransf). Nun schickt das Modul dem Master ein Paket, das nur seine Modulnummer enthält, der Master antwortet, indem er die Vektoren schickt und dann ein leeres Paket. Jetzt kann das Modul einen Speicherbereich für die Dreiecke reservieren. Wieder schickt das Modul dem Master ein Paket, das die Modulnummer enthält, und wieder antwortet der Master, diesmal mit der Liste der Dreiecke. Damit ist die Initialisierungsphase abgeschlossen. Alle folgenden Pakete des Masters an das Modul enthalten eine Matrix, anhand derer transformiert werden soll. Das Modul transformiert, zeichnet in den z/p-Puffer und liefert für alle sichtbaren Dreiecke jeweils die Anzahl der sichtbaren Punkte im p-Puffer zurück, gefolgt von der Nummer des Dreieckes. Die Zählung der Dreiecke erfolgt dabei rückwärts, das letzte hat also die Nummer 0, das vorletzte die Nummer 1 und so weiter. Alle Zahlen werden als long berechnet. Weil die Liste der Punkte eventuell nicht in die Ringpuffer des Kernel paßt, werden mehrere Pakete geschickt, jeweils geführt von der Nummer des Moduls und gefolgt von einem Paar, dessen erstes long 0, das zweite im letzten Paket 1, sonst 0 ist (Bild 3.2). Die Anzahl der je Paket maximal zu versendenden long-Paare wurde in der Initialisierungphase als "Anzahl Zählpaare je Ergebnispaket vom Modul an den Master" festgelegt. &Algorithmen 4 Algorithmen 4.1 Vektortransformation Um Objekte, die in allgemeinen Koordinaten gegeben sind, aus einer bestimmten Perspektive darstellen zu können, werden die die Eckpunkte der finiten Elemente definierenden Vektoren anhand einer Matrix transformiert. Dabei wäre für eine Verschiebung der Objekte eine Addition mit einem konstanten Vektor ausreichend, für eine Skalierung die Multiplikation mit einer Konstanten. Schon bei der Drehung im Raum muß jedoch mit einer 3*3 Matrix multipliziert werden. Um eine Kette von einzelnen Transformationen zu vermeiden, werden diese alle als 4*4 Matrizen dargestellt und zunächst in eine einzige Matrix zusammenmultipliziert. Die einzelnen dieser drei primitiven Transformationen sehen wie folgt aus. Verschiebung (Translation): (1 0 0 0) (x' y' z' 1) := (x y z 1) * (0 1 0 0) (0 0 1 0) (Dx Dy Dz 1) Skalierung: (Sx 0 0 0) (x' y' z' 1) := (x y z 1) * (0 Sy 0 0) (0 0 Sz 0) (0 0 0 1) Rotation (um die x-Achse): (1 0 0 0) (x' y' z' 1) := (x y z 1) * (0 cos w sin w 0) (0 -sin w cos w 0) (0 0 0 1) Rotation (um die y-Achse): (cos w 0 -sin w 0) (x' y' z' 1) := (x y z 1) * ( 0 1 0 0) (sin w 0 cos w 0) ( 0 0 0 1) Rotation (um die z-Achse): ( cos w sin w 0 0) (x' y' z' 1) := (x y z 1) * (-sin w cos w 0 0) ( 0 0 1 0) ( 0 0 0 1) Die Vektoren wurden um einen vierten Wert, eine Eins, zu einem Quadrupel erweitert, was in diesem Stadium zwar noch nicht notwendig gewesen wäre, aber bei Ersetzen der letzten Spalte der Matrix die Möglichkeit ganz anderer Transformationen bietet, beispielsweise zur Errechnung einer Zentralprojektion. Allerdings ergibt sich dann im vierten Element des Ergebnisvektors keine Eins, um den Vektor wieder zu normieren, wird abschließend der Vektor durch diesen Wert dividiert und es ergibt sich der Vektor: (x'/u y'/u z'/u u/u) = (x" y" z" 1). Alle diese Transformationen erledigt die Routine lmtransf, und zwar jeweils für eine ganze Liste von Vektoren. Dabei wird für den Sonderfall, daß die letzte Spalte der Matrix normiert ist, die Division durch Eins gar nicht erst angesetzt. & 4.2 z-Puffer Algorithmus Es sollen Objekte in einem dreidimensionalen Raum in die Ebene projiziert und dargestellt werden. Von Objekten, die die selbe Fläche in der Bildebene belegen, soll jeweils das vordere, dem Betracher nähere, gezeichnet, das hintere, verdeckte, nicht gezeichnet werden. Ein schneller, aber speicherintensiver Algorithmus dies zu erreichen ist der z-Puffer Algorithmus. Neben dem eigentlich zu füllenden Bildspeicher wird ein ebenso viele Punkte umfassendes Feld für lineare Werte bereit gestellt, der z-Puffer, in dem für jeden der gezeichneten Bildpunkte festgehalten wird, wie weit er vom Betrachter entfernt ist. Der z-Puffer wird zu Beginn mit einem Wert initialisiert, der "sehr weit weg" bedeutet, für einen integren z-Puffer wäre dies zum Beispiel maxint, für einen aus Fließkommazahlen bestehenden eine ausreichend große Zahl. Es werden grundsätzlich alle Objekte in allen Punkte gezeichnet, nur daß für jeden einzelnen Punkt geprüft wird, ob der zugehörige Wert im z-Puffer größer ist als die interpolierte Entfernung des neuen Punktes vom Betrachter. Ist dies nicht der Fall, wird weder das Bild noch der z-Puffer in diesem Punkt verändert, denn der neue Punkt ist ja verdeckt, also nicht sichtbar. & 4.3 Sutherland Hodgman Clipping Es kann vorkommen, daß zu zeichnende Objekte ganz oder teilweise außerhalb des Bildfensters zu liegen kommen. Daher müssen jede Begrenzungsfläche eines Objektes so zurecht geschnitten werden, daß die sich ergebende Fläche nicht aus dem Bildfenster herausragt. Sie wird also als Differenz der kompletten Begrenzungsfläche und dem Komplement des Bildfensters berechnet. Weil das Bildfenster als Clip-Fenster konvex ist, bietet sich der Algorithmus nach Sutherland und Hodgman an. Dieser trennt den Vorgang des Zurückschneidens eines Polygons nach den einzelnen Kanten des Fensters auf. Zum Beispiel könnte zuerst alles, was links von der linken Kante des Fensters liegt, weggeclippt werden (Bild 4.1). Für jede Fensterkante wird nun das Polygon einmal rundherum durchlaufen und es werden für das Zielpolygon alle Punkte vermerkt, die auf der Innenseite der Fensterkante liegen, zusätzlich alle Schnittpunkte des Polygons mit der Fensterkante, natürlich in der Reihenfolge, wie sie beim Umlaufen des Polygons auftreten. Da die Begrenzungsflächen in diesem Programm allesamt Dreiecke sind, und da ein Dreieck von Haus aus immer konvex sind, ergeben sich, wenn dieser Vorgang für alle vier Kanten des Fensters wiederholt wird, ebenfalls konvexe Polygone mit jeweils maximal sieben Ecken. Der Sutherland Hodgman Algorithmus in Hochsprachennotation, für eine einzelne Clip-Kante: begin s := input_polygon [length (input_polygon)]; for z := 1 to length (input_polygon) do p := input_polygon [z]; if inside (p, clip_boundary) then if inside (s, clip_boundary) then output (p) {case 1} else i := intersect (s, p, clip_boundary); output (i); {case 4} output (p) end else if inside (s, clip_boundary) then i := intersect (s, p, clip_boundary); output (i) {case 2} else null {case 3} end; s := p end end Die Fälle (case 1..4) beziehen sich auf Bild 4.2, output erzeugt den jeweils nächsten Punkt des Ausgabepolygons. Wird keine Punkt erzeugt, so liegt das Dreieck ganz außerhalb des Fensters und ist unsichtbar. Von den insgesamt erzeugten bis zu sieben Kanten sind höchstens drei weder horizontal noch vertikal. Dies ist insofern interessant, als für diagonale Kanten später je eine Division berechnet wird, die es zu vermeiden gilt. Bei dem Clipping selber können jedoch bis zu sieben Divisionen auftreten. Zusammen mit zwei weitern Divisionen (d_zx, d_zy) ergibt sich übrigens eine Gesamthöchstzahl von 12 Divisionen pro Dreieck. & &Der Prozessor i860 5 Der Prozessor i860 und einige Anmerkungen zum konkreten Einsatz. Die Beschreibung lehnt stark an das "Programmer's Reference Manual" an. Für eine vollständige Beschreibung ist dort nachzulesen. 5.1 Allgemeine Beschreibung Der i860 wurde in zwei Versionen angeboten, der älteren XR-Version und der erweiterten XP-Version. Da im Projekt die XR-Version verwendet wird, wird hier auch nur diese beschrieben. 5.1.1 Überblick Der Prozessor i860 ist speziell für den Einsatz in Grafikrechnern und für Massenberechnungen von Fließkommatermen konzipiert. Neben normalen Integeroperationen und Programmkontrollbefehlen stellt der i860 eine Reihe von Befehlen speziell für die Verarbeitung von Fließkommazahlen und Grafik zur Verfügung. Weiter befinden sich bereits auf dem Prozessor umfangreiche Cachespeicher und eine Speicherverwaltung (memory management unit MMU). Auf die MMU wird im Weiteren nicht näher eingegangen, da sie für die vorliegende Arbeit nicht relevant ist. Lediglich das getrennt erstellte Minimalbetriebssystem für den Knotenrechner bedient sich der MMU. Die Cachespeicher, im einzelnen sind dies ein Datencache von 8 Kilobyte und ein Befehlscache von 4 Kilobyte, werden gesondert beschrieben (5.4). Auf dem Chip selbst befinden sich mehrere breite Datenbusse, wodurch die Leistung des Prozessors durchaus gesteigert wird. So können gleichzeitig Befehle und Operanden in die Register geholt werden, während die ausführenden Einheiten ebenfalls gleichzeitig Registerzugriffe durchführen können. Dabei sind wiederum die einfache Einheit (core unit) und die Fließkomma- und Grafikeinheit größtenteils unabhängig voneinander, so daß auch diese parallel arbeiten können, allerdings nur unter interessanten Nebenbedingungen. Die meisten einfachen Befehle werden in einem Taktzyklus ausgeführt, wobei es auch hier wieder auf geschickte Optimierung seitens des Programmierers ankommt, da oft die Konstellation der Befehle ausschlaggebend ist für die konfliktfreie Ausführung. Dies hängt damit zusammen, daß die interne Struktur der ausführenden Einheit eine Pipeline ist, daß heißt, es werden Befehle und Operanden bereits geholt, während der vorige Befehl noch bearbeitet wird. Teilweise geschieht eine Konfliktvermeidung hier automatisch, es werden also beispielsweise Befehle, die auf das Ergebnis des vorhergehenden zugreifen, blockiert, bis das Ergebnis zur Verfügung steht, teilweise muß sich auch der Programmierer selbst um die Auflösung von Konflikten kümmern, zum Beispiel bei einer Reihe von Sprungbefehlen ist zu beachten, daß der Sprung erst nach dem auf den Sprungbefehl folgenden Befehl ausgeführt wird (delay slot). 5.1.2 Befehle Es gibt zwei Gruppen von Befehlen, die in getrennten Einheiten ausgeführt werden: - einfache Befehle (core instructions) - Fließkomma- und Grafikbefehle Der Prozessor ist in der Lage, auf Wunsch Befehle aus beiden Gruppen gleichzeitig ausführen (dual-instruction mode). Dabei sind jedoch, wie bereits erwähnt, einige Nebenbedingungen und Einschränkungen zu beachten. So ist es keinesfalls möglich, an jeder Stelle im Programm den dual-instruction mode zu beginnen oder zu beenden. Auch gibt es eine Reihe von Befehlen, die im dual-instruction mode nicht zusammen auftreten dürfen. Die Fließkomma- und Grafikeinheit selbst enthält drei Recheneinheiten, die Multiplikationseinheit, die Additionseinheit und die Grafikeinheit. Auch hier ist es möglich zwei Einheiten parallel zu nutzen. Eine spezielle Gruppe von Fließkommabefehlen führt gleichzeitig Berechnungen in der Multiplikations- und der Additionseinheit aus (dual-operation instructions, pipelined floatingpoint add and multiply PFAM). Hier erkennt man, daß der i860 besonders für die erstellte Vektortransformation geeignet ist: Jeder Vektor wird in der speziellen Version in zehn Doppelbefehlen transformiert, wobei je neun Additionen und neun Multiplikationen durchgeführt sowie drei Werte gelesen und drei geschrieben werden. 5.1.3 Die einfache Einheit Hier werden nicht nur alle einfachen Befehle ausgeführt, sondern auch alle Befehle geholt. Fließkomma- und Grafikbefehle werden an die entsprechende Einheit weitergereicht. In der einfachen Einheit werden folgende Befehlsgruppen ausgeführt: - Laden und Speichern der Integer- und der Fließkommaregister. - Transfer von Integer- nach Fließkommaregister (ixfr). - Integerarithmetik bis 32 bit, mit und ohne Vorzeichen. - Schiebebefehle (shift). - Logische Befehle. - Programmflußkontrollbefehle (Sprungbefehle, relativ oder absolut, auch bedingt und indirekt). - Systemkontrollbefehle und ähnliches. 5.1.4 Fließkommaeinheit In dieser Einheit befinden sich die Fließkommaregister, die unterschiedlich aufgeteilt werden können, in 32 Register je 32 bit (single precision) oder 16 Register je 64 bit (double precision). Drei weitere Register (KR, KI und T) zum Ablegen von Zwischenergebnissen können mit Hilfe der PFAM-Befehle genutzt werden. Alle drei Verarbeitungseinheiten sind jeweils skalar oder als Pipeline programmierbar. Die meisten Befehle sind in beiden Varianten verfügbar. Die Additionseinheit führt Addition, Subtraktion, Vergleich und Formatkonversion durch. Die Multiplikationseinheit führt Multiplikation sowohl von Fließkomma- als auch von Integerwerten durch. Einen kompletten Divisionbefehl gibt es nicht, statt dessen steht ein Befehl zur Verfügung, der eine Näherung an den Kehrwert eines Operanden liefert (~1/x). Ist man an einem genaueren Kehrwert interessiert, muß man diesen durch ein Approximationsverfahren selbst ermitteln. Ein ähnlicher Befehl für die Berechnung des Kehrwertes der Quadratwurzel des Operanden ist ebenfalls verfügbar (~1/r(x)). Komplexere Funktionen, zum Beispiel trigonometrische, werden nicht angeboten, da diese kaum schneller als auf Softwareebene laufen, statt dessen jedoch den Chip noch weit komplizierter machen würden, als er bereits ist. Laut Handbuch wird der IEEE-Standard für binäre Fließkommaarithmetik (ANSI/IEEE Std 754-1985) eingehalten, eine sehr erleichternde Anmerkung, zumal Fließkommawerte von einem fremden Prozessor übertragen werden sollen. 5.1.5 Grafikeinheit Die Grafikeinheit ist Teil der Fließkomma- und Grafikeinheit und greift auf die Fließkommaregister zu, die paarweise als 64 bit Integer verarbeitet werden. Weiter gibt es ein spezielles MERGE-Register. Die Befehle sind zugeschnitten auf Anwendungen aus der 3D-Grafik, besonders Gouraud- und Phongfarbverlaufsberech- nungen und Darstellung verdeckender Flächen mit Hilfe des Z-Puffer-Algorithmus. Parallelität wird erzeugt, indem die Befehle auf 64 Bit arbeiten, auch wenn je Pixel weniger Bit benötigt werden, so daß im allgemeinen mehrere Punkte gleichzeitig bearbeitet werden können. Hierbei hilft das MERGE-Register, das als Maske für die aktiven Pixel anzusehen ist. Es hat sich herausgestellt, daß die Grafikbefehle eine ganze Reihe von festen Voraussetzungen an die zu verarbeitende Grafik stellen. Die z-Puffer-Befehle gehen davon aus, daß der z-Puffer ganzzahlige Werte von 16 oder 32 Bit enthält. Werden jedoch Fließkommazahlen verwendet, so können diese Befehle nicht mehr eingesetzt werden. Dadurch sind auch das MERGE-Register und die PM-bits nicht mehr verwendbar, da diese nur durch die zchk-Befehle gesetzt werden. Ist also schon diese eine Voraussetzung nicht mehr erfüllt, ist der Einsatz der stark zusammmen arbeitenden Grafikbefehle nicht mehr möglich. Ganz abgesehen davon ist zum Beispiel der Sinn des Befehles faddz fragwürdig. Dieser Befehl ist gedacht für Distanzinterpolation, speziell für Z-Puffer zu 16 bit. Dabei soll die Interpolation mit Fixpunktzahlen je 32 bit erfolgen, wovon 16 bit die Vorkommastellen sind. Warum nicht gleich mit 32 bit Z-Puffer Werten gerechnet werden soll, ist unklar, würde es doch den Einsatz des Registers MERGE überflüssig machen, ohne erhöhten Rechenaufwand. 5.1.6 Memory Management Unit (MMU) Der i860 verfügt über eine komplette virtuelle Speicheradressiereinheit. Diese ist geeignet, das Benutzerprogramm davor zu bewahren, sich um den tatsächlichen Speicheraufbau des konkreten Rechners zu kümmern. Die Handhabung der MMU ist also Sache des Betriebssystems und ist für die vorliegende Aufgabe unwesentlich. 5.1.7 Parallele Architektur Die Parallelitätseigenschaften des i860 sind auf niedriger Ebene angesiedelt, was bedeutet, daß für die Handhabung derselben tief in die Struktur des Prozessors eingegriffen werden muß. Der Prozessor unterstützt den Programmierer nur halbherzig bei dem Versuch, die Parallelitätseigenschaften voll auszunutzen. Als theoretisches Ideal wäre anzusehen, einen Compiler zu entwickeln, der in der Lage ist, zu jedem in einer Hochsprache (oder in C) gelieferten Programmtext ein annähernd optimales Compilat zu erzeugen. Das wäre wahrscheinlich eine Höllenarbeit. Schraubt man seine Ansprüche etwas zurück, könnte man mit einem Compiler vorlieb nehmen der den Prozessor als Vektorrechner ansieht und dementsprechend nur vektorisierbare Probleme in parallelen Code abbilden kann. Eine weitere Einschränkung der Forderungen führt zu einem Compiler, der an sich skalar abbildet, jedoch für einzelne Probleme in einer Bibliothek vorgefertigte optimierte Lösungen bietet. Zu erkennen ist eine tiefe Kluft zwischen Machbarem und Ideal. An dieser Stelle wird auch ganz deutlich, daß die vorliegende Arbeit nur als Notlösung aufgrund des Fehlens des idealen Compilers angesehen werden kann. Wie allerdings der ideale Compiler zu erstellen sein könnte, ist nicht Teil dieser Arbeit. Das Handbuch behauptet, es wäre möglich, die volle Leistung des Prozessors von bis zu drei Operationen je Taktzyklus durch sorgfältiges Optimieren zu erreichen. Daß könne man, indem man die Befehle so anordne, daß sie sich nicht gegenseitig verzögern, indem man immer einfache und Fließkommabefehle im dual-instruction mode kombiniere und so weiter. Praktisch ist das natürlich nicht möglich, da es ja nicht darum geht, den Prozessor auszulasten, sondern primär darum, ein gewünschtes Ergebnis zu berechnen. Und da zeigt sich bald, daß es eben nicht immer gleichzeitig einfache und Fließkommaberechnungen anzustellen gibt und daß viele Algorithmen in sich Abhängigkeiten bergen, die eine verzögerungsfreie Anordnung unmöglich machen. Hinzu kommt, daß die erwähnten Geschwindigkeiten nur erreicht werden können, wenn keine Verzögerungen durch zusätzliche Speicherzugriffe stattfinden, was aber in der Praxis auch nicht immer der Fall ist. Die nahezu volle Ausnutzung der Rechenleistung gelingt aufgrund dieser Erfahrungen nur, wenn in kurzen Schleifen intensiv gerechnet werden kann, wie zum Beispiel im Sonderfall in lmtransf. Für die Routine zpbuf treffen die Bedingungen schon nicht mehr zu, sie ist weder eine kurze Schleife noch besteht sie aus einer homogenen Mischung einfacher und Fließkommabefehle. Außerdem birgt sie sehr viele direkte Abhängigkeiten, besonders in den vielen bedingten Sprüngen, so daß das Ideal von einem ausgeführten Befehl in einem Taktzyklus nicht annähernd erreicht wird, und drei Operationen pro Taktzyklus schon gar nicht. 5.1.8 Software Entwicklungsumgebung Hier ist der Simulator und Debugger zu erwähnen. Mit Hilfe dieses Programmes war es möglich, die erstellten Prozeduren wenigstens etwas zu testen, obwohl die Zielmaschine nicht fertiggestellt werden konnte. Der Debugger ist in seiner Kommandosprache allerdings gewöhnungsbedürftig und nicht übermäßig komfortabel. Auf die Verwendung der Compiler wurde verzichtet, da erstens keiner eine akzeptable Hochsprache übersetzt und zweitens mit Sicherheit davon ausgegangen werden konnte, daß es sich nicht um einen auch nur annähernd idealen Compiler handelt. & 5.2 Datentypen Der i860 kennt sowohl ganze als auch Fließkommazahlen. Ganze Zahlen je 32 bit sind mit und ohne Vorzeichen vorhanden, außerdem rechnet die Grafikeinheit mit Feldern von Zahlen je 8, 16 oder 32 bit. Lade- und Speicherbefehle transportieren 8, 16, 32, 64 oder 128 bit. Fließkommazahlen gibt es mit "einfacher oder doppelter Genauigkeit". Die Bits im Datum werden von der niederwertigsten Stelle an nummeriert, angefangen bei 0. Dargestellt wird die Stellen von rechts nach links. 5.2.1 Integer, Ganze Zahlen mit Vorzeichen Ganze Zahlen werden im Zweierkomplement dargestellt. Werden ganze Zahlen von 8 oder 16 bit geladen, wird das Register vorzeichenrichtig auf 32 gefüllt. Werden 8 oder 16 bit gespeichert, wird auf die entsprechenden niederwertigen Bits des Registers zugegriffen. 32 bit Addition und Subtraktion werden von der einfachen Einheit erledigt, 64 bit Addition und Subtraktion können in der Grafikeinheit vorgenommen werden, die Fließkommaeinheit kann 52 bit Integer multiplizieren. 5.2.2 Kardinale Zahlen ohne Vorzeichen Soll ohne Vorzeichen gerechnet werden, ist beim Laden und Speichern zu beachten, daß die entsprechenden Befehle vorzeichenrichtig erweitern. Ansonsten stehen entsprechende Befehle wie für Integer zur Verfügung. 5.2.3 Fließkommazahlen, "einfache Genauigkeit" (single precision) Das Datum wird vom höchstwertigen Bit her eingeteilt, 1 bit für das Vorzeichen s, 8 bit für den Exponenten e, 23 bit für die Mantisse m. Gemäß ANSI/IEEE Standard 754 ergibt sich der dargestellte Wert wie folgt: - Für e=0 und m=0 ist der Wert 0 . - Für 0 isrc1 subs isrc1,isrc2,r0 bc subu isrc1,isrc2,r0 bnc & 5.6.1.10 Schiebe Integer Register nach links (shift left) shl isrc1,isrc2,idest isrc1 kann auch eine direkte 16 bit Konstante sein, vorzeichenbehaftet. Funktion: idest := isrc2 um isrc1 bit nach links verschoben es werden isrc1 Nullen nachgeschoben Von isrc1 werden nur die niederwertigen 5 Bit als Schiebezähler genommen. Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus Anmerkungen: Der Assembler kodiert für den Befehl "mov isrc2,idest" einen Schub: shl r0,isrc2,idest und für den Befehl "nop" ebenfalls: shl r0,r0,r0 & 5.6.1.11 Schiebe Integer Register nach rechts (shift right) shr isrc1,isrc2,idest shra isrc1,isrc2,idest isrc1 kann auch eine direkte 16 bit Konstante sein, vorzeichenbehaftet. Funktion: idest := isrc2 um isrc1 bit nach rechts verschoben für shr werden isrc1 Nullen nachgeschoben, für shra wird jeweils das Vorzeichen nachgeschoben Wenn shr: SC := isrc1 Von isrc1 werden nur die niederwertigen 5 Bit als Schiebezähler genommen. Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus & 5.6.1.12 Schiebe zwei Integer Register nach rechts (shift right double) shrd isrc1,isrc2,idest Funktion: idest := (isrc1:isrc2) um SC bit nach rechts verschoben (isrc1:isrc2) wird als 64 bit Integer verstanden, die niederwertigen 32 Bit sind isrc2, die höherwertigen sind isrc1. Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus Anmerkungen: Der Assembler kodiert für den Befehl "fnop" einen Doppelschub: shrd r0,r0,r0 Dieser Fließkomma-Nicht-Befehl ist nötig, um im dual-instrcution-mode die Möglichkeit zu haben, die Fließkomma- und Grafikeinheit für einen Befehl ruhen zu lassen. shrd kommt deshalb in Frage, weil er nicht wie die Flieskommabefehle eine Pipeline bewegt oder langwierig rechnet, dennoch aber das D-bit gesetzt hat, und daher für den Prozessor im dual-instruction-mode als Fließkommabefehl durchgeht. Sowas ist RISC. Um eine Rotation auszuführen, nehme man folgende Sequenz: shr count,r0,r0 //Lade Schiebezähler nach SC shrd isrc,isrc,idest //Rotiere isrc um SC bit nach rechts nach idest & 5.6.1.13 Logische Verknüpfungen (logical operations) and isrc1,isrc2,idest andnot isrc1,isrc2,idest or isrc1,isrc2,idest xor isrc1,isrc2,idest Funktion: idest := isrc2 AND/ANDNOT/OR/XOR isrc1 CC := idest = 0 Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus & 5.6.1.14 Logische Verknüpfungen in der oberen Registerhälfte (logical operations, high half) andh #const,isrc2,idest andnoth #const,isrc2,idest orh #const,isrc2,idest xorh #const,isrc2,idest Funktion: idest := isrc2 AND/ANDNOT/OR/XOR (const um 16 bit nach links verschoben) CC := idest = 0 Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus Anmerkung: Der Assembler kodiert den Befehl "mov const32,idest" als zwei Oder: orh h%const32,r0,idest or l%const32,idest,idest & 5.6.1.15 Unbedingte Verzweigung (branch unconditionally) br lbroff Funktion: Führe einen weiteren Befehl aus Setze Programmzähler auf brx(lbroff) Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus & 5.6.1.16 Bedingte Verzweigung (branch conditionally) bc lbroff bnc lbroff Funktion: Sprungbedingung: CC = 1 für bc, CC = 0 für bnc Wenn Bedingung erfüllt: Setze Programmzähler auf brx(lbroff) Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn verzweigt wird +1 wenn der vorige Befehl ein addu, adds, subu, subs, pfeq oder pfgt war. & 5.6.1.17 Bedingte Verzweigung verzögert (branch conditionally, taken) bc.t lbroff bnc.t lbroff Funktion: Sprungbedingung: CC = 1 für bc.t, CC = 0 für bnc.t Wenn Bedingung erfüllt: Führe einen weiteren Befehl aus Setze Programmzähler auf brx(lbroff) sonst: Überspringe den folgenden Befehl Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn nicht verzweigt wird +1 wenn der vorige Befehl ein addu, adds, subu, subs, pfeq oder pfgt war. Anmerkung: Warum Intel nicht einen bedingten Verzweigungsbefehl eingebaut hat, der immer einen weiteren Befehl ausführt, bevor eventuell gesprungen wird, ist unklar, wäre doch damit die Ausführungszeit immer auf einen Takt begrenzt. & 5.6.1.18 Vergleich und Verzweigung (test and branch) bte isrc1,isrc2,sbroff btne isrc1,isrc2,sbroff isrc1 kann auch eine direkte 5 bit Konstante sein, ohne Vorzeichen. Funktion: Sprungbedingung: isrc1 = isrc2 für bte, isrc1 # isrc2 für btne Wenn Bedingung erfüllt: Setze Programmzähler auf brx(sbroff) Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus +2 wenn verzweigt wird & 5.6.1.19 Test, Verzweigung und Addition (branch on LCC and add) bla isrc1,isrc2,sbroff Funktion: LCC_temp := (isrc2 + isrc1 >= 0) isrc2 := isrc2 + isrc1 Führe einen weiteren Befehl aus Wenn LCC: Setze Programmzähler auf brx(sbroff) LCC := LCC_temp isrc1 und isrc2 müssen zwei verschiedene Register sein. Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn nicht verzweigt wird Anmerkungen: Dieser Befehl ist für Zählschleifen gedacht. Allerdings kann er, anders als bei anderen Prozessoren, nicht in geschachtelten Schleifen verwendet werden, da LCC während des Schleifenrumpfes erhalten bleiben muß. Zweckmäßigerweise ist bla daher für die innerste Schleife zu verwenden. Beispiel für eine Schleife, die n mal durchlaufen wird: adds -2,n,icntd //Schleifenzähler-2 (da erst nach -1 beendet wird) bla r0,icntd,schleife //LCC vorbereiten adds -1,r0,iincr //Schleifenzählung rückwärts, iincr = -1 schleife: Rumpf der Schleife mit Ausnahme des letzten Befehls bla iincr,icntd,schleife Letzter Befehl des Rumpfes der Schleife Wichtig ist, daß die Schleife mindestens einmal durchlaufen wird. & 5.6.1.20 Unterfunktionsaufruf (subroutine call) call lbroff Funktion: r1 := Adresse des übernächsten Befehls (oder Paares im dual-instruction-mode) Führe einen weiteren Befehl aus Setze Programmzähler auf brx(lbroff) Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn r1 im nächsten Befehl benutzt wird +... wenn bestimmte Cachezugriffe stattfanden. & 5.6.1.21 Unterfunktionsaufruf indirekt (indirect subroutine call) calli [isrc1] Funktion: r1 := Adresse des übernächsten Befehls (oder Paares im dual-instruction-mode) isrc1_temp := isrc1 Führe einen weiteren Befehl aus Setze Programmzähler auf isrc1_temp isrc1 darf nicht r1 sein. Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 2 Taktzyklen +1 wenn r1 im nächsten Befehl benutzt wird +... wenn bestimmte Cachezugriffe stattfanden. & 5.6.1.22 Verzweigung indirekt unbedingt (branch indirect unconditionally) bri [isrc1] Funktion: isrc1_temp := isrc1 Führe einen weiteren Befehl aus Wenn irgendwelche trap-bits in psr gesetzt sind: diverse Systemaktionen Setze Programmzähler auf isrc1_temp (siehe Handbuch 7.11) Wird in der einfachen Einheit ausgeführt. Ausführungszeit: 2 Taktzyklen Anmerkung: Dieser Befehl wird mit Register r1 verwendet für den Rücksprung aus Unterfunktionen. & 5.6.2 Fließkomma- und Grafikbefehle 5.6.2.1 Funktionsweise einer Pipeline Viele Berechnungen, die der Prozessor zur Ausführung eines Befehls anstellen muß, lassen sich in mehrere Einzelschritte (Stufen) aufteilen. Wenn die Hardware so gestaltet wird, daß diese Stufen unabhängige Einheiten darstellen, ist es möglich, daß die erste Stufe bereits für eine neue Berechnung genutzt wird, sobald die nächste Stufe von ihr die Zwischenergebnisse erhalten hat und die zweite Berechnungsstufe des vorigen Befehls ausführt. Diese Arbeitsweise entspricht in der Struktur einem Fließband und heißt nach dem englischen Pipeline. Es gibt mehrere Möglichkeiten, so eine Pipeline zu handhaben. Die für den Programmierer komfortabelste ist die, die er gar nicht sieht, die nämlich durch den Befehl angestoßen wird und dann selbstständig rechnet und, sobald sie fertig ist, die Ergebnisse in die Register ablegt. Nachteil hierbei ist, daß die Hardware für eine Konfliktvermeidung sorgen muß, falls auf das Zielregister des Befehls zugegriffen wird, während dieser noch rechnet. Die für den Hardwaredesigner einfachste ist die, die der Programmierer gefälligst selbst zu bewegen und kontrollieren hat, daß hieße, es gäbe einen Befehl "Eine_Stufe_ausführen", der in alle Stufen der Pipeline eingreift und genau festlegt, was die einzelnen Stufen zu tun haben, und die Pipeline um einen Schritt weiterbewegt. Die Pipelines im i860 vereinen beide Techniken, indem zwar der Befehl, der die Operanden für die ersten Stufe bereitstellt, auch die benötigten Begleitdaten (Rechengenauigkeit, gewünschte Operation) zur Verfügung stellt und diese von Stufe zu Stufe weitergereicht werden, jedoch je Befehl die Pipeline nur um einen Schritt weiterbewegt wird und das Zielregister erst durch den Befehl festgelegt wird, durch den das Ergebnis aus der letzten Stufe herausgeholt wird. Außerdem benutzt der i860 die Pipelineschaltkreise auch für die skalare Berechnung, so daß die noch in Berechnung befindlichen Inhalte der einzelnen Stufen durch Verwendung skalarer Befehle verloren gehen. Dies gilt nicht für die Ladepipeline des Befehls pfld. Der i860 verfügt über mehrere Pipelines, neben der bereits erwähnten Ladepipeline über eine Additionspipeline, eine Multiplikationspipeline und eine Grafikpipeline. Die Additionspipeline ist drei Stufen lang, das Ergebnis eines Befehls wird also durch den drittnächsten Befehl abgelegt. Die Länge der Multiplikationspipeline hängt von der Genauigkeit der Operanden ab, wobei bei einfacher Genauigkeit drei, bei doppelter zwei Stufen vorhanden sind. Die Grafikpipeline schließlich ist einstufig. Bei der Angabe der Rechengenauigkeit bei einem Pipelinebefehl ist zu beachten, daß die gewünschte Ergebnisgenauigkeit durch den initiierenden Befehl festgelegt wird, während das Zielregister dieses Befehls sich auf das aus der letzten Stufe austretende Ergebnis bezieht. Wird von einem Befehl das Zielregister gleichzeitig als Quelloperand verwendet, wird das Ergebnis der letzten Stufe direkt in die erste Stufe wieder eingefüllt. Dabei muß die Genauigkeit des Ergebnisses mit dem der Quelloperanden übereinstimmen, es sei denn es ist f0. Wird bei Verwendung der Multiplikationspipeline mit wechselnden Genauigkeiten gerechnet, ändert die Pipeline dementsprechend ihre Länge, wobei je nach Übergang eine Stufe der Pipeline verloren geht, oder eine zusätzliche entsteht. Wird ein Befehl mit doppelter Genauigkeit gestartet nach einem mit einfacher Genauigkeit, legt er das Ergebnis der dritten, letzten Stufe ins Zielregister, verliert das Ergebnis der zweiten Stufe, schiebt die Ergebnisse der ersten Stufe in die zweite, jetzt letzte Stufe und füllt die erste mit den neuen Operanden. Wird ein Befehl mit einfacher Genauigkeit gestartet nach einem mit doppelter Genauigkeit, legt er das Ergebnis der zweiten, letzten Stufe ins Zielregister, das Ergebnis der ersten Stufe gelangt in die zweite Stufe, die erste wird mit den neuen Operanden gefüllt und in die dritte, letzte und neue Stufe wird eine Null geschrieben. Bei den Formatangaben (.xx) steht jeweils der erste Buchstabe für die Genauigkeit der Operanden, der zweite für des Ergebnisses, wobei s für einfache (single), d für doppelte (double) Genauigkeit steht. & 5.6.2.2 Multipliziere Fließkommazahl (floating point multiply) fmul.xx fsrc1,fsrc2,fdest pfmul.xx fsrc1,fsrc2,fdest pfmul3.dd fsrc1,fsrc2,fdest .xx = .ss, .sd, .dd Funktion (fmul): fdest := fsrc1 * fsrc2 Funktion (pfmul, pfmul3): fdest := Multiplikationspipeline_letzte_Stufe Multiplikationspipeline vorrücken Multiplikationspipeline_Stufe1 := fsrc1 * fsrc2 Der Befehl pfmul3 erzwingt eine dreistufige Pipeline trotz doppelter Genauigkeit. Allerdings darf der Befehl nur in bestimmten, für uns nicht interessanten Sonderfällen verwendet werden, da er sonst undefinierte Ergebnisse liefert. Sehr seltsam. Im Pipelinemodus dürfen fsrc1 und fdest nicht das selbe Register sein, es sei denn, beide seien f0. Wird in der Multiplikationseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fsrc1 das Ergebnisregister des vorigen Befehls war. +1 wenn der vorige Befehl eine Multiplikation doppelter Genauigkeit war. +2..4 wenn ein skalarer Fließkommabefehl aussteht. & 5.6.2.3 Multipliziere Fließkommamantisse (floating point multiply low) fmlow.dd fsrc1,fsrc2,fdest Funktion: fdest := niederwertige 53 Bits (fsrc1 Mantisse * fsrc2 Mantisse) fdest Bit 53 := Bit 105 (fsrc1 Mantisse * fsrc2 Mantisse) Wird in der Multiplikationseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fsrc1 das Ergebnisregister des vorigen Befehls war. +1 wenn der vorige Befehl eine Multiplikation doppelter Genauigkeit war. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Der Befehl fmlow ist geeignet, eine Multiplikation von ganzen Zahlen durchzuführen, allerdings müssen dazu die ganzen Zahlen in die doppelten Fließkommaregister hin und her geschaufelt werden: ixfr isrc1,ftmp1 //ftmp1 und ftmp2 seien Doppelregister, ixfr isrc2,ftmp2 //deren obere Hälfte jeweils ignoriert wird. fmlow.dd ftmp1,ftmp2,ftmp2 fxfr ftmp2,idest //Ergebnis zu 32 bit. & 5.6.2.4 Kehrwertannäherung Fließkommazahl (floating point reciprocal, floating point reciprocal square root) frcp.xx fsrc2,fdest frsqr.xx fsrc2,fdest .xx = .ss, .sd, .dd Funktion (frcp): fdest := 1 / fsrc2, mit absolutem Mantissenfehler < 1/128 Funktion (frsqr): fdest := 1 / Wurzel (fsrc2), mit absolutem Mantissenfehler < 1/128 Ist fsrc2=0 bei frcp, oder fsrc2<=0 für frsqr, dann wird eine Ausnahmebehandlung eingeleitet. Wird in der Multiplikationseinheit ausgeführt. Ob durch diese Befehle die Multiplikationspipeline gelöscht wird, läßt sich dem Handbuch leider nicht entnehmen. Ich vermute, daß die Pipeline nicht gelöscht wird, da der Befehl skalar ist und dennoch nicht zu unter den eingangs erwähnten Verzögerungen (+2..4) führt, woraus man schließen kann, daß er nicht die Pipelineschaltkreise durchläuft. Aber da uns Intel im Unklaren läßt, muß bei der Programmierung vom Schlimmsten ausgegangen werden. Schade, daß schlechte Handbücher den Durchsatz senken. Ausführungszeit: 1 Taktzyklus +1 wenn fsrc1 das Ergebnisregister des vorigen Befehls war. +1 wenn der vorige Befehl eine Multiplikation doppelter Genauigkeit war. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Um genaue Kehrwerte oder gar eine Division durchzuführen, kann eine der folgenden Sequenzen verwendet werden (fdest := fdend / fdsor). Dabei liegt der Newton-Raphson Algorithmus zugrunde, bei dem mehrfach bessere Näherungen berechnet werden, bis der Fehler gegen die Mantisse unerheblich wird: Neuer_Wert := Alter_Wert * (2 - Alter_Wert * Divisor) Neuer_Fehler := 2 * (Alter_Fehler)^2 Division_einfache_Genauigkeit: frcp.ss fdsor,fdest //erster Versuch (8 bit) fmul.ss fdsor,fdest,ftmp1 fsub.ss fzwei,ftmp1,ftmp1 //fzwei enthalte 2.0 (einfach) fmul.ss fdest,ftmp1,fdest //zweiter Versuch (15 bit) fmul.ss fdsor,fdest,ftmp1 fsub.ss fzwei,ftmp1,ftmp1 fmul.ss fdest,ftmp1,fdest //dritter Versuch (29 bit) fmul.ss fdend,fdest,fdest //noch mit Dividend multiplizieren Division_doppelter_Genauigkeit: frcp.dd fdsor,ftmp1 //erster Versuch (8 bit) fmul.dd fdsor,ftmp1,fdest fsub.dd fzwei,fdest,fdest fmul.dd ftmp1,fdest,ftmp1 //zweiter Versuch (15 bit) fmul.dd fdsor,ftmp1,fdest fsub.dd fzwei,fdest,fdest fmul.dd ftmp1,fdest,ftmp1 //dritter Versuch (29 bit) fmul.dd fdsor,ftmp1,fdest fsub.dd fzwei,fdest,fdest fmul.dd ftmp1,fdest,ftmp1 //vierter Versuch (57 bit) fmul.dd fdend,ftmp1,fdest //noch mit Dividend multiplizieren Diese beiden Beispiele dienen als Wink mit dem Zaunpfahl, beim Entwurf von Algorithmen zur Implementierung auf dem i860 Divisionen zu vermeiden, wo es geht. & 5.6.2.5 Addiere / Subtrahiere Fließkommazahl (floating point add / subtract) fadd.xx fsrc1,fsrc2,fdest pfadd.xx fsrc1,fsrc2,fdest fsub.xx fsrc1,fsrc2,fdest pfsub.xx fsrc1,fsrc2,fdest .xx = .ss, .sd, .dd Funktion (fadd,fsub): fdest := fsrc1 +- fsrc2 Funktion (pfadd,pfsub): fdest := Additionspipeline_Stufe3 Additionspipeline vorrücken Additionspipeline_Stufe1 := fsrc1 +- fsrc2 Wird in der Additionseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +2..4 wenn ein skalarer Fließkommabefehl aussteht. & 5.6.2.6 Pseudoaddition Fließkommazahl (floating point adder move) famov.xx fsrc1,fdest pfamov.xx fsrc1,fdest .xx = .ss, .sd, .ds, .dd Funktion (famov): fdest := fsrc1 Funktion (pfamov): fdest := Additionspipeline_Stufe3 Additionspipeline vorrücken Additionspipeline_Stufe1 := fsrc1 Wird in der Additionseinheit ausgeführt. Dabei wird die komplette Additionspipeline durchlaufen, wie bei normalen Additionsbefehlen. Ausführungszeit: 1 Taktzyklus +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Der Assembler kodiert die Befehle "(p)fmov.sd" und "(p)fmov.ds" als Pseudoadditionen (p)famov.xx & 5.6.2.7 Vergleiche Fließkommazahlen (floating point compares) pfgt.xx fsrc1,fsrc2,fdest pfle.xx fsrc1,fsrc2,fdest pfeq.xx fsrc1,fsrc2,fdest .xx = .ss, .dd Funktion: fdest := Additionspipeline_Stufe3 Für pfeq: CC := (fsrc1 = fsrc2) sonst: CC := (fsrc1 > fsrc2) Additionspipeline vorrücken Additionspipeline_Stufe1 := undefiniert Wird in der Additionseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkungen: Ein erstaunlicher Vergleichsbefehl: Er hat ein Ergebnisregister und geht in die Pipeline. Das Ergebnis ist natürlich nicht das vom Vergleich, sondern das der drittletzten Addition. Und wieso sollte man eine Version dieses Befehls ohne Pipeline brauchen, wenn der die Pipeline dann komplett ruinieren würde? Wer die Pipeline gar nicht verwendet, den stört auch nicht, daß die Vergleiche ein bißchen an ihr rumschieben. Ebenfalls erstaunlich: pfgt und pfle machen genau das Gleiche. Der einzige Unterschied ist, daß der Assembler beim ersteren das R-bit löscht, beim letzteren setzt. Das soll bei der Ausnahmeverarbeitung helfen, beim Rücksprung ins Programm die Flags richtig zu setzen. Wer auf dieses Angebot verzichten möchte, kann getrost pfgt und pfle beliebig austauschen. & 5.6.2.8 Konversion Fließkommazahl nach Integer (floating point to integer converion) fix.xx fsrc1,fdest pfix.xx fsrc1,fdest ftrunc.xx fsrc1,fdest pftrunc.xx fsrc1,fdest .xx = .sd, .dd Funktion (fix,ftrunc): fdest := 64-bit Wert, wovon die niederwertigen 32 bit dem ganzzahligen Anteil von fsrc1 entsprechen (für fix gerundet) Funktion (pfix,pftrunc): fdest := Additionspipeline_Stufe3 Additionspipeline vorrücken Additionspipeline_Stufe1 := 64-bit Wert, wovon die niederwertigen 32 bit dem ganzzahligen Anteil von fsrc1 entsprechen (für pfix gerundet) Wird in der Additionseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Zur Ausführungszeit beachte man die der bedingten Verzweigungsbefehle. & 5.6.2.9 Doppel-Operations Befehle (dual operation instruction) pfam.xx fsrc1,fsrc2,fdest pfsm.xx fsrc1,fsrc2,fdest pfmam.xx fsrc1,fsrc2,fdest pfmsm.xx fsrc1,fsrc2,fdest .xx = .ss, .sd, .dd Funktion: Für pfam,pfsm: fdest := Additionspipeline_Stufe3 sonst: fdest := Multiplikationseinheit_letzte_Stufe Additionspipeline und Multiplikationspipeline vorrücken Additionspipeline_Stufe1 := A_op1 +- A_op2 (pf(m)am +, pf(m)sm -) Multiplikationspipeline_Stufe1 := M_op1 * M_op2 Wird in der Additionseinheit und in der Multiplikationseinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fsrc1 das Ergebnisregister des vorigen Befehls war. +1 wenn der vorige Befehl eine Multiplikation doppelter Genauigkeit war. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkungen: Wie auch beim Fließkommamultiplikationsbefehl ist die Multiplikationspipeline je nach Rechengenauigkeit drei- oder zweistufig. Für die Wahl der Rechengenauigkeit ist zu beachten, daß sich die Angabe der Eingangsgenauigkeit nur auf die Operanden der Mutiplikation bezieht, während sowohl die Genauigkeit der Operanden der Additionspipeline als auch die aller Ergebnisse durch die Zielgenauigkeitsangabe bestimmt werden. Bleibt zu erläutern, was mit A_op und M_op gemeint ist. Dieser Befehl arbeitet mit vier Operanden und zwei Ergebnissen. Da aber nur drei Register spezifiert werden können (Drei-Adreß-Form), werden die übrigen drei Operanden durch Verknüpfung von beiden Pipelines und aus drei speziellen Registern gebildet. Dabei sind viele Kombinationen (Bild 5.1) möglich, die am besten in einer Tabelle zusammengestellt werden. Die Register KI, KR sind dazu gedacht, Eingangsoperanden mit konstanten Faktoren zu multiplizieren. Das Register T kann als Pipelineverzögerung verwendet werden, oder für konstante Offsets. Für Matrixmultiplikation und ähnliche Anwendungen ist die Struktur wirklich gut geeignet. Leider können die Register KI, KR und T nicht einfach so gelöscht werden, und da T nur über das Ergebnis der Multiplikationspipeline zugänglich ist, benötigt man mindestens drei Befehle, um T zu löschen. Loesche_KI_KR_und_T: r2apt.dd f0,f0,f0 r2apt.dd f0,f0,f0 i2apt.dd f0,f0,f0 & Die Namen der Befehle sind nicht etwa pfam, pfsm, pfmam und pfmsm, sondern fügen sich aus einem Haufen Buchstaben zusammen, die etwas über die verwendeten Operanden aussagen. Für Befehle mit M_op2 = fsrc2 lautet der Befehl: {r,i} 2 {a,m,} {p,s} {1,t} wobei die einzelnen Buchstaben die Operanden und Operation festlegen: {r,i} für M_op1: r -> KR i -> KI 2 für M_op2: 2 -> fsrc2 {a,m,} für A_op2: a -> Ergebnis der Additionspipeline, lade T m -> Ergebnis der Multiplikationspipeline, lade T -> Ergebnis der Multiplikationspipeline {p,s} für Operation: p -> Addition s -> Subtraktion {1,t} für A_op1: 1 -> fsrc1 t -> T, lade KR oder KI Für Befehle, die weder KR noch KI laden, lautet der Befehl: {ra,rm,ia,im,m12} {t,} {1,a,m,t} {p,s} {2,m,a} wobei die einzelnen Buchstaben die Operanden und Operation festlegen: {ra,rm,ia,im,m12} für M_op1 und M_op2: ra -> KR und Additionsergebnis rm -> KR und Multiplikationsergebnis ia -> KI und Additionsergebnis im -> KI und Multiplikationsergebnis m12 -> fsrc1 und fsrc2 {t,} für T: t -> lade T -> lade T nicht {1,a,m,t} für A_op1: 1 -> fsrc1 a -> Ergebnis der Additionspipeline m -> Ergebnis der Multiplikationspipeline t -> T {p,s} für Operation: p -> Addition s -> Subtraktion {2,m,a} für A_op2: 2 -> fsrc2 m -> Ergebnis der Multiplikationspipeline a -> Ergebnis der Additionspipeline Leider sind nicht alle Kombinationen möglich: Bei der Anwendung der dual-operation Befehle fällt stark auf, daß bei der Bereitstellung von Kombinationsmöglichkeiten der Datenpfade und Quell- und Zielregister etwas zu sehr gespart wurde. Neben der Auswahl der additiven Operation (+ oder -) und der Genauigkeit der Operanden wurden für die Festlegung der Datenpfade lediglich fünf Bit des Befehlswortes abgestellt. Beim Programmieren muß man daher immer wieder feststellen, daß nach Skizzierung der Befehlsfolge die Umsetzung einer in beiden Pipelines abzuwickelnden komplizierteren Berechnung in konkrete Befehle daran scheitert, daß ausgerechnet die aktuell erforderliche Kombination von Quell- und Zieloperanden nicht vorgesehen ist. Dies trifft zwar kaum für klassische Anwendungen wie etwa die Matrixmultiplikation zu, jedoch schon bei der Vektortransformation (im Sonderfall der Prozedur lmtransf) ergeben sich Probleme. Welcher Tanz aufgeführt werden muß, um dort die richtigen Zwischenergebnisse zum richtigen Zeitpunkt weiterverarbeiten zu können, ist in der Beschreibung der Prozedur lmtransf nachzulesen. Betrachtet man die Beschreibung der Kodierung der Befehle, findet man keinen Grund, warum nicht für die Kodierung des Pfadfeldes der pfam-Befehle mehr Bits spendiert wurden. Da aber der i860 nicht nur nicht mehr in Entwicklung ist, sondern schon nicht mehr hergestellt wird, soll diese Frage nur als Anregung im Raum stehen bleiben und nicht näher konkretisiert werden. & Es folgt eine Tabelle der einzelnen Befehle, jeweils additiv und subtraktiv. Dabei bezeichnen M_res und A_res die Ergebnisse der Multiplikations- bzw. Additionspipeline. Befehl(+) Befehl(-) M_op1 M_op2 A_op1 A_op2 Lade fdest r2p1 r2s1 KR fsrc2 fsrc1 M_res A_res r2pt r2st KR fsrc2 T M_res KR A_res r2ap1 r2as1 KR fsrc2 fsrc1 A_res T A_res r2apt r2ast KR fsrc2 T A_res T,KR A_res i2p1 i2s1 KI fsrc2 fsrc1 M_res A_res i2pt i2st KI fsrc2 T M_res KI A_res i2ap1 i2as1 KI fsrc2 fsrc1 A_res T A_res i2apt i2ast KI fsrc2 T A_res T,KI A_res rat1p2 rat1s2 KR A_res fsrc1 fsrc2 T A_res m12apm m12asm fsrc1 fsrc2 A_res M_res A_res ra1p2 ra1s2 KR A_res fsrc1 fsrc2 A_res m12ttpa m12ttsa fsrc1 fsrc2 T A_res T A_res iat1p2 iat1s2 KI A_res fsrc1 fsrc2 T A_res m12tpm m12tsm fsrc1 fsrc2 T M_res A_res ia1p2 ia1s2 KI A_res fsrc1 fsrc2 A_res m12tpa m12tsa fsrc1 fsrc2 T A_res A_res mr2p1 mr2s1 KR fsrc2 fsrc1 M_res M_res mr2pt mr2st KR fsrc2 T M_res KR M_res mr2mp1 mr2ms1 KR fsrc2 fsrc1 M_res T M_res mr2mpt mr2mst KR fsrc2 T M_res T,KR M_res mi2p1 mi2s1 KI fsrc2 fsrc1 M_res M_res mi2pt mi2st KI fsrc2 T M_res KI M_res mi2mp1 mi2ms1 KI fsrc2 fsrc1 M_res T M_res mi2mpt mi2mst KI fsrc2 T M_res T,KI M_res mrmt1p2 mrmt1s2 KR M_res fsrc1 fsrc2 T M_res mm12mpm mm12msm fsrc1 fsrc2 M_res M_res M_res mrm1p2 mrm1s2 KR M_res fsrc1 fsrc2 M_res mm12ttpm mm12ttsm fsrc1 fsrc2 T M_res T M_res mimt1p2 mimt1s2 KI M_res fsrc1 fsrc2 T M_res mm12tpm mm12tsm fsrc1 fsrc2 T M_res M_res mim1p2 mim1s2 KI M_res fsrc1 fsrc2 M_res & 5.6.2.10 Addiere / Subtrahiere lange Integer (long integer add / subtract) fiadd.xx fsrc1,fsrc2,fdest pfiadd.xx fsrc1,fsrc2,fdest fisub.xx fsrc1,fsrc2,fdest pfisub.xx fsrc1,fsrc2,fdest .xx = .ss (32 bit), .dd (64 bit) Funktion (fiadd,fisub): fdest := fsrc1 +- fsrc2 Funktion (pfiadd,pfisub): fdest := Grafikpipeline_Stufe1 Grafikpipeline vorrücken Grafikpipeline_Stufe1 := fsrc1 +- fsrc2 Ist fdest nicht f0, darf es nicht fsrc1 oder fsrc2 sein. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fsrc2 nicht f0 oder dieser Befehl pfiadd oder pfisub ist und fdest vom nächsten Befehl in der Additions- oder Mulitplikationseinheit verwendet wird. +1 wenn fdest vom nächsten Befehl in der Grafikeinheit verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Der Assembler kodiert die Befehle "(p)fmov.ss" und "(p)fmov.dd" als Langintegeradditionen (p)fiadd.xx mit fsrc2 = f0. & 5.6.2.11 Z-Puffer Vergleich (z-buffer check 16 or 32 bit) fzchks fsrc1,fsrc2,fdest pfzchks fsrc1,fsrc2,fdest fzchkl fsrc1,fsrc2,fdest pfzchkl fsrc1,fsrc2,fdest Funktion (fzchks;fzchkl): Betrachte alle Operanden als Feld von vier;zwei Elementen je 16;32 bit fsrc1(3;1)..fsrc1(0), fsrc2(3;1)..fsrc2(0), fdest(3;1)..fdest(0), wobei das nullte das niederwertigste Element sei. PM := PM nach rechts geschoben um 4;2 bit MERGE := 0 Für i := 0 .. 3;1 : PM [i + 4;6] := fsrc2(i) <= fsrc1(i) (vorzeichenlos) fdest(i) := Minimum (fsrc1(i),fsrc2(i)) Funktion (pfzchks;pfzchkl): Betrachte alle Operanden als Feld von vier;zwei Elementen je 16;32 bit fsrc1(3;1)..fsrc1(0), fsrc2(3;1)..fsrc2(0), fdest(3;1)..fdest(0), wobei das nullte das niederwertigste Element sei. PM := PM nach rechts geschoben um 4;2 bit MERGE := 0 Für i := 0 .. 3;1 : PM [i + 4;6] := fsrc2(i) <= fsrc1(i) (vorzeichenlos) fdest(i) := Grafikpipeline_Stufe1 Grafikpipeline_Stufe1 := Minimum (fsrc1(i),fsrc2(i)) Ist fdest nicht f0, darf es nicht fsrc1 oder fsrc2 sein. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fdest vom nächsten Befehl in der Grafik-, Additions- oder Multiplikationseinheit verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Dieser Befehl ist für die Implementierung des Z-Puffer Algorithmus gedacht. Dabei wird davon ausgegangen, daß die Tiefenwerte Z als Integer in einer Genauigkeit von 16 oder 32 bit vorliegen. Es werden jeweils 2 oder 4 Vergleiche parallel durchgeführt und entsprechend die Minima in fdest zusammengesetzt. Außerdem werden in PM die benötigten Bits gesetzt, um mit dem Pixelspeicherbefehl pst die zu ändernden Pixel schreiben zu können. Dabei ist allerdings zu beachten, daß fzchk die höchstwertigen Bits in PM setzt, während pst die niederwertigsten prüft, es kann also nicht einfach ein pst auf das entsprechende fzchk folgen. Stattdessen müssen die beiden Befehle so ineinander verflochten werden, daß der Befehl pst immer genau dann zur Tat schreitet, wenn genügend befehle fzchk die benötigten Bits bis nach rechts geschoben haben. fzchkl Neues_Z,Z_Puffer,Z_Puffer ... //und noch drei fzchkl, um PM zu schieben pst.d Neue_Pixel,#8(Bild)++ //überschreibt nur die unsichtbaren Pixel mit neuen Werten. & 5.6.2.12 Pixel Addition (pixel add) faddp fsrc1,fsrc2,fdest pfaddp fsrc1,fsrc2,fdest Funktion (faddp) (Pixelgröße PS = 8;16;32 bit): MERGE := MERGE nach rechts geschoben um 8;6;8 bit fdest := fsrc1 + fsrc2 Betrachte alle Operanden als Feld von 4;4;2 Elementen je 16;16;32 bit fsrc1(3;3;1)..fsrc1(0) usw., wobei das nullte das niederwertigste Element sei. Für i := 0 .. 3;3;1 : Die oberen 8;6;8 Bit von MERGE(i) := die oberen 8;6;8 Bit von fdest(i) Funktion (pfaddp) (Pixelgröße PS = 8;16;32 bit): MERGE := MERGE nach rechts geschoben um 8;6;8 bit fdest := Grafikpipeline_Stufe1 Grafikpipeline_Stufe1 := fsrc1 + fsrc2 Betrachte alle Operanden als Feld von 4;4;2 Elementen je 16;16;32 bit fsrc1(3;3;1)..fsrc1(0) usw., wobei das nullte das niederwertigste Element sei. Für i := 0 .. 3;3;1 : Die oberen 8;6;8 Bit von MERGE(i) := die oberen 8;6;8 Bit von fsrc1(i)+fsrc2(i) Ist fdest nicht f0, darf es nicht fsrc1 oder fsrc2 sein. Alle Operanden sind Registerpaare je 64 bit. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fdest vom nächsten Befehl in der Grafik-, Additions- oder Multiplikationseinheit verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Dieser Befehl ist für Farbwertinterpolation gedacht, es werden jeweils Fixpunktzahlen akkumuliert und als RGB- oder Grauwerte im Register MERGE abgelegt, wobei bei RGB-Werte für jede Farbe ein faddp nötig ist, zuerst für Blau, dann für Grün und schließlich für Rot. Bei Grauwerten kann faddp nur jeden zweiten Punkt berechnen, es sind also je zwei ineinander verschränkte Befehle faddp nötig. Von einem Element im Feld der Pixel zum nächsthöheren kann ein Übertrag auftreten, da die Elemente nicht separat sondern als ein langer Integer addiert werden. Diesen Übertrag zu vermeiden ist der Programmierer selbst verantwortlich. & 5.6.2.13 Z-Puffer Addition (z-buffer add) faddz fsrc1,fsrc2,fdest pfaddz fsrc1,fsrc2,fdest Funktion (faddz): MERGE := MERGE nach rechts geschoben um 16 bit fdest := fsrc1 + fsrc2 Lade Bits 63..48 und 31..16 in MERGE aus (fsrc1 + fsrc2) Funktion (pfaddz): MERGE := MERGE nach rechts geschoben um 16 bit fdest := Grafikpipeline_Stufe1 Grafikpipeline_Stufe1 := fsrc1 + fsrc2 Lade Bits 63..48 und 31..16 in MERGE aus (fsrc1 + fsrc2) Ist fdest nicht f0, darf es nicht fsrc1 oder fsrc2 sein. Alle Operanden sind Registerpaare je 64 bit. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fdest vom nächsten Befehl in der Grafik-, Additions- oder Multiplikationseinheit verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Dieser Befehl ist gedacht für Distanzinterpolation, speziell für Z-Puffer zu 16 bit. Dabei soll die Interpolation mit Fixpunktzahlen je 32 bit erfolgen, wovon 16 bit die Vorkommastellen sind. Warum nicht gleich mit 32 bit Z-Puffer Werten gerechnet werden soll, ist unklar, würde es doch den Einsatz des Registers MERGE überflüssig machen ohne erhöhten Rechenaufwand. & 5.6.2.14 Register MERGE mit Zahl verodern (or with merge register) form fsrc1,fdest pform fsrc1,fdest Funktion (form): fdest := fsrc1 OR MERGE MERGE := 0 Funktion (pform): fdest := Grafikpipeline_Stufe1 Grafikpipeline_stufe1 := fsrc1 OR MERGE MERGE := 0 Ist fdest nicht f0, darf es nicht fsrc1 sein. Alle Operanden sind Registerpaare je 64 bit. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn fdest vom nächsten Befehl in der Grafik-, Additions- oder Multiplikationseinheit verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. Anmerkung: Dieser Befehl ist dazu gedacht, in ein Feld von Pixeln, die im Register MERGE angehäuft wurden, noch zusätzlich Bits einbauen zu können und dann MERGE in einem Fließkommaregisterpaar abzulegen, um die interpolierten Pixel dann zum Beispiel mit Hilfe des Z-Puffer Algorithmus ins Bild zu bringen. & 5.6.2.15 Übertrage von Integer nach Fließkommaregister (transfer integer to fp register) fxfr fsrc1,idest Funktion: idest := fsrc1 Es werden 32 Bit übertragen, es wird keine Formatkonversion vorgenommen. Die Grafikpipeline wird gelöscht. Wird in der Grafikeinheit ausgeführt. Ausführungszeit: 1 Taktzyklus +1 wenn idest vom nächsten Befehl verwendet wird. +2..4 wenn ein skalarer Fließkommabefehl aussteht. +... wenn bestimmte Cachezugriffe stattfanden. Anmerkung: Soll eine Formatkonversion vorgenommen werden, so ist einer der Befehle fix oder ftrunc zu verwenden. & 5.6.3 Sonstige Befehle Die übrigen Befehle sollen hier nicht beschrieben werden, da sie für die Aufgabenstellung völlig unerheblich sind. Der Vollständigkeit halber folgt eine Auflistung der Befehle: trap isrc1,isrc2,idest //software trap intovr //trap on integer overflow ld.c csrc2,idest //load from control register st.c isrc1,csrc2 //store to control register flush #const(isrc2) //flush internal cache line flush #const(isrc2)++ lock //begin interlocked sequence unlock //end interlocked sequence &Vektortransformation lmtransf 6 Vektortransformation lmtransf Diese Prozedur berechnet für jeden Vektor aus einer Liste anhand einer 4*4 Matrix einen neuen Vektor und legt diesen in einer neuen Liste ab. Die Eingabevektoren sind jeweils Tripel von Fließkommazahlen einfacher Genauigkeit, ebenso die Ausgabevektoren. Da für die Multiplikation mit der Matrix jedoch Quadrupel benötigt werden, werden die Eingangsvektoren um den vierten Wert 1 erweitert (virtuell), die Ausgangsvektoren durch den transformierten vierten Wert dividiert und um die entstehende 1 gekürzt. 6.1 Division durch Null Bei dieser Division kann selbstverständlich der Divisor Null auftreten. Dies ist für einen zu transformierenden Vektor (x,y,z,1) und ein Matrix, deren letzte Spalte (a,b,c,d) sei, genau dann der Fall, wenn gilt: ax + by + cz + d = 0 Ob dieser Fall tatsächlich nicht eintreten kann, kann ich nicht beurteilen, da jedoch die Aufgabenstellung davon ausgeht, daß diese Division durch Null nicht auftreten wird, wurde auf eine Überprüfung durch die Prozedur lmtransf verzichtet. Tritt der Fehler dennoch auf, so geht er zu Lasten des Anwenders. 6.2 Detailbeschreibung der Prozedur lmtransf und des Optimierungsvorganges. Wie in der Beschreibung des Befehles frcp schon erwähnt, sollten Divisionen nach Möglichkeit vermieden werden, weshalb für den Fall, daß die vierte Spalte der Matrix gleich (0,0,0,1) ist und demzufolge eine Division durch 1 erfolgen würde, diese bei allen Vektoren gespart wird. Für diesen Sonderfall wird eine optimierte Schleife durchlaufen. Zunächst soll die Beschreibung dieses Sonderfalls erfolgen. Dieser ist auch gut geeignet, den Aufbau einer optimierten Kernschleife zu erläutern, da er relativ übersichtlich ist. 6.2.1 Sonderfall ohne Division Für die Programmierung einer Prozedur in Assembler ist es notwendig, ständig Überblick über die zur Verfügung stehenden Resourcen, wie etwa Register und Pipelines, zu behalten. Dafür ist sowohl eine ausreichende Kommentierung schon bei der Erstellung des Programmes notwendig, als auch eine genaue Kenntnis der einzelnen Befehle des Prozessors und ihrer Effekte erforderlich. Dies trifft besonders für eine RISC-CPU wie den vorliegenden i860 zu. Um größere Verwirrung und den Verlust des Überblicks zu verhindern, ist es ratsam, die Umsetzung des Algorithmus in das optimierte Maschinenprogramm in mehrere Stufen zu gliedern. Als erste Stufe bietet sich an, in einer hochsprachenähnlichen Schreibweise (etwa Pascal-ähnlich) den Algorithmus niederzuschreiben, um ihn sodann in möglichst kleine Häppchen zerteilen zu können. Zusätzlich sollten die Ein- und Ausgaben des Algorithmus aufgelistet werden: // eingaben: eine liste von vektoren "a" je drei float, // eine 4*4 matrix "M". // ausgabe: eine liste von vektoren "b" je drei float. // for count = 1 .. length(list) : // a' := (a1,a2,a3,1) // b' := a' * M // for i = 1 .. 3 : bi := bi' / b4' rof // rof Die nähere Beschreibung einzelner Teilschritte erfolgt danach, bis eine ausreichend detailierte Beschreibung vorliegt. // die transformation im einzelnen: // bi' = a1'*M1i + a2'*M2i + a3'*M3i + M4i für i = 1..4. Bei der Umsetzung des Algorithmus in Assembler kann nun in kleinen Schritten vorgegangen werden, was jedoch immer noch chaotisch genug sein wird. Daher wird auch diese Umsetzung wieder in mehrere Stufen geteilt. Erst die letzte dieser Stufen sollte Feinoptimierung enthalten und sich etwa um folgende Dinge kümmern: - Füllen von Delayslots nach Sprungbefehlen (br, bri, call, calli, bla). Die entsprechenden Slots werden zunächst mit nop-Befehlen gefüllt. - Vertauschen von Befehlen, um Verzögerungen zu begegnen. In den Angaben zur Ausführungszeit der Befehle sind häufig die vorigen und folgenden Befehle und deren Operanden ausschlaggebend, weshalb es sinnvoll ist, aufeinanderfolgende Sequenzen an den entsprechenden Stellen auseinander zu ziehen und dann ineinander zu verschränken. Das geht natürlich nur, wenn die beiden Sequenzen voneinander unabhängig sind. In lmtransf wird dies besonders auffällig am Anfang, wo jeder zweite Befehl ein pfld ist. Da laut Handbuch ein pfld etwa zwei Zyklen benötigt, werden die Befehle zur Initialisierung diverser Register (t,kr,ki,lcc,r20,f15...) jeweils zwischen die pfld's gestreut, um diese aufzulockern. - Dual-instruction-mode. Es werden jeweils einfache Befehle und Befehle der Fließkommaeinheit abwechselnd angeordnet. Weicht die Anzahl der in einer Scheife befindlichen einfachen Befehle von der der Fliesskommabefehle nur unwesentlich ab, so werden nop's oder fnop's zugefügt, da diese keinen Einfluß auf die Ausführungszeit haben sollten, zum Beispiel in der Schleife sonderloop. Andere Optimierungsmaßnahmen sind eher strukturbedingt und müssen von vornherein erfolgen. Ganz wichtig ist hier die Verwendung der Pipelines. Ist abzusehen, daß eine Folge von Befehlen erstens nur aus Fließkommabefehlen besteht und zweitens in einigen Rechenschritten unabhängig voneinander ist, wird eine Pipelinesequenz aufgebaut. Um die Länge dieser Sequenz möglichst gering zu halten, werden zunächst alle Abhängigkeiten zwischen den einzelnen Rechenschritten ermittelt (Bild 6.1). Von diesen Abhängigkeiten wird die längste Kette genommen, um als Grundgerüst zu dienen. Im Sonderfall ist dies eine der drei Additionsketten. Bei der Notierung ist es nicht wichtig, die korrekten Befehlsnamen zu verwenden, da diese, besonders bei Verwendung von Dual-operation-Befehlen, noch variieren werden: //m1 m2 a1 a2 ar pfmul.ss f16,f12,f0 //M11 a1 - .m .m *1 pfam.ss f- ,f- ,f0 //a2 M21 M41 mr - .am .am pfam.ss f14,f24,f0 //a3 M31 ar mr <- .am .am pfam.ss f- ,f- ,f0 //- - ar mr <- .a .a pfadd.ss f- ,f- ,f8 //- - - - b1 Hierbei sollen die Kürzel .m, .a und .am andeuten, welche Pipelines durch die hier zu stehen kommenden Befehle bewegt werden müssen (a für Addition, m für Multiplikation). Der Befehl *1 benötigt drei Eingangsoperanden, die Adreßform des i860 läßt jedoch nur zwei zu. Allerdings stehen uns noch die Register KR, KI und T zur Verfügung. Es wird KR gewählt, um a2 abzulegen, da a2 auch in den anderen beiden Additionsketten benötigt wird. Außerdem werden die anderen zwei Additionsketten eingefügt, denn da die Pipelines dreistufig sind, fallen die anderen zwei Ketten genau dazwischen (In die freien Stellen .m, .a und .am): & & //m1 m2 a1 a2 ar k pfmul.ss f16,f12,f0 //M11 a1 - pfmul.ss f17,f12,f0 //M12 a1 - *2 pfam.ss f18,f12,f0 //M13 a1 - - - kr := a2 pfam.ss f- ,f- ,f0 //kr M21 M41 mr - pfam.ss f- ,f- ,f0 //kr M22 M42 mr - pfam.ss f- ,f- ,f0 //kr M23 M43 mr - pfam.ss f14,f24,f0 //a3 M31 ar mr <- pfam.ss f14,f25,f0 //a3 M32 ar mr <- pfam.ss f14,f26,f0 //a3 M33 ar mr <- pfam.ss f- ,f- ,f0 //- - ar mr <- pfam.ss f- ,f- ,f0 //- - ar mr <- pfam.ss f- ,f- ,f0 //- - ar mr <- pfadd.ss f- ,f- ,f8 //- - - - b1 pfadd.ss f- ,f- ,f9 //- - - - b2 pfadd.ss f- ,f- ,f10 //- - - - b3 Wieder benötigen wir in einer Zeile drei Quelloperanden (*2). Diesmal bleibt uns nichts anderes übrig, als einen weiteren Befehl in die Pipeline einzuschieben. Dabei geht jedoch der Zusammenhang der Ein- und Ausgänge verloren, da die Pipelines selber nach wie vor dreistufig sind. Um über das entstehende Loch, das für das Laden des Registers KR notwendig wurde, das Ergebnis der Multiplikationspipeline hinüber zu retten, muß dieses Ergebnis zwischengespeichert werden. Da es die Multiplikationspipeline verläßt, bietet sih das Register T an. Allerdings gibt es zwar einen pfam-Befehl, der KR und T lädt, jedoch keinen, der T und ein normales Register addieren kann (*3): r2apt.ss f13,f0, f0 //- - - - - kr := a2, T := mr *3 pfam.ss f- ,f- ,f0 //kr M21 M41 T - Die zweite Idee ist, einfach das Ergebnis der Multiplikation in einem normalen Fließkommaregister abzulegen. Beim Laden haben wir dann natürlich wieder das gleiche Problem wie vorher: Drei Operanden. Beim näheren Hinsehen entdeckt man schließlich noch ein "Register", das Zwischenergebnisse halten kann: Die Additionspipeline. Dieses "Register" ist zwar zeitlich begrenzt auf genau drei Befehle (von *4 bis *5), das stört hier aber nicht besonders. Durch geschickte Anordnung der Befehle ergibt sich die folgende Sequenz: //m1 m2 a1 a2 ar k,t pfmul.ss f18,f12,f0 //M13 a1 - pfmul.ss f16,f12,f0 //M11 a1 - pfmul.ss f17,f12,f0 //M12 a1 - *4 r2pt.ss f13,f0, f0 //- - t=0 mr - kr := a2 pfam.ss f28,f20,f0 //kr M21 M41 mr - pfam.ss f29,f21,f0 //kr M22 M42 mr - *5 pfam.ss f30,f22,f0 //kr M23 M43 ar - t := 0 pfam.ss f14,f24,f0 //a3 M31 ar mr <- pfam.ss f14,f25,f0 //a3 M32 ar mr <- pfam.ss f14,f26,f0 //a3 M33 ar mr <- *6 pfam.ss f- ,f- ,f0 //- - ar mr <- pfam.ss f- ,f- ,f0 //- - ar mr <- pfam.ss f- ,f- ,f0 //- - ar mr <- *7 pfadd.ss f- ,f- ,f8 //- - - - b1 pfadd.ss f- ,f- ,f9 //- - - - b2 pfadd.ss f- ,f- ,f10 //- - - - b3 Hierbei muß sichergestellt sein, daß T=0 ist, da in der Additionspipeline mit T addiert wird. Dies muß sein, da es keinen pfam-Befehl gibt, der sowohl KR laden als auch ein Produkt und ein Fließkommaregister addieren kann. Aus diesem Grund werden auch in der Einleitung der Prozedur die Register KR und T gelöscht. Weil das ganze eine Schleife werden soll, ist nun zu überlegen, wieviele der letzten Befehle der Schleife mit Befehlen vom Anfang der Schleife überlagert werden können. In diesem Fall sind es sechs, was an der Kommentierung leicht abzulesen ist: Die Multiplikationspipeline wird in den letzten sechs Schritten nicht mehr geladen, einen ebensolangen Leerlauf weist die Additionspipeline auf. Wenn nun von den letzten sechs Befehlen zusätzlich die Aufgaben der ersten sechs übernommen werden können, werden diese ersten dennoch nicht überflüssig, da sie als Einleitung in die Schleife benötigt werden. Eine Ausleitung aus der Schleife am Ende ist hingegen nicht nötig, weil es keinen Unterschied macht, ob die Pipelines mit Nullen gefüllt werden oder mit überflüssigen Operanden. Das einzige Problem hierbei wird, daß die Ladepipeline mehr Vektoren aus dem Speicher holt, als verwendet werden (24 Byte), da dies aber nicht ins Gewicht fällt, wird dieser "Fehler" einfach in die Spezifikation eingearbeitet: Die Liste der Eingangsvektoren hat 24 Byte länger zu sein, als zur Unterbringung der relevanten Vektoren nötig, die überzähligen zwei Vektoren sollten (0,0,0) sein, um Ausnahmen zu verhindern. Bleibt, die Befehle zum Laden und Speichern der Vektoren sowie den Schleifensprungbefehl bla einzustreuen. Die Ladebefehle, die den nächsten Vektor in f12..f14 ablegen und den Übernächsten anfordern, fangen vor der Stelle *6 an, um f12 rechtzeitig gefüllt zu haben, und hören danach auf, um f14 nicht zu überschreiben, solange der alte Wert noch gebraucht wird. Der Befehl bla hat einen Delayslot und muß deshalb zunächst von einem fnop gefolgt werden. Dieser fnop wird dann durch den ersten Befehl der Schleife ersetzt. Ab Stelle *7 werden die Ergebnisse b1..b3 gespeichert. Bei Verwendung des Dual-instruction-mode sind zahlreiche Ausnahmen und Randbedingungen zu beachten. Wichtig für die Anordnung der Befehle ist vor allem, daß Anfang und Ende des Dual-instruction-mode angekündigt werden müssen. Deshalb ist es nicht ganz einfach, den Dual-instruction-mode am Ende der Schleife zu verlassen, und es müssen zwei fnop's eingefügt werden. 6.2.2 Normalfall mit Division Beim Normalfall mit Division wird genauso vorgegangen wie beim Sonderfall. Die längste Kette von Abhängigkeiten (Bild 6.2) ist hier die Berechnung von b4' gefolgt von 1/b4' und dann Multiplikation mit bi' (i = 1..3). In dieses Gerüst werden die Berechnungen der bi' (i = 1..3) eingefügt, dann werden die Enden der Schleife ineinangesteckt, soweit möglich. Anstatt die Herleitung zu demonstrieren, wird diesmal die fertige Schleife in ihre Bestandteile zerpflückt. Die Einleitung der Schleife wird nicht betrachtet. Als erster Teil wird das Gerüst, die Berechnung von 1/b4' herausgenommen: ...Mitte der Schleife: m12apm.ss f12,f19,f0 //a1 M14 r2pt.ss f13,f0, f0 // kr := a2 r2s1.ss r2p1.ss f31,f23,f10 //kr M24 M44 mr i2pt.ss ia1p2.ss m12apm.ss f14,f27,f0 //a3 M34 ar mr i2pt.ss mim1p2.ss m12apm.ss // ar mr ...Additionspipeline steht still (viermal pfmul)... r2p1.ss normalloop: (nächste Runde) r2p1.ss r2ap1.ss f0, f0, f11 // b4' m12apm.ss m12apm.ss frcp.ss f11,f7 //1/b4' init newton/raphson, kills M-pipe ...Berechnung des Kehrwertes durch zweifache Näherung: m12apm.ss f11,f7, f0 //b4' gs1 - - - gs = guess m12tpa.ss m12apm.ss r2s1.ss f15,f0, f0 //- - 2.0 mr - r2p1.ss mi2pt.ss f7, f0 // ki := gs1 ia1p2.ss f0, f0, f0 //ki ar gs2 := gs1*(2-gs1*b4') m12apm.ss i2pt.ss f11,f0, f0 // ki := b4' mim1p2.ss f7 //ki mr gs2 m12apm.ss r2pt.ss r2s1.ss f15,f0 //- - 2.0 mr r2p1.ss i2pt.ss f7, f0, f0 // ki := gs2 ia1p2.ss f0, f0, f0 //ki ar - - - res := gs2*(2-gs2*b4') m12apm.ss i2pt.ss f8, f0, f0 // ki := b1' ...Der nächste Befehl beendet die Kehrwertberechnung. ...Gleichzeitig werden die drei Multiplikationen mit bi' gestartet. mim1p2.ss f0, f0, f7 //ki mr gs3 m12apm.ss f9, f7, f0 //b2' gs3 pfmul.ss f10,f7, f0 //b3' gs3 pfmul.ss f8 // b1 pfmul.ss f9 // b2 pfmul.ss f10 // b3 Die Berechnungen der bi' (i = 1..3) sind jeweils wesentlich kürzer, da die Division fehlt. Berechnung von b1': ...Mitte der Schleife: r2pt.ss f13,f0, f0 // kr := a2 ...Ende der Schleife: pfmul.ss f12,f16,f9 //a1 M11 b2 pfmul.ss r2p1.ss normalloop: (nächste Runde) r2p1.ss f28,f20,f0 //kr M21 M41 mr - r2ap1.ss m12apm.ss m12apm.ss f0, f0, f0 //- - ar mr - m12apm.ss m12tpa.ss m12apm.ss f14,f24,f8 //a3 M31 - - tx r2s1.ss r2p1.ss mi2pt.ss f10 //- - - - ty ...vier Befehle später: mim1p2.ss f8, f10 // tx ty m12apm.ss r2pt.ss r2s1.ss f8 // b1' Berechnung von b2': ...Mitte der Schleife: r2pt.ss f13,f0, f0 // kr := a2 ...Ende der Schleife: pfmul.ss f12,f17 //a1 M12 pfmul.ss pfmul.ss f14,f25 //a3 M32 r2p1.ss f29,f21,f0 //kr M22 M42 mr normalloop: (nächste Runde) r2p1.ss r2ap1.ss // t := mr m12apm.ss f0, f0, f0 //- - ar mr m12apm.ss m12apm.ss m12tpa.ss // t ar m12apm.ss r2s1.ss r2p1.ss f9 // b2' Berechnung von b3': ...Mitte der Schleife: r2pt.ss f13,f0, f0 // kr := a2 normalloop: (nächste Runde) ...nach dem frcp-Befehl: m12tpa.ss f12,f18,f0 //a1 M13 m12apm.ss r2s1.ss r2p1.ss f30,f22,f9 //kr M23 M43 mr mi2pt.ss ia1p2.ss m12apm.ss f14,f26,f0 //a3 M33 ar mr - i2pt.ss mim1p2.ss m12apm.ss f0 // ar mr - r2pt.ss r2s1.ss r2p1.ss f10 // b3' Der nop-Befehl am Anfang der Schleife muß sein, da am Ende der Schleife der Dual-instruction-mode nicht bereits im bla-Befehl beendet werden darf, sondern erst einen Befehl später. Daher folgt der Schleife auch noch ein fnop als erste Hälfte eines Dual-instruction-mode Paars. Weder das nop noch das fnop kosten Zeit. Zuletzt wird die Rücksprungadresse vom Stack geholt und dieser korrigiert. & // Transformation einer Vektorliste anhand einer Matrix. // Eingaben: eine Liste von Vektoren "a" je drei float, // eine 4*4 Matrix "M". // Ausgabe: eine Liste von Vektoren "b" je drei float. // for count = 1 .. length(list) : // a' := (a1,a2,a3,1) // b' := a' * M // for i = 1 .. 3 : bi := bi' / b4' rof // rof // // Die Transformation im einzelnen: // bi' := a1'*M1i + a2'*M2i + a3'*M3i + M4i für i = 1..4. // // Für den Fall b4' = 1 muss die Division nicht durchgeführt werden // b4' = 1 gilt, wenn M44 = 1 und Mi4 = 0 für i = 1..3. // Daher wird zunächst die Matrix untersucht und für diesen // Sonderfall eine optimierte Schleife ohne Division durchlaufen. .text .align 8 // Alle float-Berechnungen erfolgen in single precision. // Freie register: r16..r20, f2..f31 (werden geändert !) // Eingabe Parameter: // r16 = Anzahl der Vektoren (length(list)) // r17 = Zeiger auf Eingangsvektoren, (a1.s,a2.s,a3.s,a1.s ...) // r18 = Zeiger auf Ausgangsvektoren, (b1.s,b2.s,b3.s,b1.s ...) // r19 = Zeiger auf 4*4 Matrix, (M11.s,M12.s,M13.s,M14.s,M21.s ... M44.s) // Ausgabe erfolgt in die Liste r18^ // die Matrix wird in den Registern f16..f31 gehalten. // a1..a3=f12..f14, b1..b3=f8..f10, b1'..b4'=f8..f11 // Temporäre Konstanten: // r20 = -1 // f15 = 1.0, später f15 = 2.0 //!Achtung: Es wird keine Überprüfung auf Division durch 0 gemacht, // hierum muss sich der Aufrufer kümmern. //!Achtung: Es werden jeweils zwei Vektoren (24 byte) mehr gelesen, als // in der Liste vorhanden. Diese Lesezugriffe dürfen nicht von der // MMU verhindert werden, die gelesenen Vektoren müssen (0,0,0) sein. .align 8 nop //für das korrekte alignment für dual-instruction-mode lmtransf: addu -4,r2,r2 //reserviere 1 long auf stack st.l r1,0(r2) //rette returnadresse pfld.d 0(r19),f0 //lade matrix f16..f31 := r19^ d.r2apt.dd f0,f0,f0 //clear t,kr,ki pfld.d 8(r19),f0 //(jeweils zwei Register) r2apt.dd f0,f0,f0 pfld.d 16(r19),f0 //alle zwei zyklen pfld i2apt.dd f0,f0,f0 pfld.d 24(r19),f16 orh 0x3F80,r0,r20 //1.0 = 0x3F800000 pfld.d 32(r19),f18 ixfr r20,f15 //"Konstante" f15 := 1.0 pfld.d 40(r19),f20 adds -1,r0,r20 //Konstante r20 := -1 pfld.d 48(r19),f22 adds -1,r16,r16 //Zähler um eins vermindern pfld.d 56(r19),f24 bc lmtransdone //Zähler < 1 -> ende pfld.l 0(r17),f26 //und fordere ersten a-Vektor an bla r20,r16,lminitbla//und bla-Schleife vorbereiten pfld.l 4(r17)++,f28 lminitbla: addu -4,r18,r18 //Listenzeiger für autoincr. vorbereiten pfld.l 4(r17)++,f30 pfeq.ss f0,f19,f0 //prüfe Sonderfall Mx4 = (0,0,0,1) pfld.l 4(r17)++,f12 //lade Eingangsvektor a. bnc normalfall //cc=0 -> Normalfall pfeq.ss f0,f23,f0 bnc normalfall pfeq.ss f0,f27,f0 bnc normalfall pfeq.ss f15,f31,f0 bnc normalfall //i=1..3: bi := a1*M1i + a2*M2i + a3*M3i + M4i sonderfall: //m1 m2 a1 a2 ar k,t pfmul.ss f18,f12,f0 //M13 a1 - pfld.l 4(r17)++,f13 pfmul.ss f16,f12,f0 //M11 a1 - d.pfmul.ss f17,f12,f0 //M12 a1 - r2pt.ss f13,f0, f0 //(kr)0 t=0 mr - kr := a2, add=Ehrenrunde r2p1.ss f28,f20,f0 //kr M21 M41 mr - pfld.l 4(r17)++,f14 d.r2p1.ss f29,f21,f0 //kr M22 M42 mr - d.r2ap1.ss f30,f22,f0 //kr M23 M43 ar - t=?*0 sonderloop: d.m12apm.ss f14,f24,f0 //a3 M31 ar mr <- pfld.l 4(r17)++,f12 //lade eingangsvektor a. d.m12apm.ss f14,f25,f0 //a3 M32 ar mr <- pfld.l 4(r17)++,f13 d.m12apm.ss f14,f26,f0 //a3 M33 ar mr <- nop d.m12apm.ss f12,f18,f0 //a1" M13 ar mr <- start next vector here pfld.l 4(r17)++,f14 d.m12apm.ss f12,f16,f0 //a1" M11 ar mr <- nop d.m12apm.ss f12,f17,f0 //a1" M12 ar mr <- nop d.r2pt.ss f13,f0, f8 //(kr)0 t=0 mr b1 kr := a2", add=Ehrenrunde fst.l f8, 4(r18)++ //speichere ausgangsvektor b [8.6.1.3] d.r2p1.ss f28,f20,f9 //kr M21 M41 mr b2 fst.l f9, 4(r18)++ d.r2p1.ss f29,f21,f10 //kr M22 M42 mr b3 bla r20,r16,sonderloop d.r2ap1.ss f30,f22,f0 //kr M23 M43 ar - t := ?*0 fst.l f10,4(r18)++ // fnop ld.l 0(r2),r1 //Returnadresse fnop addu 4,r2,r2 //restauriere Stack bri r1 //Rücksprung // nop //, pfmul ..,f0 stört nicht. //i=1..4: bi' := a1*M1i + a2*M2i + a3*M3i + M4i (i=4 vorrangig -> rcp) normalfall: //m1 m2 a1 a2 r# k,t pfmul.ss f19,f12,f0 //M14 a1 - pfld.l 4(r17)++,f13 ra1p2.ss f15,f15,f0 //- - 1.0 1.0 - pfld.l 4(r17)++,f14 r2pt.ss f13,f0, f0 //- - - - - kr := a2 r2p1.ss f31,f23,f0 //kr M24 M44 mr - m12apm.ss f0, f0, f15 //- - - - f15 := 2.0 m12apm.ss f0, f0, f0 //- - - - - m12apm.ss f14,f27,f0 //a3 M34 ar mr - m12apm.ss f12,f17,f0 //a1 M12 - - - m12apm.ss f12,f16,f0 //a1 M11 - - - d.m12apm.ss f14,f25,f0 //a3 M32 ar mr - r2p1.ss f29,f21,f0 //kr M22 M42 mr - normalloop: r2p1.ss f28,f20,f0 //kr M21 M41 mr - nop //[8.6.2.4] & [8.6.2.12] r2ap1.ss f0, f0, f11 //- - - - b4' t := mr m12apm.ss f0, f0, f0 //- - ar mr - m12apm.ss f0, f0, f0 //- - ar mr - frcp.ss f11,f7 //1/b4' init newton/raphson, kills M-pipe m12apm.ss f11,f7, f0 //b4' gs1 - - - gs = guess m12tpa.ss f12,f18,f0 //a1 M13 t ar - m12apm.ss f14,f24,f8 //a3 M31 - - tx r2s1.ss f15,f0, f0 //- - 2.0 mr - d.r2p1.ss f30,f22,f9 //kr M23 M43 mr b2' d.mi2pt.ss f7, f0, f10 //- - - - ty ki := gs1 d.ia1p2.ss f0, f0, f0 //ki ar - - - gs2 := gs1*(2-gs1*b4') pfld.l 4(r17)++,f12 m12apm.ss f14,f26,f0 //a3 M33 ar mr - pfld.l 4(r17)++,f13 i2pt.ss f11,f0, f0 //- - - - - ki := b4' pfld.l 4(r17)++,f14 mim1p2.ss f8, f10,f7 //ki mr tx ty gs2 m12apm.ss f12,f19,f0 //a1 M14 ar mr - r2pt.ss f13,f0, f0 //- - - - - kr := a2 r2s1.ss f15,f0, f8 //- - 2.0 mr b1' r2p1.ss f31,f23,f10 //kr M24 M44 mr b3' i2pt.ss f7, f0, f0 //- - - - - ki := gs2 ia1p2.ss f0, f0, f0 //ki ar - - - res := gs2*(2-gs2*b4') m12apm.ss f14,f27,f0 //a3 M34 ar mr - i2pt.ss f8, f0, f0 //- - - - - ki := b1' mim1p2.ss f0, f0, f7 //ki mr - - gs3 d.m12apm.ss f9, f7, f0 //b2' gs3 ar mr - d.pfmul.ss f10,f7, f0 //b3' gs3 - d.pfmul.ss f12,f17,f8 //a1 M12 b1 fst.l f8, 4(r18)++ //speichere Ausgangsvektor b. d.pfmul.ss f12,f16,f9 //a1 M11 b2 fst.l f9, 4(r18)++ d.pfmul.ss f14,f25,f10 //a3 M32 b3 bla r20,r16,normalloop r2p1.ss f29,f21,f0 //kr M22 M42 mr - fst.l f10,4(r18)++ // fnop lmtransdone: ld.l 0(r2),r1 //Returnadresse bri r1 //Rücksprung addu 4,r2,r2 // restauriere Stack &z/p-Puffer Routine zpbuf 7 z/p-Puffer Routine zpbuf Die Routine zpbuf erhält als Eingabe die Liste der transformierten Vektoren und eine Liste von Dreiecken. Als Ausgabe erzeugt sie in einen z-Puffer und einen p-Puffer gezeichnet ein Bild der beschriebenen Dreiecke. Um zu diesem Bild zu gelangen, werden die Dreiecke eins nach dem anderen jeweils am Rand der Puffer, am Bildfenster, abgeschnitten, geclippt. Es entstehen konvexe Polygone mit bis zu sieben Kanten. Diese werden entsprechend ihrer errechneten Entfernung vom Betrachter in den z-Puffer und den p-Puffer eingezeichnet. Der z-Puffer enthält die Entfernung des hier gezeichneten Punktes vom Betrachter, der p-Puffer enthält nicht direkt eine Farbe, sondern die Nummer des Dreieckes, das an dem jeweiligen Punkt sichtbar ist, oder -1 für den Hintergrund. 7.1 Datenformat Die Liste der transformierten Vektoren hat das gleiche Format wie die Vektorlisten bei lmtransf: Direkt aufeinanderfolgende Tripel (x,y,z) von Fließkommazahlen einfacher Genauigkeit. Die Liste der Dreiecke ist nur dahingehend festgelegt, daß jede Dreieckbeschreibung mit drei Indizes in die Vektorliste anfangen muß, welche die Eckpunkte angeben, gefolgt von einem Block zusätzlicher Daten fester Länge, die aber hier uninteressant sind, da für den z/p-Puffer Algorithmus nur die Eckpunkte benötigt werden (Bild 7.1). Um die Indizes als relative Zeiger in die Vektorliste verwenden zu können, müssen sie mit 12 multipliziert werden (Tripel von Zahlen je vier Byte). Die beiden Bildpuffer (z, p) sind zweidimensionale Felder, die Horizontale bildet den inneren Index, die Vertikale den äußeren. Die Elemente des p-Puffer sind Integer je 32 Bit, die des z-Puffer Fließkommazahlen einfacher Genauigkeit. 7.2 Detailbeschreibung Nach kurzer Einleitung (Laden von Konstanten, Vorbereiten von Zeigern) werden aus den Indizes erst relative Zeiger in die Vektorliste errechnet (r28..r30, ab zpdreieckloop), dann durch die Ladepipeline per pfld die drei Vektoren geladen und dabei die Zeiger zu absoluten summiert. Die drei Vektoren sollen schließlich in den Registern (f16,f17,f18), (f19,f20,f21) und (f22,f23,f24) landen. Allerdings werden von den Vektoren zunächst nur der y-Anteil komplett und der x-Anteil in die Pipeline geladen, wo dieser zunächst stecken bleibt. Hier kommt uns gerade recht, daß die Ladepipeline drei Stufen hat. Die Vektoren sollen nämlich beim Laden gleich vorsortiert werden, es soll der unterste Vektor der erste sein, also f17<=f20 und f17<=f23 gelten. Die Anteile der Vektoren werden auf jeweils eine andere Art sortiert: Der x-Anteil wurde bereits in der ursprünglichen Reihenfolge in die Ladepipeline geladen, er muß also beim Herausholen sortiert werden, der z-Anteil wird gleichzeitig in bereits sortierter Reihenfolge in die Ladepipeline geladen und schließlich linear herausgeholt. An dieser Stelle fällt sehr unangenehm auf, daß bei Daten, die durch die Ladepipeline geladen werden, jeweils die letzten drei das Problem mit sich bringen, daß sie nur aus der Ladepipeline herausgeholt werden können, indem nutzlosen Speicherstellen referenziert werden. Für jedes Anwerfen der Ladepipeline werden also drei überflüssige Speicherzugriffe gemacht (5.6.1.5). Für das Austauschen des y-Anteils von zwei Vektoren wird die Grafikpipeline zweckentfremdet (Befehle pfmov). Nachdem die Vektoren auf diese Weise geladen und teilweise sortiert wurden, wird grob überprüft, ob das beschriebene Dreieck sichtbar ist, um den Prozessor nicht unnötig mit dem folgenden, doch recht aufwendigen Sutherland Hodgman Algorithmus zu strapazieren. Außerdem wird auf Sichtbarkeit bezüglich des z-Anteils geprüft. Dabei werden alle Dreiecke, deren mindestens einer der Vektoren hinter dem Betrachter liegt, ausgeschlossen. Einen dreidimensionalen Sutherland Hodgman durchzurechnen, wäre gegen das Ergebnis ein unverhältnismäßig hoher Aufwand, da außer dem eigentlichen Clipping in z-Richtung noch einige zusätzliche Sichtbarkeitsüberprüfungen durchzuführen und zusätzliche Divisionen zu berechnen wären (5.6.2.4). & & Als nächstes werden die Koordinaten eines zusätzlichen Punktes berechnet, des Schnittpunktes der Horizontalen durch einen der oberen Eckpunkte mit der Gerade durch den anderen oberen und den unteren Eckpunkt (Bild 7.2). Dazu müssen eventuell zunächst die beiden "oberen" Punkte vertauscht werden, wenn einer nicht höher als der untere ist (Bild 7.3), da ansonsten eine Division durch Null drohen würde. Sind alle Punkte auf gleicher Höhe, dann ist daß Dreieck deformiert, flach, und wird nicht gezeichnet. Für den Punkt pmid2 müssen zwei Divisionen berechnet werden, die zu allem Unglück auch noch in Serie von einander abhängen. Es wurde für ein kleines Stück sogar auf die Verwendung der Pipelines verzichtet, da nicht ausreichend anderweitige Kalkulationen durchzuführen wären, mit denen die Pipelines hätten beschäftigt werden können. Anhand des Punktes pmid2 werden die Differenzen d_zx, d_zy sowie z_0 für die Interpolation der z-Werte eines beliebigen Punktes berechnet. Da die z-Koordinate für jeden beliebigen Punkt interpoliert werden kann, wird bei den folgenden Berechnungen, insbesondere beim Clipping, der z-Anteil nicht mehr mitgeführt. 7.2.1 Clippingschleife Für das sich durch das Clipping ergebende Polygon wird ein Feld bereitgestellt, das sieben Zahlenpaare faßt. Die drei Eckpunkte werden in die letzten drei Stellen geschrieben. Bei jedem Durchlauf der Sutherland Hodgman Schleife kann höchstens ein Punkt zusätzlich entstehen zu der Zahl der bereits errechneten, da das Eingabepolygon ein Dreieck und daher mit Sicherheit konvex ist. Das Ausgabepolygon kann somit jeweils ab einer Stelle weiter vorne abgelegt werden, ohne noch nicht gelesene Werte der Eingabe zu überschreiben (Bild 7.4). Für jeden der vier Durchläufe der Schleife muß mit einer jeweils anderen Fensterkante verglichen werden, für den Fall daß Clipping erforderlich ist, muß eine jeweils andere Schnittpunktberechnung ausgeführt werden. Da es beim i860 keinen indizierten Sprung gibt, mit dem anhand eines Zählers jeweils in eine andere Subroutine für den Vergleich beziehungsweise den Schnitt gesprungen werden könnte, liegt es nahe, die Adresse der jeweiligen Routine vorweg zu errechnen. Aber auch eine programmrelative Adressierungsart ist nicht verfügbar. Zumindest nicht auf den ersten Blick. Wenn man den Befehl call hingegen scharf anschaut, gibt sich dieser als Sequenz von zwei Befehlen zu erkennen (den time slot ignorierend): br zieladresse ld.l instruction_counter + 8, r1 Damit haben wir den Programmzähler im Register r1. Für den Fall, daß gar nicht gesprungen werden soll, legen wir die Zieladresse einfach hinter den auf den call folgenden Befehl. Selbstverständlich muß zuvor eine eventuell noch in r1 befindliche Rücksprungadresse irgendwohin gerettet werden. Mit diesem Trick wird also ein Zeiger auf die Subroutine shcmpleft geladen (nach r28), der in jedem Schleifendurchlauf um 16 (vier Befehle) erhöht wird, um den nächsten Vergleich zur Verfügung zu stellen. Außerdem ist (r28+8) der Zeiger auf die Schnittpunktberechnung, beziehungsweise auf den Einsprung zu dieser, da der Schnittpunkt wieder eine Division erfordert und somit recht aufwendig zu berechnen ist (shisecthori, shisectverti). In eben diesen Routinen ist neben der Division wieder so wenig zu errechnen, daß die Pipelinestruktur des i860 nur in begrenztem Umfang zur Geltung kommt. In der Schleife (shouterloop..shouternext) wird streng nach Sutherland Hodgman vorgegangen. Am Ende wird jeweils, sobald überhaupt keine Punkte ausgegeben wurden, das Dreieck als nicht sichtbar erkannt. & & 7.2.2 Zeilenweise scannen Das entstandene Polygon wird von unten nach oben zeilenweise gezeichnet. Dazu werden theoretisch die Kanten in linke und rechte Begrenzer sortiert (Bild 7.5). Die Eckpunkte liegen aber bereits in der Reihenfolge vor, wie sie auf dem Rand des Polygons liegen. Zusätzlich ist bekannt, daß entweder der erste oder der letzte der bis zu sieben Punkte der unterste ist, wenn nicht sogar beide (Bild 7.6). Wenn beide Punkte die untere horizontale Kante des Polygons bilden, ist damit auch klar, welche Punkte die linke und welche die rechte Begrenzung bilden, es sei denn die Punkte wären gleich, wodurch wieder der Fall einträte, daß es nur einen untersten Punkt gibt. Gibt es einen untersten Punkt, dann entscheiden die Steigungen der von ihm ausgehenden Kanten darüber, welcher der angrenzenden Punkte die linke und welcher die rechte Begrenzung bildet. Im der Routine wird dies allerdings erst in der Schleife erkannt, um unnötige Berechnungen von Steigungen zu vermeiden, ein Flag (r14) zeigt an, ob die Frage nach der linke und rechten Begrenzung schon geklärt ist. Die Schleife (zplineloop) fängt damit an, daß geprüft wird, ob für die nun folgende Zeile auf der linken oder rechten Seite eine neue Begrenzungskante vorliegt, in welchem Fall deren Steigung berechnet wird (Bild 7.7). Ist nur die linke oder nur die rechte Steigung zu berechnen, werden dennoch beide neu ermittelt, da dies keinen erheblichen Mehraufwand bedeutet, beide Berechnungen können durch die Pipelinestruktur des i860 nebeneinander versetzt erfolgen. Beim ersten Durchlauf der Schleife sind ohnehin meist zwei Steigungen zu berechnen. Ist die Steigung ermittelt (zpsteigungstimmt) wird der erste zu zeichnende Punkt in der Zeile links berechnet, wobei die x-Koordinate abgerundet wird, um den Punkt in das Raster der z/p-Puffer zu fügen. Eine Fließkommazahl zu runden und wieder als Fließkommazahl abzulegen ist ein ziemlicher Aufwand, da das Ergebnis des Befehles ftrunc ein Integer ist, der zwar in einem Fließkommaregisterpaar abgelegt wird, aber mit Aufwand in eine Fließkommazahl doppelter Genauigkeit zurück gerechnet sein will, da es keinen Befehl float gibt. Stehen diese Startwerte für die Interpolation der Tiefe z bereit, kann endlich die zentrale Schleife eingeleitet werden. Dies geschieht ähnlich wie in lmtransf, indem zunächst die auszuführenden Befehle linear notiert werden, dann nops eingefügt werden, wo ohnehin Verzögerungen auftreten, daß heißt dort, wo nops gratis sind, und dann der Schleife Anfang mit ihrem Ende überlagert wird, soweit wie das möglich ist. Da diese Schleife sehr kurze ist - sie enthält, abgesehen von den beiden Speicherbefehle, nur drei Befehlspaare, - überlagert sie sich selbst mehrfach, will heißen, bevor ein Ergebnis vorliegt, muß die Schleife mehrfach durchlaufen werden. Den logischen Anfang macht der Befehl pfadd, der den Interpolationssummanden auf die Tiefe z aufaddiert. Diese Addition kommt erst im übernächsten Durchlauf der Schleife aus der Pipeline, sie wird durch pfgt und wiederum pfadd befördert und durch pfgt im dritten Schleifendurchlauf schließlich entnommen. Während des zweiten Durchlaufes wird der Wert des z-Puffers durch den Befehl fld geladen, er wird im dritten Durchlauf dann mit dem frisch berechneten Interpolanden verglichen (pfgt), das Ergebnis dieses Vergleiches landet im Prozessorstatusregister und wird im vierten Durchlauf der Schleife vom Befehl bnc genutzt, um zu entscheiden, ob der Punkt gezeichnet wird oder nicht (fst, fst). Daß bei der Berechnung der Tiefe z jeweils 2*d_zx addiert wird und nicht nur d_zx, liegt daran, daß nicht auf den letzten Wert von z aufsummiert wird, sondern auf den vorletzten. Es sind ja immer zwei Additionen in der Pipeline unterwegs, die letzte steht noch nicht zur Verfügung, wenn die neue berechnet werden soll, also wird auf die vorletzte zurückgegriffen. Die Nummer, die in den p-Puffer eingetragen wird, ist die Nummer des Dreieckes. Die Dreiecke werden jedoch rückwärts durchgezählt, daß heißt, das erste der n Dreiecke hat die Nummer n-1, das letzte die Nummer Null. Die innere Schleife endet ebenso abrupt wie die Kernschleifen in lmtransf: Bereits zuviel geladene und verglichene Werte werden einfach wieder abgeworfen. Deshalb muß auch hier der Zugriff auf die hinter dem z-Puffer liegenden folgenden zwei Stellen (8 Byte) möglich sein. & // Zeichne Dreiecke in z/p-Puffer (mit clipping) // Eingaben: Eine Liste von Dreiecken "d" je drei Indizes (##), // eine Liste von Vektoren "a" je drei float, // Größe (Fenster) und Instanz eines z/p-Puffers // Ausgabe: Veränderung des z/p-Puffers // // Die Vektoren müssen derart transformiert sein, dass sie dem Fenster // des Puffers entsprechen. Es wird also nicht das Einheitsfenster // (0..1,0..1) angenommen, sondern (0..windowx,0..windowy). // // for all d : // d = (pbot,pone,ptwo) with pbot.y < pone.y, pbot.y < ptwo.y // calc pmid2, d_zx, d_zy, z_0. (level at origin) // clip d to viewport (-> convex polygon) by sutherlandhodgeman // if visible then // take lowest point(s) to start // y = trunc (lp(0).y) // loop // if next line at left then calc new d_xl, xl. fi (exit when last) // if next line at right then calc new d_xr, xr. fi // calc zl for trunc(xl) // horizontal line to z/p-buffer (y,trunc(xl),trunc(xr),zl,d_zx) // inc(y,1), inc(xl,d_xl), inc(xr,d_xr) // end // fi // rof // // clip+sort: // sutherland-hodgeman // // calc pmid2: (intersection ptop..pbot with horizontal at pmid.y) // pmid2.y = pmid.y // pmid2.x = pbot.x + (ptop.x-pbot.x) / (ptop.y-pbot.y) * (pmid.y-pbot.y) // pmid2.z = pbot.z + (ptop.z-pbot.z) / (ptop.y-pbot.y) * (pmid.y-pbot.y) // if ptop.y = pbot.y then not visible // // calc d_zx (f12): // d_zx = (pmid.z-pmid2.z) / (pmid.x-pmid2.x) // if pmid2.x = pmid.x then not visible // // calc d_zy (f13): // d_zy = (ptop.z-pbot.z - (ptop.x-pbot.x) * d_zx) / (ptop.y - pbot.y) // // calc z_0 (f11): // z_0 = pmid.z - (d_zx * pmid.x) - (d_zy * pmid.y) // // calc d_xl: // if line is vertical then d_xl = 0 else // d_xl = (le.x - lb.x) / (le.y - lb.y) // wobei lb, le die Endpunkte der Strecke sind // // calc xl: // if line is vertical then xl = lp(i).x else // xl = lb.x + d_xl * (y - lb.y) // // calc zl: // zl = z_0 + (d_zx * trunc(xl)) + (d_zy * y) // // horizontal line: // for x = trunc(xl) .. trunc(xr) : // at (x,y) z/p-buffer ?= zl/#p // zl += d_zx // rof .text .align 8 // Es werden floats in single precision verwendet. // Freie Register: r12..r31, f2..f31 (werden geändert) // Eingabe Parameter: // r16 = Anzahl der Dreiecke // r17 = Zeiger auf die Liste der Dreiecke. Die ersten drei long // jedes Dreieckes sind Indizes in die Vektorliste r19. // r18 = Länge eines Feldes in r17 ("Inkrement je Dreieck") // r19 = Zeiger auf die Liste der transformierten Vektoren (^single prec.) // r20 = Zeiger auf den z-Puffer (y*x*single prec.) // r21 = Zeiger auf den p-Puffer (y*x*long) // r22 = Breite der Puffer in Elementen (x) (16 bit) // r23 = Höhe der Puffer in Elementen (y) (16 bit) // r24 = Zeiger auf einen temporären Puffer (56 byte) // Ausgabe erfolgt in die Puffer r20^,r21^ // Temporäre Konstanten: // r12 = -1 // f2 = 2.0 // f3 = 1.0 // f14 = float (r22) // f15 = float (r23) // f30,f31 = 0x4330.0000.0000.0000, // was das BIAS für Konversion Integer -> double ist. // // Befehle die durch die Optimierung in andere Prozedurbereiche gerutscht // sind, sind dort mit // >> gekennzeichnet, an ihrer alten Stelle mit // // << auskommentiert (beziehungsweise umgekehrt). zpbuf: addu -4,r2,r2 //reserviere 1 long auf stack st.l r1,0(r2) //rette returnadresse orh 0x3F80,r0,r31 //1.0 (single precision) ixfr r31,f3 adds -1,r0,r12 //konstante r12 = -1 addu 4,r19,r19 //r19 zeige jeweils auf vektor.y //vektor.x: -4(r19), vektor.z: +4(r19) fadd.ss f3,f3,f2 //2.0 (single precision) orh 0x4330,r0,r31 ixfr r31,f31 fmov.ss f0,f30 //f30,f31 = BIAS für Konversion (double) fmov.ss f31,f29 //Konversion Integer -> single ixfr r22,f28 fsub.dd f28,f30,f26 fmov.ds f26,f14 //breite fürs clipping =float(r22) ixfr r23,f28 fsub.dd f28,f30,f26 fmov.ds f26,f15 //höhe fürs clipping =float(r23) zp3eckfertig: zpnotvisible: // br zpdreieckloop // nop // zpdreieckloop: adds -1,r16,r16 //zähler um 1 vermindern bc zpbufdone //zähler < 1 -> ende ld.l 0(r17),r28 //r28..r30:3 indizes in die vektorliste shl 2,r28,r28 //diese indizes werden mit 12 multipliziert shl 1,r28,r31 //um als relative adresse zu r19^ zu addu r31,r28,r28 //fungieren (12 = 8+4). ld.l 4(r17),r29 pfld.l r19(r28)++,f0 // >> shl 2,r29,r29 shl 1,r29,r31 addu r31,r29,r29 ld.l 8(r17),r30 pfld.l r19(r29)++,f0 // >> shl 2,r30,r30 shl 1,r30,r31 addu r31,r30,r30 // << pfld.l r19(r28)++,f0 //drei punkte (f16,f17,f18),(f19,f20,f21) // << pfld.l r19(r29)++,f0 //und (f22,f23,f24), dann gleich sortieren. pfld.l r19(r30)++,f0 pfld.l -4(r28),f17 //y1..y3 laden, x1..x3 in die loadpipe. pfld.l -4(r29),f20 addu r18,r17,r17 //addiere für nächstes dreieck pfld.l -4(r30),f23 //sortiere die punkte nach y, so dass pfgt.ss f17,f20,f0 //der erste punkt der tiefste ist. pfmov.ss f17,f0 //fülle y1 in die graficpipeline bnc zpalessb //if b y2 pfld.l 4(r29),f19 br zpholez2 pfld.l 4(r28),f16 // zpalessb: //if a y3 pfld.l 4(r30),f22 pfld.l 4(r29),f19 br zpholez pfld.l 4(r28),f16 // zpaleast: //sortiere (a,b,c) pfld.l 4(r28),f16 pfld.l 4(r29),f19 zpholez2: pfld.l 4(r30),f22 zpholez: // >> pfmov.ss f0,f17 //hole y1 aus der Grafikpipeline // >> pfld.l 0(r24),f18 //hole z1..z3 aus der Ladepipe (schon sortiert) // >> pfld.l 0(r24),f21 //in die Pipeline geladen werden sollte nichts, // >> pfld.l 0(r24),f24 //was jedoch nicht geht, daher 0(r24) . pfgt.ss f0,f20,f0 //prüfe ob dreieck ganz ausserhalb liegt (grob) pfmov.ss f0,f17 // << bnc zpinnenb //if y2<0 and pfgt.ss f0,f23,f0 bc zpnotvisible //...y3<0 then zpinnenb: pfgt.ss f15,f17,f0 pfld.l 0(r24),f18 // << bnc zpnotvisible //if y1>=top then zpinnent: pfgt.ss f0,f16,f0 pfld.l 0(r24),f21 // << bnc zpinnenl //if x1<0 and pfgt.ss f0,f19,f0 bnc zpinnenl //...x2<0 and pfgt.ss f0,f22,f0 bc zpnotvisible //...x3<0 then zpinnenl: pfgt.ss f14,f16,f0 pfld.l 0(r24),f24 // << bc zpinnenr //if x1>=right and pfgt.ss f14,f19,f0 bc zpinnenr //...x2>=right and pfgt.ss f14,f22,f0 bnc zpnotvisible //...x3>=right then zpinnenr: pfgt.ss f0,f18,f0 bc zpnotvisible //if z1<0 then pfgt.ss f0,f21,f0 bc zpnotvisible //if z2<0 then pfgt.ss f0,f24,f0 pfsub.ss f20,f17,f0 // >> bc zpnotvisible //if z3<0 then // berechne pmid2 (temporär), z_0 (f11), d_zx (f12), d_zy (f13). //m1 m2 a1 a2 res k,t // << pfsub.ss f20,f17,f0 // y2 y1 pfeq.ss f20,f17,f0 // y2= y1 ? pfadd.ss f0, f0, f0 // - - bnc.t zp_y1lessy2 pfsub.ss f23,f17,f4 // y3 y1 dy = y2-y1 pfadd.ss f0, f20,f0 //vertausche (x2,y2,z2) <-> (x3,y3,z3) pfadd.ss f0, f23,f0 //wenn dann immer noch eine division pfadd.ss f0, f19,f0 //durch 0 drohen würde, ist das dreieck pfadd.ss f0, f22,f23 //flach -> nicht sichtbar pfadd.ss f0, f21,f20 pfadd.ss f0, f24,f22 pfsub.ss f20,f17,f19 // y2 y1 pfeq.ss f20,f17,f24 // y2= y1 ? pfadd.ss f0, f0, f21 // - - bc zpnotvisible pfsub.ss f23,f17,f4 // y3 y1 dy = y2-y1 zp_y1lessy2: frcp.ss f4, f5 //ry = 1/dy m12apm.ss f4, f5, f0 //dy ry - - ra1s2.ss f19,f16,f0 //- - x2 x1 ra1s2.ss f21,f18,f13 //- - z2 z1 sub = y3-y1 (my) r2s1.ss f2, f0, f0 //- - 2.0 mr mul r2pt.ss f5, f0, f6 //- - - - sub = x2-x1 (mx), KR := ry pfadd.ss f0, f0, f7 // - - sub = z2-z1 (mz) ra1p2.ss f0, f0, f0 //ry ar - - sub pfmul.ss f13,f6, f0 //my mx pfmul.ss f13,f7, f0 //my mz pfmul.ss f4, f5, f5 //dy ry mul->ry mrm1s2.ss f22,f16,f8 //- - x3 x1 mul = mx*my mrm1s2.ss f24,f18,f9 //- - z3 z1 mul = mz*my r2s1.ss f2, f0 ,f0 //- - 2.0 mr mul r2pt.ss f5, f0, f10 //- - - - sub = x3-x1, KR := ry pfadd.ss f0, f0, f11 // - - sub = z3-z1 ra1p2.ss f0, f0, f0 //ry ar - - sub pfmul.ss f0, f0, f0 //- - pfmul.ss f0, f0, f0 //- - pfmul.ss f8, f5, f5 //mxmy mr mul -> 1/(y2-y1) pfmul.ss f9, f5, f0 //mzmy 1/dy pfmul.ss f0, f0, f0 //- - mr2s1.ss f10,f0, f8 //- - f10 mr mul = mx*my/dy pfeq.ss f10,f8, f0 // f10=mr ? mr2p1.ss f0, f0, f9 //- - - - mul = mz*my/dy bc zpnotvisible pfadd.ss f0, f0, f4 // - - sub = d_zx divisor frcp.ss f4, f8 //rdx = 1/f4 (erste näherung) fmul.ss f4, f8, f10 fst.d f16,32(r24) // >> fsub.ss f2, f10,f10 fst.l f19,40(r24) // >> addu 16,r0,r30 // >> fmul.ss f8, f10,f8 //zweite näherung fst.l f20,44(r24) // >> addu 3,r0,r29 // >> fmul.ss f4, f8, f10 fst.d f22,48(r24) // >> pfsub.ss f2, f10,f0 // 2.0 tmp pfsub.ss f11,f9, f0 // z3z1 f9 r2pt.ss f8, f0, f0 //- - - - KR := f8 rat1p2.ss f0, f0, f0 //f8 ar - - sub r2p1.ss f0, f0, f9 //- - - - sub = z3-pmid2.z pfmul.ss f0, f0, f0 //- - pfmul.ss f9, f11,f11 //f9 mr mul = 1/(x3-pmid2.x) pfmul.ss f0, f0, f0 //- - pfmul.ss f0, f0, f0 //- - pfmul.ss f6, f12,f12 //mx mr mul = d_zx pfmul.ss f22,f12,f0 //x3 d_zx pfmul.ss f0, f0, f0 //- - r2s1.ss f7, f0, f0 //- - mz mr mul = mx*d_zx r2s1.ss f24,f0, f0 //- - z3 mr mul = x3*d_zx r2pt.ss f5, f0, f0 //- - - - KR := 1/dy ra1p2.ss f0, f0, f0 //1/dy ar - - add = mz-mx*d_zx r2p1.ss f0, f0, f11 //- - - - add = z3-x3*d_zx pfmul.ss f0, f0, f0 //- - pfmul.ss f0, f0, f13 //y3 mr mul = d_zy fmul.ss f23,f13,f10 //y3*d_zy // >> fsub.ss f11,f10,f11 //z_0 = z3-x3*d_zx-y3*d_zy //für den folgenden clipping-Algorithmus werden nur jeweils x und y //benötigt, daher wird z nicht gespeichert und nicht geclippt. // << fst.d f16,32(r24) //3 vektoren in temporäres feld ablegen, // << fst.l f19,40(r24) //dabei davor platz für 4 vektoren lassen // << fst.l f20,44(r24) // << fst.d f22,48(r24) //sutherlandhogdeman algorithm addu 24,r24,r26 // >> call shloadpctor1 //r1 := program counter + 8 = shcmpleft fsub.ss f11,f10,f11 // << //Verwende call um den Programmzähler zu laden //In jedem Durchlauf der Schleife shouterloop werden jeweils andere //Subroutinen für den Vergleich (aussen/innen: shcmp..) und für die //Berechnung des Schnittpunktes mit der Kante verwendet (shisect..). shcmpleft: //shcmp+0: bri r1 //vergleiche mit jeweils einer pfgt.ss f0,f16,f0 //Kante des Begrenzungsrechteckes br shisectverti //f16 = x, f17 = y fmov.ss f0,f8 //f14 = rechts, f15 = oben shcmpright: //CC = 1 -> ausserhalb bri r1 //left: x < 0 pfgt.ss f16,f14,f0 //right: x > rechts br shisectverti //bottom:y < 0 fmov.ss f14,f8 //top: y > oben shcmpbottom: bri r1 pfgt.ss f0,f17,f0 br shisecthori //zur Schnittpunktberechnung lade jeweils fmov.ss f0,f8 //x' bzw. y' nach f8 shcmptop: bri r1 pfgt.ss f17,f15,f0 // br shisecthori fmov.ss f15,f8 shisecthori: //berechne schnittpunkt der Strecke mit y=y' -> ausgeben // x' = x1 + (y'-y1)*(x2-x1)/(y2-y1) //m1 m2 a1 a2 res k,t fst.l f8,12(r15) //gib schnittpunkt aus (y') pfsub.ss f20,f17,f0 // y2 y1 pfeq.ss f20,f8, f0 // y2=y'? pfsub.ss f19,f16,f0 // x2 x1 bc shisecth2 //y2=y'! -> gib aus (x2,y') pfeq.ss f17,f8, f4 // y1=0? sub = y2-y1 frcp.ss f4, f5 //ry = 1/(y2-y1) bc shisecth1 //y1=y'! -> gib aus (x1,y') m12apm.ss f4, f5, f0 //y2y1 ry - - ra1s2.ss f8, f17,f6 //y' y1 - - sub = x2-x1 r2pt.ss f5, f0, f0 //- - - - KR := ry r2s1.ss f2, f0, f0 //- - 2.0 mr mul = ry*(y2-y1) pfeq.ss f6, f0, f7 // x2=x1 ? sub = y'-y1 m12apm.ss f6, f7, f0 //x2x1 y'y1 - - bc shisecth1 //x1=x2! -> gib aus (x1,y') ra1p2.ss f0, f0, f0 //ry ar - - sub pfmul.ss f0, f0, f0 //- - pfmul.ss f0, f0, f6 //- - mul = fct pfmul.ss f0, f0, f5 //- - mul = ry fmul.ss f4, f5, f7 //y2y1 ry fsub.ss f2, f7, f7 // 2.0 mr fmul.ss f5, f7, f7 //ry ar mul = 1/(y2-y1) fmul.ss f6, f7, f7 //fct mr fadd.ss f16,f7, f7 // x1 mr add = x' bri r1 fst.l f7,8(r15)++ // gib schnittpunkt aus (x') shisecth1: bri r1 fst.l f16,8(r15)++ // shisecth2: bri r1 fst.l f19,8(r15)++ // shisectverti: //berechne schnittpunkt der Strecke mit x=x' -> ausgeben // y' = y1 + (x'-x1)*(y2-y1)/(x2-x1) //m1 m2 a1 a2 res k,t fst.l f8,8(r15)++ //gib schnittpunkt aus (x') pfsub.ss f19,f16,f0 // x2 x1 pfeq.ss f19,f8, f0 // x2=x'? pfsub.ss f20,f17,f0 // y2 y1 bc shisectv2 //x2=x'! -> gib aus (x',y2) pfeq.ss f16,f8, f4 // x1=0? sub = x2-x1 frcp.ss f4, f5 //rx = 1/(x2-x1) bc shisectv1 //x1=x'! -> gib aus (x',y1) m12apm.ss f4, f5, f0 //x2x1 rx - - ra1s2.ss f8, f16,f6 //x' x1 - - sub = y2-y1 r2pt.ss f5, f0, f0 //- - - - KR := rx r2s1.ss f2, f0, f0 //- - 2.0 mr mul = rx*(x2-x1) pfeq.ss f6, f0, f7 // y2=y1 ? sub = x'-x1 m12apm.ss f6, f7, f0 //y2y1 x'x1 - - bc shisectv1 //y1=y2! -> gib aus (x',y1) ra1p2.ss f0, f0, f0 //rx ar - - sub pfmul.ss f0, f0, f0 //- - pfmul.ss f0, f0, f6 //- - mul = fct pfmul.ss f0, f0, f5 //- - mul = rx fmul.ss f4, f5, f7 //x2x1 rx fsub.ss f2, f7, f7 // 2.0 mr fmul.ss f5, f7, f7 //rx ar mul = 1/(x2-x1) fmul.ss f6, f7, f7 //fct mr fadd.ss f17,f7, f7 // y1 mr add = y' bri r1 fst.l f7,4(r15) // gib schnittpunkt aus (y') shisectv1: bri r1 fst.l f17,4(r15) // shisectv2: bri r1 fst.l f20,4(r15) // shloadpctor1: addu r0,r1,r28 //adresse des zu verwendenden vergleiches // << addu 16,r0,r30 //starte mit 3 vektoren je 8 byte (16 = 8*(3-1)) // << addu 3,r0,r29 //vergleiche mit 4 Begrenzungskanten // << addu 24,r24,r26 //zeiger auf den ersten vektor (ausgang) shouterloop: addu r0,r26,r27 //zum lesen der eingangsvektoren addu r30,r26,r31 //zeiger auf den letzten eingangsvektor adds -8,r26,r15 //zählzeiger für die erzeugten bytes fld.l 8(r31),f16 //lade letzten vektor vorweg (geschloss. ring) calli r28 //liegt er ausserhalb ? fld.l 12(r31),f17 // bnc shinnerhalb shausserhalb: fmov.ss f16,f19 fmov.ss f17,f20 fld.l 8(r27)++,f16 //lade zweiten vektor für die strecke calli r28 fld.l 4(r27),f17 // bc shbeideaussen addu 8,r28,r31 calli r31 //output schnittpunkt nop //, leider nicht zu vermeiden shbeideinnen: fst.l f16,8(r15)++ //gib zweiten punkt aus fst.l f17,4(r15) adds -8,r30,r30 bc shouternext //kein vektor mehr ? shinnerhalb: fmov.ss f16,f19 fmov.ss f17,f20 fld.l 8(r27)++,f16 //lade zweiten vektor für die strecke calli r28 fld.l 4(r27),f17 // bnc shbeideinnen addu 8,r28,r31 calli r31 //output schnittpunkt nop //, leider nicht zu vermeiden shbeideaussen: //gib keinen punkt aus adds -8,r30,r30 bnc shausserhalb //noch ein vektor ? shouternext: subs r15,r26,r30 //neuer bytezähler 8 * (vektoren-1) bc zpnotvisible //kein erzeugter punkt -> unsichtbar addu 16,r28,r28 //nächste Begrenzungskante wählen adds -1,r29,r29 bnc.t shouterloop //schleife 4 mal durchlaufen, : adds -8,r26,r26 //je runde einen vektor vorher anfangen //r26, r15 : Zeiger auf ersten, letzten Vektor im Polygon. fld.d 0(r26),f16 //f16,f17: Erster Vektor links fld.d 0(r15),f18 //f18,f19: Erster Vektor rechts adds 8,r0,r27 //Vektoren sind aus der Liste zu lesen, die adds -8,r0,r28 //linken vorwärts r27(r26)++, die rechten //rückwärts von hinten r28(r15)++ or 1,r0,r14 //r14: eventuell noch links<->rechts tauschen pfeq.ss f17,f19,f0 //links.y=rechts.y bc zpdifferentpoint //wenn ungleich: den tiefsten als startpunkt //wählen pfgt.ss f17,f19,f0 //links.y > rechts.y (wähle kleinsten aus) bnc zplinkstiefst fmov.dd f18,f16 //mit dem letzten Vektor anfangen br zpevtlrichtigrum adds -8,r26,r26 //den ersten noch mal zurückstellen zplinkstiefst: fmov.dd f16,f18 //mit dem ersten Vektor anfangen br zpevtlrichtigrum adds 8,r15,r15 //den letzten noch mal zurückstellen .align 8 zpdifferentpoint: //wenn links.x > rechts.x, dann vertauschen pfeq.ss f16,f18,f0 bc zpevtlrichtigrum pfgt.ss f16,f18,f0 pfmov.dd f16,f0 //Bereite Tausch vor bnc zprichtigrum pfmov.dd f18,f18 //vertausche Vektoren pfmov.dd f0,f16 addu 0,r15,r31 //vertausche Zeiger addu 0,r26,r15 addu 0,r31,r26 adds -8,r0,r27 //vertausche Richtung adds 8,r0,r28 zprichtigrum: or r0,r0,r14 //Kein Tausch mehr nötig zpevtlrichtigrum: fix.sd f17,f6 //berechne y0 >= Vektor.y (>=0) fxfr f6,r30 fmov.ss f31,f7 //zurück nach float (für Vergleiche) fsub.dd f6,f30,f4 //weil es kein aufrunden auf den nächsthöheren fmov.ds f4,f24 //Integer gibt und weil wir neben dem Zähler pfgt.ss f17,f24,f0 //y0 = r30 die gleiche Zahl als Fliesskommazahl pfadd.ss f0, f24,f0 //y0 := y0 + 0 bnc zpaufgerundet //für Vergleiche mitführen. pfadd.ss f3, f24,f0 //y0 := y0 + 1 adds 1,r30,r30 //r30 = f24.s = y0 zpaufgerundet: ixfr r22,f4 //Breite einer Zeile im z/p-Puffer pfadd.ss f0, f0, f0 pfadd.ss f0, f0, f0 fmlow.dd f6,f4,f6 //Index auf die Zeile im z/p-Puffer ixfr r16,f10 //Nummer des Dreiecks (N-1..0) or r0,r0,r13 //Flag r13<>0 -> berechne d_xl, xl, d_xr, xr fxfr f6,r29 // = Zeilenbreite * Zeilennummer zplineloop: pfgt.ss f17,f24,f24 //Steht links ein neuer Punkt an ? pfadd.ss f0, f0, f28 //xr := xr + d_xr (vom Schleifenende) bc zplinkshoeher zplinkerpunkt: bte r26,r15,zp3eckfertig //fertig, wenn das Polygon alle ist fmov.dd f16,f20 //Wird Anfangspunkt der Strecke fld.d r27(r26)++,f16 //Lade neuen Endpunkt pfgt.ss f17,f24,f0 //Vielleicht gleich noch einer (wg. horizontal) bnc zplinkerpunkt fmov.ss f16,f26 //xl, pfeq.ss f16,f20,f0 fmov.ss f0,f27 //d_xl für den Fall: Strecke vertikal bc zplinkshoeher or 1,r0,r13 //Berechne neu d_xl, xl zplinkshoeher: pfgt.ss f19,f24,f0 //Steht rechts ein neuer Punkt an ? bc zprechtshoeher zprechterpunkt: bte r26,r15,zp3eckfertig //fertig, wenn das Polygon alle ist fmov.dd f18,f22 //Wird Anfangspunkt der Strecke fld.d r28(r15)++,f18 //Lade neuen Endpunkt pfgt.ss f19,f24,f0 //Vielleicht gleich noch einer (wg. horizontal) bnc zprechterpunkt fmov.ss f18,f28 //xr, pfeq.ss f18,f22,f0 fmov.ss f0,f29 //d_xr für den Fall: Strecke vertikal bc zprechtshoeher or 1,r0,r13 //Berechne neu d_xr, xr zprechtshoeher: bte r0,r13,zpsteigungstimmt //Neuberechnung von xl, d_xl, xr, d_xr. Wird alles in einem erledigt, da in //den Pipelines links und rechts jeweils abwechselnd berechnet werden. // d_xl = (l1x - l0x) / (l1y - l0y) (desgleichen d_xr, xr) // xl = l0x + d_xl * (y0 - l0y) //m1 m2 a1 a2 res k,t pfsub.ss f17,f21,f0 // l1y l0y pfsub.ss f19,f23,f0 // r1y r0y pfsub.ss f16,f20,f0 // l1x l0x pfsub.ss f18,f22,f4 // r1x r0x sub = dly pfadd.ss f0, f0, f8 // - - sub = dry frcp.ss f4, f5 //rly = 1/dly frcp.ss f8, f9 //rry = 1/dry m12apm.ss f4, f5, f6 //dly rly - - sub = dlx m12apm.ss f8, f9, f7 //dry rry - - sub = drx pfmul.ss f0, f0, f0 //- - r2s1.ss f2, f0, f0 //- - 2.0 mr mul r2s1.ss f2, f0, f0 //- - 2.0 mr mul r2pt.ss f5, f0, f0 //- - - - KR := rly r2pt.ss f9, f28,f28 //rly ar - - sub, KR := rry ra1s2.ss f24,f21,f0 //rry ar y0 l0y sub ra1s2.ss f24,f23,f0 //- - y0 r0y pfmul.ss f4, f5, f5 //dly mr mul = rly pfmul.ss f8, f9, f9 //dry mr mul = rry r2p1.ss f0, f0, f0 //- - - - r2s1.ss f2, f0, f4 //- - 2.0 mr sub = y0-l0y (yl0y) r2s1.ss f2, f0, f8 //- - 2.0 mr sub = y0-r0y (yr0y) r2pt.ss f5, f0, f0 //- - - - KR := rly r2pt.ss f9, f28,f28 //rly ar - - sub, KR := rry ra1s2.ss f0, f0, f0 //rry ar - - sub pfmul.ss f0, f0, f0 //- - pfmul.ss f6, f5, f5 //dlx mr mul = 1/dly pfmul.ss f7, f9, f9 //drx mr mul = 1/dry pfmul.ss f0, f0, f0 //- - pfmul.ss f4, f27,f27 //yl0y mr mul = d_xl pfmul.ss f8, f29,f29 //yr0y mr mul = d_xr pfmul.ss f0, f0, f0 //- - r2p1.ss f20,f0, f0 //- - l0x mr mul r2p1.ss f22,f0, f0 //- - r0x mr mul pfgt.ss f27,f29,f0 // d_xl > d_xr ? pfadd.ss f0, f0, f26 // - - add = xl pfadd.ss f0, f0, f28 // - - add = xr bnc zpkeintausch //wenn d_xl <= d_xr dann kein Tausch bte r0,r14,zpkeintauschb //schon mal vertauscht ? .align 8 //align für dual instruction mode ## nop ? d.pfmov.dd f16,f0 //Bereite Tausch vor d.pfmov.dd f18,f18 //vertausche Vektoren d.pfmov.dd f20,f16 addu 0,r15,r31 //vertausche Zeiger d.pfmov.dd f22,f22 addu 0,r26,r15 d.pfmov.dd f26,f20 //vertausche d_xl, d_xr, xl, xr addu 0,r31,r26 d.pfmov.dd f28,f28 adds -8,r0,r27 //vertausche Richtung pfmov.dd f0, f26 adds 8,r0,r28 fnop zpkeintausch: or r0,r0,r14 //nicht noch mal vertauschen. zpkeintauschb: zpsteigungstimmt: //m1 m2 a1 a2 res k,t pftrunc.sd f26, f0 // [xl] pfadd.ss f0, f31,f0 // h%BIAS pfadd.ss f0, f0, f0 // - - pftrunc.sd f28, f6 // [xr] add = [xl].d fxfr f6,r31 pfadd.ss f0, f0, f7 // - - add = h%BIAS pfsub.dd f6, f30,f0 // [xl] BIAS pfadd.ss f0, f0, f6 // - - add = [xr].d fxfr f6,r13 m12apm.ss f13,f24,f0 //dzy y0 - - d.pfmov.ds f4, f4 // [xl] add = [xl].d d.m12apm.ss f0, f0, f0 //- - - - d.r2pt.ss f12,f0, f0 //- - - - KR := d_zx subs r13,r31,r13 //xr-xl = anzahl punkte - 1 d.r2p1.ss f11,f4, f4 //dzx ar z_0 mr add = [xl].s adds r31,r29,r25 //Index (x,y) in den Puffer d.m12apm.ss f0, f0, f0 //- - - - shl 2,r25,r25 //als Index 4 byte je Element (single, long) d.m12apm.ss f0, f0, f0 //- - - - adds r25,r20,r25 //Zeiger in den Z-Puffer d.m12apm.ss f0, f0, f0 //- - ar mr subs r21,r20,r31 //relativer Abstand vom Z- zum P-Puffer d.pfadd.ss f0, f0, f0 // - - fld.l (r25),f5 //Ersten Wert aus Z-Puffer laden d.pfadd.ss f12,f12,f0 // dzx dzx adds r29,r22,r29 //Nächste Zeile (Index vorbereiten) d.pfadd.ss f12,f4, f4 // dzx zl add = zl adds -4,r31,r31 //...abzüglich Korrektur wegen fld.l 4(r25)++ d.pfgt.ss f5, f4, f0 // zbuf > zl ? bla r12,r13,zpmehrnext d.r2ap1.ss f4, f0, f6 //- - zl ar add = d_zx+d_zx fld.l 4(r25)++,f5 zpmehrnext: d.fnop bnc zpmehrdahinter d.fnop //neuer z-Wert in den z-Puffer: fst.l f4,-4(r25) //Korrektur wegen des fld.l 4(r25)++ d.fnop //Nummer des Dreieckes nach p-Puffer: fst.l f10,r31(r25) //r31 bereits korrigiert zpmehrdahinter: d.pfgt.ss f5, f4, f4 //Addition fertig -> vergleichen bla r12,r13,zpmehrnext d.pfadd.ss f6, f4, f0 //addiere 2*d_zx, weil je 2 additionen fld.l 4(r25)++,f5 //in der pipeline sind pfadd.ss f27,f26,f0 //xl := xl + d_xl adds 1,r30,r30 //r30 = f24.s = y0 pfadd.ss f3, f24,f0 //y0 := y0 + 1 nächste Zeile or r0,r0,r13 //Flag r13<>0 -> berechne d_xl, xl, d_xr, xr pfadd.ss f29,f28,f0 //xr := xr + d_xr br zplineloop pfadd.ss f0, f0, f26 // zpbufdone: ld.l 0(r2),r1 //returnadresse bri r1 //rücksprung addu 4,r2,r2 //: restauriere stack &Schnittstellenroutine Radiosity 8 Schnittstellenroutine Radiosity Diese Routine bildet das eigentliche Modul, das vom Master Aufträge und Daten erhält, Ergebnisse abliefert und die Funktionen lmtransf und zpbuf sowie syscalls aufruft. Der Ablauf der Kommunikation wurde bereits im Abschnitt "3.3 Schnittstelle vom Modul zum Master (konkret)" beschrieben. Beim Aufruf von syscalls wird davon ausgegangen, daß der Stack nicht zerstört wird, allerdings werden darüber hinaus keine weiteren Annahmen gemacht. Daher müssen die Zeiger auf die Felder "kmif" und "syscall" nach jedem syscall wieder geladen werden. Bei der Initialisierung der Schnittstelle wird ein Feld für 16 globale Parameter angelegt, außerdem gleichzeitig ein eigener Stack von einem Kilobyte und ein Zwischenspeicher von vier Kilobyte. Die 16 globalen Parameter sind jeweils vier Byte lang, der Inhalt des Feldes ist folgender: +0 ^kmif +4 Adresse des Master +8 Nummer des Moduls +12 Breite des z-Puffers in Elementen +16 Höhe des z-Puffers in Elementen +20 Anzahl der Vektoren +24 Anzahl der Dreiecke +28 Anzahl der Bytes je Dreieck +32 Anzahl Zählpaare je Ergebnispaket vom Modul an den Master +36 Zeiger auf die Liste der transformierten Vektoren +40 Zeiger auf die Liste der nicht transformierten Vektoren +44 Zeiger auf die Liste der Dreiecke +48 Zeiger auf den z-Puffer +52 Zeiger auf den p-Puffer +56 Länge des z-Puffers in Bytes +60 Zeiger auf den Zählpuffer, in dem die Ergebnisse der Punktzählung gesammelt werden, wird als Paket an den Master geschickt. Bei der Zählung der Punkte wird in Gruppen zu je 1024 Dreiecknummern vorgegangen. Dabei ist wieder zu beachten, daß die von zpbuf in den p-Puffer eingetragenen Werte die Dreiecke rückwärts abgezählt repräsentieren, daß heißt, das in der Liste der Dreiecke mit n Einträgen erste Dreieck hat die Nummer n-1, das letzte die Nummer Null. Der p-Puffer wird für jede Gruppe von 1024 Dreiecken einmal durchgesucht, für alle Punkte, die mit einer zu dieser Gruppe gehörigen Nummer versehen sind, wird ein Zähler erhöht (rssummieren). Alle Zähler, die größer als Null sind, werden in der nächsten Schleife (rsauswerten) gesammelt und mit der Dreiecknummer in den Zählpuffer ausgegeben, um von dort an den Master gesendet zu werden. Dieser zweite Zählpuffer ist nötig, um eine Maximallänge für an den Master zurückzusendende Pakete festlegen zu können. Beim Übertragen in diesen Zählpuffer werden die 1024 Zähler wieder gelöscht. Die Subroutine rspuffervoll schickt den Zählpuffer an den Master, nachdem sie die Modulnummer voran und das Paar (0,0) hintan gestellt hat. Das letzte der Pakete wird nicht mit (0,0) sondern (0,1) abgeschlossen (r31). & // Schnittstelle des Moduls Radiosity // (Beschreibung siehe 3.3) // // Rechenphase: // objects[view] := lmtransf (matrix,objects[world]); // z_buf := infinite; // p_buf := 0; // zp_buf := f (objects[view]); // emmiting_light (objects) := sum (p_buf;p_buf = object); // .text .align 8 // Eingabe Parameter: // r16 = Zeiger auf das Kernel-Modul-Interface (kmif, 3.1) entrypoint: addu -4,r2,r2 //reserviere long auf Stack st.l r16,0(r2) //rette kmif-Zeiger ld.l 8(r16),r17 //^syscall ld.l 20(r17),r17 //^sethimem calli r17 //reserviere einen kleinen Puffer or 5184,r0,r16 //1024 + 64 + 4096 Byte ld.l 0(r2),r17 //kmif-Zeiger addu 1020,r16,r2 //nimm 256 long als Stack... addu 1024,r16,r15 //...den Rest für Parameter und als Puffer: // >> st.l r15,0(r2) //rette Pufferzeiger st.l r17,0(r15) //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 8(r17),r17 //waitbus calli r17 st.l r15,0(r2) // << ld.l 0(r2),r15 //Puffer ld.l 0(r16),r17 //Übertrage Paket in Puffer: st.l r17,4(r15) //Adresse des Master ld.l 4(r16),r17 st.l r17,8(r15) //Nummer des Moduls ld.s 8(r16),r17 st.l r17,12(r15) //Breite des z-Puffers in Elementen ld.s 10(r16),r17 st.l r17,16(r15) //Höhe des z-Puffers in Elementen ld.l 12(r16),r17 st.l r17,20(r15) //Anzahl der Vektoren ld.l 16(r16),r17 st.l r17,24(r15) //Anzahl der Dreiecke ld.l 20(r16),r17 st.l r17,28(r15) //Anzahl der Bytes je Dreieck ld.l 24(r16),r17 //Anzahl Zählpaare je Ergebnispaket st.l r17,32(r15) //vom Modul an den Master ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 12(r17),r17 //^freebus calli r17 nop // ld.l 0(r2),r15 //Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem ld.l 20(r15),r16 //Anzahl der Vektoren addu 2,r16,r16 //Platz für 2 mehr (siehe lmtransf) shl 2,r16,r16 shl 3,r16,r18 // * 12 -> Anzahl Bytes addu r18,r16,r16 // calli r17 st.l r16,40(r15) ld.l 0(r2),r15 //Puffer st.l r16,36(r15) //Zeiger für die transformierten Vektoren ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem calli r17 ld.l 40(r15),r16 //Nochmal so viel Bytes ld.l 0(r2),r15 //Puffer st.l r16,40(r15) //Zeiger für die nicht transformierten Vektoren ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 4(r17),r19 //^sendbus ld.l 4(r15),r16 //Masteradresse addu 8,r15,r17 //Zeiger auf die Modulnummer calli r19 or 4,r0,r18 //4 byte übertragen ld.l 0(r2),r15 //Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 8(r17),r17 //^waitbus calli r17 nop // ld.l 0(r2),r15 //Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 12(r17),r17 //^freebus calli r17 nop // ld.l 0(r2),r15 //Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem ld.l 24(r15),r16 //Anzahl der Dreiecke ixfr r16,f4 ld.l 28(r15),r16 //Bytes je Dreieck ixfr r16,f6 fmlow.dd f4,f6,f6 calli r17 fxfr f6,r16 // Anzahl Bytes = Dreiecke * Bytes pro Dreieck ld.l 0(r2),r15 //Puffer st.l r16,44(r15) //Zeiger auf die Dreieckliste ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 4(r17),r19 //^sendbus ld.l 4(r15),r16 //Masteradresse addu 8,r15,r17 //Zeiger auf die Modulnummer calli r19 or 4,r0,r18 //4 byte übertragen ld.l 0(r2),r15 //Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem ld.l 12(r15),r16 //Breite des z-Puffer ixfr r16,f4 ld.l 16(r15),r16 //Höhe des z-Puffer ixfr r16,f6 fmlow.dd f4,f6,f6 fxfr f6,r16 shl 2,r16,r16 //Anzahl Bytes = Breite * Höhe * 4 calli r17 st.l r16,56(r15) // Länge des z-Puffers ld.l 0(r2),r15 //Puffer st.l r16,48(r15) //Zeiger auf den z-Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem calli r17 ld.l 56(r15),r16 //ebensolang wie der z-Puffer: der p-Puffer ld.l 0(r2),r15 //Puffer st.l r16,52(r15) //Zeiger auf den p-Puffer ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 20(r17),r17 //^sethimem ld.l 32(r15),r16 //Anzahl der Zählpaare bei der Auswertung shl 2,r16,r16 //..*4+12 -> Länge des Ausgabepuffers calli r17 adds 12,r16,r16 // ld.l 0(r2),r15 //Puffer st.l r16,60(r15) //Zeiger auf den Zählpuffer immerwieder: ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 8(r17),r17 //^waitbus calli r17 //Matrix erhalten nop // ld.l 0(r2),r15 //Puffer or r0,r16,r19 //^Matrix ld.l 36(r15),r18 //Ausgangsvektoren ld.l 40(r15),r17 //Eingangsvektoren call lmtransf //Transformiere ! ld.l 20(r15),r16 //Anzahl Vektoren ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 12(r17),r17 //^freebus calli r17 //Matrix freigeben nop // ld.l 0(r2),r15 //Puffer ld.l 48(r15),r20 //Zeiger auf den z-Puffer ld.l 52(r15),r21 //Zeiger auf den p-Puffer orh 0x7F00,r0,r16 //0x7F000000 = 2^127 ixfr r16,f16 //f16 := weit weg (Hintergrund) adds -1,r0,r22 ld.l 56(r15),r17 //Länge des z-Puffer in Bytes shr 2,r17,r17 //..in long ixfr r22,f20 //f20 := -1 (Integer) addu -4,r20,r18 //autoincrement prekompensieren adds -1,r17,r17 //Anzahl Wiederholungen - 1 bla r22,r17,rsloeschen addu -4,r21,r19 // rsloeschen: fst.l f16,4(r18)++ //z/p-Puffer löschen bla r22,r17,rsloeschen fst.l f20,4(r19)++ // ld.l 24(r15),r16 //Anzahl der Dreiecke ld.l 44(r15),r17 //Zeiger auf die Liste der Dreiecke ld.l 28(r15),r18 //Länge eines Feldes in r17 ld.l 36(r15),r19 //Zeiger auf die Liste der transformierten V. ld.l 12(r15),r22 //Breite der Puffer in Elementen ld.l 16(r15),r23 //Höhe der Puffer in Elementen call zpbuf addu 64,r15,r24 //, Zeiger auf einen temp. Puffer (56 Byte) ld.l 0(r2),r15 //Puffer // p-Puffer auswerten. Dies geschieht in Gruppen zu je 1024 Dreiecken, deren // Punkte gezählt werden. Die Zählung wird an den Host gesendet, dann // werden die nächsten 1024 Dreiecke bearbeitet adds -1,r0,r20 ld.l 24(r15),r21 //Anzahl der Dreiecke adds -1,r21,r21 shr 10,r21,r21 //Gruppenzähler addu 64,r15,r24 //1024-long Zählpuffer or r0,r0,r23 //Ausgabezähler rsgruppenext: or 511,r0,r19 bla r20,r19,rsgruppeloesch addu -8,r24,r18 // rsgruppeloesch: //lösche den Zählpuffer bla r20,r19,rsgruppeloesch fst.d f0,8(r18)++ // ld.l 56(r15),r17 shr 2,r17,r17 adds -1,r17,r17 //Elemente im p-Puffer - 1 bla r20,r17,rssummieren ld.l 52(r15),r16 //p-Puffer rssummieren: ld.l 0(r16),r18 shr 10,r18,r19 //eines der aktuellen 1024 Dreiecke ? btne r19,r21,rsfalschegruppe and 0x03FF,r18,r19 //ja: modulo 1024 als index shl 2,r19,r19 ld.l r19(r24),r22 //Eintrag um 1 erhöhen addu r19,r24,r19 addu 1,r22,r22 st.l r22,0(r19) rsfalschegruppe: bla r20,r17,rssummieren addu 4,r16,r16 // shl 10,r21,r16 or r0,r24,r18 or 1023,r0,r19 ld.l 0(r18),r17 rsauswerten: //Zählpuffer auswerten bte r0,r17,rsnullwertig //Mehr als null Punkte ? ld.l 32(r15),r31 ld.l 60(r15),r25 btne r23,r31,rsnichtvoll call rspuffervoll //Puffer ausgeben or r0,r0,r31 // rsnichtvoll: addu 1,r23,r23 shl 3,r23,r31 addu r25,r31,r31 st.l r17,-4(r31) //Anzahl Punkte für dieses Dreieck st.l r16,0(r31) //Nummer von diesem Dreieck (werden rückwärts rsnullwertig: // gezählt: n-1..0) addu 1,r16,r16 adds -1,r19,r19 fst.l f0,0(r18) //letzten Zähler löschen bnc.t rsauswerten ld.l 4(r18)++,r17 // nächsten Zähler laden adds -1,r21,r21 bnc rsgruppenext call rspuffervoll //letzter Puffer wird ausgegeben or 1,r0,r31 // br immerwieder nop // rspuffervoll: addu -28,r2,r2 //Rette diverse Register auf dem Stack: st.l r16,0(r2) st.l r18,4(r2) st.l r19,8(r2) st.l r21,12(r2) st.l r24,20(r2) st.l r1,24(r2) ld.l 0(r15),r17 //kmif-Zeiger ld.l 8(r17),r17 //^syscall ld.l 4(r17),r20 //^sendbus ld.l 4(r15),r16 //an den Master schicken ld.l 60(r15),r17 //den Zählpuffer shl 3,r23,r18 addu 12,r18,r18 //Anzahl Bytes = 8 * Paare + 12 addu r17,r18,r19 ld.l 8(r15),r16 //an den Anfang: Modulnummer st.l r16,0(r17) st.l r0,-8(r19) //Sendung abschliessen mit (0,0) calli r20 st.l r31,-4(r19) //...oder (0,1) für das letzte. ld.l 0(r2),r15 //Puffer ld.l 24(r2),r1 ld.l 20(r2),r24 ld.l 12(r2),r21 ld.l 8(r2),r19 ld.l 4(r2),r18 ld.l 0(r2),r16 adds -1,r0,r20 addu 28,r2,r2 ld.l 0(r2),r15 bri r1 or r0,r0,r23 // &Programmteil Raytracing 9 Programmteil Raytracing Für das in der Einleitung skizzierte Bildgenerierungsprogramm wäre neben den hier vorgestellten Routinen für das Verfahren Radiosity und einem Rahmenprogramm, das im Master läuft, noch ein Modul mit Funktionen für das Verfahren Raytracing zu implementieren. Dieses besteht zum einen wieder aus den beiden Kernroutinen lmtransf und zpbuf, da sowohl Vektoren transformiert als auch Sichtbarkeiten von Dreiecken geprüft werden müssen, hinzu käme eine weitere z-Puffer Routine, die neben dem z-Puffer nicht wie bisher einen p-Puffer führt, sondern über die Fläche des jeweiligen Dreieckes Normalenvektoren interpoliert und diese in einen Bildpuffer einträgt. Die Elemente dieses Bildpuffers wären also Tripel von Fließkommazahlen. Anhand dieser Normalen wäre es dem entsprechenden Rahmenprogramm dann möglich, gemäß dem Verfahren Raytracing Blickstrahlen durch die Szene zurück zu verfolgen. Im Großen und Ganzen lehnt sich die Struktur der entsprechenden Routine (sie werde znbuf genannt) stark an die der Routine zpbuf an: Wieder ist der Sutherland Hodgman Algorithmus zu durchlaufen, die Zeilen werden ebenfalls zeilenweise gescannt. Der einzige Unterschied wäre, daß nicht nur z-Werte interpoliert würden, sondern zusätzlich jeweils ein kompletter Normalenvektor. In einer Hochsprache wäre es kein großes Problem, diese Routine aus der bereits bestehenden zpbuf zu entwickeln. Da aber das Programmieren in Assembler, besonders in RISC-Assembler, viel mehr Ebenen umfaßt als das Programmieren in Hochsprachen - zusätzlich zum eigentlichen Algorithmus sind Register, Speicherbereiche, Pipelines, Abhängigkeiten zwischen Befehlen und allerlei Ausnahmen und Nebeneffekte zu beachten - und diese Ebenen nach Möglichkeit alle optimal bearbeitet werden sollen, wäre der Aufwand für die Entwicklung der Routine znbuf wahrscheinlich ebenso hoch wie der für zpbuf, wenn nicht sogar höher. Als Beispiel seien der dual-instruction mode und die dual-operation Befehle genannt. Die entsprechenden Sequenzen müßten, wollte man auch für znbuf möglichst optimale Ergebnisse erzielen, komplett neu zusammengestellt werden. &Epilog E.1 Compiler Programmieren ist eine Kunst und Assemblerprogrammierung ist eine Kunst für sich. So sehr diese auch den Intellekt fordern mag, kann nichts darüber hinwegtäuschen, daß Assemblerprogrammierung auf weiten Strecken zur eintönigen Routinearbeit werden kann. Nicht von ungefähr wurden Compiler schon sehr früh in der Geschichte des Computers entwickelt, immer an der Grenze der Leistungsfähigkeit der Maschinen. Der Wunsch nach Erledigen von Routinearbeit in möglichst kurzer Zeit ist immerhin eine der wenigen Möglichkeiten, den Bau von Computern zu rechtfertigen. Da der Bau eines Compilers für eine RISC-Maschine um etliches komplexer ist als das pure Programmieren einer solchen Maschine, schreckt natürlich jeder zunächst vor dieser Aufgabe zurück. Spätestens aber, wenn einem das Optimieren zu eintönig wird, zur Routinetätigkeit nämlich, wird der Wunsch nach einem brauchbaren Compiler wach und, je nach Ambition, der Wunsch, diesen im Zweifelsfall eigenhändig zu erstellen. Ein Blick zurück auf die bisher fertiggestellten Projekte, ihrerseits wenige an der Zahl, und die Tatsache, daß die Computerwissenschaft nach wie vor einem hohen Innovationsschub unterliegt und daher Produkte nicht besonders lange dem Stand der Technik entsprechen, schrecken von dem Vorhaben jedoch wieder ab, könnte es doch eintreten, daß der lang ersehnte Compiler fertiggestellt ist zu einem Zeitpunkt, da ihn schon niemand mehr haben will. Tatsächlich ist dieser Fall eingetreten: Es ist kein wirklich brauchbarer Compiler für den i860 bekannt, die Produktion des i860 ist jedoch bereits eingestellt. E.2 Intel Zwei Zitate aus dem Programmierhandbuch zum i860, Seite iv: "Intel übernimmt keinerlei Verantwortung für den Einsatz seiner Produkte, ebensowenig für irgendwelche Fehler in diesem Dokument, und geht keine Verpflichtung ein, die Informationen in diesem Handbuch zu aktualisieren." Seite v: "Service und Unterstützung für die Kunden sind Hauptmerkmale für den Erfolg eines Produktes." Unter der zusätzlichen Annahme, daß man am Erfolg ihrer Produkte den Erfolg einer Firma ablesen kann, erhalten diese Zitate ihren besonderen Beigeschmack. Konkret kann ich jedem potentiellen Kunden nur raten, diese Aussagen von Intel zu beherzigen - auch wenn das erste Zitat kleingedruckt daherkommt, - um vor bösen Überraschungen beim Einsatz der gewählten Hardware gefeit zu sein. "Intel" und "i860" sind eingetragene Warenzeichen der Firma Intel. E.3 Literatur intel: i860 Microprocessor Family, Programmer's Reference Manual 1992, Intel Literature Sales, P.O.Box 7641, Mt. Prospect, IL 60056-7641 J. D. Foley, A. van Dam: Fundamentals of Interactive Computer Graphics, Addison-Wesley Publishing Company, Inc. 1982, ISBN 0-201-14468-9