Optimale systolische Präfixberechnungen: Ein praxisrelevanter Beitrag zum Entwurf effizienter paralleler Algorithmen

استفاده موفقیت آمیز از پردازش الکترونیکی داده ها در تقریباً در تمام زمینه های زندگی، از جمله، بر استفاده از الگوریتم های کارآمد برای حل مشکلات در نظر گرفته شده است. برخی از این مشکلات با فرکانس بالا (مثلاً به عنوان مشکلات فرعی مسائل پیچیده تر) و با ابعاد بزرگ مشکل رخ می دهند. اهمیت اساسی این مشکلات اساسی منجر به تلاش مداوم برای کاهش زمان محاسبات و افزایش اندازه مشکل قابل درمان می شود. الزامات حاصل را می توان از دو طریق برآورده کرد. از یک طرف، تلاش‌هایی برای افزایش سرعت و ظرفیت سیستم‌های محاسباتی متوالی تک پردازنده‌ای متداول با توسعه بیشتر فناوری‌های مرسوم انجام می‌شود. موفقیت های چشمگیری در این زمینه طی بیست سال گذشته به دست آمده است. با این حال، در این بین، محدودیت‌هایی در اینجا به دست آمده است که دیگر اجازه نمی‌دهد تا پیشرفت‌های بیشتری با دستورات بزرگ انجام شود. این موانع را می توان به روش دوم، با بهره برداری از تکمیل موازی احتمالی وظایف فرعی و پردازش همزمان چندین نمونه مشکل غلبه کرد. با این حال، برای دستیابی به افزایش قابل توجهی در عملکرد، تعداد قابل توجهی یا بسیار زیاد پردازنده مورد نیاز است. توسعه گاه متلاطم فناوری در زمینه میکروالکترونیک، این راه دوم را از اهمیت زیادی برخوردار کرده است.

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.