External Memory Algorithmus - Versionsgeschichte

Fan-vom-Wiki: /* Anwendung */ Tippfehler

2024-11-28T03:22:05Z

Anwendung: Tippfehler

← Nächstältere Version		Version vom 28. November 2024, 05:22 Uhr
Zeile 52:		Zeile 52:

	== Anwendung ==		== Anwendung ==
	Es existieren diverse Bibliotheken und Tools um External Memory Algorithmen zu implementieren. ~~Ein~~ umfassende Übersicht ist in Vitter (2006) ab Seite 141 zu finden.		Es existieren diverse Bibliotheken und Tools um External Memory Algorithmen zu implementieren. Eine umfassende Übersicht ist in Vitter (2006) ab Seite 141 zu finden.

	== Geschichte ==		== Geschichte ==

Invisigoth67: typo

2024-09-01T14:52:11Z

typo

← Nächstältere Version		Version vom 1. September 2024, 16:52 Uhr
Zeile 45:		Zeile 45:

	== Motivation ==		== Motivation ==
	Klassischerweise wird die Laufzeit von Algorithmen in Berechnungsmodellen ohne Speicherhierarchie analysiert. In diesen Modellen verursacht ein Speicherzugriff konstante Kosten, genau wie die Ausführung arithmetischer Befehle. Des Weiteren sind die Kosten eines Speicherzugriffs unabhängig von der Adresse auf die zugegriffen wird, sowie von vorangegangenen Zugriffen.<ref name="Vitter 2006" />		Klassischerweise wird die Laufzeit von Algorithmen in Berechnungsmodellen ohne Speicherhierarchie analysiert. In diesen Modellen verursacht ein Speicherzugriff konstante Kosten, genau wie die Ausführung arithmetischer Befehle. Des Weiteren sind die Kosten eines Speicherzugriffs unabhängig von der Adresse, auf die zugegriffen wird, sowie von vorangegangenen Zugriffen.<ref name="Vitter 2006" />

	Diese Annahmen sind vereinfachend und entsprechen nicht der Realität. Einerseits unterscheiden sich die Zugriffszeiten zwischen zwei Ebenen der Speicherhierarchie für gewöhnlich um Größenordnungen. Andererseits führen Caches sowie die Funktionsweise von Festplatten dazu, dass der Zugriff auf mehrere aufeinander folgende Adressen in der Regel schneller ist, als der Zugriff auf zufällige Adressen (siehe auch [[Lokalitätseigenschaft]]).<ref name="Vitter 2006" />		Diese Annahmen sind vereinfachend und entsprechen nicht der Realität. Einerseits unterscheiden sich die Zugriffszeiten zwischen zwei Ebenen der Speicherhierarchie für gewöhnlich um Größenordnungen. Andererseits führen Caches sowie die Funktionsweise von Festplatten dazu, dass der Zugriff auf mehrere aufeinander folgende Adressen in der Regel schneller ist, als der Zugriff auf zufällige Adressen (siehe auch [[Lokalitätseigenschaft]]).<ref name="Vitter 2006" />

Thomas Dresler: Korrektur

2024-08-13T06:51:10Z

Korrektur

← Nächstältere Version		Version vom 13. August 2024, 08:51 Uhr
Zeile 56:		Zeile 56:
	== Geschichte ==		== Geschichte ==
	Laut Vitter<ref name="Vitter 2006" /> begann die Arbeit an External Memory Algorithmen bereits 1956 in [[Stanford University\|Stanford]] mit H. B. Demuths Dissertation ''Electronic data sorting''.<ref name="Demuth 1994" />		Laut Vitter<ref name="Vitter 2006" /> begann die Arbeit an External Memory Algorithmen bereits 1956 in [[Stanford University\|Stanford]] mit H. B. Demuths Dissertation ''Electronic data sorting''.<ref name="Demuth 1994" />
	Auch [[Donald E. Knuth]] beschäftigte sich in seiner 1973 ~~veröffentlichte~~ Monografie ''[[The Art of Computer Programming]] – Volume 3: Sorting and Searching'' ausgiebig mit dem Sortieren von Daten auf Magnetbändern und zum Teil auch auf Festplatten.<ref name="Knuth 1973" />		Auch [[Donald E. Knuth]] beschäftigte sich in seiner 1973 veröffentlichten Monografie ''[[The Art of Computer Programming]] – Volume 3: Sorting and Searching'' ausgiebig mit dem Sortieren von Daten auf Magnetbändern und zum Teil auch auf Festplatten.<ref name="Knuth 1973" />
	Etwa zur selben Zeit präsentierte [[Robert Floyd\|Robert W. Floyd]] in seiner Arbeit ''Permuting Information in Idealized Two-Level Storage'' ein Modell mit großer Ähnlichkeit zu PDM mit Parametern <math>D=1</math>, <math>P=1</math>, <math>B=M/2=\Theta(N^c)</math> wobei <math>0<c<1</math>.<ref name="Floyd 1972" />		Etwa zur selben Zeit präsentierte [[Robert Floyd\|Robert W. Floyd]] in seiner Arbeit ''Permuting Information in Idealized Two-Level Storage'' ein Modell mit großer Ähnlichkeit zu PDM mit Parametern <math>D=1</math>, <math>P=1</math>, <math>B=M/2=\Theta(N^c)</math> wobei <math>0<c<1</math>.<ref name="Floyd 1972" />
	1988 erweiterten Aggarwal und Vitter in ''The input/output complexity of sorting and related problems'' Floyds Modell um die Möglichkeit von parallelen Block-Transfers.<ref name="Aggarwal 1988" />		1988 erweiterten Aggarwal und Vitter in ''The input/output complexity of sorting and related problems'' Floyds Modell um die Möglichkeit von parallelen Block-Transfers.<ref name="Aggarwal 1988" />

Visualnarrative: Interwikilink entfernt

2023-12-18T07:46:25Z

Interwikilink entfernt

← Nächstältere Version		Version vom 18. Dezember 2023, 09:46 Uhr
Zeile 7:		Zeile 7:
	=== Definition ===		=== Definition ===
	Das Modell besteht aus einem ''internen Speicher'' welcher <math>M</math> Datenelemente fasst, sowie einem unbegrenzten ''externen Speicher'' welcher aus <math>D</math> Festplatten besteht. Der wesentliche Performance-Indikator ist die I/O-Komplexität: die Anzahl von Zugriffen auf den externen Speicher zur Lösung eines Problems mit <math>N</math> Datenelementen. Bei jedem Zugriff auf den externen Speicher kann von jeder der <math>D</math> Festplatten ein Block von <math>B</math> Datenelementen in den internen Speicher geladen werden. Analog kann vom internen in den externen Speicher geschrieben werden. Des Weiteren soll gelten <math>M < N</math> sowie <math>1 \leq DB \leq M/2</math>.<ref name="Vitter 2006" />[[Datei:Data striping example.svg\|alt=Beispiel für data striping\|mini\|320x320px\|Zwei Dateien A und B der Größe <math>4B</math> welche im striping Verfahren auf die Festplatten D1 bis D3 verteilt sind.]]		Das Modell besteht aus einem ''internen Speicher'' welcher <math>M</math> Datenelemente fasst, sowie einem unbegrenzten ''externen Speicher'' welcher aus <math>D</math> Festplatten besteht. Der wesentliche Performance-Indikator ist die I/O-Komplexität: die Anzahl von Zugriffen auf den externen Speicher zur Lösung eines Problems mit <math>N</math> Datenelementen. Bei jedem Zugriff auf den externen Speicher kann von jeder der <math>D</math> Festplatten ein Block von <math>B</math> Datenelementen in den internen Speicher geladen werden. Analog kann vom internen in den externen Speicher geschrieben werden. Des Weiteren soll gelten <math>M < N</math> sowie <math>1 \leq DB \leq M/2</math>.<ref name="Vitter 2006" />[[Datei:Data striping example.svg\|alt=Beispiel für data striping\|mini\|320x320px\|Zwei Dateien A und B der Größe <math>4B</math> welche im striping Verfahren auf die Festplatten D1 bis D3 verteilt sind.]]
	Bei <math>D > 1</math> Festplatten müssen für eine effiziente Verarbeitung die Eingabedaten des Problems im [[Data striping\|''striped'']] ~~([[:en:Data striping\|en]])~~ Format auf den <math>D</math> Platten verteilt vorliegen (siehe die nebenstehende Abbildung für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen. Hierdurch können <math>N</math> Datenelemente mit der optimalen Anzahl von <math>\Theta(N/DB)</math> I/Os in den externen Speicher geschrieben oder von ihm gelesen werden.<ref name="Vitter 2006" />		Bei <math>D > 1</math> Festplatten müssen für eine effiziente Verarbeitung die Eingabedaten des Problems im [[Data striping\|''striped'']] Format auf den <math>D</math> Platten verteilt vorliegen (siehe die nebenstehende Abbildung für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen. Hierdurch können <math>N</math> Datenelemente mit der optimalen Anzahl von <math>\Theta(N/DB)</math> I/Os in den externen Speicher geschrieben oder von ihm gelesen werden.<ref name="Vitter 2006" />

	Oft können die Formeln der resultierenden Anzahl von I/Os vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden. Hieraus ergeben sich die abgeleiteten Größen <math>n = N/B</math> sowie <math>m = M/B</math>.<ref name="Vitter 2006" />		Oft können die Formeln der resultierenden Anzahl von I/Os vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden. Hieraus ergeben sich die abgeleiteten Größen <math>n = N/B</math> sowie <math>m = M/B</math>.<ref name="Vitter 2006" />

Farin12: 1. Abs 1. Satz Kommafehler

2021-02-21T13:47:53Z

1. Abs 1. Satz Kommafehler

← Nächstältere Version		Version vom 21. Februar 2021, 15:47 Uhr
Zeile 1:		Zeile 1:
	Ein '''External Memory Algorithmus''' (auch '''Out-of-Core Algorithmus''') ist ein [[Algorithmus]] der darauf optimiert ist Datenmengen effizient zu verarbeiten, welche die Kapazität des verfügbaren [[Arbeitsspeicher\|Hauptspeichers]] übersteigen. Zugriffe auf Massenspeicher wie [[Festplattenlaufwerk\|Festplatten]] oder [[Network Attached Storage\|Netzwerkspeicher]] sind aber um mehrere Größenordnungen langsamer als Operationen der [[Arithmetisch-logische Einheit\|ALU]] oder Zugriffe auf höhere Ebenen der [[Speicherhierarchie]]. Deshalb ist für die Performance von External Memory Algorithmen die Anzahl der [[Eingabe und Ausgabe\|I/O-Operationen]] auf langsamen Massenspeichern maßgeblich.		Ein '''External Memory Algorithmus''' (auch '''Out-of-Core Algorithmus''') ist ein [[Algorithmus]], der darauf optimiert ist, Datenmengen effizient zu verarbeiten, welche die Kapazität des verfügbaren [[Arbeitsspeicher\|Hauptspeichers]] übersteigen. Zugriffe auf Massenspeicher wie [[Festplattenlaufwerk\|Festplatten]] oder [[Network Attached Storage\|Netzwerkspeicher]] sind aber um mehrere Größenordnungen langsamer als Operationen der [[Arithmetisch-logische Einheit\|ALU]] oder Zugriffe auf höhere Ebenen der [[Speicherhierarchie]]. Deshalb ist für die Performance von External Memory Algorithmen die Anzahl der [[Eingabe und Ausgabe\|I/O-Operationen]] auf langsamen Massenspeichern maßgeblich.
	[[Datei:External Memory Model.svg\|alt=Visualisierung des Parallel Disk Models.\|mini\|350x350px\|Das Parallel Disk Model, hier mit <math>D=P=1</math>. Der interne Speicher fasst <math>M</math> Datenelemente, der externe Speicher ist unbegrenzt. Datentransfer zwischen beiden findet immer in Blöcken der Größe <math>B</math> statt.]]		[[Datei:External Memory Model.svg\|alt=Visualisierung des Parallel Disk Models.\|mini\|350x350px\|Das Parallel Disk Model, hier mit <math>D=P=1</math>. Der interne Speicher fasst <math>M</math> Datenelemente, der externe Speicher ist unbegrenzt. Datentransfer zwischen beiden findet immer in Blöcken der Größe <math>B</math> statt.]]

Orthographus: Komma

2020-09-23T11:14:12Z

Komma

← Nächstältere Version		Version vom 23. September 2020, 13:14 Uhr
Zeile 38:		Zeile 38:
	Als ein einfaches Beispiel für einen I/O-optimalen External Memory Sortieralgorithmus soll External Memory Merge Sort mit <math>D = 1</math> dienen. Dieser Algorithmus arbeitet in zwei Phasen.<ref name="Vitter 2006" />		Als ein einfaches Beispiel für einen I/O-optimalen External Memory Sortieralgorithmus soll External Memory Merge Sort mit <math>D = 1</math> dienen. Dieser Algorithmus arbeitet in zwei Phasen.<ref name="Vitter 2006" />

	Die erste Phase namens ''run formation'' erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in <math>N/M</math>sortierte Teilfolgen der Länge <math>M</math>(die sogenannten ''runs''). Jede dieser Teilfolgen wird erzeugt indem <math>m</math> der <math>n</math> Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.<ref name="Vitter 2006" />		Die erste Phase namens ''run formation'' erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in <math>N/M</math> sortierte Teilfolgen der Länge <math>M</math> (die sogenannten ''runs''). Jede dieser Teilfolgen wird erzeugt, indem <math>m</math> der <math>n</math> Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.<ref name="Vitter 2006" />

	In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils <math>m</math> runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was <math>2n</math> I/Os entspricht. Nach <math>\Theta(\log_m n)</math>Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.<ref name="Vitter 2006" />		In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils <math>m</math> runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was <math>2n</math> I/Os entspricht. Nach <math>\Theta(\log_m n)</math> Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.<ref name="Vitter 2006" />

	Insgesamt benötigt der Algorithmus also <math>\Theta(n \log_m n)</math> I/Os und ist somit optimal.<ref name="Vitter 2006" />		Insgesamt benötigt der Algorithmus also <math>\Theta(n \log_m n)</math> I/Os und ist somit optimal.<ref name="Vitter 2006" />

3I3ER: missing space

2020-06-13T11:09:38Z

missing space

← Nächstältere Version		Version vom 13. Juni 2020, 13:09 Uhr
Zeile 40:		Zeile 40:
	Die erste Phase namens ''run formation'' erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in <math>N/M</math>sortierte Teilfolgen der Länge <math>M</math>(die sogenannten ''runs''). Jede dieser Teilfolgen wird erzeugt indem <math>m</math> der <math>n</math> Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.<ref name="Vitter 2006" />		Die erste Phase namens ''run formation'' erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in <math>N/M</math>sortierte Teilfolgen der Länge <math>M</math>(die sogenannten ''runs''). Jede dieser Teilfolgen wird erzeugt indem <math>m</math> der <math>n</math> Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.<ref name="Vitter 2006" />

	In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils <math>m</math>runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was <math>2n</math> I/Os entspricht. Nach <math>\Theta(\log_m n)</math>Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.<ref name="Vitter 2006" />		In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils <math>m</math> runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was <math>2n</math> I/Os entspricht. Nach <math>\Theta(\log_m n)</math>Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.<ref name="Vitter 2006" />

	Insgesamt benötigt der Algorithmus also <math>\Theta(n \log_m n)</math> I/Os und ist somit optimal.<ref name="Vitter 2006" />		Insgesamt benötigt der Algorithmus also <math>\Theta(n \log_m n)</math> I/Os und ist somit optimal.<ref name="Vitter 2006" />

Crazy1880: Vorlagen-fix (OCLC) + ISBN-fix

2020-04-12T19:10:12Z

Vorlagen-fix (OCLC) + ISBN-fix

← Nächstältere Version		Version vom 12. April 2020, 21:10 Uhr
Zeile 98:		Zeile 98:
	{{Literatur		{{Literatur
	\|Autor=Demuth, Howard B.		\|Autor=Demuth, Howard B.
	\|Hrsg=
	\|Titel=Electronic data sorting		\|Titel=Electronic data sorting
	\|Auflage=
	\|Verlag=Department of Electrical Engineering, Stanford University		\|Verlag=Department of Electrical Engineering, Stanford University
	\|Ort=
	\|Datum=1956		\|Datum=1956
			\|OCLC=25124024}}
	\|ISBN=
	\|Seiten=
	\|Online=http://worldcat.org/oclc/25124024
	\|Abruf=2019-07-29}}
	</ref>		</ref>
	<ref name="Knuth 1973">		<ref name="Knuth 1973">
	{{Literatur		{{Literatur
	\|Autor=Knuth, Donald Ervin		\|Autor=Knuth, Donald Ervin
	\|Hrsg=
	\|Titel=The Art of Computer Programming. Vol. 3, Sorting and Searching		\|Titel=The Art of Computer Programming. Vol. 3, Sorting and Searching
	\|Auflage=
	\|Verlag=Addison-Wesley		\|Verlag=Addison-Wesley
	\|Ort=
	\|Datum=1973		\|Datum=1973
	\|ISBN=0-201-89685-0		\|ISBN=0-201-89685-0}}
	\|Seiten=
	\|Online=http://worldcat.org/oclc/951274350
	\|Abruf=2019-07-29}}
	</ref>		</ref>
	<ref name="Floyd 1972">		<ref name="Floyd 1972">
Zeile 131:		Zeile 119:
	\|Ort=Boston, MA		\|Ort=Boston, MA
	\|Datum=1972		\|Datum=1972
	\|ISBN=~~978-~~1-4684-2003-6		\|ISBN=1-4684-2003-8
	\|Seiten=105–109		\|Seiten=105–109
	\|Online=http://link.springer.com/10.1007/978-1-4684-2001-2_10
	\|Abruf=2019-07-29
	\|DOI=10.1007/978-1-4684-2001-2_10}}		\|DOI=10.1007/978-1-4684-2001-2_10}}
	</ref>		</ref>
Zeile 146:		Zeile 132:
	\|Datum=1988-08-01		\|Datum=1988-08-01
	\|Seiten=1116–1127		\|Seiten=1116–1127
	\|Online=http://portal.acm.org/citation.cfm?doid=48529.48535
	\|Abruf=2019-07-29
	\|DOI=10.1145/48529.48535}}		\|DOI=10.1145/48529.48535}}
	</ref>		</ref>

Phzh: Form, typo

2019-11-19T00:37:17Z

Form, typo

Änderungen zeigen

Aka: /* Geschichte */ Leerzeichen vor Referenz entfernt

2019-08-20T21:36:37Z

Geschichte: Leerzeichen vor Referenz entfernt

← Nächstältere Version		Version vom 20. August 2019, 23:36 Uhr
Zeile 58:		Zeile 58:
	Auch [[Donald E. Knuth]] beschäftigte sich in seiner 1973 veröffentlichte Monografie ''[[The Art of Computer Programming]] – Volume 3: Sorting and Searching'' ausgiebig mit dem Sortieren von Daten auf Magnetbändern und zum Teil auch auf Festplatten.<ref name="Knuth 1973" />		Auch [[Donald E. Knuth]] beschäftigte sich in seiner 1973 veröffentlichte Monografie ''[[The Art of Computer Programming]] – Volume 3: Sorting and Searching'' ausgiebig mit dem Sortieren von Daten auf Magnetbändern und zum Teil auch auf Festplatten.<ref name="Knuth 1973" />
	Etwa zur selben Zeit präsentierte [[Robert Floyd\|Robert W. Floyd]] in seiner Arbeit ''Permuting Information in Idealized Two-Level Storage'' ein Modell mit großer Ähnlichkeit zu PDM mit Parametern <math>D=1</math>, <math>P=1</math>, <math>B=M/2=\Theta(N^c)</math> wobei <math>0<c<1</math>.<ref name="Floyd 1972" />		Etwa zur selben Zeit präsentierte [[Robert Floyd\|Robert W. Floyd]] in seiner Arbeit ''Permuting Information in Idealized Two-Level Storage'' ein Modell mit großer Ähnlichkeit zu PDM mit Parametern <math>D=1</math>, <math>P=1</math>, <math>B=M/2=\Theta(N^c)</math> wobei <math>0<c<1</math>.<ref name="Floyd 1972" />
	1988 erweiterten Aggarwal und Vitter in ''The input/output complexity of sorting and related problems'' Floyds Modell um die Möglichkeit von parallelen Block-Transfers. <ref name="Aggarwal 1988" />		1988 erweiterten Aggarwal und Vitter in ''The input/output complexity of sorting and related problems'' Floyds Modell um die Möglichkeit von parallelen Block-Transfers.<ref name="Aggarwal 1988" />
	1994 führten Vitter und Shriver das Parallel Disk Model ein, welches eine realitätsnähere Version von Aggarwal und Vitters Modell darstellt.<ref name="Vitter 1994" />		1994 führten Vitter und Shriver das Parallel Disk Model ein, welches eine realitätsnähere Version von Aggarwal und Vitters Modell darstellt.<ref name="Vitter 1994" />