[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki29\/2021\/11\/25\/externer-speicheralgorithmus-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki29\/2021\/11\/25\/externer-speicheralgorithmus-wikipedia\/","headline":"Externer Speicheralgorithmus \u2013 Wikipedia","name":"Externer Speicheralgorithmus \u2013 Wikipedia","description":"before-content-x4 Beim Rechnen, externe Speicheralgorithmen oder Out-of-Core-Algorithmen sind Algorithmen, die darauf ausgelegt sind, Daten zu verarbeiten, die zu gro\u00df sind,","datePublished":"2021-11-25","dateModified":"2021-11-25","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki29\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki29\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/c1\/External_memory.svg\/220px-External_memory.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/c1\/External_memory.svg\/220px-External_memory.svg.png","height":"220","width":"220"},"url":"https:\/\/wiki.edu.vn\/wiki29\/2021\/11\/25\/externer-speicheralgorithmus-wikipedia\/","wordCount":3715,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Beim Rechnen, externe Speicheralgorithmen oder Out-of-Core-Algorithmen sind Algorithmen, die darauf ausgelegt sind, Daten zu verarbeiten, die zu gro\u00df sind, um auf einmal in den Hauptspeicher eines Computers zu passen.  Solche Algorithmen m\u00fcssen optimiert werden, um effizient Daten abzurufen und darauf zuzugreifen, die in langsamen Massenspeichern (Hilfsspeicher) wie Festplatten oder Bandlaufwerken gespeichert sind, oder wenn sich der Speicher in einem Computernetzwerk befindet.[1][2]  Externe Speicheralgorithmen werden in der externes Speichermodell.  Der Cache links h\u00e4lt mB{displaystyle {tfrac {M}{B}}}       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4  Bl\u00f6cke der Gr\u00f6\u00dfe        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4B{displaystyle B}  jeweils f\u00fcr insgesamt m Objekte.  Der externe Speicher auf der rechten Seite ist unbegrenzt.Externe Speicheralgorithmen werden in einem idealisierten Berechnungsmodell analysiert, das als externes Speichermodell (oder E\/A-Modell, oder Festplattenzugriffsmodell).  Das externe Speichermodell ist eine abstrakte Maschine \u00e4hnlich dem RAM-Maschinenmodell, jedoch mit einem Cache zus\u00e4tzlich zum Hauptspeicher.  Das Modell erfasst die Tatsache, dass Lese- und Schreibvorg\u00e4nge in einem Cache viel schneller sind als im Hauptspeicher, und dass das Lesen langer zusammenh\u00e4ngender Bl\u00f6cke schneller ist als das zuf\u00e4llige Lesen mit einem Platten-Lese- und Schreibkopf.  Die Laufzeit eines Algorithmus im externen Speichermodell wird durch die Anzahl der erforderlichen Lese- und Schreibvorg\u00e4nge im Speicher definiert.[3]  Das Modell wurde 1988 von Alok Aggarwal und Jeffrey Vitter vorgestellt.[4]  Das externe Speichermodell bezieht sich auf das Cache-Oblivious-Modell, aber Algorithmen im externen Speichermodell k\u00f6nnen sowohl die Blockgr\u00f6\u00dfe als auch die Cachegr\u00f6\u00dfe kennen.  Aus diesem Grund wird das Modell manchmal als bezeichnet Cache-f\u00e4higes Modell.[5]Das Modell besteht aus einem Prozessor mit einem internen Speicher oder Cache der Gr\u00f6\u00dfe m, verbunden mit einem unbegrenzten externen Speicher.  Sowohl der interne als auch der externe Speicher sind in Gr\u00f6\u00dfenbl\u00f6cke unterteilt B.  Eine Eingabe\/Ausgabe- oder Speicher\u00fcbertragungsoperation besteht darin, einen Block von B zusammenh\u00e4ngende Elemente vom externen zum internen Speicher, und die Laufzeit eines Algorithmus wird durch die Anzahl dieser Ein-\/Ausgabeoperationen bestimmt.[4]Table of ContentsAlgorithmen[edit]Anwendungen[edit]Geschichte[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Algorithmen[edit]Algorithmen im externen Speichermodell nutzen die Tatsache, dass beim Abrufen eines Objekts aus dem externen Speicher ein ganzer Block der Gr\u00f6\u00dfe abgerufen wird        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4B{displaystyle B}.  Diese Eigenschaft wird manchmal als Lokalit\u00e4t bezeichnet.Auf der Suche nach einem Element unter n{displaystyle N}  Objekte ist im externen Speichermodell \u00fcber einen B-Baum mit Verzweigungsfaktor m\u00f6glich B{displaystyle B}.  Mit einem B-Baum k\u00f6nnen Suchen, Einf\u00fcgen und L\u00f6schen in . erreicht werden \u00d6(ProtokollB\u2061n){displaystyle O(log_{B}N)}  Zeit (in Big O-Notation).  Information Theoretisch ist dies die minimal m\u00f6gliche Laufzeit f\u00fcr diese Operationen, so dass die Verwendung eines B-Baums asymptotisch optimal ist.[4]Externes Sortieren ist das Sortieren in einer externen Speichereinstellung.  Die externe Sortierung kann \u00fcber die Verteilungssortierung, \u00e4hnlich wie bei Quicksort, oder \u00fcber a . erfolgen mB{displaystyle {tfrac {M}{B}}}-way Merge sortieren.  Beide Varianten erreichen die asymptotisch optimale Laufzeit von \u00d6(nBProtokollmB\u2061nB){displaystyle O({tfrac {N}{B}}log_{tfrac {M}{B}}{tfrac {N}{B}})}  Sortieren n Objekte.  Diese Schranke gilt auch f\u00fcr die schnelle Fourier-Transformation im externen Speichermodell.[2]Das Permutationsproblem besteht darin, neu anzuordnen n{displaystyle N}  Elemente in eine bestimmte Permutation.  Dies kann entweder durch Sortieren erfolgen, was die obige Sortierlaufzeit erfordert, oder indem jedes Element der Reihe nach eingef\u00fcgt wird und der Vorteil der Lokalit\u00e4t ignoriert wird.  Somit kann die Permutation in erfolgen \u00d6(Mindest(n,nBProtokollmB\u2061nB)){displaystyle O(min(N,{tfrac {N}{B}}log_{tfrac {M}{B}}{tfrac {N}{B}}))}  Zeit.Anwendungen[edit]Das externe Speichermodell erfasst die Speicherhierarchie, die in anderen g\u00e4ngigen Modellen, die beim Analysieren von Datenstrukturen verwendet werden, wie etwa der Direktzugriffsmaschine, nicht modelliert wird, und ist n\u00fctzlich, um untere Grenzen f\u00fcr Datenstrukturen zu beweisen.  Das Modell ist auch n\u00fctzlich f\u00fcr die Analyse von Algorithmen, die mit Datens\u00e4tzen arbeiten, die zu gro\u00df sind, um in den internen Speicher zu passen.[4]Ein typisches Beispiel sind geografische Informationssysteme, insbesondere digitale H\u00f6henmodelle, bei denen der vollst\u00e4ndige Datensatz leicht mehrere Gigabyte oder sogar Terabyte an Daten \u00fcberschreitet.Diese Methodik geht \u00fcber Allzweck-CPUs hinaus und umfasst auch GPU-Computing sowie klassische digitale Signalverarbeitung.  Im Allzweck-Computing auf Grafikprozessoren (GPGPU) werden leistungsstarke Grafikkarten (GPUs) mit wenig Speicher (im Vergleich zum bekannteren Systemspeicher, der meist einfach als RAM bezeichnet wird) mit relativ langsamer CPU-zu- GPU-Speichertransfer (im Vergleich zur Rechenbandbreite).Geschichte[edit]Eine fr\u00fche Verwendung des Begriffs “out-of-core” als Adjektiv bezieht sich 1962 auf Ger\u00e4te die nicht der Kernspeicher einer IBM 360 sind.[6]  Eine fr\u00fche Verwendung des Begriffs “out-of-core” in Bezug auf Algorithmen erscheint 1971.[7]Siehe auch[edit]Verweise[edit]^ Vitter, JS (2001).  \u201eExterne Speicheralgorithmen und Datenstrukturen: Umgang mit MASSIVE DATA\u201c. ACM-Computing-Umfragen. 33 (2): 209\u2013271.  CiteSeerX 10.1.1.42.7064.  mach:10.1145\/384192.384193.^ ein B Vitter, JS (2008). Algorithmen und Datenstrukturen f\u00fcr externen Speicher (PDF). Grundlagen und Trends in der Theoretischen Informatik.  Reihe zu Grundlagen und Trends in der Theoretischen Informatik. 2.  Hannover, MA: Jetzt Verlage.  S. 305\u2013474.  CiteSeerX 10.1.1.140.3731.  mach:10.1561\/0400000014.  ISBN 978-1-60198-106-6.^ Zhang, Donghui;  Tsotras, Vassilis J.;  Levialdi, Stefano;  Grinstein, Georges;  Berry, Damon Andrew;  Gouet-Brunet, Valerie;  Kosch, Harald;  D\u00f6ller, Mario;  D\u00f6ller, Mario;  Kosch, Harald;  Maier, Paul;  Bhattacharya, Arnab;  Ljosa, Vebj\u00f6rn;  Nack, Frank;  Bartolini, Ilaria;  Gouet-Brunet, Valerie;  Mei, Tao;  Rui, Yong;  Crucianu, Michel;  Shih, Frank Y.;  Fan, Wenfei;  Ullman-Cullere, Mollie;  Clark, Eugen;  Aronson, Samuel;  Mellin, Jonas;  Berndtsson, Mikael;  Grahne, G\u00f6sta;  Bertossi, Leopoldo;  Dong, Guozhu;  et al.  (2009).  “I\/O-Modell der Berechnung”. Enzyklop\u00e4die der Datenbanksysteme.  Springer Wissenschaft+Wirtschaftsmedien.  S. 1333\u20131334.  mach:10.1007\/978-0-387-39940-9_752.  ISBN 978-0-387-35544-3.^ ein B C D Aggarwal, Alok;  Vitter, Jeffrey (1988). “Die Eingabe-\/Ausgabekomplexit\u00e4t der Sortierung und damit verbundene Probleme”. Mitteilungen des ACM. 31 (9): 1116-1127.  mach:10.1145\/48529.48535.^ Demaine, Erik (2002). Cache-Oblivious Algorithmen und Datenstrukturen (PDF).  Vorlesungsnotizen der EEF Summer School zu Massive Data Sets.  Arhus: BRICS.^ NASA SP.  NASA.  1962. p.  276.^ Computer in der Krise.  ACM.  1971. p.  296.Externe Links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki29\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki29\/2021\/11\/25\/externer-speicheralgorithmus-wikipedia\/#breadcrumbitem","name":"Externer Speicheralgorithmus \u2013 Wikipedia"}}]}]