Optimale systolische Prfixberechnungen: Ein praxisrelevanter Beitrag zum Entwur [Paperback]

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.1 Einleitung.- I Zur Modellierung und Bewertung von synchronen Hardware-Algorithmen.- 2 Motivation.- 3 Ein allgemeines Modell.- 4 Realisierungsunabh?ngige Bewertung.- 5 Eingabedaten-abh?ngige I/O-Schemata.- 6 Realisierungen.- 7 Realisierungsabh?ngige Bewertung.- II Untere Schranken.- 8 Pr?liminarien.- 9 Realisierungsunabh?ngige untere Schranken.- 10 Allgemeine realisierungsabh?ngige untere Schranken.- 11 Untere Schranken f?r zeitoptimale Verfahren.- III Obere Schranken.- 12 Vorbemerkungen.- 13 Pr?fixberechnung in Linearzeit.- 14 PPCs in konstanter Zeitl³+