Wikipedia - Benutzerbeiträge [de]

Diskussion:MapReduce

2011-05-03T21:30:23Z

132.231.64.78: /* Das Beispiel ist verwirrend oder enthält Fehler */ bessere Antwort, Kommentar zur Artikel-Korrektur

kann es sein, dass in dem wordcount beispiel die ganzen parameternamen überhaupt nicht mit den kommentaren übereinstimmen??? (''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/91.61.76.246|91.61.76.246]] ([[Benutzer Diskussion:91.61.76.246|Diskussion]]) 18:06, 14. Jul 2010 (CEST)) 

== Artikel angelegt ==

Ich habe erstmal einen Grossteil aus der englischen Version übersetzt und übernommen.
Mehr in den nächsten Tagen.

--[[Benutzer:Marc van Woerkom|Marc van Woerkom]] 15:03, 11. Sep. 2008 (CEST)
==Bildbeschreibung fehlt bei ''<nowiki>[[Bild:mapreduce.png]]</nowiki>'' ==
Der Artikel enthält ein [[WP:Bild|Bild]], dem eine Bildbeschreibung fehlt, überprüfe bitte, ob es sinnvoll ist, diese zu ergänzen. Gerade für blinde Benutzer ist diese Information sehr wichtig. Wenn du dich auskennst, dann statte bitte das Bild mit einer aussagekräftigen Bildbeschreibung aus. Suche dazu nach der Textstelle ''<nowiki>[[Bild:mapreduce.png]]</nowiki>'' und ergänze sie.
:Wenn du eine fehlende Bildbeschreibung ergänzen willst, kannst du im Zuge der Bearbeitung folgende Punkte prüfen:
:* [[WP:Namensraum|Namensraum]] Datei: Bilder sollte im Namensraum Datei liegen. Bitte ändere die alten Bezeichnungen [[WP:Bild#Einbindung|<code>Bild:</code>]] und <code>Image:</code> in <code>Datei:</code>.
:* [[WP:Bild#Feste Skalierung|Skalierung]]: Außerhalb von [[Hilfe:Infoboxen|Infoboxen]] sollten keine festen Bildbreiten (zum Beispiel 100px) verwendet werden. Für den Fließtext im [[Hilfe:Namensräume|Artikelnamensraum]] gibt es [[WP:Bild#Thumbnails|Thumbnails]] in Verbindung mit der ''automatischen Skalierung''. Um ein Bild/eine Grafik in besonderen Fällen dennoch größer oder kleiner darzustellen, kann der „upright“-Parameter verwendet werden. Damit erfolgt eine prozentuale Skalierung, die sich an den Benutzereinstellungen orientiert. --[[Benutzer:SpBot|SpBot]] 23:43, 1. Mär. 2009 (CET)

== Das Beispiel ist verwirrend oder enthält Fehler ==

Mal abgesehen davon, dass ich nicht verstehe, warum in der Zwischenergebnisliste zweimal "T_der" vorkommt, einmal mit 2 Treffern und einmal mit 3 Treffern, ist mindestens das Ergebnis falsch: ("der", 3), denn "der" kommt im Text 4 mal vor. (''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Benutzer:82.82.176.39|82.82.176.39]] ([[Benutzer Diskussion:82.82.176.39|Diskussion]] | [[Spezial:Beiträge/82.82.176.39|Beiträge]]) 00:11, 21. Jan. 2010 (CET)) 

Wenn bei jedem Wort das Wort und eine 1 abgelegt wird (anstatt einen Zähler zu inkrementieren), könnte man sich doch die 1 sparen, oder? (''nicht [[Hilfe:Signatur|signierter]] Beitrag von'' [[Benutzer:79.213.236.85|79.213.236.85]] ([[Benutzer Diskussion:79.213.236.85|Diskussion]] | [[Spezial:Beiträge/79.213.236.85|Beiträge]]) 15:01, 24. Jan. 2010 (CET)) 
::Nein, da bei verketteten Vorgängen, und das ist es spätestens im nächsten Schritt, nicht mehr eine 1 dasteht, sondern die Ergebnisse von Reduziervorgängen, also z.B. eine 5... Generell sollten diese Vorgänge imemr austauschbar sein. --[[Benutzer:Bitsandbytes|Bitsandbytes]] 16:47, 24. Jan. 2010 (CET)

Eigentlich gibt es keine T_wort-Listen, so dass die (wort, 1)-Paare unsortiert im Speicher jedes Map-Prozesses stehen. Daher braucht man auch aus diesem Grund die 1en.
Am Ende des Map-Prozesses kann man sogenannte Combiner benutzen, um vorweg zusammenzufassen.
Ich habe jetzt die angesprochenen offensichtlichen Fehler und Unklarheiten korrigiert (verifiziert mit Hadoop-Ausgabe: hadoop/bin/hadoop jar hadoop/examples.jar wordcount Das_Lied_von_der_Glocke-Anfang.txt Ausgabe_ohne_Normalisierung/), trotzdem ist der beschriebene Ablauf noch irreführend.
Beispielsweise gibt es keinen Lockstep, keine einzelnen Zwischenergebnis-Listen, die erste Unterteilung in Sätze ist unrealistisch, die Normalisierung würde der Map-Prozess mit erledigen, ...
[[Spezial:Beiträge/132.231.64.78|132.231.64.78]] 23:30, 3. Mai 2011 (CEST)

== Andere Anwendungsgebiete ==
Bei MapReduce wird hier nur von der Häufigkeitsanalyse gesprochen. Gibt es noch andere Anwendungsgebiete, in denen es nicht alleine um das suchen der Häufigkeiten geht? Kann man MapReduce z.B. auch andere, nicht-textuelle Daten anwenden? Zum Beispiel auf Sequenzen, die sich schwer in "Worte" teilen lassen? Ich denke dabei an Signale (Schwingungen) in denen man Muster erkennen will. Oder mehrdimensionale Daten wie Bilder? --[[Benutzer:Stueckseln|Stueckseln]] 15:11, 11. Sep. 2010 (CEST)

MapReduce

2011-05-03T21:17:01Z

132.231.64.78: /* Beispielhafte Berechnung */ offensichtliche Fehler und Unklarheiten korrigiert (verifiziert mit Hadoop-Ausgabe), trotzdem ist der beschriebene Ablauf noch irreführend

'''MapReduce''' ist ein von [[Google Inc.]] eingeführtes [[Framework]] für [[Nebenläufigkeit|nebenläufige]] Berechnungen über große (mehrere [[Petabyte]]<ref>[http://news.cnet.com/8301-10784_3-9955184-7.html Google spotlights data center inner workings | Tech news blog - CNET News.com]</ref>) Datenmengen auf [[Computercluster]]n.
Dieses Framework wurde durch die in der [[Funktionale Programmierung|funktionalen Programmierung]] häufig verwendeten Funktionen ''[[map (Informatik)|map]]'' und ''[[reduce (Informatik)|reduce]]'' inspiriert,<ref name="map">"Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages." -[http://labs.google.com/papers/mapreduce.html "MapReduce: Simplified Data Processing on Large Clusters"], von Jeffrey Dean und Sanjay Ghemawat, [[Google Labs]]</ref> auch wenn die [[Semantik]] des Frameworks von diesen abweicht.<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.5859&rep=rep1&type=pdf "Google's MapReduce Programming Model -- Revisited"] – Paper von Ralf Lämmel, [[Microsoft]]</ref>
2010 wurde für MapReduce ein US-Patent erteilt<ref>[http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=7,650,331.PN.&OS=PN/7,650,331&RS=PN/7,650,331 Patentanmeldung (US Patent Office)]</ref>

MapReduce-Implementierungen wurden in [[C++]], [[Erlang (Programmiersprache)|Erlang]], [[Java (Programmiersprache)|Java]], [[Python (Programmiersprache)|Python]] und vielen anderen Programmiersprachen realisiert.

== Arbeitsweise ==
=== Illustration des Datenflusses ===
[[Bild:mapreduce.png]]

Das obige Bild illustriert den Datenfluss bei der MapReduce-Berechnung.
* Die Eingabedaten ("D, A, T, A") werden auf eine Reihe von Map-Prozessen verteilt (bunte Rechtecke), welche jeweils die vom Nutzer bereitgestellte Map-Funktion berechnen.
* Die Map-Prozesse werden idealerweise parallel ausgeführt.
* Jede dieser Map-Instanzen legt Zwischenergebnisse ab (dargestellt durch die gelben Dreiecke).
* Von jeder Map-Instanz fließen Daten in eventuell verschiedene Zwischenergebnisspeicher.
* Sind alle Zwischenergebnisse berechnet, ist diese sogenannte Map-Phase beendet und die Reduce-Phase beginnt.
* Für jeden Satz an Zwischenergebnissen berechnet jeweils genau ein Reduce-Prozess (graue Rechtecke) die vom Nutzer bereitgestellte Reduce-Funktion und damit die Ausgabedaten (violette Ovale).
* Die Reduce-Prozesse werden idealerweise auch parallel ausgeführt.

=== Definition der MapReduce-Funktion ===
Das MapReduce-Framework realisiert eine [[Funktion (Mathematik)|Funktion]], welche aus einer [[Liste (Datenstruktur)|Liste]] von [[Schlüssel (Informatik)|Schlüssel]]-[[Wert]]-[[Geordnetes Paar|Paar]]en (Eingabeliste) eine neue Liste von Schlüssel-Wert-Paaren (Ausgabeliste) berechnet:
: <math>\begin{align}
\mathrm{MapReduce} : (K\times V)^* &\to (L\times W)^* \\
{\lbrack(k_1, v_1), \ldots, (k_n, v_n)\rbrack} &\mapsto \lbrack (l_1, w_1), \ldots, (l_m, w_m)\rbrack
\end{align}</math>
Erläuterung:
* Die Mengen <math>K</math> und <math>L</math> enthalten '''Schlüssel''', die Mengen <math>V</math> und <math>W</math> enthalten '''Werte'''.
* Alle Schlüssel <math>k \in K</math> sind vom gleichen Typ, z. B. Strings.
* Alle Schlüssel <math>l \in L</math> sind vom gleichen [[Datentyp|Typ]], z. B. ganze Zahlen.
* Alle Werte <math>v \in V</math> sind vom gleichen Typ, z. B. Atome.
* Alle Werte <math>w \in W</math> sind vom gleichen Typ, z. B. Gleitkommazahlen.
* Wenn <math>A</math> und <math>B</math> Mengen sind, so ist mit <math>A\times B</math> die Menge aller Paare <math>(a, b)</math> gemeint, wobei <math>a \in A</math> und <math>b \in B</math> ([[Kartesisches Produkt]]).
* Wenn <math>M</math> eine Menge ist, so ist mit <math>M^*</math> die Menge aller endlichen Listen mit Elementen aus <math>M</math> gemeint (angelehnt an den [[Kleene-Stern]]) - die Liste kann auch leer sein.

=== Definition der Map- und Reduce-Funktionen ===
Der Nutzer konfiguriert das Framework über die Bereitstellung der beiden Funktionen Map und Reduce, die wie folgt definiert sind:
: <math>\begin{align}
\mathrm{Map} : K\times V &\to (L\times W)^* \\
(k, v) &\mapsto \lbrack(l_1, x_1), \ldots, (l_{r_k}, x_{r_k})\rbrack
\end{align}</math>
bzw.
: <math>\begin{align}
\mathrm{Reduce} : L\times W^* &\to W^* \\
\left(l, {\lbrack y_1, \ldots, y_{s_l}\rbrack}\right) &\mapsto \lbrack w_1, \ldots, w_{m_l}\rbrack
\end{align}</math>

=== Map-Phase ===
* Map bildet ein Paar, bestehend aus einem Schlüssel <math>k</math> und einem Wert <math>v</math>, auf eine Liste von neuen Paaren <math>(l_r, x_r)</math> ab, welche die Rolle von '''Zwischenergebnissen''' spielen, die Werte <math>x_r</math> sind vom gleichen Typ wie die Endergebnisse <math>w_i</math>.
* Bei einem neuen Paar <math>(l, x)</math> verweist der von Map vergebene Schlüssel <math>l</math> dabei auf eine Liste <math>T_l</math> von Zwischenergebnissen, in welcher der von Map berechnete Wert <math>x</math> gesammelt wird.
* Das Framework ruft für jedes Paar in der Eingabeliste die Funktion Map auf.
* All diese Map-Berechnungen sind voneinander unabhängig, so dass man sie nebenläufig und verteilt auf einem Computercluster ausführen kann.

=== Reduce-Phase ===
* Sind alle Map-Aufrufe erfolgt bzw. liegen alle Zwischenergebnisse in <math>T_l</math> vor, so ruft das Framework für jede Zwischenwertliste die Funktion Reduce auf, welche daraus eine Liste von Ergebniswerten <math>w_j</math> berechnet, die vom Framework in der Ausgabeliste als Paare <math>(l, w_j)</math> gesammelt werden.
* Auch die Aufrufe von Reduce können unabhängig auf verschiedene Prozesse im Computercluster verteilt werden.

Anmerkung: Diese Darstellung war etwas vereinfacht, denn in der Regel wird die Steuerung des MapReduce Verfahrens eine Anzahl <math>R</math> von Reduce-Prozessen anstreben, so dass, wenn es mehr Zwischenergebnisse <math>(l, x)</math> als Reduce-Prozesse gibt, mehrere <math>l</math> Zwischenergebnisse in einer Liste gespeichert werden. Die entsprechenden Paare werden vor der Reduce-Berechnung nach Schlüsseln sortiert.

=== Combine-Phase ===
Optional kann zwischen der Map- und der Reduce-Phase noch eine Combine-Phase erfolgen. Diese hat in der Regel die gleiche Funktionalität wie die Reducefunktion, wird aber auf dem gleichen Knoten wie die Map-Phase ausgeführt. Dabei geht es darum, die Netzwerklast zu reduzieren.<ref>[http://labs.google.com/papers/mapreduce.html MapReduce-Paper]</ref> Der Sinn der Combine-Phase erschließt sich sofort bei der Betrachtung des [[MapReduce#Beispiel: Verteilte Häufigkeitsanalyse mit MapReduce|Wordcount-Beispiels]]: Auf Grund der unterschiedlichen Häufigkeit von Wörtern in natürlicher Sprache, würde bei einem deutschen Text beispielsweise sehr oft eine Ausgabe der Form ("und", 1) erzeugt (gleiches gilt für Artikel und Hilfsverben). Durch die Combine-Phase wird nun aus 100 Nachrichten der Form ("und", 1) lediglich eine Nachricht der Form ("und", 100). Dies kann die Netzwerkbelastung signifikant reduzieren, ist aber nicht in allen Anwendungsfällen möglich.

== Beispiel: Verteilte Häufigkeitsanalyse mit MapReduce ==
=== Problem ===
Man möchte für umfangreiche Texte herausfinden, wie oft welche Wörter vorkommen.

=== Angabe der Map- und Reduce-Funktionen ===
<code>
map(String name, String document):
// key: document name
// value: document contents
for each word w in document:
EmitIntermediate(w, 1);

reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result +=v;
Emit(result);</code>

=== Map-Phase ===
* Map bekommt jeweils einen Dokumentnamen ''name'' und ein Dokument ''document'' als Zeichenkette übergeben.
* Map durchläuft das Dokument Wort für Wort.
* Jedes Mal, wenn ein Wort ''w'' angetroffen wird, wandert eine 1 in die ''w''-Zwischenergebnisliste (falls diese noch nicht existiert, wird sie angelegt).
* Ist man mit allen Wörtern durch und hat der Text insgesamt ''n'' verschiedene Wörter, so endet die Map-Phase mit ''n'' Zwischenergebnislisten, jede für ein anderes Wort sammelnd, welche so viele 1-Einträge enthält, wie das entsprechende Wort im Dokument gefunden wurde.
* Eventuell liefen viele Map-Instanzen gleichzeitig, falls dem Framework mehrere Worte und Dokumente übergeben wurden.

=== Reduce-Phase ===
* Reduce wird für das Wort ''word'' und die Zwischenergebnisliste ''partialCounts'' aufgerufen.
* Reduce durchläuft die Zwischenergebnisliste und addiert alle gefundenen Zahlen auf.
* Die Summe result wird an das Framework zurückgegeben, sie enthält, wie oft das Wort ''word'' im Dokument gefunden wurde.
* Die Zwischenergebnisse konnten parallel, durch gleichzeitige Reduce-Aufrufe, berechnet werden.
Insgesamt:
* Aus einer Liste von Dokumentnamen und Dokumenten, wird eine Liste von Worten und Worthäufigkeiten generiert.

=== Beispielhafte Berechnung ===
Zum Beispiel wäre folgende Berechnung auf einem [[Das Lied von der Glocke|klassischen Text]] denkbar:

<code>
Text = "Fest gemauert in der Erden
Steht die Form, aus Lehm gebrannt.
Heute muß die Glocke werden,
Frisch, Gesellen! seid zur Hand.
Von der Stirne heiß
Rinnen muß der Schweiß,
Soll das Werk den Meister loben,
Doch der Segen kommt von oben."</code>

Der Text wird in Sätze aufgeteilt, dabei bietet sich eine [[Normalisierung (Text)|Normalisierung]] an, indem man alles klein schreibt und die Satzzeichen entfernt:

<code>
Eingabeliste = [ (satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt"),
(satz_2, "heute muß die glocke werden frisch gesellen seid zur hand"),
(satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der "
"segen kommt von oben") ]</code>

Die Eingabeliste hat drei Paare als Elemente, wir können daher drei Map-Prozesse starten:

<code>
P1 = Map(satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt")
P2 = Map(satz_2, "heute muß die glocke werden frisch gesellen seid zur hand")
P3 = Map(satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der segen "
"kommt von oben")</code>

Die Map-Aufrufe generieren diese Zwischenergebnispaare:

<code>
P1 = [ ("fest", 1), ("gemauert", 1), ("in", 1), ("der", 1), ("erden", 1), ("steht", 1), ("die", 1), ("form", 1),
("aus", 1), ("lehm, 1), ("gebrannt", 1) ]
P2 = [ ("heute", 1), ("muß", 1), ("die", 1), ("glocke", 1), ("werden", 1), ("frisch", 1), ("gesellen", 1),
("seid", 1), ("zur", 1), ("hand", 1) ]
P3 = [ ("von", 1), ("der", 1), ("stirne", 1), ("heiß", 1), ("rinnen", 1), ("muß, 1), ("der", 1), ("schweiß", 1),
("soll", 1), ("das", 1), ("werk", 1), ("den", 1), ("meister", 1), ("loben", 1), ("doch", 1), ("der", 1),
("segen", 1), ("kommt", 1), ("von", 1), ("oben", 1) ]</code>

Die Map-Prozesse liefern ihre Paare an das MapReduce Framework, welches diese in den Zwischenergebnislisten sammelt. Parallel könnte folgendes geschehen (Die gleiche Taktung der 3 Map-Prozesse ist unrealistisch, tatsächlich überlappen sich die Ausführungen. Die T_wort-Listen sind lokal pro Map-Prozess vorhanden und werden *nicht* zwischen den Schritten synchronisiert):

<code>
1. Schritt:
T_fest = [ 1 ], neu angelegt vom Framework
T_heute = [ 1 ], neu
T_von = [ 1 ], neu

2. Schritt:
T_gemauert = [ 1 ], neu
T_muß = [ 1 ], neu
T_der = [ 1 ], neu

3. Schritt:
T_in = [ 1 ], neu
T_die = [ 1 ], neu
T_stirne = [ 1 ], neu</code>

Im vierten Schritt sieht man, dass Zwischenergebnislisten lokal für jeden Map-Prozess existieren und nich nicht global wiederverwendet werden können:

<code>
4. Schritt:
T_der = [ 1 ], neu (der 1. Map-Prozess hat noch kein T_der, nur der 2.!)
T_glocke = [ 1 ], neu
T_heiss = [ 1], neu

5. Schritt
T_erden = [ 1 ], neu
T_werden = [ 1 ], neu
T_rinnen = [ 1 ], neu

6. Schritt
T_steht = [ 1 ], neu
T_frisch = [ 1 ], neu
T_muß = [ 1 ], neu (der 3. Map-Prozess hat noch kein T_muß!)
</code>

Im siebten Schritt kommt dann zum ersten Mal vor, dass ein weiteres Vorkommen in einer bereits angelegten Zwischenergebnisliste gesammelt wird:

<code>
7. Schritt
T_die = [ 1 ], neu (der 1. Map-Prozess hat noch kein T_die!)
T_gesellen = [ 1 ], neu
T_der = [ 1, 1 ], beim 3. Map-Prozess seit Schritt 2 vorhandene Liste verwenden</code>

usw.

Nach 21 Schritten sind alle drei Map-Prozesse mit ihrer Arbeit durch, die Map-Phase endet und es beginnt die Reduce-Phase.
Die Zwischenergebnislisten, die von verschiedenen Map-Prozessen zu demselben Wort angelegt wurden, werden zusammengefügt.
Für jede der entstandenen Zwischenergebnislisten (hier sortiert aufgeführt)

<code>
reduce
T_der = [ 1 ] ++ [ 1, 1, 1 ] -> [ 4 ]
T_die = [ 1, 1 ] -> [ 2 ]
T_fest = [ 1 ] -> [ 1 ]
T_gemauert = [ 1 ] -> [ 1 ]
T_glocke = [ 1 ] -> [ 1 ]
T_heiss = [ 1 ] -> [ 1 ]
T_heute = [ 1 ] -> [ 1 ]
T_in = [ 1 ] -> [ 1 ]
T_muß = [ 1 ] ++ [ 1 ] -> [ 2 ]
T_stirne = [ 1 ] -> [ 1 ]
T_von = [ 1, 1 ] -> [ 2 ]</code>
usw.

können wir parallel einen Reduce-Prozess starten, der jeweils die Elemente aufzählt.
Das Ergebnis von MapReduce sieht in etwa so aus:

<code>
Ausgabeliste = [ ("fest", 1), ("heute", 1), ("von", 2), ("gemauert", 1), ("muß", 2), ("der", 3),
("in", 1), ("die", 2), .. ]</code>

=== Fazit ===
Die MapReduce-Formulierung hat den Vorteil, dass sich mit den zwei Phasen in natürlicher Weise jeweils eine Parallelisierungsmöglichkeit ergibt, welche man mit einem Cluster für eine beschleunigte Berechnung verwenden kann. Bei sehr großen Datenmengen ist die Parallelisierung unter Umständen bereits erforderlich, weil die Datenmengen für einen einzelnen Prozess (und das ausführende Rechnersystem) zu groß sind.

== Mehr Beispiele ==
{| class="wikitable" 
|-
! Verfahren
! Map-Funktion
! Reduce-Funktion
|-
| Verteiltes [[grep]] || Gibt die gefundene Zeile ([[hit]]) in einen Zwischenergebnisspeicher || Reicht durch ([[Identische Abbildung]], genauer: [[Projektion (Mathematik)|Projektion]] der 2. Komponente)
|}

== Weblinks ==
=== Fachartikel ===
* [http://labs.google.com/papers/mapreduce.html "MapReduce: Simplified Data Processing on Large Clusters"] – [[Paper]] von Jeffrey Dean und Sanjay Ghemawat, [[Google Labs]]
* [http://labs.google.com/papers/sawzall.html "Interpreting the Data: Parallel Analysis with Sawzall"] – Paper von Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan, [[Google Labs]]
* [http://csl.stanford.edu/%7Echristos/publications/2007.cmp_mapreduce.hpca.pdf "Evaluating MapReduce for Multi-core and Multiprocessor Systems"] – Paper von Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, und Christos Kozyrakis, [[Stanford University]] (PDF-Datei; 353 kB)
* [http://www.dbms2.com/2008/08/26/why-mapreduce-matters-to-sql-data-warehousing/ "Why MapReduce Matters to SQL Data Warehousing"] – Analyse zur Einführung von MapReduce/SQL seitens [[Aster Data Systems]] und [[Greenplum]]
* [http://pages.cs.wisc.edu/~dekruijf/docs/mapreduce-cell.pdf "MapReduce for the Cell B.E. Architecture"] – Paper von Marc de Kruijf und Karthikeyan Sankaralingam, [[University of Wisconsin-Madison]] (PDF-Datei; 528 kB)
* [http://www.cse.ust.hk/catalac/users/saven/GPGPU/MapReduce/PACT08/171.pdf "Mars: A MapReduce Framework on Graphics Processors"] – Paper von Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, Tuyong Wang, [[Hong Kong University of Science and Technology]], veröffentlicht in Proc. PACT 2008. Es führt Design und Implementierung von MapReduce auf [[Grafikprozessor|Graphikprozessoren]] vor. (PDF-Datei; 326 kB)
* [http://portal.acm.org/citation.cfm?doid=1247480.1247602 "Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters"] – Paper von Hung-Chih Yang, Ali Dasdan, Ruey-Lung Hsiao und D. Stott Parker, [[Yahoo]] und [[UCLA]], veröffentlicht in Proc. of ACM SIGMOD, pp. 1029--1040, 2007. (Dieses Paper zeigt, wie man MapReduce auf relationale Datenverarbeitung ausweitet)
* FLuX: Der [http://citeseer.ist.psu.edu/647742.html ''Fault-tolerant''], [http://citeseer.ist.psu.edu/546646.html ''Load Balancing''] ''eXchange operator'' der [[UC Berkeley]] bietet eine Alternative zu Googles MapReduce, mit [[Failover]] aber zusätzlichen Implementierungskosten.

=== Software ===
* [http://hadoop.apache.org/mapreduce/ Apache Hadoop MapReduce]
* [http://discoproject.org/ disco] Open Source Projekt (Python und Erlang) des [[Nokia]] Research Center
* [http://www.greenplum.com/resources/mapreduce/ Greenplum MapReduce] von [[Greenplum]]
* [http://www.alphaworks.ibm.com/tech/mapreducetools IBM MapReduce Tools for Eclipse] – ein [[Plug-in]], welches die Erstellung von MapReduce Anwendungen mit [[Eclipse (Software)|Eclipse]] unterstützt.
* [http://labs.trolltech.com/page/Projects/Threads/QtConcurrent QtConcurrent] Open Source C++ MapReduce Implementierung (nicht-verteilt) von [[Qt Software]]
* [http://skynet.rubyforge.org Skynet] [[Ruby (Programmiersprache)|Ruby]] Map/Reduce Framework
* [http://projects.camlcity.org/projects/plasma.html Plasma MapReduce] ist eine Open Source MapReduce Implementierung in [[Ocaml]] mit einem eigenen verteilten Dateisystem, PlasmaFS. Plasma MapReduce wurde von Gerd Stolpmann (Darmstadt) entwickelt.

== Quellen ==
<references />

[[Kategorie:Computercluster]]
[[Kategorie:Google]]
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Softwarearchitektur]]
[[Kategorie:Verteiltes System]]

[[cs:MapReduce]]
[[en:MapReduce]]
[[es:MapReduce]]
[[eu:MapReduce]]
[[fa:نگاشت‌کاهش]]
[[fr:MapReduce]]
[[it:MapReduce]]
[[ja:MapReduce]]
[[ko:MapReduce]]
[[nl:MapReduce]]
[[pl:MapReduce]]
[[ru:MapReduce]]
[[zh:MapReduce]]

World Digital Library

2010-05-26T11:01:22Z

132.231.64.78: /* Partner des Projektes */ falsches Land korrigiert, siehe Wikipedia-Link: König Abdullah Universität für Wissenschaft und Technologie

{{Infobox Website
| Name = World Digital Library
| Logo = [[Datei:World Digital Library Logo 2008-04-24.png]]
| url = http://www.worlddigitallibrary.org
| Kommerziell = kostenlose Nutzung
| Beschreibung = Download-Portal für bedeutsame Dokumente der Weltkultur
| Sprachen = arabisch, chinesisch, englisch, französisch, portugiesisch, russisch, spanisch
| Registrierung = offen zugänglich
| Eigentümer = [[Vereinigte Staaten]], [[UNESCO]]
| Urheber = [[Library of Congress]]
| Erschienen = 21. April 2009
| Jahreseinnahmen = gesponsertes Projekt
| Slogan =
}}

Die '''World Digital Library''', auf [[Deutsche Sprache|Deutsch]] „Digitale Weltbibliothek“, ist ein [[Projekt]] der US-Nationalbibliothek [[Library of Congress]] und der [[UNESCO]]. Die World Digital Library stellt kulturell herausragende Dokumente aus aller Welt über das Internet kostenlos und für jedermann zur Verfügung.

== Projektziel ==
Das Ziel des Projektes ist es, mit den Materialien das kollektive digitale Gedächtnis der Menschheit zu bewahren und das internationale und interkulturelle Verständnis zu fördern. Ausdrücklich werden auch Nationen gefördert, die nicht zur westlichen und englischsprechenden Welt gehören. Ein besonderes Augenmerk wird auf die Kulturen des Nahen Ostens gelegt.

Diese kulturellen Ressourcen sollen Lehrkräften, Schülern und Interessenten offen stehen und zur wissenschaftlichen Forschung beitragen.

Zudem soll die Menge und die Vielfalt des kulturellen Inhaltes im Internet erweitert und die digitale Zusammenarbeit der Partnerinstitutionen zwischen und innerhalb der beteiligten Länder aufgebaut und verbessert werden.

== Geschichte ==
=== Initiative ===
Nach mehr als 20 Jahren Abwesenheit waren die USA 2003 in die UNESCO zur ständigen Mitarbeit zurückgekehrt. Als Nationalkommissar der USA für die UNESCO wurde der Leiter der Kongressbibliothek [[James Hadley Billington]] [[Kandidat|nominiert]]. Bei seiner ersten Teilnahme an der Jahreskonferenz im Juni 2005 wurde er zu einem Plenarvortrag eingeladen. Sein Vortrag war mit ''A View of the Digital World Library'' betitelt und er entwarf eine Vision, dass die reichen Sammlungen der Institutionen und Bibliotheken der Welt wieder zurückgegeben werden sollten.

[[Google Inc.]] wurde der erste Teilnehmer dieser [[Public Private Partnership]] und spendete 2005 drei Millionen Dollar zur Entwicklung der World Digital Library.

{{Zitat-en|[…] institutions, libraries, and museums have preserved could be given back to the world free of charge and in a new form far more universally accessible than any forms that have preceded it.|Übersetzung=[…] Institute, Bibliotheken und Museen haben aufbewahrt und könnten es der Welt gratis zurückgeben und dies in einer Form, die universeller zugänglich ist als jegliche Formen, die es vorher gab.|Autor=James H. Billington in seinem Vortrag vor dem Plenum der UNESCO}}

=== Planungsphase ===
Auf der Jahreskonferenz der Nationalkommission 2006 legte der Seniorreferent der Kongressbibliothek John Van Oudenaren einen Projektplan vor. Damit konnte die Initiative Billingtons in die Tat umgesetzt werden. Zunächst wurden von den beteiligten Partnern die Grundlagen in vier Hauptbereichen beraten.
* technische Struktur
* Auswahl
* Führung
* Finanzierung
Im Dezember 2006 trafen sich 45 Direktoren und technische Leiter von Nationalbibliotheken mit weiteren Kultur- und Bildungsrepräsentanten in Paris, um die Entwicklung der Digitalen Weltbibliothek zu diskutieren und das Projekt in Angriff zu nehmen. Die Teilnehmer bildeten Arbeitsgruppen für jeden dieser vier Projektbereiche, um die Anforderungen zu formulieren.

=== Realisierungsphase ===
Der Planungsprozess wurde mit einem Treffen der Arbeitsgruppen in der ersten Hälfte von 2007 fortgesetzt, weitere Experten für Digitalbibliotheken wurden hinzugezogen. [[Informatik|Informatiker]], Spezialisten aus der [[Bibliothekswissenschaft]] und der [[World Wide Web|Webentwicklung]], sowie Experten der [[Fundraising|Geldbeschaffung]] führten die Projektarbeit weiter. Diese Arbeitsgruppen legten ihre Ergebnisse im Juli 2007 in einer WDL-Gruppe zusammen und erstellten eine Präsentation über die Struktur des Webauftritts.<ref>[http://project.wdl.org/project/english/docs/World_Digital_Library_Demonstration.pdf Die Demonstration als pdf]</ref> Diese Ausarbeitung wurde am 17. Oktober 2007 in Paris auf der 34. Sitzung der UNESCO als WDL-Präsentation vorgelegt. Der Prototyp der digitalen Weltbibliothek wurde von den UNESCO-Delegierten getestet. Während dieser Tagung unterzeichnete der Direktor der Kongressbibliothek, James H. Billington, und der stellvertretende UNESCO-Direktor für Kommunikation und Information, Abdul Waheed Khan, ein Abkommen zur weiteren Arbeit.

Anfang September 2008 entschloss sich die [[Organization of American States]] (OAS) mit der US-Kongressbibliothek bei der Entwicklung der WDL zusammenzuarbeiten. Ihr Generalsekretär José Miguel Insulza unterzeichnete gemeinsam mit dem Kongressbibliothekar James Billington einen Vertrag über Zusammenarbeit am OAS-Sitz.

Im folgenden Zeitraum bis zum Frühjahr 2009 konnten knapp 40 Partner zur Mitarbeit gewonnen werden. Neben den Gründungsmitgliedern sind die Nationalbibliotheken von Ägypten, Brasilien, China, Frankreich, Irak, Israel, Russland, Serbien, Schweden und Uganda beteiligt. Die [[Bibliotheca Alexandrina]] beteiligt sich mit der International Federation of Library Associations and Institutions (IFLA).<ref>[http://www.ifla.org/ Website der IFLA]</ref>

Am 21. April 2009 wurde die World Digital Library in Paris durch UNESCO-Generaldirektor [[Koichiro Matsuura]] und den Leiter der Library of Congress James Hadley Billington offiziell eröffnet.<ref>[[Spiegel Online]]: ''[http://www.spiegel.de/netzwelt/web/0,1518,620226,00.html Weltgeschichte in 1170 Bildern]'' vom 21. April 2009.</ref>

== Projektumfang ==
In das Projekt werden Manuskripte, Karten, seltene Bücher, Musik, Tonaufnahmen, Filme, Fotos und Architekturpläne und weitere Dokumentenarten aufgenommen. Eine Suche ist im Volltext über ein Eingabefeld und auch grafisch möglich. Mit einer Zeitleiste kann der Zeitraum der Ergebnissuche eingeschränkt werden. Für die Vorauswahl wird eine Weltkarte zur Auswahl von Regionen angeboten.

Das ausgewählte Dokument kann mit einem [[Abbildungsmaßstab|Zoom]] auf Einzelheiten in der hochaufgelösten Version durchsucht werden. Zu den digitalisierten Originaldokumenten ist ein erläuternder Erklärungstext vorhanden.

Im Kopf der Internetseite befinden sich in der englischen Fassung die Suchvorgaben
* Place (Ort, Region),
* Time (Zeitraum),
* Topic (Stichwort),
* Type of Item (Kategorie),
* Institution (Partnerinstitut).

Projektsprachen sind die sechs offiziellen [[Vereinte Nationen|UNO]]-Sprachen Arabisch, Chinesisch, Englisch, Französisch, Russisch und Spanisch sowie zusätzlich Portugiesisch, die Sprachauswahl ist über eine Auswahleingabe möglich. In einem weiteren Eingabefeld lassen sich Stichworte für eine Volltextsuche eingeben. Bei erfolgter Dokumentauswahl werden verwandte Dokumente (related items) angeboten.

Die [[Barrierefreiheit]] wurde nach den Empfehlungen der [[Web Content Accessibility Guidelines|Web Content Accessibility Guidelines 2.0]] umgesetzt.

Die World Digital Library und das europäische [[Webportal|Portal]] ''[[Europeana]]'' sind zwei getrennte Projekte und haben verschiedene Zielsetzungen. Europeana deckt vor allem digitale Sammlungen über Europa in europäischen Bibliotheken, Archiven und Museen ab. Die World Digital Library wird kulturell und historisch besonders bedeutsame Inhalte aus allen 193 Mitgliedsländern der UNESCO anbieten.<ref>[http://www.wdl.org/en/about/faq.html World Digital Library: Frequently Asked Questions]</ref> Die vorwiegend als [[Tagged Image File Format|TIFF]]- und [[Portable Document Format|PDF]]-Dateien gespeicherten Objekte werden nicht aus den originalen Standorten verlinkt, sondern liegen auf gesonderten Servern der WDL.

Beim Start enthielt die WDL 1170 Objekte, bereits zwei Tage später wurden 1358 Objekte gemeldet. Billington sagte hierzu: „Es ist ein offener Prozess.“ Demgemäß gibt es auch keine Zielgröße.<ref>[http://www.netzeitung.de/kultur/1336877.html Netzeitung am 23. April 2009]</ref>

== Partner des Projektes ==
Deutsche, österreichische und Schweizer Institutionen haben Ende April 2009 zwar Objekte angemeldet, sind aber noch nicht als Projektpartner beteiligt.

{| class ="wikitable sortable"
|- class="hintergrundfarbe5"
! Bibliothek
! width="200" | Standort
|-
| [[Bibliotheca Alexandrina]] || {{SortKey|Ag}} Ägypten
|-
| [[Brown University]] || USA
|-
| [[Center for the Study of the History of Mexico|Zentrum für Geschichtsstudien Mexikos]] || USA
|-
| [[Qatar Foundation]] || Katar
|-
| [[Columbus Memorial Library]] || USA
|-
| [[International Federation of Library Associations and Institutions]] || international
|-
| [[Nationalbibliothek von Bagdad|Nationalbibliothek und Archiv Iraks]] || Irak
|-
| [[John Carter Brown Library]] || USA (Rhode Island)
|-
| [[King Abdullah University of Science and Technology|König Abdullah Universität für Wissenschaft und Technologie]] || Saudi-Arabien
|-
| [[Library of Congress|US-Kongressbibliothek]] || USA
|-
| [[Mamma Haidara Commemorative Library]] || Mali
|-
| [[National Archives and Records Administration]] || USA
|-
| [[National Central Library]] || USA
|-
| [[National Diet Library]] || Japan
|-
| {{SortKey|Ag}} [[Egyptian National Library and Archives|Ägyptische Nationalbibliothek und -archiv]] || {{SortKey|Ag}} Ägypten
|-
| [[National Institute of Anthropology and History|US-Nationalinstitut für Anthropologie und Geschichte]] || USA
|-
| [[National Library of Brazil|Nationalbibliothek Brasiliens]] || Brasilien
|-
| [[Chinesische Nationalbibliothek]] || China
|-
| [[Bibliothèque nationale de France|Französische Nationalbibliothek]] || Frankreich
|-
| [[Jüdische National- und Universitätsbibliothek|Israelische Nationalbibliothek]] || Israel
|-
| [[Russische Nationalbibliothek]] || Russland
|-
| [[Narodna Biblioteka Srbije|Nationalbibliothek Serbiens]] || Serbien
|-
| [[Kungliga Biblioteket|Nationalbibliothek Schwedens]] || Schweden
|-
| [[National Library of Uganda|Nationalbibliothek Ugandas]] || Uganda
|-
| [[Königliche Bibliothek der Niederlande|Königliches Institut für Südostasien und die Karibik der Niederlande]] || Niederlande
|-
| [[Russische Staatsbibliothek]] || Russland
|-
| [[St. Mark Coptic Library]] || USA (Ohio)
|-
| [[Tetouan-Asmir Association]] || Marokko
|-
| [[University Library in Bratislava|Universitätsbibliothek Bratislava]] || Slowakei
|-
| [[University of Pretoria Library|Universitätsbibliothek Pretoria]] || Südafrika
|-
| [[Wellcome Library]] || Großbritannien
|-
| [[Yale University Library|Universitätsbibliothek von Yale]] || USA
|-
| [[Yeltsin Presidential Library|Präsident Jelzin Bibliothek]] || Russland
|}

== Weblinks ==
{{Commonscat}}
* [http://www.wdl.org/ Internetseite der World Digital Library]
* [http://www.heise.de/newsticker/Das-digitale-Gedaechtnis-der-Welt-soll-online-nutzbar-werden--/meldung/97681 Bericht zur 34. UNESCO-Tagung]
* [http://archive.ifla.org/VI/2/p2/national-libraries.htm National Libraries of the World] ([[International Federation of Library Associations and Institutions|IFLA]])
* [http://search.theeuropeanlibrary.org/portal/de/libraries.html Die Nationalbibliotheken Europas]

== Einzelnachweise ==
<references />

[[Kategorie:Internet]]
[[Kategorie:Digitale Bibliothek]]
[[Kategorie:Website]]

[[ar:المكتبة الرقمية العالمية]]
[[az:Dünya Elektron Kitabxanası]]
[[bg:Световна цифрова библиотека]]
[[en:World Digital Library]]
[[es:Biblioteca Digital Mundial]]
[[fi:Maailman digitaalinen kirjasto]]
[[fr:Bibliothèque numérique mondiale]]
[[he:הספרייה הדיגיטלית העולמית]]
[[id:Perpustakaan Digital Dunia]]
[[it:World Digital Library]]
[[jv:Perpustakaan Digital Donya]]
[[ka:მსოფლიო ციფრული ბიბლიოთეკა]]
[[nl:Digitale wereldbibliotheek]]
[[pl:Światowa Biblioteka Cyfrowa]]
[[pt:World Digital Library]]
[[ro:World Digital Library]]
[[ru:Всемирная цифровая библиотека]]
[[sk:Svetová digitálna knižnica]]
[[sl:Svetovna digitalna knjižnica]]
[[th:หอสมุดดิจิทัลแห่งโลก]]
[[tr:Dünya Dijital Kütüphanesi]]
[[zh:世界数字图书馆]]

Tomita-Parser

2009-11-30T14:55:52Z

132.231.64.78: /* Graphstapel */ Konsistenz mit Grafik

Ein '''Tomita-Parser''' (nach [[Masaru Tomita]]) ist ein [[Parser|Parsverfahren]] für [[kontextfreie Grammatik|kontextfreie Grammatiken]], das eine Verallgemeinerung des [[LR(k)]]-Verfahrens ist. Das Verfahren wird deshalb auch '''GLR(k)-Verfahren''' (für ''Generalized'' LR(k)) genannt.

Ausgangspunkt des Tomita-Parsers ist der Tabellenerstellungsvorgang des LR(k)-Verfahrens. Bei Grammatiken, die nicht die LR(k)-Eigenschaft haben (u.a., aber nicht nur, [[Mehrdeutige Grammatik|ambige]] Grammatiken), führt dieser Vorgang zu Mehrfacheinträgen, sog. ''Konflikten'':

* ''Shift-Reduce-Konflikt'': es besteht die Möglichkeit, das nächste Eingabesymbol auf den [[Stapelspeicher|Stapel]] des Parsers zu legen oder eine erkannte rechte Seite einer [[Produktionsregel]] durch die linke Regelseite zu ersetzen.
* ''Reduce-Reduce-Konflikt'': es gibt mindestens zwei Produktionsregeln, mit deren Hilfe eine Reduktion erfolgen kann.

Der Algorithmus des Tomita-Parsers verfolgt diese Konflikte pseudo-parallel weiter. Als Datenstruktur wird ein sog. ''Graphstapel'' (''graph structured stack'') - ein [[Graph (Graphentheorie)#Gerichteter azyklischer Graph|gerichteter azyklischer Graph]] - verwendet, der alle bereits vollzogenen Parsoperationen repräsentiert.

== Graphstapel ==
Die verwendete Repräsentation der Parsergebnisse geschieht – ähnlich wie beim [[Chart-Parser]] - mittels eines gerichteten azyklischen Graphen.

[[Bild:GLRStack1.png|thumb|400px|Abb 1.: Graphstack für den Satz ''sie beobachtet ihn mit dem Fernglas'']]

Abb. 1 zeigt einen solchen [[Graph (Graphentheorie)|Graphen]] nach Beendigung des Parsvorgangs für den Beispielsatz „''sie beobachtet den Einbrecher mit dem Fernglas''“.
Die dabei verwendete, [[Mehrdeutige Grammatik|ambige]] Grammatik ist:

# [[Satz (Grammatik)|S]] --> [[Nominalphrase|DP]] [[Verbalphrase|VP]]
# [[Verbalphrase|VP]] --> [[Verbalphrase|Vbar]]
# [[Verbalphrase|VP]] --> [[Verbalphrase|VP]] [[Präpositionalphrase|PP]]
# [[Verbalphrase|Vbar]] --> [[Verb|V]][[Transitivität (Grammatik)|trans]] [[Nominalphrase|DP]]
# [[Nominalphrase|DP]] --> [[Determinativ (Wortart)|Det]] [[Nominalphrase|NP]]
# [[Nominalphrase|DP]] --> [[Pronomen|Pron]]
# [[Nominalphrase|NP]] --> [[Nominalphrase|Nbar]]
# [[Nominalphrase|Nbar]] --> [[Nomen|N]]
# [[Nominalphrase|Nbar]] --> [[Nominalphrase|Nbar]] [[Präpositionalphrase|PP]]
# [[Präpositionalphrase|PP]] --> [[Präposition|P]] [[Nominalphrase|DP]]

Für den Beispielsatz erlaubt sie zwei verschiedene [[Syntaxbaum|syntaktische Analysen]]. Aufgrund dieser Ambiguität hat sie nicht die LR(k)-Eigenschaft, führt also zu Mehrfacheinträgen in der Parstabelle.

Jeder [[Knoten (Graphentheorie)|Graphknoten]] hat einen eindeutigen Knotennamen (dieser beginnt mit "n").
Die roten Knoten enthalten Elemente aus dem Vokabular der Grammatik, also einerseits [[Nichtterminalsymbol]]e und andererseits Wörter ([[Terminalsymbol]]e). Die blauen Knoten dagegen enthalten Zustandsnummern der [[LR-Parser|LR]]-Parstabelle. Man kann schön sehen, wie im Knoten ''n21'' zwei bis dahin verschiedene Analysen bei der Integration der [[Präposition]] „mit“ wieder zusammenlaufen. Die nachfolgende [[Präpositionalphrase]] „mit dem Fernglas“ wird also nur einmal analyisiert.

== Parsalgorithmus ==
Wie beim LR(k)-Verfahren besteht der Parsprozess aus eine Reihe von tabellengesteuerten Shift- bzw. Reduktionsschritten. Beim Shift-Schritt wird ein Wort aus der Eingabe entfernt und auf den Stapel gelegt. Bei einem Reduktionsschritt wird die rechte Seite (γ) einer Produktionsregel A → γ, die in umgekehrter Reihenfolge auf dem Stapel liegt, durch die linke Regelseite (A) ersetzt. Im Unterschied zum LR(k)-Verfahren wird der reduzierte Teil jedoch nicht aus dem Stapel gelöscht, sondern bleibt erhalten. Dies bedeutet, dass der Stapel monoton wächst.
Der Vorgang wird durch die GLR(k)-Tabelle gesteuert. Zu jedem Zeitpunkt befindet sich der Parser in einem definierten Zustand (vgl. [[Kellerautomat]]). Mit diesem Zustand und dem/den nächsten Symbol(en) der Eingabe wird die GLR(k)-Tabelle konsultiert und die nächsten Operationen (shift, reduce, accept, error) und der Folgezustand bestimmt. Im Fall von Mehrfacheinträgen (Konflikten) werden diese quasi parallel verfolgt. Nachfolgende Shift-Operationen können diese parallelen Verarbeitungsstränge jedoch wieder synchronisieren; dies ist wichtig für die [[Zeitkomplexität]] des Verfahrens.

== Beziehung zu anderen Parsverfahren ==
Der Tomita-Parser ist ein vorkompilierter [[Chart-Parser]].

== Literatur ==
Masaru Tomita: ''Dynamic construction of finite-state automata from examples using hill-climbing''. In: ''Proceedings of the Fourth Annual Cognitive Science Conference''. Ann Arbor, MI, 1982, S. 105-108

[[Kategorie:Compilerbau]]
[[Kategorie:Formale Sprachen]]

[[en:GLR parser]]
[[ja:GLR法]]
[[pl:Parser GLR]]
[[pt:Analisador sintático GLR]]
[[ru:GLR-парсер]]

Intel iAPX 432

2009-11-04T11:16:23Z

132.231.64.78: eindeutigere Formulierung

Der '''Intel iAPX 432''' war [[Intel]]s erster 32-Bit-[[Mikroprozessor]]. Er wurde [[1981]] als Set bestehend aus drei Integrierten Schaltkreisen eingeführt und war als das grundlegende Intel-Design für die [[1980er]] Jahre geplant. Fortschrittliche Funktionen wie [[Präemptives Multitasking]] und das Speichermanagement waren in Hardware implementiert, daher nannte man das Design auch den "Micromainframe".

Die Datenstruktur-Unterstützung des Prozessors erlaubte es, moderne [[Betriebssystem]]e mit viel weniger Programmcode als bei gewöhnlichen CPUs zu implementieren - der 432 erledigte stattdessen einen Großteil der Arbeit intern in Hardware. Im Vergleich zu anderen Prozessoren war die Chipstruktur extrem komplex. Intels Ingenieuren gelang es mit der damaligen Halbleitertechnik nicht, das Konzept in eine effiziente Implementierung umzusetzen. Die CPU war sehr langsam und teuer, und Intels Pläne, die [[x86]]-Architektur durch die iAPX 432 zu ersetzen, endeten in einem wirtschaftlichen Desaster.

Die Abkürzung ''iAPX'' stand für '''''i'''ntel '''A'''dvanced '''P'''rocessor ar'''chi'''tecture'', wobei das X vom griechischen Buchstaben [[Chi]] kam; aber wenn man APX auch Griechisch deutet, dann heißt das '''''a''r''chi'''tecture.

== Geschichte ==
=== Entwicklung ===
Das 432er-Projekt begann [[1975]] als ''i8800'' und sollte sich in die existierenden Produktlinien [[Intel 8008|8008]] und [[Intel 8080|8080]] einreihen. Das Design war von Anfang an als reines 32-Bit-Design geplant. Es sollte wesentlich leistungsfähiger und komplexer als die bisherigen Intel-Prozessoren sein und lag noch weit jenseits der Fähigkeiten der damaligen Prozesstechnologie. Die CPU musste daher in mehrere Chips aufgeteilt werden.

Der Hauptprozessor (''General Data Processor'', GDP) bestand aus zwei Chips. Ein Chip (der 43201) holte und dekodierte die Instruktionen, der zweite (43202) führte sie aus. Optional stand mit dem 43203 Interface-Prozessor (IP) auch ein I/O-Controller zur Verfügung. Insgesamt bestand das Drei-Chip-Gespann aus 250000 Transistoren und war damit eines der umfangreichsten Designs seiner Zeit. So bestand beispielsweise der [[Motorola 68000]] aus etwa 68000 Transistoren, davon ein Drittel für den [[Microcode]].

[[1983]] führte Intel zwei zusätzliche Chips für die ''iAPX 432 Interconnect Architecture'' ein, die ''43204 Bus Interface Unit'' (BIU) und die ''43205 Memory Control Unit'' (MCU). Mit ihnen wurden Multiprozessorsysteme mit bis zu 63 Knoten möglich.

=== Die Fehler des Projekts ===
Mehrere Designeigenschaften sorgten dafür, dass der iAPX 432 viel langsamer war, als er hätte sein können. Die Zwei-Chip-Umsetzung des GDP begrenzte diesen auf die Geschwindigkeit der Verdrahtung auf dem Mainboard. Dies war allerdings weniger ein Problem. Weitaus ernster war der Mangel an [[Cache]]s und [[Register (Computer)|Registern]]. Auch der [[Befehlssatz]] bremste die Leistung, weil anstatt der sonst üblichen, [[Speicherausrichtung|auf Wortgrenzen liegenden]] (''word-aligned'') Instruktionen fester Länge, auf Bit-Grenzen liegende (''bit-aligned'') Instruktionen variabler Länge verwendet wurden. Die Dekodierung der Instruktionen wurde dadurch komplex und langsam. Die BIU sollte fehlertolerante Systeme unterstützen, was einen merklichen [[Overhead]] auf dem Bus mit sich brachte. 40 Prozent der Zeit verbrachte der Bus mit Wartezyklen.

Untersuchungen nach Ende des Projekts ergaben, dass das größte Problem wohl im [[Compiler]] lag, der in allen Fällen allgemeine und langsame Befehle verwendete, statt einfache und schnelle Befehle zumindest da zu benutzen, wo dies sinnvoll gewesen wäre. Der iAPX 432 kannte beispielsweise einen sehr teuren intermodularen [[Prozeduraufruf]]sbefehl, den der Compiler für alle Aufrufe verwendete. Die viel schnelleren Sprungbefehle ignorierte er. Ein weiterer sehr langsamer Aufruf war ''enter_environment'', mit dem der Speicherschutz eingerichtet wurde. Der Compiler rief ihn für jede einzelne Variable im System auf, obwohl die weitaus meisten in einem existierenden Environment liefen und nicht geprüft werden mussten. Um die Situation noch schlimmer zu machen, wurde grundsätzlich [[call by value]] und nicht [[call by reference]] verwendet, was in vielen Fällen riesige Speicherkopien erforderlich machte.

=== Nachwirkungen ===
Aus dem Fehlschlag iAPX 432 wurde die Lehre gezogen, dass die Unterstützung von Objekten auf CPU-Ebene zu einem komplexen Design führt, das unweigerlich langsam läuft. Seit Erscheinen des iAPX 432 hat niemand mehr ein ähnliches Design auf die Beine gestellt. Tatsächlich sieht es aber so aus, als ob die Unterstützung von [[Objektorientierung]] überhaupt nicht das Problem war. Der iAPX 432 litt unter Problemen, die jedes Chip-Design langsam gemacht hätten.

Intel hatte große Mengen an Zeit und Geld in die Entwicklung und das Marketing des 432 investiert, hatte ein fähiges Team darauf angesetzt und zögerte, das Team nach diesem Fehlschlag einfach aufzugeben. Unter Führung des neuen Chefdesigners Glenford Myers sollte der Hauptprozessor neu entwickelt und dann im Rahmen eines [[Joint-Venture]]s mit [[Siemens]] gebaut werden. Aus diesem Projekt entstand später die CPU-Serie [[Intel i960|i960]], die sich lange Zeit großer Beliebtheit im Embedded-Markt erfreute. [[1990]] gab das zuständige Team den i960 ab und begann mit der Entwicklung des bis in die heutigen Tage erfolgreichen [[P6-Familie|P6-Kerns]], der [[1995]] im [[Pentium Pro]] debütierte und auch heute noch – in weiterentwickelter Form – als [[Pentium M]] verkauft wird. Auch die [[Intel Core 2|Core 2]] Mikroarchitektur, auf die Intel nach dem Fehltritt mit der [[Netburst]]-Architektur zurückkam, basiert auf dem P6-Kern.

== Siehe auch ==
* [[Liste von Mikroprozessoren]]

{{Navigationsleiste Intel-Prozessoren}}

[[Kategorie:Intel-Prozessor|IAPX 432]]

[[en:Intel iAPX 432]]
[[es:Intel iAPX 432]]
[[it:Intel iAPX 432]]
[[ja:Intel iAPX 432]]
[[ko:인텔 iAPX 432]]
[[no:Intel iAPX 432]]
[[pl:Intel iAPX 432]]
[[pt:Intel iAPX 432]]
[[ru:Intel iAPX 432]]