Parallele Algorithmen by Dr. rer. nat. F. Hoßfeld (auth.)

By Dr. rer. nat. F. Hoßfeld (auth.)

Zu den allgemeinen Einordnungen von Algorithmen ist in den letzten Jahren eine neue Klassifikation wichtig geworden: parallel as opposed to sequentiell. Die Ursache findet sich in der nicht zuletzt durch die Entwicklungen der Halbleitertechnologie, vor allem aber durch den wachsenden Druck von Anwendungen, die höchste Rechnerleistung erfordern, erhöhten Bedeutung von Parallelprozessorarchitekturen. Das zunehmende Interesse an Parallelrechnern hat die Entwick­ lung von parallelen Algorithmen zur Lösung vielfältiger Problemstellungen beschleunigt. Eine Darstellung von Grundprinzipien, Entwurfsmöglichkeiten und Realisierungen paralleler Algorith­ males, die das Leistungspotential innovativer Rechnerarchitekturen erschließen, erscheint für die integrale Betrachtung der Thematik des "Parallel Computing" nicht nur notwendig, sondern auch - vor allem auf die deutschsprachige Fachliteratur bezogen - überfällig. Dem vorliegenden Band liegt das Skriptum -einer Spezial vorlesung gleichen Titels zugrunde, die ich im Sommersemester 1980 an der Universität Dortmund auf Einladung der Abteilung Informatik gehalten habe. Es ist nicht das Ziel, eine möglichst vollständige Sammlung der in den Zweigen dieses expansiven Forschungsgebietes bisher entwickelten parallelen Algorithmen zu liefern; vielmehr sollen mit dieser Annäherung an eine erste Gesamtdarstellung der Themati- insbesondere auch durch die Gegenüberstellung von repräsentativen sequentiellen Algorithmen - Charakteristika originärer paralleler Algorithmen aufgezeigt und ihr Bezug zu den Architektur­ elementen von Parallelprozessoren verdeutlicht werden. Dadurch soll auch hierzulande das Interesse an dieser immer wichtiger werdenden Fragestellung weiter gefördert und der Einstieg in die junge, über ein breites Spektrum von hauptsächlich englischsprachigen Fachzeitschriften verstreute Originalliteratur erleichtert werden; wegen der angelsächsischen Dominanz auf diesem Gebiet lassen sich dabei für die klare Begriffsbestimmung naturgemäß gewisse Anglizismen nicht vermeiden.

Show description

Read Online or Download Parallele Algorithmen PDF

Similar german_5 books

Rhetorik für den Ingenieur

Rhetorik für den Ingenieur. - Diese Aussage impliziert eine paintings Sonderbehandlung für eine spezielle Berufsgruppe. Unterscheidet sich denn deren Rhetorik, d. h. genaugenommen die Handhabung rhetorischer Ausdrucksformen und -mittel, so wesentlich von der Rhetorik anderer Berufe? Sehr generalisiert betrachtet sicher­ lich, wenn guy die üblichen Kommunikationsgewohnheiten der I ngenieure analysiert.

Programmierung und Datenstrukturen: Eine Einführung anhand von Beispielen

Dieses Buch ist aus der zweisemestrigen EinfUhrungsvorlesung Informatik 1 und 2 an der ErR Ziirich entstanden. Da der Inhalt des ersten Semesters, der die Abschnitte 1 und 2 umfasst, eine unkonventione11e EinfUhrung in die Informatik darstellt, ist eine ErkHirung angebracht, damit der Leser beurteilen kann, ob die Voraussetzungen und Zielsetzungen dieses Buches auf ihn zutreffen.

Interaktive Systeme: Software-Entwicklung und Software-Ergonomie

Die Akzeptanz und damit der Erfolg interaktiver Systeme (Software und zur gemeinsamen Bewaltigung von Aufgaben durch Mensch und computing device) wer den grofitenteils von ihrer Benutzerschnittstelle bestimmt. Daher ziihlen Benutzer schnittstellen heute zu intensiv beforschten Systemkomponenten. Die Gestaltung interaktiver Systeme wird nicht nur von software program und an der Schnitt stelle dominiert.

Extra resources for Parallele Algorithmen

Sample text

Wie steht es mit Unabhängigkeitsannahmen über die Verteilung der Eingabedaten? Mit dem Maß für das Verhalten im Mittel geht man darüber hinaus das Risiko ein, von einem zwar selten auftretenden, für die Laufzeit aber sehr schlechten Satz von Eingabedaten überrascht zu werden. Formal können wir beide Komplexitätsmaße etwa folgendermaßen fassen, wenn wir dazu definieren: Es sei n die Menge aller möglichen Eingabedaten (w1,w2, ..... ). l Es sei TCA;w) der Rechenzeitverbrauch für den Algorithmus A bei der Fragestellung weIl Der Fragestellung w messen wir die natürliche Zahl g(w) als "Problemgröße" zu; es sei definiert fl*:w 6 ll, wobei g(w) = n.

3 Problemklassifizierung durch Schranken Über weite Strecken werden wir hier den Zugang zur Komplexität wesentlich pragmatischer suchen können. Allerdings kommt bei der schließlichen Zielsetzung, bei den parallelen Algorithmen, eine neue Qualität in Gestalt der p ) 1 Prozessoren hinzu. Die Existenz von Komplexitätsschranken für Algorithmen kann als Grundlage für die Klassifizierung der Probleme dienen. So hat Jakeman 1976 vorgeschlagen, auf diese Weise 4 verschiedene Klassen von Problemen zu identifizieren: (I) ~s gibt eine Klasse von Problemen, für die Komplexitäts-Schraricen mit Hilfe bestimmter Sätze und Beweistechniken bestimmt werden können, ohne daß eine wirkliche Konstruktion eines Algorithmus für diese Probleme erforderlich (oder möglich) ist.

B) Die Methode auf der Grundlage des "Divide-and-Conquer" erfordert Bit-Operationen (vgl. Aha, Hopcroft and Ullman /15/, S. 62). (3) Allgemeine Rekurrenz Die Zeitkomplexität von Algorithmen, die nach dem "Teile-und-Herrsche"-Konzept entwickelt werden können, läßt sich durch rekurrente Gleichungen beschreiben, in die der Aufwand für die Teilprobleme eingeht sowie ggf. ein Anteil, der der akuten Problemgröße proportional ist. }) + bn c für n = 1 für n> 1. 54 SA TZ: Es seien a, bund c nicht-negative Konstante.

Download PDF sample

Rated 4.02 of 5 – based on 20 votes

Related posts