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 in \(\mathcal{O}(n \, \log \, n)\) auf \(\mathcal{O}(1)\) verbessert und damit die Indizierung von Tabellen in Datenbanken überflüssig werden?
Sendet jeder Funkbaustein (gleichzeitig) auf der Frequenz, die einem Wert der zugehörigen Speicherzelle entspricht, der in das kleinste positive natürliche und für alle Werte gültige Intervall transformiert wurde, dann empfangen die Gegenstellen diese neuen Werte in \(\mathcal{O}(1)\) sortiert und können sie in \(\mathcal{O}(n)\) ausgeben. Dies erfordert eine hierarchische Organisation als Binärbaum. Hierbei sendet erst der 0-Knoten und dann der 1-Knoten an den übergeordneten Knoten.
Ist der übergeordnete Knoten noch nicht besetzt, speichert er den Wert des 0-Knotens. Für jeden weiteren freien übergeordneten Knoten wird entsprechend verfahren und der 1-Knoten nachgezogen. Dies kann in insgesamt \(\mathcal{O}(\log \, n)\) geschehen und ermöglicht damit eine Ausgabe aller Knoten durch Traversieren des so entstandenen Binärbaums in \(\mathcal{O}(n)\). Das Anhängen einer Reihenfolgezahl in \(\mathcal{O}(n)\) macht gleiche Werte zuerst verschieden.
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. Da z. B. Cloud Computing zunimmt, stellt dies aber kein großes Problem dar.
Bei weniger Frequenzen als zu übertragenden Werten nutzen wir (optischen) Richtfunk oder verdoppeln 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 sinnvoll – etwa für Tabellenabfragen.
Ordnen wir die Funkbausteine in einer geraden Linie an und legen jeweils zwei dieser Linien kreuzweise übereinander, so können sie ohne Überschneidung senden, wenn sie gegenüberliegend befestigt werden. Dann kommen wir mit einer oder wenigen Frequenzen aus. In einer Abfrage lassen sich so \(k + 1\) Tabellen in \(\mathcal{O}(1)\) statt in \(\mathcal{O}(n \, \log_k \, n)\) verknüpfen. 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 wie etwa Vergleiche umzusetzen. Im Verbund lässt sich in Verbindung mit Netzwerken und schneller Datenübertragung (z. B. DSL) parallel rechnen – etwa um (lineare) Optimierungsaufgaben in linearer Zeit zu lösen. Auch assoziative Probleme lassen sich so parallel lösen – evtl. besser als im Gehirn.
© 2011-2019 by Boris Haase