Thema: binäre Division

[erik.vikinger]

Hallo,

Und ja, ich lese alle Beiträge sehr sorgfältig, im Rahmen der Möglickeiten auf dem kleinen Android-Display.

Sicher? Dann vermute ich mal das Android keine Fragezeichen darstellen kann, Du hast genau 12 Stück davon in meinen Beiträgen komplett übersehen und nur dieses eine beachtet.


Grüße
Erik

[Dimension]

Dann vermute ich mal das Android keine Fragezeichen darstellen kann

Eines letzten Dinge, die noch funktionieren.

Zu deinen Fragen:

128 bit Dividend, Divisor gerne weniger.

Ein Branch des Ausführungs-Graphen. Also alles zwischen Bedingungen und Schleifen.

Jeder Kern ist für allgemeine Zwecke vorgesehen. Es sollen nur wenige Instruktionen angeboten werden, darunter Integer-Arithmetik, Bit-Manipulation und Vergleiche (alles gepackt in 8, 16, 32, 64 oder 128 bit), dazu Bedingungen und Schleifen, anstelle von Sprungbefehlen.

Vergleiche werden im Register gespeichert. Es gibt überhaupt keine Flags.

Bedingungen und Schleifen stellen nicht parallelisierbare Befehle dar. Ein Paket an parallelisierbaren Instruktionen wird zuerst komplett abgearbeitet.

Gruß

[Dimension]

Die Instruktionen verwenden den lokalen SRAM, anstelle von Registern. Daten werden explizit und 4k-seitenweise aus dem RAM geladen.

Der Zugriff auf Peripherie und Stringbefehle laufen im Speichercontroller.

Weitere Instruktionen betreffen die Verwaltung und den Nachrichtenaustausch zwischen den Kernen.

Damit viele weitere Fragen aufgeworfen zu haben fürchtend,
Gruß

Aaron

[erik.vikinger]

Hallo,

Dann vermute ich mal das Android keine Fragezeichen darstellen kann

Eines letzten Dinge, die noch funktionieren.

Soso, da bin ich aber froh das ich keines dieser smarten Phönchen habe.

128 bit Dividend, Divisor gerne weniger.

Aber die Größe des Divisors gibt vor wie viel Logik die Divisions-HW kostet, der Divisor bestimmt die Breite der Subtraktionen/Vergleiche und der Dividend gibt nur vor wie breit das Shift-Register ist von dem immer ein kleiner Teil (der so groß ist wie der Divisor) bearbeitet wird. Für meine CPU hab ich mir überlegt das ich zwei leicht unterschiedliche Divisionseinheiten haben will (wenn im FPGA noch Platz ist): eine mit voller Breite 128:64 = 64,64 (Dividend:Divisior = Quotient,Rest) die immer nur ein Bit pro Takt errechnet und eine mit reduziertem Divisor 128:24 = 64,24 die immer 4 Bit pro Takt errechnet. Da ich in der Slow-ALU eh mindestens einen Takt zum Vorbereiten der Parameter und selektieren der zuständigen Logik benötige kann ich dabei auch prüfen wie viele Bits im Divisor tatsächlich benutzt werden und damit sicher einen Großteil der Divisionen erheblich beschleunigen.

Ein Branch des Ausführungs-Graphen. Also alles zwischen Bedingungen und Schleifen.

Aha, Dir geht es also um Loop-Unrolling in Hardware. Das schätze ich mal als relativ Aufwendig ein da dabei die HW selbstständig ermitteln muss welche Variablen (Register) bei jeder Iteration neu benutzt werden (also parallelisiert werden können) und welche Variablen den Schleifenzähler darstellen (das muss nicht nur eine Variable sein und die muss auch nicht simpel Inkrementiert/Dekrementiert werden) und welche Variablen für alle Iterationen immer Konstant sind. Dazu kommt das die Hardware zuverlässig erkennen können muss welche Schleifen nicht parallelisierbar sind (selbst wenn die Abhängigkeit zwischen den Iterationen nicht linear ist und nur über den Speicher geht), schau Dir dazu mal den RC4-Verschlüsselungsalgorithmus an (das ist ein tolles Beispiel für sehr simplen Code bei dem man trotzdem nicht erkennen kann welche Iteration von welcher abhängt). Ich vermute mal das es einfacher ist sowas dem Compiler zu überlassen und dafür ein bisschen mehr Code-Cache zu haben (damit die Schleifen auch größer sein dürfen). Beim Pentium 4 war Loop-Unrolling extrem effektiv weil diese CPU relativ viele Befehle aktiv haben kann und der L1-Code-Cache hinter dem Decoder sitzt (die damaligen Intel-Compiler haben das Loop-Unrolling auch bis ins extrem getrieben und damit auch einen echten Vorteil gegenüber dem gcc raus geholt).

Jeder Kern ist für allgemeine Zwecke vorgesehen. Es sollen nur wenige Instruktionen angeboten werden, darunter Integer-Arithmetik, Bit-Manipulation und Vergleiche (alles gepackt in 8, 16, 32, 64 oder 128 bit), dazu Bedingungen und Schleifen

Also RISC mit SIMD.

anstelle von Sprungbefehlen.

Um allgemeine Sprungbefehle wirst Du nicht umhin kommen, überlege mal wie Du ein switch-Konstrukt umsetzen möchtest.

Vergleiche werden im Register gespeichert. Es gibt überhaupt keine Flags.

Also sowas wie Alpha, der hat auch keine Flags und prüft bei bedingten Befehlen direkt den Inhalt eines beliebigen Registers ob dies bestimmten Kriterien entspricht. Hast Du Dir schon mal überlegt was für Nachteile dieses Konzept haben kann? Meiner persönlichen Meinung nach ist es effektiver den Vergleich und den bedingten Sprung in einen Befehl zu vereinen also einen bedingten Sprung bauen der das Verhältnis zwischen 2 beliebigen Registern prüft (das geht sogar für Floating-Point ganz einfach), solange Du genug Bits in den Befehlen hast sollte das kein Problem sein (das Sprungziel muss auch nicht allzu viele Bits haben da bedingte Sprünge üblicherweise nur kurze Strecken springen).

Bedingungen und Schleifen stellen nicht parallelisierbare Befehle dar.

Das ist aber doof, Sprünge stellen ein interessantes Betätigungsfeld für spekulative Ausführung dar.

Hast Du schon mal an VLIW oder EPIC gedacht?
Kannst Du Bitte noch ein paar Sätze mit einer allgemeineren Zielbeschreibung dazu packen?  Damit man auch mal das große Ganze etwas besser erkennen kann.


Grüße
Erik