*Dr. Werner Gerhard ist wiss. Angestellter am Lehrstuhl Rechnerarchitektur und Verkehrstheorie der Universität Erlangen-Nürnberg.

Feldrechner zählen zu den parallelen Rechnerarchitekturen. Sie galten bisher als

Spezialrechner für einen begrenzten Aufgabenkreis. Werner Erhard* schildert im folgenden Beitrag die technischen Grundlagen dieser Architektur und in welchen Bereichen Feldrechner mittlerweile eingesetzt werden können.

In der Öffentlichkeit wurde der Begriff Supercomputer immer mit dem Typ des Pipeline-Rechners in Verbindung gebracht. Die Gründe hierfür waren zum einen, daß sich insbesondere die Computerhersteller aus den USA als Marktführer das Pipeline-Prinzip zu eigen machten, zum anderen, weil die Benutzer glaubten, mit ihren bisherigen Programmen auf diesen Pipeline-Rechnern die von den Herstellern angegebenen Spitzenleistungen erzielen zu können.

Inzwischen ist hier eine gewisse Ernüchterung eingetreten, so daß auch Alternativen eine Chance am Markt erhalten. Zu diesen zählt der Feldrechner. Er besteht aus einem in der Regel zweidimensionalen Feld von Prozessorelementen, die alle zu einem bestimmten Zeitpunkt den gleichen Befehl abarbeiten, allerdings auf unterschiedlichen Daten. Man spricht hier vom SIMD-Prinzip (SIMD = Single Instruction, Multiple Data).

Bitalgorithmen beschleunigen mathematische Operationen

Bisher galten diese Feldrechner im allgemeinen als Spezialrechner, die sich nur für einen kleinen Aufgabenkreis eignen. Das Institut für Mathematische Maschinen und Datenverarbeitung VII an der Universität Erlangen-Nürnberg besitzt eine fast zehnjährige Erfahrung mit dieser Technik und hat nachgewiesen, daß sich die Feldrechner mittlerweile sehr vielfältig einsetzen lassen.

Ein Feldrechner ist für folgende Problemstellungen geeignet:

- Wenn das Problem beziehungsweise der Lösungsalgorithmus auf Matrizen oder Vektoren abbildbar ist. Hierzu gehört das Lösen von Gleichungssystemen, Finite-Elemente-Methoden, Multigrid-Methoden und so weiter.

- Wenn die Matrizen beliebige Größen haben. Es gibt inzwischen mehrere Möglichkeiten, große Matrizen so zu zerlegen, daß sie von einem kleineren Prozessorfeld optimal bearbeitet werden können. Durch Maskierung können einzelne Prozessoren von der Bearbeitung ausgeblendet werden, so daß auch an den Rändern von Matrizen keine Probleme entstehen.

- Falls bei der Lösung des Problems Teile von Matrizen, zum Beispiel Zeilen oder Spalten, gebraucht werden. Dies ist bei der Multiplikation von Matrizen oder bei der Bildung des Skalarprodukts der Fall.

- Wenn zu einem erheblichen Teil mit logischen Werten gerechnet wird - zum Beispiel bei der Behandlung der Ising-Modelle. Bei logischen Größen werden tatsächlich nur 1-Bit-Werte verarbeitet, was eine extrem hohe Verarbeitungsleistung (Größenordnung 10¹º Operation/Sekunde) zur Folge hat.

- Wenn mit unterschiedlichen Wortlängen gearbeitet wird, wie in der Bildverarbeitung, wo Bildinformation oftmals in 4 oder 8 Bits abgespeichert wird. Möglich sind Wortlängen von 1 bis n Bits, wobei n lediglich von der Größe des zur Verfügung stehenden Speichers abhängt.

- Wenn oft Standardfunktionen wie Quadratwurzel, Logarithmus, Exponentialfunktion, Sinus oder Cosinus gebraucht werden.

Durch den Einsatz neuartiger Algorithmen, sogenannter Bitalgorithmen, ist es möglich, die Quadratwurzel in einer Zeit zu berechnen, die kleiner ist als die Ausführungszeit einer Gleitkommamultiplikation. Für den Logarithmus und die Exponentialfunktion ist dies in der Gleitkommamultiplikationszeit möglich, beim Sinus oder Cosinus liegen die Werte bei der dreifachen Multiplikationszeit. Man erreicht dies dadurch, daß man die Funktionswerte nicht mehr über eine Reihenentwicklung berechnet, sondern auf einfache Operationen wie Addition, Schiebeoperation und Tabellenzugriffe übergeht und die Werte interaktiv berechnet.

Dies sei hier am Beispiel der Quadratwurzel dargestellt: Wir wollen die Wurzel von N = x bestimmen, gesucht ist also x, dabei ist N größer als 0 und kleiner als 1. Haben wir im n-ten Interaktionschritt ein x(n)<N berechnet, mit einem Rest r(n) = N - x(n), dann setzen wir X(n+1) = (x(n) + b(n) + 1)**2. Dabei bedeutet b(n + 1) das Setzen des Bits an der Stelle n+ 1. Wir berechnen jetzt den Rest r(n + 1) = N - (x(n) + b(n)+ 1)**2 = r(n) - (2*x(n)+b(n)+ 1)*b(n+ 1).

Wir müssen jetzt drei Fälle unterscheiden:

r(n + 1) = 0 Die Wurzel ist exakt berechnet. Rechnung bendet

r(n + 1) > 0 b(n + 1) = 1, berechne r(n + 2)

r(n + 1) < 0 b(n + 1) = 0, r(n + 1) = r(n), berechene r(n + 2)

Dabei ist der Ausdruck (2*x(n) + b(n) + 1)*b(n + 1) sehr schnell zu berechnen, da sich 2*x(n) durch einen Linksshift um eine Stelle, + b(n + 1) durch Setzen des Bits an der Stelle n + 1 und * b(n + 1) durch einen Rechtsshift um n+ 1 Stellen realisieren läßt.

Auf ähnlichen Prinzipien beruht die Berechnung der anderen Standardfunktionen. Diese Bitalgorithmen lassen sich mit gewissen Einschränkungen auch auf Rechner übertragen, die byte- oder wortweise arbeiten. Feldrechner sind immer dann sehr gut einsetzbar, wenn einer oder sogar mehrere der oben genannten Aufgabenstellungen zutreffen.

Die Programmierung ist nach einer kurzen Eingewöhnungszeit einfach, da höhere Programmiersprachen, wie zum Beispiel Fortran, mit Erweiterungen für Vektor- und Matrixoperationen zur Verfügung stehen. Die Programme selbst sind sehr übersichtlich und kurz, da unter anderem fast alle Laufschleifen wegfallen.

Es ist relativ schwierig, eine konkrete Aussage über die Leistungsfähigkeit solcher Feldrechner zu machen, da ihre Leistung von der Problemstellung und dem gewählten Lösungsalgorithmus abhängig ist. Wir haben jedoch die Erfahrung gemacht, daß man gegenüber seriellen Großrechnern um eine Zeiteinheit nach unten kommt. Das bedeutet, daß man bei CPU-Zeiten von Stunden am seriellen Rechner, von CPU-Zeiten im Minutenbereich am Feldrechner ausgehen kann.

Typische Vertreter dieses Feldrechnertyps sind der DAP510 von der britischen Firma AMT (Active Memory Technology), der STARAN und der MPP (Massive Parallel Processor) von der amerikanischen Firma Goodyear.