Optimale systolische Präfixberechnungen: Ein praxisrelevanter Beitrag zum Entwurf effizienter paralleler Algorithmen (DUV: Datenverarbeitung) (German Edition)

Der erfolgreiche Einsatz der elektronischen Datenverarbeitung in fast allen Lebensbereichen beruht u.a. auf der Verwendung von effizienten Algorithmen zur Lösung der jeweils betrachteten Probleme. Einige dieser Probleme treten in besonders großer Häufigkeit (z.B. als Teilprobleme komplexerer Probleme) und mit großen Problemdimensionen auf. Die fundamentale Bedeutung dieser grundlegenden Probleme führt zu einem beständigen Streben nach Verringe­ rung der Rechenzeiten und Erhöhung der behandelbaren Problemgrößen. Den hieraus resultierenden Anforderungen kann man auf zweierlei Weise begegnen. Zum einen wird versucht, durch Fortentwicklung herkömmlicher Technologien die Geschwindigkeit und Kapazität konventioneller sequentieller Ein-Prozessor-Rechensysteme zu steigern. Diesbezüglich hat man in den letz­ ten zwanzig Jahren bedeutende Erfolge erzielt. Mittlerweile sind hier jedoch Grenzen erreicht, die keine weiteren Verbesserungen um Größenordnungen mehr erlauben. Diese Barrieren lassen sich auf dem zweiten Weg überwinden, der Ausnutzung von möglicher paralleler Erledigung von Teilaufgaben und der gleichzeitigen Bearbeitung mehrerer Probleminstanzen. Um zu einer deutli­ chen Leistungssteigerung zu kommen, wird allerdings eine signifikante bzw. sehr große Anzahl von Prozessoren benötigt. Die z.T. stürmische technologi­ sche Entwicklung im mikroelektronischen Bereich hat diesem zweiten Weg zu einer großen Bedeutung verholfen. Front Matter....Pages i-6 Einleitung....Pages 7-20 Front Matter....Pages 21-21 Motivation....Pages 23-31 Ein allgemeines Modell....Pages 33-65 Realisierungsunabhängige Bewertung....Pages 67-81 Eingabedaten-abhängige I/O-Schemata....Pages 83-86 Realisierungen....Pages 87-95 Realisierungsabhängige Bewertung....Pages 97-116 Front Matter....Pages 119-119 Präliminarien....Pages 121-128 Realisierungsunabhängige untere Schranken....Pages 129-139 Allgemeine realisierungsabhängige untere Schranken....Pages 141-181 Untere Schranken für zeitoptimale Verfahren....Pages 183-192 Front Matter....Pages 197-197 Vorbemerkungen....Pages 199-206 Präfixberechnung in Linearzeit....Pages 207-215 PPCs in konstanter Zeit durch Zeit- /Ortsunbestimmtheit....Pages 217-220 Zeitmehrdeutige Hardware-Algorithmen....Pages 221-234 Ein zeit-/ortseindeutiger 2D□-Algorithmus für schnelle PPCs....Pages 235-291 Ein zeit-/ortseindeutiges 3D□-Verfahren für schnelle PPCs....Pages 293-302 Zusammenstellung der oberen Schranken für PPCs....Pages 303-308 Schlußbemerkungen und Ausblick....Pages 309-311 Back Matter....Pages 313-341