Untergrenze für Arbeitsspeicher?

Hier ist eine vielleicht naive Frage, die mich gereizt hat: Gibt es eine asymptotische Untergrenze, um willkürlich großen Speicher zufällig anzusprechen? Mein Grund für die Annahme ist, dass der kürzeste Weg zu einem physisch gespeicherten Speicher durch den dreidimensionalen Raum führen muss und die Diagonale hier eine minimale Länge haben muss.$\Omega(\sqrt[3]{n})$

Wenn Sie beispielsweise beliebig viele Elemente sortieren, muss das Adressieren dieser Elemente möglicherweise etwas proportional zum Abstand kosten. Selbst wenn Sie zwischen jedem einzelnen Punkt in einem bestimmten Raum ein Hochgeschwindigkeitskabel haben, scheint es, als ob eine geometrische Grenze begrenzt ist höher als .$\Omega(n \lg n)$

Was ist falsch an meiner Argumentation?

Wenn Sie über Latenz sprechen, ja, das klingt für mich richtig. Eine Untergrenze für die Entfernung impliziert aufgrund von Überlegungen zur Lichtgeschwindigkeit eine Untergrenze für die Latenz. In der Praxis dominieren diese Überlegungen zur Lichtgeschwindigkeit jedoch wahrscheinlich erst, wenn die Speichermenge extrem groß ist.

Übrigens ist die Situation anders, wenn es um die Bandbreite (dh die Anzahl der pro Sekunde ausgeführten Arbeitsspeicheroperationen mit wahlfreiem Zugriff) als um die Latenz geht. Durch Sortieren von Netzwerken können viele Speicheroperationen mit wahlfreiem Zugriff gleichzeitig verarbeitet werden.

Eine wichtige Einschränkung ist, dass Sie anscheinend von einer Architektur ausgehen, in der links eine große CPU und rechts ein großer Speicher vorhanden sind und die irgendwie voneinander getrennt sind. Dies ist jedoch nicht unbedingt die einzige Möglichkeit, eine Berechnung zu strukturieren. Man kann eine Berechnung auch als parallele Berechnung strukturieren, bei der Sie ein 2-D- oder 3-D-Netz kleiner Prozessoren mit jeweils einem eigenen lokalen Arbeitsspeicher haben. Der Zugriff auf Ihren lokalen Speicher kann jetzt sehr schnell erfolgen, während der Zugriff auf weit entfernten Speicher langsam ist. In gewissem Sinne gibt es immer noch eine oder gebundene Operation, aber die$\sqrt{n}$$\sqrt[3]{n}$$n$ ist für den lokalen Speicher viel kleiner als für den weit entfernten Speicher. Wenn Ihr Algorithmus also so konzipiert ist, dass die meisten Speicheroperationen für den lokalen Speicher ausgeführt werden, können Sie möglicherweise die von Ihnen beschriebene Untergrenze (in einigen Fällen) "übertreffen" Sinn).

In der Computerarchitektur misst man häufig die Leistung einer Schaltung durch das Maß: Mit anderen Worten, die Fläche der Schaltung ( ) multipliziert mit der Zeit, die die Schaltung benötigt, um eine Berechnung ( ) abzuschließen . Wenn Sie möchten, können Sie sich dies als Preis-Leistungs-Verhältnis vorstellen: Es ist der Preis (der als proportional zur Fläche der Schaltung angenommen wird) geteilt durch die Leistung (die Anzahl der Berechnungen, die pro durchgeführt werden können) zweitens, dh die Umkehrung von$AT$$A$$T$$T$). Eine Standardarchitektur mit einer einzigen bulligen CPU und einem großen Speicher ist nicht immer die optimale Architektur. Manchmal können Sie große Beschleunigungen (mehr als einen konstanten Faktor) erzielen, indem Sie parallele Berechnungen oder andere Architekturen verwenden. Dies ist zumindest teilweise auf genau das Problem zurückzuführen, das Sie erwähnt haben: Es ist viel schneller, auf Speicher in Ihrer Nähe zuzugreifen, als auf Speicher in der Ferne. Das Caching (z. B. L1-Cache, L2-Cache usw.) basiert ebenfalls auf demselben Prinzip.

Im Folgenden finden Sie ein Beispiel für ein Papier in der Welt der Kryptographie, in dem der Entwurf von Spezialschaltungen für kryptoanalytische Aufgaben in Betracht gezogen und diese Aspekte berücksichtigt werden. Beispielsweise verfügt es über eine Reihe von Prozessoren, einen großen Speicher und ein Sortiernetzwerk zwischen den beiden, um Speicherzugriffe von den Prozessoren zum Speicher weiterzuleiten. Dies ermöglicht es, dass eine große Anzahl von Speicheroperationen gleichzeitig "im Flug" ist, obwohl die Latenz nicht beseitigt wird.

• Die vollen Kosten für kryptoanalytische Angriffe . Michael J. Wiener. Journal of Cryptology, 2004.

Wenn Sie weiter in diese Denkrichtung eintauchen möchten, gibt es eine interessante (aber meist theoretische) Debatte darüber, ob die richtige Metrik Fläche oder Volumen ist, dh ob die rechte Untergrenze oder . Ja, die Welt ist dreidimensional, aber die Wärmeableitung ist zweidimensional. Ein riesiger Würfel von Computern würde durch seine Fähigkeit, Wärme abzuleiten, begrenzt, die mit seiner Oberfläche und nicht mit seinem Volumen skaliert. In diesem Sinne kann man weitermachen. Wenn dies nach einem faszinierenden Thema klingt, lesen Sie Q.9 (S. 45-46) des folgenden Dokuments:$\sqrt{n}$$\sqrt[3]{n}$

• Ungleichmäßige Risse im Beton: die Kraft der freien Vorberechnung . Daniel J. Bernstein und Tanja Lange. ASIACRYPT 2013.

Siehe verwandte Untergrenzen für die Berechnung (und den Speicher, der als eine Form der Berechnung angesehen werden kann), die für begrenzte Kommunikationsgeschwindigkeit, Untergrenzen für die Einheitsgröße und feste räumliche Dimension empfindlich sind.

David C. Fisher: Ihre bevorzugten parallelen Algorithmen sind möglicherweise nicht so schnell wie Sie denken. IEEE Trans. Computers 37 (2): 211 & ndash; 213 (1988)

$d$$\sqrt[d+1]{N}$

$O(\sqrt{n})$

Offensichtlich wird diese Einschränkung aufgehoben, wenn wir Wurmlöcher herausfinden. In diesem Fall können wir unseren Computer auch in einem Taschenuniversum betreiben.