Willkommen, schön sind Sie da!
Logo Ex Libris

Parallele Algorithmen

  • Kartonierter Einband
  • 244 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Zu den allgemeinen Einordnungen von Algorithmen ist in den letzten Jahren eine neue Klassifikation wichtig geworden: parallel vers... Weiterlesen
20%
75.00 CHF 60.00
Print on Demand - Auslieferung erfolgt in der Regel innert 4 bis 6 Wochen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

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 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.

Inhalt

Inhaltsverzeichnis:.- 1 Grundlagen und Voraussetzungen.- 1.1 Einfà hrung.- 1.2 Zielsetzung.- 1.3 Ãoebersichtsliteratur.- 1.4 Parallelprozessoren: Ãoebersicht.- 2 Analyse und Bewertung von Algorithmen.- 2.1 Der Algorithmusbegriff 9.- 2.1.1 Der Euklid-Algorithmus.- 2.2 Anforderungen an einen Algorithmus.- 2.3 LeistungsmaÃYe: Komplexità t.- 2.3.1 Komplexità tsmaÃYe.- 2.3.2 ProblemgröÃYe.- 2.3.3 Verhalten im Mittel u. schlechtesten Fall.- 2.4 Rechnermodelle zur Komplexità tsanalyse.- 2.4.1 Komplexità tszusammenhà nge zwischen Turing- und Register-Maschinen.- 2.4.2 Gap- und Speedup-Theorem.- 2.4.3 Problemklassifizierung durch Schranken.- 2.5 Kategorien "guter" und "schlechter" Algorithmen.- 2.5.1 Erfolge des Algorithmen-Design.- 2.6 Konzepte fà r effiziente Algorithmen.- 2.6.1 Rekursion.- (1) (Binà re) Bà ume.- (2) Rekursives Programm INORDER.- (3) Berechnung der Zeitkomplexità t.- 2.6.2 'Teile-und-Herrsche'-Konzept.- (1) MAÃ-MIN-Algorithmus.- (2) Berechnung der Komplexità t.- (3) Allgemeine Rekurrenz.- 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.7.1 Komplexità tsgrenzen: absolut.- 3.7.2 Transformation.- 3.7.3 Reduktion bei Klammerung.- 3.7.4 Komplexità tsgrenzen: Status.- 3.8 Speedup-Klassen paralleler Algorithmen.- 3.9 Literaturà bersicht: neuere Algorithmen.- 4 Algorithmen der Linearen Algebra.- 4.1 Berechnung von An.- 4.1.1 Serielles Verfahren.- 4.1.2 Paralleler Algorithmus fà r Xn.- (1) Rekursives Doppeln.- (2) Binà rdarstellung von n.- (3) Methode nach Kung (1974).- 4.1.3 Potenzen quadratischer Matrizen.- 4.1.4 Berechnung von (X, X2,, Xn).- 4.2 Matrixmultiplikation.- 4.2.1 Orthodox-serielle Matrixmultiplikation.- 4.2.2 Die Winograd-Identità t.- 4.2.3 Winograd-Algorithmus der Matrixmultiplikation.- 4.2.4 Strassen-Algorithmus fà r (2x2)-Matrizen.- 4.2.5 Strassen-Algorithmus fà r n = m. 2k+1.- 4.2.6 Winograds Variante.- 4.2.7 Die Karatsuba-Makarov-Methode.- 4.2.8 Paralleler Algorithmus fà r Arrayprozessoren.- (1) Parallelisierung.- (2) Realisierung mit Arrayprozessor.- (3) "Systolischer" Algorithmus fà r Bandmatrizen.- 4.2.9 Parallele Berechnung des Skalarproduktes.- 4.2.10 Paralleler Algorithmus mit O(logn).- 4.2.11 Matrix-Kettenprodukt.- 4.3 Transponieren von Matrizen.- 4.3.1 Das Perfect-Shuffle-Prinzip.- 4.3.2 Transposition von (2mx2m)-Matrizen.- (1) Speicherordnung.- (2) Perfect-Shuffle.- 4.3.3 Algorithmus nach Schumann.- (1) Das Verfahren.- (2) Beispiel.- (3) Formale Darstellung.- (4) Parallelisierung mittels "q-nà rem Unshuffle".- 4.4 Lineare Gleichungssysteme.- 4.4.1 Lösungsbedingungen.- 4.4.2 Die GauÃY-Elimination.- (1) Konstruktion des Verfahrens.- (2) Dreiecks-Zerlegung.- (3) Komplexità t der GauÃY-Elimination.- 4.4.3 Das GauÃY-Jordan-Verfahren.- (1) Konstruktion des Verfahrens.- (2) Algorithmus.- (3) Arithmetische Operationen.- (4) Pivotisierung.- 4.4.4 Paralleles GauÃY-Jordan-Verfahren.- (1) Algorithmus.- (2) Algorithmus fà r n Prozessoren.- 4.4.5 Parallele Matrix-Inversion nach Csanky.- (1) Konstruktion des Algorithmus.- (2) Der Csanky-Algorithmus.- (3) ZeitkompleÃ-ità t.- (4) Bemerkungen zur Stabilità t.- 4.5 Lineare Rekurrente Systeme.- 4.5.1 Definition linearer rekurrenter Systeme.- 4.5.2 Serielle Rà cksubstitution.- 4.5.3 Der Column-Sweep-Algorithmus.- (1) Der Algorithmus.- (2) Speedup und Effizienz.- 4.5.4 Rekurrenter Produktform-Algorithmus I.- (1) Funktionsweise des Algorithmus.- (2) Das allgemeine Dreiecks-ystem.- (3) Der Algorithmus.- (4) Zeitkomplexità t und Prozessorzahlen.- (5) Spezialfall des Sameh/Brent-Satzes.- 4.5.5 Satz von Sameh und Brent à ber R(n,m).- 4.5.6 Rekurrenter Produktform-Algorithmus II.- (1) Gewöhnliche rekurrente Systeme und allgemeine Dreieckssystem-Produkt form.- (2) Rekursionsbeziehungen.- (3) Zeitkomplexità t und Prozessorzahl.- (4) Produktform-Algorithmus II fà r m < n-1.- 4.5.7 Ergebnisse fà r beschrà nkte Prozessorzahlen.- 4.5.8 Rekurrente Systeme mit konstanten Koeffizienten.- 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ÃYbemerkungen.

Produktinformationen

Titel: Parallele Algorithmen
Autor:
EAN: 9783540122838
ISBN: 978-3-540-12283-8
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Genre: Sonstiges
Anzahl Seiten: 244
Gewicht: 429g
Größe: H244mm x B170mm x T13mm
Jahr: 1983

Weitere Produkte aus der Reihe "Informatik-Fachberichte"