Parallelrechner und wissenschaftliches Rechnen

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Viele ingenieur- und naturwissenschaftliche Fragestellungen lassen sich ohne hohe Rechenleistung nicht beantworten. Unter dem Schlagwort „Grand Challenges" z.B. werden eine Reihe von Problemen des wissenschaftlichen Rechnens angesprochen, die eine Rechenleistung von mehr als 10**12 MFlops und einen Arbeitsspeicher von mehr als 10**12 Bytes erfordern. Parallelrechner besitzen mehrere Verarbeitungseinheiten und ein leistungsstarkes Verbindungssystem, so daß alle Verarbeitungseinheiten gleichzeitig zur Lösung einer Aufgabe beitragen können. Mit einem Parallelrechner könnte also im Prinzip die verfügbare Rechenleistung beliebig gesteigert werden.

J. L. Hennessy, D. A. Patterson: "However, progress in building and using effective and efficient parallel processors has been slow. This rate of Progress has been limited by difficult software problems as well As by a long process of evolving architecture of multiprocessors to enhance usability and improve efficiency. ... The use of parallel processing in some domains is beginning to be understood. Probably first among these IS the domain of scientific and engineering computation. This application domain has an almost limitless thirst for more computation [5]."

Das sogenannte Flynnsche Schema klassifiziert Rechnerarchitekturen nach der Anzahl der vorhandenen Datenströme (SD/MD single/multiple data stream) und der Anzahl der vorhandenen Instruktionsströme (SI/MI Single/multiple instruction stream) [6]. Daraus lassen sich die Kombinationen SISD, SIMD und MIMD bilden. Zu den SIMD-Rechnern zählen die Vektorrechner und die Feldrechner; zu den MIMD-Rechner zählen:

• UMA-Architekturen mit einem zentralen Speicher, wobei die Speicherzugriffszeit für alle Prozessoren, unabhängig vom Ort des Zugriffs, dieselbe ist (Uniform Memory Access)
• NUMA-Architekturen mit einem physikalisch verteilten gemeinsamen Speicher; die Zugriffsgeschwindigkeit hängt vom Ort des Zugriffs ab (Non-Uniform Memory Access) und
• NORMA-Architekturen; die Prozessoren besitzen unterschiedliche lokale Adreßräume. Jeder Prozessor kann somit nur auf seinen lokalen Speicher direkt zugreifen (NO-RemoteMemory-Access). Die Kommunikation unter den Prozessoren geschieht durch Botschaftenaustausch.

Datenflußrechner sind Parallelrechner gänzlich anderer Architektur. Sie realisieren Nebenläufigkeit auf Instruktionsebene nach dem Datenflußprinzip, das inzwischen auch in die Mikroarchitektur der Mikroprozessoren Eingang gefunden hat.

Als Beispiel für die strukturelle Vielgestaltigkeit heutiger Parallelrechner sei kurz die Architektur der SPP-Rechner der Firma Convex vorgestellt. Ein SPP-Rechner besteht aus bis zu 64 Rechnerknoten vom NUMA-Typ, also selbst Parallelrechnern, die über ein globales Verbindungsnetzwerk verbunden sind. Abb. 1 zeigt den Aufbau dieser Knoten, Hypernodes genannt. Jeder Hypernode enthält vier CPUs mit privatem Speicher und Instruktions-Cache. Ein sogenannter CPU-Agent bildet die Schnittstelle zum lokalen Verbindungsnetzwerk, das ein Bus oder ein Kreuzschienenverteiler sein kann. Jeder Hypernode enthält außerdem neben einem privaten auch einen global zugänglichen Speicher.

Die erzielbare Beschleunigung für eine typische Anwendung mit Laufzeit T(p) hängt offensichtlich nicht nur von der Anzahl p der Prozessoren des Parallelrechners sondern auch von der Anzahl der parallelisierbaren Verarbeitungsschritte ab. Wenn ein Bruchteil f davon sequentiell abgearbeitet werden muß, gilt für die Beschleunigung (Speed-Up):

S(p) = T(1)/T(p) = p/(1+f(p-1)). Man nennt diese Beziehung das „Amdahlsche Gesetz". (Es stammt aus dem Jahre 1967 und basiert allerdings auf vereinfachenden Annahmen.) Um z.B. eine Effizienz E(p) = S(p)/p größer 0,5 zu erzielen, muß f für p = 100 kleiner 1% sein. Dies verdeutlicht, wie wichtig es ist, Anwendungen so zu strukturieren, daß ihr Skalaranteil möglichst klein wird.

Diesen Überlegungen liegt zugrunde, daß die betrachtete Anwendung skalierbar, d.h. sowohl auf einem System mit einem wie auch auf einem mit p Verarbeitungseinheiten lauffähig ist. Ein Parallelrechner andererseits ist skalierbar, wenn er ohne Änderung seiner Basisarchitektur in seiner Leistung erweitert werden kann und zwar derart, daß skalierbare Anwendungen nicht modifiziert werden müssen. Ein skalierbarer Parallelrechner erlaubt einen schrittweisen Ausbau der Hard- und Software, so daß einmal getätigte Investitionen ihren Wert nicht verlieren. Man kann das System bei Bedarf erweitern und preisgünstige offtheshelf Bausteine der neuesten Technologie verwenden. Für skalierbare Anwendungen wird man – im Prinzip – an keine Leistungsgrenze stoßen. Wenn wir nämlich die parallele Bearbeitungszeit konstant halten, indem wir mit größer werdendem Multiprozessor auch die Problemgröße erhöhen, und sie mit der Bearbeitungszeit auf einem Monorechner vergleichen, dann erhalten wir für den sogenannten skalierten Speed-Up Ss (p) = f+(lf )p. Der skalierte Speed-Up ist also nicht limitiert.

Die für viele wissenschaftlichen Probleme benötigte hohe Rechenleistung können im Grunde nur große, skalierbare Parallelrechner bereitstellen. Moderne Parallelrechner sind dazu in der Lage, aber meist nur, wenn die Programme dafür optimiert werden. Was überwunden schien, nämlich das mühsame Optimieren von Programmen, ist nun wieder notwendig. Dafür gibt es eine Reihe von Gründen. Der wichtigste ist wohl, daß die Prozessoren zwar immer leistungsfähiger wurden, die Leistung der Speichersysteme aber nicht mithalten konnte.

K. David: "Processors have become much, much faster in the past decade, but memory speeds haven’t kept pace. In the hardware, a lot of fancy tricks are now used to help memory keep up with CPU. But a bad memory access pattern in a critical loop might defeat all this wonderful hardware – in which case, your 100 MHz processor isn’t doing a lot of good [3]."

Y. N. Patt: "There IS a growing awareness that algorithms work better (i.e., execute faster) if their authors have a clue As to the nature of the hardware These algorithms are to run on. You can easily throw away all the performance a modern processor buys you, if you don’t know how to harness that horsepower. Ergo, greater attention IS being paid to computer architecture by the algorithm community."

In anderen Worten, ein Parallelrechner läßt sich nur bei Kenntnis und mit Beachtung seiner Architektur effizient programmieren. Ein effizientes Programm hat z.B. die Verbindungs- und Cachestruktur des Rechners (Abb. 1) zu berücksichtigen und falsche Datenabhängigkeiten zu vermeiden, die verhindern können, daß ansonsten unabhängige Instruktionen parallel ausgeführt werden. Wie gut die Ausnutzung der Parallelität gelingt, wird maßgeblich auch von der Güte der Abbildung der Anwendung auf die Systemarchitektur bestimmt [6].

D. E. Stevenson: "The scientist or engineer who avoids These considerations IS at a grave disadvantage. In the same way that sloppy experimental technique cannot be tolerated, so too the inappropriate marrying of applications, algorithms and architectures cannot be tolerated in computer modeling (computational engineering). It IS important to realize that computer technology can be applied inappropriately."

Viele numerische Lösungsansatze mathematischer Modelle, die im Bereich des wissenschaftlichen Rechnens zur Anwendung kommen, nutzen Bibliotheken numerischer Basis-Algorithmen. Entwickelt man dafür optimierte, der jeweiligen Zielarchitektur angepaßte, parallele Implementierungen, kann man der zuvor angesprochenen Problematik, nämlich die Architektur des Parallelrechners explizit berücksichtigen zu müssen, begegnen: Die Bibliotheksroutinen bilden dann eine abstrakte, architekturunabhängige Schnittstelle zu den optimierten numerischen Routinen.

J. Dongarra et al.: "The design and implementation of a library of scalable mathematical Software IS critical to the success of our effort to make parallel computers truly useful to scientists and engineers [1]."

Beispiele für derartige Bibliotheken sind BLAS, LA-PACK, NAG sowie IMSL. Nach einer weitgehenden Konzentration auf Implementierungen für Vektor- sowie UMA-Architekturen gelten nun die aktuellen Bemühungen auch parallelisierten Versionen für NUMA, NORMA und SIMD-Systeme, siehe z.B. die ScaLAPACK Version der LAPACK Bibliothek [2]. Moderne Computer-Algebra-Systeme wie AXIOM, MATHEMATICA und MAPLE erlauben zudem eine einheitliche Integration dieser numerischen Basis-Werkzeuge. Sie bieten einheitliche Schnittstellen für den Zugriff auf numerische (externe) Algorithmen (z.B. NAGAXIOM bzw. NAG, IMSL-MATHEMATICA über das InterCall Paket). Diese Kombination abstrakter symbolischer Werkzeuge zur mathematischen Modellbildung in Verbindung mit einer hocheffizienten numerischen Simulation auf Parallelrechnern eröffnet dem wissenschaftlichen Rechnen neue Horizonte [4].

Jedoch stößt man bei diesem Ansatz auch auf prinzipielle Schwierigkeiten. So können i.a. nicht alle Charakteristika paralleler Systeme über abstrakte Bibliotheksroutinen verdeckt werden. Vor allem erweist sich der Aspekt der Datenverteilung auf die verteilten Speicher des Systems als schwierig. Statische Entscheidungen zur Datenpartitionierung sind dafür ebenso erforderlich wie eine explizite Berücksichtigung der dynamischen Datenumverteilung. Gerade die Forderung nach Skalierbarkeit der Soft- und Hardware verlangt, daß geeignete Datenumverteilungsmuster gefunden werden. Dies ist jedoch ein Optimierungsproblem, das zu komplex ist, um vollautomatisch gelöst werden zu können. Gegenwärtige Ansätze beschränken sich deshalb darauf, dem Programmierer eine wohldefinierte Menge mehr oder weniger elementarer Verteilungsmuster zur Verfügung zu stellen.

                   Artikelanfang  Seitenanfang

Literatur

1. Choi J., Dongarra J. J. et al.: Constructing Numerical Software Libraries for High-Performance Computing Environments, First Int. Workshop "Parallel Scientific Computing", PARA 94, June 1994
2. Choi J., Dongarra J. J. et al.: ScaLAPACK reference manual, Technical Memorandum ORNL/TM-12470, Oak Ridge National Laboratory, Oak Ridge, 1994
3. David K.: High Performance Computing, O’Reilly, 1993
4. Golub G., Ortega J. M.: Scientific Computing – An Introduction with Parallel Computing, Academic Press, 1993
5. Hennesy J. L., Patterson D. A.: Computer Architecture – a quantitative approach, M. Kaufman Pub., zweite Auflage, 1995.
6. Waldschmidt K. (Hrsg.): Parallelrechner: Architekturen – Systeme – Werkzeuge, Teubner Verlag, 1995

Autor & Copyright
M. Dal Cin, S. Kindermann
Institut für Mathematische Maschinen und Datenverarbeitung,
Universität Erlangen-Nürnberg,
Martensstraße 3,
D-91058 Erlangen

© 1996 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

• Kurzinfo
• Erläuterung
• Resümee
• Literatur
• Autor & Copyright

Kurzinfo Unter dem Begriff „Peer-to-Peer" etabliert sich ein höchst interessantes Paradigma für die Kommunikation im Internet. Obwohl ursprünglich nur für die sehr pragmatischen und rechtlich umstrittenen Dateitauschbörsen entworfen, können die Peer-to-Peer-Mechanismen zur verteilten Nutzung unterschiedlichster Betriebsmittel genutzt werden und neue Möglichkeiten für Internet-basierte Anwendungen eröffnen.

Erläuterung

Zahlreiche Telekommunikationsunternehmen berichten, dass zur Zeit das Verkehrsaufkommen von Peer-to-Peer-Diensten etwa 50% des Gesamtvolumens ausmacht, in Spitzenzeiten sogar 75%. Aufgrund des weiterhin anhaltenden Wachstums des Internets hinsichtlich Teilnehmerzahlen und Datenaufkommen, aber auch durch die gestiegenen Anforderungen des ständig wachsenden Anwendungsspektrums, lassen sich zahlreiche Anwendungen mit den traditionellen, auf Client-Server-Ansätzen basierenden Methoden oft nur noch mit erheblichem Aufwand realisieren. Als aktuelle Beispiele sind hier neben Dateitauschbörsen insbesondere verteilte Dateisysteme und Grid-Computing zu nennen.

Im Zuge dieser jüngsten Entwicklungen lassen sich drei grundlegende Anforderungen an Internet-basierte Anwendungen im künftigen Internet identifizieren:

• Die Skalierbarkeit ist eine elementare Voraussetzung, um den weiterhin steigenden Teilnehmerzahlen sowie dem immensen Ressourcenbedarf (Bandbreite, Speicherplatz, Rechenkapazität) bestimmter Anwendungen gerecht zu werden. So gilt es von Beginn an Flaschenhälse zu vermeiden, um auch ein Wachstum um mehrere Größenordnungen effizient bewältigen zu können.
• Sicherheit und Verlässigkeit spielen im Zuge einer wachsenden Anzahl gezielter Angriffe (sog. „Distributed-denial-of-service-Attacken") auf zentrale Dienste eine entscheidende Rolle für die Verfügbarkeit strategisch wichtiger und sicherheitsrelevanter Dienste [Projekte: FreeNet http://freenet.sourceforge.net, Tarzan http://pdos.lcs.mit.edu/tarzan/] . Auch eine zensurresistente Speicherung von Daten und Anonymität gewinnt durch aktuelle Entwicklungen entscheidend an Bedeutung.
• Mehr Flexibilität und Dienstgüte sind für die einfache und schnelle Integration neuer Dienste ein weiteres entscheidendes Erfolgskriterium künftiger Internet-Technologien. So konnten bisher dringend benötigte Dienste, wie etwa Gruppenkommunikation oder Mobilität, bis heute nicht mit einer adäquaten Qualität realisiert werden [Projekt i3: http://i3.cs.berkeley.edu] .

Somit wird deutlich, dass die seit Anfang der 80er-Jahre zunehmend eingesetzten Client-Server-basierten Anwendungen den neuen Anforderungen des Internets nicht mehr umfassend gerecht werden. Insbesondere zentrale Instanzen – deren Ressourcen zum Flaschenhals werden können, die gezielte Angriffspunkte darstellen oder, die aufgrund ihrer strategischen Lage im Netzwerk nicht ohne hohe Kosten modifiziert werden können – bereiten zunehmend Probleme. An dieser Stelle versprechen nun die Konzepte des Peer-to-Peer-Networking bzw. Peer-to-Peer-Computing durch einen grundlegenden Paradigmenwechsel die genannten Probleme einfacher lösen zu können. Es sei angemerkt, dass wir hier Peer-to-Peer-Networking nicht von Peer-to-Peer-Computing unterscheiden wollen, sondern uns auf „peer to peer" als Eigenschaft, Charakter, Verfahren bzw. Mechanismus konzentrieren.

Ausgehend von einer ersten Definition bei Oram [3] wird unter einem Peer-to-Peer-System ein „sich selbst organisierendes System gleichberechtigter, autonomer Einheiten (Peers)" verstanden, „das vorzugsweise ohne Nutzung zentraler Dienste auf der Basis eines Rechnernetzes mit dem Ziel der gegenseitigen Nutzung von Ressourcen operiert" – kurzum ein System mit vollständig dezentraler Selbstorganisation und Ressourcennutzung .Neben diesen grundlegenden Prinzipien lassen sich Peer-to-Peer-Systeme nach unserem Verständnis durch die folgenden Charakteristika beschreiben, wobei oftmals nur im Idealfall alle Eigenschaften gleichzeitig zutreffen.

Zur dezentralen Ressourcennutzung

1. Die relevanten Betriebsmittel (Bandbreite, Speicherplatz, Rechenkapazität) werden möglichst gleichmäßig verteilt genutzt und befinden sich an den sog. „Kanten" der Rechnernetze, bei den „Peers". Damit könnte man aus Sicht des Netzwerkes Peer-to-Peer-Systeme als die konsequente Weiterentwicklung des Ende-zu-Ende-Prinzips [4] auffassen, das als eines der entscheidenden Prinzipien für den bisherigen Erfolg des Internets gilt.
2. Eine Menge von Peers nutzen untereinander die von ihnen wiederum zur Verfügung gestellten Betriebsmittel. Die bekanntesten Beispiele solcher Betriebsmittel sind Speicherplatz (in Form von Dateien, u.a. mit Musik, Video und Programmen als Inhalt) und Prozessorleistung. Daneben sind aber auch Konnektivität, menschliche Präsenz oder aber geographische Nähe zu nennen. Beispiele hierfür sind Instant-Messaging-Daten und Gruppenkommunikationsanwendungen.
3. Peers sind über das Netz miteinander verbunden und meist weltweit verteilt.
4. Ein Peer ist oftmals nicht stets unter derselben Internet-Adresse zu identifizieren (variable Konnektivität).Typischerweise erhalten Peers beim Verbinden an das Netz jeweils eine neue Internet-Adresse dynamisch zugeteilt. Peers sind auch häufig über längere Zeit nicht am Netz angeschlossen oder gar abgeschaltet. Aufgrund dieser Unwägbarkeiten aber auch aus zahlreichen weiteren Gründen führen daher viele Peer-to-Peer-Anwendungen oberhalb der normalen Internet-Adressierung individuelle Adressräume ein. So werden Inhalte meist durch unstrukturierte Identifikatoren adressiert, die mit Hilfe von Hash-Funktionen aus den jeweiligen Inhalten gewonnen werden. Dies hat zur Folge, dass Daten nicht mehr mit ihrer Lokation (Adresse des Servers) identifiziert werden, sondern vielmehr durch den Inhalt selbst. Befinden sich beispielsweise mehrere Instanzen eines Datums im System, so kann jede dieser Instanzen das Ziel der Wegewahl werden. Das Auffinden eines Datums in einem Peer-to-Peer-System erfolgt somit durch eine inhaltsbasierte Wegewahl („content based routing") an Stelle der bislang angewandten ortsbezogenen Wegewahl.

   Zur dezentralen Selbstorganisation

5. Zur eigentlichen Nutzung der Betriebsmittel interagieren Peers direkt miteinander. Dies erfolgt im Allgemeinen ohne jegliche zentrale Steuerung. Hierin drückt sich wiederum ein ganz zentrales Merkmal von Peer-to-Peer-Systemen aus, das sie von traditionellen Client-Server-Systemen unterscheidet: während letztere Koordination ausgehend vom Server als ordnendes Paradigma verwenden, bauen Peer-to-Peer-Systeme auf Kooperation zwischen gleichberechtigten Partnern. Der Hintergrund dieses Wechsels begründet sich vor allem in der Vermeidung von Flaschenhälsen und dem Verlust von Zuverlässigkeit im Vergleich zu zentralisierten Lösungen.
6. Der Zugriff auf bzw. Transfer der gemeinsam benutzten Betriebsmittel erfolgt direkt zwischen den Peers. Hierfür existiert kein zentraler Dienst. P2P-Systeme stehen für eine grundsätzliche Dezentralisierung der Steuerung, auch wenn im Sinne der Leistungssteigerung dann auch in existierenden Systemen unter Umständen zentrale Elemente eingefügt werden, beispielsweise um die Suche nach Betriebsmitteln effizienter zu gestalten. Man bezeichnet solche Systeme auch oft als hybride Peer-to-Peer-Systeme (Abb.1b).
7. Peers selbst besitzen sowohl Client- als auch Server-Funktionalität, d.h. Peers sind beides zugleich (Abb.1c). Dies unterscheidet P2P-Systeme wesentlich von herkömmlichen Systemen mit asymmetrischer Funktionalitätsverteilung (Abb.1a) und führt sowohl zu erhöhter Flexibilität hinsichtlich der bereitgestellten Funktionalität als auch zu sehr unterschiedlichen Anforderungen an den Entwurf von Peer-to-Peer-Systemen.
8. Peers sind untereinander gleichberechtigt. Sie besitzen individuell die vollständige Autonomie bezüglich ihrer jeweiligen Betriebsmittel.
9. Das Auffinden von Ressourcen sollte möglichst ohne jeglichen zentralen Dienst erfolgen (in Abb.1a und 1b sind zentrale Dienste dafür vorhanden, in Abb.1c nicht). Idealerweise geschieht die gesamte Steuerung selbstorganisierend bzw. im ad-hoc-Modus. Wie bereits erwähnt kann hiervon im Sinne der Leistungssteigerung zwar abgewichen werden, ohne jedoch den dezentralen Charakter von P2P-Systemen völlig auszuhöhlen. Dies führt zu Peer-to-Peer-Systemen mit hybrider Struktur (Abb.1b).

Peer-to-Peer ist damit keinesfalls nur ein Verfahren zum Austausch von Dateien, sondern vielmehr ein grundlegendes Entwurfsprinzip für verteilte Systeme, in dem deutlich der Paradigmenwechsel von Koordination zu Kooperation, von Zentralisierung zu Dezentralisierung und von Kontrolle hin zu Anreizen erkennbar ist. Eine Vielzahl wichtiger Forschungsfragestellungen stehen im Zusammenhang mit geeigneten Anreizsystemen. Eine faire Balance im „Nehmen" und „Geben" unterschiedlicher Peers zu ermöglichen, kann über den Erfolg dieser Technologie entscheiden [Projekt „Market Management of Peer to Peer Services" http://www.mmapps.org] .

Einige Forschungsaspekte zu Peer-to-Peer

Bei Peer-to-Peer-Networking besteht eine grundsätzliche Herausforderung in der dezentralen Selbstorganisation eines verteilten Systems ohne die Nutzung zentraler Dienste. In diesem Zusammenhang kommt der effizienten Suche nach der Lokation eines gewünschten Datums und der damit verbundenen Verwaltung der Inhalte eine zentrale Rolle zu. Darauf aufbauend wird ein Großteil der Funktionalität von Peer-to-Peer-Systemen verwirklicht. Im Gegensatz zu zentralen Server-Anwendungen, bei denen der Speicherort eines Datums inhärent bekannt ist, können Daten in dezentralen Architekturen an zahlreichen, zum Teil weit entfernten, Stellen im Netz gespeichert werden. In den vergangenen beiden Jahren haben sich zur Lösung dieses Problems zwei Richtungen entwickelt, die kurz betrachtet werden: strukturierte und unstrukturierte Peer-to-Peer-Systeme.

Unstrukturierte Peer-to-Peer-Systeme

Unstrukturierte Verfahren wurden vor allem in den ersten Peer-to-Peer-basierten Dateitauschsystemen eingesetzt und basierten oftmals noch auf einer Server-orientierten Suche. Dabei wurde die Lokation eines Datums in einem Server verwaltet, die anschließende Kommunikation erfolgte jedoch zwischen den Peers direkt (hybrider Ansatz, vgl. Abb.1b). Andere Ansätze basieren auf dem Prinzip des Flutens, d.h. Suchnachrichten werden an alle beteiligten Systeme gesendet, bis das gewünschte System erreicht wird und sich identifiziert.

Es wird schnell deutlich, dass beide Ansätze nicht skalieren. So besitzen die Server-orientierten Verfahren einen Flaschenhals hinsichtlich ihrer Systemressourcen (Speicher, Rechenleistung und Netzbandbreite) und die Fluten-basierten Verfahren führen zu enormen Belastungen der Kommunikationsverbindungen. In der Regel entstanden diese unstrukturierten Peer-to-Peer-Anwendungen nach Anforderungen des Marktes (größtenteils für Dateitauschbörsen und Instant-Messaging) und wurden dementsprechend schnell und unkoordiniert entworfen.

Strukturierte Peer-to-Peer-Systeme

Von der Forschung wurde die Herausforderung der Skalierbarkeit unstrukturierter Peer-to-Peer-Anwendungen aufgegriffen und im Hinblick auf die enormen Möglichkeiten dezentral selbstorganisierender Systeme verschiedene Ansätze zur verteilten, inhaltsadressierbaren Speicherung von Daten (verteilte Indexstrukturen) verfolgt. Diese so genannten verteilten Hash-Tabellen („distributed hash tables", DHT) wurden neben dem Aspekt der verteilten Indexierung vor allem mit dem Ziel der Skalierbarkeit, Verlässigkeit und Fehlertoleranz entwickelt. So weisen sie gegenüber unstrukturierten Verfahren nicht nur in diesen Punkten, sondern auch in der Leistungsfähigkeit, entscheidende Vorteile auf. Verteilte Hash-Tabellen ermöglichen in der Regel das Auffinden eines Datums im Netz mit einer Komplexität von O(log N) – vergleichbar mit den bekannten, nichtverteilten Such- und Indexierungsverfahren. Im Vergleich zu den mindestens linearen Komplexitäten der zuvor genannten unstrukturierten Peer-to-Peer-Anwendungen, können sowohl das zugrunde liegende Netz als auch die Anzahl der Teilnehmer beliebig weiterwachsen, ohne die Leistungsfähigkeit der verteilten Anwendung zu gefährden. Notwendige Verwaltungsoperationen, wie etwa das Einfügen neuer Inhalte, neuer P2P-Knoten, aber auch Fehlerfälle, wie der Ausfall von Knoten, besitzen in den meisten Ansätzen verteilter Hash-Tabellen eine Komplexität von O(log N) bzw. O(log² N).

Die Arbeitsweise der verschiedenen verteilten Hash-Tabellen ist generell sehr ähnlich und unterscheidet sich im Wesentlichen in den verwendeten Such- und Verwaltungsstrategien. So existieren Ring-basierte Ansätze, wie etwa Pastry, Tapestry und Chord, die auf ähnlichen Suchverfahren wie Binär- oder B*-Bäume beruhen, und geometrische Verfahren, wie „content addressable networks" (CAN). Generell wird jedem Knoten einer verteilten Hash-Tabelle ein bestimmter Teil des Suchraums (0 –2 ^n-1)zugeteilt, wobei oftmals aus Redundanzgründen eine Replikation in benachbarten Knoten stattfindet. Durch baumähnliche Routingverfahren (beispielsweise bei Pastry)oder Sprunglisten (beispielsweise bei Chord)wird eine Anfrage von einem beliebigen Einstiegsknoten zum verwaltenden Knoten der gesuchten Kennung weitergeleitet, wobei ein logarithmischer Aufwand gewährleistet werden kann. Die für die Wegewahl notwendige Information umfasst hierbei in der Regel ebenfalls einen Umfang von O(log N)Einträgen pro Knoten.

Neben den erwähnten Ähnlichkeiten zu bekannten Indexierungsverfahren aus dem Datenbankbereich ist zu beachten, dass verteilte Hash-Tabellen zusätzlich Mechanismen zur verteilten Verwaltung der Datenstruktur, Verfahren zur Redundanz und dem Auffinden möglichst naher Instanzen des gesuchten Datums verfügen. Hinsichtlich Details der jeweiligen Such- und Verwaltungsoperationen bestimmter verteilter Hash-Tabellen wird auf die jeweiligen Publikationen verwiesen. Balakrishnan et al.[1] geben hierzu eine gute Übersicht.

Resümee

An künftige verteilte Systeme und Anwendungen werden für einen erfolgreichen Einsatz im Internet gestiegene Anforderungen gestellt. Neben der Skalierbarkeit, einer entsprechenden Qualität und mehr Flexibilität stellen die Verlässigkeit und der Schutz vor gezielten Angriffen kritische Eigenschaften dar, deren intensive Erforschung mit einer erfolgreichen Umsetzung in die Praxis die Relevanz von Peer-to-Peer-Anwendungen und -Systemen entscheidend prägen wird

                   Artikelanfang  Seitenanfang

Literatur

1. Balakrishnan H., Kaashoek M. F., Karger D., Morris R., Stoica I.: Looking up data in P2P systems: Communications of the ACM 46 (2), Februar 2003
2. Eberspächer J., Steinmetz R. (Hrsg.): Schwerpunktheft zu Peer-to-Peer, Praxis in der Informationsverarbeitung & Kommunikation (PIK). K. G. Sauer Verlag, Juni 2003
3. Oram A.: Harnessing the power of disuptive technologies. O’Reilly, Sebastopol/CA, USA 2001
4. Saltzer J. H., Reed D. P., Clark D. D.: End-to-end arguments in system design. ACM Transactions on Computer Systems 2 (4), 277 –288 (1984)

Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert.

                   Artikelanfang  Seitenanfang

Autor & Copyright
R. Steinmetz
TU Darmstadt,
Darmstadt
ralf.steinmetz@kom.tu-darmstadt.de

K. Wehrle
Universität Tübingen
Klaus.Wehrle@uni-tuebingen.de

DOI 10.1007/s00287-003-0362-9
© Springer-Verlag 2004

                   Artikelanfang  Seitenanfang

Pervasive/Ubiquitous Computing

• Kurzinfo
• Erläuterung
• Literatur
• Autor & Copyright

Kurzinfo Unter den beiden oft äquivalent gebrauchten Begriffen „Pervasive Computing" und „Ubiquitous Computing" wird die Allgegenwärtigkeit von Informationsverarbeitung und damit einhergehend der jederzeitige Zugriff auf Daten von beliebiger Stelle aus verstanden.

Erläuterung

Internetfähige Handys und Spielkonsolen sowie PDAs, die drahtlos mit anderen Geräten ihrer Umgebung kommunizieren, sind erste Vorboten des kommenden „Post-PC-Zeitalters", welches u.a. dadurch charakterisiert ist, dass aus Anwendersicht das Internet mit Mobilkommunikationssystemen wie z.B. UMTS zusammenwächst („mobile internet") und dass sich Anwendungen vom PC oder Server emanzipieren und in kleine eigenständige, spezialisierte „information appliances" abwandern [2, 4].

Ermöglicht wird dies durch den weiter anhaltenden Fortschritt der Informationstechnik – das Moore'sche Gesetz mit seiner postulierten anderthalbjährlichen Verdoppelung der Leistungsfähigkeit von Prozessoren und Speicherbausteinen (bzw. der entsprechenden Verkleinerung und Verbilligung bei konstanter Leistungsfähigkeit) dürfte noch eine ganze Reihe von Jahren seine Gültigkeit behalten.

Aber auch neue Entwicklungen der Materialwissenschaft (z.B. kleinste Sensoren, „leuchtendes Plastik", „elektronische Tinte") und Fortschritte der Kommunikationstechnik, insbesondere im drahtlosen Bereich, tragen in technischer Hinsicht dazu bei, dass es bald kleinste und spontan miteinander kommunizierende Rechner im Überfluss geben wird. Diese sollten dann allerdings oft kaum mehr als solche wahrgenommen werden, da sie in Gebrauchsgegenstände eingebettet werden und so mit der alltäglichen Umgebung verschmelzen.

Smart Devices

Bei den zukünftigen informationstechnisch aufgerüsteten Alltagsgegenständen, sog. „smart devices", wird es sich anfangs sicherlich eher um höherpreisige Haushaltsgeräte, Werkzeuge, Spielzeuge oder Autos handeln, die einen offensichtlichen Mehrwert durch sensorgestützte Informationsverarbeitung und Kommunikationsfähigkeit erhalten. Letztendlich geht es aber auch um so alltägliche Dinge wie Schreibstifte (die alles digitalisieren, was mit ihnen geschrieben wird), Kleidungsstücke (welche sich an besuchte Orte oder belauschte Gespräche erinnern mögen) oder Regenschirme, die einen Internet-Wetterdienst abonniert haben und ggf. die Haustür veranlassen, eine freundliche Erinnerung anzuzeigen.

Letzteres mag etwas absurd erscheinen oder nach Science-Fiction klingen – tatsächlich ist es aber nicht ganz einfach, sich auszumalen, was in einer Welt aus informatisierten und miteinander vernetzten Alltagsdingen unter Berücksichtigung ökonomischer und gesellschaftlicher Bedingungen möglich und akzeptabel ist und welche neuen Anwendungen und Dienste sowie Geschäftsfelder sich herausbilden könnten, wenn etwa Dinge sich genau lokalisieren können oder aus der Ferne identifizierbar sind oder wenn Gegenstände ein (in das Internet ausgelagertes) episodisches Gedächtnis besitzen, wodurch ihr sensorischer Input für andere abfragbar ist. Prinzipiell scheint dies jedenfalls bald machbar, genauso wie vielleicht das elektronisch beschreibbare „smart paper", welches manchen Computern dann ein radikal anderes Aussehen, etwa als zusammenfaltbare Straßenkarte, verleihen könnte. In den Konsequenzen zu Ende gedacht, dürfte eine Welt aus „smarten" Dingen jedenfalls zu einer deutlich veränderten Wahrnehmung unserer Umgebung führen, größere gesellschaftliche und ökonomische Auswirkungen haben und damit letztendlich sogar von politischer Relevanz sein. Mit Sicherheit ist dabei die Privatsphäre im Sinne von Datenschutz und „Privacy" betroffen; die weitergehenden Folgen in kultureller und wirtschaftlicher Hinsicht erscheinen derzeit allerdings noch relativ unklar.

Verschwindende Technologie

Die hier angedeutete langfristige Vision wurde von dem 1999 früh verstorbenen Mark Weiser, seinerzeit leitender Wissenschaftler am Forschungszentrum von XEROX in Palo Alto, propagiert, der dafür bereits vor mehr als 10 Jahren den Begriff „Ubiquitous Computing" prägte [5]. Weiser sieht Technik als reines Mittel zum Zweck an, die in den Hintergrund treten sollte, um eine Konzentration auf die Sache an sich zu ermöglichen – der PC als Universalwerkzeug sei dafür der falsche Ansatz, da dieser aufgrund seiner Komplexität die Aufmerksamkeit zu sehr in Anspruch nehme. Er schreibt u.a.:

„As technology becomes more imbedded and invisible, it calms our lives by removing the annoyances . . . The most profound technologies are those that disappear. They weave themselves into the fabric of everyday life until they are indistinguishable from it."

Ob das scheinbar Paradoxe gelingt, nämlich trotz zunehmender Menge und Allgegenwart von Information diese dann – etwa mittels intuitiver Schnittstellen und impliziter Informationsverarbeitung – auch einfacher zu nutzen, bleibt abzuwarten. Die von Weiser avisierte „verschwindende Technologie" hat jedenfalls der neuen „Disappearing-Computer"-Forschungsinitiative der EU [6] nicht nur den Namen verliehen, sondern auch ganz wesentlich deren Forschungsprogramm und Ziele beeinflusst.

Während allerdings Weiser den Begriff „Ubiquitous Computing" eher in akademisch-idealistischer Weise als eine unaufdringliche, humanzentrierte Technikvision verstand, die sich erst in der weiteren Zukunft realisieren lässt, hat die Industrie dafür später den Begriff „Pervasive Computing" mit einer leicht unterschiedlichen Akzentuierung geprägt: Auch hier geht es um die überall eindringende und allgegenwärtige Informationsverarbeitung, jedoch mit dem primären Ziel, diese eher kurzfristig im Rahmen von Electronic-Commerce-Szenarien und Webbasierten Geschäftsprozessen nutzbar zu machen.

Anfänge des Pervasive Computing

In gewisser Hinsicht findet Pervasive Computing zumindest in rudimentärer Weise derzeit bereits statt, da z.B. schon jetzt WAP-Handys oder andere drahtlos kommunizierende PDAs und Information Appliances über fernladbaren Programmcode mit lokaler „Intelligenz" ausgestattet werden können und so situationsangepasst einen Informationszugang „immer und überall" ermöglichen. Entsprechend wird unter dem Begriff „Pervasive Computing" vielfach eine Ansammlung von modernen IT-Techniken zur Realisierung größerer, oft internetbezogener Anwendungssysteme subsumiert, bei denen mobile und heterogene Front-End-Geräte eingesetzt werden. Dazu gehören Kommunikationskonzepte und -protokolle (z.B. WAP, Bluetooth, HTTP), Techniken zur Datenrepräsentation (z.B. XML) und Betriebssoftware für Chipkarten und PDAs genauso wie allgemeinere Softwarekonzepte, Middleware und Methoden der Kryptographie [1].

Für die praktische und angewandte Forschung und Entwicklung in der Informatik ergeben sich vielfältige Betätigungsmöglichkeiten – sowohl in den Einzeldisziplinen als auch im komplexen Zusammenspiel der verschiedenen Aspekte [3]. Dies wird schon deutlich, wenn man sich vergegenwärtigt, dass es zumindest in der ultimativen Vision gewissermaßen um die Verlängerung des Internets bis in beliebige Alltagsgegenstände hinein geht. Gegenüber der heutigen Netztechnik stellen sich hier nicht nur die bekannten Probleme (Protokolle, Routing, Quality of Service etc.) in einer wesentlich größeren Dimension, sondern der höhere Grad an Mobilität, Dynamik und Heterogenität führt auch zu ganz neuen Aspekten.

Systemarchitekturen müssen z.B. berücksichtigen, dass bei portablen und eingebetteten Systemen mit elektrischer Energie äußerst sparsam umgegangen werden muss, dass nicht immer und überall eine direkte Kommunikationsmöglichkeit besteht, dass schon aus Kosten- und Platzgründen die Systemressourcen oft sehr begrenzt sind und dass man zum Management der „Geräte" keinen Systemverwalter einstellen kann – spontane Vernetzung, „plug & play", automatische Synchronisation der Daten zwischen verschiedenen Information Appliances sowie hochgradige Interoperabilität und fehlertolerantes Verhalten sind unverzichtbar!

Fragen

Wichtige Aspekte ergeben sich aber auch bei grundlegenderen Fragen, die breiter erforscht werden müssen (und Stoff für manche Dissertation ergeben dürften), wenn die Vision des Ubiquitous Computing Realität werden sollte: Wie lässt sich z.B. das Datenschutzproblem angehen, wenn sehr viele Sensoren und „smart devices" personenbezogene Daten erzeugen und diese kommunizieren – und zwar ohne dass jeder zum Sicherheitsexperten werden muss? Oder: Wie lassen sich die Unmengen von generierten Daten strukturieren, damit Anwendungen, die man in einer offenen Welt nicht alle kennen kann, sie geeignet nutzen können? Oder: Wie finden Geräte und Services automatisch zueinander und welche Ontologie liegt ihrem Verhandlungsprotokoll zugrunde? Oder: Wie interagiert man eigentlich mit unsichtbaren Computern? Offensichtlich sind hierfür neue Interaktionstechniken nötig, z.B. bessere Sprachein- und -ausgabe oder sogar weitgehend implizite Schnittstellen.

Besonders spannend erscheinen die Möglichkeiten (und aus Forschungssicht auch die damit verbundenen Probleme!), die sich durch Anwendung und Kombination neuer Techniken ergeben.

Beispielhaft seien hier zum Schluss noch einige Gebiete aufgeführt, die etwas weiter in die Zukunft weisen. Dazu gehört das „wearable computing", das vielfältige Anwendungsmöglichkeiten bietet, aber beispielsweise im Bereich der automatischen Erkennung von Gesichtern oder Situationen grundlegende Forschungsfragen aufwirft. Ein anderes Beispiel sind Techniken zur Positionsbestimmung (etwa mittels satellitengestützter Systeme wie GPS oder Funkpeilverfahren bei Handys), die zusammen mit weiteren Sensorinformationen ein orts- und kontextbezogenes Verhalten von „smart objects" ermöglichen – auch hier gibt es noch viel zu erforschen.

Schließlich seien noch die Möglichkeiten erwähnt, die sich durch fernabfragbare elektronische Marker (z.B. sog. passive „radio tags") an Alltagsgegenständen ergeben – damit lassen sich Artefakte der realen Welt eindeutig erkennen und so in Echtzeit mit einem zugehörigen Datensatz oder aktiven Schattenobjekt der virtuellen Welt verknüpfen, wodurch letztendlich beliebige Dinge mit spezifischen Informationsverarbeitungsfähigkeiten ausgestattet werden können.

Computing without Computers

Pervasive und Ubiquitous Computing scheinen durch die breite Nutzung von Computern in Form von Sekundärartefakten und die damit einhergehende engere Kopplung von Informationswelt und physischer Welt einen Paradigmenwechsel in den Informatik einzuleiten: Zum einen folgt auf das PC-Zeitalter nunmehr die Ära des überall vorhandenen, aber unsichtbaren Rechners, zum anderen verliert durch die Spezialisierung in Form von „smart devices" die Metapher des Computers als Universalwerkzeug an Überzeugungskraft, wenn auch nicht an grundsätzlicher Bedeutung.

Wenn alles von miteinander vernetzten Prozessoren durchdrungen ist, werden aber Informatikkonzepte umso wichtiger – „computing without computers" lautet hier die gelegentlich zu hörende und etwas spöttisch formulierte Devise. Gemeint ist dabei der Computer als ein durch seine physische Gestalt identifizierbares „Rechengerät" – in dieser Form dürfte man ihn irgendwann wohl tatsächlich nur noch im Museum bewundern können.

                   Artikelanfang  Seitenanfang

Literatur

1. Hansmann, U., Merk, L., Nicklous, M., Stober, T.: Pervasive Computing Handbook. Berlin Heidelberg New York: Springer 2001
2. Norman, D. A.: The Invisible Computer. Cambridge/MA: MIT Press 1998
3. Thomas, P., Gellersen, H. W. (eds.): Proc. 2nd Int. Symp. Handheld and Ubiquitous Computing. Berlin Heidelberg New York: Springer 2000
4. Want, R., Borriello, G.: Special Issue on Information Appliances. IEEE Computer Graphics and Applications, May/June 2000
5. Weiser, M.: The Computer for the 21st Century. Scientific American, September 1991, 66–75
6. Disappearing Computer: www.i3net.org/ser_pub/services/dc

                   Artikelanfang  Seitenanfang

Autor & Copyright
Friedemann Mattern
ETH Zürich,
Department of Computer Science,
Institute of Information Systems,
CH-8092 Zürich
mattern@inf.ethz.ch

© 2001 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang