Externes Rechnen

Beim externen Rechnen geht es um die Lösung komplexer Probleme; Probleme, die so umfangreich sind, daß die anfallenden Datenmengen nicht in den Hauptspeicher passen und ausgelagert werden müssen.

Die traditionellen Methoden, Algorithmen asymptotisch zu analysieren, reichen für dieses Gebiet bei weitem nicht aus. Traditionell wird angenommen, daß alle Daten in den Hauptspeicher passen, so daß elementare Operationen in konstanter Zeit ausgeführt werden können. Methoden zum externen Rechnen versuchen, den Aufwand zum Ein- und Auslagern der anfallenden grossen Datenmengen zu berücksichtigen.

Bisherige Ansätze reichen aber zur Beurteilung der praktischen Verwendbarkeit nicht aus. Es werden nicht nur sämtliche Konstanten vernachlässigt, vor allem aber wird auch mit weitgehend vereinfachten Modellen gearbeitet, z.B. wird meistens angenommen, daß beliebige interne Operationen umsonst durchgeführt werden können.

Unser Ziel ist es, zur Behebung dieser Mankos beizutragen. In einer ersten Arbeit haben wir versucht, Ansätze für paralleles Rechnen auch für externes Rechnen nutzbar zu machen.

• J. F. Sibeyn, M. Kaufmann: "BSP-Like External-Memory Computation", Proc. 3rd Italian Conference on Algorithms and Complexity, LNCS 1203, Springer Verlag, pp. 229-240, 1997.