Homepage von Boris Haase




Funkrechnen • Internet und Co • Programmieren mit Stair • Sortieren und Suchen  (Vorherige | Nächste)



Funkrechnen

Funkrechnen

Wie kann eine Speicherzelle mit möglichst vielen anderen durch Funkbausteine auf unterschiedlichen Frequenzen kommunizieren, um paralleles Rechnen zu unterstützen? Wie kann dadurch Sortieren von n Werten von O(n log n) auf O(1) verbessert und damit die Indizierung von Tabellen in Datenbanken überflüssig werden?

Wenn jeder Funkbaustein (gleichzeitig) auf der Frequenz sendet, die seinem in das kleinste positive natürliche dann für alle Werte gültigen Intervall transformierten Wert der zugehörigen Speicherzelle entspricht, dann empfangen die Gegenstellen diese neuen Werte in O(1) sortiert und können sie in O(n) ausgeben, wenn sie hierarchisch als Binärbaum organisiert sind, indem erst der 0-Knoten und dann der 1-Knoten an seinen übergeordneten sendet.

Wenn der übergeordnete Knoten noch nicht besetzt ist, speichert er den Wert des 0-Knotens. Für jeden weiteren freien übergeordneten Knoten wird entsprechend verfahren und der 1-Knoten nachgezogen. Dies ist in insgesamt O(log n) möglich und ermöglicht damit eine Ausgabe aller Knoten durch Traversieren des so entstandenen Binärbaums in O(n). Gleiche Werte werden zuerst durch Anhängen einer Reihenfolgezahl in O(n) verschieden gemacht.

Es ist klar, dass die Funkstrecken nur von der Größe der Funkbausteine abhängen und der Funk von außen nicht gestört werden darf. Hier bieten sich schwache (ggf. abgeschirmte) Signale und ein vorgegebener Frequenzbereich an. Evtl. ist erst eine Realisierung in Rechenzentren vorzusehen, solange die Funkbausteine noch relativ groß sind, was aber bspw. aufgrund des zunehmenden Cloud Computings kein großes Problem darstellt.

Bei weniger Frequenzen als zu übertragenden Werten nutze on (optischen) Richtfunk oder verdopple die Anzahl der Sendedurchläufe für jedes weitere Bit. Sind die Frequenzwerte kleiner als die zu übertragenden Werte, so ist für jede Übersteigung um einen weiteren Frequenzbereich ein weiterer Sendedurchlauf für das Nachsortieren erforderlich. Ggf. sind für zusätzlich auftretende Werte Überlaufbereiche (z. B. für Tabellenabfragen) sinnvoll.

Ordnet on die Funkbausteine in einer geraden Linie an und legt jeweils zwei dieser Linien kreuzweise übereinander, so können sie, wenn sie gegenüberliegend befestigt werden, ohne Überschneidung senden und on kommt mit einer oder wenigen Frequenzen aus. So können k + 1 Tabellen in einer Abfrage in O(1) statt in O(n logk n) verknüpft werden. Allerdings setzt die Notwendigkeit einer seriellen Abarbeitung dem parallelen (Funk-) Rechnen Grenzen.

Die Funktechnik kann auch benutzt werden, um paralleles Senden an parallele Addierwerke zu realisieren oder andere (lineare) Rechenoperationen umzusetzen (z. B. Vergleiche). In Verbindung mit Netzwerken und schneller Datenübertragung (z. B. DSL) kann im Verbund parallel gerechnet werden (z. B. um (lineare) Optimierungsaufgaben in linearer Zeit zu lösen). Auch assoziative Probleme lassen sich so (besser als im Gehirn) parallel lösen.

© 2011 by Boris Haase


Valid XHTML 1.0 • Haftungsausschluss • mail@boris-haase.de • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • Seitenbeginn