Parallele Algorithmen - Hossfeld, F.

. .

Résumé :
Zu den allgemeinen Einordnungen von Algorithmen ist in den letzten Jahren eine neue Klassifikation wichtig geworden: parallel versus 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? men, 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 Spektrumvon 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.

Sommaire:
Inhaltsverzeichnis:.- 1 Grundlagen und Voraussetzungen.- 1.1 Einf??hrung.- 1.2 Zielsetzung.- 1.3 ??bersichtsliteratur.- 1.4 Parallelprozessoren: ??bersicht.- 2 Analyse und Bewertung von Algorithmen.- 2.1 Der Algorithmusbegriff 9.- 2.2 Anforderungen an einen Algorithmus.- 2.3 Leistungsma??e: Komplexit??t.- 2.4 Rechnermodelle zur Komplexit??tsanalyse.- 2.5 Kategorien guter und schlechter Algorithmen.- 2.6 Konzepte f??r effiziente Algorithmen.- 3 Elemente paralleler Algorithmen.- 3.1 Prozessor-Voraussetzungen.- 3.2 Parallele Zeitkomplexit??t: Definitionen.- 3.3 Darstellung paralleler Operationen.- 3.4 Satz von Munro und Paterson (1973).- 3.5 Satz von Brent (1974).- 3.6 Rekursives Doppeln.- 3.7 Parallele Berechnung arithmetischer Ausdr??cke.- 3.8 Speedup-Klassen paralleler Algorithmen.- 3.9 Literatur??bersicht: neuere Algorithmen.- 4 Algorithmen der Linearen Algebra.- 4.1 Berechnung von An.- 4.2 Matrixmultiplikation.- 4.3 Transponieren von Matrizen.- 4.4 Lineare Gleichungssysteme.- 4.5 Lineare Rekurrente Systeme.- 5 Schnelle Fourier-Transformation (FFT).- 5.1 Diskrete Fourier-Transformation (DFT).- 5.2 Fast Fourier Transform (FFT).- 5.3 Parallele FFT.- 6 Partielle Differentialgleichungen und weitere Gebiete.- 6.1 Partielle Differentialgleichungen.- 6.2 Andere Gebiete der Numerik.- 6.3 Graphenalgorithmen.- 7 Wechselwirkungen mit der Architektur und Technologie.- 7.1 Parallelisierung im Rechnermodell und bei realen Rechnern.- 7.2 Kommunikationskomplexit??t.- 7.3 Hardware- und systolische Algorithmen.- 8 Schlu??bemerkungen.