Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


13. Externes Sortieren



Praktische Erwägungen

Um die Implementation der oben umrissenen Sortiermethode zu beenden, müssen die Ein- und Ausgabe-Funktionen implementiert werden, die die Daten zwischen der Zentraleinheit und den externen Einheiten übertragen. Diese Funktionen sind offenbar der Schlüssel zu einer guten Leistungsfähigkeit des externen Sortierens, und ebenso offensichtlich machen sie es erforderlich, einige systembezogene Fragen sorgfältig zu betrachten (als Gegenstück zu Fragen des Algorithmus). (Leser, die sich nicht mit Computern auf der »System«-Ebene beschäftigen, können die folgenden Absätze auslassen.)

Ein Hauptziel bei der Implementation sollte sein, dafür zu sorgen, daß sich Lesen, Schreiben und Berechnen so gut wie möglich überlappen. Viele große Computersysteme besitzen unabhängige Zentraleinheiten für die Steuerung der großen Ein- und Ausgabe-Einheiten, die diese Überlappungen möglich machen. Die Effizienz, die mit einer externen Sortiermethode erreicht werden kann, hängt von der verfügbaren Anzahl solcher Einheiten ab.

Für jede Datei, die gelesen oder geschrieben wird, kann die Doppelpufferung (double buffering) genannte standardmäßige Systemprogrammmiertechnik benutzt werden, um die Überlappung der Ein- und Ausgabe (E/A) mit der Berechnung zu maximieren. Die Idee besteht darin, zwei »Puffer« zu unterhalten, einen zur Verwendung durch die Zentraleinheit und einen zur Verwendung durch die E/A-Einheit (oder den Prozessor, der die E/A-Einheit steuert). Während der Eingabe verwendet der Prozessor den einen Puffer, während die Eingabeeinheit den anderen füllt. Wenn der Prozessor seinen Puffer nicht mehr benutzt, wartet er, bis die Eingabeeinheit ihren Puffer gefüllt hat, und dann werden die Rollen der Puffer vertauscht: Der Prozessor verwendet die neuen Daten aus dem soeben gefüllten Puffer, während die Eingabeeinheit den Puffer, dessen Daten der Prozessor bereits benutzt hat, neu füllt. Die gleiche Methode kommt bei der Ausgabe zur Anwendung, wobei die Rollen des Prozessors und der Einheit vertauscht sind. Gewöhnlich ist die für die E/A benötigte Zeit wesentlich größer als die Verarbeitungszeit, so daß der Effekt der Doppelpufferung darin besteht, daß die Rechenzeit vollständig überdeckt wird; die Puffer sollten daher so groß wie möglich sein.

Eine Schwierigkeit bei der Doppelpufferung besteht darin, daß in Wirklichkeit nur etwa die Hälfte des verfügbaren Speicherplatzes ausgenutzt wird. Dies kann zu einer uneffizienten Arbeitsweise führen, wenn viele Puffer beteiligt sind, wie es beim P-Weg-Mischen der Fall ist, wenn P nicht klein ist. Dieses Problem kann mit Hilfe einer Methode gelöst werden, die Vorhersage (forecasting) genannt wird und die Verwendung von nur einem zusätzlichen Puffer (anstelle von P Puffern) während des Mischprozesses erfordert. Die Vorhersage läuft wie folgt ab: Der beste Weg, um während des Prozesses von Replacement Selection Eingabe und Berechnung zu überlappen, besteht sicherlich darin, die Eingabe in den Puffer, der als nächster gefüllt werden muß, mit dem Verarbeitungsteil des Algorithmus zu überlappen. Und es ist leicht zu bestimmen, welcher Puffer das ist: Der Eingabepuffer, der als nächster geleert wird, ist derjenige, dessen letztes Element am kleinsten ist. Wenn zum Beispiel A O S mit I R T und A G N gemischt wird, so wissen wir, daß der dritte Puffer als erster geleert wird, danach der erste. Eine einfache Möglichkeit, um beim Mehrweg-Mischen die Verarbeitung mit der Eingabe zu überlappen, besteht daher darin, einen zusätzlichen Puffer zu verwenden, der von der Eingabeeinheit entsprechend dieser Regel gefüllt wird. Wenn der Prozessor einen leeren Puffer vorfindet, wartet er, bis der Eingabepuffer gefüllt ist (falls er noch nicht gefüllt worden ist); dann beginnt er, diesen Puffer zu benutzen, und veranlaßt die Eingabeeinheit, entsprechend der Vorhersageregel mit dem Füllen des gerade geleerten Puffers zu beginnen.

Die wichtigste Entscheidung, die bei der Implementation des Mehrweg-Mischens zu treffen ist, ist die Wahl von P, der »Ordnung« des Mischens. Beim Sortieren mit Hilfe von Bändern, wo nur sequentieller Zugriff gestattet ist, ist diese Wahl einfach: P muß um eins kleiner sein als die verfügbare Anzahl von Bandeinheiten, da für das Mehrweg-Mischen P Eingabebänder und ein Ausgabeband verwendet werden. Offenbar müssen mindestens zwei Eingabebänder vorhanden sein, so daß der Versuch, beim Sortieren mit Bändern weniger als drei Bänder zu verwenden, nicht besonders sinnvoll ist.

Beim Sortieren mit Hilfe von Platten, wo der Zugriff auf beliebige Positionen gestattet ist, wobei dieser aber etwas teurer ist als ein sequentieller Zugriff, ist es gleichfalls sinnvoll, P um eins kleiner zu wählen als die verfügbare Anzahl von Platten, um die höheren Kosten eines nichtsequentiellen Zugriffs zu vermeiden, die zum Beispiel entstehen würden, wenn sich zwei verschiedene Eingabedateien auf der gleichen Platte befänden. Eine andere häufig benutzte Alternative ist, P genügend groß zu wählen, so daß das Sortierverfahren in zwei Mischphasen vollendet ist. Es ist gewöhnlich nicht sinnvoll zu versuchen, das Sortieren in einem Durchlauf auszuführen, doch ein Sortieren mit zwei Durchläufen kann oft mit einem hinreichend kleinen P realisiert werden. Da bei Replacement Selection ungefähr N/2M Sequenzen erzeugt werden und die Anzahl der Sequenzen bei jedem Mischdurchlauf durch P geteilt wird, bedeutet dies, daß als Wert für P die kleinste ganze Zahl gewählt werden sollte, für die P2 > N/2M gilt. Für unser Beispiel des Sortierens einer Datei mit 200 Millionen Wörtern auf einem Computer mit einem Speicher, der eine Million Wörter umfaßt, würde sich ergeben, daß P = 11 eine sichere Wahl wäre, um ein Sortieren in zwei Durchläufen zu gewährleisten. (Der richtige Wert von P kann exakt berechnet werden, nachdem die Sortierphase abgeschlossen ist.) Die richtige Wahl zwischen diesen beiden Alternativen des kleinsten sinnvollen Wertes von P und des größten sinnvollen Wertes von P hängt sehr stark von vielen Systemparametern ab; beide Alternativen (und einige Zwischenwerte) sollten in Betracht gezogen werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]