Systolischer Array

Systolischer Array ist die Bezeichnung für ein Pipe-Netzwerk von DPUs (Data Path Units), meist in Matrix-Anordnung, durch welches Datenströme hindurchgetaktet werden – im Gegensatz zum Instruction Systolic Array, durch den Befehle hindurchgeschickt werden.

Der Begriff „systolisch“ soll die Datenströme durch den Array mit dem Blutkreislauf vergleichen, wobei der Taktgeber quasi das pumpende Herz ist. Ein normaler systolischer Array benötigt keine Befehle, da die Operationen in den DPUs per Handshake durch die Ankunft der Daten am jeweiligen DPU-Eingang „transport-triggered“ automatisch ausgelöst werden. (Es gibt auch Mischformen mit instruction-systolischen Anteilen.) Systolische Arrays waren insbesondere in den 1980er Jahren ein beliebtes Forschungsgebiet, insbesondere von Mathematikern. Die damaligen Synthese-Methoden waren deshalb auch ausschließlich algebraischer Natur (bzw. eine lineare Projektion), weshalb die Anwendung systolischer Arrays auf Anwendungen mit regelmäßigen Datenabhängigkeiten beschränkt war, denn diese Synthese-Methoden lieferten nur uniforme lineare Pipes.

Diese Einschränkung der praktischen Anwendbarkeit wurde um 1995 von Rainer Kress aufgehoben durch die Verallgemeinerung des systolischen Array zum „super-systolischen Array“, indem er die algebraischen Methoden durch Simulated Annealing ersetzte. Dadurch wurden nicht-uniforme Pipe-Netzwerke beliebiger Form möglich, wie Zickzack, spiralig, mit Verzweigungen und unendlich vielen beliebigen anderen Formen. Damit hatte hier grobkörniges Reconfigurable Computing Sinn. Vom super-systolischen Array wurde das Xputer Paradigma abgeleitet.

Erfinder waren 1978 Charles Leiserson und H. T. Kung und unter Leitung von Kung wurden in den 1980er Jahren an der Carnegie Mellon University in verschiedenen WARP Projekten das Konzept in Hard- und Software erprobt. 1988 entwickelte sich dort eine Zusammenarbeit mit Intel zum Bau eines Chips (iWARP) der als Rechnerknoten von Parallelcomputern basierend auf systolischen Arrays dienen sollte.

Literatur

• M. Foster, H. Kung: Design of Special-Purpose VLSI Chips: Example and Opinions. Proc. ISCA, La Baule, France, 1980
• R. Kress et al.: A Datapath Synthesis System for the Reconfigurable Datapath Architecture; Asia and South Pacific Design Automation Conference (ASP-DAC'95). Makuhari, Chiba, Japan, Aug./Sept. 1995
• N. Petkov: Systolic Parallel Processing. North-Holland; 1992