Optimale systolische Präfixberechnungen

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.